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

第,22,章,-,*,Chapter 22,Network Layer:,Delivery,(,交付,),Forwarding,(,转发,),and Routing,(,路由,),1,转发：,将分组放置到通向目的地的路径上去。,源端和路由器需要具有,路由表,。,2,2.2 Forwarding,(,转发,),如何使路由表的查找更加有效,?,2,Route method vs.,next-hop,method,转发策略,3,Host-specific versus,network-specific,method,4,Default method,5,Forwarding Process,6,例,22.1,M,ake a routing table for router R1,/0,0.0.0.0,7,Show the forwarding process if a packet arrives at,R1,in the figure with the destination address,180.70.65.,140,.,例,22.2,(140),10,=(,1 0,0 0 1 1 0 0),2,(192),10,=(,1 1,0 0 0 0 0 0),2,(,由,/26),与,(,1 1,0 0 0 0 0 0),2,(,1 0,0 0 0 0 0 0),2,不匹配于,(140),10,=(,1,0 0 0 1 1 0 0),2,(128),10,=(,1,0 0 0 0 0 0 0),2,(,由,/25),与,(,1,0 0 0 0 0 0 0),2,(,1,0 0 0 0 0 0 0),2,匹配于,因此从,m0,转发。,8,Show the forwarding process if a packet arrives at R1 in the figure with the destination address 201.4.22.,35,.,例,22.3,(35),10,=(,0 0,1 0 0 0 1 1),2,9,Show the forwarding process if a packet arrives at,R1,in the figure with the destination address,18.24.32.78,.,例,22.4,10,Address aggregation,(,地址聚合,减少表项数）,_ _ _ 00000000 (0),_ _ _ 01000000 (64),_ _ _ 10000000 (128),_ _ _ 11000000 (192),/24 /26,11,Longest mask matching,（最长掩码匹配）,D=140.24.7.200,(200),10,=(,11,001000),2,思考：将一个网络划分成,2,个子网，地址数比例为,1:3,。如何划分（路由器的两个出口对应这两个子网，表项内容）？,12,例,22.5,Hierarchical routing,（层次路由）,13,Routing Table,F,ive flags,:U G H D M,u,p,g,ateway,h,ost a,d,ded,m,odified,-specific -redirection,-redirection,使用该表项的主机数目,使用该表项已转发的分组数目,14,直接交付,间接交付,15,16,17,Direct vs.Indirect Delivery (,在,22.2,后讲,),2,2.1 Delivery,（交付）,18,2,2.3,Unicast Routing Protocols,路由算法的分类,使用全局信息还是局部信息？,全局信息,:,每个路由器获取整个网络的拓扑,(,连通性,),和链路代价信息,(,广播,),“,链路状态,”,算法,(Link State Routing/OSPF),局部信息,:,每个路由器仅从相邻节点获取代价信息,“,距离向量,”,算法,(Distance Vector Routing/RIP),静态还是动态,？,静态,:,路由表配置后不被自动改变,动态,:,根据网络状态自动修改路由表,周期性修正,根据链路代价变化而修正,19,u,y,x,w,v,z,2,2,1,3,1,1,2,5,3,5,链路,(x,x,),的代价记为,c(x,x,),代价可以由时延、带宽、差,错率、费用、转跳数等度量。,路径,(x,1,x,2,x,3,x,p,),的代价,=c(x,1,x,2,)+c(x,2,x,3,)+c(x,p-1,x,p,),Q:,在,u,到,z,之间的最小代价路径是哪条？,路由算法,:,用于发现最小代价路径的算法,代价（,cost,）,20,Autonomous systems,Intra-and Interdomain Routing,21,22,距离向量算法,(,Distance Vector Routing),定义：,c(x,v,),：,x,至相邻节点,v,的代价,d,x,(y,),:x,至,y,的最小代价路径的总代价,则有,v,是,x,的所有相邻节点。,d,x,(y,)=min,c(x,v,)+,d,v,(y,),v,Bellman-Ford,公式,(,动态规划,),x,a,x,e,y,b,c(x,a,),c(x,b,),c(x,e,),d,a,(y,),d,b,(y,),d,e,(y,),23,d,x,(y,),：从,x,至,y,的最小代价估计,c(x,v,),：,x,至相邻节点,v,的代价,节点,x,记录自本节点至所有其它节点,y,的距离向量估计,D,x,=,d,x,(y,):y,N,节点,x,接收来自相邻节点,v,的距离向量,D,v,=,d,v,(y,):,yN,节点,x,从相邻节点,v,接收到新的,“,距离向量,”,后，使用,B-F,公式修正自身的距离向量,D,x,=,d,x,(y,):y,N,：,对于,x,的每一个目的节点,y N,，,d,x,(y,),min,v,c(x,v,)+,d,v,(y,),取得最小值的邻节点,v*,是,x,至,y,路径上的,“,next hop,”,。,距离向量算法描述,24,距离向量算法示例,1,（同步运算）：,u,y,x,w,v,z,2,2,1,3,1,1,2,5,3,5,u,节点有三个相邻节点,v,x,w,，,已知,d,v,(z,)=5,d,x,(z,)=3,d,w,(z,)=3,d,u,(z,)=min,c(u,v)+,d,v,(z,),c(u,x)+,d,x,(z,),c(u,w)+,d,w,(z,),=min 2+5,(v),1+3,(x),5+3 (w),=4 (,x,),u,作为源节点，从,u,到,z,的最小代价路径的“下一站”是,x,。,由,B-F,公式,:,25,Distance vector routing tables,距离向量算法示例,2,（异步运算）：,26,Initialization,of tables in distance vector routing,27,由接收的距离向量修正路由表,E,5,E,7,7,28,Two-node loop instability,Problem of Distance Vector Routing,解决措施,:,设置,“,代价,”,的最大值,(,如,100),；,B,向,A,发路由表之前，删去,”,next,”,为,”,A,”,的行；,对,“,next=A,”,的项，,B,向,A,发,“,x,”,使得,A,重置,x,表项的,timer,，但不修正,cost,值。,29,Three-node instability,A C B,直至,cost,30,RIP,协议（,Routing Information Protocol,）,RIP,采用,“,距离向量法,”,；,RIP,的,“,代价,”,为,“,转跳数,”,，每段链路的代价为,1,；,RIP,的最大转跳数为,15,。,31,RIP updating algorithm,（异步运算）,各,router,将本站的距离向量发送给邻站,某,router,接收到邻站,j,发来的,RIP,报文,对报文中的各个,dest,k,(k=1,2,.N):,dest,k,在本站路由表中？,将“,dest,k,新,cost,k,+1,j,”,加入路由表,新,cost,k,+1旧,cost,k,？,将“新,cost,k,+1,j,”,更新该表项,至目的站,k,的下一站是,j,？,将“新,cost,k,+1,”,更新该表项,Y,Y,N,N,N,Y,结束,定时器事件或本地状态变化,32,Link state routing,每个节点知道整个网络拓扑以及各链路代价,每个节点将自身邻域的链路状态信息向全网广播,所有节点具有相同的,“,图”,每个节点以自身为根，计算从根到各个其它节点的最小代价路径,（,Dijkstra,算法,:,经过,k,次迭代，得到至,k,个节点的最小代价路径。）,作出该节点的路由表,33,34,链路状态法建立路由表的步骤（四步）,步骤,1,：生成,“,link state packet (LSP),”,含,“,node ID,neighbor,cost,seq.,live-time,”,周期性或发现网络状态发生变化时,步骤,2,：,Flooding,LSPs,(,各节点仅转发新版本的,LSP),步骤,3,：构造,“,最短路径树,”,（,p.36,示例）,步骤,4,：根据,“,最短路径树,”,生成路由表,（,P.37,示例）,35,步骤,3,：构造,“,最短路径树,”,36,Routing table for node A,A,A,A,C,步骤,4,：根据,“,最短路径树,”,生成路由表,37,OSPF (Open Shortest Path First),“,intra-AS,”,协议,链路状态算法,LS,报文的分发（广播）,每个节点具有相同的网络拓扑图,采用,Dijkstra,算法计算路由,OSPF,报文广播到本,AS,中的所有路由器。,OSPF,分组直接封装在,IP,分组中。,安全性：所有,OSPF,报文均进行认证,(,防止非法信息修改路由表,),；,允许使用多条相同代价的路径,(RIP,仅支持一条路径,),；,对于每一条链路,支持多种代价度量；,支持单播和组播,:,组播,OSPF(MOSPF),使用同单播,OSPF,一样的拓扑数据（在,OSPF,最佳树基础上，剪裁成,“,组成员,”,路径树）；,在大的地理范围，采用分层式,OSPF,（,“,area,”,）。,OSPF,的,“,先进,”,特点,(,在,RIP,中不具有的,),：,38,Areas,两级的层次结构,:,局部区域,骨干区域,内部路由器之间的,“,Link-state,”,广播仅在局部区域中,；,每个,内部路由器,具有所在区域内的详细拓扑信息。,区域边界路由器,“,汇总,”,本区域中到各网络的路径代价，将此信息告知其它区域的,“,区域边界路由器,”,。,骨干路由器,:,在骨干区域范围内运行,OSPF,路由协议,(,广播，运算,),。,边疆路由器,:,实现同其它自治系统的连接,(,网关,),。,39,Types of links,(1)Point-to-point link,40,(2)Transient link,(3)Stub link,41,虚拟链路,非真实相邻的两个路由器间的一条通路，人工配置为虚拟,“,相邻,”,，实际可能通过若干个路由器。,(4),Virtual link,Types of Packets,“,link state packet (LSP)”,含,“,node ID,neighbor,cost,seq.,live-time,”,真实路由器发送,D,esignated router,发送,A,rea border router,发送给相邻,area,Area border router,发送给,AS boundary router,AS boundary router,发送给本,AS,42,graphical representation in OSPF,Designated router,43,因特网的,“,inter-AS,”,路由协议,:BGP,为何,“,Intra-AS,”,和,“,Inter-AS,”,使用不同的路由策略,?,政策性原因,规模原因,性能原因,Path vector routing,BGP(Border Gateway Protocol,）,44,在边界路由器中的,BGP,协议实体的功能,:,从相邻,AS,获取其它网络的可达性信息；,将上述可达性信息传递给本,AS,中的所有路由器；,基于可达性信息以及其它,“,选路策略,”,，确定至其它,AS,中网络的,“,好,”,路径。,3b,1d,3a,1c,2a,AS3,AS1,AS2,1a,2c,2b,1b,3c,45,1.BGP,的基本概念,BGP,路由器基于半永久性,TCP,连接,(port 179),交换路由信息：,BGP,“,会话,”,（,sessions,）,3b,1d,3a,1c,2a,AS3,AS1,AS2,1a,2c,2b,1b,3c,eBGP,session,iBGP,session,在,3a,和,1c,之间进行,“,eBGP,”,会话，,AS3,发送经,AS3,的可达性信息给,AS1,。,1c,使用,“,iBGP,”,会话来分发新的可达性信息给,AS1,中的所有路由器。,1b,使用,1b,到,2a,的,“,eBGP,”,会话传递可达性信息给,AS2,。,当各个路由器获知新的可达路径信息后,在自身的转发表中建立新的表项。,46,2.,路径属性,每个自治系统有唯一的,“,自治系统号,”,(ASN),传递的报文中包含若干,BGP,属性。,两种重要的,BGP,属性,:,AS-PATH:BGP,报文传递过程中经过的,AS,集合的列表，如,:,“,AS6,AS7,，,”,（可检测、防止路径循环）；,NEXT-HOP:,“,为到达下一个,AS,，,BGP,网关转发报文的出口,IP,地址,”,（示例：,1d,根据到,3a,的,“,出口地址,j,”,的最短路径，确定到子网,x,的路由表项,“,目的网络,x,出端口,k,”,）,47,3.BGP,报文,BGP,报文封装在,TCP,报文段中。,BGP,报文类型（四种）,:,OPEN:,在对等方之间建立,TCP,连接，并对发送方进行认证；,UPDATE:,传送新的路径信息（或去除旧的路径信息,),KEEPALIVE,：在不传递,UPDATE,报文期间，保持已建立的连接，或对,OPEN,报文作确认。,NOTIFICATION:,报告前三种报文的差错。,4.BGP,路径选择,路由器从,BGP,报文可获知到子网,x,的不止一条的路径，路由器要从中选择。,去除准则,(,按优先级排序,):,本,AS,的政策性选择（偏好值设置）；,最短的,AS,路径（,AS,跳数）；,最近的,“,NEXT-HOP,”,路由器,(,端口,),；,其它准则,48,2,2.4 Multi,cast Routing Protocols,Unicasting,Unicast,Multicast,and Broadcast,49,Multicasting,Broadcasting,50,Multicasting vs.multiple,unicasting,E,fficiency,Delay,51,Common multicast protocols,RPF RPB RPM,Distance-Vector Multicast Routing Protocol,Multicast-OSPF,Core-Based Tree,Protocol Independent Multicast-Dense Mode,Protocol Independent Multicast-Sparse Mode,52,MOSPF,(source-based tree),M,ulticasting,OSPF,(link-state routing),The tree is,premade,prepruned,and ready to be used,D,站为根算出的,tree,B,站为根算出的,tree,各站均以,A,站为根算出的,tree,。一对,”,源，组,”,产生一棵树。,53,比较：,OSPF:,each router use,Dijkstra,algorithm to create a least-cost tree in that the,router as the root,and the rest of routers as nodes of the tree.,MOSPF:,each router use,Dijkstra,algorithm to create a least-cost tree in that the,source as the root,and with the router itself as a node in the tree (each router creates exactly the same tree for the same source-group pair).,54,MOSPF,在原,OSPF,协议基础上，增加了一种新的,“,link state update,”,报文(,group membership LSA),用于传递,“,路由器,单播地址,同路由器,组播地址,的关联信息,”,(含有组成员主机的网络表示为作为组成员的,“,designated router,”,)。,由此,在组播树的,LSDB,中,用组成员(由同一的组播地址判定)的单播地址由,Dijkstra,算法计算出该组成员构成的,least-cost tree。,当组成员关系变化时，也发送上述报文，更新,least-cost tree。,MOSPF is,data-driven,:the first time a MOSPF router receives a multicast packet with a given source and group address,the router calculates the tree,and saved in the cache memory for future use.,55,DVMRP,(source-based tree),Distance Vector Multicast Routing Protocol,RPF (,Reverse path forwarding,),a,b,a,b,路由表,目的网络,下,一路由器,出,端口,Des.Net,a,Source IP,入端口,a,Source IP,入端口,b,(Broadcasting),56,Problem with RPF,RPF eliminates the loop in the flooding process.,In RPF,the router forwards(,broadcasts,)only the packets that have traveled the shortest path from the source to the router;all other copies are discarded.,57,RPB,(,Reverse path broadcasting,),对,特定的源和组，各,Net,仅选择一个,router,作为该源和组的,“,指定的父路由器,”,RPB creates a shortest-path broadcast tree from the source to each destination.It guarantees that each destination receives one and only one copy of the packet.,58,RPM,(,Reverse path multicasting,),RPM adds,pruning,and,grafting,to RPB to create a multicast shortest path tree that supports dynamic membership changes.,59,CBT,(core-based tree),Group-shared protocol,Formation of the tree,60,select a center router for the group(core),every other router gets,unicast,address of the center router,routers connected with the networks in which there are group members send“join message”to the center router,each intermediate router forwards the“join message”,recording information(senders address,port,multicast address),every router involved knows its upstream router and downstream router,so the tree is formed,61,Sending multicast packets,In CBT,the source sends the multicast packet to the core router.The core router,decapsulates,the packet and forwards it to all interested hosts.,62,Shortest path tree in unicast routing,unicast routing,In unicast routing,each router in the domain has a table that defines a shortest path tree to possible destinations.,63,Source-based tree approach,In the source-based tree approach,each router needs to have one shortest path tree for each group.,Multicasting routing,64,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.,65,