مسيريابي موازي در شبكه هاي ابر مكعب با گرههاي داراي نقص
چكيده
مفهوم تحمل پذيري خطاي سخت به منظور مشخص نمودن خصيصه مسيريابي موازي معرفي شد. بر
اين مبنا، اينگونه اظهار ميشود كه يك شبكه
G با درجه
يا رتبه d از تحمل پذيري خطاي سخت برخوردار است، البته در صورتي كه با حداكثر d-2
گره نقصدار، هر يك از گرههاي u و v در G بوسيله مسيرهاي- مجزاي-گره ... بيكديگر
متصل شده باشند، جاييكه ... و ... تعداد همسايگان يا نواحي مجاور بدون نقص گرههاي
u و v در G بترتيب ميباشند. ما نشان ميدهيم كه شبكههاي ابرمكعب (معكبهاي
متداخل) به ميزان زيادي از تحمل پذيري خطاي بالايي برخوردار ميباشند و الگوريتمي
را توسعه ميدهند كه تشكيل دهنده ميزان حداكثري مسيرهاي مجزاي - گره در يك شبكه ابر
مكعب داراي نقص ميباشد. الگوريتم ما بر حسب زمان و طول مسيرهاي مجزاي- گره بهينه
گرديده است.
مسيريابي
موازي، بر روي شبكههايي كه از اندازه بزرگي برخوردار ميباشند و در عين حال ممكن
است داراي نقايصي نيز باشند، بعنوان يك مسئله مهم در مطالعه شبكههاي بهم پيوسته
كامپيوتري مطرح است. اين پديده به شبكه ها اجازه ميدهد تا به منظور تحمل گرههاي
معيوب بتوانند مسيرهاي جايگزيني را داشته باشند. مفهوم جديد تحمل پذيري خطاي سخت
شبكه به منظور سنجش تحمل پذيري خطا در شبكههاي بهم پيوسته معرفي شده است و براي
شبكههاي استار يا ستارهاي مورد بررسي قرار گرفته است. در مقاله جاري، ما به
مطالعه تحمل پذيري سخت شبكههاي بهم پيوسته، مخصوصا شبكههاي معروف ابر مكعب، ادامه
ميدهيم.
ابر مكعب
Qn n- ابعادي بوسيله محققين بسياري بصورت گسترده بعنوان يك توپولوژي شبكه بهم
پيوسته براي سيستمهاي چند رايانهاي مورد بررسي قرار گرفته است. مسيريابي موازي بر
روي شبكههاي ابر مكعب بدون گره نقص دار در ابتدا بر اساس آنچه در بخش مرجع (18)
گفته شده است مورد مطالعه قرار گرفت. علاه بر اين، الگوريتمي كه باعث تشكيل مسيرهاي
مجزاي - گره بين جفتهاي منبع- مقصد بصورت منفصل ميشود در بخش مرجع (8، 14)
پيشنهاد شده است. مشكل شناسايي قطر شبكههاي ابر مكعب معيوب در بخش (10، 11) مد نظر
قرار گرفته است. بسياري از الگوريتمهاي ارتباطات تحمل پذيري خطا بر روي مسير يابي
يك به يك متمركز بوده و بر اين مبنا انتشار در شبكههاي ابر مكعب پيشنهاد شده است.
ابر مكعب
Qn n-ابعادي يك نمودار بدون جهت ميباشد كه متشكل از گرههاي 2n
است كه بوسيله اعداد باينري از 0 الي 2n-1 و گرههاي اتصال لبه
n2n-1 مشخص ميشود بگونهاي كه شاخصهاي باينري آن دقيقا به ميزان
يك بيت متفاوت هستند. در صورتي كه دو گره اتصالي در بيت iام (اولين
بيت، چپترين بيت خواهد بود) با هم متفاوت باشند، نام لبه تحت
عنوان i-edge خوانده خواهد شد.
تحمل قدرتمند نقص يكي از ضمايم طبيعي مطالعه تحملپذيري عيوب شبكه و مسيريابي موازي
شبكه بشمار ميآيد. عليالخصوص، چنين مبحثي تحمل پذيري نقص شبكههاي داراي اندازه
بزرگ با گرههاي نقصدار را مورد مطالعه قرار ميدهد. در اين بررسي، ما تحمل پذيري
خطاي سخت شبكههاي ابرمكعبي معروف را مورد مطالعه قرار داده و نشان داديم كه
شبكههاي ابرمكعبي از خصيصه تحمل پذيري قدرتمندي در برابر نقص و خطا برخوردار
ميباشند. بر اين مبنا، ما يك الگوريتم زماني
O(n2) را
توسعه داديم كه براي دو گره بدون نقص مشخص شده u و v در ابرمكعب n- بعدي On با
حداكثر n-2 گره داراي نقص نسبت به ايجاد مسيرهاي بدون نقص مجزاي- گره ... از u به v
اقدام نموده، بگونهاي كه طول مسيرها بوسيله ... محدود و مشخص شده است. پيچيدگي
زماني الگوريتم ما نيز بهينه شده است، چرا كه هر مسير از u به v ممكن است داراي
طولي به بزرگي n باشد و همچنين ممكن است به ميزان n- مسير مجزاي – گره از u به v
وجود داشته باشد. بنابر اين، حتي چاپ اين مسيرها نيز زماني برابر با ... را در بر
خواهند داشت. طول مسيرهاي ايجاد شده بوسيله الگوريتم ما بهينه ميباشد، بگونهاي كه
ميتوانيم نسبت به ايجاد جفتهاي گرهاي u و v در ابر مكعب Qn با n-2 گره داراي نقص
اقدام نمائيم كه براي آن هر مجموعه از n مسير موازي اتصال دهنده u و v حداقل يك
مسير طول ... را خواهد داشت. در نهايت، الگوريتم ما نيازي به دانش قبلي در خصوص
نقايص و شكستهاي پيشين ندارد.
تحمل پذيري قدرتمند نقص براي شبكههايي كه با درجه محدوديت روبرو ميباشند، نظير
شبكههاي حلقوي، شبكههاي بافته و شبكههاي پروانهاي، نسبتا آسانتر است. از طرف
ديگر، تحمل پذيري قدرتمند خطا و نقص براي شبكههاي بدون درجه محدوديت، نظير
شبكههايي كه بر مبناي گراف كيلي (Cayley
graphs) ميباشند، بنظر بسيار مشكلتر است. شبكههاي ابر مكعب و شبكههاي استار يا
ستارهاي دو موردي هستند كه جزء اولين كلاسهاي شبكههايي بشمار ميآيند كه تحمل
پذيري بالاي آنها در مقابل خطا و نقصهاي شبكهاي به اثبات رسيده است. براي
شبكههاي استار، تحمل پذيري قدرتمند نقص بر مبناي پارتيشن متعامد شبكههاي استار
اثبات شد، در حاليكه براي شبكههاي ابرمكعب، تحمل پذيري قوي خطا و نقص توسط پيش
انطباق دقيق نواحي مجاور گرههاي منبع و مقصد ثابت شده است. بر اين مبنا، مطالعه
تحمل پذيري زياد نقايص ديگر شبكههاي سلسله مراتبي با درجه نامحدود قابل توجه خواهد
بود.
