Chapter 11 Unicast Routing Protocols

Chapter 11 Unicast Routing Protocols
TCP/IP Protocol Suite Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

OBJECTIVES: To introduce the idea of autonomous systems (ASs) that divide the Internet into smaller administrative regions. To discuss the idea of distance vector routing and the RIP that is used to implement the idea. To discuss the idea of link state routing as the second intra-AS routing method and OSPF that is used to implement the idea. To discuss the idea of path vector routing as the dominant inter-AS routing method and BGP that is used to implement the idea. TCP/IP Protocol Suite

Chapter Outline 11.1 Introduction 11.2 Intra- and Inter-Domain Routing
11.3 Distance Vector Routing 11.4 RIP 11.5 Link State Routing 11.6 OSPF 11.7 Path Vector Routing 11.8 BGP TCP/IP Protocol Suite

11-1 INTRODUCTION An internet is a combination of networks connected by routers. When a datagram goes from a source to a destination, it will probably pass through many routers until it reaches the router attached to the destination network. TCP/IP Protocol Suite

Topics Discussed in the Section
Cost or Metric Static versus Dynamic Routing Table Routing Protocol TCP/IP Protocol Suite

代价或基准(cost or metric) 选路基准带宽时延。。。 TCP/IP Protocol Suite

静态路由表与动态路由表静态路由表人工配置动态路由表系统自动更新(思考：如何更新？) TCP/IP Protocol Suite

路由选择协议针对动态路由表动态路由表更新路由查询分内部协议与外部协议 TCP/IP Protocol Suite

11-2 INTER- AND INTRA-DOMAIN ROUTING
Today, an internet can be so large that one routing protocol cannot handle the task of updating the routing tables of all routers. For this reason, an internet is divided into autonomous systems. TCP/IP Protocol Suite

Autonomous System (AS)
An AS is a group of networks and routers under the authority of a single administration. Routing inside an autonomous system is called intra-domain routing. Routing between autonomous systems is called inter-domain routing. TCP/IP Protocol Suite

Figure 11.1 Autonomous systems
TCP/IP Protocol Suite

主要路由协议域内路由协议 RIP:距离向量 OSPF:链路状态域间路由协议 BGP:路径向量 TCP/IP Protocol Suite

Figure 11.2 Popular routing protocols

11.3 Distance Vector routing
网络拓扑：由通信链路(或网络)将多个路由器互连的图路由算法：已知节点间的距离，使用Bellman-Ford(或Ford-Fulkerson)算法求图中任意两个节点之间的最短路径 TCP/IP Protocol Suite

Bellman-Ford Algorithm Distance Vector Routing Algorithm Count to Infinity TCP/IP Protocol Suite

Bellman-Ford算法示例求图11.3任意两个节点之间的最短距离 TCP/IP Protocol Suite

Figure 11.3 A graph for Bellman-Ford algorithm

Bellman-Ford算法要点节点i的所有邻居节点(i的1-hop邻居节点)都知道(也可能不知道)到节点j的最短距离
求节点i和节点j间的最短距离：节点i至每个邻居节点间的距离分别加上该邻居节点至节点j的最短距离，然后再从得数中选择最小的一个 TCP/IP Protocol Suite

Figure 11.4 The fact behind Bellman-Ford algorithm

利用Bellman-Ford算法创建距离向量
节点至其自身的距离被初始化为0，节点至所有其他节点的距离被初始化∞ 已知相邻节点之间的距离(即节点知道其1-hop邻居节点间的距离) 利用Bellman-Ford算法求一个节点至网络拓扑中任意节点间的距离(包括自身) TCP/IP Protocol Suite

带更新机制的距离向量路由算法(1) 路由器的距离向量
路由信息：目的网络、至目的网络的距离(或代价)、下一跳路由器距离：一个路由器到某个网络的距离(网络数)；至1-hop网络的距离为1 两个直接相邻的路由器间的距离为1(经过一个网络) 初始化阶段所有路由器的距离向量为至1-hop网络(与路由器直接相邻的网络)的距离(1)，然后将自己的距离向量(R)发给1-hop路由器 TCP/IP Protocol Suite

