تحقیق در مورد کارایی الگوریتم مسیریابی شکسته شده برای شبکه های چندبخشی سه طبقه

بخشی از مقاله

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

چكيده:
اين مقاله شبكه هاي سويچنگ سه طبقه 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 بوسيله بسط دادن مدل بررسي كردند

بخش 2: مقدمات
اين بخشي قسمتي از نتايج قبلي به علاوه تعاريف ونكاتي كه در مدل هاي blocking خودمان استفاده كرديم و يك شماي مسيريابي براي شبكه هاي clos را نشان مي دهد.

‎1st. استراتژي هاي مسيريابي
ما مي توانيم در مورد 3 كلاس از استراتژي هاي مسيريابي براي ارتباطات چند پخشي بحث كنيم. فرض كنيد كه يك درخواست (x,y) با شبكه موجود با فرمول c( سازگار است.اولين الگوريتم مسيريابي اين است كه سويچ مياني را كه هر كدام يك اتصال را با يكي از مقصدها برقرار مي كند را پيدا كنيم. سوي
هاي لايه مياني تحت اين الگوريتم پيش گنجايش خروجي نيازي به قابليت چندپخشي ندارند هوانگ نشان داد كه يك همچين شبكه اي nonbloking است اگر فقط اگر باشد.

از آنجاييكه الگوريتم نيازمند جايگزين كردن درخواستهاي همه پخشي مي باشد فقط در ابتدا ترين لايه يعني را به ورودي ميتواند تعداد زيادي از درخواست هاي جايگزين داشته باشد كه بوسيله سويچ هاي مياني متفاوت هدايت مي شوند در نتيجه تعداد زيادي از سويچ هاي مياني احتمال دارد از طرف سويچ ورودي پلاك شوند.

دومين استراتژي مسيريابي خروج از سيستم را تا زمان نياز به تعويق مي اندازد الگوريتم كندي در fanowt در شبكه clos سه طبقه تلاش مي كشد تا يك سويچ مياني را كه بتواند يك اتصال به تمام مقاصد در سويچهاي خروجي را پيدا كند و نيازي به قابليت همه پخشي در سويچهاي ورودي ندارد در عوض نياز به آن دارد كه سويچ مياني پيدا كند كه هيچ تقاضايي را به تمامي سويچ هاي خروجي مقصد رد y حمل نمي كنند.
هوانگ همچنين نشان داد كه شبكه تحت اين استراتژي nonblocking است اگر و فقط اگر باشد.

تعداد نقاط عرضي براي c(n,r,m) برابر است با mr(2n+r) . بنابراين هر دو الگوريتم مسيريابي به عدد نقطه عرضي نياز دارند. اين واقعيت كه تعداد نقاط عرضي بصورت توان دوم رشد پيدا مي كندن باعث شده است كه شبكه هاي nonblocking در ارتباطات چند پخشي بكار نروند.
دليل اينكه الگوريتم نياز به تعداد زيادي نقطه عرضي براي تشكيل يك سويچ خط عرضي ساده دارد اين است كه آنها از قابليت ظرفيت خروجي در طبقه اول و مياني بعره نمي گيرند.

كلاس آخر از استراتژي ها يك تركيب از دو روش متفاوت است كه اجازه مي دهد تا سويچ ورودي يك درخواست به چندين سويچ مياني ارسال كند و هر كدام از سويچ هاي مياني يك زير مجموعه از مقصد را هدايت مي كنند. به اين وسيله قابليت بهره وري گنجايش خروجي در تمام سه طبقه بعينه مي شود.

B.صفات منيره اتصالات بين طبقه اي
براي شرح وضعيت اتصالات بخش به عنوان مجموعه اي از سويچ هاي مياني قابل دسترسي كه به سويچ ورودي x متصل شده اند و هيچ درخواستي را حمل نمي كنند را مشخص مي كنيم.
در شكل 1 براي مثال را مجموعه اي از سويچ هاي مياني موجود كه متصل شده اند به سويچ خروجي y كه هيچ درخواستي را حمل نمي كند تعريف مي كنيم.
در همان شكل

For a set of out put swite ches:تعريف 1
Y={
الگوريتم fanout كند تقاضاي چند پخشي (x,y) را بوسيله بكاربردن يك سويچ مياني كنترل مي كند.
براي كنترل صحيح درخواست بايد حداقل يك سويچ مياني در وجود داشته باشد.
اين روش اگر اجازه نداشته باشد كه درخواست هاي موجود را دوباره بازآرايي كند نمي تواند درخواست را هدايت كند براي نمونه فكر كنيد يك درخواست به حالت زير داريم: در شكل 1

{5}={2,7,5} {5}=V1 بنابراين سويچ مياني 5 قابل دسترسي است و براي درخواست جديد موجود است.
براي يك درخواست جديد ديگر داريم

بنابراين از اين به بعد نخواهيم توانست درخواست جديد ديگري را توسط سويچ مياني هدايت كنيم.
فرض مي كنيم كه ما فقط الگوريتم fanout كند را بكار مي بريم. سويچ ورودي x دارد حداكثر درخواست به علاوه يك درخواست جديد سازگار به مشخصه (x,y) مي فرستد، از آنجاييكه هر درخواست اجازه دارد فقط از يك سويچ مياني استفاده كند.
سويچ خروجي y در y حداكثر درخواست مقرر براي سازگاري و حداكثر اتصال از نوع اشغال شده دارد. تعداد اتصالات I اشغال شده بستگي به الگوريتم مسير يابي دارد.

يك الگوريتم مسيريابي بصورت محض از يك درخواست چند پخشي براي استفاده از حداكثر k سويچ مياني جلوگيري كند به عنوان مثال سويچ ورودي حداكثر n-1 اتصال I اشغال شده دارد.

C.توزيع درخواست هاي چندپخشي
احتمال پلاك شدن درخواست fanout d قسمت بار داده شده شبكه كه با PB(d) مشخص شده است يك تابع است از 2 پارامتر p1,p2 كه احتمال هاي اينكه يك اتصال 7 ويك اتصال O توسط ديگر تقاضا ها اشغال شده اند هستند. همه اين پارامترها مرتبط با متغيرهاي مستقل مثل ترافيك الگوها و پيكربندي شبكه هستند.
فرض مي كنيم كه يك درگاه ورودي با احتمال Qd از درخواست dfanout و PB(d) احتمال پلاك شدن براي باشد آنگاه بهره وري شبكه ورودي يعني احتمال اشغال درگاه ورودي a مي باشد كه

و تعداد مورد انتظار از درگاهاي ورودي اشغال شده مي باشد.

اگر f(d) را تابع چگالي احتمال درخواست هاي ورودي با d.fanout در تفكر بگيريم آنگاه داريم
فرض كنيد درخواستهاي واگذار شده در سيستم سويچنگ توزيع شده اند با تابع چگالي احتمال g(d) مي توان بدست آورد.
اگر يك الگوريتم مسيريابي اجازه دهد كه يك درخواست چندپخشي از يك سويچ مياني استفاده كند ودرخواستهاي بصورت تصادفي از طريق m سويچ طبقه مياني هدايت شوند آنگه ما را بدست مي آوريم. تعداد درگاههاي خروجي اشغال شده برابر است با ميانگين درجه ظرفيت خروجي باشد.

B را بهره وري شبكه خروجي تعريف مي كنيم كه با احتمال يك درگاه خروجي اشغال شده باشد برابر مي باشد و قابل ذكر است كه
ثابت مي شود كه درخواستها بصورت تصادفي از طريق اتصال O هدايت مي شود بنابراين خواهيم رسيد به رابطه
برخلاف شبكه نقطه به نقطه متقارن بهره وري در يك شبكه چندپخشي ممكن است با بهره وري خروجي فرق كند.ما از روي احتياز يك بهره وري به رنگ را براي نمايش يك بهره وري شبكه عمومي انتخاب مي كنيم. قابل ذكر مي باشد كه ad=b براي شبكه متقارن و d كوچكتر از يك نمي باشد بنابراين b بهره وري شبكه عمومي مي شود.

D-مدل هاي blacking پيشين
تا جائيكه ما اطلاع داريم تمام مدل هاي پلاكينگ براي شبكه هاي clos چند پخشي بر پايه مدل نقطه به نقطه لي كه از نوع پلاكينگ هستند بنا شده اند در اين مدل يك سوئيچ مياني از طرف طبقه ورودي و يا از طرف طبقه خروجي با احتمال 1-( پلاك مي شود.

بنابراين احتمال پلاك شدن براي درخواست يعني اگر تمام سويچ هاي مياني پلاك شده باشند از رابطه زير بدست مي آيد برابر است با (1
اين مدل به غير از چندين مورد در پيش تر موارد تقريب خوبي مي باشد كه آن چندين مورد عبارتند از اينكه، اول از همه شرايط nonblocking سازگار نيست از آنجايي كه آن دارد مقادير غيرصفر مثبت اگر چه m خيلي بزرگ است و شبكه nonblock مي شود در فرمول 1 PB صفر نمي شود وربطي هم باين ندارد كه چند تا سوئيچ مياني در شبكه ها بكار مي رود.

ثانيا مدل به گران هاي بالاي اشغال اتصالات بين طبقه اي توجه نمي كند. با توجه به اينكه يك درخواست سازگار سوئيچ خروجي y را به عنوان مقصد داردوچون سويچ خروجي مي تواند حداكثر n2-1 درخواست به علاوه يك درخواست جديد بيشتر از n2-1 اتصال از نوع O داشته باشد در يك دلخواه مشغول نمي شوند. براي اتصالات بخش I يك منطق مشابه نيز بكار مي رود.

بنابراين بيشينه تعداد آن بستگي به انتخاب الگوريتم مسيريابي دارد. در نهايت مدل به احتمال blocking يك سوئيچ مياني از طرف سوئيچ ورودي يا خروجي توجه مي كند ولي از تاثير پلاك شدن سوئيچ هاي مياني توسط هر 2 سوئيچ ورودي خروجي چشم پوشي مي كند. از آنجائيكه معلوم كرديم كه تعداد اتصالات مشغول پلاك شدن يك سوئيچ مياني بر احتمال پلاك شدن ديگر سوئيچ هاي مياني تاثير مي گذارد در قسمت بعد يك مدل پلاكرينگ با دقت بيشتر را براي شبكه هاي clos چند پخشي براي كامل كردن اين كمبودها پيشنهاد مي كنيم.

III احتمال پلاك شدن شبكه هاي چندپخشي
اين بخش مدل پلاكينگ الگوريتم fanaut كند را در شبكه متقارن c(n,r,m) مطالعه مي كند و نشان مي دهد كه مدل سازگار است با شرايط nonbloking بطوريكه احتمال پلاك شدن در تعداد يكساني از سوئيچ هاي مياني تقريبا به صفر مي رسد.
همانطوري كه در بخش II نشان داده شد يك درخواست چند پخشي (x,y) پلاك مي شوند اگر وفقط اگر باشد.بگذاريد احتمال اينكه سوئيچ ورودي (m-j)xسويچ مياني قابل دسترسي داشته باشد و باشد را پيدا كنيم.

حال احتمال j سوئيچ مياني غيرقابل دسترسي را حساب مي كنيم. سويچهاي مياني قابل دسترسي بصورت تصادفي در ميان m سوئيچ مياني پراكنده و توزيع شده اند كه بوسيله توزيع دو جمله اي (m,p1) تقريب زده مي شود. در تحت شرايطي كه تعداد سوئيچهاي غيرقابل دسترسي بزرگتر از n-1 مي باشد بنابراين احتمال اينكه j سويچ مياني غيرقابل دسترسي باشند از روابط زير بدست مي آيند

‎1st. احتمال اينكه k سويچ مياني آماده باشند.
بگذاريد mxd عدد اتصال O براي درخواست چند پخشي سازگار (x,y) از فكر كنيم ما ويژگي اتصالات بين طبقه اي با يك مشكل اشغالي در mxd سلول از ماتريس مستطيلي را شرح ميدهيم. يك خانه ميتواند به وسيله يك نقطه با احتمال p2 تحت شرايطي كه هر كدام از ستونها حداكثر n-1 نقطه دارند اشغال شود. توزيع اين نقاط در يك ستون مستقل ازتوزيع آنها درستونهاي ديگر فرض مي شود. توزيع آنها به وسيله دوجمله اي تقريب زده مي شود. به يك سطر خالي يا موجودگفته مي شود اگرآن سطر شامل هيچ نقطه اي نباشد. اگر Ed را تعداد سطرهاي خالي بناميم و Aj تعداد نقاط در j امين ستون باشد آنگاه را احتمال خالي بودن k سطر مي ناميم كه از روابط زير بدست مي آيد

ما احتمال خالي بودن k سطر را با استفاده از استنتاج روي d پيدا مي كنيم. ابتدا با توجه به اينكه در يك ستون k سلول خالي يا m-k نقطه داريم:

اگر در رويداد مستقل Ad=h را داشته باشيم، آنگاه وجود دارند راه براي قراردادن h عدد نقطه داخل m سلول از ستون d ام و راه براي قراردادن j-k نقطه از h داخل j سلول كه داخل سطرهاي خالي در mx(d-1)_ زيرماتريس هستند و راه براي قراردادن باقيمانده h-j+k نقطه داخل m-j سلول، همانگونه كه در شكل 2 مي بينيم. بنابراين احتمال شرطي خالي بودن k سطر هست:

استقراء 1: احتمال خالي بودن k سطر در يك ماتريس با ساير mxd ميشود.

زيرا

اثبات: از فرمولهاي 4,3 و احتمال شرطي ميانگين داريم