TCPIP协议原理教学课件：Chapter 11 Routing Protocol

《TCPIP协议原理教学课件：Chapter 11 Routing Protocol》由会员分享，可在线阅读，更多相关《TCPIP协议原理教学课件：Chapter 11 Routing Protocol（107页珍藏版）》请在金锄头文库上搜索。

1、2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1 1Chapter 11 Routing Protocolsl lInterior(内部内部) and exterior(外部外部) routingl lRIPl lOSPFl lBGP-42024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2 2Introductionl l互互联网由网由许多多路由器路由器连接起来的网接起来的网络组成成l l数据从源站点到目的站点，可能数据从源站点到目的站点，可能经过多个多个路由

2、器路由器l l一个一个路由器路由器连接多个网接多个网络，当路由器收到，当路由器收到分分组，应该将分将分组转发到哪个网到哪个网络？2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3 3Introductionl l路由路由路由路由选择协议选择协议(Routing protocol)(Routing protocol)使得路由器使得路由器使得路由器使得路由器l lTo To shareshare the knowledge about the internet the knowledge about the internetl l

3、To To calculatecalculate the routing table based on the the routing table based on the topologytopology or or the the policiespolicies（策略）（策略）（策略）（策略）l lRouting TableRouting Tablel lStatic route Static route manually define manually definel lDynamic route Dynamic route routing protocolrouting protoc

4、oll lTable-driven routingTable-driven routing（表（表（表（表驱动驱动路由路由路由路由选择选择）l lOne router One router More routed protocolsMore routed protocolsl lOne routed protocolOne routed protocol（例如（例如（例如（例如IPIP） OneOne routing table routing tablel lOne routed protocol One routed protocol More routing protocols More

5、 routing protocolsConvergenceConvergenceOverheadOverheadScalabilityScalability2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4 4Metric（度量）（度量）l lMetricMetric：用来衡量：用来衡量：用来衡量：用来衡量通通通通过过某一网某一网某一网某一网络络所需的所需的所需的所需的代价代价代价代价l l代价代价代价代价是什么？是什么？是什么？是什么？l l代价的度量取决于代价的度量取决于代价的度量取决于代价的度量取决于Routing Pr

6、otocolRouting Protocoll lHop countHop count（跳数）（跳数）（跳数）（跳数）, bandwidth, bandwidth（带宽带宽）, delay, delay（延（延（延（延迟迟）, MTU, load, MTU, load（负载负载）, reliability, reliability（可靠性）（可靠性）（可靠性）（可靠性）, , l lRouting protocol Routing protocol 使用使用使用使用MetricMetric来来来来选择选择一条一条一条一条 best best path path （最（最（最（最优优路）路）路）

7、路）for routingfor routingl lThe metric of a route = The metric of a route = MINMIN SUMSUM(Metric(Metricn n) ) l lThe metric of a route The metric of a route MAXMAX MINMIN(Metric(Metricn n) )64K64K64K64K10M10M10M10M10M10MHop count: A Hop count: A B B Net NetBandwidth: A Bandwidth: A C C D D Net NetA A

8、D DC CB BNetNetn nPathPathn nPathPath度量取决于所需度量取决于所需度量取决于所需度量取决于所需要的服务类型要的服务类型要的服务类型要的服务类型2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite5 5Convergence（收敛）（收敛）l lConvergenceConvergencel lAll routers in a network agree on the All routers in a network agree on the topologytopologyl lConverge

9、nce timeConvergence time（收（收（收（收敛时间敛时间）l lA measure of how quickly to recover from A measure of how quickly to recover from network changesnetwork changesl l从不一致到一致所从不一致到一致所从不一致到一致所从不一致到一致所经历经历的的的的时间时间l l体体体体现现路由算法的效率路由算法的效率路由算法的效率路由算法的效率Dest.A AB BC CD D2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP P

10、rotocol Suite6 6Convergence（收敛）（收敛）l lFactors affecting convergencel lThe routing protocol usedThe routing protocol usedl lA routers distance from the point of changeA routers distance from the point of changel lThe number of routers in the networkThe number of routers in the networkl lBandwidth and

11、 traffic load on communications Bandwidth and traffic load on communications linkslinksl lA routers loadA routers loadl lTraffic patterns in relation to the topology Traffic patterns in relation to the topology changechange2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7 7Interior & Exter

12、ior Routingl l为为什么需要什么需要什么需要什么需要ASAS？l l主要原因主要原因主要原因主要原因：InternetInternet网网网网络络太大，一种路由太大，一种路由太大，一种路由太大，一种路由协议协议无法更新所有路由器的路无法更新所有路由器的路无法更新所有路由器的路无法更新所有路由器的路由表由表由表由表l lAutonomous systemAutonomous system（自治系自治系自治系自治系统统，ASAS）l lA group of A group of networks and routersnetworks and routers under the aut

13、hority of under the authority of a single a single administrationadministrationl lEach AS typically represents an independent organization and Each AS typically represents an independent organization and applies applies its own unique routing and security policiesits own unique routing and security

14、policiesl l域内路由和域域内路由和域域内路由和域域内路由和域间间路由路由路由路由l lAS numberAS numberl lAn identifying number that is assigned by an Internet registry An identifying number that is assigned by an Internet registry or a service provideor a service providel lRange: 165535Range: 165535（Private AS number: 6451265535Privat

15、e AS number: 6451265535）l lInternetInternet由若干由若干由若干由若干ASAS互相互相互相互相连连接构成接构成接构成接构成l l每个每个每个每个ASAS内可能有多个网内可能有多个网内可能有多个网内可能有多个网络络存在存在存在存在l l核心主干网也可以构成一个核心主干网也可以构成一个核心主干网也可以构成一个核心主干网也可以构成一个ASASl l核心主干网提供到核心主干网提供到核心主干网提供到核心主干网提供到所有所有所有所有可能的目的地的可能的目的地的可能的目的地的可能的目的地的可靠的、可靠的、可靠的、可靠的、统统一的、一的、一的、一的、权权威的威的威的威的

16、路由路由路由路由核心主干网核心主干网AS1AS22024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8 8Types of Autonomous Systemsl lSingle-homed ASSingle-homed ASl lOnly one exit point to the outsideOnly one exit point to the outsidel lExample: AS 1, AS 3Example: AS 1, AS 3l lMulti-homed ASMulti-homed ASl lMore than

17、 one exit point to the outsideMore than one exit point to the outsidel lExample: AS 2Example: AS 2l lNontransit ASNontransit ASl lnot allow transit traffic to pass through itnot allow transit traffic to pass through itl lTransit ASTransit ASl lallow transit traffic to pass through itallow transit tr

18、affic to pass through itAS 1AS 1AS 2AS 2R RR RR RAS 3AS 3R R2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9 9IGP vs. EGPl lIGP: Interior Gateway ProtocolIGP: Interior Gateway Protocol（内部网关（内部网关（内部网关（内部网关协议协议/ /域内路由）域内路由）域内路由）域内路由）l lTo be used To be used within an autonomous systemwithin

19、 an autonomous systeml lTo find the best path to the networkTo find the best path to the networkl lIGPIGP具有多具有多具有多具有多样样性，性，性，性，ASAS可自主可自主可自主可自主选择选择l lExampleExample：RIPRIP、OSPFOSPF、IS-ISIS-ISl lEGP: Exterior Gateway ProtocolEGP: Exterior Gateway Protocol（外部网关（外部网关（外部网关（外部网关协议协议/ /域域域域间间路由）路由）路由）路由）l

20、 lTo be used To be used between autonomous systemsbetween autonomous systemsl lTo find the best path to the AS To find the best path to the AS l lASAS间间必必必必须须使用使用使用使用统统一的一的一的一的EGPEGPl lExampleExample：BGP-4BGP-4l lNoteNotel lThe static routing or an IGP could also be used between The static routing o

21、r an IGP could also be used between autonomous systems in some caseautonomous systems in some caseAS1AS1AS2AS2R RR REGPEGPIGPIGP2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1010Routing Protocolsl lRouting protocolsRouting protocolsl lConcept of the routing methodConcept of the routing m

22、ethodl lFeatures and messagesFeatures and messagesl lOperation: discover, topology change, calculateOperation: discover, topology change, calculatel lQuestions and solutionsQuestions and solutionsProtocolProtocolTypeTypeRouting methodRouting methodPopular ver.Popular ver.RIP (RIP (路由信路由信路由信路由信息协议息协议

23、息协议息协议 ) )IGPIGPDistance vector Distance vector routingroutingRIPv1, RIPv2RIPv1, RIPv2OSPF (OSPF (开放开放开放开放最短通路优先最短通路优先最短通路优先最短通路优先) )IGPIGPLink state routingLink state routingOSPFv2OSPFv2BGP (BGP (边界网边界网边界网边界网关协议关协议关协议关协议) )EGPEGPPath vector routingPath vector routingBGP4BGP42024/8/22024/8/2TCP/IP P

24、rotocol SuiteTCP/IP Protocol Suite1111Chapter 11 Routing Protocolsl lInterior and exterior routingl lRIPl lOSPFl lBGP-42024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1212RIPl lRouting Information ProtocolRouting Information Protocol，RIPRIPl lv1v1：RFC 1058RFC 1058，v2v2：RFC 2453RFC 2453，路由信

25、息，路由信息，路由信息，路由信息协议协议 IPLANsMANsWANsICMPIGMPARPRARPNetworkNetworkLayerLayerNetworkNetworkAccess LayerAccess LayerTCPUDPTransportTransportLayerLayerRIPApplicationApplicationLayerLayer520520软件实现层次软件实现层次软件实现层次软件实现层次RIP = RIPv1RIP = RIPv12024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1313Dista

26、nce Vector（距离向量）（距离向量） Routingl l基本原理：每一个路由器基本原理：每一个路由器基本原理：每一个路由器基本原理：每一个路由器周期性地周期性地周期性地周期性地与其与其与其与其邻邻居居居居路由器路由器路由器路由器分享分享分享分享关于关于关于关于整个网整个网整个网整个网络络的路由信息的路由信息的路由信息的路由信息l l“ “我可以通我可以通我可以通我可以通过谁过谁到达哪些网到达哪些网到达哪些网到达哪些网络络” ”l l“ “分享分享分享分享” ”l lWhatWhat the the entireentire routing table routing tablel l

