سلام به همه ی همراهان عزیز. در دو قسمت قبلی سعی کردیم تا در رابطه با این که در پروتکل های link state روترها چطور همسایه هاشون رو پیدا می کنن و با اونها ارتباط همسایگی تشکیل میدن و این که چطور خودشون رو به همسایه هاشون معرفی می کنن، توضیح بدیم. در این قست قصد داریم تا با هم بررسی کنیم، بعد از این که روتری معرفی نامه ی سایر روترها در ساختار رو دریافت کرد، اون ها رو کجا ذخیره می کنه و بعد چطور با استفاده از این اطلاعات جدول روت خودش رو می سازه.
Link State Database
بعد از این که روترها معرفی نامه ی خودشون رو در قالب Link State Information ها ارسال کردند، این اطلاعات در دیتابیسی به اسم Link State Database ذخیره میشه. هر Link State Information باید دارای اطلاعاتی باشه که به کمک اون ها روتر توانایی محاسبه ی کوتاهترین مسیر رو داشته باشه. حداقل این اطلاعات عبارتند از: شناسه ای از روتر تولید کننده ی Link State Information، شناسه ای از همسایه ی متصل به این روتر و Cost یا همون هزینه از روتر تولید کننده ی Link State Information تا همسایش.
خوب فرض کنید یک ساختار ساده مثل تصویر زیر داریم:
Link State Database نهایی در تمام روترها باید مشابه لیست زیر باشه:
LSDB:{[R1,R2,2],[R1,R3,2],[R2,R1,1],[R2,R3,4],[R2,R4,3],[R2,R5,2],[R3,R1,4],[R3,R2,1],[R3,R5,2], [R4,R2,2],[R4,R5,2],[R5,R2,3],[R5,R3,4],[R5,R4,3]}
همونطور که در بالا هم گفتیم، ورودی های این دیتابیس رو به ترتیب از سمت چپ که بخوایم بررسی کنیم اینطوری میشه که: شناسه ای از روتر، شناسه ای از همسایش، Cost تا اون همسایه.
بعد از ساخته شدن این دیتابیس، نوبت به اجرای الگوریتم SPF میرسه. به نظرتون چطور روترها از این اطلاعات برای اجرای الگوریتم SPF استفاده می کنند؟
با اجرای الگوریتم SPF، در هر روتر دو لیست (یا دیتابیس) ایجاد میشه. یکی از این لیست ها PATH List (یا PATH Database) نام داره و در اون کوتاهترین مسیرها تا هر مقصد قرار می گیره و اطمینان حاصل میشه که هیچ مسیر کوتاهتری نسبت به این مسیرها وجود نداره و در واقع ورودی های این لیست، همون ورودی های Route Table بعد از خاتمه ی کار الگوریتم SPF هستند.
لیست بعدی Tentative List یا به اختصار TENT List (یا TENT Database) هست که در اون مسیرهایی که ممکنه کوتاهترین مسیر تا مقصد باشند یا نباشند قرار می گیره. در واقع هر روتی که کاندید کوتاهترین مسیر باشه در این لیست قرار می گیره.
هر روتر برای این که کوتاهترین مسیر به هر مقصد رو محاسبه کنه مراحل زیر رو طی میکنه:
- اول خودت را به عنوان root در نظر بگیر و به لیست PATH اضافه کن. Next-hop را خودت در نظر بگیر و Cost رو هم صفر در نظر بگیر.
- هر نودی که به لیست PATH اضافه شده که حالا دیگه اسمش شده PATH Node، همسایه هاش رو در Link State Database بررسی کن و هر همسایه ای که در لیست PATH نیست، به لیست TENT اضافه کن. Cost برای نودی که به لیست TENT اضافه کردی برابر میشه با Cost اون نود تا root. (به نودهایی که به لیست TENT اضافه بشن، TENT Node میگن و Cost یک TENT Node میشه: Cost از root تا PATH Node به علاوه ی Cost از PATH Node تا TENT Node. مساله ی دیگه اینه که اگر نودی به لیست TENT اضافه بشه که قبلا در این لیست ثبت شده باشه ولی با Cost بیش تر، این نود جدید جایگزین نود با Cost زیاد ثبت شده در لیست TENT میشه.)
- ورودی در TENT List با کم ترین Cost رو به لیست PATH اضافه کن. اگر دو ورودی در لیست TENT وجود داشته باشه که Cost برابر داشته باشن، یکی از ورودی ها رو به صورت تصادفی انتخاب کن و به لیست PATH اضافه کن. مرحله ی 2 رو انقدر تکرار کن که لیست TENT خالی بشه.
فرض کنید روتر R1 دیتابیسش رو تشکیل داده و حالا قصد اجرای الگوریتم SPF رو داره. اولین لیستی که توسط R1 ایجاد میشه لیست PATH هست. بر اساس مراحلی که در بالا گفته شد، اولین عملی که R1 انجام میده اینه که خودش رو به عنوان root در نظر می گیره، Next-hop رو خودش در نظر می گیره و Cost رو هم تا خودش، صفر در نظر میگیره. پس ورودی های لیست PATH و لیست TENT اینطوری میشن:
PATH: {[R1,R1,0]}
TENT: {}
روتر R1 حالا وارد مرحله ی 2 میشه. بر طبق توضیحات مرحله ی دو باید تمام همسایه های R1 در Link State Database به لیست TENT اضافه بشن:
PATH: {[R1,R1,0]}
TENT: {[R1,R2,2],[R1,R3,2]}
از بین ورودی های لیست TENT، ورودی که کم ترین Cost رو داشته باشه باید از این لیست حذف و به لیست PATH اضافه بشه، از اون جایی که هر دو ورودی، Cost یکسانی دارند، به صورت رندوم یکی از مسیرها انتخاب میشه و به لیست PATH اضافه میشه:
PATH: {[R1,R1,0],[R1,R2,2]}
TENT: {[R1,R3,2]}
تمام همسایه های گره جدیدی که به لیست PATH اضافه شده، باید از LSDB پیدا بشن و به لیست TENT اضافه بشن. اگر از بین این همسایه ها، همسایه ای باشه که قبلا به لیست PATH اضافه شده باشه، دیگه ورودی مربوط به اون همسایه به لیست TENT اضافه نمیشه. از طرف دیگه زمانی که این همسایه ها قراره به لیست TENT اضافه بشن، Cost اون ها برابر میشه با Cost شون تا نود اضافه شده به لیست PATH به علاوه ی، Cost نود اضافه شده به لیست PATH تا root، پس با این اوصاف:
PATH: {[R1,R1,0],[R1,R2,2]}
TENT: {[R1,R3,2],[R2,R3,6],[R2,R4,5],[R2,R5,4]}
از بین این ورودی ها، دوباره ورودی با کم ترین Cost از لیست TENT حذف میشه و به لیست PATH اضافه میشه:
PATH: {[R1,R1,0],[R1,R2,2],[R1,R3,2]}
TENT: {[R2,R3,6],[R2,R4,5],[R2,R5,4]}
از اون جایی که هم R2 و هم R3 هر دو به لیست PATH اضافه شدن، پس ورودی [R2,R3,6] از لیست TENT باید حذف بشه و از طرف دیگه تمام همسایه های R3 که هنوز به لیست PATH اضافه نشدن از LSDB پیدا و به لیست TENT اضافه میشن:
PATH: {[R1,R1,0],[R1,R2,2],[R1,R3,2]}
TENT: {[R2,R4,5],[R2,R5,4],[R3,R5,4]}
از بین دو مسیر با Cost یکسان و با مقدار 4، یکی به صورت رندوم انتخاب میشه و به لیست PATH اضافه میشه:
PATH: {[R1,R1,0],[R1,R2,2],[R1,R3,2],[R2,R5,4]}
TENT: {[R2,R4,5],[R3,R5,4]}
از اون جایی که R5 و R3 هر دو به لیست PATH اضافه شدن [R3,R5,4] از لیست TENT حذف میشه:
PATH: {[R1,R1,0],[R1,R2,2],[R2,R5,4]}
TENT: {[R2,R4,5]}
از اون جایی که تمام همسایه های R5 قبلا به لیست PATH اضافه شدن، هیچ ورودی جدیدی به لیست TENT اضافه نمیشه و آخرین ورودی لیست TENT به لیست PATH اضافه میشه:
PATH: {[R1,R1,0],[R1,R2,2],[R1,R3,2],[R2,R5,4],[R2,R4,5]}
TENT: {}
از اون جایی که همه ی همسایه های R4، به لیست PATH اضافه شدن، هیچ ورودی جدیدی به لیست TENT اضافه نمیشه و لیست TENT خالی میشه و کار الگوریتم با ایجاد یک گراف بدون دور مثل شکل زیر خاتمه پیدا می کنه و تمام ورودی های لیست PATH می تونن به Route Table اضافه بشن:
خب R1 تونست با اجرای الگوریتم Dijkstra Shortest Path First، کوتاهترین مسیر بدون دور به هر مقصد رو شناسایی و ورودی های Route Table اش رو به دست بیاره. (تو این متنی که من نوشتم از دو اصطلاح PATH List و TENT List استفاده شد، اگر بخوایم دقیقا بر اساس الگوریتم Dijkstra این مفاهیم رو بگیم به PATH List گفته میشه Tree Database و به TENT List گفته میشه Candidate Database.)
همونطور که دیدید در Link State ها روتر به حافظه ی بیشتری برای نگه داری دیتابیس هاش احتیاج داره، از طرف دیگه الگوریتم SPF برای اجرا شدن به پردازش بیش تری نسبت به اون چه در Distance Vector ها انجام می شد، احتیاج داره و نکته ی مهم تر این که بیشتر از اجرای الگوریتم SPF، جریان Link State Information ها در ساختار هست که بار پردازش زیادی به CPU روترها تحمیل میکنه و اگر شبکه بی ثبات باشه، تاثیر منفی بر پهنای باند میذاره و این اوضاع زمانی که پهنای باند لینک ها کم باشند، بدتر هم میشه.
بنابراین به خاطر وجود این سه مشکل، Link State ها از مفهومی استفاده میکنن به اسم Area (یا همون ناحیه). با استفاده از Area ها، تاثیرات منفی Link State ها بر memory روترها، CPU و Bandwidth کامل از بین نمیره اما در کاهش اثرات منفی بر این منابع، نقش چشم گیری داره. Link State ها ساختار شبکه رو تقسم بندی می کنند و به هر قسمت یک Area میگن.
تقسیم یک شبکه به Area های مختلف سبب می شه که روترهای داخل یک Area، Link State Information ها رو تنها داخل همون Area ای که در اون قرار دارن، flood کنند و اینطوری داخل هر Area فقط یک Link State Database احتیاج هست. کوچیکتر شدن اندازه ی دیتابیس به معنی نیاز کمتر به حافظه در هر روتر هست و از طرف دیگه به پردازش کم تر CPU برای اجرای الگوریتم SPF منجر میشه. مزیت دیگه استفاده از Area ها اینه که اگر شبکه مدام دچار تغییر در توپولوژی باشه (یعنی شبکه بی ثبات باشه)، flooding فقط محدود به همون Area ای می شه که دچار بی ثباتی شده.
شاید الان با خودتون یک حساب سرانگشتی انجام دادید و به این نتیجه رسیدید که: خب Distance Vector ها نه از الگوریتم پیچیده استفاده می کنن که بخوان به CPU زیادی احتیاج داشته باشن و نه این همه دیتابیس دارن برای این که اطلاعات رو نگه داری کنن و از طرف دیگه مدام هم اطلاعات توپولوژی در ساختار flood نمی کنن (به عبارت بهتر اصلا اطلاعات توپولوژی نمی فهمن چی هست 🙂 )، در نتیجه منابعی که مصرف میکنن کم تره و بنابراین نسبت به Link State ها بهتر هستن. اما باید بگیم که اگر شبکه خیلی بزرگ باشه و کل ساختار رو هم به صورت یکپارچه در نظر بگیریم، به هر حال روتر برای رسیدن به هر مقصد باید محاسبات پیدا کردن کوتاهترین مسیر رو انجام بده و از طرف دیگه چون شبکه یکپارچه هست، سایز Route Table روترها بزرگ میشه و در نتیجه روترها باید هر 30 ثانیه، حجم عظیم اطلاعات داخل Route Table خودشون رو Broadcast کنن!!! در نتیجه اینجاست که به قدرت استفاده از Area ها در Link State ها به راحتی پی می برید 😉
در این پنج قسمت سعی کردیم تا تفاوت های اصلی عملکردی پروتکل های Distance Vector و Link State رو بررسی کنیم. در قسمت بعد قصد داریم تا پا به سرزمین Distance Vector بذاریم و به سراغ یکی از اهالی این سرزمین بریم که از دید خیلی ها دو رگه خطاب میشه. امیدواریم هم چنان پرانرژی در این سفر همراهمون باشید 🙂
چه قدر عاااالی توضیح دادین. واقعن ازتون ممنونم. شاد باشید.