الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای (2)

سه نیازمندی ابتدایی برای تمام الگوریتم های مسیریابی ضروی هستند. این را در نظر بگیرید که ما یک توپولوژی دینامیک شبکه ای را در نظر گرفته ایم. نیازمندی 1 بر این دلالت دارد که ما باید یک الگوریتم مسیریابی انطباقی بسازیم
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای (2)
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)

 

مترجم: حبیب الله علیخانی
منبع:راسخون




 

نیازمندی های عملیاتی

ما نیازمندی های الگوریتم مسیریابی خود را به صورت زیر گروه بندی کردیم:
بسته ها برای هر جفت منبع- مقصد از گره ها در تمام زمان ها قابلیت مسیریابی دارند.

شبکه بدون بن بست است

شبکه بدون انتها (livelock) است.
سه نیازمندی ابتدایی برای تمام الگوریتم های مسیریابی ضروی هستند. این را در نظر بگیرید که ما یک توپولوژی دینامیک شبکه ای را در نظر گرفته ایم. نیازمندی 1 بر این دلالت دارد که ما باید یک الگوریتم مسیریابی انطباقی بسازیم زیرا مسیرهای استاتیک ایجاد شده بوسیله‌ی الگوریتم های فراموشی نمی تواند در زمان همپوشانی LRL تعبیه شده باشد، خارج گردد. این نوع از LRL ها پورت های خروجی غیر فعالی ایجاد می کند و به مسیر یک بسته وابسته است. بدین صورت یک مانع از سه مانع می تواند ایجاد شود.
نیازمندی دوم اغلب به سهولت و با استفاده از الگوریتم های جبری بر روی توپولوژی های استاتیک، برآوروده می شود اما با استفاده از یک الگوریتم مسیریابی انطباقی و یک توپولوژی دینامیک، تضیمین این موضوع مشکل است. ما یک اثبات ارائه کردیم که نشان می دهد، الگوریتم مسیریابی ما این نیازمندی را برطرف می کند. الگوریتم های انطباقی همچنین قابلیت اتمام کار را بهبود می دهند و بنابراین یک بسته به طور مداوم انحراف پیدا می کند و نمی تواند به مقصدش برسد. این مسئله تنها در الگوریتم هایی رخ می دهد که غیر بهینه اند. ما اطمینان داریم که الگوریتم ما تنها از مسیرهای مینیمم استفاده می کند.
تمام الگوریتم هایی که این سه نیازمندی اولیه را در شبکه‌ی دینامیک، برطرف می کنند، باید انطباقی باشد زیرا مسیر هر بسته ای که اشغال شده است، می تواند بوسیله‌ی حضور پورت های غیر فعال تحت تأثیر قرار گیرد و بنابراین این الگوریتم باید از اطلاعاتی در مورد محل شبکه‌ی محلی استفاده کند. نیازمندی 4 برای اطمینان حاصل کردن از این موضوع است که مسیرهای اطراف LRL یا پورت های غیر فعال زیاد طولانی نیستند. این مسئله موجب می شود تا شبکه به طور اضافی کار کند و این اطمینان نیز حاصل می شود که اتمام کار سیستم اتفاق نمی افتد. برای ضمانت این خاصیت در سیستم ما، ما یک نیازمندی داریم که بوسیله‌ی آن قادر هستیم به روتوری با اتصال کامل برسیم. این مسئله منجر به ایجاد یک گروه از قیود قراردادی LRL می شویم. ما این قیود را در بخش بعدی آدرس دهی می کنیم. علاوه براین، در صورتی که کوتاه ترین مسیرها همواره برای یک بسته مهیا باشد، این ضروری است که چرخش های 180 درجه ای در برخی موارد داشته باشیم. فرض کردن این موضوع که یک بسته از مقصد خود در یک محور تکی، جابجا شود، این بسته به روتوری با یک LRL می رسد که در در طول مقصدش، توسعه یافته است. این مسئله دو مسیر ممکنه ایجاد می کند. مسیری حول LRL که دو حلقه‌ی تنبیهی ایجاد می کند و یا مسیری که بوسیله‌ی آن LRL به میزان 180 درجه می چرخد. وقتی این مسیر حول LRL، کوتاه ترین روش باشد، الگوریتم مسیریابی ما باید اجازه‌ی بوجود آمدن این چرخش را بدهد.

قیود قراردادی LRL

قبل از ایجاد رابطه‌ی مسیریابی، باید یک آگاهی مناسب در مورد این مسئله وجود داشته باشد که در کجا LRL ممکن است قرار داده شود. قوانین موجود در زمینه‌ی LRL، این مسئله را دیکته می کند که توپولوژی متضمن ممکن است تغییر شکل دهند. این مسئله محیطی را تعریف می کند که در آن، الگوریتم مسیریابی باید بدون بن بست باشند و قابلیت مسیریابی نیز داشته باشند. برای جلوگیری از این مسئله که توپولوژی تغییر شکل زیادی پیدا کند و مسیرهای مناسب ایجاد کند، جفت های منبع- مقصد هیچ مسیری ندارند. ما قراردادهای LRL را در روش زیر مقید می کنیم:
یک LRL ممکن است تنها در طول یک سطر یا ستون، جایگزین شود و هیچ اتصال قطری ایجاد نشود. هر سطر و ستون روتور که بوسیله‌ی یک LRL همپوشانی می کند، باید بوسیله‌ی یک حلقه‌ی کامل از روتورهای بدون پورت های خروجی غیر فعال، در بر گرفته شوند. گره هایی که بیان کننده‌ی شروع و خاتمه‌ی LRL است همچنین در مرز حلقه قرار می گیرند. یک مثال نشاندهنده‌ی این حلقه و محل قرارگیری اتصال ممکنه در شکل 1 نشان داده شده است. مادامی که حلقه نقض نشده باشد، LRL با جهات مختلف ممکن است در همان ستون یا سطر جایگزین شوند. در این حالت هیچ حد روشنی برای عدد LRL مجزا وجود ندارد.
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)
این قیود به طور مفهومی تعداد کل LRL ها را که می توانند ایجاد شوند را محدود کرده است. از آنجایی که ما اجازه نمی دهیم تا هیچ گره لبه ای همپوشانی کند، ماکزیمم طول LRL برابر K-2 است که در اینجا، K قطر مش می باشد. همچنین LRL ها نمی توانند در سطرها و ستون های مجاور، قرار داده شوند. بنابراین، عدد کل طول ماکزیمم LRL می تواند با الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) جایگزین شود. بنابراین، عدد کل گره هایی که می توانند همپوشانی کنند، به صورت زیر محاسبه شود:
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)
که در اینجا، 24 تا از 64 گره در شبکه‌ی با مش بندی 8 در 8 قرار داده می شوند. یک مقایسه‌ی واضح میان درجه‌ی آزادی جاگیری LRL و قابلیت مسیریابی وجود دارد: وقتی LRL بیشتری وجود داشته باشند، روش های کمتری برای بسته ها وجود دارد. وقتی قیود آزاد شوند، توپولوژی متضمن می تواند به مقدار بزرگتری تغییر کند و بنابراین، الگوریتم های مسیریابی باید پیچیده تر شوند. در سیستم ما، با اطمینان حاصل کردن از این موضوع که هیچ دو گره مجاور ممکن نیست با LRL های متفاوت وجود داشته باشند، این ممکن است که رابطه‌ی مسیریابی فرض های زیر را در نظر گرفته باشد: اولا، اگر دو پورت خروجی بر روی مسیر مینیمم یک بسته وجود داشته باشد و یکی از آنها غیر فعال باشد، سایر پورت ها در حالت دیفالت قرار دارند. دوما، پورت های خروجی با جهات یکسان بر روی هر گره عمودی مجاور در حالت دیفالت قرار دارند. این مسئله موجب می شود تا الگوریتم مسیریابی بسته را به سمت پورت غیر فعال، سوق داده شود.

رابطه‌ی توپولوژی

این مسئله از توضیحات ارائه شده در زمینه‌ی قیود مسیریابی در بخش بعدی فهمیده می شود که یک الگوریتم مسیریابی متداول به تنهایی کافی نمی باشد. در الگوریتم های طراحی شده برای توپولوژی های استاتیک، برای ساده سازی، این فرض شده است که اگر یک بسته در هر جهتی از مقصدش، جابجا شود، پورت خروجی به سمت جهتی تمایل دارد که مسر مینیمم است. برای مش بندی های غیر منظم که در زمان اضافه شدن LRL ایجاد می شوند، این مسئله ضرورتا صحیح نمی باشد. این پورت ممکن است غیر فعال باشد یا یک بسته را به بیش از یک کانال هدایت می کند. بنابراین، پارتیشن بندی الگوریتم مسیریابی به روابط مسیریابی( R) و تابع انتخاب(S)، ممکن نیست. R باید قادر باشد تا از اطلاعات مربوط به توپولوژی شبکه‌ی کنونی استفاده کند به نحوی که این R می تواند به پورت های قرار گرفته بر روی مسیر مینیمم غیر منظم، بازگشت کنند. همچنین به طور نرمال، S از این نوع از اطلاعات استفاده می کند. روابط مسیریابی انطباقی و مینیمم باید قرارگیری کنونی بسته را از مقصد آن محاسبه کند. سپس، آن کانال هایی که از آن جهات استفاده می کنند( بدون شعبه دار شدن هر قید بازگشتی)، بازگشت داده می شوند.
بنابراین،رابطه‌ی مسیریابی Op-bypass به دو بخش تقسیم می شود. بخش اول(معادله‌ی هفتم) پورت های بهینه را بر روی مسیرهای بهینه‌ی غیر منظم محاسبه می کند و در پورتهای یک روتور که بر روی مسیر بهینه‌ی منظم واقع شده اند، به سختی عمل می کنند( همانگونه که در الگوریتم 1 و 2 نشان داده شده است). توجه کنید که این الگوریتم ها می توانند به عنوان الگوریتم های منفرد مورد استفاده قرار گیرد اما برای افزایش وضوح، ما این الگوریتم ها را به طور مجزا مورد بررسی قرار داده ایم. کدهای کاذب بر روی صفحات بعدی، نشاندهنده‌ی روشی است که بوسیله‌ی آن، یک گروه از کانال های مینرالی غیر منظم(C_min) از گروه کانال های C بر روی مسیر بهینه‌ی منظم، محاسبه می شوند.
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)
که در اینجا، T یک گروه از حالت های ممکنه از توپولوژی های محلی است والگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) پرتوان ترین کانال خروجی بر روی مسیر مینیمم غیر منظم می باشد. بخش بعدی رابطه، قیود چرخش را اعمال می کند تا بدین صورت اطمینان حاصل گردد، شبکه بدون بن بست است. این رابطه در معادله‌ی زیر نشان داده شده است:
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)
که در اینجا، الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) یک گروه از کانال ها بر روی مسیر مینیمم غیر منظم است که در آن قیود چرخش می شکند. توجه کنید کهالگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) است.
الگوریتم 1. محاسبه‌ی پرت های نامنظم و مینیمم برای الگوریتم های مورد استفاده که در آنها یک پورت خروجی بر روی مسیر مینیمم منظم وجود دارد.
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)
الگوریتم 2: محاسبه‌ی پرت های نامنظم و مینیمم برای الگوریتم های مورد استفاده که در آنها دو پورت خروجی بر روی مسیر مینیمم و منظم وجود دارد.
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)
الگوریتم 3. موارد مورد استفاده در تابع انتخاب
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)

Opt-bypass