27、WhenWhen at at regularregular intervals intervalsl lWhereWhere only with only with neighborneighborl lTo calculate the routing tableTo calculate the routing tablel l距离向量算法（距离向量算法（距离向量算法（距离向量算法（Bellman-FordBellman-Ford或或或或Ford-FulkersonFord-Fulkerson算法）算法）算法）算法）l l通通通通过过累累累累积积distance vectorsdistance

28、 vectors，来不断更新路由表来不断更新路由表来不断更新路由表来不断更新路由表2 21 13 34 45 56 61 11 12 21 11 11 11 11 11 13 34 46 65 53 32 21 13 3 3 3 3 31 1 1 12 2 2 24 4 4 4 4 4 4 46 65 5 5 52024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1414l l从哪从哪从哪从哪获获得得得得DVDV？l l邻邻居居居居节节点周期性的路由通告点周期性的路由通告点周期性的路由通告点周期性的路由通告报报文中文中文中文中l

29、l什么是什么是什么是什么是DVDV？l l一个一个一个一个有序有序有序有序对对（v v，d d）l lv v：目的网：目的网：目的网：目的网络络l ld d：到：到：到：到该该目的网目的网目的网目的网络络的距离的距离的距离的距离l l准确准确准确准确说说：应该应该是到目的网是到目的网是到目的网是到目的网络络的的的的MetricMetricl l怎么理解怎么理解怎么理解怎么理解DVDV？l l假假假假设设路由器路由器路由器路由器j j从从从从邻邻居居居居i i获获得得得得DVDV（v v，d diviv），表示），表示），表示），表示邻邻居居居居i i告告告告诉诉路由器路由器路由器路由器j j

30、：l l“ “我可以到达某个目的网我可以到达某个目的网我可以到达某个目的网我可以到达某个目的网络络v v，我到那的距离是，我到那的距离是，我到那的距离是，我到那的距离是d diviv” ”l l那么，那么，那么，那么，对对于路由器于路由器于路由器于路由器j j就可以推出以下就可以推出以下就可以推出以下就可以推出以下结论结论：l l“ “我通我通我通我通过过邻邻居居居居i i，可以到达，可以到达，可以到达，可以到达v v，且距离是，且距离是，且距离是，且距离是d divivd dji ji” ”距离向量（距离向量（Distance Vector，DV） j ji iv vd dji jid di

31、v ivv,dv,divivD DNext_hopNext_hopMMvidivdji2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1515RIP Messagel lFormat ( =512 bytes )l lEncapsulation: UDP ( port 520 )CommandCommandVersionVersionIP addressIP addressAll 0sAll 0sAll 0sAll 0sAll 0sAll 0sMetric ( Metric ( hop counthop count ) )Al

32、l 0sAll 0sFamilyFamilyR Re ep pe ea at te ed d2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1616Types of Messagesl lRequest ( Command = 1 ): Request ( Command = 1 ): broadcastbroadcastl l功能：功能：功能：功能：ask forask for a response containing a response containing all or partall or part of the

33、routers of the routers routing tablerouting table. .（“ “问问路路路路 ）l lAll entries ( IP address = 0.0.0.0 )All entries ( IP address = 0.0.0.0 )l lTo be sent by a router that has just To be sent by a router that has just come upcome up（当路由器（当路由器（当路由器（当路由器刚刚接入网接入网接入网接入网络络）l lSpecific entries ( IP address

34、0.0.0.0 )Specific entries ( IP address 0.0.0.0 )l lTo be sent by a router that has some To be sent by a router that has some time-out entriestime-out entries（询问询问超超超超时时表表表表项项）l lResponse ( Command = 2 )Response ( Command = 2 )l lSolicitedSolicited（询问询问响响响响应应）：响）：响）：响）：响应应RequestRequest分分分分组组 l lUnic

35、ast Unicast to the askerto the askerl lTo be sent only in answer to a requestTo be sent only in answer to a requestl lUnsolicitedUnsolicited（非非非非询问询问响响响响应应）：）：）：）：regularregular updates updates（周期更新）（周期更新）（周期更新）（周期更新）l lBroadcast Broadcast to every to every neighborneighborl lTo be sent every 30 s,

36、contain the To be sent every 30 s, contain the entire routing tableentire routing table2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1717Example of RIP Message2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1818RIP Operationl lDiscoveryl lTopology changel lCalculatingl lRIP upd

37、ating algorithmRIP updating algorithmInitializeInitializethe RTthe RTSendSend the the RTRTUpdateUpdatethe RTthe RT收敛收敛收敛收敛? ?SendSendthe RTthe RTper 30 sper 30 sNoNoYesYesFind the Find the changechangeUpdateUpdatethe RTthe RTSend the RTSend the RTon scheduleon scheduleLike discoveryLike discoverySpl

38、it horizons & poison reverseSplit horizons & poison reverseTriggered updateTriggered update阶段阶段阶段阶段1 1阶段阶段阶段阶段2 22024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite1919Initializing the Routing Tablel l初始初始初始初始阶阶段，路由器的路由表中只有段，路由器的路由表中只有段，路由器的路由表中只有段，路由器的路由表中只有直直直直连连网网网网络络的路由的路由的路由的路由l lRFC 105

39、8: metric = 1RFC 1058: metric = 1l lIn most routers: metric = 0In most routers: metric = 0l lExamples of some routers routing tableExamples of some routers routing tablel lCisco routerCisco routerC C 10.1.1.0 is directly connected, FastEthernet0/0 10.1.1.0 is directly connected, FastEthernet0/0l l华为

40、华为 routerrouterDst/Mask Proto Pref Metric Nexthop InterfaceDst/Mask Proto Pref Metric Nexthop Interface10.1.1.0/24 10.1.1.0/24 Direct Direct 0 0 0 0 10.1.1.254 Ethernet0 10.1.1.254 Ethernet0RFC 1058: section 3.6RFC 1058: section 3.62024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2020Exampl

41、e：Initial routing tables in a small autonomous systemDst.Dst.MetricMetricNexthopNexthop2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2121Sending RIP Responses (RFC 1058 Section 3.5) l l什么什么什么什么时时候会候会候会候会“ “Sending RIP Responses”Sending RIP Responses”？l l收到了一个收到了一个收到了一个收到了一个RIP Request RI

42、P Request 对对RIPRIP请请求作响求作响求作响求作响应应l lby the regular routing updateby the regular routing update广播路由表广播路由表广播路由表广播路由表l lby triggered updates by triggered updates 当路由表当路由表当路由表当路由表项项的的的的MetricMetric值发值发生生生生变变化化化化时时l lSource IP addressSource IP addressl lThe IP address of the sending interfaceThe IP addr

43、ess of the sending interfacel lConsider: multiple IP addresses on a single physical Consider: multiple IP addresses on a single physical interfaceinterface（RFC1058 P29RFC1058 P29）l lIn each entryIn each entryl lAddress: host addr, subnet addr, network Address: host addr, subnet addr, network addr, 0

44、.0.0.0addr, 0.0.0.0l lMetric:Metric: from the routing table without change from the routing table without change2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2222RFC 1058: Updating the Routing TableWhen receive a response RIP messageWhen receive a response RIP messagel lFirst to check fo

45、r validityFirst to check for validity（有效性）（有效性）（有效性）（有效性）l lPort number, source IP addressPort number, source IP addressl lThen to process the entries in RIP message one Then to process the entries in RIP message one by oneby one1.1.IgnoreIgnore the entry whose metric, address or unused fields the e

46、ntry whose metric, address or unused fields are are invalidinvalid2.2.UpdateUpdate the entrys the entrys metric = min ( metric + 1, 16 )metric = min ( metric + 1, 16 )3.3.If If the entry address is not in the RT, then the entry address is not in the RT, then addadd it it4.4.Else ifElse if the the ne

47、xt-hopnext-hop in the RT is in the RT is same withsame with source IP source IP address, then address, then replacereplace the route in the RT with this the route in the RT with this entryentry5.5.Else ifElse if the new the new metricmetric is is lower thanlower than the one in the RT, the one in th

48、e RT, then then replacereplace the route in the RT with this entry the route in the RT with this entry2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite23231+1Updating the Routing TableA AB BD DNETNET1 1NETNET6 6C CNETNET3 3NETNET4 4NETNET5 5NETNET2 2E ER RA A路由表路由表路由表路由表RIP Message from RRI

49、P Message from RBBDst.MetricNET11NET31NET43NET52NET62Dst.MetricNET11NET42NET53NET64Nexthop-RERERENET22RERIP Message from RRIP Message from RB B after after incrementincrementDst.MetricNET12NET3NET4NET5NET62433NET32RB5RBR RAAs RIP Messages RIP MessageDst.MetricNET11NET32NET42NET53NET65NET222024/8/220

50、24/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2424Network DiscoveryA AB BC CN1N1N2N2N3N3N4N41 12 21 12 21 12 2N3-10N4-20N1-10N2-20N2-10N3-20路由表：路由表：路由表：路由表：目的网络目的网络下一跳下一跳发送接口发送接口MetricN3N3N1N1N2N2B1B12 21 1A2A21 11 1B2B21 11 1C1C12 21 1N4N4A: (N1, 1) (N2, 1)A: (N1, 1) (N2, 1)B: (N2, 1) (N3, 1)B: (

51、N2, 1) (N3, 1)C:C: (N3, 1) (N4, 1) (N3, 1) (N4, 1)B: (N2, 1) (N3, 1)B: (N2, 1) (N3, 1)N4N4B1B12 22 2N1N1B2B21 12 2A: (N1,1) (N2,1) (N3,2)A: (N1,1) (N2,1) (N3,2)B: (N2,1) (N3,1)B: (N2,1) (N3,1) (N1,2) (N4,2) (N1,2) (N4,2)C:C: (N3,1) (N4,1) (N2,2)(N3,1) (N4,1) (N2,2)B: (N2,1) (N3,1)B: (N2,1) (N3,1) (N

52、1,2) (N4,2) (N1,2) (N4,2)A:(N1,1)(N2,1)(N3,2)(N4,3)A:(N1,1)(N2,1)(N3,2)(N4,3)B: (N2,1) (N3,1)B: (N2,1) (N3,1) (N1,2) (N4,2) (N1,2) (N4,2)C:(N3,1)(N4,1)(N2,2)(N1,2)C:(N3,1)(N4,1)(N2,2)(N1,2)B: (N2,1) (N3,1)B: (N2,1) (N3,1) (N1,2) (N4,2) (N1,2) (N4,2)2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protoco

