计算机网络课件

第五章 网络互连技术（三）李崇荣清华大学信息网络工程研究中心2003年11月19日清华大学信息学院平台课程《计算机网络》1清华大学信息网络工程研究中心第五章 网络互连技术5.1 网络互连的基本概念5.2 地址5.3 路由选择算法5.4 路由选择协议概述2清华大学信息网络工程研究中心路由技术的基本概念1）什么是路由(routing)技术2）路由技术在网络中的地位和作用3）有关路由的一些名词概念4）路由选择的基本活动5）路由的实现3清华大学信息网络工程研究中心路由问题：路径选择如何把这封信发往旧金山？北京上海东京旧金山可选路径北京旧金山北京东京旧金山北京上海东京旧金山香港旧金山5清华大学信息网络工程研究中心谁来完成路径选择工作上海邮局东京邮局旧金山香港？旧金山由邮局组成的邮政系统完成路径选择的全过程由每个邮局进行具体的存储转发工作东京？6清华大学信息网络工程研究中心路径选择依据根据信宿地址确定下一个站点是谁路径选择方法查看邮局各自去往信宿的路由表如何进行路径选择去往旧金山7清华大学信息网络工程研究中心网络的路径选择方式直接寻径（源与宿在相同网络）在物理网络内部确定主机—主机的数据传输路径间接寻径（源与宿在不同网络）确定到达目的网络的数据传输路径在目的网络中用直接寻径方法到达信宿直接寻径与间接寻径的关系8清华大学信息网络工程研究中心间接寻径举例BEthernet141.20.11.0141.20.11.25141.20.11.33AC141.20.28.55Ethernet141.20.28.0Ethernet141.20.17.0141.20.17.21141.20.17.26141.20.28.67DATAIPHdrEthHdr宿MAC地址=141.20.28.67的Eth地址 宿IP地址=141.20.28.67下站IP地址141.20.11.33目的网络:141.20.28/24下站地址:141.20.17.26端口：141.20.17.21的MAC地址下站IP地址141.20.28.67D数据从主机A发送到主机DDATA

宿IP地址=141.20.28.67宿MAC地址=141.20.11.33的Eth地址EthHdrIPHdr10清华大学信息网络工程研究中心间接寻径：第三层数据交换被寻径的数据单元是数据报（datagram）通过信宿的IP地址寻径（查看路由表）通过路由表的相互关联获得到达信宿的全部信息输入 输出 B的第三层IPHdrDATAIPHdrDATAdatagramdatagram查看路由表，下站IP地址是141.20.17.2612清华大学信息网络工程研究中心路由技术的概念为IP数据报在网间寻找传输路径采用间接寻径方式将数据报逐站传递通过网间互连设备—路由器实现路由功能信宿地址去往信宿的路径路由表14清华大学信息网络工程研究中心2）路由技术的地位和作用实现异种网络互连的关键技术完成OSI参考模型的第三层功能体现TCP/IP协议IP层的设计思想屏蔽下层与物理网络相关的技术细节用统一的IP地址分层次寻址和寻径根据网络地址实现到达目的网络的路径选择根据主机地址在目的网络中选择到达信宿的路径15清华大学信息网络工程研究中心3）有关路由的一些名词概念网关（Gateway）驿站（Hop）自治系统（AutonomousSystem）路由表（RoutingTable）16清华大学信息网络工程研究中心网关概念的早期解释BEthernet141.20.11.0141.20.11.25141.20.11.33AC141.20.28.55Ethernet141.20.28.0Ethernet141.20.17.0141.20.17.21141.20.17.26141.20.28.67D路由器网络28与网络17的互连系统网络11与网络17的互连系统17清华大学信息网络工程研究中心网关概念的当前解释数据链路层DataLink网络层Network传输层Transport应用层Application网关（Gateway）路由器（Router）18清华大学信息网络工程研究中心早期邮政系统的驿站（Hop）甲地乙地发信人收信人驿站11驿站12驿站21驿站22信源信宿20清华大学信息网络工程研究中心计算机网络的驿站（Hop）甲地乙地发信人收信人驿站11驿站12驿站21驿站22信源信宿IPdatagramIP数据报传输路径中的路由器21清华大学信息网络工程研究中心路由表每个站点/主机用某个特定的路由协议建立和维护的、向网络发送IP包的路由信息。路由表包含的主要信息DestinationInterfaceGateway目的地址网关/主机地址网卡/串口某台主机地址某个子网地址某个网络地址Default（默认路由）23清华大学信息网络工程研究中心128.1.5.1路由表举例128.1.4.0128.1.5.0128.1.5.2128.1.5.5A主机A的路由表24清华大学信息网络工程研究中心路径判断选择最佳传输路径什么是最佳？定义一种度量标准（Metric）如何得到最佳？根据度量标准确定一种路由算法根据算法收集路由信息，作出判断将判断结果填入路由表路由器之间交换网络动态的路由信息26清华大学信息网络工程研究中心数据交换将IP包在网间传送在IP层查看去往信宿的路由表，确定下一站点找不到下站的路由，丢弃数据报找到下站的路由，确定下站的物理地址在数据链路层数据封装，送网下站数据交换特点数据报的目的IP地址始终保持不变帧的目的物理地址根据路径判定结果逐站改变27清华大学信息网络工程研究中心5）路由的实现确定路由算法设计目标选择类型定义最佳路径的度量准则实现路由协议路由传输协议（RoutedProtocol）网间经路由被传输的协议：IP，OSI，Netware路由选择协议（RoutingProtocol）实现路由选择算法的协议：RIP，OSPF，BGP28清华大学信息网络工程研究中心选择最佳路由的度量参数路径长度由网络管理员定义每条网络链路的代价(cost)，从源到宿的代价总和为路径长度以路径中的站点（hop）为单位，从源到宿的站点数之和为路径长度可靠性 链路数据传输的可靠性（误码率）延迟 数据包从源到宿需要花费的传输时间带宽 链路的最大传输能力以及网络流量负载 网络资源（例如路由器的CPU）的使用率通信代价 占用通信线路的费用30清华大学信息网络工程研究中心路由选择算法1.默认路由2.静态路由3.动态路由之一：距离向量法4.动态路由之二：链路状态法31清华大学信息网络工程研究中心1.默认路由（DefaultRoute）什么是默认路由？对那些在路由表中未包含其路由选择信息的信宿（网络/主机）设定的缺省路径在路由表中信宿地址取值0.0.0.0(Default)默认路由的作用对所有自治系统以外的信宿都采用默认路由简化路由计算，提高寻径效率，缩短表长32清华大学信息网络工程研究中心默认路由举例网络A网络DRdb0c0f0e0DefaultRde0DefaultRdf0DefaultRa b0DefaultRa c0RaRcRbRfRe33清华大学信息网络工程研究中心2.静态路由静态路由的概念静态路由工作原理路由配置举例故障举例（网络拓扑结构变化）用人工修改配置排除故障34清华大学信息网络工程研究中心静态路由的概念由网络管理员设置路由表简单、有效，适于结构简单的网络不适于拓扑结构和传输流量经常改变的复杂网络35清华大学信息网络工程研究中心静态路由举例网络A网络C网络BRa路由表网络B Rb a2网络C Rc a3Rb路由表网络A Ra b3网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1RaRbRc36清华大学信息网络工程研究中心链路发生故障网络A网络C网络BRb路由表网络A Ra b3网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1??Ra路由表网络B Rb a2网络C Rc a3RaRbRc37清华大学信息网络工程研究中心解决办法：人工修改网络A网络C网络BRb路由表网络A Rc b2网络C Rc b2Rc路由表网络B Rb c2网络A Ra c3a1a3a2c3c2c1b2b3b1！！不适于网络变化！Ra路由表网络B Rc a3网络C Rc a3RaRbRc38清华大学信息网络工程研究中心3. 距离向量算法Distance-Vector1)D-V算法的基本概念2)D-V算法的动态特性3)D-V算法的收敛性问题及其解决办法4)D-V算法小结39清华大学信息网络工程研究中心A路由表1) 距离向量算法的基本概念周期性地相互传递信息每个路由器向与它相邻的站点发送一个包含它到所有其他路由器的距离的向量（最短路径或最小代价）维护各自的路由表路由器根据邻居发送的距离—向量的动态信息启动算法，更新路由表DCAB路由表C路由表B40清华大学信息网络工程研究中心距离向量法的计算举例ADECB718221计算从E经相邻站点A、B和D到达信宿A、B、C和D的最小代价D(destination,neighbor)最小代价D(des,nei)E的路由表得从E到达信宿的最佳路径（最小代价）路由表41清华大学信息网络工程研究中心2) D-V算法的动态特性建立路由表的初始过程发现新的网络发现链路断开42清华大学信息网络工程研究中心D-V建立路由表的初始过程ACB10.0.0.040.0.0.030.0.0.020.0.0.0a0 a1 b0 b1 c0 c143清华大学信息网络工程研究中心D-V网络发现过程剖析 1 1 ACB到达信宿40.0.0.0的路由变化如果网络中的最长路径为N，则算法经过N次迭代计算后收敛。即第N步之后，网上的所有路由器都获得到达信宿40.0.0.0的路由信息。40.0.0.0down40.0.0.0up44清华大学信息网络工程研究中心3) 距离向量法的收敛性问题问题逐站传递更新信息，算法的收敛速度慢有可能出现各站路由信息不一致有可能传播错误的路由信息后果在站点间构成更新路由的路径环（RoutingLoops）计数至无穷大（CounttoInfinity）45清华大学信息网络工程研究中心40.0.0.0

