A unified fault-tolerant routing scheme for a class of cluster networks

Khaled Day*, Bassel Arafeh, Abderezak Touzene

*المؤلف المقابل لهذا العمل

نتاج البحث: المساهمة في مجلةArticleمراجعة النظراء

3 اقتباسات (Scopus)


Large cluster systems with thousands of nodes have become a cost-effective alternative to traditional supercomputers. In these systems cluster nodes are interconnected using high-degree switches. Regular direct interconnection network topologies including tori (k-ary n-cubes) and meshes are among adapted choices for interconnecting these high-degree switches. We propose a generalized fault-tolerant routing scheme for highly connected regular interconnection networks and derive conditions for its applicability. The scheme is based on the availability of efficiently identifiable disjoint routes between network nodes. When routing paths become faulty, alternative disjoint routes are identified and taken. The methods used to identify the routing paths, to propagate failure information, and to switch from a routing path to another incur little communication and computation overhead. If the faults occur reasonably apart in time, then packets are efficiently routed along paths of minimal or near-minimal lengths. In the unlikely case where several faults occur in a short period of time, the scheme still delivers packets but possibly along longer paths. The proposed scheme and its properties are first presented in general terms for any interconnection topology satisfying certain derived connectivity conditions. The applicability of the general scheme is then illustrated on examples of well known regular topologies satisfying the derived connectivity conditions including the binary hypercube, the k-ary n-cube and the star graph networks.

اللغة الأصليةEnglish
الصفحات (من إلى)757-768
عدد الصفحات12
دوريةJournal of Systems Architecture
مستوى الصوت54
رقم الإصدار8
المعرِّفات الرقمية للأشياء
حالة النشرPublished - أغسطس 2008

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.1700.1708???


أدرس بدقة موضوعات البحث “A unified fault-tolerant routing scheme for a class of cluster networks'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا