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

سلام به همه ی همراهان عزیز. اگر با موفقیت از سرزمین Distance Vector عبور کنیم، سرزمین بعدی که بهش خواهیم رسید ‏Link State‏ نام داره. زمانی که از  Link State Routing Protocol ها یاد میشه، اون ها رو ‏هوشمند ولی پر از رمز و راز و پیچیدگی معرفی می کنن. بهتره پیش از ورود به این سرزمین، ‏کمی با خصوصیات این روتینگ پروتکل ها آشنا بشیم!  🙂

***

تاریخچه ی مختصری از تکنولوژی مسیریابی ‏Link State
برخلاف Distance Vector ها که فقط مسیرها را تبلیغ می کنند و هیچ  دیدی از کل شبکه در اختیار قرار نمی دهند، در ‏link state‏ ها روتر، مسیر تبلیغ نمی کند بلکه اطلاعاتی راجع به لینک های متصل به خود، وضعیت این لینک ها و همسایه ‏هایی که به این لینک ها متصل می باشند را به همسایه های خود تبلیغ می کند. روترها تا زمانی که این اطلاعات را از ‏همسایه های خود دریافت نکنند مسیری را برای رسیدن به مقصدی انتخاب نمی کنند. پس می توان اینگونه بیان کرد که:

اگر Distance Vector ‏ها حکم یک تابلو سر دو راهی را دارند، Link State ها در حکم یک نقشه ی کامل می باشند.

اما نحوه ی عملکرد ‏link state‏ ها به طور کلی به اینصورت است که:‏

• تشکیل رابطه ی ‏adjacency‏ یا مجاورت با همسایه ها
•  معرفی خود به همسایه ها
  
• ساخت دیتابیسی از اطلاعاتی که از همسایه ها فراگرفته شده
• ساخت جدول روت بر اساس اطلاعات دیتابیس تشکیل شده
  ‏
  ‏تمام عملکرد ‏Link State‏ ها در این چهار خط خلاصه می شود. اما این فقط ظاهر امر می باشد، بیایید دقیق تر بررسی کنیم و ببینیم ‏پشت هر کدام از این موارد چه اتفاقی در حال رخ دادن است.‏

• همسایه: در این سرزمین هرکسی همسایه محسوب نمی شود. در اینجا همسایه کسی است که با آن ارتباط مجاورت شکل ‏گرفته باشد. برای برقراری این ارتباط لازم است که همسایه ها اول یکدیگر را شناسایی کنند. برخلاف ‏distance vector‏ ها که هر روتری که با آن ها یک لینک ارتباطی مشترک میداشت، همسایه محسوب میکردند، اینجا از مکانیزم دقیق تری برای پیدا ‏کردن همسایه ها استفاده می شود آن هم پروتکلی است به اسم ‏Hello Protocol‏. عملکرد ‏Hello‏ پروتکل به این صورت است که، روترها شروع به ارسال پکتی به اسم hello برای معرفی خود و اعلام حضور خود بر روی ساختار می کنند. به این ترتیب اگر پکت hello ای، به یک روتر که به زبان روتر ارسال کننده ی پکت hello صحبت می کند برسد روتر، همسایه ای که این پکت را ارسال کرده شناسایی کرده و همسایه ها یکدیگر را پیدا می کنند.

تا به اینجا مشخص گردید که آداب معاشرت برای اهالی این سرزمین مهم است: “اول ‏سلام کن! اما نوع سلام کردن نیز مهم است! هرکسی به من سلام کند همسایه ی من محسوب نمیشود!”  پس پکت های ‏hello‏ باید دارای یکسری پارامترها باشند که از این پارامترها با عنوان پارامترهای همسایگی یاد می شود. اگر در هر دو روتر ‏این پارامترها یکسان باشند، روترها با هم همسایه می شوند. توضیح مربوط به این پارامترها را به موقع در قسمت های بعدی انجام خواهیم داد.

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

چه موضوعی باعث شد که در ‏Link State‏ ها از چنین مکانیزمی برای پیدا کردن همسایه ها استفاده شود؟ در همان زمان ‏distance vector‏ ها نیز با روش خود همسایه ها را پیدا می کردند، پس چرا روش آنها کنار ‏گذاشته شد و مکانیزم دیگری جایگزین شد؟ در جواب باید بگوییم که اگر به خاطر داشته باشید ‏distance vector‏ ها برای آن که بتوانند روترهایی که به زبان آن ها سخن میگفتند پیدا کنند، پیام های خود را Broadcast می کردند! و این یعنی ‏تحمیل بار ترافیک اضافی به شبکه. چرا که حتی دیوایس هایی که به زبان روتر صحبت نمیکردند نیز، آن پیام ها را دریافت می کردند، آنها را پردازش میکردند، و بعد از پردازش آن ها متوجه می شدند که این پیام برای آنها نیست و دورش می انداختند و این امر به معنی بار پردازشی بیهوده ای است که نیازی به آن نمی باشد.

اما در ‏link state‏ ها پکت های مربوط به روتینگ پروتکل، فقط برای روترهایی ارسال خواهد شد که به زبان روتر سخن می گویند. از سوی دیگر، امکان دیگری که این مکانیزم فراهم می آورد آن است که بعد از تشکیل همسایگی، مواظب ارتباطات همسایگی نیز هست و به نوعی همانند بسته های ‏keepalive‏ عمل می کند. به این ترتیب اگر همسایه ای در مدت زمان مشخص به روتر پکت ‏hello‏ ‏ارسال نکند یعنی ارتباط با آن بنا به هر دلیلی دچار مشکل شده و همسایگی از بین می رود. پس تشخیص ‏fail‏ شدن همسایه ها و در دسترس نبودن مسیرهایی که از جانب آن همسایه قابل دسترس بودند نیز، به مراتب با سرعت بیشتری نسبت به ‏distance vector‏ ها صورت می گیرد.‏

• معرفی خود به همسایه ها: ‏link state‏ ها همانند ‏distance vector‏ ها که در آنها روترها در همان ابتدا بلافاصله الگوریتم پیدا کردن بهترین مسیر را اجرا می کنند و سپس هر آن چه در جدول ‏روت خود دارند برای همسایه ها تبلیغ می کنند و سپس به ازای هر مسیری که دریافت می کنند دوباره الگوریتم پیدا کردن بهترین مسیر را اجرا نموده و اینگونه زمان زیادی صرف اجرای الگوریتم می نمایند، عمل نمی کنند. رسم بعدی اهالی این سرزمین این است که: “بعد از این که سلام ‏کردی و به درستی هم سلام نمودی، حال خودت را معرفی کن! ولی باز هم نه یک معرفی کوتاه و مختصر، بلکه یک معرفی کامل!!! ”  ‏پس روتر باید به همسایه های خود بگوید، چه لینک هایی به آن متصل هستند، وضعیت این لینک ها چگونه است و چه همسایه هایی را از طریق هر لینک شناسایی نموده.

اما برای این که روتر این معرفی نامه را ارسال کند، تمام این اطلاعات را در قالب یک واحد داده جمع آوری کرده که بسته به نوع پروتکل Link State اسم این واحد داده متفاوت است. مثلا در OSPF اسم این واحد داده ‏Link State Advertisement (LSA)‎‏ و در IS-IS اسم آن Link State Packet (LSP) است (چون تمرکز ما بر روی نحوه ی عملکرد کلی Link State هاست؛ به جای اصطلاحات LSA یا LSP از اصطلاح Link State Information برای اشاره به این واحد داده استفاده می کنیم.) هنگامی که از Link State information ها و نحوه ی ارسال آن ها صحبت می شود از اصطلاحی به اسم ‏flood‏ (یا همان جریان به فارسی) استفاده می کنند. یعنی اینگونه بیان می شود که Link State Information ها باید در کل ساختار جاری شوند! اما این اصطلاح ‏به چه معنی است؟ معنی این اصطلاح آن است که، هر روتر Link State Information ای را که دریافت می کند، یک کپی از آن برای خود تهیه کرده و آن را در یک دیتابیس به اسم ‏Link Satate Database‏ ذخیره می کند و سپس آن Link State Information را برای سایر  همسایه های خود غیر از آن همسایه ای ‏که این Link State Information را از آن دریافت کرده، ارسال می کند و اینگونه یک Link State Information در ساختار جاری می شود!

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

اولین سوال این که به نظر شما ‏flood‏ یک Link State Information در ‏ساختار تا چه زمانی باید ادامه پیدا کند؟ یا مثلا این که ‏یک Link State Information بعد از تولید شدن، دیگر برای همیشه معتبر باقی می ماند؟باید اول بیان کنیم که کار flood Link State Information ها زمانی خاتمه پیدا میکند که تمام روترها تمام Link State Information ها را از سایر روترهای موجود در ساختار دریافت کرده باشند. از ‏طرف دیگر برای Link State Information ها سن درنظر گرفته میشود. به این معنی که هنگامی که روتری یک Link State Information تولید میکند برای آن سنی در نظر میگیرد که بسته به نوع پروتکل Link State، این مقدار می تواند صفر و یا یک مقدار حداکثر باشد و به ازای روترهایی که Link State Information از آنها عبور می کند، مقدار تعیین شده برای سن آن، کم یا اضافه می شود. حتی ‏اگر Link State Information در دیتابیس یک روتر ثبت هم شود، باز هم همین حالت کاهش یا افزایش سن، برای آن Link State Information وجود خواهد داشت.

اگر سن یک Link State Information از صفر شروع شود، آنقدر سن آن افزایش پیدا میکند تا به یک مقدار حداکثر برسد که از آن با نام MaxAge یاد می شود و مقدار آن نیز توسط خود روتینگ پروتکل مشخص می گردد. در این شرایط آن Link State Information باید از دیتابیس تمام روترها حذف شود. همین حالت برای زمانی که مقدار سن یک Link State Information از یک مقدار حداکثر(MaxAge) شروع می شود و کاهش پیدا می کند نیز صدق می نماید. یعنی در این شرایط اگر سن یک Link State Information به مقدار صفر رسد، باید از دیتابیس تمام روترها حذف شود.

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

سوال دیگری که مطرح می شود آن است که، فرض کنید یکی از لینک های متصل به روتری مانند X در یک ساختار down شود. روتر X بلافاصله Link State Information ای را به ‏همسایه های خود در قالب یک پیام آپدیت ارسال می کند تا به آن ها این ‏down‏ شدن را اطلاع دهد. بلافاصله بعد از ارسال Link State Information، ‏دوباره لینک ‏up‏ می شود و باز هم روتر بلافاصله Link State Information‏ مربوط به این تغییر جدید را با یک پیام آپدیت دیگر ارسال می کند. فرض ‏کنید روتر دیگری در انتهای این ساختار وجود دارد که از دو مسیر به روتر ‏X‏ دسترسی دارد و Link State Information ها را دریافت میکند. ولی از یک ‏مسیر این ‏Link State Information ها با تاخیر به آن میرسند. این روتر، اول Link State Information مربوط به up شدن لینک را دریافت می کند و سپس با تاخیر، Link State Information اول که مربوط به ‏down‏ شدن لینک بود، دریافت می کند.

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

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

این که این روش ها چه هستند و چطور عمل می کنند، در قسمت بعد بررسی خواهیم کرد. در این سفر همراه ما باشید 🙂