53、l Suite2525Topology ChangeA AB BC CN1N1N2N2N3N3N4N41 12 21 12 21 12 2N3-10N4-20N1-10N2-2N2-1N3-20N3N3N1N1N2N2B1B12 21 1A2A21 11 1B2B21 1 1 1C1C12 21 1N4N4N4N4B1B12 22 2N1N1B2B21 1 2 2B: (N2,16) (N3,1)B: (N2,16) (N3,1) (N1,16) (N4,2) (N1,16) (N4,2)A: (N1,1) (N2,16)A: (N1,1) (N2,16) (N3,16) (N4,16) (N

54、3,16) (N4,16)0 00 0 C: (N3,1) (N4,1)C: (N3,1) (N4,1) (N2,16) (N1,16) (N2,16) (N1,16) 2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2626Timers in RIPTimersTimersGarbage collectionGarbage collection120 s120 s(for each route)(for each route)ExpirationExpiration180 s180 s(for each route)(for

55、 each route)PeriodicPeriodic30 s30 s(for each router)(for each router)收到更新收到更新收到更新收到更新E = 180sE = 180s收到更新收到更新收到更新收到更新E = 180sE = 180sMetric 16Metric 16G = 120sG = 120s30s30s180s180s删除删除删除删除路由路由路由路由120s120sn n实现中：实现中：实现中：实现中： P P252530s30s G G60s60s控制报文的发送，控制报文的发送，控制报文的发送，控制报文的发送，为防止所有路由器同为防止所有路由器同为

56、防止所有路由器同为防止所有路由器同时更新引起的网络过时更新引起的网络过时更新引起的网络过时更新引起的网络过载，载，载，载，P P 值为值为值为值为2535 2535 秒秒秒秒间的一个随机数。间的一个随机数。间的一个随机数。间的一个随机数。管理路由有效性。管理路由有效性。管理路由有效性。管理路由有效性。每收到某条路由的每收到某条路由的每收到某条路由的每收到某条路由的更新，更新，更新，更新，E E定时器就定时器就定时器就定时器就要复位；若超时，要复位；若超时，要复位；若超时，要复位；若超时，路由跳数设为路由跳数设为路由跳数设为路由跳数设为1616P = 30sP = 30s，发送更新发送更新发送更

57、新发送更新P = 30sP = 30s，发送更新发送更新发送更新发送更新保证邻居路由器能够获知无保证邻居路由器能够获知无保证邻居路由器能够获知无保证邻居路由器能够获知无效路由。无效的路由表项在效路由。无效的路由表项在效路由。无效的路由表项在效路由。无效的路由表项在G TimerG Timer内，继续被路由器定内，继续被路由器定内，继续被路由器定内，继续被路由器定期通告，其期通告，其期通告，其期通告，其MetricMetric16162024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2727Problems with RIPl l

58、Slow convergence（缓慢收慢收敛）l l网内某网内某网内某网内某处发处发生的生的生的生的变变化要化要化要化要传传播到网内的其它地方，播到网内的其它地方，播到网内的其它地方，播到网内的其它地方，这这个个个个过过程是比程是比程是比程是比较较慢的慢的慢的慢的l l原因：原因：原因：原因：l l路由器的路由更新是通路由器的路由更新是通路由器的路由更新是通路由器的路由更新是通过过周期性周期性周期性周期性的的的的RIP Res.RIP Res.来广播的来广播的来广播的来广播的l lInstability（不（不稳定性）定性）l lAn internet running RIP can bec

59、ome An internet running RIP can become unstableunstable routing loop routing loop2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2828Slow ConvergenceNet 1Net 1Net 2Net 2Net n+1Net n+10 seconds0 seconds15 seconds15 secondsn15 secondsn15 secondsl lSolutionSolutionl lTo limit the hop count to

60、 15To limit the hop count to 15l l16 is considered infinity and designates an 16 is considered infinity and designates an unreachable networkunreachable network2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite2929Routing LoopNet 1Net 1Net 2Net 2Net 3Net 3Net1Routing tableRouting tableNet1AR

61、outing tableRouting tableA AB BYou can reach net1 You can reach net1 through me with through me with length 2length 2B can reach net1 ! B can reach net1 ! Great !Great !Hop count Hop count changed !changed !- -1 116162 23 3Hop count Hop count changed !changed !4 4- -B B16161616B: ( net1, 2 )B: ( net

62、1, 2 )A: ( net1, 3 )A: ( net1, 3 )B: ( net1, 4 )B: ( net1, 4 )2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3030Some Remedies for Instabilityl lTriggered update（触（触发更新）更新）l lSplit horizons（水平分割）（水平分割）l lPoison reverse（毒性逆（毒性逆转）l lA variation of split horizonsA variation of split horizons

63、l lHold-down timer（抑制定（抑制定时器，器，not in RFC）None of them are 100% effective !2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3131Triggered Updatel lAn attempt to An attempt to speed upspeed up the convergence the convergencel lIf there are If there are no changesno changes on the network on

64、the networkl lTo send update messages at usual To send update messages at usual 30-s30-s intervals intervalsl lIf there is a If there is a changechangel lTo send update messages almost To send update messages almost immediatelyimmediatelyl lSpecial handlingSpecial handlingl lTo To limit the frequenc

65、ylimit the frequency of triggered updates of triggered updatesl lSet a timer for a random time between 1 and 5 sSet a timer for a random time between 1 and 5 sl lA single update is triggered when the timer expiresA single update is triggered when the timer expiresl lTo To limit the routeslimit the r

66、outes included in triggered updates included in triggered updatesl lAt least those changed routesAt least those changed routes2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3232Split Horizonsl l基本思路：路由器在路由更新基本思路：路由器在路由更新时，要，要根据根据发送接口送接口，选择性性地地组织更新分更新分组l l原原原原则则是：通是：通是：通是：通过过某个某个某个某个接口接口接口

67、接口获获得得得得的路由信息，的路由信息，的路由信息，的路由信息，不再不再不再不再从从从从这这个接口个接口个接口个接口回送回送回送回送过过去去去去2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3333Split HorizonsNet 1Net 1Net 2Net 2Net 3Net 3A AB BNet2Net21 1Net3Net32 2Net1Net11 1RIP messagesRIP messagesNet1Net12 2Net2Net21 1Net3Net31 1RIP messagesRIP messages20

68、24/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3434Poison Reversel l基本操作：基本操作：l l路由更新仍然是将整个路由表路由更新仍然是将整个路由表路由更新仍然是将整个路由表路由更新仍然是将整个路由表发发送出去送出去送出去送出去l l但是，但是，但是，但是，对对于那些从某个接口于那些从某个接口于那些从某个接口于那些从某个接口获获得的路由表得的路由表得的路由表得的路由表项项在在在在通通通通过过同同同同样样的接口更新的接口更新的接口更新的接口更新扩扩散散散散时时，要将其，要将其，要将其，要将其MetricMetri

69、c值值设为设为1616l l意思是：意思是：意思是：意思是：“ “不要使用不要使用不要使用不要使用该该数数数数值值，我所知道的关于，我所知道的关于，我所知道的关于，我所知道的关于这这条路由的信息是来自你的条路由的信息是来自你的条路由的信息是来自你的条路由的信息是来自你的” ”2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3535Poison ReverseNet 1Net 1Net 2Net 2Net 3Net 3A AB BNet2Net21 1Net3Net32 2RIP messagesRIP messagesNet1

70、Net11616Net2Net21616Net3Net31616Net1Net11 1RIP messagesRIP messagesNet2Net21616Net3Net31 1Net1Net11616Net2Net21 1Net3Net31616Net1Net12 2Disadvantage:Disadvantage: Increasing the size of Increasing the size of the routing messages the routing messages2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protoc

71、ol Suite3636问题还没有结束问题还没有结束Net 1Net 1A AB BC CD DE E1.1.Net 1 Net 1 unreachableunreachable, then E sends a , then E sends a triggered triggered updateupdate to its neighbor A to its neighbor A2.2.Then A knows Net 1 is unreachable from E, Then A knows Net 1 is unreachable from E, then sends a triggere

72、d update only to then sends a triggered update only to neighbors B and D because of the neighbors B and D because of the split split horizonshorizons3.3.B and D know Net unreachable from A, then B and D know Net unreachable from A, then send a triggered update only to the neighbor C send a triggered

73、 update only to the neighbor C because of the split horizonsbecause of the split horizons4.4.Assume that C has known about Net 1 from B, Assume that C has known about Net 1 from B, and C sends a regular update about Net 1 is and C sends a regular update about Net 1 is accessible to D before the trig

74、gered update accessible to D before the triggered update has been received. has been received. 5.5.Then D think Net 1 can be reachable through Then D think Net 1 can be reachable through C, so D updates its routing table and informs C, so D updates its routing table and informs A A routing looprouti

75、ng loopX X2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3737Hold-down Timerl l路由器在收到关于某网路由器在收到关于某网路由器在收到关于某网路由器在收到关于某网络络不可达信息后的一段固定不可达信息后的一段固定不可达信息后的一段固定不可达信息后的一段固定时间时间内，内，内，内，忽略任何关于忽略任何关于忽略任何关于忽略任何关于该该网网网网络络的路由信息的路由信息的路由信息的路由信息l lTo prevent update messages from To prevent update message

76、s from reinstating reinstating inaccessible routesinaccessible routesl l算法：算法：算法：算法：l lWhen a router receives an update that indicates a When a router receives an update that indicates a network is unreachable, it starts a hold-down timer ( 180 network is unreachable, it starts a hold-down timer ( 1

77、80 s )s )l lWhile the hold-down timer is running, the router will While the hold-down timer is running, the router will NOTNOT accept any update about the inaccessible route accept any update about the inaccessible route UNLESSUNLESS l lthe update comes from the originator of the previously the upda

