شبکه‌های کامپیوتری/مسیریابی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۶۶:
[[Image:Dijkstra algorithm example 5.svg]]
{| style="text-align: center; background-color:#FFFFDD;" cellpadding=3 border=1 cellspacing=0
سطر ۹۵ ⟵ ۹۶:
| L || 15 || K
|}
جدول نشان می دهد که اگر روتر J بخواهد بسته ها را به روتر D بفرستد، ابتدا باید آن را به روتر H ارسال کند. هنگامی که بسته ها به روتر H می رسند، روتر کنونی جدول خود را بررسی می کند و تصمیم می گیرد که بسته ها را به D ارسال کند. در الگوریتم های بردار فاصله، هر روتر باید مراحل زیر را دنبال کند:
1. وزن لینک هایی که به طور مستقیم به آن متصل شده است را شمارش می کند و اطلاعات را در جدول خود ذخیره می کند.
2. در یک دوره زمانی خاص، روتر جدول خود را به روترهای همسایه خود (نه همه روترها) ارسال می کند و جدول مسیریابی هر یک از همسایگانش را دریافت می کند.
3. براساس اطلاعاتی که روتر از جداول مسیریابی همسایگان خود دریافت می کند، خود را به روز می کند.
بیایید یک نمونه دیگر (شکل زیر را نشان بدهیم) را در نظر بگیریم.<br />
[[Image:Pic DV 1.svg]]
The cost of each link is set to 1. Thus, the least cost path is simply the path with the fewer hops. The table below represents each node knowledge about the distance to all other nodes:
<br />
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
! rowspan="2" | Information <br/> stored at node
! colspan="7" | Distance to reach node
|-
! A !! B !! C !! D !! E !! F !! G
|-
! A || 0 || 1 || 1 || <math>\infty</math> || 1 || 1 || <math>\infty</math>
|-
! B || 1 || 0 || 1 || <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || <math>\infty</math>
|-
! C || 1 || 1 || 0 || 1 || <math>\infty</math> || <math>\infty</math> || <math>\infty</math>
|-
! D || <math>\infty</math> || <math>\infty</math> || 1 || 0 || <math>\infty</math> || <math>\infty</math> || 1
|-
! E || 1 || <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0 || <math>\infty</math> || <math>\infty</math>
|-
! F || 1 || <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0 || 1
|-
! G || <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 1 || <math>\infty</math> || 1 || 0
|}
<br />
Initially, each node sets a cost of 1 to its directly connected neighbors and infinity to all the other nodes. Below is shown the initial routing table at node A:
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
! Destination !! Cost !! Next Hop
|-
| B || 1 || B
|-
| C || 1 || C
|-
| D || <math>\infty</math> || -
|-
| E || 1 || E
|-
| F || 1 || F
|-
| G || <math>\infty</math> || -
|}
During the next step, every node sends a message to its directly connected neighbors. That message contains the node's personal list of distances. Node F, for example, tells node A that it can reach node G at cost of 1; node A also knows that it can reach F at a cost of 1, so it adds these costs to get the cost of reaching G by means of F. Because 2 is less than the current cost of infinity, node A records that it can reach G at a cost of 2 by going trough F. Node A learns from C that node B can be reached from C at a cost of 1, so it concludes that the cost of reaching B via C is 2. Because this is worse than the current cost of reaching B, which is 1, the new information is ignored. The final routing table at node A is shown below:
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
! Destination !! Cost !! Next Hop
|-
| B || 1 || B
|-
| C || 1 || C
|-
| D || 2 || C
|-
| E || 1 || E
|-
| F || 1 || F
|-
| G || 2 || F
|}
The process of getting consistent routing information to all the nodes is called '''convergence'''.
The final set of costs from each node to all other nodes is shown in the table below:
{| border=1 cellpadding=5 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
! rowspan="2" | Information <br/> stored at node
! colspan="7" | Distance to reach node
|-
! A !! B !! C !! D !! E !! F !! G
|-
! A || 0 || 1 || 1 || 2 || 1 || 1 || 2
|-
! B || 1 || 0 || 1 || 2 || 2 || 2 || 3
|-
! C || 1 || 1 || 0 || 1 || 2 || 2 || 2
|-
! D || 2 || 2 || 1 || 0 || 3 || 2 || 1
|-
! E || 1 || 2 || 2 || 3 || 0 || 2 || 3
|-
! F || 1 || 2 || 2 || 2 || 2 || 0 || 1
|-
! G || 2 || 3 || 2 || 1 || 3 || 1 || 0
|}
The cost of each link is set to 1. Thus, the least cost path is simply the path with the fewer hops.
One of the problems with distance vector algorithms is called "count to infinity." Let's examine the following problem with an example:
Consider a network with a graph as shown below. There is only one link between D and the other parts of the network.
[[Image:Dijkstra algorithm example 13.svg]]
with vectors
d [A][A] = 0 d [A][B] = 1 d [A][C] = 2 d [A][D] = 3
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
|-
! !! A !! B !! C !! D
|-
! A
| 0 || 1 || 2 || 3
|-
! B
| 1 || 0 || 1 || 2
|-
! C
| 2 || 1 || 0 || 1
|-
! D
| 3 || 2 || 1 || 0
|}
Now the C to D link crashes
So cost [C][D] = ∞
C used to forward any packets with address D directly on the CD link, but now link is down, so C has to recompute its distance vector (and make a new choice of how to forward packets to D) - similarly D has to update its vector. After updating their vectors at C and D, we have
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
|-
! !! A !! B !! C !! D
|-
! A
| 0 || 1 || 2 || 3
|-
! B
| 1 || 0 || 1 || 2
|-
! C
| 2 || 1 || 0 || 3
|-
! D
| <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0
|}
C views B as the best route to D, with cost 1 + 2, so C sends new vector to B. B learns that its former choice for sending to D via C now has higher cost, so B should recompute its vector.
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
|-
! !! A !! B !! C !! D
|-
! A
| 0 || 1 || 2 || 3
|-
! B
| 1 || 0 || 1 || 4
|-
! C
| 2 || 1 || 0 || 3
|-
! D
| <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0
|}
View of B is that routing to D can either go via A or C with equal cost - B sends updated vector. Both A and C get updated vector from B and learn that their preferred route to D now has higher cost, so they recompute their own vectors.
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
|-
! !! A !! B !! C !! D
|-
! A
| 0 || 1 || 2 || 5
|-
! B
| 1 || 0 || 1 || 4
|-
! C
| 2 || 1 || 0 || 5
|-
! D
| <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0
|}
Then A and C send their vectors, B has to update its vector again, sending another round to A and C, obtaining.
{| border=1 cellpadding=10 cellspacing=0 style="text-align: center; background-color: #FFFFDD;"
|-
! !! A !! B !! C !! D
|-
! A
| 0 || 1 || 2 || 7
|-
! B
| 1 || 0 || 1 || 6
|-
! C
| 2 || 1 || 0 || 7
|-
! D
| <math>\infty</math> || <math>\infty</math> || <math>\infty</math> || 0
|}
Notice that the routing table is very slowly converging to the fact that
d [x][D] = ∞ for x = A or x = B or x = C
This process loops until all nodes find out that the weight of link to D is infinity. In this way, experts say that distance vector algorithms have a slow convergence rate. In conclusion, distance vector algorithm is not robust. One way to solve this problem is for routers to send information only to the neighbors that are not exclusive links to the destination. For example, in this case, B should not send any information to C about D, because C is the only way to D.
| |||