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

«کارایی الگوریتم مسیریابی شکسته شده برای شبکه های چندبخشی سه طبقه»
چکیده:
این مقاله شبکه های سویچنگ سه طبقه 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 را نشان می دهد.

استراتژی های مسیریابی ما می توانیم در مورد 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 سویچ میانی غیرقابل دسترسی باشند از روابط زیر بدست می آیند احتمال اینکه 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 و احتمال شرطی میانگین داریم از آنجاییکه ستون آخر حداکثر m-k نقطه دارد و زیرماتریس با سایز mx(d-1) حداقل k سطر خالی دارد بنابراین ماتریس mxdk سطر خالی می توان داشته باشد همانطور که در شکل 2 نشان داده شده است.

از این رو مقدار j,h هستند.

که نشان می دهد اگر شبکه تعداد زیادی درخواست fanout داشته باشد ما میتوانیم نشان دهیم که رویدادهای و مستقل از هم هستند.

هر درخواست fanout بزرگ از میان فقط یک سوییچ میانی تحت شرایط الگوریتم fanout کند هدایت می شود هر چند که احتمال اینکه دو یا بیشتر نقطه همزمان سطر را اشغال کنند بالاتر از احتمال آن است که نقاط به شکل یکنواخت در میان تمام سطرها پراکنده شوند.

به عنوان نتیجه رویدادهای وابسته به هم بدون توجه به وابستگی نتایج در دسته بالاگرفتن احتمال پلاکینگ یک کوواریانس مثبت دارند.

احتمال پلاکینگ یک درخواست با d fanout: یک درخواست جدید سازگار (x,y) اگر پلاک میشود تحت شرایط احتمال پلاک شدن این است که هیچ یک از m-j سویچ میانی موجود را با سایز نمونه k وجمعیت m در یک توزیع فوق مقایسات فضایی (k,m,m-j) انتخاب نکنیم قضیه 9: بریا شبکه متقارن c(n,r,m) اگر درجه متوسط fanout d, باشد و مشغولیت شبکه b باشد احتمال پلاکینگ یک درخواست با فرمول (x,y) برای باشد.

اثبات: از استقرا 1 فرمول 3و6 احتمال پلاک شدن یک درخواست سازگار (x,y) برای می باشد، c.شبکه های پلاک نشدنی باسازگاری احتمال پلاک شدن باشد صفر می باشد که با شرط پلاک نشدنی قطعی در بخش II.A سازگار می باشد.

ما برای اثبات سازگاری به استقرا زیر نیاز داریم: استقرا 2: اثبات: ما ثابت می کنیم این استقرا را بوسیله اسنتاج روی d هنگامی که d=1 باشد (مقدار اولیه آن) و m-k>n-1 , ک این یک تناقض است از سازگاری فرض می کنیم برای شاخص جمع زنی اول به ما می دهد و در نهایت اگر باشد آنگاه n-1+k می باشد هنگامی که باشد بنابراین داریم h+k با فرض اینکه مساوی هستند با صفر به ازای تمامی بنابراین pd(m,p2,n,k) سفرهستند قضیه 2: برای یک شبکه clos چند پخشی متقارن بافرمول c(n,r,m) احتمال پلاکینگ با الگوریتم fanoutکند صفر می شود اگر m>(r+1)(n-1) برای این مقدار k بوسیله استقرارء 2 داریم pd(m,p2,n,k)=o به ازای هر d درباره .بنابراین احتمال بلاکینگ برای یک درخواست از fanout d را در استقرار برابر صفر است.

D.

احتمال پلاکنیک برای شبکه های نامتقارن نتایجی را که برای یک شبکه به فرمول c(n,r,m) بدست آمده را می توان برای شبکه نامتقارن تعمیم داد.

ما اثبات را شرح خواهیم داد جزئیات اثبات شبکه متقارن می باشد.

قضیه 3: برای شبکه نامتقارن اگر حد میانی درجه fanout برابر d باشد و مشغولیت a باشد ومسئولیت خروجی شبکه b باشد احتمال پلاکینگ یک درخواست از d fanoutبرابر است با : زیرا اثبات: باتوجه به درخواست سازگار (x,y) برای به ازای سویچ خروجی yey حداکثر درخواست را حمل می کند در استقرا 1 سویچ ورودی x دارد حداکر درخواست را حمل می کند.

الگوریتم مسیریابی شکسته شده یکی از مشکلات الگوریتم با fanout کند این است که احتمالات بلاکینگ برای درخواست با fanout بزرگ در بعضی از بهره وری های شبکه مرجع داده شده بسیار بزرگ باشد بنابراین درخواست fanout بزرگ به ندرت از طریق سیستم یویچینگ هدایت می شود یا اینکه مجبور می شود منتظر بماند تا مشغولیت شبکه به اندازه کافی پایین بیاید تا بتواند درخواست راهدایت کند.

اگر چه ما در خواستهای بزرگ برای fanout را نادر در نظر گرفتیم ولی اینکه برای درخواستهای با fanout بزرگ ما احتمال بلاکینگ بالایی داریم ناخوشایند می باشد.

برای حل کردن این مشکل ما الگوریتم دیگری را بکار می بریم که به ما اجازه می دهد برای فرستادن درخواست از سوئیچ ورودی بیش از یک سویچ میانی برای fanout های بزرگ استفاده شود اگر چه ما نیاز داریم که درخواستهای فرستاده شده تعداد مقاصد یکسانی داشته باشند که البته ممکن است در تعداد درخواستهای بالا استثناتی نیز داشته باشیم.