78、te comes from the originator of the previously inaccessible updateinaccessible updatel lor from a router reporting a better metric to the or from a router reporting a better metric to the inaccessible networkinaccessible network“ “好消息传得快，坏消息传得慢好消息传得快，坏消息传得慢好消息传得快，坏消息传得慢好消息传得快，坏消息传得慢” ”原因：等待足够长的时间，确保

79、所有路由器都收到坏消息原因：等待足够长的时间，确保所有路由器都收到坏消息原因：等待足够长的时间，确保所有路由器都收到坏消息原因：等待足够长的时间，确保所有路由器都收到坏消息2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3838RIP Version 2l lMessage formatMessage formatl lOperationOperationl lAuthentication: Family = 0xFFFFAuthentication: Family = 0xFFFFl lMulticastingMultica

80、sting: 224.0.0.9: 224.0.0.9l lRIPRIP报报文文文文仅对仅对网网网网络络中的中的中的中的RIPRIP路由器路由器路由器路由器进进行多播行多播行多播行多播l lEncapsulation: UDP ( port 520 )Encapsulation: UDP ( port 520 )CommandCommandVersionVersionIP addressIP addressSubnet MaskSubnet MaskAll 0sAll 0sNext HopNext HopMetricMetricRoute TagRoute TagFamilyFamily202

81、4/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite3939Chapter 11 Routing Protocolsl lInterior and exterior routingl lRIPl lOSPFl lBGP-42024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4040OSPFl lOpen Shortest Path First，OSPFl lv2v2：RFC 2328RFC 2328，开放最短路径，开放最短路径，开放最短路径，开放最短路径优优先先先先 IPL

82、ANsMANsWANsICMPIGMPARPRARPNetworkNetworkLayerLayerNetworkNetworkAccess LayerAccess LayerTCPUDPTransportTransportLayerLayerOSPFApplicationApplicationLayerLayer8989软件实现层次软件实现层次2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4141Link State Routingl lTo To calculatecalculate the routing the ro

83、uting tabletablel lDijkstra algorithmDijkstra algorithm ( SPF ( SPF algorithm )algorithm )l lSPF algorithm to form a SPF algorithm to form a SPF treeSPF treeThe idea The idea ： Every router should Every router should have the have the whole whole picturepicture of the of the internetinternet2024/8/2

84、2024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4242Dijkstra Algorithml lCalculating a tree of shortest paths with the router itself as rootl lDivides the nodes into 2 setsl lTentativeTentative（临时临时性性性性节节点集合）点集合）点集合）点集合）if pass the criteriaif pass the criterial lPermanentPermanent（永久性（永久性（永久性（永久性节

85、节点集合）点集合）点集合）点集合）2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4343Dijkstra AlgorithmB BC CF F7 72 22 22 24 42 23 33 3H HD DE EG G2 26 61 1(2, A)(2, A)(4, B)(4, B)(8, B)(8, B)(5, E)(5, E)(6, E)(6, E)(7, F)(7, F)(9, H)(9, H)节点节点节点节点CostCost路径路径路径路径E EB BF FC CG GD DHH2 2 7 7A A-B-BA-BA-B-

86、E-EA A-G-G4 4A-BA-B-C-C8 8A-B-EA-B-E-F -F5 5A-B-EA-B-E-G-G6 6A-B-E-FA-B-E-F-C-C8 8A-B-E-FA-B-E-F-H-H7 7A-B-E-GA-B-E-G-H-H1010A A9 9A-B-E-F-HA-B-E-F-H-D-DA-B-CA-B-C-D-D11112024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4444什么是链路状态路由协议什么是链路状态路由协议l l什么是什么是路由器的路由器的链路状路状态（Link-state）？）？l l链链路（

87、路（路（路（类类型，度量，型，度量，型，度量，型，度量， up/downup/down）l l通通通通过该链过该链路所路所路所路所连连接的接的接的接的邻邻居居居居链链路路路路标识标识l l“ “邻邻居居居居” ”的的的的类类型取决于型取决于型取决于型取决于链链路的路的路的路的类类型型型型l l链路状路状态路由路由协议要求路由器需要建立其所要求路由器需要建立其所在区域内在区域内每台路由器的所有每台路由器的所有链路状路状态的完整的完整数据数据库所在区域的网所在区域的网络拓扑拓扑l l路由器根据拓扑路由器根据拓扑执行行SPF（最短路径（最短路径优先算先算法），最法），最终以以该路由器路由器为树根，由

88、它出根，由它出发到到其他各个网其他各个网络的路径的路径为树枝的一棵枝的一棵树关键：链路状态关键：链路状态关键：链路状态关键：链路状态到底如何描述？到底如何描述？到底如何描述？到底如何描述？2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4545链路状态路由协议的关键问题链路状态路由协议的关键问题l l如何刻画路由器之如何刻画路由器之间的的邻居关系居关系l l如何建立自己所在区域内每台路由器的所如何建立自己所在区域内每台路由器的所有有链路状路状态的完整数据的完整数据库网网络拓扑拓扑2024/8/22024/8/2TCP/IP P

89、rotocol SuiteTCP/IP Protocol Suite4646路由器间的邻居关系路由器间的邻居关系l l路由器路由器路由器路由器间间的的的的邻邻居关系由居关系由居关系由居关系由连连接它接它接它接它们们的网的网的网的网络类络类型决定型决定型决定型决定l l举举例：例：例：例：l l点到点网点到点网点到点网点到点网络络只只只只连连接两台路由器接两台路由器接两台路由器接两台路由器l l可能会有可能会有可能会有可能会有多台路由器多台路由器多台路由器多台路由器连连在一个在一个在一个在一个以太网以太网以太网以太网上上上上l l这这种网种网种网种网络络被称被称被称被称为为转转接网接网接网接网络

90、络l l转转接网接网接网接网络络的路由器的路由器的路由器的路由器间间的的的的邻邻居关系比居关系比居关系比居关系比较较多多多多链链路状路状路状路状态态开开开开销销大大大大l l转转接网接网接网接网络络上的路由器只与上的路由器只与上的路由器只与上的路由器只与指定路由器指定路由器指定路由器指定路由器建立建立建立建立邻邻居关系居关系居关系居关系RARARBRBLAN2LAN2RDRDLAN1LAN1LAN4LAN4RCRCLAN3LAN3RARARBRBLAN2LAN2RDRDLAN1LAN1LAN4LAN4RCRCLAN3LAN32 22 22 23 31 14 41 12 22024/8/2202

91、4/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4747获取网络拓扑获取网络拓扑l lTo share the knowledge about the internetl lWhatWhat the state of its the state of its link stateslink states ( ( LSA LSA ) )l lWhereWhere with with every other routerevery other router ( ( floodingflooding ) )l lWhenWhen there is a t

92、here is a changechange ( ( event-driven event-driven ) )2 21 13 34 45 56 64 43 35 56 61 11 14 42 210102222A AB BI IJ JC CD DE EF FGG6 6 6 6 6 6 6 6 6 62024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4848OSPF网络类型网络类型1.1.点到点网点到点网络2.2.广播多路广播多路访问网网络l l例如：以太网、令牌例如：以太网、令牌例如：以太网、令牌例如：以太网、令牌环环网网网网

93、3.3.非广播型多路非广播型多路访问（NBMA）网）网络 l l例如：例如：例如：例如：帧帧中中中中继继，X.25X.25Frame RelayX.25Transit networkTransit network（转接（转接（转接（转接网络）：该网络上有多网络）：该网络上有多网络）：该网络上有多网络）：该网络上有多个路由器个路由器个路由器个路由器2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite4949OSPF Link Typesl lOSPF中中一条网一条网络连接接就是就是一条一条链路路1.1.点到点点到点链路（路（Poin

94、t-to-point link）：）：l l连连接两个路由器接两个路由器接两个路由器接两个路由器l l邻邻居居居居邻邻居路由器居路由器居路由器居路由器2.2.转接接链路（路（Link to transit network）：）：l l转转接接接接链链路路路路是是是是连连接有若干路由器的接有若干路由器的接有若干路由器的接有若干路由器的网网网网络络l l每个路由器可能有多个每个路由器可能有多个每个路由器可能有多个每个路由器可能有多个邻邻居居居居节节点点点点l lBroadcastBroadcast（局域网）（局域网）（局域网）（局域网）l lNBMANBMA（非广播型多路（非广播型多路（非广播型多

95、路（非广播型多路访问访问 ）广域网广域网广域网广域网Frame RelayX.25?2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite5050连接：连接：Transit network存在的问题存在的问题l lNN个路由器个路由器个路由器个路由器组组成的成的成的成的转转接网接网接网接网络络，每个路由器都有（，每个路由器都有（，每个路由器都有（，每个路由器都有（NN1 1）个）个）个）个邻邻居路由器（即居路由器（即居路由器（即居路由器（即N-1N-1条条条条连连接）接）接）接）l l这这种种种种邻邻居居居居连连接关系：接关系：接关

96、系：接关系：低效、且不低效、且不低效、且不低效、且不现实现实l l解决思路：解决思路：解决思路：解决思路：将将将将转转接接接接网网网网络络本身也本身也本身也本身也抽象抽象抽象抽象成成成成为为一个一个一个一个路由器（路由器（路由器（路由器（节节点）点）点）点）l l具体方案：具体方案：具体方案：具体方案：选择选择一个一个一个一个指定路由器指定路由器指定路由器指定路由器来来来来充当充当充当充当转转接网接网接网接网络络抽象成抽象成抽象成抽象成为为的的的的路由器路由器路由器路由器节点2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite51

97、51在在Transit network中存在：中存在： DR(指定路由器指定路由器)和和BDR(备份指定路由器备份指定路由器)l lDesignated router & backup DR (Designated router & backup DR (指定路由器指定路由器指定路由器指定路由器 & & 备备份指定路由器份指定路由器份指定路由器份指定路由器) )l l在在在在转转接网接网接网接网络络中，所有一般路由器中，所有一般路由器中，所有一般路由器中，所有一般路由器只与只与只与只与该该网网网网络络中的中的中的中的DR/BDRDR/BDR建立建立建立建立邻邻居关系居关系居关系居关系！l l指

