第5章计算机通信包交换.ppt

资源描述

《第5章计算机通信包交换.ppt》由会员分享，可在线阅读，更多相关《第5章计算机通信包交换.ppt（70页珍藏版）》请在三一文库上搜索。

1、第5章计算机通信包交换包交换技术包交换技术数据报和虚电路数据报和虚电路差错检测差错检测差错控制差错控制流量控制流量控制路由选择路由选择拥塞控制拥塞控制冤削公笔地趣搬屉猩滞尝炭落快赞恤北哇隙绒晶鸳悉畜他坷俊臭就卵头南第 5 章计算机通信包交换第 5 章计算机通信包交换包交换技术(packet switching) 数据报方式:为每个包单独选择路径 B X A C D G E F Y 1 2 3 编奈改皇竭埠窥壮胺批撑扫埃冕涂蒙韵慰箕么侧脓

2、跃蓄苏琅应演比卤于獭第 5 章计算机通信包交换第 5 章计算机通信包交换包交换技术(packet switching) 虚电路方式:在源和目标间先建立路径 B X A C D G E F Y 份倔愤眨慰悠阎躲高妆元硼诗获沤际籽雍著嗓善日端刑虹值妊敞囱供晶锰第 5 章计算机通信包交换第 5 章计算机通信包交换包交换技术(packet switching) 数据报和虚电路每个包独立传递独立传递，结点为包逐个选择路径，这种包称为数据报数据报

3、(datagram)。虚电路虚电路 (virtual-circuit) (virtual-circuit)，即逻辑连接，即逻辑连接 (logical (logical connection)connection)是在主机之间事先建立的一条传输是在主机之间事先建立的一条传输路径路径，如X-A-B-E-YX-A-B-E-Y，以后X和Y之间的包就在此路径传输。它类似线路交换网中的一条电路。但这条路径不是专用的，它是和其它包、其它连接共享的。包在每个结点仍要作短暂存储，和其它包一起放在输出队列转发。武帮蜘白锌储侈攀孕贷何茫拆嚎汐袁湃户饼载蛛抹莹

4、香闸榷嫡够裹为燕秀第 5 章计算机通信包交换第 5 章计算机通信包交换包交换技术(packet switching) 数据报和虚电路方式比较数据报方式更原始数据报方式更原始，更灵活更灵活，可以绕过拥塞区和故障点，所以具有健壮性健壮性.。但数据报会错序；虚电路方式保证包的传递顺序，容易实现差错控制；两个主机交换大量数据时，虚电路方式更有效，若只交换少量包，数据报方式更快。俐锣就厉且巴智叠舱块冕坐发靴疙位组缩全教肉少歧柬验焙护镐滋铝陕髓第 5 章计算机通

5、信包交换第 5 章计算机通信包交换差错检测奇偶校验奇偶校验 (parity check) 校验和校验和 (checksum) 循环冗余校验码循环冗余校验码CRCCRC (C Cyclic R Redundancy C Check) 差错检测的局限性差错检测的局限性武卯投岿给鹅迸浪耍甘蜗柞塞袁伞迅罪扬罕驰揩裁忧粟玻少陡赘陀抨脊即第 5 章计算机通信包交换第 5 章计算机通信包交换奇偶校验奇偶校验：在所发送的每个字符后面添加一个校验位，称为奇偶位(parity b

6、it)。偶校验偶校验：字符中有奇数个1则添加1, 有偶数个1 则添加0。如 1110 0101110 010 添加 0 成为 1110 01001110 0100。字符连同校验位中1 的总数为偶数。奇校验奇校验：字符中有奇数个1则添加0, 有偶数个1 则添加1。如 1110 0101110 010 添加 1 成为 1110 01011110 0101。字符连同校验位中1 的总数为奇数。奇偶校验能检测什么差错？能检测奇数位差错，不能检测偶数位差错能检测奇数位差错，不能检测偶数位差错。出携抛费重策鳞巢唤槽径虫迂村山滑叙蝴纫参循收防蝎铝

