《计算机网络——自顶向下方法与Internet特色》幻灯片Lecture45

1、4-1Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Br

2、oadcast and multicast routing4-2因特网中的路由选择r全球因特网是由诸多 Autonomous Systems (AS)互联而成:m小型自治系统（小型自治系统（Stub AS）: 中小型企业m分区自治系统（分区自治系统（Multihomed AS）:大型企业 (非跨越的)m跨越式自治系统（跨越式自治系统（Transit AS）: NBP等r两层路由选择: mIntra-AS: 由网管决定mInter-AS: 唯一性的标准4-3因特网的AS层次Inter-AS 边界 (外部网关) 路由器Intra-AS 内部 (网关) 路由器4-4Intra-AS Routing

3、AS内部选路rAlso known as Interior Gateway Protocols (IGP) 内部网关协议rMost common Intra-AS routing protocols:mRIP: Routing Information ProtocolmOSPF: Open Shortest Path FirstmIGRP: Interior Gateway Routing Protocol (Cisco proprietary)4-5Intra-AS路由选择r也称为内部网关协议 Interior Gateway Protocols (IGP)r最常用的 IGP有:mRIP:

4、Routing Information Protocol(路由选择信息协议) mOSPF: Open Shortest Path First(开放式最短路径优先（协议）)mIGRP: Interior Gateway Routing Protocol (内部网关路由选择协议，Cisco产权)4-6Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram forma

5、tmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routing4-7RIP ( Routing Information Protocol)rDistance vector algorithmrIncluded in BSD-UNIX Distribution in 1982rDistance metric: #

6、 of hops (max = 15 hops)DCBAuvwxyzdestination hops u 1 v 2 w 2 x 3 y 3 z 2 From router A to subsets:4-8RIP advertisementsrDistance vectors: exchanged among neighbors every 30 sec via Response Message (also called advertisement)rEach advertisement: list of up to 25 destination nets within AS4-9RIP (

7、Routing Information Protocol)r距离向量算法(Distance vector algorithm)r含在BSD-UNIX 1982版中r距离的度量单位: # of hops (max = 15 hops)mCan you guess why?r距离向量: 通过Response报文每隔30秒交换一次 (也称为 广告-advertisement)r每次广告: 发布最多为 25 个AS内的目的子网列表4-10RIP: Example Destination Network Next Router Num. of hops to dest. wA2yB2 zB7x-1.wx

8、yzACDBRouting table in D4-11RIP: Example Destination Network Next Router Num. of hops to dest. wA2yB2 zB A7 5x-1.Routing table in DwxyzACDB Dest Next hops w - 1 x - 1 z C 4 . .Advertisementfrom A to D4-12RIP: Link Failure and Recovery If no advertisement heard after 180 sec - neighbor/link declared

9、deadmroutes via neighbor invalidatedmnew advertisements sent to neighborsmneighbors in turn send out new advertisements (if tables changed)mlink failure info quickly propagates to entire netmpoison reverse used to prevent ping-pong loops (infinite distance = 16 hops)4-13RIP: 链路失效和恢复链路失效和恢复 如果某条链路在18

10、0秒内没有被听到广告 - 相邻结点/链路被申明取消(declared dead)m经由该结点的路由被终止m新的广告送往所有其他相邻结点m其他相邻结点依次发出新的广告 (如果路由表发生变化)m这样链路失效的信息迅速传遍整个网络m使用毒性逆转来防止乒乓循环 (设置有限距离 = 16 hops)4-14RIP Table processingrRIP routing tables managed by application-level process called route-d (daemon)radvertisements sent in UDP packets, periodically r

11、epeatedphysicallinknetwork forwarding (IP) tableTransprt (UDP)routedphysicallinknetwork (IP)Transprt (UDP)routedforwardingtable4-15RIP路由表处理rRIP路由表通过应用层的进程 route-d (daemon-守护程序)来管理r由应用层进程管理的路由表为通过UDP的广告调用, 并周期性重复4-16Chapter 4: Network Layerr4. 1 Introductionr4.2 Virtual circuit and datagram networksr

12、4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routing4-17OSPF (Open Shortest Path First)r“open”: publicly availa