98、定路由器的功能：指定路由器的功能：指定路由器的功能：指定路由器的功能：l l与与与与该转该转接网接网接网接网络络中的其它路由器建立毗中的其它路由器建立毗中的其它路由器建立毗中的其它路由器建立毗邻邻关系关系关系关系l l作作作作为该转为该转接网接网接网接网络络的的的的“ “发发言人言人言人言人” ” l l通告通告通告通告转转接网接网接网接网络络的网的网的网的网络络地址地址地址地址l l是是是是转转接网接网接网接网络络中中中中LSALSA的集中的集中的集中的集中处处理点理点理点理点l lPurposePurpose：减少：减少：减少：减少Transit networkTransit networ

99、k的路由开的路由开的路由开的路由开销销l lReduce the number of adjacencies required on a broadcast or Reduce the number of adjacencies required on a broadcast or NBMA networkNBMA networkl lReduce the amount of routing protocol traffic and the size of Reduce the amount of routing protocol traffic and the size of the lin

100、k-state databasethe link-state database2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite5252OSPF Link Types2.2.转接接链路（路（Link to transit network）：）：l l邻邻居居居居指定路由器指定路由器指定路由器指定路由器3.3.残残桩链路（路（Link to stub network）：）：l l只只只只连连接到某一个路由器的网接到某一个路由器的网接到某一个路由器的网接到某一个路由器的网络络l l邻邻居居居居网网网网络络4.4.虚虚链路（路（Vir

101、tual link）l l两个路由器之两个路由器之两个路由器之两个路由器之间链间链路断开路断开路断开路断开时时，人工，人工，人工，人工创创建一条建一条建一条建一条更更更更长长路径的虚路径的虚路径的虚路径的虚拟链拟链路（路（路（路（经过经过多个路由器）多个路由器）多个路由器）多个路由器）Area 0Area 0Area 2Area 2Area 1Area 1Area 3Area 3将网络抽象将网络抽象将网络抽象将网络抽象成成成成1 1个节点个节点个节点个节点（路由器）（路由器）（路由器）（路由器）指定路由器指定路由器指定路由器指定路由器2024/8/22024/8/2TCP/IP Protoco

102、l SuiteTCP/IP Protocol Suite5353关键：链路状态到底如何描述？关键：链路状态到底如何描述？2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite5454举例举例链路类型链路类型链路类型链路类型链路标识链路标识链路标识链路标识链路数据链路数据链路数据链路数据点到点点到点点到点点到点10.24.8.1010.24.8.101 1点到点点到点点到点点到点10.24.9.1110.24.9.112 2残桩残桩残桩残桩10.24.7.010.24.7.0255.255.255.0255.255.255.02024

103、/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite5555平面路由平面路由 VS. 分层路由分层路由l lRIPRIP是一种典型的平面是一种典型的平面是一种典型的平面是一种典型的平面路由路由路由路由协议协议，即，即，即，即ASAS内的所内的所内的所内的所有路由器的地位都是平有路由器的地位都是平有路由器的地位都是平有路由器的地位都是平等的，等的，等的，等的，执执行的路由功能行的路由功能行的路由功能行的路由功能都相同都相同都相同都相同l lOSPFOSPF是一种分是一种分是一种分是一种分层层路由：路由：路由：路由：l lAS AS 划分成若

104、干区域划分成若干区域划分成若干区域划分成若干区域（AreaArea）l l路由器在路由功能上出路由器在路由功能上出路由器在路由功能上出路由器在路由功能上出现现分工分工分工分工Area 1Area 1Area 2Area 2Area 0 (Area 0 (backbonebackbone) )Autonomous SystemAutonomous SystemToTootherotherASsASs2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite5656Splitting the AS into Areas!l l分区域理由：大

105、分区域理由：大分区域理由：大分区域理由：大规规模的网模的网模的网模的网络络会会会会给给OSPFOSPF路由器路由器路由器路由器带带来来来来沉重的沉重的沉重的沉重的负负担担担担l l链链路状路状路状路状态态的改的改的改的改变变，可能会使路由器，可能会使路由器，可能会使路由器，可能会使路由器经经常常常常执执行行行行SPFSPF（最短（最短（最短（最短路径路径路径路径优优先）算法先）算法先）算法先）算法l l路由表膨路由表膨路由表膨路由表膨胀胀l l每个路由器需要保持的完整网每个路由器需要保持的完整网每个路由器需要保持的完整网每个路由器需要保持的完整网络络拓扑（拓扑（拓扑（拓扑（链链路数据路数据路数

106、据路数据库库）l lOSPFOSPF将网将网将网将网络络划分成若干划分成若干划分成若干划分成若干较较小的区域小的区域小的区域小的区域l l区域内的路由器区域内的路由器区域内的路由器区域内的路由器执执行行行行SPFSPF算法算法算法算法l l区域区域区域区域间间：交交交交换汇总换汇总后的路由信息，而不是后的路由信息，而不是后的路由信息，而不是后的路由信息，而不是详细详细的路由的路由的路由的路由信息信息信息信息2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite5757Splitting the AS into Areas!l lAd

107、vantagesAdvantagesl lReduce Reduce LSALSA (link state advertisements ) (link state advertisements ) overheadoverheadl lReduce frequency of SPF calculationsReduce frequency of SPF calculationsl lSmaller routing tablesSmaller routing tablesArea 1Area 1Area 0Area 0Area 2Area 22024/8/22024/8/2TCP/IP Pro

108、tocol SuiteTCP/IP Protocol Suite5858Splitting the AS into Areas!l lAS中存在两种中存在两种层次的路由次的路由l lIntraIntra-area routing-area routing（区域内路由）（区域内路由）（区域内路由）（区域内路由）l l区域内路由器区域内路由器区域内路由器区域内路由器执执行行行行链链路状路状路状路状态态路由算法路由算法路由算法路由算法l lInterInter-area routing-area routing（区域（区域（区域（区域间间路由）路由）路由）路由）l l由一些特殊路由器由一些特殊路由器

109、由一些特殊路由器由一些特殊路由器负责负责将某一区域的将某一区域的将某一区域的将某一区域的路由路由路由路由汇总汇总之后之后之后之后向其它区域更新向其它区域更新向其它区域更新向其它区域更新2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite5959OSPF Areal lAreaArea：包含在：包含在：包含在：包含在ASAS中的一些网中的一些网中的一些网中的一些网络络、主机和路由器、主机和路由器、主机和路由器、主机和路由器的集合的集合的集合的集合l l类类型：型：型：型：标标准区域、主干区域（准区域、主干区域（准区域、主干区域（准区

110、域、主干区域（ Backbone area Backbone area ）、残）、残）、残）、残桩桩区域（区域（区域（区域（Stub areaStub area）Autonomous SystemAutonomous SystemArea 1Area 1Area 2Area 2Area 0 (backbone)Area 0 (backbone)ToTootherotherASsASs2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6060OSPF区域类型区域类型l l区域的区域的区域的区域的类类型型型型：决定决定决定决定了了了

111、了该该区域内路由器所能接收的区域内路由器所能接收的区域内路由器所能接收的区域内路由器所能接收的路由信息的路由信息的路由信息的路由信息的类类型型型型l l标标准区域：区域内路由器能准区域：区域内路由器能准区域：区域内路由器能准区域：区域内路由器能够够接收接收接收接收链链路状路状路状路状态态更新更新更新更新和和和和路由路由路由路由归纳归纳（区（区（区（区间间路由）路由）路由）路由）l l主干区域：具有主干区域：具有主干区域：具有主干区域：具有标标准区域的一切属性，特殊之准区域的一切属性，特殊之准区域的一切属性，特殊之准区域的一切属性，特殊之处处在于：它需要在于：它需要在于：它需要在于：它需要负责负

112、责互互互互连连其它所有其它所有其它所有其它所有区域区域区域区域l l残残残残桩桩区域：区域：区域：区域：这这种区域种区域种区域种区域不接收不接收不接收不接收那些那些那些那些自治系自治系自治系自治系统统以外以外以外以外的的的的路由信息路由信息路由信息路由信息l l如果需要如果需要如果需要如果需要发发送分送分送分送分组组到自治系到自治系到自治系到自治系统统之外的网之外的网之外的网之外的网络络，区域内路，区域内路，区域内路，区域内路由器将使用由器将使用由器将使用由器将使用默默默默认认路由路由路由路由2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protoco

113、l Suite6161Area Area 2 2Area 3Area 3Area 0Area 0Area Area 1 1Area 0Area 0l lBackbone areal lBe responsible for distributing routing Be responsible for distributing routing information information between non-backbone areasbetween non-backbone areasl lMust be contiguousl lNOT need be physically conti

114、guousNOT need be physically contiguousl lVirtual linkVirtual linkArea 0： Backbone areaArea 0Area 0Area 2Area 2Area 1Area 1Area 3Area 32024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6262OSPF Router TypesAutonomous SystemAutonomous SystemArea 1Area 1Area 2Area 2Area 0 (backbone)Area 0 (back

115、bone)To otherTo otherASASABRABR，BRBRIRIRASBRASBR，BRBRIRIR，BRBRl lInternal routerInternal router（内部路由器）（内部路由器）（内部路由器）（内部路由器）, IR, IRl lBackbone routerBackbone router（主干路由器）（主干路由器）（主干路由器）（主干路由器）, BR, BRl lArea Border RouterArea Border Router（区域边界路由器）（区域边界路由器）（区域边界路由器）（区域边界路由器）, ABR, ABRl lAS Border Ro

116、uterAS Border Router（ ASAS边界路由器）边界路由器）边界路由器）边界路由器）, ASBR, ASBR2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6363OSPF Router Typesl l内部路由器内部路由器内部路由器内部路由器 (IR)(IR)l l路由器所有接口都在同一个区域内路由器所有接口都在同一个区域内路由器所有接口都在同一个区域内路由器所有接口都在同一个区域内l l同一区域同一区域同一区域同一区域IRIR具有相同的具有相同的具有相同的具有相同的链链路状路状路状路状态库态库l l主干路由