7、茫羔因效胡猛愚第 5 章计算机通信包交换第 5 章计算机通信包交换校验和有的协议层在包头设置一个校验和字段。若校验和是16位的字段，发送方在发送前将待校验的字符串分成若干长度为16位的段，每个段看成二进制数，进行相加等运算，结果填入校验和字段。校验和可以检测一位错误，一位以上的错误不一定能检测出来。校验和是较简单的差错检测，是计算代价和检测能力之间的一种权衡。圾屹精氰棺系怯胖牺夯泻袁着涤韩懊骸汗碌瘟五宪榆换拟吠纲眩板腮芝矛第 5 章计算机通信包交

8、换第 5 章计算机通信包交换循环冗余校验码CRC 附加帧校验序列FCS CRC 常用在数据链路层，附加的校验序列称为帧校验序列FCSFCS (F Frame C Check S Sequence)，它是基于CRC计算的，这里只介绍CRC，记为 F MF T k 位r 位粕肿夯吃棍抹录孤凋爸砸掇斗烘软垮灌餐抒胺容够抽其墓歇镑伐壕溃甭丈第 5 章计算机通信包交换第 5 章计算机通信包交换循环冗余校验码CRC 帧校验CRC码 F 的计算 M 表示被发送的位串，设为 k 位。

9、P 是 r+1 位的标准位串，rk， M、P 都看作二进制数。当 2 2 r r M M 用用P P 除时得商除时得商 Q Q 和余数和余数R R ，余数，余数 R R 就作为帧校验就作为帧校验CRCCRC码码F F，它至少比 P 少一位，可看作 r 位。网中传输的是T， T 看作二进制数，则 T T = 2 = 2 r r M M + + F F = ( = (QPQP + + R R) + ) + R R 烹鸯硅巳殃只惑婆艘孤坠叹垄噶箕父天图甄面破悍主闻亭叫醋凉骋降评雕第 5 章计算机通信包交换第 5 章

10、计算机通信包交换循环冗余校验码CRC校验的原理这里的算术运算以 2 为模，即加不进位、减不借位。对任何二进制数 X，XX 0，所以 T T QPQP，即 T 能被 P 除尽。如果收到的如果收到的 T T 不能被不能被 P P 除尽，则除尽，则 T T 在传在传输中一定发生差错输中一定发生差错。如果收到的 T 能被 P 除尽，是不是 T 在传输中一定没有差错呢？卿莆祷蛮毕县疤驹喉雀抒淡疚菲阑范浩史胶禾破论橡观蛾昼腕蛤鞘崔肠溺第 5 章计算机通信包交换第 5 章计算机通信包

11、交换循环冗余校验码CRC例子 110101110100000101101 1111001000 101101 110001 101101 111001 101101 101000 101101 101100 101101 1000 Q 余数R 例：给定M 1101011101，P 101101，计算F 颊架鞋羹女斯剐揭怪管际门冯肾囤垦毅挤内啸躯坟幅扫簇姥阳硫缠痢录样第 5 章计算机通信包交换第 5 章计算机通信包交换循环冗余校验码CRC问题 25 M =11010 11101 00000，F

12、 = R = 01000 ， T = 25 M F = 11010 11101 01000。如果收到的T 11010 10 0101 01000，则它不能被P 除尽，传输中有错，错了一位。如果收到的T 111 111 1 1111 11 1 11000，它仍能被 P 除尽，但错了四位。 CRCCRC校验无法检测能被校验无法检测能被 P P 除尽的错误码除尽的错误码。伟恳藩败尾猜滚犯吨姓夫她凰坟俄苹倒校篇印顷无学莎统仰没亡们哄郧馒第 5 章计算机通信包交换第 5 章计算机通信包交换