الگوریتم Op-y بوسیله‌ی Schweibert و Jayasimha ارائه شده است. این الگوریتم به طور کامل انطباقی است و بدون بن بست است. ما از این الگوریتم به عنوان پایه برای کار خودمان استفاده کردیم زیرا نویسندگان نشان دادند که این الگوریتم تعداد مینیمم چرخش های ممنوعه و کانال های مجازی را ارائه کرده اند. بنابراین، این الگوریتم دارای حداقل محدودیت و کمترین هزینه می باشد. ما یک الگوریتم جدید ارائه کرده ایم که Opt-bypass نامیده می شود. این الگوریتم مشابه الگوریتم Op-y است اما علاوه بر آن، دارای اصلاحات و بخش های اضافی نیز هست. این بخش ها به منظور بررسی اثر LRL و اتصالات غیر فعال است که در بخش های بعدی، در مورد آنها صحبت شد.
اصلاحات ما شامل یک کانال مجازی اضافی به نامالگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) است و این بخش شامل چرخش های مجاز یک بسته است. Opt-y اجازه می دهد تا بسته ها در زمانی که دارای مسیریابی کاملا غربی است، هم از کانال های شمالی و جنوبی استفاده کنند. ما هیچ وقت اجازه چرخش صفر درجه را در میان کانال ها و در جهت یکسان را نمی دهیم. این تنها محدودیت اضافی با توجه به استفاده از کانالی می باشد که ما پیشنهاد داده ایم. اجتناب از بن بست در دو الگوریتم بر اساس مدل محدودیت اولین چرخش غربی، توجیه می شود. این مدل نشان می دهد که این الگوریتم از بن بست خالی است. این کار با اطمینان حاصل کردن از این موضوع حاصل می شود که هیچ کانالی نمی تواند به کانال باند غربی وابسته باشد. به دلیل اینکه این کانال ها باید ابتدا از یک مسیر بسته ای استفاده کنند، Op-y از VCs و یک گروه اصلاح شده از محدودیت های چرخشی استفاده می کند و بوسیله‌ی آنها از اجازه می دهد تا رویه‌ی مسیریابی به طور کامل انطباقی باشد و همچنین بدون بن بست باشد.
تنها یک کانال منفرد شرقی وجود دارد( c_(1,E)) اما دوکانال مجازی غربی یعنی الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) والگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) وجود دارد. که علاوه بر انها کانال های اضافی شمالی و جنوبی نیز وجود دارند. یک بخش اضافه شده به Op-y کانال مجازی غربی- ثانویه است. این کانال به زیر تابع مسیریابی R_1 متصل شده است و اکنون کانال هایالگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) ، الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) ، c_(1,E)، الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) ، الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) را تغذیه می کند.
حضور بی نظمی های توپولوژیک می تواند منجر به ایجاد مسیرهایی برای بسته شود که بوسیله‌ی یک پورت غیر فعال یا یک LRL مسدود شده است. این مسدود شدن زمانی رخ می دهد که با یک پورت غیر فعال روبرو شود. در این حالت بسته باید به سمت آن مسیردهی شود. اگر LRL مورد استفاده قرار گیرد، ایم بخش باید تعیین کند که کدام پورت موجب ایجاد حداقل پرش می شود. اگر پورت های دیگری وجود داشته باشند که دارای مسیر مینیمم باشند، پس، بسته باید از طریق آنها مسیردهی شود. اگر تنها پورت موجود در مسیر بهینه، مسدود باشد، رابطه‌ی مسیریابی به دو پورت عمودی باز می گردد زیرا این پورت ها، دو پورت مینیمم غیر منظم هستند. این عمل می تواند منجر به شعبه ای شدن قیود چرخشی شود و موجب پدید آمدن بن بست گردد. قوانین زیر از بروز این بن بست جلوگیری می کند. به دلیل اینکه چرخش های 180 درجه ای در بیشتر الگوریتم های مسیریابی مجاز نمی باشد، ما این مسئله را در بخش 5.5 به طور جزئی مورد بررسی قرار می دهیم.
قیود زیر برای Opt-bypass وجود دارد. این قیود هم اکنون با ایجاد جایگزین های توپولوژیک در ذهن، ساخته می شوند. این قیود قابل پیش بینی نیستند و بسته ها باید قادر باشند تا روش های بهینه‌ی غیر منظم که در اطراف آنها وجود دارد، را دنبال کنند( بدون آنکه وابستگی سیکلی ایجاد کنند). قیود 4 تا 7 نسبت به قیود بیان شده برای Opt-y اکیدی تر هستند. با مقایسه‌ی Opt-y، ما تنها قیود محکم تری برای کانال های موجود ارائه کرده ایم:
چرخش های 90 درجه از الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) به الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) ی غربی قدغن است. این محدودیت چرخش غربی برای جلوگیری کردن از ایجاد وابستگی های سیکلی در نظر گرفته شده است. توجه کنید که چرخش از الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) و الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) به الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) ، قدغن نمی باشد.
کانال های الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) و الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) باید در منبع مورد استفاده قرار گیرند، اگر بسته ای برای مسیردهی به غرب مورد نیاز باشد.
چرخش های صفر درجه از الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) به الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) و از الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) به الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) ممنوع هستند. Opt-y تنها این چرخش ها را در صورتی ممنوع کرده است که بسته ها نیاز به مسیردهی به سمت غرب داشته باشند. ما این چرخش ها را در تمام زمان ها ممنوع کرده ایم. سپس اگر یک بسته در الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) یا الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) نیاز به مسیردهی به غرب داشته باشد، رابطه‌ی مسیردهی تنها به الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) اختصاص دارد و از بروز بن بست جلوگیری می شود. بنابراین، VC 1 برای مسیریابی انطباقی شرق/شمال یا جنوب مورد استفاده قرار می گیرد و VC 2 برای مسیریابی انطباقی غرب، شمال یا جنوب مورد استفاده قرار می گیرد.
یک بسته ممکن است در زمانی که‌ی کانال ترمینال است، از الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) استفاده کند. ضمنا، هر بسته در الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) می تواند چرخش هایی به الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) ایجاد کند. این مسئله این اطمینان را حاصل می کند که الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) از کانالی فرار کرده است که بوسیله‌ی بسته هایی که از الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) استفاده کرده اند، مورد استفاده قرار نگرفته است. این کانال ها ممکن است بعدا برای مسیریابی سایر ابعاد مورد نیاز باشد.
ما همچنین قیودی را تخصیص داده ایم که بوسیله‌ی آنها بسته ها ممکن است در طول LRL مسیردهی شود. همچنین شرایط برای چرخش 180 درجه ای نیز به صورت زیر مهیا می شود:
اگر این اتصال به مقصدش نرسد، یک بسته ممکن است به LRL ارسال گردد
اگر اتصال به مقصدش برسد و بسته نمایش داده شود، بسته ممکن است به LRL ارسال گردد. در حالت، بسته به نحوی نمایش داده می شود که در زمان خروج از LRL، چرخش 180 درجه ای بدست می آورد. روش ما تنها اجازه می دهد تا یک بسته مسیر دهی گردد اگر، مسیر پرش کمتری داشته باشد(الگوریتم 1 را ببینید).
یک بسته ممکن است در LRL ارسال گردد اگر اتصال به مقصدش برسد و بسته بیشتر از یک سمت حرکت کند.

