كارايي الگوريتم مسيريابي شكسته شده براي شبكه هاي چندبخشي سه طبقه

دسته بندي : علوم پایه » ریاضی
چكيده:
اين مقاله شبكه هاي سويچنگ سه طبقه clos را از نظر احتمال bloking براي ترافيك تصادفي در ارتباطات چند بخشي بررسي مي كند حتي چنانچه سويچ هاي ورودي توانايي چند بخشي را نداشته باشند و نياز داشته باشند به تعداد زياد وغيرمجازي از سويچهاي مياني براي فراهم كردن اين مسيرهايي كه پلاك نشوند مطابق درخواستها مدل احتمالي اين ديد را به ما ميدهد كه احتمال پلاك شدن در آن بسيار كاهش يافته و تقريبا به صفر مي رسد در ضمن اينكه تعداد سويچهاي مياني بسيار كمتر از تعداد تئوريك آن است.
در اين مقاله يك الگوريتم مسيريابي شكسته شده را فعال پلاك شدن در آن معدني شده است براي اينكه قابليت مسيريابي با fanout بالا را برآورده كند. ما همچنين مدل تحليلي را بوسيله شبه سازي كردن شبكه بر روي
فهرست اصطلاحات: چند بخشي، ارزيابي عملكرد، مدل احتمالي، شبكه هاي سويچينگ


معدني:
شبكه هاي clos بخاطر انعطاف پذيري وساده بود نشان بطور گسترده در شبكه هاي تلفن، ارتباطات Data و سيستمهاي محاسبه اي موازي بكار برده مي شوند. كارايي خيلي از برنامه هاي كاربردي بوسيله يك عمل چند بخشي موثر كه پيغامي را به چند دريافت كننده بصورت همزمان مي فرستد بهتر مي شود. به عنوان مثال در سيستمهاي چند پردازنده اي يك متغير همزمان سازي قبل از آنكه پرازنده ا بكارشان ادامه دهند بايد فرستاده شود. همانطوريكه برنامه هاي كاربردي به خدمات چند بخشي موثر كه توسعه پيدا كرده نياز دارند در طي چند سال اخير حتي در شبكه هاي با دامنه عمومي طراحي سيستمهاي سويچينگ كه بطور موثر بادرخواستهاي چندبخشي سروكار دارد نيز اهميت پيدا كرده است.
تلاشهاي زيادي براي سازگار كردن شبكه هاي clos (كه در ابتدا براي ارتباطات نقطه به نقطه توسعه پيدا كرده بودند) براي آنكه با ارتباطات چند بخشي وفق پيدا كنند انجام شده است.شبكه clos چند بخشي با قابليت پلاك نشدن هنوز بسيار گران در نظر گرفته ميشوند براي همين كارايي آن را روي پيكربندي هاي كوچكتر از معمول در نظر نمي گيرند.
يك شبكه clos سه طبقه بوسيله نشان داده مي شود كه سويچهاي طبقه ورودي m سويچهاي لايه مياني و سويچهاي لايه خروجي است، هر كدام از سويچهاي لايه ورودي تاپورت ورودي خارجي دارند و به هر كدام از سويچهاي لايه مياني اتصال دارد بنابراين ارتباط بين طبقه ورودي وطبقه مياني وجود دارد . هر سويچ طبقه خروجي عدد پورت خروجي دارد و به هر كدام از سويچها يك درخواست اتصال نشان داده ميشود به شكل c(x,y) كه در آن x يك سويچ ورودي و را يك مجموعه مقصد از سويچهاي خروجي است.
چندي /1 درجه fanout درخواست ناميده مي شود. به يك مجموعه از درخواستهاي اتصال سازگار گفته مي شود اگر جمع تصادفات هر كدام از سويچهاي ورودي از بزرگتر نباشد وجمع تصادفات كدام از سويچهاي خروجي بزرگتر از نباشد.
يك درخواست با شبكه موجود سازگار است اگر تمام درخواستها و همچنين درخواست جديد سازگار باشد در شكل (1) براي نمونه با پيكربندي موجود سازگار است ولي سازگار نيست جون سويچ خروجي شماره 1 درخواست را قبلا حمل كرده است. يك خط سير براي درخواست اتصال جديد يك درخت است كه سويچ ورودي x را به مجموعه /1 تا سويچ خروجي از ميان سويچهاي مياني متصل مي كند. يك درخواست اتصال قابل هدايت است اگر يك مسير روي تمامي اتصالات بين طبقه اي پيدا كند وبتواند ردر انحصار قرار دهد.
ماسول و جدول براي اولين بار nonblacking محض /1 وشبكه clos سه طبقه قابل بازآيي را براي اتصالات چندگانه كه اتصالات بين هر تعداد از سويچهاي ورودي وسويچيهاي خروجي بوجود مي آورد را معدني كردند.
هرانگ قابليت بازايي وخواص nonblaking شبكه هاي clos چند بخشي را تحت شرايط مختلف ومحدوديت هاي fonout مورد بررسي قرار داد
يانگ وماسول اولين تحليل خود را كه اجازه مي داد سويچهاي هر طبقه براي كاهش نيازهاي سخت افزاري همانند سازي كند را انجام دادند آنها ثابت كردند كه اگر تعداد سويچهاي مياني o(nlogr/logloyr) باشد آنگاه شبكه nonblacking بوجود آمده است كه تمام درخواستها از حداكثر k عدد سويچ مياني استفاده مي كند كه k نيز ثابت مي باشد. علاوه بر مطالعات شبكه هاي clos چندبخشي nonblamking چندين تلاش رويكرد براي تعيين رفتاري blacking شبكه هاي swiching براي ارتباطات نقطه نقطه وجود داشت.
اين تحقيق مدلهاي احتمالي را را كه بصورت نزديكي رفتار شبكه هاي سويچينگ سه طبقه اي را تخمين مي زند را تامين مي كند.
براي ارتباطات چند بخشي هرانگ ولين يك مدل blocking از درخواستهاي چند پخشي قابل بازآرايي را در شبكه clos نقطه به نقطه nonblocking با فرمول c(n,r,2n-1) پيشنهاد كردند. يانگ ووانگ رفتار blaocking درخواستهاي چند پخشي را روي شبكه clos بوسيله بسط دادن مدل بررسي كردند