سلام به همه ی هم سفران عزیز. در قسمت قبلی با نحوه ی تشکیل ارتباط همسایگی و چگونگی عملکرد EIGRP در تضمین و تحویل پکت هاش آشنا شدیم. در این قسمت قصد داریم به سراغ مولفه ی سوم از مولفه های اصلی عملکردی EIGRP بریم که در واقع بررسی الگوریتمی هست که EIGRP از اون برای محاسبه ی بهترین مسیر به هر مقصد با شرط loop free بودن اون مسیر در هر لحظه استفاده میکنه. پس بیاید کمی بیشتر با این الگوریتم آشنا بشیم 🙂
***
Diffusing Update Algorithm (DUAL):
DUAL تضمین می کند که شبکه در هر لحظه حتی در هنگام رخ دادن تغییرات در توپولوژی و همگرایی مجدد ساختار، loop free باقی بماند. بر خلاف سایر پروتکل های Distance Vector که بر اساس الگوریتم Bellman-Ford فعالیت می کنند و در صورت بروز تغییری در توپولوژی، آپدیت ها به صورت ناهماهنگ توسط نودها در ساختار ارسال می شوند، DUAL برای آن که بتواند تنها در بخش هایی که تحت تاثیر تغییر واقع شده اند محاسبات یافتن بهترین مسیر جایگزین بعدی را انجام دهد، نیازمند آن است که از یک روش هماهنگ برای انتشار اطلاعات بین تمام نودها در ساختار استفاده کند که این روش diffusing computation نام دارد. بر اساس diffusing computation تنها روترهایی که تحت تاثیر تغییر باشند محاسبات مربوط به یافتن بهترین مسیر جدید بعدی که loop free باشد را انجام می دهند.
به بیان دیگر diffusing computation روند ارسال Query برای یافتن مسیری به مقصدی است که fail شده است. روترهایی که از مقصد مورد نظر اطلاعی نداشته باشند بلافاصله به Query دریافت کرده پاسخ می دهند و وارد جریان محاسبات diffusing computation نمی شوند. به این ترتیب روند انجام diffusing computation تنها در یک بخش خلاصه شده و در کوتاهترین زمان ممکن این روند خاتمه می یابد.
یکی از ویژگی های DUAL آن است که می توان با پنهان کردن اطلاعات reachability، دامنه ی نقاطی که diffusing computation باید در آن ها صورت گیرد، کاهش داد و به بیان بهتر مدیر شبکه این امکان را داشته باشد که با انجام اعمالی چون Summerization یا فیلترینگ داخل یک AS بتواند، failure domain های کوچکتری ایجاد کرده و از این طریق زمان همگرایی را مدیریت کند.
اما قبل از بررسی دقیق تر قوانین diffusing computation، ابتدا باید برخی مفاهیم و اصطلاحات توضیح داده شوند.
زمانی که روتری برای نخستین بار همسایه ی EIGRP جدیدی پیدا می کند، بعد از طی روند شکل گیری همسایگی (که در قسمت قبل بیان گردید) اطلاعات مربوط به تمام مسیرهایی که تاکنون فراگرفته را در قالب پیام آپدیتی برای همسایه ی خود ارسال می کند. این اطلاعات شامل متریکی که آن روتر تا هر مقصد محاسبه کرده نیز می شود. روتر دریافت کننده ی این پیام آپدیت، بر اساس متریکی که همسایه تا یک مقصد خاص تبلیغ کرده که اصطلاحا به آن Reported Distance (RD) گفته می شود به علاوه ی Cost لینک تا آن همسایه، شروع به محاسبه ی متریک تا آن مقصد می کند.
اگر تا یک مقصد چندین مسیر تبلیغ شده باشد، به ازای هر مسیر متریک جداگانه ای محاسبه شده و کم ترین متریک محاسبه شده تا آن مقصد به عنوان Feasible Distance (FD) برای آن مقصد در نظر گرفته می شود.
EIGRP برای یافتن بهترین مسیر بدون لوپ تا مقصد از شرطی استفاده میکند که اصطلاحا Feasibility Condition (FC) نامیده می شود و در واقع بررسی کننده ی آن است که متریک تبلیغ شده از جانب یک همسایه از مقدار FD محاسبه شده کم تر است یا نه.
اگر همسایه ای مسیری را برای رسیدن به یک مقصد تبلیغ کند که مقدار متریک محاسبه شده توسط آن تا آن مقصد(RD) از مقدار FD محاسبه شده توسط روتر برای آن مقصد کم تر باشد، آن همسایه به عنوان Feasible Successor (FS) در نظر گرفته می شود. اگر مقدار RD تبلیغی از جانب همسایه بیشتر یا حتی مساوی مقدار FD باشد، آن همسایه به عنوان Feasible Successor انتخاب نخواهد شد.
ممکن است چند همسایه به عنوان Feasible Successor انتخاب شوند. از بین همسایه هایی که به عنوان FS انتخاب شده اند، همسایه ای که برای رسیدن به مقصد، کم ترین متریک برای آن محاسبه شده باشد به عنوان Successor انتخاب می شود. Successor درواقع همان روتر next-hop برای ارسال پکت ها به مقصد می باشد. سایر FS ها در جدولی با نام Topology Table نگهداری می شوند و در حالت عادی تنها زمانی استفاده می شوند که Successor بنا به هر دلیلی fail شود.
◊ دقت داشته باشید که متریک مسیر از سمت Successor می تواند برابر و یا کم تر از مقدار FD باشد. FD الزاما متریک محاسبه شده برای Successor نیست بلکه مقدار متریکی است که در لحظه ی گذار از وضعیت Active به Passive محاسبه شده است (در ادامه این دو وضعیت شرح داده شده اند).
مفاهیم Feasible Successor و Feasibility Condition در واقع عوامل اصلی جلوگیری از لوپ در EIGRP می باشند:
- از آن جایی که مقدار متریک تبلیغی از جانب همسایه هایی که به عنوان FS انتخاب می شوند همواره باید کم تر از FD باشد، روتر هرگز مسیری را که نهایتا به خودش منتهی شود به عنوان FS انتخاب نخواهد کرد چرا که چنین مسیری قطعا متریکی بزرگتر از FD خواهد داشت.
- از سوی دیگر وجود FS ها و ذخیره ی آن ها علاوه بر Successor این امکان را برای EIGRP فراهم می آورد که در صورت از دسترس خارج شدن Successor، در کوتاهترین زمان ممکن بهترین مسیر بعدی را جایگزین کرده و به همگرایی مجدد برسد.
EIGRP برای هر مسیری که برای رسیدن به هر مقصد محاسبه کرده دو وضعیت در نظر میگیرد: Passive و Active.
- Passive: اگر به ازای مقصدی حداقل یک همسایه وجود داشته باشد که کوتاهترین مسیر ممکن loop free که شرط FC برای آن صدق کند، تبلیغ نماید آن مسیر در وضعیت Passive قرار خواهد گرفت. به بیان بهتر اگر برای رسیدن به یک مقصد حداقل یک FS وجود داشته باشد که کوتاهترین مسیر ممکن تا آن مقصد را تبلیغ نماید، آن مسیر به وضعیت Passive می رود. همانطور که در بالا نیز ذکر گردید FS ای که کوتاهترین مسیر loop free تا یک مقصد را تبلیغ نماید، Successor خطاب می شود. پس مسیر Passive مسیری با حداقل یک Successor می باشد. چنین مسیری قابل استفاده بوده و در جریان مسیریابی از آن استفاده می شود.
- Active: برخلاف وضعیت Passive، مسیری در وضعیت Active قرار خواهد گرفت که هیچ FS ای (و متعاقبا هیچ Successor ای) برای آن وجود نداشته باشد. چنین مسیری نمی تواند در جریان مسیریابی شرکت کند و قابل استفاده نیست. روتر برای مسیری که در وضعیت Active قرار داشته باشد باید طی فرآیندی هماهنگ از همسایه های خود پرس و جو کرده تا بتواند کوتاهترین مسیر loop free برای آن مقصد را پیدا نماید.
مجموعه ای از قوانین که مشخص کننده ی آن هستند که چه زمان و چگونه مسیری از وضعیت Passive به Active منتقل می شود و بالعکس، DUAL Finite State Machine (DUAL FSM) خطاب می شوند.
DUAL Finite State Machine:
برای بررسی DUAL FSM ابتدا باید با این موضوع آشنا باشید که چه زمان Diffusing Computation انجام می شود.
زمانی که مسیرهای فرا گرفته شده از طریق EIGRP در وضعیت Passive باشند، محاسبات Diffusing Computation نیز صورت نمی گیرد. اما اگر برای مسیری تغییری حاصل شود که اصطلاحا به این تغییرات input event گفته می شود، روتر لیست FS های مسیری که برای آن input event رخ داده بررسی می کند. input event ها می توانند یکی از موارد زیر باشند:
- تغییر در cost یک لینک directly connected
- تغییر در وضعیت یک لینک directly connected (UP/Down شدن لینک)
- دریافت یک پکت Update/Query/Reply
اولین گام در ارزیابی مجدد FS ها انجام local computation می باشد. در واقع local computation محاسبه ی مجدد متریک تمام FS های موجود برای مسیری است که input event برای آن رخ داده باشد. بر اثر انجام local computation ممکن است یکی از موارد ذیل رخ دهد:
- اگر distance (متریک) یک FS کم تر از distance محاسبه شده برای Successor فعلی گردد، FS جایگزین Successor فعلی می شود.
- اگر distance محاسبه شده ی جدید کم تر از FD باشد، FD با این مقدار جدید به روزرسانی می شود.
- اگر distance محاسبه شده ی جدید با distance موجود تفاوت داشته باشد، یک پیام آپدیت به تمام همسایه ها ارسال می شود.
تا زمانی که روتر در حال انجام local computation می باشد، مسیرها در وضعیت Passive باقی خواهند ماند. اگر FS ای برای مسیر یافت شود، یک پیام آپدیت به همسایه ها ارسال شده و تغییری در وضعیت مسیرها حاصل نخواهد شد. اما اگر FS ای یافت نشود روتر اقدام به اجرای diffusing computation کرده و مسیری که برای آن diffusing computation اجرا شده به وضعیت Active می رود. تا زمانی که diffusing computation کامل نشود و مسیر به وضعیت Passive باز نگردد، روتر نمی تواند این اعمال را در قبال مسیر در وضعیت Active انجام دهد:
- تغییر Successor
- تغییر distance ای که برای آن مسیر تبلیغ کرده
- تغییر FD آن مسیر
- آغاز یک diffusing computation جدید برای آن مسیر
diffusing computation با ارسال Query آغاز می شود، به این صورت که روتر بر روی تمام لینک های خود به تمام همسایگان EIGRP خود Query ارسال خواهد کرد و تا زمانی که از تمام همسایه هایی که برای آن ها Query ارسال شده Reply ای دریافت نگردد، diffusing computation خاتمه نخواهد یافت، روتر برای آن که تشخیص دهد کدام یک از همسایگان، Reply مربوط به Query ارسال شده را برای آن ارسال کرده اند از پرچمی با نام reply status flag بهره می گیرد و به ازای هر همسایه که برای آن Query ارسال کرده مقدار این پرچم را یک می نماید. به محض دریافت Reply از جانب همسایه، مقدار این پرچم برای آن همسایه صفر می گردد.
از سوی دیگر ممکن است در حالی که مسیر به یک مقصد هم چنان در وضعیت Active قرار دارد، input event دیگری رخ دهد. به همین دلیل DUAL چندین حالت Active در نظر میگیرد و برای تشخیص آن که مقصد مورد نظر اکنون در کدام یک از این حالت های Active قرار دارد از پرچمی با نام query origin flag استفاده می کند.
در تصویر زیر وضعیت های DUAL FSM نمایش داده شده که شماره های بر روی فلش ها در واقع input event هایی هستند که سبب تغییر وضعیت یک مسیر می شوند.
توصیف input event هایی که سبب تغییر از یک وضعیت به وضعیت دیگر می شوند به شرح ذیل می باشد:
- اگر برای یک مقصد Query ای از جانب همسایه ای دریافت شود که آن همسایه Successor برای رسیدن به آن مقصد نباشد و هم چنین برای آن مقصد یک FS نیز وجود داشته باشد، در چنین صورتی مسیر به آن مقصد هم چنان در وضعیت Passive باقی خواهند ماند. از آن جایی که روتر برای آن مقصد حداقل یک FS دارد باید به Query دریافت شده پاسخ دهد. هر متریکی که از طریق این Query تبلیغ شده باشد باید در جدول توپولوژی ثبت شده و برای بررسی عدم تاثیر آن بر Successor فعلی، شرط FC برای آن بررسی شود.
- اگر وضعیت یک لینک directly connected تغییر کند (up/down یا تغییر cost) و یا Update یا Query ای دریافت شود که برای یک مقصد تغییری در متریک را تبلیغ کنند و در تمام این موارد، این تغییرات هیچ تاثیری بر Successor آن مقصد نداشته باشد و یا حتی در صورت اثر، برای آن مقصد یک FS وجود داشته باشد، مسیر به آن مقصد هم چنان در وضعیت Passive باقی خواهند ماند. در تمام این حالات باید با ارسال Update ای، متریک جدید به همسایه ها اطلاع داده شود.
- اگر برای یک مقصد از جانب Successor آن، Query دریافت شود و برای آن مقصد به غیر از Successor هیچ FS دیگری وجود نداشته باشد، مسیر به آن مقصد به وضعیت Active رفته و روتر به تمام همسایگان خود با رعایت قانون Split Horizon این Query را ارسال می کند. در چنین حالتی برای مسیر به آن مقصد query origin flag با مقدار 3 تنظیم شده و reply status flag مقدار 1 می گیرد.
- اگر لینک directly connected ای down شود و یا cost آن افزایش یابد و یا Update ای برای آن مقصد دریافت شود که در آن متریک به مقصد مورد نظر افزایش یافته باشد، اگر برای آن مقصد هیچ FS ای وجود نداشته باشد، مسیر به آن مقصد به وضعیت Active رفته و به تمام همسایگان Query ارسال می شود. در چنین حالتی query origin flag برای مسیر به آن مقصد مقدار 1 گرفته و reply status flag مقدار 1 می گیرد.
- اگر مسیر به مقصدی در وضعیت Active قرار داشته باشد و از Successor آن مسیر Query ای دریافت شود، مسیر هم چنان در وضعیت Active باقی خواهند ماند ولی origin flag برای آن مقدار 2 خواهد گرفت. reply status flag نیز هم چنان دارای مقدار یک خواهد بود. در چنین شرایطی متریک FS جدید با متریکی که سبب وضعیت Active برای مسیر شده، مقایسه می گردد.
- اگر مسیر به مقصدی در وضعیت Active باشد و از جانب همسایه ای که Successor برای آن مقصد نبوده، Query ای دریافت شود، مسیر هم چنان در وضعیت Active باقی می ماند و باید با ارسال یک Reply به Query دریافت شده پاسخ داده شود. هم چنین متریکی که از طریق Query جدید دریافت شده نیز باید ثبت شود.
- اگر مسیر به مقصدی در وضعیت Active باشد و cost لینک تغییر کند و یا Update ای با یک متریک تغییریافته ی جدید از همسایه ای که برای آن مقصد Successor نیست، دریافت شود، مسیر به آن مقصد هم چنان در وضعیت Active باقی می ماند. اطلاعات متریک موجود در این پیام آپدیت، ثبت می شوند. زمانی که مسیری در وضعیت Active باشد، هیچ آپدیت یا Query ای در رابطه با آن مسیر ارسال نخواهد شد.
- اگر مسیر به مقصدی در وضعیت Active باشد و Reply ای دریافت شود که از جانب همسایه یا روتری باشد که ارتباط با آن fail شده بوده، روتر دریافت Reply ای که به سبب آن Query ارسال شده ثبت می کند و reply status flag برای همسایه ای که Reply ارسال کرده صفر می گردد. اگر هنوز از تمام همسایه ها Reply دریافت نشده باشد، مسیر به مقصد مورد نظر هم چنان در وضعیت Active باقی خواهند ماند.
- اگر زمانی که مسیر به مقصدی در وضعیت Active باشد، لینک بین روتر و Successor آن مقصد fail شود و یا cost آن افزایش یابد، روتر با این مورد همانند دریافت Reply از جانب Successor عمل می کند. اگر این اتفاق بعد از ارسال Query توسط روتر برای آن مقصد رخ داده باشد، روتر query origin flag را برای مسیر به آن مقصد صفر مقدار دهی می کند تا نشان دهنده ی آن باشد که تغییر دیگری در توپولوژی رخ داده و این مسیر هنوز در وضعیت Active قرار دارد.
- اگر زمانی که مسیر به مقصدی در وضعیت Active باشد، لینک بین روتر و Successor آن مقصد fail شود و یا cost آن افزایش یابد، روتر با این مورد همانند دریافت Reply از جانب Successor عمل می کند. اگر این اتفاق بعد از ارسال Query توسط Successor برای آن مقصد رخ داده باشد، روتر query origin flag را برای مسیر به آن مقصد 2 مقدار دهی می کند تا نشان دهنده ی آن باشد که تغییر دیگری در توپولوژی رخ داده و این مسیر هنوز در وضعیت Active قرار دارد.
- اگر مسیر به مقصدی در وضعیت Active باشد و cost لینک تا Successor افزایش یابد و این امر در شرایطی اتفاق بیافتد که Reply از تمام همسایه ها دریافت شده و هنوز FS ای وجود نداشته باشد، روتر باید هم چنان در وضعیت Active باقی بماند و باید مجددا به تمام همسایه ها Query ارسال شود و query origin flag نیز برای مسیر به آن مقصد 1 در نظر گرفته می شود.
- اگر مسیر به مقصدی به دلیل دریافت Query از Successor آن مقصد در وضعیت Active قرار گرفته باشد و آخرین Reply مورد انتظار نیز در قبال این Query دریافت شده باشد ولی باز هم هیچ FS ای یافت نشده باشد، مسیر به آن مقصد باید در وضعیت Active باقی بماند. در چنین شرایطی query origin flag برای مسیر به آن مقصد 3 در نظر گرفته می شود.
- اگر query origin flag برای مسیر به مقصدی مقدار 3 داشته باشد که نشان دهنده ی آن است که مسیر به آن مقصد به علت دریافت Query از جانب Successor آن به وضعیت Active رفته است، با دریافت تمام Reply ها از جانب تمام همسایه ها، مسیر دوباره به وضعیت Passive برگشته و به Successor آن Reply ای ارسال می گردد.
- اگر مقدار query origin flag برای مسیر به مقصدی 0 باشد که نشان دهنده ی آن است که مسیر به آن مقصد بر اثر تغییری در توپولوژی تا Successor در وضعیت Active قرار گرفته، نیازی به ارسال Reply به Successor قبلی نیست. اگر شرط FC رعایت شده باشد، مسیر دوباره به وضعیت Passive باز گردانده می شود.
- اگر مقدار query origin flag برای مسیر به مقصدی 1 باشد که نشان دهنده ی آن است که روتر یا خود تولید کننده ی Query بوده و یا با وجود دریافت Reply های مورد انتظار از تمام همسایه ها، شرط FC رعایت نشده بوده که مسیر به مقصد مورد نظر در وضعیت Active قرار گرفته است، مقدار FD بی نهایت در نظر گرفته شده و از بین متریک های دریافت شده توسط Reply ها، کم ترین مقدار متریک به عنوان FD جدید انتخاب می شود و مسیر به مقصد مورد نظر به وضعیت Passive بازگردانده می شود و به Successor قبلی در صورتی که Query از آن دریافت شده باشد، Reply ای ارسال می گردد.
- اگر مقدار query origin flag، برای مسیر به مقصدی 2 باشد که نشان دهنده ی آن است که Query از جانب Successor آن مقصد دریافت شده و یا در حالی که مسیر در وضعیت Active بوده، متریک تا آن مقصد افزایش یافته است و سبب شده که مسیر به آن مقصد در وضعیت Active باشد، اگر تمام Reply های مورد انتظار از تمام همسایه ها دریافت شده باشد و برای آن مقصد FS ای نیز یافت شده باشد، مسیر به وضعیت Passive بازگشته و در پاسخ به Query ارسال شده از جانب Successor نیز Reply ای ارسال می گردد.
***
میدونم که این قسمت شاید کمی سخت و پیچیده و البته طولانی بود اما درک این که EIGRP چطور عمل میکنه مهم ترین بخش در شناخت این پروتکل محسوب میشه. این قسمت هنوز ادامه داره اما برای این پست به نظرم رسید که تا همینجا فعلا کافی باشه. اما اگر علاقه پیدا کردید که اولین بار این الگوریتم چه شکلی و توسط چه کسی مطرح شد، می تونید از طریق این لینک به الگوریتم اولیه ی DUAL دسترسی پیدا کنید.
امیدوارم سال جدید، سالی پر از موفقیت و سلامت و شادی برای همه ی عزیزان باشه. ممنون از همراهی همیشگیتون.
سال نو مبارک 🙂
