第十章路由选择协议

第十章路由选择协议内容摘要：

、主机和路由器的集合。 自治系统又可划分为若干个不同的区域。 在区域的所有网络必须是互相连接的。  在一个区域内的路由器使用洪泛法传送路由选择信息。  区域边界路由器 将有关本区域的信息概括起来发送给其他区域。  在自治系统中有一个特殊区域叫做 主干 ，在自治系统中的所有区域必须连接到主干上。  如果由于某些问题，在主干和区域之间的连通性被破坏了，则管理员必须创建路由器间的 虚链路 ，以保持作为一级区域的主干的各种功能的连续性。 Area 30 自治系统中的区域 区域边界路由器 Autonomous system Area 1 区域边界路由器 Area 2 Area 0 (主干 ) 主干路由器 主干路由器 到其他的 AS AS 边界路由器 31 链路状态路由选择 在链路状态路由选择协议中，每一个路由器与在该区域内的每一个路由器共享其邻站的信息。 理解关键： 1. 共享关于邻站的信息。 每一个路由器向本区域内的每一个其他路由器发送其邻站的状态。 2. 与每一个其他路由器共享。 每一个路由器向本区域内的每一个其他路由器发送其邻站的状态。 发送的方法是洪泛法（ flooding）。 最终，每一个路由器（没有例外）都会收到同样信息的一个副本。 3. 只要有了变化就共享。 仅当有了变化时每一个路由器才共享其邻站的信息。 这使得互联网上的通信量比距离向量路由选择所需的通信量要小。 32 链路的类型 链路的类型 残桩链路 过渡链路 点对点链路 虚拟链路 两个路由器直接连接 连接有若干个路由器的网络 只连接到一个路由器的网络 当路由器之间的链路断开时创建的 33 （一）点对点链路 点对点链路 ，而中间没有任何其他的主机或路由器。 34 （二）过渡链路 Ether A B C D E 过渡链路 A B C D E 不实际的表示 A B C D E 实际的表示 指定路由器  一方面，现在每一个路由器只有一个邻站，即指定路由器（网络），另一方面，这个指定路由器（即网络）有 5个邻站。  是一种连接有若干个路由器的网络。 数据可以从任何一个路由器进入网络，并从任何一个路由器离开网络。 35 （三）残桩链路  残桩链路是只连接到一个路由器的网络。  数据分组通过这个单一路由器进入网络，而离开网络也是通过这个路由器。 Ether A 残桩链路 A 表示法 指定路由器 36 链路状态数据库  链路状态数据库是一个区域内的互联网拓扑的表格表示。  它给出了每一个路由器与其邻站的包括度量在内的关系。  在同一个区域内的每一个路由器具有同样的链路状态数据库。 B A/6 C/2 E/1 A B/6 D/2 C B/2 F/2 G/5 D A/2 E/2 E B/1 D/2 F/4 F C/2 E/4 G/1 G C/5 F/1 A D B C G E F 6 2 2 2 1 4 2 5 1 Network 37 Dijkstra 算法 （路由器）开始，本地结点即树的根。 0指派给这个结点，并使它成为第一个永久结点。 ，并使它成为试验的。 ： ① 寻找具有最小累计代价的结点，并使它成为永久的。 ② 若一个结点从多于一个方向可达，选择具有最短累计代价的方向。 3至 5，直到每一个结点成为永久的。 38 一个实例 A B C D E F N3 N5 Ether Ether Ether N2 N1 N4 T1 line T3 line Token ring FDDI 上图是一个具有 7个网络和 6个路由器的小互联网。 39 上图的图形表示 N5 N2 N3 N1 N4 A B C D E F 2 3 8 8 5 7 4 4 2 5 2 9 5 40 最短路径计算 N5 N2 N3 N1 N4 A B C D E F Problem: Calculate the shortest paths from A 41 Step 1 A Step: 1. Start with A 0 Node A is the root of the shortest paths tree. 42 Step 2 N1 A D Step: 2. Make A permanent, add its neighbors 0 5 8 Now we have two tentative nodes, N1 and D. 43 N1 Step 3 B C D Step: 3. Make N1 permanent, add its neighbors A 0 5 8 5 5 44 Step 4 N1 B C D Step: 4. Make C permanent, add its neighbors A 0 5 8 5 5 N2 7 45 Step 5 N1 B D E Step: 5. Make B permanent, a。