چکیده:
این مقاله شبکه های سویچنگ سه طبقه 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 و احتمال شرطی میانگین داریم
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 35 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله کارایی الگوریتم مسیریابی شکسته شده برای شبکه های چندبخشی سه طبقه