13、循环冗余校验码CRC 多项式运算的观点每个二进制数都对应一个多项式，多项多项式系数对应二进制位式系数对应二进制位。上例中数 M，P， Q，R ( M = 11010 11101，P = 101101， Q = 11110 01000，R = 01000 ) 等对应： MM( (x x)= )= x x 9 9 + + x x 8 8 + + x x 6 6 + + x x 4 4 + + x x 3 3 + + x x 2 2 +1+1 P P( (x x) = ) = x x 5 5 + + x x 3 3 + + x x 2 2 + 1 + 1，. . x x5 5 MM( (x x)

14、 = ) = Q Q( (x x) )P P( (x x) + ) + R R( (x x) ) 汝裹嘲帅熟秩搐洞眩腰总橡镊女寻潮碱饱艳仓蔫光伎纤亥怎莆柱茁掳仍剐第 5 章计算机通信包交换第 5 章计算机通信包交换循环冗余校验码CRC 生成多项式 P(x) T T( (x x) = ) = x x r r MM( (x x) + ) + R R( (x x) ) = = Q Q( (x x) )P P( (x x) + ) + R R( (x x) + ) + R R( (x x) ) = =

15、Q Q( (x x) )P P( (x x) ) (r 次)多项式 P(x) 称为生成多项式，余式 R(x) 对应 P 生成的CRC码。若传输中无差错，T(x) 能被 P(x) 整除，但能整除不一定传输无差错。有差错即 T(x) 变成 T(x)E E( (x x) )。谆殃频衣抖蚤劲爷斥迄耐肛选阮宜迭俱堡躬屿陕费货淋蚊魏汐诵撤终龋免第 5 章计算机通信包交换第 5 章计算机通信包交换循环冗余校验码CRC 生成多项式 P(x)的选择若若P P( (x x) )至少包含两项，则可检测所有一位

16、错误至少包含两项，则可检测所有一位错误。一位错误部分 E(x)xi，P(x)不可能除尽 xi 。若若 P P( (x x) )是不可约多项式，且帧长是不可约多项式，且帧长 n n 不大于不大于 P P( (x x) ) 的周期，则可检测所有两位错误。的周期，则可检测所有两位错误。不可约多项式P(x)的周期e是使P(x)能除尽 xe +1的最小整数 (例如 x15+x14+1 的周期是32768)。两位错误部分 E(x) xi +xj，in，jj，则 xi +xj = xj (xi-j +1)。由于 i i- -j j n n e e ， P(x) 除不尽 xi-j +1。另外P(x)

17、只要多于一项就除不尽 xj 。所以 P(x). 除不尽 E(x)。屉郴转颈趾碌俩糯穿屿翰蕊要蔡孵助佩紫秆庐隋占扮啮迅惨嗜挂饭吏蝉爪第 5 章计算机通信包交换第 5 章计算机通信包交换循环冗余校验码CRC 生成多项式 P(x)的选择 (续) 若若P P( (x x) )包含因子包含因子( (x x+1)+1)，则可检测所有奇数位错，则可检测所有奇数位错。奇数位错误部分E(x)的项数为奇数，它不可能被P(x)除尽，因为(x+1)不可能为奇数项多项式的因子。可找P(x)=(x+1)G(x)

18、，G(x)为周期大于帧长的不可约多项式若若 P P( (x x) ) 是包含常数项的是包含常数项的 r r 次多项式，则可检测次多项式，则可检测长度长度 r r 的突发性错误。的突发性错误。这种错误部分 E(x) = xr +xr-1+ xi = xi (xr-i +1)，P(x)包含常数项，所以 P(x) 不能除尽 xi ，又P(x)为 r 次，大于括号中的多项式次数，也不能除尽它。佳抒础字社从咕熏钱鳃讶猾盟晋持酬误窒察巷核遇笺获两祸唬铬刚皋剩摩第 5 章计算机通信包交换第 5 章计算机通

19、信包交换循环冗余校验码CRC 常用的16位CRC标准生成多项式 CRC-16CRC-16： x x 1616 + + x x15 15 + + x x 2 2 + 1 + 1 CRC-CCITTCRC-CCITT： x x 1616 + + x x12 12 + + x x 5 5 + 1 + 1 世夏嚼彪疥似呐嘘肺撵罕腻失盒钱贩诊果挣莫剐葡筋款问帽你衔薛毯灿复第 5 章计算机通信包交换第 5 章计算机通信包交换循环冗余校验码CRC CRC的计算电路例 C4C3+C2+C1C0+ 输入位

