Fault-tolerant routing in hypercubes using probability vectors

J. Al-Sadi, K. Day, M. Ould-Khaoua*

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

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

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


In this paper, we propose a new fault-tolerant routing algorithm for the hypercube, which overcomes the performance limitations of the recently proposed safety vectors algorithm [IEEE Trans. Parallel Distrib. Syst. 9 (4) (1998) 321]. We present first a method for evaluating the k-level unsafety sets SkA for all 1 ≤ k ≤ n in an n-dimensional hypercube. The k-level unsafety set at node A represents the set, SkA, of all nodes at Hamming distance k from A, which are faulty or unreachable from A due to faulty nodes or links. Equipped with these unsafety sets we show how each node calculates numeric probability vectors and uses them to achieve efficient fault-tolerant routing. A probability-based analysis is conducted to prove some properties of the proposed fault-tolerant algorithm. A performance comparison against the safety vectors algorithm, through extensive simulation experiments, reveals that the new algorithm exhibits superior performance in terms of routing distances and percentage of reachability.

اللغة الأصليةEnglish
الصفحات (من إلى)1381-1399
عدد الصفحات19
دوريةParallel Computing
مستوى الصوت27
رقم الإصدار10
المعرِّفات الرقمية للأشياء
حالة النشرPublished - سبتمبر 2001

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1708???
  • ???subjectarea.asjc.1700.1705???
  • ???subjectarea.asjc.1700.1704???
  • ???subjectarea.asjc.1700.1702???


أدرس بدقة موضوعات البحث “Fault-tolerant routing in hypercubes using probability vectors'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا