سفر به اعماق پروتکل های مسیریابی: Link State ها (۲)

سلام به همه ی همراهان عزیز. اگر از مطلب قبل یادتون باشه، گفتیم که پیچیده ترین و مهم ترین بخش عملکرد Link State ها مربوط می شد به جریان Link State Information ها در ساختار. و گفتیم برای این که این جریان درست انجام بشه از فیلدهایی داخل فرمت Link State Information (اگر براتون سواله که چرا من از لفظ Link State Information استفاده می کنم، در قسمت قبل این موضوع رو توضیح دادم 🙂 ) استفاده می شد که یکی از اون ها Sequence Number بود. طراحی عملکرد این فیلد تاثیر زیادی بر نحوه ی فلودینگ Link State Information ها میذاشت. به همین دلیل مدل های مختلفی برای نحوه ی عملکرد این فیلد معرفی شد که عبارت بودند از : Linear , Circular و Lollipop. قصد داریم تا در این مطلب، با هم این مدل ها رو بررسی کنیم.

***

• در نظر گرفتن فضای خطی برای Sequence Number:

در این مدل تصمیم بر آن شد که مقدار فیلد Sequence Number در یک بازه ی خطی متناهی از اعداد مثبت قرار داشته باشد. بنابراین اینطور در نظر گرفته شد که اگر Sequence Number، یک فیلد N بیتی باشد مثلا 32 بیتی، حداکثر مقداری که می تواند در آن قرار گیرد: 4,293,967,296=2³² ‏‎ خواهد بود. ‏پس بازه ی خطی از 0 شروع شده و تا ‏‎4,293,967,296 ادامه می یابد و شمارش Sequence Number هم از صفر شروع شده تا به حداکثر این بازه برسد.

در این روش اگر چند Link State Information یکسان با Sequence Number های مختلف دریافت می گردید، Link State Information با Sequence Number بزرگتر جدیدتر در نظر گرفته می شد. اما این مدل دو مشکل بزرگ داشت: اول این که در این مدل، بازه به صورت متناهی در نظر گرفته شده بود و  زمان طراحی این مدل فرض بر این بود که مقدار حداکثر بازه، آنقدر بزرگ است که روتر ‏به این مقدار حداکثر نمی رسد. اما این موضوع در نظر گرفته نشد که روتر یک دستگاه است و ممکن است دچار تداخل در عملکرد شده و همین امر باعث شود که مقدار Sequence Number به حداکثر مقدار تعیین شده برای آن برسد. در این صورت اتفاقی که رخ می داد آن بود که کل فرآیند از ‏کار می افتاد و آنقدر منتظر می ماند تا ‏Age‏ آنLink State Information ‎  در تمام ‏دیتابیس ها منقضی شده و حذف شود و حال فرآیند می توانست نمونه ی جدیدی از آنLink State Information ‎  با مقدار حداقل برای Sequence Number را تولید و ارسال نماید.

‏از سوی دیگر مساله ی بعدی که در نظر گرفته نشد آن بود که: اگر روتر در میانه ی کار ریستارت ‏می شد، دوباره شمارش را از 0 شروع می کرد (یعنی سر این بازه) اما همسایه های آن روتر در دیتابیس های خود همان ‎ ‎Link State Information ‎  قبل از ریستارت شدن را داشتند که مقدار Sequence Number برای آن قطعا بیشتر از صفر بود. پس هر ‎ Link State Information ‎  ای که از جانب روتر ریستارت ‏شده برای همسایه هایش ارسال می شد، از جانب همسایه ها رد می گردید. برای همین قانونی مطرح کردند که اگر روتری ریستارت شد و‎ Link State Information ‎ با ‎ Sequence Number ای کمتر از ‎ Sequence Number آنLink State Information ‎  در دیتابیس همسایه ها ارسال کرد، روترهای همسایه متوجه می شوند که آن روتر ریستارت شده و‎ Link State Information ‎ای که در دیتابیس خود ‏دارند را برای آن روتر ارسال می کنند تا به این روش روتر ریستارت شده از آخرین ‎ Sequence Number باخبر شده و شمارش را از همانجا شروع کند.

اما باز ‏هم اینجا یک مشکل وجود داشت: اگر مقدار‎ Sequence Numberبه مقدار حداکثر بازه نزدیک شده باشد چه اتفاقی می افتد؟ اینگونه باز هم روتر ‏ریستارت می شد. پس باید یک حداکثری برای تعداد دفعات ریستارت شدن هم در نظر گرفته می شد‎. پس با این اوصاف دو مشکل وجود داشت: یکی آن که بازه متناهی بود و ممکن بود مقدار Sequence Number به حداکثر بازه برسد، و دوم مشکل ریستارت شدن روتر در میانه ی کار بود.

• در نظر گرفتن فضای مدور:

به دلایل مشکلات روش خطی، روش دیگری با نام بازه ی مدور معرفی گردید. در این روش از یک فضای نامتناهی از اعداد مثبت برای مقدار Sequence Number استفاده شد به این صورت که همیشه Sequence Number در بازه ای بین 0 تا 0 قرار داشت. پس اگر فیلد Sequence Number به عنوان مثال 6 بیتی باشد، حداکثر مقداری که در این فیلد می تواند قرار بگیرد برابر است با: 64= 2⁶ و وقتی روتر  به این مقدار حداکثر برسد دوباره به صفر بازمی گردد. در نتیجه همانند روش خطی، فرآیند از کار نمی افتد تا سن Link State Information به پایان رسد و سپس مجددا شمارش از صفر شروع شود.

 در این روش به منظور تشخیص Link State Information جدیدتر از قانونی استفاده شد که اینگونه بیان می کرد که: اگر از یک Link State Information یکسان دو نمونه با Sequence Number های متفاوت دریافت شد، مقدار Sequence Number ها را از هم کم کن. اگر حاصل این تفریق از نصف حداکثر بازه بزرگتر بود، Link State Information ای با Sequence Number کم تر به عنوان Link State Information جدیدتر انتخاب گردد و اگر حاصل تفریق از نصف حداکثر بازه کوچکتر یا مساوی آن بود، Link State Information ای با Sequence Number بزرگتر به عنوان Link State Information جدیدتر در نظر گرفته شود.

 با یک مثال نحوه ی عملکرد این روش را با هم بررسی کنیم: فرض کنیم فیلد Sequence Number، شش بیتی در نظر گرفته شده، در نتیجه حداکثر بازه برابر است با: 64=2⁶ و نصف این مقدار می شود: 32=64/2 . حال اگر همزمان روتر دو نمونه از یک Link State Information با Sequence Number هایی برابر 40 و 18 دریافت کند، بر طبق قانون اینگونه محاسبه می کند که: 22=18-40 و 22 نیز کوچکتر از 32 (یعنی نصف بازه است) پس Link State Information ای که Sequence Number بزرگتر دارد جدیدتر می باشد، بنابراین Link State Information با Sequence Number برابر 40 را به دیتابیس خود اضافه می کند. حال اگر یک نمونه دیگر از همین Link State Information ولی با Sequence Number ای با مقدار 5 به دست روتر رسد محاسبات را مجددا به اینصورت انجام می دهد که: 35=5-40 و 35 بزرگتر از 32 است در نتیجه، Link State Information ای که به تازگی به دستش رسید با Sequence Number ای برابر 5 را جدیدتر درنظر می گیرد و به دیتابیس خود اضافه می کند.

 در شرایط عادی این روش درست کار می کرد اما باز هم دو نکته فراموش شد:اول این که روتر یک دستگاه است و ممکن است دچار تداخل در عملکرد شود و این قوانین برای پیدا کردن جدیدترین Link State Information دیگر جوابگو نباشند.

مثلا فرض کنید روتری در شبکه دچار تداخل در عملکرد شود و از یک Link State Information چندین نمونه با Sequence Number های یکسان، مثلا 56 در شبکه flood کند. از سوی دیگر همسایه ی این روتر هم دچار تداخل در عملکرد شده و بیت ها را drop کند، مثلا از یک Link State Information بیت دوم از سمت چپ در فیلد Sequence Number را drop کند که در این صورت مقدار Sequence Number می شود 40 و از یک Link State Information دیگر نیز دو بیت اول از سمت چپ در فیلد Sequence Number را drop کند که در این صورت مقدار Sequence Number برابر می شود با 8 و به این ترتیب سه Link State Information یکسان ولی با Sequence Number های متفاوت در شبکه پخش نماید. نتیجه این که به صورت همزمان این همسایه از یک سمت این Link State Information را با Sequence Number های متفاوت پخش میکند و از طرف دیگر نیز روتر تولید کننده ی Link State Information همین Link State Information را با Sequence Number های یکسان پخش میکند.

روتری در این ساختار چند Link State Information دریافت می کند. فرض کنید اول Link State Information ای با Sequence Number برابر 56 و همزمان یک Link State Information مشابه با Sequence Number ای برابر 40،خوب 16=40-56 که کم تر از 32 است پس، Link State Information با عدد بزرگتر جدیدتر در نظر گرفته می شود. از سوی دیگر دوباره Link State Information ای به دست روتر می رسد با مقدار 8 برای Sequence Number پس 48=8-56  که بزرگتر از 32 است، پس Link State Information ی با Sequence Number کوچکتر جدیدتر در نظر گرفته می شود یعنی 8 . دوباره Link State Information ای با مقدار 40 به دست روتر میرسد و این روال به همین شکل ادامه می یابد.

نتیجه این که با flood این Link State Information ها دیگر جدید بودن آن ها از روی بزرگتر یا کوچکتر بودن مقدار Sequence Number قابل تشخیص نیست و این Link State Information مدام داخل دیتابیس بازنویسی شده و این عمل آنقدر تکرار می شود که بافر سرریز کرده و شبکه از کار می افتد!

شاید تصور کنید این مثال خیلی غیرمنطقی و دور از ذهن است. اما شاید آرپانت هم آن زمان که از یک پروتکل Link State که در آن از فضای مدور 6 بیتی برای Sequence Number بهره گرفته شده بود، در ساختار خود استفاده می کرد، همین تصور را داشت که تداخل در عملکرد یکی از روترهایش سبب از کار افتادن کل ساختار شبکه اش گردید ! 🙂

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

• مدل Lollipop:

تا به اینجا متوجه شدیم که هم فضای خطی و هم فضای مدور دارای نقاط ضعفی اساسی بودند که قابل چشم پوشی نبودند. اما هرکدام به نوبه ی خود مزایایی هم داشتند. در نتیجه تصمیم گرفته شد تا در یک مدل جدید از تلفیقی از این دو روش استفاده شود. یعنی ترکیبی از یک فضای خطی و یک فضای مدور و به این صورت مدل lollipop معرفی شد (شاید هنگامی که به چگونگی تلفیق این دو روش فکر می کردند؛ شخصی با یک آبنبات چوبی از مقابل آن ها رد شده بود یا شاید مثلا به آبنبات چوبی علاقه ی بسیاری داشتند یا … بگذریم 🙂  )                                                                          سر آبنبات چوبی گرد است  و دسته ی آن شبیه یک خط. پس سر آبنبات چوبی فضای مدور و دسته ی آن  فضای خطی است. اما اینجا از اعداد علامت دار استفاده گردید، یعنی بازه ای از اعداد مثبت و منفی. بنابراین اگر فیلد Sequence Number را 32 بیتی در نظر بگیریم، در این صورت 2³¹ عدد مثبت و 2³¹  عدد منفی در نظر گرفته شد (دقت کنید که از 2³² استفاده نشده)  که اگر فضا را N بیتی در نظر بگیریم در این صورت مقدار حداقل بازه یعنی N- که برابر است با: 2³¹– و حداکثر بازه یعنی N-1 که برابر است با:1-2³¹، استفاده نمی شوند.

