شبکه ‌ابر مکعب مسیریابی موازی

شبکه ‌ابر مکعب مسیریابی موازی – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

مسیریابی موازی  در شبکه ‌های ابر مکعب با گره‌های دارای نقص

چکیده

مفهوم تحمل پذیری خطای سخت به منظور مشخص نمودن خصیصه مسیریابی موازی معرفی شد. بر این مبنا، اینگونه اظهار می‌شود که یک شبکه G با درجه یا رتبه d از تحمل پذیری خطای سخت برخوردار است، البته در صورتی که با حداکثر d-2 گره‌ نقص‌دار، هر یک از گره‌های u و v در G بوسیله مسیرهای- مجزای-گره  بیکدیگر متصل شده باشند، جاییکه  و  تعداد همسایگان یا نواحی مجاور  بدون نقص گره‌های u و v در G بترتیب می‌باشند. ما نشان می‌دهیم که شبکه‌های ابرمکعب (معکب‌های متداخل) به میزان زیادی از تحمل پذیری خطای بالایی برخوردار می‌باشند و الگوریتمی را توسعه می‌دهند که تشکیل دهنده میزان حداکثری مسیرهای مجزای – گره در یک شبکه ابر مکعب دارای نقص می‌باشد. الگوریتم ما بر حسب زمان و طول مسیرهای مجزای- گره بهینه گردیده است.

شبکه ‌ابر مکعب مسیریابی موازی

۱- مقدمه

مسیریابی موازی، بر روی شبکه‌هایی که از اندازه بزرگی برخوردار می‌باشند و در عین حال ممکن است دارای نقایصی نیز باشند، بعنوان یک مسئله مهم در مطالعه شبکه‌های بهم پیوسته کامپیوتری مطرح است. این پدیده به شبکه ‌ها اجازه می‌دهد تا به منظور تحمل گره‌های معیوب بتوانند مسیرهای جایگزینی را داشته باشند. مفهوم جدید تحمل پذیری خطای سخت شبکه به منظور سنجش تحمل پذیری خطا در شبکه‌های بهم پیوسته معرفی شده است و برای شبکه‌های استار یا ستاره‌ای مورد بررسی قرار گرفته است. در مقاله جاری، ما به مطالعه تحمل پذیری سخت شبکه‌های بهم پیوسته، مخصوصا شبکه‌های معروف ابر مکعب، ادامه می‌دهیم.

ابر مکعب Q_n  n– ابعادی بوسیله محققین بسیاری بصورت گسترده بعنوان یک توپولوژی شبکه بهم پیوسته برای سیستمهای چند رایانه‌ای مورد بررسی قرار گرفته است. مسیریابی موازی بر روی شبکه‌های ابر مکعب بدون گره نقص دار در ابتدا بر اساس آنچه در بخش مرجع (۱۸) گفته شده است مورد مطالعه قرار گرفت. علاه بر این، الگوریتمی که باعث تشکیل مسیرهای مجزای – گره بین جفت‌های منبع- مقصد بصورت منفصل می‌شود در بخش مرجع (۸، ۱۴) پیشنهاد شده است. مشکل شناسایی قطر شبکه‌های ابر مکعب معیوب در بخش (۱۰، ۱۱) مد نظر قرار گرفته است. بسیاری از الگوریتمهای ارتباطات تحمل پذیری خطا بر روی مسیر یابی یک به یک متمرکز بوده  و بر این مبنا انتشار در شبکه‌های ابر مکعب پیشنهاد شده است.