13、blerUses Link State algorithm mLS packet disseminationmTopology map at each nodemRoute computation using Dijkstras algorithmrOSPF advertisement carries one entry per neighbor routerrAdvertisements disseminated to entire AS (via flooding)mCarried in OSPF messages directly over IP (rather than TCP or

14、UDP4-18OSPF (Open Shortest Path First) 开放式最短路径优先（协议）r“open-开放”: 协议的规范化描述向公众开放r使用链路状态算法(Link State algorithm) mLS 分组传播m在每个结点存放网络的拓扑图m路由计算使用Dijkstra算法rOSPF 广告为每个相邻的路由器配置一个条目r广告弥散到 整个 AS (via flooding-泛洪法)4-19OSPF “advanced” features (not in RIP)rSecurity: all OSPF messages authenticated (to prevent ma

15、licious intrusion) Two kinds of authentications: Sample or MD5rMultiple same-cost paths allowed (only one path in RIP) rIntegrated uni- and multicast support: mMulticast OSPF (MOSPF) uses same topology data base as OSPFrHierarchical OSPF in large domains.4-20OSPF “先进”性 (RIP所不具备的)r安全性: 所有的 OSPF 报文须经认

16、证 (以防止各种可能的攻击); 使用简单和MD5两种认证。r多个等值路径允许同时存在 (而在RIP中只能存在一条)r支持集成化的单播和组播(multicast) : m组播 OSPF (MOSPF)使用与 OSPF相同的拓扑数据库r在大型域中可以使用层次型OSPF4-21Hierarchical OSPF 一个AS可以有一个Backbone OSPF区和多个局部OSPF区。主干区域，包含所有区域边界路由器和主干路由器，同时包含边界路由器，向外界联系4-22Hierarchical OSPFrTwo-level hierarchy: local area, backbone.mLink-stat

17、e advertisements only in area meach nodes has detailed area topology; only know direction (shortest path) to nets in other areas.rArea border routers: “summarize” distances to nets in own area, advertise to other Area Border routers.rBackbone routers: run OSPF routing limited to backbone.rBoundary r

18、outers: connect to other ASs.4-23层次型OSPFr双层结构: 本地, 主干.m链路状态只是在本地范围内广告 m每个结点具有详细的本地拓扑; 对其他区域中的网络仅知在某个方向 (最短路径) .r区界路由器区界路由器(Area border routers): “汇总”了所在区域中到达各网络的距离,同时向其他区界路由器发广告.r主干路由器主干路由器(Backbone routers): 仅限于在主干上运行 OSPF 路由算法.r边界路由器边界路由器(Boundary routers): 连接其他的AS.4-24Chapter 4: Network Layerr4.

19、1 Introductionr4.2 Virtual circuit and datagram networksr4.3 Whats inside a routerr4.4 IP: Internet ProtocolmDatagram formatmIPv4 addressingmICMPmIPv6r4.5 Routing algorithmsmLink statemDistance VectormHierarchical routingr4.6 Routing in the InternetmRIPmOSPFmBGPr4.7 Broadcast and multicast routing4-

20、25Internet inter-AS routing: BGPrBGP (Border Gateway Protocol): the de facto standardrBGP provides each AS a means to:rObtain subnet reachability information from neighboring ASs.rPropagate the reachability information to all routers internal to the AS.rDetermine “good” routes to subnets based on re

21、achability information and policy.1.Allows a subnet to advertise its existence to rest of the Internet: “I am here”4-26因特网inter-AS路由选择: BGPrBGP (Border Gateway Protocol，边界网关协议): 事实上的标准r路径向量路径向量(Path Vector) 协议:m与距离向量协议类似m每个边界网关(Border Gateway)向其对等的相邻实体(peers)广播通往目的AS的整条路经 (I.e, 一系列 ASs)mE.g., 网关 X可以

22、发送从它通往目的AS Z的路经: Path (X,Z) = X,Y1,Y2,Y3,Z4-27BGP basicsrPairs of routers (BGP peers) exchange routing info over semi-permanent TCP connections: BGP sessionsrNote that BGP sessions do not correspond to physical links.rWhen AS2 advertises a prefix to AS1, AS2 is promising it will forward any datagram

23、s destined to that prefix towards the prefix.mAS2 can aggregate prefixes in its advertisement3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP sessioniBGP session4-28Distributing reachability inforWith eBGP session between 3a and 1c, AS3 sends prefix reachability info to AS1.r1c can then use iBGP do distribute this

24、 new prefix reach info to all routers in AS1r1b can then re-advertise the new reach info to AS2 over the 1b-to-2a eBGP sessionrWhen router learns about a new prefix, it creates an entry for the prefix in its forwarding table.3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP sessioniBGP session4-29Path attributes &a

25、mp; BGP routesrWhen advertising a prefix, advert includes BGP attributes. mprefix + attributes = “route”rTwo important attributes:mAS-PATH: contains the ASs through which the advert for the prefix passed: AS 67 AS 17 (ASN)mNEXT-HOP: Indicates the specific internal-AS router to next-hop AS. (There ma

26、y be multiple links from current AS to next-hop-AS.)rWhen gateway router receives route advert, uses import policy to accept/decline.4-30BGP route selectionrRouter may learn about more than 1 route to some prefix. Router must select route.rElimination rules (消除规则：一条一条执行，直到选出一条路为止):mLocal preference

27、value attribute （本地偏好值属性）: policy decision （策略决定）。通过策略决定选择本地偏好值最高的路径。m在余下的路径中，按Shortest AS-PATH规则选 m在余下的路径中按Closest NEXT-HOP router: hot potato routing1.在余下的路径中，采用Additional criteria 4-31BGP messagesrBGP messages exchanged using TCP.rBGP messages:mOPEN: opens TCP connection to peer and authenticates

28、 sendermUPDATE: advertises new path (or withdraws old)mKEEPALIVE keeps connection alive in absence of UPDATES; also ACKs OPEN requestmNOTIFICATION: reports errors in previous msg; also used to close connection4-32因特网inter-AS路由选择: BGPrBGP 使用 TCP交换报文.rBGP报文:mOPEN: 打开通往对等实体的 TCP连接并对发送者进行认证mUPDATE: 公告新的

29、路经 (或撤销旧路经)mKEEPALIVE : 在不进行UPDATES时保持连接的激活; 也用来ACKs OPEN 请求mNOTIFICATION: 报告先前报文的错误;也用来关闭连接4-33BGP routing policy Figure 4.5-BGPnew: a simple BGP scenario A B C W X Y legend: customer network: provider network rA,B,C are provider networks （AS）rX,W,Y are customer (of provider networks)：stub network （桩网络或端网络）rX is dual-homed: attached to two networksmX does not want to route from B via X to Cm. so X