中科大,计算机网络课件14.ppt

TCP/IP Protocol Suite,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,TCP/IP Protocol Suite,*,Chapter,14,Upon completion you will be able to:,Unicast,Routing Protocols:RIP,OSPF,and BGP,Distinguish between intra and,interdomain,routing,Understand distance vector routing and RIP,Understand link state routing and OSPF,Understand path vector routing and BGP,Objectives,1,TCP/IP Protocol Suite,单播路由协议,路由问题描述为：给定一组路由器和连接路由器的一组链路，寻找一条从源路由器到目的路由器的最佳路径。,最佳路径：从源路由器到目的路由器的代价最小的路径。,路由优化较多考虑的目标是,最小化分组延迟和最大化吞吐量，但这是一对矛盾。作为折衷，大多数网络最小化分组跳数。,路由表是由路由算法建立起来的一张表，通常包含了分组转发路径上下一跳地址的信息。,路由协议用于在路由器之间交换网络状态信息，以便动态地更新路由表。,2,TCP/IP Protocol Suite,14.1 INTRA-AND INTERDOMAIN ROUTING,Routing inside an autonomous system is referred to as,intradomain,routing.Routing between autonomous systems is referred to as,interdomain,routing.,3,TCP/IP Protocol Suite,Figure 14.1,Autonomous systems,4,TCP/IP Protocol Suite,Figure 14.2,Popular routing protocols,5,TCP/IP Protocol Suite,14.2 DISTANCE VECTOR ROUTING,In distance vector routing,the least cost route between any two nodes is the route with minimum distance.In this protocol each node maintains a vector(table)of minimum distances to every node,The topics discussed in this section include:,Initialization,Sharing,Updating,When to Share,Two-Node Loop Instability,Three-Node Instability,6,TCP/IP Protocol Suite,Figure 14.3,Distance vector routing tables,7,TCP/IP Protocol Suite,Figure 14.4,Initialization of tables in distance vector routing,8,TCP/IP Protocol Suite,In distance vector routing,each node shares its routing table with its immediate neighbors periodically and when there is a change.,Note:,9,TCP/IP Protocol Suite,Figure 14.5,Updating in distance vector routing,10,TCP/IP Protocol Suite,Figure 14.6,Two-node instability,11,TCP/IP Protocol Suite,Figure 14.7,Three-node instability,12,TCP/IP Protocol Suite,14.3 RIP,The Routing Information Protocol(RIP)is an,intradomain,routing protocol used inside an autonomous system.It is a very simple protocol based on distance vector routing.,The topics discussed in this section include:,RIP Message Format,Requests and Responses,Timers in RIP,RIP Version 2,Encapsulation,13,TCP/IP Protocol Suite,Figure 14.8,Example of a domain using RIP,14,TCP/IP Protocol Suite,Figure 14.9,RIP message format,15,TCP/IP Protocol Suite,Figure 14.10,Request messages,16,TCP/IP Protocol Suite,Figure 14.11 shows the update message sent from router R1 to router R2 in Figure 14.8.The message is sent out of interface 130.10.0.2.,Example,1,See Next Slide,The message is prepared with the combination of split horizon and poison reverse strategy in mind.Router R1 has obtained information about networks 195.2.4.0,195.2.5.0,and 195.2.6.0 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(130.10.02)as the next hop address.,17,TCP/IP Protocol Suite,Figure 14.11,Solution to Example 1,18,TCP/IP Protocol Suite,Figure 14.12,RIP timers,19,TCP/IP Protocol Suite,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?,Example,2,Solution,The 21 timers are listed below:,Periodic timer:1 Expiration timer:20 5=15 Garbage collection timer:5,20,TCP/IP Protocol Suite,Figure 14.13,RIP version 2 format,21,TCP/IP Protocol Suite,Figure 14.14,Authentication,22,TCP/IP Protocol Suite,RIP uses the services of UDP on well-known port 520.,Note:,23,TCP/IP Protocol Suite,14.4 LINK STATE ROUTING,In link state routing,if each node in the domain has the entire topology of the domain,the node can use,Dijkstras,algorithm to build a routing table.,每一个点有整个,Domain,全局的拓扑,.,The topics discussed in this section include:,Building Routing Tables,24,TCP/IP Protocol Suite,Figure 14.16,Link state knowledge,25,TCP/IP Protocol Suite,Figure 14.15,Concept of link state routing,26,TCP/IP Protocol Suite,Figure 14.17,Dijkstra,algorithm,27,TCP/IP Protocol Suite,Figure 14.18,Example of formation of shortest path tree,28,TCP/IP Protocol Suite,Table 14.1,Routing table for node A,29,TCP/IP Protocol Suite,14.5 OSPF,The Open Shortest Path First(OSPF)protocol is an,intradomain,routing protocol based on link state routing.Its domain is also an autonomous system.,开放最短路径优先,The topics discussed in this section include:,Areas,区域,Metric,度量,Types of Links,链路类型,Graphical Representation,图形表示法,OSPF Packets OSPF,分组,Link State Update Packet,链路状态更新分组,Other Packets,其他分组,Encapsulation,封装,30,TCP/IP Protocol Suite,Figure 14.19,Areas in an autonomous system,内部路由器,(Internal router),区域边界路由器,(Area border router),主干路由器,(Backbone router)AS,边界路由器,(AS boundary router),31,TCP/IP Protocol Suite,Figure 14.20,Types of links,链路类型,点对点链路,转接链路,残桩链路,虚拟链路,32,TCP/IP Protocol Suite,Figure 14.21,Point-to-point link,33,TCP/IP Protocol Suite,Figure 14.22,Transient link,34,TCP/IP Protocol Suite,Figure 14.23,Stub link,35,TCP/IP Protocol Suite,Figure 14.24,Example of an AS and its graphical representation in OSPF,36,TCP/IP Protocol Suite,Figure 14.25,Types of OSPF packets,共有,5,种不同的,LSA,：,路由器链路,网络链路,汇总链路到网络,汇总链路到,AS,边界路由器,外部链路,37,TCP/IP Protocol Suite,Figure 14.26,OSPF common header,公共首部,38,TCP/IP Protocol Suite,Figure 14.27,Link state update packet,39,TCP/IP Protocol Suite,Figure 14.28,LSA general header,40,TCP/IP Protocol Suite,Figure 14.29,Router link,41,TCP/IP Protocol Suite,Figure 14.30,Router link LSA,42,TCP/IP Protocol Suite,Table 14.2,Link types,link identification,and link data,43,TCP/IP Protocol Suite,Give the router link LSA sent by router 10.24.7.9 in Figure 14.31.,Example,3,Solution,This router has three links:two of type 1(point-to-point)and one of type 3(stub network).Figure 14.32 shows the router link LSA.,See Next Slide,See Figure 14.32,44,TCP/IP Protocol Suite,Figure 14.31,Example 3,45,TCP/IP Protocol Suite,Figure 14.32,Solution to Example 3,46,TCP/IP Protocol Suite,Figure 14.33,Network link,47,TCP/IP Protocol Suite,Figure 14.34,Network link advertisement format,48,TCP/IP Protocol Suite,Give the network link LSA in Figure 14.35.,Example,4,Solution,.,See Next Slide,See Figure 14.36,49,TCP/IP Protocol Suite,Figure 14.35,Example 4,50,TCP/IP Protocol Suite,Figure 14.36,Solution to Example 4,51,TCP/IP Protocol Suite,In Figure 14.37,which,router(s,)sends out router link,LSAs,?,Example,5,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.,See Next Slide,52,TCP/IP Protocol Suite,Figure 14.37,Example 5 and Example 6,53,TCP/IP Protocol Suite,In Figure 14.37,which,router(s,)sends out the network link,LSAs,?,Example,6,Solution,All three network 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.,54,TCP/IP Protocol Suite,Figure 14.38,Summary link to network,55,TCP/IP Protocol Suite,Figure 14.39,Summary link to network LSA,56,TCP/IP Protocol Suite,Figure 14.40,Summary link to AS boundary router,57,TCP/IP Protocol Suite,Figure 14.41,Summary link to AS boundary router LSA,58,TCP/IP Protocol Suite,Figure 14.42,External link,59,TCP/IP Protocol Suite,Figure 14.43,External link LSA,60,TCP/IP Protocol Suite,Figure 14.44,Hello packet,61,TCP/IP Protocol Suite,Figure 14.45,Database description packet,62,TCP/IP Protocol Suite,Figure 14.46,Link state request packet,63,TCP/IP Protocol Suite,Figure 14.47,Link state acknowledgment packet,64,TCP/IP Protocol Suite,OSPF,分组格式,OSPF,使用,5,种类型的分组：,问候分组：节点使用该分组建立邻居关系，测试邻居的可达性。（包含本节点信息及已知邻居的清单）,数据库描述分组：当节点收到一个新邻居的问候分组时，发送数据库描述分组，分组中仅包含数据库中每一行的标题。,链路状态请求分组：由需要一条或几条特定路由的路由器发送。,链路状态更新分组：路由器使用该分组通告它的链路状态。,链路状态确认分组：用于对收到的链路状态更新分组进行确认。,OSPF,分组被封装在,IP,数据报中传输，,OSPF,协议提供确认机制以实现流量控制和差错控制。,65,TCP/IP Protocol Suite,距离向量路由选择,/,链路状态路由选择：限制,可缩放性,当运行区域的跳数稍微多了一些时，距离向量路由选择就变得不稳定。,链路状态路由选择需要非常大的资源来计算路由表，同时由于使用,flooding,的方式，会产生很大的通信量。,引入了第三种路由选择协议，路径向量路由协议。,66,TCP/IP Protocol Suite,14.6 PATH VECTOR ROUTING,Path vector routing is similar to distance vector routing.There is at least one node,called the speaker node,in each AS that creates a routing table and advertises it to speaker nodes in the neighboring,ASs,.,路径向量路由选择,The topics discussed in this section include:,Initialization,Sharing,Updating,67,TCP/IP Protocol Suite,Figure 14.48,Initial routing tables in path vector routing,68,TCP/IP Protocol Suite,Figure 14.49,Stabilized tables for four autonomous systems,69,TCP/IP Protocol Suite,防止环路,不稳定性和环路问题可以通过检查看它的自治系统是否在到达终点的路径上。,70,TCP/IP Protocol Suite,14.7 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.,The topics discussed in this section include:,Types of Autonomous Systems,Path Attributes,BGP Sessions,External and Internal BGP,Types of Packets,Packet Format,Encapsulation,71,TCP/IP Protocol Suite,Figure 14.50,Internal and external BGP sessions,72,TCP/IP Protocol Suite,Figure 14.51,Types of BGP messages,73,TCP/IP Protocol Suite,Figure 14.52,BGP packet header,74,TCP/IP Protocol Suite,Figure 14.53,Open message,75,TCP/IP Protocol Suite,Figure 14.54,Update message,76,TCP/IP Protocol Suite,BGP supports classless addressing and CIDR.,Note:,77,TCP/IP Protocol Suite,Figure 14.55,Keepalive,message,78,TCP/IP Protocol Suite,Figure 14.56,Notification message,79,TCP/IP Protocol Suite,Table 14.3,Error codes,80,TCP/IP Protocol Suite,BGP uses the services of TCP on port 179.,Note:,81,TCP/IP Protocol Suite,Homework,Chapter 14.10.1,7,82,TCP/IP Protocol Suite,