第五章路由算法.ppt

第五章 路由算法 5.1 路由算法概述 网络层的任务 建立、维持、中止网络的连接 网络层的核心：路由算法 路由算法的功能：指引分组通过通信子网到达目的节点 为源节点和目的节点对选择传输路径； 将分组正确地送到目的节点。 5.1 路由算法概述 5.1 路由算法概述 路由选择的优劣将直接影响网络的性能 5.1.1 路由选择算法的分类 决策地点 集中式 分布式 决策时间 分组（数据报） 会话（虚电路） 性能评价准则 吞吐量 时延 链路数 设施代价 路由选择所基于的信息源 本地 相邻节点 路径上的节点 所有节点 路由选择对网络的适应性 静态 自适应 根据负载、拓扑结构的变化自适应地调整路由 5.1.2 对路由选择算法的要求 正确性 到达目的地；交付给目的地，不再转发 计算简单 运算量小；路由计算所需信息的获取过程占用带宽少 自适应性 业务量；拓扑 稳定性 震荡少 公平性——用户 最优性 基于某项性能准则 上述要求之间存在矛盾 5.1.3 路由算法的实现 路由表 路由表：存储了分组的传送路径(下一跳) 5.1.3 路由算法的实现 路由表 路由环路问题 路由表中的附加信息 5.1.4 路由算法与流量控制的关系 “流量控制”根据时延调整负载进入网络的吞吐量； 路由算法影响分组的传输时延； 5.2 常用路由算法 网内路由 网际路由 5.2.1 广域网中的路由算法 广播 接收节点常常是全网所有成员 传播公共信息、拓扑变化信息（节点移动，节电开关、链路故障） 路由算法 洪泛 生成树 单播 Delivery: Broadcast Routing Delivery: Broadcast Routing Delivery: Broadcast Routing 5.2.1 广域网中的路由算法 洪泛算法的问题 分组的传输次数多 附加规则 不重复转发，用节点标识符和序号来保证 不回传 5.2.1 广域网中的路由算法 最短路由 最佳路由 最短路由：一对节点之间的路径最优； 限制了网络的通过量； 为避免震荡，适应业务变化的能力受限。 最佳路由基于平均指标的最优化，在全网有哪些信誉好的足球投注网站可能的路径，可将流量分配在多条路径上。 5.2.2 互连网中的路由算法 网关 WAN与WAN之间 协议转换、路由 网桥 LAN与LAN之间 Translate a packet from one format into another, e.g., ethernet to optical (FDDI) MAC层协议 路由器 connect and route between two networks 网络层 网络规模扩大与路由器内存有限之间的矛盾 分级 5.2.2 自组织网络中的路由算法 自组织网络？ 路由算法分类 5.3 最短路由算法 图论基本概念 图：定义成空间中一些节点（顶点）和连接这些节点的链路（边）的集合。 无向图：链路无方向 有向图：链路有方向 关联：如果节点是链路e的一个端点，则称边e和顶点节点相关联 方向性行走：指一个节点序列 与该序列相关联的链路 为G中的链路 方向性路径（path）：无重复节点的方向性行走 5.3 最短路由算法 图论基本概念（2） 方向性环：源节点与目的节点相同的方向性路径 强连通方向图：图中的每一对节点i,j都有一条方向性路径 连通方向图：方向图对应的无方向图是连通的。 5.3 最短路由算法 最短路径： 给每条链路 指定一个实数作为其长度 一条方向性路径 的长度为 最短路径问题就是寻找从i到m的最小长度方向性路径 链路长度可以是成本、时延、可靠性。。。。 5.3 最短路由算法 集中式最短路径算法 Bellman-Ford算法 点对多点 Dijkstra算法 点对多点 Floyd-Warshall算法。 多点对多点 Bellman-Ford算法 寻找网络中一个节点到其它所有节点的最短路由。 定义：最短（ 　 ）行走（Walk）是指在下列约束条件下从给定节点i到目的节点1的最短Walk。 ① 该行走（Walk）中最多包括h条链路，即Walk中包含的链路数至多为h条。 ② 该行走（Walk）仅经过目的节点1一次。 最短行走Walk长度用 　表示。节点i经过ｈ条链路　到达目的节点1的行走长度 对所有的h，令 　　。 B-F算法的核心思想是通过下面的公式进行迭代，即 Bellman-Ford算法 第一步：初始化。即对所有i （ｉ≠１ ）令 。 第二步：对所