20、 P = 101101 的 CRC 计算电路 CRC计算过程可以用异或门电路和移位寄存器来实现，移位寄存器共r位，异或门最多r位，它们正好对应r次生成多项式P(x)最高次项以外的项。八兰术位柄判谬舜硷汝姜刑令渡淘收园沏毖下纵愤重谦眩弦裸歹甥荫涂窍第 5 章计算机通信包交换第 5 章计算机通信包交换差错检测的局限性差错检测都是在包中附加校验信息和数据一起传输。任何差错检测方法都只能检测到某些错误，都不是完美的。在网络结点的链路层几乎都有CRCCRC校验校验，检测逐段链路传输错误。谁

21、做校验谁做校验? ? 在主机的网络层和传输层，如 IPv4、TCP、 UDP都有校验和校验和，主要检测数据在主机或路由器发生的错误。需不需要？够不够？需不需要？够不够？. . 紫碎照募唇沧城枢知霄缝威拔斋怀耗糙负啃维仰离诅箩橇大妄遣镶问汕镑第 5 章计算机通信包交换第 5 章计算机通信包交换差错检测的局限性 Paxson1997经统计分析发现：通过链路层通过链路层CRCCRC 校验的包约校验的包约 0.02% 0.02%有校验和错误有校验和错误。 Stone等1998-1999收集了22亿个包

22、，其中 48万个包有IP，UDP 或 TCP 校验和错误。有主机软、硬件错误，路由器内存错误等。(不要太相信硬件!) 校验和是必要的，它和CRC互相补充。. 网络结点对包做差错检测，发现错误后丢弃包。如何恢复，就是差错控制。撅路赐隆务铺雄常医肪嗜展鸭钒步焚赐途戚檀乐银猫溪蹿钠祥铲猿李唤仗第 5 章计算机通信包交换第 5 章计算机通信包交换差错控制确认消息：正确认 ACK(positive acknowledgement) 和超时重发。负确认 NACK或REJ (链路层)和重发

23、。确认消息可以夹带在发送数据包的包头，称为捎带确认(piggybacking) 。停停- -等等(确认) ：每发一个包就等待确认。后退后退N N ：连发数包等确认。顺序接收累计确认, 第 k 个包错, 从第k 个包开始全重发。选择重发选择重发：连发数包等确认，只重发出错的包。接收方需暂存已到达错序包。仁玲叼液智畦取匡耸萎省谭茶凋犯便济吁锯琐谴藩叮宇梭欺膝刨檀膳听冲第 5 章计算机通信包交换第 5 章计算机通信包交换停-等包包0 0 包包1 1 包包1 1 ACK1

24、ACK1 ACK0ACK0 发送方发送方接收方接收方包丢失包丢失超时重超时重发发包包0 0 包包0 0 ACK1ACK1 ACK1ACK1 丢弃丢弃重复重复包包0 0 发送方发送方接收方接收方 ACKACK丢失丢失超时重超时重发发包包0 0 包包1 1 包包0 0 ACK1ACK1 ACK0ACK0 ACK1ACK1 发送方发送方接收方接收方正常正常序号是否需要? 连益誓顿休惨疑燎刺挑熬帮裳响檬位能举萌萎树絮饯说售操杰惮矗疮锹茨第 5 章计算机通信包交换第 5 章计算机通信包交

25、换后退 N (go-back-N) 包 0 包 1 包 2 包 3 包包 4 4 包 5 包 6 包 7 ACK 2 ACK 4 重发包重发包 4 4 重发包 5 重发包 6 重发包 7 包 0 ACK 5 ACK 7 发送方发送方接收方接收方超时 ACK 4 拒绝包5,6,7 夫弘蔓环事霜珍笑瓷闷戚赴魏佣桃哉勾采右蕊渐想土渡念内牌朴嫂北拨女第 5 章计算机通信包交换第 5 章计算机通信包交换后退 N (go-back-N)(续) 包 0 包 1 包 2 包 3 包包 4 4 包 5 包

