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

مسیریابی موازی در شبكه ‌های ابر مكعب با گره‌های دارای نقص – ایران ترجمه – Irantarjomeh

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

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

مقالات رایگان

مطالعه 20 الی 100% رایگان مقالات ترجمه شده

1- قابلیت مطالعه رایگان 20 الی 100 درصدی مقالات 2- قابلیت سفارش فایل های این ترجمه با قیمتی مناسب مشتمل بر 3 فایل: pdf انگیسی و فارسی مقاله همراه با msword فارسی -- تذکر: برای استفاده گسترده تر کاربران گرامی از مقالات آماده ترجمه شده، قیمت خرید این مقالات بسیار کمتر از قیمت سفارش ترجمه می باشد.  

چگونگی سفارش

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

www.irantarjomeh.com

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

دپارتمان مهندسی كامپیوتر، دانشگاه A&M تگزاس

2002

چكیده

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

1- مقدمه

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

ابر مكعب Q_n  n– ابعادی بوسیله محققین بسیاری بصورت گسترده بعنوان یك توپولوژی شبكه بهم پیوسته برای سیستمهای چند رایانه‌ای مورد بررسی قرار گرفته است. مسیریابی موازی بر روی شبكه‌های ابر مكعب بدون گره نقص دار در ابتدا بر اساس آنچه در بخش مرجع (18) گفته شده است مورد مطالعه قرار گرفت. علاه بر این، الگوریتمی كه باعث تشكیل مسیرهای مجزای – گره بین جفت‌های منبع- مقصد بصورت منفصل می‌شود در بخش مرجع (8، 14) پیشنهاد شده است. مشكل شناسایی قطر شبكه‌های ابر مكعب معیوب در بخش (10، 11) مد نظر قرار گرفته است. بسیاری از الگوریتمهای ارتباطات تحمل پذیری خطا بر روی مسیر یابی یك به یك متمركز بوده  و بر این مبنا انتشار در شبكه‌های ابر مكعب پیشنهاد شده است.

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

مطالعه تحمل پذیری خطای شدید در شبكه‌های استار نشان داد كه مسیرهای مجزای- گره را می‌توان بصورت موثر بر مبنای تفكیك یا پارتیشن متعامد شبكه‌های استار با خطاهای آن بوجود آورد كه تفكیك كننده شبكه n-استاری در شبكه‌های ابعادی ساب‌استار n-1(n-1) و یك مجموعه مستقل I از گره‌های (n-1)! می‌باشد. صرف نظر از جرئیات، یك مسیر از ناحیه مجاور بدون نقص گره منبع u به یك مجاور بدون نقص گره مقصد v در یك شبكه ابعادی ساب‌استار (n-1) مجزا ساخته شده است و مجموعه مستقل I كمك خواهد نمود تا مسیرها از یك گره مناسب به ساب‌استار وارد شوند. الگوریتم پیشنهاد شده در (15) بوجود آورنده تعداد حداكثری مسیرهای مجزای- گره با طول تقریبا بهینه در شبكه‌های n– استاری با حداكثرn-3 گره نقص دار می‌باشد.

ما مشاهده می‌كنیم كه تكنیكهای بكار رفته شده در مطالعات قبلی در زمینه شبكه‌های استار برای شبكه‌های ابر مكعبی قابل كاربرد نمی‌باشند. مخصوصا، شبكه‌های ابر مكعب بنظر دارای ساختار تجزیه متعامد مشابهی نیستند. مسیریابی موازی در شبكه‌های ابر مكعب n– ابعادی ممكن است نیازمند ایجاد مسیرهای مجزای n– گره‌ای باشند، در حالیكه یك شبكه ابر مكعب n– بعدی را می‌توان به حداكثر n(n-1) زیرمعكب ابعادی تجزیه نمود. بنابر این، ممكن است گره بیشتری برای كمك به توزیع مسیرها به زیرمكعبها وجود نداشته باشد.

ما تكنیكهای جدیدی را توسعه داده‌ایم كه سبب بوجود آوردن مسیرهای مجزای- گره بین جفت‌های نواحی مجاور  گره منبع u و گره مقصد v شده است. در ابتدا، فرآیند Prematch باعث جفت شدگی نواحی مجاور  بدون نقص u و v در Q_n می‌شود. برای جفتهای بیان شده نواحی مجاور  u و v، ما سه رویه را برای ایجاد مسیرها بوسیله جایگشت یا شیفت دنباله‌های لبه بین آنها معرفی می‌كنیم. مسیرهای مجزای – گره بوسیله جستجوی مسیرهای مناسب، و اطمینان از آنكه هر گره در مسیر بوسیله مسیرهای دیگر مورد استفاده قرار نگرفته است، ایجاد می‌شود. الگوریتم ما نسبت به ایجاد مسیرهای مجزای – گره در زمان بهینه اقدام می‌نماید و طول مسیرها نیز همچنین در شبكه ابر مكعب Q_n بهینه می‌باشد. برای هر دو گره‌های بدون نقص u و v در Q_n، این الگوریتم مسیرهای مجزای – گره  با طول حداقل بعلاوه 4 بین u و v در زمان O(n²) را ایجاد می‌نماید.

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

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

ابر مكعب Q_n  n-ابعادی یك نمودار بدون جهت می‌باشد كه متشكل از گره‌های 2ⁿ است كه بوسیله اعداد باینری از 0 الی 2ⁿ-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 تمركز خواهیم داشت.

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

در این بخش، ما نشان خواهیم داد كه چگونه مجموعه‌ای از مسیرها بین دو گره بدون نقص 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 با استفاده از رویه ذیل را بوجود می‌آوریم.

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

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

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

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

تحمل قدرتمند نقص یكی از ضمایم طبیعی مطالعه تحمل‌پذیری عیوب شبكه و مسیریابی موازی شبكه بشمار می‌آید. علی‌الخصوص، چنین مبحثی تحمل پذیری نقص شبكه‌های دارای اندازه بزرگ با گره‌های نقص‌دار را مورد مطالعه قرار می‌دهد. در این بررسی، ما تحمل پذیری خطای سخت شبكه‌های ابرمكعبی معروف را مورد مطالعه قرار داده و نشان دادیم كه شبكه‌های ابرمكعبی از خصیصه تحمل پذیری قدرتمندی در برابر نقص و خطا برخوردار می‌باشند. بر این مبنا، ما یك الگوریتم زمانی 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) می‌باشند، بنظر بسیار مشكل‌تر است. شبكه‌های ابر مكعب و شبكه‌های استار یا ستاره‌ای دو موردی هستند كه جزء اولین كلاسهای شبكه‌هایی بشمار می‌آیند كه تحمل پذیری بالای آنها در مقابل خطا و نقص‌های شبكه‌ای به اثبات رسیده است. برای شبكه‌های استار، تحمل پذیری قدرتمند نقص بر مبنای پارتیشن متعامد شبكه‌های استار اثبات شد، در حالیكه برای شبكه‌های ابرمكعب، تحمل پذیری قوی خطا و نقص توسط پیش انطباق دقیق نواحی مجاور گره‌های منبع و مقصد ثابت شده است. بر این مبنا، مطالعه تحمل پذیری زیاد نقایص دیگر شبكه‌های سلسله مراتبی با درجه نامحدود قابل توجه خواهد بود.