带更新机制的距离向量路由算法(2) 路由器的距离向量的更新思路
当路由器从其1-hop直接相邻(通过一个网络)的路由器接收到距离向量(R)后，就要异步地(即分成式地)更新自己的路由表(距离向量，原表为T)；并将更新后距离向量表(自己为T，对其邻居节点则为R)发送给所有1-hop直接相邻的路由器 TCP/IP Protocol Suite

带更新机制的距离向量路由算法(3) 路由器的距离向量的更新方法：当路由器从其1-hop直接相邻(通过一个网络)的路由器X接收到距离向量(R)后，先按目的网络地址D搜索自己的路由表(T) 1.若找到相应表项，即原路由表有至目的网络D的表项：如果R的代价加1后小于T中的代价，则更新表项如果R与T的next值相同，但R的代价大于T的代价，也不能忽略这个数值！有可能原路由不存在了！ 2.若未找到相应表项，即原路由表没有至目的网络D的表项：插入相应表项，并更新表项cost与next值；排序路由表 TCP/IP Protocol Suite

Example 11.1 Figure 11.5 shows the initial routing table for an AS. Note that the figure does not mean that all routing tables have been created at the same time; each router creates its own routing table when it is booted. TCP/IP Protocol Suite

Figure Example 11.1 TCP/IP Protocol Suite

Example 11.2 Now assume router A sends four records to its neighbors, routers B, D, and C. Figure 11.6 shows the changes in B’s routing table when it receives these records. We leave the changes in the routing tables of other neighbors as exercise. TCP/IP Protocol Suite

Example 11.3 Figure 11.7 shows the final routing tables for routers in Figure 11.5. TCP/IP Protocol Suite

计数到无穷大(count to infinity)
距离向量路由算法存在的问题好消息(代价下降)传播的非常快坏消息(代价上升)可能传播的非常慢(count to infinity) TCP/IP Protocol Suite

计数到无穷大示例二节点循环：图11.8 TCP/IP Protocol Suite

Figure 11.8 Two-node instability

定义无穷大将其定义为一个较小的数值，如16 TCP/IP Protocol Suite

分割范围和毒性逆转分割范围(split horizons) 毒性逆转(poison reverse)
如果节点B根据其路由表认为到达X的最佳路由要经过A，则它就再将其距离向量(至X)发送给A 毒性逆转(poison reverse) 虽然节点B知道其到达X的最佳路由要经过A，但它仍将其距离向量发给A，但到X的距离标为无穷大(16) TCP/IP Protocol Suite

三节点的不稳定性分割范围和毒性逆转仍不解决的三节点不稳定性(图11.9) TCP/IP Protocol Suite

Figure 11.9 Three-node instability

11-4 RIP(1) The Routing Information Protocol (RIP) is an intra-domain (interior) routing protocol used inside an autonomous system. It is a very simple protocol based on distance vector routing. RIP implements distance vector routing directly with some considerations. TCP/IP Protocol Suite

RIP(2) 节点：路由器与网络路由表的第一列为网络地址，终点是一个网络距离为到达终点所需通过的网络(链路)数无穷大为16
“下一个节点”为到达终点而要发往的路由器地址 TCP/IP Protocol Suite

Figure 11.10 Example of a domain using RIP

RIP Message Format Request and Response Timers in RIP RIP Version 2 Encapsulation TCP/IP Protocol Suite

RIP的报文格式命令版本:1或2 系列:TCP/IP值为2 网络地址距离报文类型：请求(1)或响应(2)
此字段为14个字节，IPv4使用4个字节，其余部分全部填入0 距离发出通告报文的路由器至目的网络的跳数 TCP/IP Protocol Suite

Figure 11.11 RIP message format

请求和响应—请求当路由刚接入到网络上或路由器有一些表项超时可以询问某些特定的表项(特定邻居)或者所有表项(所有邻居)

Figure 11.12 Request messages

请求和响应—响应针询问的响应针对非询问的响应应答请求时发出。定期发送。如每隔30s或当路由表中有变化时

