الگوریتم مسیریابی حالت لینک (Link State Routing) – آموزش شبکه درس 29
الگوریتم مسیری یابی حالت مسیر (Link State Routing Algorithm) تکنیکی است که در آن روترها دانش خود درباره گره‌ها (Nodes) همسایه خودشان را با هر کدام از روترهائی که در یک شبکه وجود دارند به اشتراک می‌گذارند.
سه مفهوم کلیدی برای درک بهتر الگوریتم حالت لینک به شرح زیر است:
- داشتن دانش درباره گره‌های همسایه: در این روش، در ازای ارسال جدول مسیریابی (Routing Table) به تمام گره‌ها، یک روتر تنها اطلاعاتی را درباره گره‌هائی که در همسایگی خودش قرار دارند ارسال می‌کند. در این روش روتر هویت خود و هزینه لینک‌هائی که مستقیماً به او متصل هستند را به روترهای دیگر می‌دهد.
- سرازیر شدن (Flooding): هر کدام از روترها در این جا، اطلاعاتی را به روترهائی که در همسایگی خودش نیستند ارسال می‌کند. این فرایند به عنوان «سرازیرشدن- Flooding» شناخته می‌شود. هر روتری که پک‌های ارسال شده را دریافت می‌کند، کپی‌های از تمام همسایه‌های خودش را ارسال می‌کند. در نهایت هر کدام از روترها یک کپی از اطلاعات مشابه را در اختیار دارند.
- به اشتراک گذاری اطلاعات: یک روتر تنها زمانی اطلاعاتی را به روترهای دیگر می‌فرستد که قصد تبادل اطلاعات را داشته باشد.
دو مرحله الگوریتم مسیریابی حالت لینک
سرازیرشدن قابل اعتماد:
- شروع مرحله: هر کدام از لینک‌ها هزینه همسایگی خود را می‌داند؛
- خاتمه کار: هر کدام از گره‌ها کل گراف‌های موجود در شبکه را می‌شناسد؛
محاسبه مسیر
هر کدام از گره‌ها در اینجا از الگوریتم دایکسترا (Dijkstra’s Algorithm) بر روی گراف خود استفاده می‌کند تا بتواند مسیرهای بهینه را برای تمام گره‌ها به دست بیاورد.
- الگوریتم حالت لینک به عنوان الگوریتم دایکسرا نیز شناخته می‌شود. این الگوریتم برای یافتن کوتاه ترین مسیر از گره به هر کدام از گره‌های دیگر در شبکه به کار گرفته می‌شود.
- الگوریتم دایکسترا یک روند تکراری (Iterative) دارد و آن دارای ویژگی K است که تکرار الگوریتم را نشان می‌دهد. مسیرهای با حداقل هزینه برای K گره موجود در شبکه در این جا شناسائی می‌شوند.
برای درک بهتر، بیائید کمی با فرمول‌ها کار کنیم.
فرمول الگوریتم حالت لینک
در اینجا ما به چند مفهوم نیاز داریم که در ادامه توضیح داده ایم:
- C(I,j): این مقدار هزینه گره i به گره j را نشان می‌دهد. اگر گره i و j به صورت مستقیم نباشند در این صورت این مقدار برابر با c(i , j) = ∞ خواهد بود.
- D(V): این مقدار تعریف کننده هزینه مسیر از کد منبع تا مقصد V است که حداقل هزینه فعلی را داراست.
- P(V) این مقدار تعریف کننده گره‌های پیشین (گره‌های همسایه V) است که همراه با هزینه حداقلی مسیر جاری به منبع V است.
- N: این مقدار نشان دهنده تعداد گره‌هائی است که در شبکه وجود دارند.
اکنون برای درک بهتر به ساختار الگوریتم و نحوه به کاربردن این مقادیر نگاهی می‌اندازیم.
ساختار الگوریتم حالت لینک
nitialization
N = {A} // A is a root node.
for all nodes v
if v adjacent to A
then D(v) = c(A,v)
else D(v) = infinity
loop
find w not in N such that D(w) is a minimum.
Add w to N
Update D(v) for all v adjacent to w and not in N:
D(v) = min(D(v) , D(w) + c(w,v))
Until all nodes in N
در الگوریتم بالا، یک گام ابتدائی داریم که به وسیله یک حلقه دنبال می‌شود. تعداد دفعاتی که حلقه اجرا می‌شود، برابر با تعداد گره‌های موجود در شبکه است.
برای درک بهتر موضوع نگاهی به تصویر زیر داشته باشید:
نحوه مسیریابی در الگوریتم حالت لینک
در تصویر بالا، منبع ما ورتکس یا راس A است.
مراحلی که در اینجا اتفاق می‌افتد به شرح زیر است:
گام اول:
در گام اول یک مرحله ابتدائی یا آغازین وجود دارد. در این مرحله این دانش وجود دارد که کمترین هزینه از A مسیرهای مستقیم به همسایگانش است که در اینجا گره‌های B، C و D می‌شوند و مقدار هزینه‌های آن‌ها به ترتیب 2، 5 و 1 است. هزینه از A به B در اینجا برابر با 2 است و هزینه از A به D نیز در اینجا برابر با یک است و در نهایت هزینه A تا C برابر با 5 است. هزینه از A به E و F نیز بی نهایت است، زیرا آن‌ها به صورت غیر مستقیم به A متصل شده اند.
در جدول زیر این موضوع نمایش داده شده است:
| Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
| 1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |
گام دوم:
در جدول بالا، ما می‌توانیم ببینم که ورتکس D حاولی کمترین هزینه در مرحله اول است. به همین خاطر آن در N اضافه می‌شود و ما اکنون نیاز داریم که کم هزینه ترین مسیرها گذر کننده از D را بیابیم.
این کار را به صورت زیر انجام می‌دهیم:
- محاسبه کوتاه ترین مسیر از A به B
v = B, w = D D(B) = min( D(B) , D(D) + c(D,B) ) = min( 2, 1+2)> = min( 2, 3) The minimum value is 2. Therefore, the currently shortest path from A to B is 2.
- محاسبه کوتاه ترین مسیر از A به C
v = C, w = D D(B) = min( D(C) , D(D) + c(D,C) ) = min( 5, 1+3) = min( 5, 4) The minimum value is 4. Therefore, the currently shortest path from A to C is 4.</p>
- محاسبه کوتاه ترین مسیر از A به E
v = E, w = D D(B) = min( D(E) , D(D) + c(D,E) ) = min( ∞, 1+1) = min(∞, 2) The minimum value is 2. Therefore, the currently shortest path from A to E is 2.
- نکته: ورتکس D هیچ مسیر مستقیمی به ورتکس E ندارد. به همین خاطر مقدار D(f) به صورت بی نهایت محاسبه می‌شود.
در جدول زیر این مقادیر قرار داده شده اند:
| Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
| 1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |
| 2 | AD | 2,A | 4,D | 2,D | ∞ |
گام سوم:
در جدول بالا، ما می‌توانیم ببینیم که در مرحله دوم هر دو گره B و E حداقل هزینه را در مرحله دوم کسب کردند. اکنون بگذارید که به بررسی گره E بپردازیم. اکنون، ما می‌توانیم مشخص کنیم که حداقل هزینه مسیر در ورتکس باقیمانده E به چه صورت است.
- محاسبه کوتاه ترین مسیر از A به B
v = B, w = E D(B) = min( D(B) , D(E) + c(E,B) ) = min( 2 , 2+ ∞ ) = min( 2, ∞) The minimum value is 2. Therefore, the currently shortest path from A to B is 2.
- محاسبه کوتاهترین مسیر از A به C
v = C, w = E D(B) = min( D(C) , D(E) + c(E,C) ) = min( 4 , 2+1 ) = min( 4,3) The minimum value is 3. Therefore, the currently shortest path from A to C is 3.
- محاسبه کوتاه ترین مسیر از A به F
v = F, w = E D(B) = min( D(F) , D(E) + c(E,F) ) = min( ∞ , 2+2 ) = min(∞ ,4) The minimum value is 4. Therefore, the currently shortest path from A to F is 4.
در جدول زیر نتایج محاسبات بالا نشان داده شده است:
| Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
| 1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |
| 2 | AD | 2,A | 4,D | 2,D | ∞ | |
| 3 | ADE | 2,A | 3,E | 4,E |
گام چهارم:
در جدول بالا، ما می‌توانیم ببینیم که گره B دارای کمترین هزینه مسیر در مرحله سوم بوده است. به همین خاطر آن به N اضافه می‌شود. اکنون ما باید کم هزینه ترین مسیرهای باقیمانده که از ورتکس B می‌گذرند را محاسبه کنیم.
- محاسبه کوتاه ترین مسیر از A به C
v = C, w = B D(B) = min( D(C) , D(B) + c(B,C) ) = min( 3 , 2+3 ) = min( 3,5) The minimum value is 3. Therefore, the currently shortest path from A to C is 3.
- محاسبه کوتاه ترین مسیر از A به F
v = F, w = B D(B) = min( D(F) , D(B) + c(B,F) ) = min( 4, ∞) = min(4, ∞) The minimum value is 4. Therefore, the currently shortest path from A to F is 4.
نتیجه پردازش‌های بالا در جدول زیر نشان داده شده است:
| Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
| 1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |
| 2 | AD | 2,A | 4,D | 2,D | ∞ | |
| 3 | ADE | 2,A | 3,E | 4,E | ||
| 4 | ADEB | 3,E | 4,E |
گام پنجم:
در جدول بالا، ما می‌توانید ببینیم که ورتکس C دارای کمترین هزینه مسیر در مرحله چهارم است. به همین خاطر اکنون آن به N اضافه می‌شود و ما می‌توانیم کم هزینه ترین مسیرهائی که از ورتکس C می‌گذرند را محاسبه کنیم.
- محاسبه کوتاه ترین مسیر از A به F
v = F, w = C D(B) = min( D(F) , D(C) + c(C,F) ) = min( 4, 3+5) = min(4,8) The minimum value is 4. Therefore, the currently shortest path from A to F is 4.
در جدول زیر نتایج حاصل از محاسبه به دست آمده است:
| Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
| 1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |
| 2 | AD | 2,A | 4,D | 2,D | ∞ | |
| 3 | ADE | 2,A | 3,E | 4,E | ||
| 4 | ADEB | 3,E | 4,E | |||
| 5 | ADEBC | 4,E |
جدول نهائی:
در جدول زیر نتایج حاصل از این پردازش‌ها نشان داده شده اند:
| Step | N | D(B),P(B) | D(C),P(C) | D(D),P(D) | D(E),P(E) | D(F),P(F) |
| 1 | A | 2,A | 5,A | 1,A | ∞ | ∞ |
| 2 | AD | 2,A | 4,D | 2,D | ∞ | |
| 3 | ADE | 2,A | 3,E | 4,E | ||
| 4 | ADEB | 3,E | 4,E | |||
| 5 | ADEBC | 4,E | ||||
| 6 | ADEBCF |
معایب استفاده از این روش:
در این روش ترافیک سنگینی به خاطر وجود موضوع سرازیر شدن (Flooding) وجود دارد. سرازیر شدن می‌تواند سبب ایجاد حلقه‌های بی نهایت شودند و این مشکل تنها با استفاده از فیلد‌های زمان ترک (Time to Leave) قابل حل است.