117、器主干路由器主干路由器主干路由器 (BR)(BR)l l该该路由器至少有一个接口路由器至少有一个接口路由器至少有一个接口路由器至少有一个接口连连接到主干区域接到主干区域接到主干区域接到主干区域(Area0)(Area0)Autonomous SystemAutonomous SystemArea 1Area 1Area 2Area 2Area 0 (backbone)Area 0 (backbone)IRIRIRIR，BRBRBRBR，ABRABR2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6464OSPF Router

118、Typesl l区域区域区域区域边边界路由器界路由器界路由器界路由器(ABR)(ABR)l l路由器的接口分路由器的接口分路由器的接口分路由器的接口分别连别连接不同区域接不同区域接不同区域接不同区域l lABRABR为为其其其其连连接的每个区域接的每个区域接的每个区域接的每个区域维护维护着着着着单单独的独的独的独的链链路状路状路状路状态态数据数据数据数据库库l lABRABR从其从其从其从其连连接的区域接的区域接的区域接的区域链链路状路状路状路状态态数据数据数据数据库库中中中中归纳归纳路由，将路由，将路由，将路由，将汇总汇总路由路由路由路由发发布到主干区域，而主干区域中的布到主干区域，而主干区

119、域中的布到主干区域，而主干区域中的布到主干区域，而主干区域中的ABRABR再将再将再将再将其其其其扩扩散到其它区域散到其它区域散到其它区域散到其它区域Autonomous SystemAutonomous SystemArea 1Area 1Area 2Area 2Area 0 (backbone)Area 0 (backbone)ABRABR2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6565OSPF Router Typesl lAS边界路由器界路由器(ASBR)l l该该路由器至少有路由器至少有路由器至少有路由器至少

120、有1 1个接口个接口个接口个接口连连接另一个自治系接另一个自治系接另一个自治系接另一个自治系统统l lASBRASBR向自治系向自治系向自治系向自治系统统通告自治系通告自治系通告自治系通告自治系统统以外的路由以外的路由以外的路由以外的路由Autonomous SystemAutonomous SystemArea 1Area 1Area 2Area 2Area 0 (backbone)Area 0 (backbone)ASBRASBR，BRBR2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6666OSPF LSA (OSPF

121、 LSA (link state advertisementslink state advertisements ) Types ) Typesl lIntra-areaIntra-areal lType 1: RouterLSAType 1: RouterLSAl lType 2: NetworkLSAType 2: NetworkLSAl lInter-areaInter-areal lType 3: Summary link to networkLSAType 3: Summary link to networkLSAl lType 4: Summary link to boundary

122、 routerType 4: Summary link to boundary routerLSALSAl lExternalExternall lType 5: ASexternalLSAType 5: ASexternalLSA2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6767Intra-area LSAsl lType 1: RouterLSA(路由器路由器链路通告路通告)：在：在本区域内本区域内发布所有布所有邻居居及其及其对应链路路的信息的信息l lOriginated by all routersOrigina

123、ted by all routersl lDescribes the collected states of the Describes the collected states of the routers interfaces to an arearouters interfaces to an areal lFlooded throughout a single area onlyFlooded throughout a single area only2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6868Intra-

124、area LSAsl lType 2: NetworkLSA(Type 2: NetworkLSA(网网网网络链络链路通告路通告路通告路通告) )：由：由：由：由DRDR在在在在本区域内本区域内本区域内本区域内发发布其所在布其所在布其所在布其所在Transit networkTransit network上其它路由上其它路由上其它路由上其它路由器信息器信息器信息器信息l lOriginated for broadcast and NBMA networks Originated for broadcast and NBMA networks by the DRby the DRl lConta

125、ins the list of routers connected to the Contains the list of routers connected to the networknetworkl lFlooded throughout a single area onlyFlooded throughout a single area only2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite6969Inter-area LSAsl lType 3: SummaryLSA(Type 3: SummaryLSA(汇总链汇

126、总链路到网路到网路到网路到网络络) )：由：由：由：由ABRABR产产生，在其生，在其生，在其生，在其所属的每个区域所属的每个区域所属的每个区域所属的每个区域里中里中里中里中发发布布布布到达其它到达其它到达其它到达其它区域区域区域区域的路由信息的路由信息的路由信息的路由信息l lOriginated by ABRsOriginated by ABRsl lDescribes routes to networks outside the areaDescribes routes to networks outside the areal lFlooded throughout the LSAs

127、associated areaFlooded throughout the LSAs associated area2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7070举例举例当子网当子网当子网当子网1 1恢复连通以恢复连通以恢复连通以恢复连通以后，在子网后，在子网后，在子网后，在子网4 4中收到中收到中收到中收到的链路状态通告的链路状态通告的链路状态通告的链路状态通告2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7171Inter-area LSAsl

128、 lType 4: SummaryLSA (Type 4: SummaryLSA (汇总链汇总链路到路到路到路到ASBR) ASBR) ：由由由由ABRABR产产生，在本生，在本生，在本生，在本ASAS内的内的内的内的所有区域中所有区域中所有区域中所有区域中发发布到达布到达布到达布到达ASBRASBR的路径信息的路径信息的路径信息的路径信息l lOriginated by ABRsOriginated by ABRsl lDescribes routes to ASBRsDescribes routes to ASBRsl lFlooded throughout the LSAs associ

129、ated areaFlooded throughout the LSAs associated area2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7272External LSAsl lType 5: ASexternalLSAType 5: ASexternalLSA：由：由：由：由ASBRASBR产产生，在生，在生，在生，在本本本本ASAS内的某些区域内的某些区域内的某些区域内的某些区域中中中中发发布到达布到达布到达布到达ASAS以外网以外网以外网以外网络络的路的路的路的路径信息径信息径信息径信息l lOrigina

130、ted by ASBROriginated by ASBRl lDescribes a route to a destination in another Describes a route to a destination in another ASASl lFlooded throughout the AS except the stub Flooded throughout the AS except the stub areaarea2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7373OSPF LSA Exampl

131、el l哪些路由器会哪些路由器会哪些路由器会哪些路由器会发发送送送送RouterLSARouterLSA？l lSolutionSolutionl lAll routers advertise router link LSAs. All routers advertise router link LSAs. l lR1 has two links, Net1 and Net2.R1 has two links, Net1 and Net2.l lR2 has one link, Net2 in this AS. R2 has one link, Net2 in this AS. l lR3 h

132、as two links, Net2 and Net3R3 has two links, Net2 and Net32024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7474OSPF LSA Examplel l哪些路由器哪些路由器哪些路由器哪些路由器发发送的送的送的送的LSALSA中含有网中含有网中含有网中含有网络络信息？信息？信息？信息？l lSolutionSolutionl lAll three network must advertise network links:All three network must adv

133、ertise network links:l lR1R1通告通告通告通告Net1Net1l lBecause it is the only router and therefore the designated router.Because it is the only router and therefore the designated router.l lNet2Net2可能由可能由可能由可能由 R1, R2, R3R1, R2, R3中任意一个通告中任意一个通告中任意一个通告中任意一个通告l ldepending on which one is chosen as the design

134、ated router. depending on which one is chosen as the designated router. l lR3R3通告通告通告通告Net3 is doneNet3 is donel lbecause it is the only router and therefore the designated router. because it is the only router and therefore the designated router. 2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol

135、 Suite7575LSA的发送方式的发送方式l lLSA采用采用组播播发送，所有送，所有OSPF路由器的路由器的组播地址都是：播地址都是：224.0.0.5l l在在转接网接网络（广播多路（广播多路访问网网络、NBMA）网）网络中，中，DR和和BDR还具有自己的具有自己的组播地址：播地址：224.0.0.6l l转转接网接网接网接网络络中，由于一般路由器只与中，由于一般路由器只与中，由于一般路由器只与中，由于一般路由器只与DR/BDRDR/BDR存存存存在在在在邻邻居关系，所以其居关系，所以其居关系，所以其居关系，所以其LSALSA将将将将发发送到送到送到送到224.0.0.224.0.0.

136、6 62024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7676OSPF LSA Example1Area 1Area 1DRDRArea 0Area 0Area 2Area 2(Stub)(Stub)AS 10AS 10AS 20AS 20Type 2Type 2Type 2Type 2Type 2Type 2Type 3Type 3(Area 1)(Area 1)Type 5Type 5(AS 20)(AS 20)Type 5Type 5(AS 20)(AS 20)Type 5Type 5(AS 20)(AS 20)Type

137、 5Type 5(AS 20)(AS 20)Type 3Type 3(Area 1)(Area 1)Type 5Type 5(AS 20)(AS 20)Type 3Type 3(Area 1)(Area 1)Type 1Type 1(Area 1)(Area 1)Type 1Type 1(Area 0)(Area 0)Type 1Type 1(Area 0)(Area 0)Type 3Type 3(Area 0)(Area 0)Type 3Type 3(Area 0)(Area 0)Type 3Type 3(Area 0)(Area 0)DefaultDefaultType 5Type 5(A

138、S 20)(AS 20)Type 5Type 5(AS 20)(AS 20)Type 1Type 1(Area 1)(Area 1)Type 1Type 1(Area 1)(Area 1)2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7777OSPF LSA Example2l l两次拓扑两次拓扑两次拓扑两次拓扑变变化化化化l l子网子网子网子网4 4变为变为不可达不可达不可达不可达l l子网子网子网子网4 4变为变为可达，可达，可达，可达，R6R6变为变为ASBRASBR，并且，并且，并且，并且产产生生生生ASAS外部路由

139、外部路由外部路由外部路由子网子网1Area 1子网子网3.211.213.235.234.212R1R2R4R5.224.223子网子网2Area 2 (stub area)Area 0R6.226AS 2010.2.0.0/16AS 1010.1.0.0/16子网子网4R3子网子网子网子网1 110.1.1.0/2410.1.1.0/24子网子网子网子网2 210.1.2.0/2410.1.2.0/24子网子网子网子网3 310.1.3.0/2410.1.3.0/24子网子网子网子网4 410.1.4.0/2510.1.4.0/252024/8/22024/8/2TCP/IP Protoco