Example 11.4 Figure shows the update message sent from router R1 to router R2 in Figure The message is sent out of interface The message is prepared with the combination of split horizon and poison reverse strategy in mind. Router R1 has obtained information about networks , , and from router R2. When R1 sends an update message to R2, it replaces the actual value of the hop counts for these three networks with 16 (infinity) to prevent any confusion for R2. The figure also shows the table extracted from the message. Router R2 uses the source address of the IP datagram carrying the RIP message from R1 ( ) as the next hop address. Router R2 also increments each hop count by 1 because the values in the message are relative to R1, not R2. TCP/IP Protocol Suite

Figure 11.13 Solution to Example 11.4

RIP的计时器定期计时器截止期计时器无用信息收集计时器控制报文的发送,25-35s
管理路由的有效性。路由表项180s未收更新报文(通常为30s)，则被视为截止，距离被置为16(即目的地不可达) 无用信息收集计时器对距离为16的路由表项，再进行计时(无用信息)，120s后清除 TCP/IP Protocol Suite

Figure RIP timers TCP/IP Protocol Suite

Example 11.5 A routing table has 20 entries. It does not receive information about five routes for 200 s. How many timers are running at this time? Solution The 21 timers are listed below: Periodic timer: 1 Expiration timer: 20 − 5 = 15 Garbage collection timer: 5 TCP/IP Protocol Suite

RIP2(1) 只适用于TCP/IP协议，将RIP1字段中为0的字段定义为新的字段报文格式(图11.15) 新字段路由标记：自治系统号
子网掩码：支持无分类编址下一跳地址：定义分组必须发往的路由器 TCP/IP Protocol Suite

Figure 11.15 RIP version 2 format

RIP2(2) 无分类地址鉴别 RIP1只能用于分类编址 RIP2可用于无分类编址
当系列字段值为0xFFFF时，路由标记字段值为鉴别类型，报文的第一个表项(第三个字段)为鉴别信息(图11.16) TCP/IP Protocol Suite

Figure 11.16 Authentication

RIP2(3) 组播封装 RIP1采用广播方式将RIP报文发送给邻居节点(路由器与主机) RIP2采用组播方式将RIP报文发送给邻居路由器
RIP报文被封装在UDP数据报中周知端口：520 TCP/IP Protocol Suite

RIP uses the services of UDP on well-known port 520.
Note RIP uses the services of UDP on well-known port 520. TCP/IP Protocol Suite

11-5 LINK STATE ROUTING Link state routing has a different philosophy from that of distance vector routing. In link state routing, if each node in the domain has the entire topology of the domain—the list of nodes and links, how they are connected including the type, cost (metric), and the condition of the links (up or down)—the node can use the Dijkstra algorithm to build a routing table. TCP/IP Protocol Suite

Figure 11.17 Concept of Link state routing

Building Routing tables TCP/IP Protocol Suite

链路状态路由思路(1) 每个节点利用相同的网络拓扑创建自己的路由表网络拓扑是动态变化的，即拓扑必须更新
整个网络是基于每个节点的局部拓扑构建的 TCP/IP Protocol Suite

Figure 11.18 Link state knowledge

链路状态路由思路(2) 构建路由表每个节点创建链路状态分组(LSP)，即局部拓扑
采用可靠(带应答)洪泛(flooding)在网络中广播LSP 每个节点收到其他节点LSP构建网络拓扑，并使用Dijkstra算法求最优路径树(至所有其他节点的汇聚树，即最小生成树) 第个节点使用其最优路径树构建路由表 TCP/IP Protocol Suite

LSP要素节点标识 (邻居)链路列表序号：区别LSP 寿命:防止旧LSP长时间在域中逗留节点标识与链路列表反映了局部拓扑

LSP的产生当域的网络拓扑发生变化时：主要更新方法定期更新：计时器设置为60分钟或2小时。思考：为什么？

LSP洪泛见P255 TCP/IP Protocol Suite

形成最优路径树：Dijkstra算法表11.3和图11.19 TCP/IP Protocol Suite

Continued TCP/IP Protocol Suite

Figure 11.19 Forming shortest path three for router A in a graph

