数据通讯与计算机网络讲义 22章.ppt

代价（cost） 距离向量算法 (Distance Vector Routing) 定义：c(x,v)：x至相邻节点v的代价 dx(y) : x至y的最小代价路径的总代价 则有 dx(y)：从x至y的最小代价估计 c(x,v)：x至相邻节点v的代价 节点x记录自本节点至所有其它节点y的距离向量估计 Dx = [ dx(y): y∈N ] 节点x接收来自相邻节点v的距离向量 Dv = [ dv(y): y∈N ] 节点x从相邻节点v接收到新的“距离向量”后，使用B-F公式修正自身的距离向量Dx = [ dx(y): y∈N ]： 距离向量算法示例1（同步运算）： 两级的层次结构: 局部区域, 骨干区域 内部路由器之间的“Link-state”广播仅在局部区域中 ； 每个内部路由器具有所在区域内的详细拓扑信息。 区域边界路由器“ 汇总”本区域中到各网络的路径代价，将此信息告知其它区域的“区域边界路由器 ”。 骨干路由器: 在骨干区域范围内运行OSPF路由协议(广播，运算)。 边疆路由器: 实现同其它自治系统的连接(网关)。 因特网的“inter-AS”路由协议: BGP 政策性原因 规模原因 性能原因 在边界路由器中的BGP协议实体的功能: 从相邻AS获取其它网络的可达性信息； 将上述可达性信息传递给本AS中的所有路由器； 基于可达性信息以及其它“选路策略”，确定至其它 AS中网络的“好”路径。 1. BGP的基本概念 BGP路由器基于半永久性TCP连接 (port 179)交换路由信息： BGP“会话”（sessions） 2. 路径属性 每个自治系统有唯一的“自治系统号”(ASN) 传递的报文中包含若干BGP属性。 两种重要的BGP属性: AS-PATH: BGP报文传递过程中经过的AS集合的列表，如: “ AS6, AS7，…”（可检测、防止路径循环）； NEXT-HOP: “为到达下一个AS，BGP网关转发报文的出口IP地址”（示例：1d根据到3a的“出口地址j”的最短路径，确定到子网x的路由表项“目的网络x, 出端口k ” ） 3. BGP报文 BGP报文封装在TCP报文段中。 BGP报文类型（四种）: OPEN: 在对等方之间建立TCP连接，并对发送方进行认证； UPDATE: 传送新的路径信息（或去除旧的路径信息) KEEPALIVE：在不传递UPDATE报文期间，保持已建立的连接，或对OPEN报文作确认。 NOTIFICATION: 报告前三种报文的差错。 Source-based tree approach In the source-based tree approach, each router needs to have one shortest path tree for each group. Multicasting routing Group-shared tree approach In the group-shared tree approach, only the core router, which has a shortest path tree for each group, is involved in multicasting. RIP updating algorithm （异步运算） 各router将本站的距离向量发送给邻站 某router接收到邻站j发来的RIP报文 对报文中的各个destk , (k=1,2,..N): destk在本站路由表中？ 将“destk,新costk+1,j”加入路由表 新costk+1旧costk？ 将“新costk+1,j”更新该表项 至目的站k的下一站是j？ 将“新costk+1”更新该表项 Y Y N N N Y 结束 定时器事件或本地状态变化 Link state routing 每个节点知道整个网络拓扑以及各链路代价 每个节点将自身邻域的链路状态信息向全网广播 所有节点具有相同的“图” 每个节点以自身为根，计算从根到各个其它节点的最小代价路径 （ Dijkstra 算法: 经过k次迭代，得到至k个节点的最小代价路径。） 作出该节点的路由表 链路状态法建立路由表的步骤（四步） 步骤1：生成“link state packet (LSP)” 含“node ID, neighbor, cost, seq. , live-time, … ” 周期性或发现网络状态发生变化时 步骤2：Flooding LSPs (各节点仅转发新版本的LSP)