传播错误的路由信息 1 1 ACB到达信宿40.0.0.0的路由变化C与B之间的对话：我得不到信宿40.0.0.0的任何路由信息，你能告诉我如何到达信宿吗？我可以到达信宿，距离为1。（传播了一条过时的错误信息）既然如此，我选择经过你到达信宿的路径，距离为2。40.0.0.0down46清华大学信息网络工程研究中心 1 1 ACB到达信宿40.0.0.0的路由变化路径环（RoutingLoop）问题这条错误的路由信息在C与B之间不断复制和修改，并在网络中传播（殃及A），形成路径传播的环路。40.0.0.0down47清华大学信息网络工程研究中心 1 1 ACB到达信宿40.0.0.0的路由变化严重后果：计数至无穷大40.0.0.0down48清华大学信息网络工程研究中心距离向量法收敛性问题的解决办法定义路径代价的最大值（Maximum）提高收敛速度水平分割（SplitHorizon）毒性逆转（PoisonReverse）保持计时（Hold-DownTimers）触发更新（TriggeredUpdates）加速方法的综合应用举例49清华大学信息网络工程研究中心 1 1 ACB到达信宿40.0.0.0的路由变化（定义Hop最大值为16）定义距离的最大值收敛！40.0.0.0down50清华大学信息网络工程研究中心网关-网关协议GGPGGP概述GGP的路由发现、传播和刷新过程GGP的故障发生后的路由变化GGP协议报文51清华大学信息网络工程研究中心网关-网关协议GGP概述Internet早期的路由广播协议用于核心网关路由交换对于用路由广播协议实现路由广播算法具有示范意义特点以站点数（Hop）为距离实现D-V算法ARPANETInternet最初主干核心网关本地网点本地网点本地网点52清华大学信息网络工程研究中心发现网络ADCBNET1NET4NET3NET2(0,3)(0,4)(0,3)(0,4)(0,1)(0,2)（Hop,NetID)53清华大学信息网络工程研究中心ADCBNET1NET4NET3NET2(0,4)/D向邻居传播发现信息(0,3)/D(0,3)/B(0,4)/C54清华大学信息网络工程研究中心ADCBNET1NET4NET3NET2(0,3)(1,4)根据邻居传播的信息更新路由(0,4)(1,3)(0,1)(1,3)(0,2)(1,4)55清华大学信息网络工程研究中心ADCBNET1NET4NET3NET2(0,1)(1,3)(0,2)(1,4)传播更新信息(1,4)/B(1,3)/C56清华大学信息网络工程研究中心ADCBNET1NET4NET3NET2(0,1)(1,3)(2,4)(0,2)(1,4)(2,3)更新路由57清华大学信息网络工程研究中心ADCBNET1NET4NET3NET2(0,1)(,3)(,4)(0,2)(1,4)(2,3)B发生故障58清华大学信息网络工程研究中心GGP协议报文封装封装在IP数据报中，用IP协议传输类型路由刷新确认（收到刷新报文的回送信息）回应请求/应答（主动测试）接口状态59清华大学信息网络工程研究中心4) 距离向量算法小结采用最短路径准则，计算D信宿(距离，下站)；每个站点只知道自己和邻居的局部信息，在自己的刷新周期到来时，根据邻居的路由变化重新启动算法；算法的收敛速度慢（特别是对网络崩溃）造成全网信息的不一致，导致产生路径环，使计数至无穷大；当路径环产生时，定义距离的最大