Figure Continued TCP/IP Protocol Suite

Example 11.6 To show that the shortest path tree for each node is different, we found the shortest path tree as seen by node C (Figure 11.20). We leave the detail as an exercise. TCP/IP Protocol Suite

依据最优路径树计算路由表表11.4 TCP/IP Protocol Suite

11-6 OSPF The Open Shortest Path First (OSPF) protocol is an intra-domain routing protocol based on link state routing. Its domain is also an autonomous system. TCP/IP Protocol Suite

Area Metric Types of Links Graphical Representation OSPF Packets Link State Update Packet Other Packets Encapsulation TCP/IP Protocol Suite

区域(area)(1) OSPF将一个AS划分为若干Area
必须有的区域：主干(backbone)区域，也称Area 0。所有其他区域均连接到主干区域路由器分类：完全在一个区域内的内部路由器连接多个区域的区域边界路由器主干路由器自治系统边界路由器 TCP/IP Protocol Suite

区域(area)(2) 路由种类区域内：Flooding 区域间：区域边界路由器将有关本区域的信息汇总起来发送到其他区域自治系统间
从源路由器到主干区域；穿越主干区域到达目的区域；到达目的路由器。自治系统间 TCP/IP Protocol Suite

Figure 11.21 Areas in an autonomous system

路由基准(metric) 带宽时延。。。 TCP/IP Protocol Suite

链路的类型链路：两个路由器之间的连接类型：点对点穿越残桩虚拟 TCP/IP Protocol Suite

Figure Types of links TCP/IP Protocol Suite

点对点链路点对点链路直接连接两个路由器，中间没有任何其他的主机或路由器；路由器只有一个one-hop邻居路由器(在链路的另一端)

Figure 11.23 Point-to-point link

穿越链路穿越链路是连接若干路由器的一个网络
数据可以从任何一个路由器进入网络，并从任何一个路由器离开网络，即每个路由器有多个one-hop邻居路由器，导致通告数过多通过为穿越链路(即一个网络)设定指定路由器，使通过穿越链路互连的路由器只有一个one-hop邻居路由器从路由器到指定路由器有代价，从指定路由器到另一个路由器无代价 TCP/IP Protocol Suite

Figure Transient link TCP/IP Protocol Suite

残桩链路残桩链路是仅连接了一个路由器的网络分组通过一个路由器进入网络，并通过同一个路由器离开该网络是穿越网络的特例
用一个节点表示路由器，并用指定路由器代表网络。从路由器到指定路由器是单向链路 TCP/IP Protocol Suite

Figure Stub link TCP/IP Protocol Suite

虚拟链路当两个路由器之间的链路断开时，用一条更长的多跳路径来创建一条虚拟链路 TCP/IP Protocol Suite

Figure 11.26 Example of an AS and its graphical representation in OSPF

AS的图形表示示例 P260，图11.26 在 OSPF中，网络也是用节点(指定路由器)来表示 TCP/IP Protocol Suite

OSPF分组类型问候数据库描述链路状态请求链路状态更新链路状态确认 TCP/IP Protocol Suite

Figure 11.27 Types of OSPF packet

OSPF分组公共首部(24字节) 版本：2 类型：1-5 报文长度：包括首部在内的总报文长度源路由器地址：发送OSPF分组的源地址
区域标识检验和鉴别类型：0表示无鉴别，1表示口令鉴别：64bits TCP/IP Protocol Suite

Figure 11.28 OSPF common header

链路状态更新分组 OSPF运行的核心路由器使用链路状态更新分组通告自己的LS

Figure 11.29 Link state update packet

LSA(链路状态通告)首部(20字节)(1) 链路状态寿命 E标志：1表示这个区域是残桩区域。残桩区域是只有一条路径连接到主干区域的一种区域
T标志：1表示这个路由器能处理多种类型的服务 TCP/IP Protocol Suite

LSA(链路状态通告)首部(2) 链路状态类型路由器链路网络链路汇总链路到网络汇总链路到AS边界路由器外部链路