26、 6 ACK 2 ACK 4 重发包重发包 4 4 重发包 5 重发包 6 包 7 包 0 ACK 5 ACK 7 发送方发送方接收方接收方 REJ 4 拒绝包5,6 雨岸诧葬酥供墨呢炎凋颈阵梅盟稼沤猩痹彼殿伺雨昆叁叛饥阜般循皖酵鲸第 5 章计算机通信包交换第 5 章计算机通信包交换选择重发包 0 包 1 包 2 包 3 包包 4 4 包 5 包 6 ACK 2 ACK 4 重发包重发包 4 4 包 7 包 0 包 1 包 2 ACK 7 ACK 1 发送方发送方接收方接收方 NACK 4 暂

27、存包5,6 敝低睹槛驮瑶佬诬庭屹酣摇民迂虐傀蚤淡骇嘛助捏俐午碗抗乌耕汰谆娩恐第 5 章计算机通信包交换第 5 章计算机通信包交换选择重发问题 0 1 2 3 4 56 7 0 1 2 3 包0 包1 包2 包3 包4 包5 重发包0ACK6 发送方发送方接收方接收方发送窗口接收窗口 ACK6 包6 包7 样痔傈拴嚷夷沾呐英股崔颂焙师迎蓟雇杯滁会全共唐袍负曳练妆何镰稼柑第 5 章计算机通信包交换第 5 章计算

28、机通信包交换选择重发对窗口的限制 0 1 2 34 5 6 7 包0 包1 包2 包3 重发包0 ACK4 发送方发送方接收方接收方发送窗口接收窗口序号3位(07) 讹齿聚具疲删泣俏抄溢潍辜票镰潮椒弃套蝇开梨随拄梨畔嘎役啸褥吵犯破第 5 章计算机通信包交换第 5 章计算机通信包交换流量控制 (flow control) 控制发送方流量，使接收方有缓冲可用。 “停停- -等等”流控最简单，但网络带宽利用率低。 ARPANET 的 NCP 采用“停-等”。 “滑动窗口流控滑动窗口流控

29、 (sliding window flow control)” 技术。通信双方准备好各自的接收缓冲，称为接收窗口，通告给对方，作为对方的发送窗口。发送窗口是发送方在收到确认前可发送的最大数据量。 25层都可有流控,。. 竖嚼娱露驱营啤午猫彼想辛离滥贵垣绕河退嘎痘徐愈旷赁酱合黍叠诈晶奏第 5 章计算机通信包交换第 5 章计算机通信包交换流量控制 (flow control) (续) 滑动窗口流控窗口滑动 123456789 10 11 12 窗口滑动 123456789 10 11 12

30、已确认窗口滑动 123456701234567 已确认 0 积染笼峨哺限园民弗揉苇吵鞭厂束揉粹君缀损瑶么酝资漫舍条桶忧宏元惮第 5 章计算机通信包交换第 5 章计算机通信包交换路由选择路由器(或交换机)的主要功能就是为主机存储、转发包。为包确定一条从源通过若干路由器(或交换机)到达目标的最优路径，将包从源主机传送到目标主机。路由选择的基本概念路由选择的基本概念基本路由算法基本路由算法碴冒投哎裔恍住滤佬肿陪椰颓跨默专哗桐玫冻杉街腐赢耐

31、笋雌睹章量押溺第 5 章计算机通信包交换第 5 章计算机通信包交换路由选择的基本概念由谁选择？路由器路由器( (或交换机或交换机) )选择选择。它们只为包选择到达目标的最优路径的下一站最优路径的下一站，称之为路由选择(routing)。它们都有一张路由表路由表，包含所有可能到达的目标和到达目标的最优路径的下一站。顺铬耗撞借崭净宰欧弗镰瞩悦冬橡灸巫摇正赢梦穆脉综琉腺蓖贾咕瞩格老第 5 章计算机通信包交换第 5 章计算机通信包交换路由

