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

《数据通讯与计算机网络讲义 22章.ppt》由会员分享，可在线阅读，更多相关《数据通讯与计算机网络讲义 22章.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter 22Chapter 22Network Layer:Network Layer:Delivery(交付),Forwarding(转发),and Routing(路由)1转发：将分组放置到通向目的地的路径上去。源端和路由器需要具有路由表。22.2 Forwarding (转发)如何使路由表的查找更加有效?2l Route method vs.next-hop methodu 转发策略转发策略3l Host-specific versus network-specific method4l Default method5u Forwarding ProcessForwarding

2、Process6例例 22.122.1Make a routing table for router R1/00.0.0.07Show the forwarding process if a packet arrives at R1 in the figure with the destination address 180.70.65.140.例例 22.222.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=

3、(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 匹配于匹配于因此从因此从m0m0转发。转发。8Show the forwarding process if a packet arrives at R1 in the figure with the destination address 201.4.22.35.例例 22.322.3(35)10=(0 0 1 0 0 0 1 1)29Show the forwarding process if a packet

4、 arrives at R1 in the figure with the destination address 18.24.32.78.例例 22.422.410l Address aggregation Address aggregation (地址聚合减少表项数）_ _ _ 00000000 (0)_ _ _ 01000000 (64)_ _ _ 10000000 (128)_ _ _ 11000000 (192)/24 /2611l Longest mask matching Longest mask matching （最长掩码匹配）（最长掩码匹配）D=140.24.7.200(2

5、00)10=(11001000)2思考：将一个网络划分成2个子网，地址数比例为1:3。如何划分（路由器的两个出口对应这两个子网，表项内容）？12例例 22.522.5l Hierarchical routing Hierarchical routing （层次路由）（层次路由）13u Routing TableFive flags:U G H D Mup gateway host added modified -specific -redirection -redirection使用该表项的主机数目使用该表项已转发的分组数目14直接交付间接交付151617u Direct vs.Indirec

6、t Delivery (在在22.2后讲后讲)22.1 Delivery （交付）（交付）1822.3 Unicast Routing Protocols u 路由算法的分类使用全局信息还是局部信息？全局信息:l每个路由器获取整个网络的拓扑(连通性)和链路代价信息(广播)l“链路状态”算法 (Link State Routing/OSPF)局部信息:l每个路由器仅从相邻节点获取代价信息l“距离向量”算法 (Distance Vector Routing/RIP)静态还是动态？静态:路由表配置后不被自动改变动态:根据网络状态自动修改路由表l周期性修正l根据链路代价变化而修正19uyxwvz221

7、3112535链路(x,x)的代价记为c(x,x)代价可以由时延、带宽、差错率、费用、转跳数等度量。路径(x1,x2,x3,xp)的代价=c(x1,x2)+c(x2,x3)+c(xp-1,xp)Q:在u到z之间的最小代价路径是哪条？路由算法:用于发现最小代价路径的算法u 代价（cost）20 Autonomous systemsu Intra-and Interdomain Routing2122u 距离向量算法(Distance Vector Routing)定义：c(x,v)：x至相邻节点v的代价 dx(y):x至y的最小代价路径的总代价则有 v是x的所有相邻节点。dx(y)=min c(

8、x,v)+dv(y)vBellman-Ford公式(动态规划)xaxeybc(x,a)c(x,b)c(x,e)da(y)db(y)de(y)23 dx(y)：从x至y的最小代价估计 c(x,v)：x至相邻节点v的代价l节点x记录自本节点至所有其它节点y的距离向量估计 D Dx=dx(y):yN l节点x接收来自相邻节点v的距离向量 D Dv=dv(y):yN l节点x从相邻节点v接收到新的“距离向量”后，使用B-F公式修正自身的距离向量Dx=dx(y):yN：对于x的每一个目的节点 y N，dx(y)minv c(x,v)+dv(y)取得最小值的邻节点v*是x至y路径上的“next hop”。

9、n 距离向量算法描述24距离向量算法示例1（同步运算）：uyxwvz2213112535u节点有三个相邻节点v,x,w，已知 dv(z)=5,dx(z)=3,dw(z)=3du(z)=min c(u,v)+dv(z),c(u,x)+dx(z),c(u,w)+dw(z)=min 2+5,(v)1+3,(x)5+3 (w)=4 (x)u作为源节点，从u到z的最小代价路径的“下一站”是x。由B-F公式:25Distance vector routing tables距离向量算法示例2（异步运算）：26Initialization of tables in distance vector routin

10、g27由接收的距离向量修正路由表E5E7728Two-node loop instabilityl Problem of Distance Vector Routing解决措施解决措施:设置“代价”的最大值(如100)；B向A发路由表之前，删去”next”为”A”的行；对“next=A”的项，B向A发“x,”,使得A重置x表项的timer，但不修正cost值。29Three-node instabilityA C B直至cost 30n RIP协议（Routing Information Protocol）RIP采用“距离向量法”；RIP的“代价”为“转跳数”，每段链路的代价为1；RIP的最大

11、转跳数为15。31lRIP 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”更新该表项YYNNNY结束定时器事件或本地状态变化32u Link state routingl每个节点知道整个网络拓扑以及各链路代价每个节点将自身邻域的链路状态信息向全网广播 所有节点具有相

12、同的“图”l每个节点以自身为根，计算从根到各个其它节点的最小代价路径（Dijkstra 算法:经过k次迭代，得到至k个节点的最小代价路径。）作出该节点的路由表3334链路状态法建立路由表的步骤（四步）链路状态法建立路由表的步骤（四步）l步骤1：生成“link state packet (LSP)”含“node ID,neighbor,cost,seq.,live-time,”周期性或发现网络状态发生变化时l步骤2：Flooding LSPs (各节点仅转发新版本的LSP)l步骤3：构造“最短路径树”（p.36示例）l步骤4：根据“最短路径树”生成路由表 （P.37示例）35l步骤3：构造“最短

13、路径树”36Routing table for node AAAACl步骤4：根据“最短路径树”生成路由表37u OSPF (Open Shortest Path First)l“intra-AS”协议 l链路状态算法 LS报文的分发（广播）每个节点具有相同的网络拓扑图采用Dijkstra算法计算路由lOSPF报文广播到本AS中的所有路由器。OSPF分组直接封装在IP分组中。l安全性：所有OSPF报文均进行认证(防止非法信息修改路由表)；l允许使用多条相同代价的路径(RIP仅支持一条路径)；l对于每一条链路,支持多种代价度量；l支持单播和组播:组播OSPF(MOSPF)使用同单播OSPF一样的

14、拓扑数据（在OSPF最佳树基础上，剪裁成“组成员”路径树）；l在大的地理范围，采用分层式OSPF（“area”）。OSPF的“先进”特点(在RIP中不具有的)：38l Areas两级的层次结构:局部区域,骨干区域内部路由器之间的“Link-state”广播仅在局部区域中；每个内部路由器具有所在区域内的详细拓扑信息。区域边界路由器“汇总”本区域中到各网络的路径代价，将此信息告知其它区域的“区域边界路由器 ”。骨干路由器:在骨干区域范围内运行OSPF路由协议(广播，运算)。边疆路由器:实现同其它自治系统的连接(网关)。39l Types of links(1)Point-to-point link

15、40(2)Transient link(3)Stub link41虚拟链路非真实相邻的两个路由器间的一条通路，人工配置为虚拟“相邻”，实际可能通过若干个路由器。(4)Virtual linkl Types of Packets “link state packet (LSP)”含“node ID,neighbor,cost,seq.,live-time,”真实路由器发送Designated router发送Area border router 发送给相邻areaArea border router 发送给AS boundary routerAS boundary router 发送给本AS42

16、graphical representation in OSPFDesignated router43u 因特网的“inter-AS”路由协议:BGPl 为何“Intra-AS”和“Inter-AS”使用不同的路由策略?政策性原因 规模原因性能原因 l Path vector routingl BGP(Border Gateway Protocol）44在边界路由器中的BGP协议实体的功能:从相邻AS获取其它网络的可达性信息；将上述可达性信息传递给本AS中的所有路由器；基于可达性信息以及其它“选路策略”，确定至其它 AS中网络的“好”路径。3b1d3a1c2aAS3AS1AS21a2c2b1b

17、3c451.BGP的基本概念BGP路由器基于半永久性TCP连接(port 179)交换路由信息：BGP“会话”（sessions）3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP sessioniBGP session在3a和1c之间进行“eBGP”会话，AS3发送经AS3的可达性信息给AS1。1c使用“iBGP”会话来分发新的可达性信息给AS1中的所有路由器。1b使用1b到2a的“eBGP”会话传递可达性信息给AS2。当各个路由器获知新的可达路径信息后,在自身的转发表中建立新的表项。462.路径属性每个自治系统有唯一的“自治系统号”(ASN)传递的报文中包含若干BGP属性。

18、两种重要的BGP属性:AS-PATH:BGP报文传递过程中经过的AS集合的列表，如:“AS6,AS7，”（可检测、防止路径循环）；NEXT-HOP:“为到达下一个AS，BGP网关转发报文的出口IP地址”（示例：1d根据到3a的“出口地址j”的最短路径，确定到子网x的路由表项“目的网络x,出端口k”）473.BGP报文BGP报文封装在TCP报文段中。BGP报文类型（四种）:OPEN:在对等方之间建立TCP连接，并对发送方进行认证；UPDATE:传送新的路径信息（或去除旧的路径信息)KEEPALIVE：在不传递UPDATE报文期间，保持已建立的连接，或对OPEN报文作确认。NOTIFICATION

19、:报告前三种报文的差错。4.BGP路径选择路由器从BGP报文可获知到子网x的不止一条的路径，路由器要从中选择。去除准则(按优先级排序):1.本AS的政策性选择（偏好值设置）；2.最短的AS路径（AS跳数）；3.最近的“NEXT-HOP”路由器(端口)；4.其它准则 4822.4 Multicast Routing Protocols l Unicastingu Unicast,Multicast,and Broadcast49l Multicastingl Broadcasting50l Multicasting vs.multiple unicastingl Efficiencyl Dela

20、y51l Common multicast protocolsRPF RPB RPMDistance-Vector Multicast Routing ProtocolMulticast-OSPFCore-Based TreeProtocol Independent Multicast-Dense ModeProtocol Independent Multicast-Sparse Mode52u MOSPF (source-based tree)l Multicasting OSPF (link-state routing)l The tree is premade,prepruned,and

21、 ready to be usedD站为根算出的treeB站为根算出的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

22、 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).54l MOSPF在原OSPF协议基础上，增加了一种新的“link state update”报文(group membership LSA),用于传递“路由器单播地址同路由器组播地址的关联信息”(含有组成员主机的网络表示为作为组成员的“designated router”)。由此,在组播树的LSDB中,用组成

23、员(由同一的组播地址判定)的单播地址由Dijkstra算法计算出该组成员构成的 least-cost tree。l 当组成员关系变化时，也发送上述报文，更新least-cost tree。l 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.55u DVMRP (

24、source-based tree)Distance Vector Multicast Routing Protocolq RPF (Reverse path forwarding)abab路由表目的网络下一路由器出端口Des.NetaSource IP,入端口aSource IP,入端口b(Broadcasting)56Problem with RPFRPF eliminates the loop in the flooding process.In RPF,the router forwards(broadcasts)only the packets that have traveled

25、the shortest path from the source to the router;all other copies are discarded.57q 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 o

26、f the packet.58q RPM (Reverse path multicasting)RPM adds pruning and grafting to RPB to create a multicast shortest path tree that supports dynamic membership changes.59u CBT (core-based tree)Group-shared protocoll Formation of the tree60 select a center router for the group(core)every other router

27、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 upstr

28、eam router and downstream router,so the tree is formed 61l 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.62Shortest path tree in unicast routingl unicast routingIn unicast rout

29、ing,each router in the domain has a table that defines a shortest path tree to possible destinations.63Source-based tree approachIn the source-based tree approach,each router needs to have one shortest path tree for each group.lMulticasting routing64Group-shared tree approachIn the group-shared tree approach,only the core router,which has a shortest path tree for each group,is involved in multicasting.65