LSA(链路状态通告)首部(3) 链路状态标识符类型1(路由器链路)：路由器IP地址类型2(网络链路)：指定路由器IP地址
类型4(汇总链路到AS边界路由器)：AS边界路由器的IP地址类型5(外部链路)：外部网络的IP地址 TCP/IP Protocol Suite

LSA(链路状态通告)首部(4) 发送通告的路由器链路状态序号链路状态检验和长度：LSA长度，包括LSA首部

Figure 11.30 LSA general header

路由器链路(router link)LSA(1)
连接真路由器的一条链路(图11.31) TCP/IP Protocol Suite

Figure Router link TCP/IP Protocol Suite

路由器链路(router link)LSA(2)
路由器链路LSA通告真路由器的所有链路，LSA格式见图11.3 TCP/IP Protocol Suite

Figure Router link LSA TCP/IP Protocol Suite

路由器链路(router link)LSA字段
链路标识链路数据：与链路类型有关(表达式11.5) 链路类型服务类型数、TOS 0基准、。。。 TCP/IP Protocol Suite

Example 11.7 Figure 11.7 shows the final routing tables for routers in Figure 11.5. Solution This router has three links: two of type 1 (point-to-point) and one of type 3 (stub network). Figure shows the router link LSA. TCP/IP Protocol Suite

网络链路(network link)LSA
网络链路定义的是连接网络的一条链路由指定路由器代表穿越网络来发布此类型LSA TCP/IP Protocol Suite

Figure Network link TCP/IP Protocol Suite

网络链路通告格式网络掩码连接的路由器 TCP/IP Protocol Suite

Figure 11.36 Network link advertisement format

Example 11.8 Give the network link LSA in Figure 11.37. Solution
The network for which the network link advertises has three routers attached. The LSA shows the mask and the router addresses. Figure shows the network link LSA. TCP/IP Protocol Suite

Example 11.9 In Figure 11.39, which router(s) sends out router link LSAs? Solution All routers advertise router link LSAs. a. R1 has two links, N1 and N2. b. R2 has one link, N1. c. R3 has two links, N2 and N3. TCP/IP Protocol Suite

Figure Examples 11.9 and 11.10 TCP/IP Protocol Suite

Example 11.10 In Figure 11.39, which router(s) sends out the network link LSAs? Solution All three networks must advertise network links: a. Advertisement for N1 is done by R1 because it is the only attached router and therefore the designated router. b. Advertisement for N2 can be done by either R1, R2, or R3, depending on which one is chosen as the designated router. c. Advertisement for N3 is done by R3 because it is the only attached router and therefore the designated router TCP/IP Protocol Suite

汇总链路到网络(summary link to network)LSA
区域边界路由器使用汇总链路到网络LSA来宣布在这个区域以外的其他网络的存在(将区域x的网络信息发到区域y中，目的让网络找到区域边界路由器) 一个通告只宣布一个网络。若网络超过一个，就必须对每一个网络发出单独的通告 TCP/IP Protocol Suite

Figure 11.40 Summary link to network

汇总链路到网络LSA格式图11.41 网络掩码。。。 TCP/IP Protocol Suite

Figure 11.41 Summary link to network LSA

汇总链路到AS边界路由器(summary link to AS boundary router)LSA

Figure 11.42 Summary link to AS boundary router

Figure 11.43 Summary link to AS boundary router LSA

外部链路(external link)LSA
AS边界路由器使用外部链路LSA宣布外部网络(一次一个) TCP/IP Protocol Suite

Figure External link TCP/IP Protocol Suite

Figure 11.45 External link LSA

问候报文链路状态路由选择第一步建立邻居关系，测试邻居节点的可达性 TCP/IP Protocol Suite

Figure Hello packet TCP/IP Protocol Suite

数据库描述报文用于新接入网络的路由器从邻居节点接收完整的链路状态 TCP/IP Protocol Suite

Figure 11.47 Database description packet

链路状态请求分组新接入的路由器在收到数据库描述报文后，使用链路状态请求分组来请求关于某些路由的更多信息

Figure 11.48 Link state request packet

链路状态确认 OSPF强制路由器对所收到的每一个链路状态更新分组进行确认 TCP/IP Protocol Suite