140、l SuiteTCP/IP Protocol Suite7878第第1次拓扑变化产生的次拓扑变化产生的LSAl l子网子网子网子网1 1：l l类类型型型型1 1（路由器路由器路由器路由器链链链链路路路路）LSALSA，由内部路由器，由内部路由器，由内部路由器，由内部路由器R1R1始始始始发发，在区域，在区域，在区域，在区域1 1中洪中洪中洪中洪泛泛泛泛l l内容：内容：内容：内容：R1R1的的的的链链路数目只有路数目只有路数目只有路数目只有1 1条条条条链链路，即路，即路，即路，即连连接子网接子网接子网接子网1 1的的的的链链路路路路l l数目：数目：数目：数目：2 2个个个个LSALSAl

141、 l子网子网子网子网2 2：l l类类型型型型3 3（汇总链汇总链路到网路到网路到网路到网络络）LSALSA，由区域，由区域，由区域，由区域边边界路由器界路由器界路由器界路由器R3R3始始始始发发，在，在，在，在区域区域区域区域0 0中洪泛中洪泛中洪泛中洪泛l l内容：通告内容：通告内容：通告内容：通告连连接子网接子网接子网接子网4 4的的的的链链路，其路，其路，其路，其MetricMetric值值“ “无无无无穷穷大大大大” ”l l数目：数目：数目：数目：2 2个个个个LSALSAl l子网子网子网子网3 3：l l类类型型型型3 3（汇总链汇总链路到网路到网路到网路到网络络）LASLAS

142、，它由区域，它由区域，它由区域，它由区域边边界路由器界路由器界路由器界路由器R4R4始始始始发发，在区域在区域在区域在区域3 3中洪泛中洪泛中洪泛中洪泛l l内容：通告内容：通告内容：通告内容：通告连连接子网接子网接子网接子网4 4的的的的链链路，其路，其路，其路，其MetricMetric值值“ “无无无无穷穷大大大大” ”l l数目：数目：数目：数目：1 1个个个个LSALSA拓扑变化前，拓扑变化前，拓扑变化前，拓扑变化前，R1R1路由器链路路由器链路路由器链路路由器链路LSALSA包含两条链路：包含两条链路：包含两条链路：包含两条链路：1 1）残桩链路，）残桩链路，）残桩链路，）残桩链路

143、，2 2）转接链路）转接链路）转接链路）转接链路2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite7979第第2次拓扑变化产生的次拓扑变化产生的LSAl l子网子网子网子网1 1：l l类类型型型型1 1（路由器路由器路由器路由器链链链链路路路路LSALSA）LSALSA，由内部路由器，由内部路由器，由内部路由器，由内部路由器R1R1始始始始发发，在区域，在区域，在区域，在区域1 1中洪泛中洪泛中洪泛中洪泛l l内容：内容：内容：内容：R1R1的的的的链链路数目有路数目有路数目有路数目有2 2条条条条链链路：路：路：路：连连接子

144、网接子网接子网接子网1 1的的的的链链路和路和路和路和连连接子网接子网接子网接子网4 4的的的的链链路路路路l l数目：数目：数目：数目：2 2个个个个LSALSAl l类类型型型型4 4（汇总链汇总链路到路到路到路到ASBRASBR）LSALSA，由，由，由，由区域区域区域区域边边界路由器界路由器界路由器界路由器R3R3始始始始发发，在区域，在区域，在区域，在区域1 1中洪泛中洪泛中洪泛中洪泛l l内容：本自治系内容：本自治系内容：本自治系内容：本自治系统统的自治系的自治系的自治系的自治系统边统边界路由器界路由器界路由器界路由器R6R6l l数目：数目：数目：数目：1 1个个个个l l类类型

145、型型型5 5（外部（外部（外部（外部链链路）路）路）路）LSALSA，由，由，由，由R6R6始始始始发发，区域区域区域区域边边界路由器界路由器界路由器界路由器R3R3转发转发，在区域，在区域，在区域，在区域1 1中洪泛中洪泛中洪泛中洪泛l l内容：外部自治系内容：外部自治系内容：外部自治系内容：外部自治系统统路由器路由器路由器路由器l l数目：数目：数目：数目：1 1个个个个l l子网子网子网子网2 2：l l类类型型型型1 1（路由器路由器路由器路由器链链链链路路路路LSALSA）LSALSA，由内部路由器，由内部路由器，由内部路由器，由内部路由器R6R6始始始始发发，在区域，在区域，在区域

146、，在区域0 0中洪泛中洪泛中洪泛中洪泛l l内容：内容：内容：内容：R6R6的的的的链链路数目路数目路数目路数目有有有有1 1条条条条链链路路路路l l数目：数目：数目：数目：1 1个个个个LSALSAl l类类型型型型3 3（汇总链汇总链路到网路到网路到网路到网络络）LASLAS，由区域，由区域，由区域，由区域边边界路由器界路由器界路由器界路由器R3R3始始始始发发，在区域，在区域，在区域，在区域0 0中洪泛中洪泛中洪泛中洪泛l l内容：通告内容：通告内容：通告内容：通告连连接子网接子网接子网接子网4 4的的的的链链路路路路l l数目：数目：数目：数目：2 2个个个个LSALSAl l类类型

147、型型型5 5（外部（外部（外部（外部链链路）路）路）路）LSALSA，由，由，由，由R6R6始始始始发发，在区域，在区域，在区域，在区域0 0中洪泛中洪泛中洪泛中洪泛l l内容：外部自治系内容：外部自治系内容：外部自治系内容：外部自治系统统路由器路由器路由器路由器l l数目：数目：数目：数目：1 1个个个个l l子网子网子网子网3 3：l l类类型型型型3 3（汇总链汇总链路到网路到网路到网路到网络络）LASLAS，由区域，由区域，由区域，由区域边边界路由器界路由器界路由器界路由器R4R4始始始始发发，在区域，在区域，在区域，在区域2 2中洪泛中洪泛中洪泛中洪泛l l内容：通告内容：通告内容：

148、通告内容：通告连连接子网接子网接子网接子网4 4的的的的链链路路路路l l数目：数目：数目：数目：1 1个个个个LSALSA2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8080OSPF中的数据库中的数据库l lAdjacency databaseAdjacency databasel lAll the All the neighborsneighbors to which a router has to which a router has established bidirectional communicationes

149、tablished bidirectional communicationl lUnique for each routerUnique for each routerl lLink-state databaseLink-state databasel lThe relationship between each router and its The relationship between each router and its neighbors neighbors l lAll routers within an area have identical link-All routers

150、within an area have identical link-state databasesstate databasesl lForwarding database ( routing table )Forwarding database ( routing table )l lThe routes generated when an SPF algorithm is The routes generated when an SPF algorithm is run on the link-state databaserun on the link-state databasel l

151、The routing table on each router is uniqueThe routing table on each router is unique通过通过通过通过路由器路由器路由器路由器LSALSA和和和和网络网络网络网络LSALSA构成链路状态数据库构成链路状态数据库构成链路状态数据库构成链路状态数据库2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8181OSPF Packetsl lFormatl lMulticasting: 224.0.0.5, 224.0.0.6l lEncapsulation

152、: IP ( protocol 89 )VersionVersionTypeTypeRouter IDRouter IDArea IDArea IDPacket LengthPacket LengthAuthenticationAuthenticationAuthentication TypeAuthentication TypeChecksumChecksumH He ea ad de er rOSPF Packet DataOSPF Packet Data2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8282Packet

153、 Types1: Hello packet1: Hello packetl lA 64-byte packet sent A 64-byte packet sent periodicallyperiodically to keep a link “alive” to keep a link “alive”2: DBD ( Database Description )2: DBD ( Database Description )l lSummary contents of a routers link-state database sent to a Summary contents of a

154、routers link-state database sent to a newly discovered neighbornewly discovered neighbor3: LSR ( Link-State Request )3: LSR ( Link-State Request )l lRequests more specific information about a link from a Requests more specific information about a link from a neighbors link-state databaseneighbors li

155、nk-state database4: LSU ( Link-State Update, LSA )4: LSU ( Link-State Update, LSA )l lTransports LSAs to neighbor routers, a reply to an LSRTransports LSAs to neighbor routers, a reply to an LSR5: LSAck ( Link-State Acknowledgement )5: LSAck ( Link-State Acknowledgement )l lAck receipt of a LSA; OSP

156、Fs routing updates are connection-Ack receipt of a LSA; OSPFs routing updates are connection-orientedoriented2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8383Hello packet2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8484Link state update packetl lLSA header2024/8/22024/8/2TC

157、P/IP Protocol SuiteTCP/IP Protocol Suite8585Router link LSA2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8686OSPF Operation1. Establish router adjacencies(1. Establish router adjacencies(毗毗毗毗邻邻) )l lDone with the exchange of HellosDone with the exchange of Hellos2. Elect the DR / BDR ( i

158、f necessary )2. Elect the DR / BDR ( if necessary )l lDone on multiaccess network onlyDone on multiaccess network only3. Discover routes3. Discover routesl lDone in the ExStart and Exchange statesDone in the ExStart and Exchange states4. Select appropriate routes4. Select appropriate routesl lDone t

159、hrough the calculation of SPF algorithmDone through the calculation of SPF algorithm5. Maintain routing information5. Maintain routing informationl lDone through the regular exchange of HellosDone through the regular exchange of Hellos2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8787OSP

160、F Statesl lDownDown: Not exchange information with any neighbor: Not exchange information with any neighborl lInitInit: When an interface receives its first Hello: When an interface receives its first Hellol l2-way2-way: When it sees itself in a neighbors Hello: When it sees itself in a neighbors He

161、llol lExStartExStart: Two neighbors use Hello to negotiate who : Two neighbors use Hello to negotiate who is the “master” and who is the “slave”is the “master” and who is the “slave”l lExchangeExchange: Neighbors use DBD to send each other : Neighbors use DBD to send each other a a summary of summar

162、y of their their link-state database link-state databasel lLoadingLoading: Uses LSR, LSU, and LSAck to get : Uses LSR, LSU, and LSAck to get complete link-state informationcomplete link-state informationl lFullFull: Neighbors are fully adjacent: Neighbors are fully adjacent2024/8/22024/8/2TCP/IP Pro