بازه ی منفی یعنی از N- تا 1- مربوط به بازه ی خطی، و از 1 تا N-1 که بازه ی مثبت می باشد مربوط به فضای مدور است. شمارش از  1+N- شروع می شود و همین طور افزایش پیدا می کند تا به صفر برسد. از این لحظه به بعد وارد فضای مدور شده و همین طور شمارش ادامه پیدا کرده تا  به مقدار N-2 برسد. در این زمان دوباره شمارش از صفر شروع می شود.

در این روش اگر روتری ریستارت می شد، بعد از ریستارت شدن Link State Information ای با مقدار حداقل بازه (یعنی N-) ارسال می کرد. همسایه های آن روتر با دریافت چنین Link State Information ای متوجه می شدند که آن روتر ریستارت شده و بنابراین Link State Information مشابهی که در دیتابیس خود داشتند و مربوط به قبل از ریستارت شدن روتر بود را برای آن ارسال میکردند و روتر به همان نقطه پرش می کرد و شمارش را از آنجا شروع می کرد. روش خوبی بود اما هیچ وقت از مرحله ی آزمایشی فراتر نرفت چون هنوز هم ابهامات مربوط به پیدا کردن جدیدترین Link State Information در فضای مدور در آن وجود داشت.

به همین علت پروتکلی همانند OSPFv2 از بهترین مزایای روش Lollipop ولی در یک بازه ی خطی استفاده می کند. به این معنی که بازه ی خطی به صورت تلفیقی از اعداد مثبت و منفی در نظر گرفته می شود و مقدار حداقل بازه از 0x80000000 شروع شده و همین طور ادامه پیدا می کند تا وارد بازه ی مثبت شود، سپس مجددا به همین روش خطی شمارش ادامه پیدا می کند تا به حداکثر بازه یعنی 0x7fffffff برسد. در چنین زمانی اگر قرار بر تولید و انتشار یک نمونه دیگر از LSA باشد، اول باید LSA قبلی از تمام دیتابیس ها حذف گردد.

هم چنین برای حل مشکل این که کدام Link State Information جدیدتر است از یک روش دیگر علاوه بر Sequence Number استفاده شد و آن هم بهره گرفتن از فیلد Age بود. اینطور مطرح گردید که اگر یک روتر چند کپی از یک Link State Information یکسان و با Sequence Number های یکسان ولی Age های متفاوت دریافت نماید، اگر تفاوت Age این Link State Information جدید و Link State Information ثبت شده در دیتابیس روتر کم تر از مقداری به اسم MaxAgeDiff باشد، روتر فرض را بر این می گذارد که این Link State Information به خاطر تاخیرات نرمال شبکه دیر به دستش رسیده، در نتیجه Link State Information اصلی در دیتابیس هم چنان سرجای خود باقی مانده و این Link State Information جدید پذیرفته و ارسال نمی شود.  اما اگر تفاوت age ها بیشتر از مقدار تعیین شده برای  MaxAgeDiff باشد،  روتر فرض را بر این می گذارد که یک ناهنجاری در ساختار رخ داده که بر اثر آن Link State Information جدید بدون اضافه شدن Sequence Number ارسال شده، پس روتر Link State Information جدید را قبول کرده و آن را برای سایر روترها هم ارسال می کند. معمولا مقدار MaxAgeDiff برابر 15 دقیقه درنظر گرفته می شود.

این هم شرح مختصری از روش ها و مدل های محاسبه ی Sequence Number، اما صبر کنید! ما تا به اینجا فقط دو مورد از موارد مربوط به نحوه ی عملکرد Link State ها را بررسی کرده ایم. این که در این پروتکل ها روترها چطور همسایه های خود را پیدا می کنند و با آنها رابطه ی همسایگی تشکیل میدهند و این که چطور خود را به همسایه هایشان معرفی می کنند. ولی این که این اطلاعاتی که از همسایه ها گرفته می شود کجا و چطور ذخیره می شوند؟ و بعد چطور از این اطلاعات برای ساختن اطلاعات Route Table استفاده می شود؟ هنوز در رابطه با آن ها بحث نشده است.

در قسمت بعد به سراغ جواب این سوالات خواهیم رفت. همراه ما باشید 🙂