Figure 11.49 Link state acknowledgment packet

OSPF packets are encapsulated in IP datagrams.
Note OSPF packets are encapsulated in IP datagrams. TCP/IP Protocol Suite

OSPF分组的封装被封装为IP数据报，但带有确认机制(链路状态确认分组) TCP/IP Protocol Suite

11-7 PATH VECTOR ROUTING Distance vector and link state routing are both interior routing protocols. They can be used inside an autonomous system. Both of these routing protocols become intractable when the domain of operation becomes large. Distance vector routing is subject to instability if there is more than a few hops in the domain of operation. Link state routing needs a huge amount of resources to calculate routing tables. It also creates heavy traffic because of flooding. There is a need for a third routing protocol which we call path vector routing. TCP/IP Protocol Suite

Example 11.11 The difference between the distance vector routing and path vector routing can be compared to the difference between a national map and an international map. A national map can tell us the road to each city and the distance to be traveled if we choose a particular route; an international map can tell us which cities exist in each country and which countries should be passed before reaching that city. TCP/IP Protocol Suite

Reachability Routing Table TCP/IP Protocol Suite

可达性 AS边界路由器可到达该AS的内部网络 TCP/IP Protocol Suite

Figure Reachability TCP/IP Protocol Suite

路由表 AS边界路由器相互交换其内部可达网络列表 TCP/IP Protocol Suite

Figure 11.51 Stabilized table for three autonomous system

Figure 11.52 Routing tables after aggregation

11-8 BGP Border Gateway Protocol (BGP) is an interdomain routing protocol using path vector routing. It first appeared in 1989 and has gone through four versions. TCP/IP Protocol Suite

Types of Autonomous Systems Path Attributes BGP Sessions External and Internal BGP Types of Packets Packet Format Encapsulation TCP/IP Protocol Suite

AS类型残桩AS 多归属AS 转接AS 只有一个连接到达另一个AS。信源或信宿

路径属性周知属性(well-known attribute) 可选属性(optional attribute)
强制的，如ORIGIN,AS_PATH,NEXT_HOP 自选的可选属性(optional attribute) 传递的非传递的 TCP/IP Protocol Suite

BGP会话会话是建立在两个BGP路由器之间的一个连接会话仅用于交换路由选择信息 BGP使用TCP的服务

会话类型：外部BGP和内部BGP E-BGP会话用于两个不同的AS内的发言人节点之间互相交换信息
I-BGP用于一个AS内的两个路由器之间互相交换路由选择信息 TCP/IP Protocol Suite

Figure 11.53 Internal and external BGP sessions

BGP报文类型打开更新保活通知 TCP/IP Protocol Suite

Figure 11.54 Types of BGP messages

BGP分组首部标记长度类型 TCP/IP Protocol Suite

Figure 11.55 BGP packet header

打开报文打开与邻居节点的TCP连接 TCP/IP Protocol Suite

Figure Open message TCP/IP Protocol Suite

更新报文撤销以前通告过的路由(可为多个) 宣布一条新路由 TCP/IP Protocol Suite

Figure Update message TCP/IP Protocol Suite

BGP supports classless addressing and CIDR.
Note BGP supports classless addressing and CIDR. TCP/IP Protocol Suite

保活报文运行BGP协议的路由器(也称对等路由器)定期互相交换保活报文，维持连接 TCP/IP Protocol Suite

Figure 11.58 Keepalive message

通知报文当检测差错状态或路由器打算关闭连接时，发送通知报文 TCP/IP Protocol Suite

Figure 11.59 Notification message

BGP报文封装 BGP报文封装成TCP报文段使用周知端口179 TCP/IP Protocol Suite

BGP uses the services of TCP on port 179.
Note BGP uses the services of TCP on port 179. TCP/IP Protocol Suite

Chapter 11 Unicast Routing Protocols

Similar presentations

Presentation on theme: "Chapter 11 Unicast Routing Protocols"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

Chapter 11 Unicast Routing Protocols

Similar presentations

Presentation on theme: "Chapter 11 Unicast Routing Protocols"— Presentation transcript:

Similar presentations

About project

反馈