این مقاله بشرح ذیل طبقه‌بندی شده است. ایده‌ها و اصطلاحات در بخش ۲ معرفی می‌شوند. در بخش ۳، ما مسیرهای موازی بین دو گره دارای نقص را مورد بحث قرار می‌دهیم. در حالتی که هیچگونه نواحی مجاور  معیوبی برای گره‌های منبع و مقصد موجود نباشند، ما با استفاده از یک فرآیند نسبت به پیش مزدوج سازی نواحی مجاور  گره‌های منبع و مقصد اقدام می‌نمائیم که بنام Prematch-I خوانده می‌شود. موقعیت خاصی نیز وجود دارد که ممکن است کلیه مجموعه‌های ممکن مسیرهای موازی بین دو ناحیه مجاور گره‌های منبع و مقصد شامل شده از  Prematch-I را بلوکه نماید.  در این موقعیت، ما از فرآیند متفاوت دیگری استفاده می‌کنیم که بنام Prematch-II خوانده می‌شود. فرآیند سومی نیز بنام Prematch-III وجود دارد که در بردارنده موردی است که در آن حداقل یک مجاور دارای نقص منبع یا مقصد وجود دارد. این الگوریتم در بخش ۴ ارائه و مورد بحث قرار می‌گیرد. بخش نهایی نیز به نتیجه‌گیری این مقاله می‌پردازد.

شبکه ‌ابر مکعب مسیریابی موازی

۲- مضامین مقدماتی

ابر مکعب Q_n  n-ابعادی یک نمودار بدون جهت می‌باشد که متشکل از گره‌های ۲ⁿ است که بوسیله اعداد باینری از ۰ الی ۲ⁿ-1 و گره‌های اتصال لبه n2^n-1 مشخص می‌شود بگونه‌ای که شاخص‌های باینری آن دقیقا به میزان یک بیت متفاوت هستند. در صورتی که دو گره اتصالی در بیت iام (اولین بیت، ‌چپ‌ترین بیت خواهد بود) با هم متفاوت باشند، نام لبه تحت عنوان i-edge خوانده خواهد شد. فاصله هامینگ (Hamming) بین دو گره u و v، (u,v)dist ، طول کوتاه‌ترین مسیر از u به v می‌باشد. بطور حقیقی، (u,v)dist تعداد بیت‌هایی است که در آن شاخص‌های باینری u و v متفاوت هستند. از آنجاییکه ابر مکعب Q_n بصورت راس- متقارن می‌باشد، مجموعه‌ای از مسیرهای مجزای – گره از گره   به گره  را می‌توان به یک مجموعه مسیرهای مجزای – گره از گره  به گره  بروشی مستقیم نگاشت نمود، جاییکه . بنابر این، ما بر روی ایجاد مسیرهای مجزای- گره از گره u به گره v در Q_n تمرکز خواهیم داشت.

۳- مسیرهای موازی بین دو گره بدون نقص

در این بخش، ما نشان خواهیم داد که چگونه مجموعه‌ای از مسیرها بین دو گره بدون نقص u و v در شبکه Q_n را می‌توان ایجاد نمود.

الگوریتم مسیریابی موازی ما بر مبنای جفت موثر نواحی مجاور  گره  و  می‌باشد. ما در ابتدا در نظر می‌گیریم که گره‌های u و v دارای هیچگونه نواحی مجاور  نقص دار نمی‌باشند. ما بر مبنای استراتژی ذیل نواحی مجاور  u و v را جفت می‌کنیم.

Prematch-I

{فرضیه : u و v دارای هیچگونه نواحی مجاور  ناقص نمی‌باشند.}

1. جفت نمودن u_i با v_i1- برای

2. جفت نمودن u_j با v_j برای

تحت مزدوج سازی ارائه شده در Prematch-I، ما مسیرهای موازی بین نواحی مجاور  جفت شده u و v با استفاده از رویه ذیل را بوجود می‌آوریم.

شبکه ‌ابر مکعب مسیریابی موازی

۴- الگوریتم مسیریابی موازی بر روی شبکه‌های ابر مکعب نقص‌دار

در ابتدا، کرانه پایینی طول  مسیرهای مجزای- گره از یک گره  تا یک گره  در ابر مکعب Q_n را در نظر بگیرید که در آن  می‌باشد. همچنین یک گره مجاور  را بعنوان گره بدون نقص در نظر گرفته وتصور کنید تا خواسته باشیم مسیری را از u به v از طریق u_i بیابیم. در نظر بگیرید که کلیه نواحی مجاور u_i دارای نقص می‌باشند، بجز دو گره u و ، . پس، یک مسیر بدون عیب از قالب  از u به v دارای طولی حداقل به میزان  می‌باشد. بنابر این، طول مسیرهای مجزای  از u به v حداقل  می‌باشد.