این امر با نظریه یانگ و ماسون که در آن یک سوئیچ میانی میتوانست به تعداد دلخواهی از سوئیچ های خروجی به شرطی که تعداد سویچ های میانی از یک عدد ثابت مشخص بزرگتر نباشند متفاوت است.

شبکه های بلاک نشدنی برای الگوریتم مسیریابی شکسته قضیه 4: پلاک نشدنی است تحت شرایط الگوریتم مسیریابی شکسته شده با اندازه شکستن s اگر اثبات: N عنصر را به گروههایی با اندازه s (عنصرهای درخواست ها هستند) امکان دارد که گروه آخر تعداد کمتری از s عدد عنصر را داشته باشد) و ما داریم [N/S] گروه.

اینگونه در نظر می گیریم که درخواست (x,y) برای با شبکه موجودی سازگار است.

سویچ ورودی x می تواند در حال حمل درخواست باشد که هر کدام از آنها به حداکثر سویچ میانی مجزا میتواند وصل شده باشند.

بنابراین حداکثر سویچ میانی می تواند درخواست جدید از سویچ ورودی پلاک کند.

Y را به و… می شکنیم بطوریکه ولی اگر به s بخش پذیر نباشد.

اندازه بخش آخر می تواند کمتر از s باشد.

با توجه به یکی از زیر مجموعه های مثل یک سویچ خروجی مثل حداکثر فراخوانی دارد و از این رو اتصال مشغول از نوع O یا سویچ های میانی پلاک شده است.

در بدترین حالت حداکثر سویچ میانی پلاک شده وجود دارند.

درخواست جدید به عدد زیر درخواست تقسیم می شود.

اگر ما کمتاز سویچ میانی نداشته باشیم آن گاه سویچ میانی از طرف سویچ های ورودی و مجموعه سویچهای خروجی که به d=r2 افزایش داده شده اند پلاک نمی شوند (اتمام اثبات) قابل ذکر است که برای s=1 قضیه 4 به شرط پلاک نشدن (non-bloking) الگوریتم pre-paraout کاهش می یابد وبرای s=r2 قضیه ها به الگوریتم fanout کند کاهش پیدا کند.

برای یک شبکه سه طبقه به فرمول c(n,r,m) با به ازای ثابت c شبکه clos چند پخشی تحت روش شکستن پلاک نشدنی میشود.

اگر و همچنین عدد نقطه عرضی داشته باشیم باعث می شود که مزیتی نسبت به دیگر روش های گذشته داشته باشیم.

جدول 1 تعداد سویچهای میان مورد نیاز برای پشتیبانی از نیازهای مسیری پلاک نشدنی را برای استراتژی های مسیریابی نشان میدهد.

تعداد سویچ های میانی را بوسیله انتخاب کردن یک اندازه مناسب برای شکستن بدست می آوریم احتمال بلاک شدن split Routiny اگر چه در قضیه ،بلاک نشدن این طور فرض شده که کران بالای تعداد سویچ میانی برای هدایت درخواستهایی با ظرفیت گنجایش خروجی d هستند اما این فرض در الگوریتم اجباری نمی باشد علاوه بر این هدایت کردن درخواستها از میان سویچ های میانی کمتر اگر ممکن باشد بدون اینکه اثر سویی بر روی دیگر درخواستها داشته باشد تاثیراتی روی بسته بندی درخواستها انجام می دهد.

اگر n تعداد کل درخواستهای تضمین شده در سیستم باشد و Ns تعداد درخواستهای شکسته شده و مقدار مورد انتظار ظرفیت خروجی درخواستهای شکسته شده باشد آنگاه یک اتصال بین طبقه ای از نوع I با احتمال اشغال می شود و یک اتصال بین طبقه ای از نوع O با احتمال اشغال می شود.

احتمال اشغال شدن j عدد لینک از روابط زیر بدست می آید توضیح جدول 1 تعداد سویچ های میانی مورد نیاز برای شبکه بلاک نشدنی با فرمول c(n,r,m) به استراتژی مسیریابی وابسته است اعداد پیوست شده در جدول اندازه تکه ها برای شبکه های بعینه هستند.

احتمال بلاک شدن در خواست های شکسته شده با fanout ds ، یعنی ps(ds) بوسیله استفاده کردن از روابط مشابهی که در قسمتهای پیش استفاده شد محاسبه میشود.

به ازای هاییکه تقاضاهای شکسته شده جزو مجموعه سویچ های خروجی هستند داریم شکستن درخواست، d fanout سبب می شود زیر درخواست با اندازه s و یک درخواست به اندازه تولید شود به عنوان مثال اگر اندازه شکستن را 4 و fanout برای یک درخواست را d در نظر بگیریم خواهیم داشت زیرا درخواست شکسته شده با اندازه اگر d بر sقابل تقسیم باشد فقط [d/s] عدد درخواست شکسته شده با سایز s خواهیم داشت ما میتوانیم بکار ببریم آرگومان مشابهی را اگر را فرض کنیم A/goRITHM 1 split Routiny IN put a request (x,y) Out put return true if routed, otherwisc False 1)n 2)partition Y into 3)for I 4) w 5) return false fi 6) mi 7) od 8) for I 9) Ux 10) 11) od 12) rout 13) return true اگر درخواست شکسته شده ای بلاک شده باشد درخواستی با d fanout بلاک می شود بنابراین می توانیم احتمال بلاک شدن آن را از فرمول زیر بدست آورد.

B(x) را رویداد بلاک شدن زیر درخواست با N(x) , x fanout را روی داد بلاک نشدن زیر درخواست با fanout x در نظر می گیریم.

Oplimal spilitLazy fanoutPre-fanoutrN1224(4)2562711616376(8)1024105532321016(8)709611596464