چرخش های 180 درجه ای

الگوریتم مسیریابی اجازه‌ی چرخش های 180 درجه ای را تنها در حالتی می دهد که یک بسته به یک LRL برسد. همانگونه که در بخش قبل گفته شد، برای الگوریتم های مسیریابی، این ضروری است که از چرخش های 180 درجه ای حمایت کند و بدین وسیله بررسی کاملی از صرفه جویی در مصرف انرژی در فعالیت سوئیچینگ، حاصل شود. بیشتر الگوریتم های مسیریابی از چرخش های 180 درجه ای حمایت نمی کنند زیرا آنها می توانند سیکل هایی را در گراف وابستگی ایجاد کنند و بدین وسیله آنها باید به طور کامل در نظر گرفته شوند. هرجایی که یک بسته این چرخش را انجام دهند، این شرایطی است که در نهایت چرخشی غیر صفر قبل از رسیدن به مقصد ایجاد می گردد. یک بسته که این چرخش را انجام داده است، بباید قبل از رسیدن به گره، جذب شود. این جذب با ورود به LRL همره است. این مسئله اطمینان حاصل می کند که این کانال به دیگری دابسته نیست و نمی تواند در یک سیکل وارد شود. علاوه براین، قیود قرارگیری ارائه شده در بخش قبل، این اطمینان را حاصل می کنند که هر ستون و یا سطر که در آن چرخش 180 درجه ای رخ می دهد، نمی تواند در کنار دیگری باشد. از این رو هر وابستگی کانالی 180 درجه ای در حالتی ایزوله ایجاد می شود.
چرخش های شمال- جنوب و جنوب- شمال باید از VC با اندیس یکسان استفاده کنند. در شکل 2 ما امکان ایجاد سیکل بوجود آمده از طریق 4 چرخش 180 درجه ای، نشان داده ایم. در زمانی که الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) بوسیله‌ی بسته‌ی خطا کار مور د استفاده قرار می گیرد، ما الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) را از شکل حذف کرده ایم زیرا این کانال بواسطه‌ی قانون 4، غیر چرخه ای است. همچنین توجه کنید که به دلیل وجود قیود قرارگیری در بخش بعدی، وابستگی های 180 درجه ای این چنینی نمی تواند در ستون ها یا سطرهای مجاور رخ دهد.
الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2)
علاوه براین، یک چرخش 180 درجه ای می تواند به هر بعدی در الگوریتم های مسیریابی پایه گذاری شده بر اساس مدل چرخش ابتدایی غربی(بدون استفاده از زVCs های اضافی یا شرایط کانالی ترمینالی)، اضافه شود. بدون توجه به الگوریتم Opt-bypass، چرخش غرب به شرق می تواند در طول الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) یا الگوریتم مسیریابی بدون بن بست برای چیپ های شبکه ای(2) ،وجود داشته باشد.