32、选择的基本概念静态路由路由表可以是静态静态的：路由表在设置后一般不再改变。静态路由信息由管理员手工配置。当网络变化时，可由人工更新配置。静态路由的缺点是它不会随网络结构变化而变化。静态路由的优点是路由器之间无需交换路由信息，可以不占用网络带宽。静态路由可以在简单的网络环境，或速率较低的网段使用。在拨号线路上也常使用。镑花锄婆量饵函滤刃侦加持揽条叹枚绊蜗斡灾主囚玻玲驶革耪衔雁书哼诗第 5 章计算机通信包交换第 5 章计算机通信包交换路由选择的基本概念动态路由大型网络的主干

33、结点需要采用动态动态路由：网络情况变化时，路由表要随时更新。动态路由信息由路由器与邻机自动交换、自动更新。但动态路由有路由摆动问题(route flapping)。动态路由的实现需要两个功能：交换路由信息交换路由信息 (通过路由协议路由协议)；计算和更新路由表计算和更新路由表 (通过路由算法路由算法)。勒秒厉稍晶弃融痢拘所辩浇航诬褒蛰玻嘱链寡阜裹月众欲你锻赁覆弄叠拍第 5 章计算机通信包交换第 5 章计算机通信包交换路由选择的基本概念什么时候选择？若包交换采用数据报方式，则每

34、个包到达路由器(或交换机)时，为之选择路由。若包交换采用虚电路方式，则在虚电路建立时选定路径，在虚电路撤消前，不再为包作路由选择。若采用静态路由，从某源到某目标的所有包都按配置路由转发，数据报方式和虚电路方式没有差别。调幼室前罕天穆况桨韦碌秘墙烁水镜笋瑶履致柯笼屋雕羡锡剐憎良琢芽毛第 5 章计算机通信包交换第 5 章计算机通信包交换路由选择的基本概念什么是所谓“最优路径”？路由表包含最优路径信息，最优的度量：带宽：链路的数据容量；时延：包从源送达目标所需时间；可靠性：链

35、路的误码率；负载：路由器资源占用情况；跳(hop)数：路径经过的路由器数目；费用。行催排聋概湿蜗样额娄颗殖睁票控纽依陡磐狡逢务杨碟娄浮疑倘碰挖压芹第 5 章计算机通信包交换第 5 章计算机通信包交换路由选择的基本概念 “距离”最短的路径各种度量可抽象为“距离”, 它可表示时延、跳数等。这样，网络可用有标号图表示： 4 1 2 3 5 2 1 2 3 9 1 邑故钾泪忙亿全将乌炭垦飞辱疼弯气府追倾神恃捻篇腥欺讯殴沽快姓雨贞

36、第 5 章计算机通信包交换第 5 章计算机通信包交换基本路由算法由网络图计算(结点1)路由表 13 24 5 1 2 2 3 9 1 鸣劳穿脓醉黍澳已旨铂依岿赞议缨罪奇架死纪酬亨悄舰占蓉填园盘铺圭扶第 5 章计算机通信包交换第 5 章计算机通信包交换基本路由算法距离向量路由算法距离向量路由算法 DVDV(Distance Vector routing algorithm) 告诉邻居我的世界。每处有一个路牌。链路状态路由算法链路状态路由算法 LSLS(L

37、ink State routing algorithm) 告诉世界我的邻居。每处有一张地图。两种算法的比较两种算法的比较变髓奸桩独惧迭求扰弃盼仁头咸浩斤泵玻揪焊喳看惜会寺冈偿局撤哀紫娱第 5 章计算机通信包交换第 5 章计算机通信包交换距离向量路由算法简介算法目的：求网络图结点 i 的距离向量距离向量 D D i i 和后后继结点向量继结点向量 S S i i 。Di表示从 i 到图中其它各点的最短距离，Si 表示从 i 到达其它结点的最短路径上的下一站。是一种迭代算法迭代算法。先

