Destination A b C D E F 4 AB ABC ABFD AE AEF 9 8 3 2 4 B 20 C ABc BA BC BFDBFEBF 10 8 3 3 2 CBA CB CDCECEF A D 3 3 4 20 10 DFBA DFB DC DCE DF 50 3 3 5 EA EFBECECD EF 4 5 FEFA FBFEC FE Fig. 5-8.(a)A subnet with line capacities shown in kbps.(b) The traffic in packets/sec and the routing matrix
Line n;(pkts/sec) C;(kbps) uC;(pkts/sec)I T; (msec) Weight AB 14 25 91 0.171 2 BC 12 20 25 77 0.146 3 CD 10 12.5 154 0.073 4AE 71 0.134 5 EF 13 50 62.5 0.159 6 FD 8 10 12.5 222 0.098 7BF 10 20 25 67 0.122 8 EC 59 0.098 Fig. 5-9. Analysis of the subnet of Fig. 5-8 using a mean packet size of 800 bits. The reverse traffic(BA, CB, etc. )is the same as the forward traffic 1/|u=800bts 根据排队论,平均延迟T=1/(μC-x)
▪ 1/ = 800 bits ▪ 根据排队论，平均延迟 T = 1/ (C - )
7.2路由算法(8) 7.2.5距离向量路由算法( Distance Vector Routing) 属于动态路由算法,也称 Bellman-Ford路由算法和 Ford- Fulkerson算法,最初用于 ARPANET,被RP协 议采用 基本思想 距离和线路,并通过亐相邻路由器交换距离信息来更新表 器的佳蹭夷露为素劉蘧的荤政 两部分:到达目的 时间或距离 蹈离裳时阊時氅毘饕餒霉謇邻焻结蠹髮粢矞忑曰的结点 邻居结点X发来的表中,X到路由器的距离为X,本路由器到X 的距离为m, 则路由器经过X到的距离为×+m 根据不同 居发来的信息,计算Ⅹ+m,并取最小值,更新本路由器的路 由表; 注意:本路由器中的老路由表在计算中不被使用
7.2 路由算法（8） 7.2.5 距离向量路由算法（Distance Vector Routing） ▪ 属于动态路由算法，也称Bellman-Ford路由算法和 Ford-Fulkerson算法，最初用于ARPANET，被RIP协 议采用。 ▪ 基本思想 - 每个路由器维护一张表，表中给出了到每个目的地的已知最佳 距离和线路，并通过与相邻路由器交换距离信息来更新表； - 以子网中其它路由器为表的索引，表项包括两部分：到达目的 结点的最佳输出线路，和到达目的结点所需时间或距离； - 每隔一段时间，路由器向所有邻居结点发送它到每个目的结点 的距离表，同时它也接收每个邻居结点发来的距离表； - 邻居结点X发来的表中，X到路由器i的距离为Xi，本路由器到X 的距离为m，则路由器经过X到i的距离为Xi + m。根据不同邻 居发来的信息，计算Xi + m，并取最小值，更新本路由器的路 由表； - 注意：本路由器中的老路由表在计算中不被使用
7.2路由算法(9) New estimated Router delay from J To A K Line AO 20 21 8|A B|12 36 31 28 C25 18 19 36 D40 E14 22 F[2320 40 G18 31 6 31 H[17_20o_19 12 21 11 7 10 K24 22 22 6 33 9 15 delaydelaydelay delay New routing 8 10 12 6 table for j Vectors received from J's four neighbors Fig. 5-10.(a)A subnet.(b)Input from A, 1,h, K, and the new routing table for J
7.2 路由算法（9）
7.2路由算法(10) 无限计算问题 算法的缺陷:对好消息反应迅速,(当A连上网时)对坏消息反应迟钝 A B C D E A b C D E ∞∞ oo Initially 1 2 3 4 Initially oo After 1 exchange 3 2 3 4 After 1 exchange 2∞ oo After2 exchanges 343 4 After 2 exchanges 123∞Afer3 exchanges 5 4 5 4 After 3 exchanges 1 23 4 After 4 exchanges 5 6 5 6 After 4 exchanges 67 6 After 5 exchanges 7 8 7 8 After 6 exchanges Fig. 5-11. The count-to-infinity problem
7.2 路由算法（10） ▪ 无限计算问题 - 算法的缺陷：对好消息反应迅速， (当A 连上网时）对坏消息反应迟钝