计算机网络12网络层路由协议.pptVIP

林楠;? 可路由协议 一旦选择一条路径后，用来在路由器之间传送用户的数据报。 举例：IP;路由选择 路由算法 路由协议 RIP、OSPF、BGP 单播与组播路由选择 ;路由选择要求一台主机或路由器具有一个路由表(routing table)。 路由表中的每条记录都包含一目的IP地址和下一跳结点地址。 任何一个路由器中都没有到达目的地址的完整路由信息。 当一台主机要发送一个数据报，或者一台路由器接收到一个数据报转发时，就会查看路由表，找出与目的地址匹配的记录，然后按照记录中下一跳地址将数据报转发出去。 为了提高查询路由表的效率，使得路由表的大小易于管理，并解决安全问题，目前有几种路由选择技术： 1）下一跳路由选择 2）特定网络路由选择 3）特定主机路由选择 4）默认路由选择;路由选择 路由算法 路由协议 RIP、OSPF、BGP 单播与组播路由选择 ;连接成本 c (x, x’) 例如：c (w, z) = 5 （成本一般为1，可以根据不同网络带宽与拥塞情况而改变）; 跳数: 数据报到达目的地，所必须通过的路由器的总数。 Hop count越少，该路由线路就越好。 带宽: 连接的速度。100Mbps 的速度优于64Kbps的专线。 延迟: 把数据报从发送主机传送到接收主机所需要的时间。 负载: 路由器或网络上数据流通的数量。 可靠性: 每条网络连接上的差错率。 等等…… ;常用路由算法： 最短路径算法 Dijkstra 静态的方法（给定网络的拓扑结构， 路由变化很少） 扩散法 flooding 静态的方法 距离向量算法 D-V 动态的方法（网络拓扑结构有变化， 路由变化较多） 链路状态算法 L-S 动态的方法; 最短路径算法 Dijkstra（1959）：静态的方法 以边的权值为距离来度量最短路径，即权值和最小的路径。 经过边数最少的路径不一定是最短路径。; 最短路径算法采用的数据结构 集合S：尚未找到最短路径的结点集合； 数组R：记录路径，R[i] 为指定 源点 到 结点i 的路径上 结点i 的前一个结点； 数组D：D[i] 为从指定 源点 到 结点i 的最短距离。 算法初始化 初始化集合S：为除源点外的所有结点； 初始化数组R：如果从源点到结点v存在连接，则R(v)=源点，否则为0； 初始化数组D：如果从源点到结点v存在连接，则D(v)=该边的权值， 否则为无穷大。 ;S ;路由算法; 扩散法 flooding：不计算路径，有路就走。 例如：5到1/2；2到3/6；3到6/4；6到3/7；7到4。 存在问题：数据报重复到达某一结点。如3/6数据报循环往复发送。 解决方法： 1）在数据报头设一计数器，每经过一个结点自动加1，达到规定值时， 丢弃数据报； 2）在每个结点上建立一个登记表，则数据报再次经过时丢弃。 缺点： 重复数据报多，浪费带宽。 优点： 可靠性高，路径最短， 常用与军事网络。 ;路由算法;距离向量法（D-V Distance Vector Routing ）： 分散: 每台路由器只了解到达邻近路由器的链路成本，通过迭代计算 与相邻路由器交换信息。 动态、分布式算法、在RIP协议中使用，应用于较小的系统。 实现算法三步骤：1）测量、2）更新邻结点距离向量、3）计算。 工作原理： 每个路由器用两个向量 Di Si 来表示该点到网上所有结点的路径 距离及其下一跳结点。 （如果网络中有n个路由器，则向量 Di Si 有n个分量； Di 表示到第i个结点的最短路径， Si 表示按此最短路径到达第i个结点的下一跳。 一个数据来了，根据Di 找最短路径，根据Si 找下一个跳结点。） 相邻路由器之间交换路径信息( 即交换向量 Di )； 各结点根据路径信息更新自己的路由表。;以 J 结点为例子;路由算法;链路状态算法 “link state” 动态算法；在OSPF协议中使用，应用于较大系统。 全局: 每台路由器都具有整个网络的拓扑图，具有所有链路成本信息。