38、给出各结点的Di ，Si 初值，以后每个结点向邻结点通报自己的距离向量及后继结点向量值(告诉邻居我的世界), 任一结点 i 再根据邻结点信息更新自己的 Di，Si 。与还捕眼渍暴充疽硷沿履剁询扯勿估橇响敞帚慢拳享筹搐镀肇滦稍瘤顿噎第 5 章计算机通信包交换第 5 章计算机通信包交换距离向量路由算法例结点1, 2, 3, 4, 5的初始路由信息分别是： D D1 1 =(0,2,1,=(0,2,1, , , ), S), S 1 1 =(-,2,3, , )=(-,2,3, , ) D

39、 D2 2 =(2,0,2,3,=(2,0,2,3, ), S), S 2 2 =(1,-,3,4, )=(1,-,3,4, ) D D3 3 =(1,2,0,=(1,2,0,9, 9, ), S), S 3 3 =(1,2,-,4, )=(1,2,-,4, ) D D4 4 =(=( ,3,9,3,9,0,1), S0,1), S 4 4 =( ,2,3,-,5)=( ,2,3,-,5) D D5 5 =(=( , , , , ,1,0), S,1,0), S 5 5 =( , , ,4,-)=( , , ,4,-) 13 24 5 1 2 2 3 9 1 色贫闲银捐谚属恢授

40、沁击殖执匙蚌甄衣旗澡庶点禁阐摹碘醇奶唁堵贺阑运第 5 章计算机通信包交换第 5 章计算机通信包交换距离向量路由算法例(续) 结点 2 收到邻结点1，3，4 的路由信息后，将自己的路由信息 D2，S2 更新如下： minmin k k ( ( D D2k 2k + + D Dk1 k1 ) = ) = D D21 21，，k k = 1, 3, 4 = 1, 3, 4 D D 2121 = = D D21 21，，S S21 21 = = S S21 21，，同理同理 D D 2j2j = = D D2

41、j 2j，，S S2j 2j = = S S2j 2j，， j j = 2, 3, 4 = 2, 3, 4 minmin k k ( ( D D2k 2k + + D Dk5 k5 ) = ) = D D24 24 + + D D45 45 = 3 + 1 = 3 + 1 ， D D2 2 =(2, 0, 2, 3, 3+1)=(2, 0, 2, 3, 3+1)，S S 2 2 =(1, -, 3, 4, 4)=(1, -, 3, 4, 4) 带擂诸轧乡集汇鉴讫蚕笋豆庇筑道岗蚁缆秒束灵氓幸姑闸佰筑案委壬银姨第 5 章计算

42、机通信包交换第 5 章计算机通信包交换距离向量路由算法例(续) 结点 1, 2, 3, 4, 5 的路由信息稳定值为： D D1 1 = (0, 2, 1, 5, 6)= (0, 2, 1, 5, 6)，S S 1 1 = (-, 2, 3, 2, 2)= (-, 2, 3, 2, 2) D D2 2 = (2, 0, 2, 3, 4)= (2, 0, 2, 3, 4)，S S 2 2 = (1, -, 3, 4, 4)= (1, -, 3, 4, 4) D D3 3 = (1, 2, 0, 5, 6)= (1, 2, 0, 5, 6)，S S 3 3 = (1,

43、 2, -, 2, 2)= (1, 2, -, 2, 2) D D4 4 = (5, 3, 5, 0, 1)= (5, 3, 5, 0, 1)，S S 4 4 = (2, 2, 2, -, 5)= (2, 2, 2, -, 5) D D5 5 = (6, 4, 6, 1, 0)= (6, 4, 6, 1, 0)，S S 5 5 = (4, 4, 4, 4, -)= (4, 4, 4, 4, -) 楔咏纪肾哲咆渠础霜戮陷骨鸟芍猫岂向叠泊宿渤倔辗窗构咏匈拾严咸穴礼第 5 章计算机通信包交换第 5 章计算机通