163、tocol SuiteTCP/IP Protocol Suite8888Step 1. Establish router adjacenciesI am router ID 172.68.5.1 and I see no oneDown State172.68.5.1/24E0172.68.5.2/24E1ABRouter B 邻接表邻接表172.68.5.1/24, int E1Init StateI am router ID 172.68.5.2, and I see 172.68.5.1Router A 邻接表邻接表172.68.5.2/24, int E0Two-way StateHe

164、llo3954743907071339547439070713Hello39547439070713395474390707132024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite8989Step 3. Discover routesHello PacketHello PacketABExstartExchangeLoadingFullHello PacketHello PacketDBD PacketDBD PacketDBD PacketDBD PacketLSAck PacketLSAck PacketLSAck Packe

165、tLSAck PacketLSR PacketLSR PacketLSU PacketLSU PacketLSAck PacketLSAck Packet2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9090小结：小结：RIP vs. OSPFl l对网网络拓扑的了解拓扑的了解l l路由路由计算方法算方法l l路由更新方式路由更新方式l l路由更新内容路由更新内容l l收收敛速度速度l l适用适用环境境2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9191

166、Chapter 11 Routing Protocolsl lInterior and exterior routingl lRIPl lOSPFl lBGP-42024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9292BGP-4l lBorder Gateway Protocol，BGPl lv4v4：RFC 1771RFC 1771，RFC 1772RFC 1772，边边界网关界网关界网关界网关协议协议 IPLANsMANsWANsICMPIGMPARPRARPNetworkNetworkLayerLayerNetworkN

167、etworkAccess LayerAccess LayerTCPUDPTransportTransportLayerLayerBGP-4ApplicationApplicationLayerLayer179179软件实现层次软件实现层次2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9393BGPl lBGP是自治系是自治系统之之间的路由的路由协议l l为什么什么DV、LS不适合自治系不适合自治系统之之间的路由的路由协议？l l互互互互联联网（多个网（多个网（多个网（多个ASAS组组成）成）成）成）规规模大，路由模大，路由模

168、大，路由模大，路由计计算量大算量大算量大算量大l l最小跳数的路由不一定最小跳数的路由不一定最小跳数的路由不一定最小跳数的路由不一定优优先先先先选择选择策略路由策略路由策略路由策略路由AS10AS10OSPFOSPFAS21AS21RIPRIPAS32AS32OSPFOSPFBGPBGPBGPBGPBGPBGPISP2ISP2ISP1ISP1AS32AS32可以是：可以是：可以是：可以是： Nontransit ASNontransit AS Transit ASTransit AS2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Sui

169、te9494从从BGP的观点来看互联网的观点来看互联网AS1AS10 0AS2AS20 0AS3AS30 0AS5AS50 0AS4AS40 0到AS60的路由是：AS20、 AS10、AS30AS6AS60 02024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9595Path Vector Routing（路径向量路（路径向量路由选择）由选择）l l思想与距离向量路由思想与距离向量路由选择相似：相似：l l每个每个每个每个ASAS中指定一些中指定一些中指定一些中指定一些发发言言言言节节点点点点代表整个代表整个代表整个代表整个A

170、SASl l发发言言言言节节点点点点创创建到达其他网建到达其他网建到达其他网建到达其他网络络的路由表，并将其的路由表，并将其的路由表，并将其的路由表，并将其通知通知通知通知给给相相相相邻邻ASAS中中中中发发言言言言节节点点点点l l路由信息路由信息路由信息路由信息：（网：（网：（网：（网络络，路径路径路径路径）l l路径：路径：路径：路径：ASAS列表列表列表列表组组成成成成2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9696路由信息：（目的地，路径）路由信息：（目的地，路径）初始路由表初始路由表初始路由表初始路由表稳定

171、后的路由表稳定后的路由表稳定后的路由表稳定后的路由表2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9797Path Vector Routing Tablel l路由表：路由表：路由表：路由表： 目的地，目的地，目的地，目的地，Next-hopNext-hop，PathPath l lPathPathl lAn ordered An ordered list of ASslist of ASs that a packet should that a packet should travel through to reach

172、the destinationtravel through to reach the destinationl lExampleExamplel lLoop preventionLoop preventionNetworkNext RouterPathN01R01 AS14, AS23, AS67N02R05 AS22, AS67, AS05, AS89N03R06 AS67, AS89, AS09, AS34N04R12 AS62, AS02, AS092024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9898Path vec

173、tor packets2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite9999Policy routing（策略路由选择）（策略路由选择）l l当当ASBR收到路径向量收到路径向量报文，文，检查其通告的其通告的路径（路径（Path）l l如果路径中所列出的某个如果路径中所列出的某个如果路径中所列出的某个如果路径中所列出的某个ASAS不符合路由策略，不符合路由策略，不符合路由策略，不符合路由策略，则则忽略忽略忽略忽略这这一路由通告一路由通告一路由通告一路由通告l l不更新路由表不更新路由表不更新路由表不更新路由表l l也不也不也

174、不也不继续继续向向向向邻邻居居居居ASBRASBR通告通告通告通告l l路由路由选择不一定再是基于最小跳数的了不一定再是基于最小跳数的了2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite100100BGP Path Attributesl l属性属性属性属性给给出了关于某条路径的相关信息，在策略路出了关于某条路径的相关信息，在策略路出了关于某条路径的相关信息，在策略路出了关于某条路径的相关信息，在策略路由由由由时时属性列表可以帮助属性列表可以帮助属性列表可以帮助属性列表可以帮助选选路决策路决策路决策路决策l lForm: For

175、m: l lTypesTypesl lWell-known mandatoryWell-known mandatory（熟知（熟知（熟知（熟知强强制）制）制）制）l lExample: ORIGIN (1), AS_PATH (2), NEXT_HOP (3)Example: ORIGIN (1), AS_PATH (2), NEXT_HOP (3)l lWell-known discretionary Well-known discretionary （熟知自（熟知自（熟知自（熟知自选选）l lExample: LOCAL_PREF (5), ATOMIC_AGGREGATOR Exampl

176、e: LOCAL_PREF (5), ATOMIC_AGGREGATOR (6), AGGREGATOR (7)(6), AGGREGATOR (7)l lOptional transitiveOptional transitive（可（可（可（可选传递选传递）l lOptional non-transitive Optional non-transitive （可（可（可（可选选非非非非传递传递）l lExample: MULTI_EXIT_DISC (4)Example: MULTI_EXIT_DISC (4)2024/8/22024/8/2TCP/IP Protocol SuiteTCP

177、/IP Protocol Suite101101IBGP & EBGPAS 1AS 1R RAS 3AS 3AS 2AS 2R RR RR RR RAS 3AS 3R RR REBGPEBGPEBGPEBGPEBGPEBGPEBGPEBGPIBGPIBGPIBGPIBGPIBGPIBGP2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite102102BGP Messagesl lMessage headerl lEncapsulationl lTCP ( port 179 ) TCP ( port 179 ) unicasting

178、 unicastingTypeTypeMakerMaker（authentication or synchronizationauthentication or synchronization）LengthLength1 16 6 b by yt te es s2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite103103Message Typesl lType 1: OPENType 1: OPENl lEstablish the peer relationshipEstablish the peer relationship

179、l lType 2: UPDATEType 2: UPDATEl lAdvertiseAdvertise（宣布）（宣布）（宣布）（宣布） reachable or withdrawnreachable or withdrawn（撤（撤（撤（撤销销） routes routes using NLRI and path attributesusing NLRI and path attributesl lNLRI: network layer reachability information NLRI: network layer reachability information l lType

180、3: NOTIFICATIONType 3: NOTIFICATIONl lInform the receiving router of errorsInform the receiving router of errorsl lType 4: KEEPALIVEType 4: KEEPALIVEl lInterval keeps peer relationshipInterval keeps peer relationshipl lRecommend: 1/3 Hold Time intervalRecommend: 1/3 Hold Time interval2024/8/22024/8/

181、2TCP/IP Protocol SuiteTCP/IP Protocol Suite104104BGP Operationl lEstablish the BGP peer relationshipEstablish the BGP peer relationshipl lExchange all candidate BGP routes, Exchange all candidate BGP routes, including withdraw routesincluding withdraw routes1.1.1.12.2.2.2Net 6.0.0.0/8, 7.0.0.0/8Net

182、6.0.0.0/8, 7.0.0.0/8Net 4.0.0.0/8, 5.0.0.0/8Net 4.0.0.0/8, 5.0.0.0/8Net 4.0.0.0/8Net 4.0.0.0/8Net 5.0.0.0/8Net 5.0.0.0/8Net 6.0.0.0/8Net 6.0.0.0/8Net 7.0.0.0/8Net 7.0.0.0/8Net 6.0.0.0/8Net 6.0.0.0/8Net 7.0.0.0/8Net 7.0.0.0/8Net 4.0.0.0/8Net 4.0.0.0/8Net 5.0.0.0/8Net 5.0.0.0/8Withdraw 4.0.0.0/8Withdr

183、aw 4.0.0.0/82024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite105105BGP Routing Process ModelInputInputPolicyPolicyEngineEngineDecisionDecisionProcessProcessRoutesRoutesused used bybyrouterrouterOutputOutputPolicyPolicyEngineEngineRoutesRoutesreceivedreceivedfrom peersfrom peersFilteringFilt

184、eringChoosingChoosingthe bestthe bestrouterouteRoutesRoutessentsentto peersto peersFilteringFilteringBGPBGPTableTableIP RoutingIP RoutingTableTable2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite106106Referencel lMark McGregor，CCNP 思科网思科网络技技术学学院教程（第五学期）高院教程（第五学期）高级路由，人民路由，人民邮电出版社，出版社，2001.

185、12.1l lOSPF: Chapter 4, 5, OSPF: Chapter 4, 5, l lBGP: Chapter 8, 9 BGP: Chapter 8, 9 2024/8/22024/8/2TCP/IP Protocol SuiteTCP/IP Protocol Suite107107Summaryl l路由路由l l静静静静态态 vs. vs. 动态动态l l路由路由协议l l类类型型型型l lIGPIGP：RIPRIP、 OSPFOSPFl lEGPEGP：BGP-4BGP-4l l操作操作操作操作l l路由信息交路由信息交路由信息交路由信息交换换：whatwhat、 whenwhen、wherewherel l路由路由路由路由计计算算算算