ما هم اکنون آماده هستیم تا الگوریتم اصلی خود برای مسیریابی موازی در شبکه‌های ابر مکعب Q_n با حداکثر n-2 گره نقص‌دار را ارائه نمائیم. برای دو گره بدون نقص   و  در Q_n، الگوریتم ما بوجود آورند مسیرهای عاری از نقص مجزای – گره  از u به v می‌باشند، بگونه‌ای که طول مسیرها بوسیله  محدود می‌شود. این الگوریتم بنام Parallel-Routing (مسیریابی موازی) خوانده شده و در شکل ۳ نشان داده می‌شود.

شبکه ‌ابر مکعب مسیریابی موازی

۵- نتیجه‌گیری

تحمل قدرتمند نقص یکی از ضمایم طبیعی مطالعه تحمل‌پذیری عیوب شبکه و مسیریابی موازی شبکه بشمار می‌آید. علی‌الخصوص، چنین مبحثی تحمل پذیری نقص شبکه‌های دارای اندازه بزرگ با گره‌های نقص‌دار را مورد مطالعه قرار می‌دهد. در این بررسی، ما تحمل پذیری خطای سخت شبکه‌های ابرمکعبی معروف را مورد مطالعه قرار داده و نشان دادیم که شبکه‌های ابرمکعبی از خصیصه تحمل پذیری قدرتمندی در برابر نقص و خطا برخوردار می‌باشند. بر این مبنا، ما یک الگوریتم زمانی O(n²) را توسعه دادیم که برای دو گره بدون نقص مشخص شده u و v در ابرمکعب n– بعدی O_n با حداکثر n-2 گره دارای نقص نسبت به ایجاد مسیرهای بدون نقص مجزای- گره  از u به v اقدام نموده، بگونه‌ای که طول مسیرها بوسیله  محدود و مشخص شده است. پیچیدگی زمانی الگوریتم ما نیز بهینه شده است، چرا که هر مسیر از u به v ممکن است دارای طولی به بزرگی n باشد و همچنین ممکن است به میزان n– مسیر مجزای – گره از u به v وجود داشته باشد. بنابر این، حتی چاپ این مسیرها نیز زمانی برابر با  را در بر خواهند داشت. طول مسیرهای ایجاد شده بوسیله الگوریتم ما بهینه می‌باشد، بگونه‌ای که می‌توانیم نسبت به ایجاد جفت‌های گر‌های u و v در ابر مکعب Q_n با n-2 گره دارای نقص اقدام نمائیم که برای آن هر مجموعه از n مسیر موازی اتصال دهنده u و v حداقل یک مسیر طول  را خواهد داشت. در نهایت، الگوریتم ما نیازی به دانش قبلی در خصوص نقایص و شکستهای پیشین ندارد.

تحمل پذیری قدرتمند نقص برای شبکه‌هایی که با درجه محدودیت روبرو می‌باشند، نظیر شبکه‌های حلقوی، شبکه‌های بافته و شبکه‌های پروانه‌ای، نسبتا آسان‌تر است. از طرف دیگر،  تحمل پذیری قدرتمند خطا و نقص برای شبکه‌های بدون درجه محدودیت، نظیر شبکه‌هایی که بر مبنای گراف کیلی (Cayley graphs) می‌باشند، بنظر بسیار مشکل‌تر است. شبکه‌های ابر مکعب و شبکه‌های استار یا ستاره‌ای دو موردی هستند که جزء اولین کلاسهای شبکه‌هایی بشمار می‌آیند که تحمل پذیری بالای آنها در مقابل خطا و نقص‌های شبکه‌ای به اثبات رسیده است. برای شبکه‌های استار، تحمل پذیری قدرتمند نقص بر مبنای پارتیشن متعامد شبکه‌های استار اثبات شد، در حالیکه برای شبکه‌های ابرمکعب، تحمل پذیری قوی خطا و نقص توسط پیش انطباق دقیق نواحی مجاور گره‌های منبع و مقصد ثابت شده است. بر این مبنا، مطالعه تحمل پذیری زیاد نقایص دیگر شبکه‌های سلسله مراتبی با درجه نامحدود قابل توجه خواهد بود.