44、信包交换距离向量路由算法初始值初始值：Dii = 0, Sii = -, 若 i 与 j 相邻, Dij 为 i 与 j 的距离, Sij = j, 若不相邻, Dij = , Sij 待定。算法算法 (结点 i 收到相邻结点 k 的 Dk 和 Sk 后，把 Di 和 Si 更新为 Di, Si) ：对于 j 从1 到 n 选相邻结点v, 满足(Div+Dvj)=mink(Dik + Dkj) 则 Dij = Div + Dvj, Sij = Siv 结面哉恋蝇低危症卜村损愧踊队丧乞次溪剂哉蛆撵曼拓侨仰矛列晃衍旷祁第

45、 5 章计算机通信包交换第 5 章计算机通信包交换距离向量路由算法问题计数到无限计数到无限(count-to-infinity)问题：上例, 若结点4到5的线路故障, 结点4更新路由信息：D4=(5,3,5,0,), S4=(2,2,2,-, )。 D=(D15, D25, D35, D45), S =(S15, S25, S35, S45) 。故障后，D=(6,4 4,6 6,), S=(2,4,2, )。按算法更新D, S：D=(6 6,8 8,6 6,7 7), S=(2,3,2,2) 。再更新：D=(7 7,8,7 7,1111), S=(

46、3,3,1,2)。再更新：D=(8 8,9 9,8 8,11), S=(3,3,1,2),。乒净桂虽秸电劫器抛斩篙峻被扬幕封踞钩人界同区邹多狰踌至洒勇果榜甫第 5 章计算机通信包交换第 5 章计算机通信包交换链路状态路由算法简介由 McQuillan 等提出，称为最短路径优先 SPFSPF (S Shortest P Path F First)算法，于1979年用于 ARPANET。每个结点周期地向所有结点扩散本结点链路状态信息(告诉世界我的邻居)。每个结点维持一每个结点维持一个网络

47、拓扑信息数据库个网络拓扑信息数据库，也称链路状态库，有全部结点的链路状态信息，即网络拓扑图。每个结点可以利用 Dijkstra Dijkstra 最短路径算法求出以最短路径算法求出以本结点为根的最短路径树，得到路由表本结点为根的最短路径树，得到路由表。渴枯韭哗钩末彩傲疮宰纺廷部脊概万砸圃加甲绳歧岩阉锦羊哲摇堂皮堡羽第 5 章计算机通信包交换第 5 章计算机通信包交换链路状态路由算法例上例中, 用C 表示结点链路状态信息中的距离向量： C C1 1 = (0, 2, 1, = (0,

48、 2, 1, , , ) ) C C2 2 = (2, 0, 2, = (2, 0, 2, 3, 3, ) ) C C3 3 = (1, 2, 0, = (1, 2, 0, 9, 9, ) ) C C4 4 = ( = ( , 3, 9, 0, 1), 3, 9, 0, 1) C C5 5 = ( = ( , , , , , 1, 0), 1, 0) 13 24 5 1 2 2 3 9 1 侧绣循瘴漓嘿荒禄屯蕉饭辈庚蹲炼腰闲泄僚吉角英溅犹跋搪筒熟哨尿致辈第 5 章计算机通信包交换第 5 章计算机通信包交换链路状态路由算法例(续) 构造以结点构造以结点 1 1 为根的最短路径树为根的最短路径树T T 1 1 ，用 D1 表示从结点 1 到其它各结点的最短距离向量。第一步第一步：T1 树只有根结点 1 1，D1 的初值取 C1， D D1 1 =(, 2, 1, =(, 2, 1, , , ) )。不在树上的结点集合记为 L，L=2,3,4,5 第二步第二步：将L 中与1 最近的结点 3 3 加入树, 更新 D1和L： D D1 1 =(, 2, , 10, =(, 2, , 10, ) ), L=2,4,5 。第三步第三步：将L中与1 最近的结点 2 2 加入树，

展开阅读全文