تابع انتخاب

همانگونه که در بخش قبلی گفته شد، روابط مسیریابی انطباقی نیازمند یک تابع انتخاب است که بوسیله‌ی آن، یک گروه از کانال های خروجی قابل تنظیم، انتخاب شوند. ما هم اکنون، یکی از توابع انتخاب را معرفی خواهیم کرد. این تابع تابع Xlookahead نامیده می شود. این تابع نسبت به توابع انتخاب دیگر متفاوت است. این تابع تنها از یک داده‌ی اشغال کانال خروجی استفاده می کند و بوسیله‌ی آن، تعیین می کند که کدام بسته‌ی مربوط به کانال خروجی، معتبر است. همانگونه که در بخش قبلی گفته شد، هر روتور با یک پورت که می تواند در حالت اتصال یا انفصال به LRL باشد، بوسیله‌ی یک حلقه از روتورهای محافظتی، تحت محافظت قرار داده شده اند. اگر در روتور مسدود شده، پورت مسدود شده به مسیر مینیمم منظم، متکی نباشد، پس روتور نگهبان می تواند بسته را بدون ایجاد توالی و در طول روتور دیگر، ارسال کند. به هر حال، ما می توانیم ترافیک را به نحوی تقسیم کنیم که هر پورت مسدود بر روی راه مینیمم دو نوع واقع شده باشند:
روتور مسدود شده تنها روتوری باشد که به روتور نگهبان قرار گرفته بر روی مسیر مینیمم موجود برای بسته، قرار دارد.
روتور مسدود شده یکی از دو روتوری است که به نگهبان متصل شده اند. در واقع این روتور نگهبان در طول مسیر مینیمم منظم برای بسته قرار گرفته است.
ترافیک نوع 1 در روتور مسدود شده، باید به میزان 0 درجه بچرخد. و به عبارت دیگر، نگهبان باید دارای دو پورت خروجی بر روی مسیر مینیمم منظم باشد. این نوع از ترافیک در زمانی مد نظر است که می خواهیم اطمینان حاصل کنیم، مقدار کافی از بازده ترافیک از قرارگیری LRL ایجاد شده است. نوع دوم از ترافیک می تواند در زمانی مطلوب باشد که نگهبان در طول مسیر مینیمم منظم قرار گرفته است. این مسئله به دلیل وجود قیود قرارگیری LRL ایجاد شده است. این مسیر باید از حالت مسدود بودن، خارج گردد. این مسئله موجب می شود تا مقدار ترافیکی که به روتور مسدود شده می رسد، کاهش یابد. تابع انتخاب، میزان جهش ها ایجاد شده بوسیله‌ی LRL را کاهش می دهد. این تابع با توجه به الگوریتم 3 کار می کند. گروه کانال های ساختاری مخصوص خروج (c_valid) کاهش داده می شوند و تنها ان دسته از کانال هایی باقی می ماند که موجب می شوند بسته در مرحله‌ی پرش بعدی، مسدود گردد(خط 4، الگوریتم 3). توجه کنید که در یک شبکه‌ی مش بندی که از روابط مسیریابی Opt-bypass استفاده می کنند، حداقل دو کانال به تابع انتخاب حرکت داده می شوند. این عملکرد تابع همچنین اطمینان حاصل می کنند که اگر یکی از کانال ها به روتور دارای LRL هدایت گردد، کوچکترین مسیر ایجاد می شود ( الگوریتم 3- خط 6).
مشابه با رابطه‌ی مسیریابی، داده های توپولوژیک T مورد استفاده قرار گرفته است. این کار نیازمند برخی محاسبات بر پایه‌ی جابجایی بسته از مقصدش، می باشد. Xlookahead ممکن است بعد از اجرای این تابع، به بیش ازیک کانال برگردد. اگر این مسئله اتفاق افتد، کانال های قرار گرفته در سمت محور X، مطلوب هستند. توابع انتخاب دیگری نیز وجود دارند که می توان از آنها استفاده کرد. بعد از اجرای این تابع، این تابع ممکن است از سایر اطلاعات شبکه ای نیز استفاده کنند و همچنین از روش های انتخاب متعارف مانند آنهایی که در بخش قبلی توصیف شد، استفاده می کنند.

