مبتدی (مناسب برای درک مفهوم کلی مطلب)

F1889

روتر انحراف بدون بافرمعمولی
مسیریابی انحراف بدون بافر به عنوان جایگزینی برای روتر دارای بافر سنتی در شبکه روی تراشه برای صرفه جویی در هزینه سخت افزار بسیار مورد توجه قرار می گیرد. همانطور که در شکل ۱ نشان داده شده است، معماری روتور انحراف بدون بافر اساسی (BBDR) بر اساس مش دو بعدی در منبع [۱۴] است. معمولا پنج جفت پورت ورودی / خروجی در یک روتر وجود دارد و هر پورت ورودی تنها یک ریجستر دارد. این پورت دارای یک خط لوله سه مرحله ای است. بسته های ورودی پورت های ورودی در رجیستری ها ثبت می شوند و محاسبات مسیریابی به طور موازی برای تصمیم گیری در مورد پورت خروجی توسط الگوریتم خاص اعمال می شود. هنگامی که دو یا چند بسته یک پورت خروجی مشابه را مطرح می کنند، طرح اولویت برای نظارت بر اینکه کدام بسته پورت دلخواه را اشغال می کند، استفاده می شود و سپس تنها یکی از بسته ها را می توان به این پورت فرستاد. بقیه بسته ها به هر یک از پورت های موجود در دسترس منحرف می شوند. سوئیچ میله عرضی روشن می شود که ورودی پورت رابه پورت خروجی مورد نیازمتصل می کند. بدیهی است، طرح اولویت و مکانیزم تخصیص پورت BBDR نقش مهمی در عملکرد آن ایفا می کند و به علاوه منجر به پیچیدگی بالا نیز می شود. به منظور ساده سازی طرح روتر بدون بافر، یک روتر انحرافی بدون بافر بهبود یافته به نام CHIPPER در منبع [۱۵] ارائه شد، که از یک شبکه جایگزینی جدید به جای یک سوئیچ میله عرضی سنتی استفاده کرد تا تخصیص پورت خروجی را تکمیل کند. در همین حال، یک رویکرد کنترل کارآمد جریان با مونتاژ مجدد بسته، برای بهبود عملکرد و دستیابی به آزادی دد لاک طراحی شد. این یک روش پیاده سازی جدید برای مسیریابی انحراف بدون بافرارزان است.با این حال، همانطور که در منبع [۱۳] ذکر شد، انحراف باعث از دست دادن عملکرد مطلوب در شبکه بدون بافر می شود. بنابراین،کاهش مغایرت و انحراف یک مسئله مهم برای روتر انحراف بدون بافر است.
برای کاهش انحراف در مسیریابی انحراف بدون بافر، یک LDBR در منبع[۱۳] با استفاده ازخط اتصال شبکه چند کاناله و مسیریابی انحراف بر اساس مدل فعلی ارائه شد. معماری LDBR در شکل ۲ ارائه داده شده است. خط لوله آن شامل یک مرحله ورودی و مرحله خروجی است و هر مرحله خط لوله یک چرخه برای اجرا می طلبد. شمارنده انتقال فعال H-V تولید کننده سیگنال های tick_h و tick_v برای اتصال مستقیم و اتصال متقابل است.
در مرحله ورودی،یک اجکتور چند کاناله که شامل چهار سوئیچ است برای انتخاب فلیت های خروج استفاده می شود. هر سوئیچ در دو حالت برای اتصال مستقیم و متقابل عمل می کند. حالت اتصال مستقیم زمانی تعیین می شود که یک بسته ورودی باید به مرحله خروجی ارسال شود. حالت اتصال متقابل زمانی تعیین می شود که یک بسته ورودی به روتورمقصد آن وارد می شود و باید دفع شود یا یک بسته محلی باید تزریق شود. در مرحله خروجی، واحد جایگزینی متشکل از دو سوئیچ بود که برای تخصیص پورت های خروجی استفاده می شود. مکانیزم انتخاب در مرحله ورودی و روش مسیریابی مرحله خروجی می تواند به طور موثری تراکم را کاهش دهد. با این حال، منطق پردازش مرحله ورودی برای LDBR منجر به پیچیدگی بالا می شود. علاوه بر این، مسیریابی XY برای LDBR، فقدان یک مکانیسم تعادل بار است که ممکن است معیارهای عملکرد مسیریابی را کاهش دهد.

۳٫ روتر انحراف بدون بافر پیشنهاد شده
همانطور که در شکل ۳ نشان داده شده، معماری LBBDR پیشنهادی کمی از BBDR و LDBR شبکه روی تراشه متفاوت است. دفع فلیت از پورت ورودی محلی زمانی مجاز است که یکی از رجیسترهای ورودی خالی باشد و یک کانال ورودی حداقل آزاد باشد. اگر فلیت ورودی از پورت مسیریابی به روترمقصد خود رسیده باشد،،می تواند از یک پورت خروجی محلی توسط اجکتور محلی چند کاناله دفع شود. در غیر این صورت، الگوریتم مسیریابی انحراف تعادل بار پیشنهادی برای تصمیم گیری در پورت خروجی مورد استفاده قرار می گیرد.این امر توسط گروه تسهیم ساز و غیر تسهیم ساز تکمیل می شود.
بعضی از تعاریف ضروری برای توضیح الگوریتم مسیریابی انحراف تعادل بار پیشنهاد شده ارائه شده است.
تعریف ۱٫ (Xs، Ys)، (Xc، Yc) و (Xd، Yd) برای مختصات مسیریابی فلیت برای گره های منبع، جریان و مقصد در شبکه قرار می گیرند.
تعریف ۲٫ R برای نشانگر تعویض مسیریابی انحراف تعادل بار است.
تابع الگوریتم مسیریابی انحراف تعادل بار پیشنهادی برای تصمیم گیری در پورت های خروجی مسیریابی و داوری و نظارت تراکم پورت های خروجی برای فلیت های ورودی است. این تابع یک شناسه توازن تعادل را در روتر منبع برای کنترل مسیر اولیه X یا Y جهت فلیت استفاده می کند. پس از آن، هر فلیت بر اساس مسیر یابی XY یا YX در شبکه مسیر یابی می شود. هنگامی که مغایرت پورت های خروجی بوجود می آید، یک روش اولویت اول نزدیک تر که بدان معنی است که فلیت نزدیکترین به روتر مقصد در شبکه با بالاترین اولویت است. جزییات الگوریتم مسیر یابی انحراف تعادل بار برای تخصیص پورت و طرح اولویت در الگوریتم ۱ ارائه می شود.
الگوریتم ۱٫ الگوریتم مسیر یابی انحراف تعادل بار
۱: ورودی: فلیت ورودی f از L، E، W، S، N:
۲- خروجی: تخصیص پورت خروجی L، E، W، S، N