اطلاعات در حالت محلی

همانگونه که ما گفته ایم، الگوریتم مسیریابی باید حالت پورت های خروجی محلی را تعیین کنند. ما فرض می کنیم که اطلاعات حالت پورت محلی در هر روتور مهیا شده است. علاوه بر این، ما فرض می کنیم که هر روتور، تنها حالت هر پورت خروجی همسایه را دارد. با استفاده از این اطلاعات، هر گره یک جدول توپولوژی را دارا می باشد. این جدول برای این استفاده می شود تا اطمینان داشته باشیم، قیود قرارگیری مورد تأیید باشند و به اتخاذ تصمیم گیری های مورد نیاز، کمک می کند. همچنین با استفاده از این جدول، این اطمینان حاصل می شود که بسته ها به پورت های خروجی غیرفعال مسیردهی نشوند.
در یک مش بندی دو بعدی استاندارد، هر گره یک جدول دارای 16 مقدار است. در سیستم ما، فرض شده است که حالت هر پورت خروجی بینان کننده‌ی یک عدد صحیح است. در اینجا صفر بیان کننده‌ی این است که پورت غیر فعال است و 1 بیان کننده‌ی این است که پورت خروجی قادر است به صورت پیکربندی مش بندی شده قرار گیرد. وقتی یک پورت خروجی به LRL اتصال یابد، طول LRL در اتصال های استاندارد، برای بیان حالت آن مورد استفاده قرار می گیرد. این همان بیانی است که برای کدگذاری کاذب در بخش 5.4 مورد استفاده قرار می گیرند. حالت پورت ورودی تک بیتی است و این بیان کننده‌ی این است که پورت یک LRL یا یک اتصال استاندارد ایجاد می کند. در نتیجه، هرجایی که یک LRL جدید مورد استفاده قرار گیرد، هر گره از LRL باید به همسایه اش پیغام دهد و بدین وسیله جدول داده های این بخش ها، به روز رسانی می شود. این گره های همسایه می توانند سپس یک گره نگهبان در حول هر گره ایجاد کنند که این گره به یک LRL متصل است یا دارای پورت غیر فعال است.
در یک شبکه‌ی دارای LRL استاندارد، اطلاعات حالت اتصال می تواند قبل از زمان اجرا، ذخیره سازی شود. در LRL دینامیک، اینی ضروری است که هر روتور این داده ها را از همسایه هایش دریافت کند. این مسئله می تواند از طریق خطوط کنترل خارجی یا با عبور بسته های کنترلی در شبکه، اجرا شود. به دلیل اینکه این اطلاعات تنها در زمان نیاز مورد استفاده قرار می گیرند، این روش به سهولت می تواند در شبکه های با اندازه‌ی دلخواه ومرد استفاده قرار گیرد.
استفاده از مطالب این مقاله با ذکر منبع راسخون، بلامانع می باشد.



 

 

نسخه چاپی