شکل ۳ معماری LBBDR
همانطور که در الگوریتم ۱ نشان داده شده است، الگوریتم مسیر یابی انحراف تعادل بار پیشنهادی عمدتا شامل تصمیم گیری اولیه مسیریابی روتر در روتر منبع و روش اولویت نزدیک تر-اولین برای رفع مغایرت پورت های خروجی است. تصور می شود که شرق و غرب بیان جهت X را ایجاد می کنند و جنوب و شمال بیانگر جهت Y در شبکه هستند. ابتدا، فلیت های ورودی از پورت ورودی محلی و پورت های ورودی مسیریابی در ریجسترهای ورودی ثبت می شوند. برای فلیت وارد شده از پورت ورودی محلی، جهت مسیراولیه آن از X یا Y در شبکه بر اساس شناسه R مشخص می شود که یک طرح گسترده از کار ما است. اگر مقدار R برابر با ۰ باشد، فلیت از جهت X درون ناحیه جفت منبع مقصد مسیریابی می شود. در غیر این صورت، از جهت Y مسیریابی می شود. R هنگامی که جهت مسیر اولیه برای هر فلیت تزریق شده از پورت ورودی محلی مشخص می شود، تغییر می کند. با استفاده از این مکانیزم، مغایرت پورت ها می تواند در مقایسه با روش مسیریابی سنتی با یک جهت اولیه، مانند مسیریابی XY، کاهش یابد. برای فلیت های ورودی های از پورت های مسیریابی، آنها با توجه به مسیر XY یا YX در جهت مسیر اولیه X یا Y در شبکه مسیریابی می شوند. بنابراین،تسهیم سازو غیر تسهیم ساز از LBBDR مسئول مسیر یابی فلیت ها در یک جهت خاص و رفع مغایرت پورت های خروجی هستند. روش اولی- نزدیکتر به این معنی است که فلیت نزدیکتر به روتر مقصد با اولویت بالاتر است. این فلیت به پورت مورد نظر منتقل می شود و در اسرع وقت با استفاده از مزیت کاهش بار در شبکه، به روتر مقصد مسیر یابی می شود. هنگامی که بار شبکه کاهش می یابد، انحراف از فلیت ها نیز کاهش خواهد یافت.
۴٫ بحث و تجزیه و تحلیل
به منظور نشان دادن برتری LBBDR، مقایسه های بین الگوریتم مسیریابی معمولی XY و مسیریابی انحراف تعادل بار پیشنهادی در شکل ۴ و ۵ نشان داده شده است. ما مختصرا در مورد مغایرت اختلاف پورت ها و نحوه رفع مغایرت پورت ها برای سه روتر در توپولوژي مش ۲D بحث می کنیم .
شکل ۴ مسیرهای مسیریابی برای رسیدگی به مغایرت پورت های خروجی را برای سه طرح مسیریابی نشان می دهد. فرض بر این است که سه فلیت f1، f2 و f3 از گره منبع (۰، ۲)، (۱،۳) و (۱، ۲) به گره مقصد (۱، ۱)، (۱، ۰) و (۲، ۲) در شبکه به ترتیب مسیر یابی می شوند. مغایرت پورت خروجی در گره (۱، ۲) مطابق با مسیر XY بوجود می آید. همانطور که در شکل ۴ (b) نشان داده شده است، f1 را می توان از مسیر دیگری مسیریابی کرد تا از ایجاد مغایرت پورت در گره (۱، ۲) به دلیل چرخش جهت مسیر اولیه درLBBDR جلوگیری نمود. بنابراین، مغایرت پورت خروجی را می توان در LBBDR کاهش داد.

شکل ۵ مسیرهای مسیریابی برای دو طرح از قدیمی ترین روش های اولویت اول و روش اولویت نزدیک تر-اولین را به منظور حل مغایرت پورت خروجی نشان می دهد. در ادامه بحث مغایرت پورت در گره (۱، ۲)، فرض بر این است که فلیت f1 به گره (۱، ۳) بر اساس طرح اولویت قدیمی ترین-اولین منحرف می شود. در گره (۱، ۳)، پورت خروجی مورد نظر از جنوب با توجه به اولویت بالاتر توسط فلیتf1 به دست می آید و سپس از طریق گره (۱، ۲) به گره مقصد (۱، ۱) مسیر یابی /هدایت می شود. در حالی که فلیت f2 در گره منبع (۱، ۳) به گره (۲، ۳) به دلیل اولویت پایین تر نسبت به فلیت f1 منحرف می شود. سپس از طریق مسیریابی ضروری پنج هوپ در شبکه، به گره مقصد هدایت می شود. بنابراین، تعداد کل هوب های مسیریابی برای فلیت f1 و f2 به گره مقصد در شبکه ۹ است.
برای LBBDR، فلیت f1 دارای اولویت بالاتری نسبت به فلیت f2 است که مطابق با روش اولویت اول-نزدیکتر برای حل مغایرت پورت در گره (۱، ۲) است. بنابراین، پورت خروجی مورد نظر توسط فلیت f1 به دست می آید و به مقصد، فلیت f2 طبق روش اولویت نزدیک تر-اولین برای حل مغایرت پورت ها در گره (۱، ۲)، مسیر یابی می شود. بنابراین، پورت خروجی مورد نظر توسط فلیت f1 به دست می آید و به طور مستقیم به گره مقصد (۱، ۱) هدایت می شود در حالی که فلیت f2 به گره (۰، ۲) منحرف می شود وبه گره مقصد (۱، ۰) از طریق چهار مسیر یابی هوب لازم هدایت می شود. بنابراین، تعداد کل هوب های مسیریابی برای فلیت f1 و f2 به گره مقصد هفت است. هوب های مسیریابی ضروری کمتر برای حل مغایرت پورت های خروجی ، به معنی بار کمتر در شبکه است که برای کاهش انحراف مفید است.