第 19 章互联网的操作 (1) 因特网路由协议 南京大学计算机系 黄皓教授 2007 年 10 月 9 日星期二 2007 年 10 月 12 日星期五 1
Reference TCP/IP Tutorial and Technical Overview, ibm.com/redbooks Christian Huitma, Routing in the Internet. 南京大学计算机系讲义 2
Routing Protocols Routing Information About topology and delays in the internet Routing Algorithm Used to make routing decisions based on information 南京大学计算机系讲义 3
全球因特网 因特网结构 接入网络 /ISP 区域 ISP/ 国家网络 国际主干网 第一层 国家主干网 第二层 区域 ISP 美洲区 第三层 接入网, 校园网, 无线 LAN 亚太区 国际链路 南美区 欧洲区 南京大学计算机系讲义 4
额外跳 R1 主干网络 R2 核心路由器 核心路由器 R3 非核心路由器 限制路由器的数量 非核心路由其选择一个核心路由器作为默认路由器 额外跳 南京大学计算机系讲义 5
隐藏网络 主干网络 R1 本地网络 R2 R3 本地网络 本地网络 R4 本地网络 南京大学计算机系讲义 6
Autonomous systems The definition of an autonomous system (AS) is integral to understanding the function and scope of a routing protocol. An AS is defined as a logical portion of a larger IP network. AS is normally comprised of an internetwork within an organization. It is administered by a single management authority. Exchange information Common routing protocol A connected network There is at least one route between any pair of nodes 南京大学计算机系讲义 7
Interior Gateway Protocols (IGPs) Interior gateway protocols allow routers to exchange information within an AS. Examples of these protocols are Open Short Path First (OSPF) and Routing Information Protocol (RIP). Exterior Gateway Protocols (EGPs) Exterior gateway protocols allow the exchange of summary information between autonomous systems. An example of this type of routing protocol is Border Gateway Protocol (BGP). 南京大学计算机系讲义 8
南京大学计算机系讲义 9
Application of IRP and ERP 南京大学计算机系讲义 10
Types of IP routing Static routing Static routing is manually performed by the network administrator. The administrator is responsible for discovering and propagating routes through the network. These definitions are manually programmed in every routing device in the environment. There is no communication between routers regarding the current topology of the network. 南京大学计算机系讲义 11
static routes can be used: To manually define a default route. To define a route that is not automatically advertised within a network. When complex routing policies are required. To provide a more secure network environment. To provide more efficient resource utilization. 南京大学计算机系讲义 12
Routing Distance-vector Each node (router or host) exchange information with neighboring nodes Neighbors are both directly connected to same network First generation routing algorithm for ARPANET Node maintains vector of link costs for each directly attached network and distance and next-hop vectors for each destination Used by Routing Information Protocol (RIP) Requires transmission of lots of information by each router Distance vector to all neighbors Contains estimated path cost to all networks in configuration Changes take long time to propagate 南京大学计算机系讲义 13
Bellman-Ford Algorithm Method Step 1 [Initialization] L 0 (n) =, for all n s L h (s) = 0, for all h Step 2 [Update] j 1 j 2 n j k For each successive h 0 For each n s, compute L h+1 (n)= min j [L h (j)+w(j,n)] s Connect n with predecessor node j that achieves minimum Eliminate any connection of n with different predecessor node formed during an earlier iteration Path from s to n terminates with link from j to n 南京大学计算机系讲义 14
Bellman-Ford Algorithm Method Step 1 [Initialization] L 0 (n) =, for all n s L h (s) = 0, for all h Step 2 [Update] j 1 j 2 n j k For each successive h 0 For each n s, compute L h+1 (n)= min j [L h (j)+w(j,n)] s Connect n with predecessor node j that achieves minimum Eliminate any connection of n with different predecessor node formed during an earlier iteration Path from s to n terminates with link from j to n 南京大学计算机系讲义 15
disadvantages with DV During an adverse condition, the length of time for every device in the network to produce an accurate routing table is called the convergence time. In large, complex internetworks using distance vector algorithms, this time can be excessive. To reduce convergence time, a limit is often placed on the maximum number of hops contained in a single route. Distance vector routing tables are periodically transmitted to neighboring devices. They are sent even if no changes have been made to the contents of the table. 南京大学计算机系讲义 16
Bellman-Ford Algorithm Method Step 1 [Initialization ] h=1 h=2 L 0 (n) =, for all n s L h (s) = 0, for all h L(1) =2, L(2)=3, 2 s L(j) =, j <> 1,2 3 L(1) = 2, L(2) = 3, h=3 L(3)=3, L(4)=7 L(1) = 2, L(2) = 3, L(3)=3, L(4)=4 1 2 1 1 s 5 3 4 1 1 2 6 s 3 2 1 2 s 3 2 1 2 1 1 3 4 3 4 5 3 1 4 6 南京大学计算机系讲义 17
Routing Link-state Designed to overcome drawbacks of distance-vector When router initialized, it determines link cost on each interface Advertises set of link costs (Link State Advertisement, LSA ) to all other routers in topology Not just neighboring routers From then on, monitor link costs If significant change, router advertises new set of link costs Each router can construct topology of entire configuration Can calculate shortest path to each destination network Router constructs routing table, listing first hop to each destination Router does not use distributed routing algorithm Use any routing algorithm to determine shortest paths In practice, Dijkstra's algorithm Open shortest path first (OSPF) protocol uses link-state routing. Also second generation routing algorithm for ARPANET 南京大学计算机系讲义 18
Shortest-Path First (SPF) algorithm The SPF algorithm is used to process the information in the topology database. It provides a treerepresentation of the network. The device running the SPF algorithm is the root of the tree. The output of the algorithm is the list of shortest-paths to each destination network. 南京大学计算机系讲义 19
Exterior Router Protocols Not Distance-vector Link-state and distance-vector not effective for exterior router protocol Distance-vector assumes routers share common distance metric ASs may have different priorities May have restrictions that prohibit use of certain other AS Distance-vector gives no information about ASs visited on route 南京大学计算机系讲义 20
Exterior Router Protocols Not Link-state Different ASs may use different metrics and have different restrictions Impossible to perform a consistent routing algorithm. Flooding of link state information to all routers unmanageable 南京大学计算机系讲义 21
Exterior Router Protocols Path-vector Dispense with routing metrics Provide information about which networks can be reached by a given router and ASs crossed to get there Does not include distance or cost estimate Each block of information lists all ASs visited on this route Enables router to perform policy routing E.g. avoid path to avoid transiting particular AS E.g. link speed, capacity, tendency to become congested, and overall quality of operation, security E.g. minimizing number of transit ASs 南京大学计算机系讲义 22
Routing Information Protocol (RIP) 23
Convergence 1 A B 1 1 C 10 1 D 1 N Router D to the target network: Directly connected network. Metric 1. Router B to the target network: Next hop is router D. Metric is 2. Router C to the target network: Next hop is router B. Metric is 3. Router A to the target network: Next hop is router B. Metric is 3. 南京大学计算机系讲义 24
counting to infinity the link connecting router B and router D fails. A 1 10 1 1 C D N 1 1 B The length of a route must be less than 15. 15 = infinity. 南京大学计算机系讲义 25
split horizon The "simple " scheme omits routes learned from one neighbor in updates sent to that neighbor. A About A, B About C, D, B B C About D,B About C,A, B D About A,C About B,C,D About D, C About B, C, A About C, A, D About B, A 南京大学计算机系讲义 26
split horizon 1 A B 1 1 C 10 1 D 1 N Wait for timeout 南京大学计算机系讲义 27
Split horizon with poisoned reverse "Split horizon with poisoned reverse includes such routes in updates, but sets their metrics to infinity. If A thinks it can get to D via C, its messages to C should indicate that D is unreachable. If the route through C is real, then C either has a direct connection to D, or a connection through some other gateway. A C D N B With poison reverse, when a routing update indicates that a network is unreachable, routes are immediately removed from the routing table. 南京大学计算机系讲义 28
counting to infinity under the Split horizon with poisoned reverse 距离 B D 2 E C D 2 E E D 1 下一跳 A B C D E 南京大学计算机系讲义 29
counting to infinity under the Split horizon with poisoned reverse 距离 B D 2 E C D 2 E E D 无穷 下一跳 距离 B D 无穷 C D 2 E E D 无穷 下一跳 距离 B D 3 C C D 2 E E D 4 B 下一跳 Unreachable message reached B but not reached C. A B C D E 南京大学计算机系讲义 30
Triggered updates To get triggered updates, we simply add a rule that whenever a gateway changes the metric for a route, it is required to send update messages almost immediately, even if it is not yet time for one of the regular update message. 南京大学计算机系讲义 31
RIP is a UDP-based protocol. Each host that uses RIP has a routing process that sends and receives datagrams on UDP port number 520. 南京大学计算机系讲义 32
OSPF 33
Sample AS a OSPF network 南京大学计算机系讲义 34
Directed Graph of AS 南京大学计算机系讲义 35
SPF Tree 南京大学计算机系讲义 36
OSPF terminology 1. OSPF areas 2. Intra-area, area border and AS boundary routers 3. Physical network types 4. Neighbor routers and adjacencies 5. Designated and backup designated router 6. Link state database 7. Link state advertisements and flooding 南京大学计算机系讲义 37
(1) OSPF areas OSPF networks are divided into a collection of areas. An area consists of a logical grouping of networks and routers. The area may coincide with geographic or administrative boundaries. Each area is assigned a 32-bit area ID. 南京大学计算机系讲义 38
(1) OSPF areas benefits: Within an area, every router maintains an identical topology database, This reduces the size of the topology database maintained by each router. Areas limit the potentially explosive growth in the number of link state updates. Areas reduce the CPU processing required to maintain the topology database. 南京大学计算机系讲义 39
(1) OSPF areas Backbone area and area 0 All OSPF networks contain at least one backbone area. Additional areas may be created based on network topology or other design requirements. the backbone physically connects to all other areas. OSPF expects all areas to announce routing information directly into the backbone. 南京大学计算机系讲义 40
(2) Intra-area, area border and AS boundary routers Intra-Area Routers This class of router is logically located entirely within an OSPF area. Intraarea routers maintain a topology database for their local area. 南京大学计算机系讲义 41
(2) Intra-area, area border and AS boundary routers Area Border Routers (ABR) This class of router is logically connected to two or more areas. One area must be the backbone area. An ABR is used to interconnect areas. They maintain a separate topology database for each attached area. ABRs also execute separate instances of the SPF algorithm for each area. 南京大学计算机系讲义 42
(2) Intra-area, area border and AS boundary routers AS Boundary Routers (ASBR) This class of router is located at the periphery of an OSPF internetwork. It functions as a gateway exchanging reachability between the OSPF network and other routing environments. ASBRs are responsible for announcing AS external link advertisements through the AS. 南京大学计算机系讲义 43
(3) Physical network types Point-to-point Point-to-point networks directly link two routers. Multi-access Multi-access networks support the attachment of more than two routers. Broadcast networks have the capability of simultaneously directing a packet to all attached routers. Ethernet and tokenring LANs Non-broadcast networks. Each packet must be specifically addressed to every router in the network. X.25 and frame relay networks. 南京大学计算机系讲义 44
Sample AS a OSPF network 南京大学计算机系讲义 45
Directed Graph of AS 南京大学计算机系讲义 46
(4)Neighbor routers and adjacencies Routers that share a common network segment establish a neighbor relationship on the segment. Area-id:The routers must belong to the same OSPF area. Authentication Hello and dead intervals: The routers must specify the same timer intervals used in the Hello protocol. Neighboring routers are considered adjacent when they have synchronized their topology databases. This occurs through the exchange of link state information. 南京大学计算机系讲义 47
(5) Designated and backup designated router Each multi-access network elects a designated router (DR) and backup designated router (BDR). It forms adjacencies with all routers on the multi-access network. It generates network link advertisements listing each router connected to the multi-access network. 南京大学计算机系讲义 48
R1-R4 之间有 4 3/2=6 条链路要公告 R1-R4 与 N3 之间有 4 条链路要公告 共有 10( n 2 /2) 条链路公告 指派路由公告 N3 到 R1-R4 的链路, 路由器自己公布路由器到 N3 的链路 共 8(2n) 条链路 R1 R2 R4 R3 南京大学计算机系讲义 49
Link state database The link state database is also called the topology database(link state database). It contains the set of link state advertisements describing the OSPF network and any external connections. Each router within the area maintains an identical copy of the link state database. 南京大学计算机系讲义 50
Link state advertisements and flooding LSAs are exchanged between adjacent OSPF routers. reliable flooding. Each router stores the LSA for a period of time before propagating the information to its neighbors. If, during that time, a new copy of the LSA arrives, the router replaces the stored version. However, if the new copy is outdated, it is discarded. To ensure reliability, each link state advertisement must be acknowledged. Multiple acknowledgements can be grouped together into a single acknowledgement packet. If an acknowledgement is not received, the original link state update packet is retransmitted. 南京大学计算机系讲义 51
OSPF packet types OSPF packets are transmitted in IP datagrams. They are not encapsulated within TCP or UDP packets. OSPF uses multicast facilities to communicate with neighboring devices. Packets are sent to the reserved multicast address 224.0.0.5 (AllSPFRouters address ). 南京大学计算机系讲义 52
Common header of OSPF packets 南京大学计算机系讲义 53
five possible types of OSPF Hello This packet type is used to discover and maintain neighbor relationships. Database description This packet type describes the set of LSAs contained in the router s link state database. Link state request This packet type is used to request a more current instance of an LSA from a neighbor. Link state update This packet type is used to provide a more current instance of an LSA to a neighbor. Link state acknowledgement This packet type is used to acknowledge receipt of a newly received LSA. 南京大学计算机系讲义 54
activities to accomplish this information exchange Neighbor communication Electing a designated router Establishing adjacencies and synchronizing databases 南京大学计算机系讲义 55
Neighbor communication The Hello protocol discovers and maintains relationships with neighboring routers. Hello packets are periodically sent out to each router interface. The packet contains the RID of other routers whose hello packets have already been received over the interface. When a device sees its own RID in the hello packet generated by another router, these devices establish a neighbor relationship. 南京大学计算机系讲义 56
Link state advertisements contain five types of information Router LSAs describes the state of the router's interfaces (links) within the area. Network LSAs lists the routers connected to a multi-access network. generated by the DR summary LSAs describe routes to destinations in other areas within the OSPF network. summary LSAs describe routes to ASBRs. AS external LSAs describes routes to destinations external to the OSPF network. 南京大学计算机系讲义 57
five types of LSA information 南京大学计算机系讲义 58
The LSA header 南京大学计算机系讲义 59
The LSA header LS type router-lsas, network-lsas, summary-lsas, AS-external- LSAs LS age The time in seconds since the LSA was originated. Link State ID This field identifies the portion of the internet environment that is being described by the LSA. The contents of this field depend on the LSA s LS type. For example, in network- LSAs the Link State ID is set to the IP interface address of the network s Designated Router Advertising Router The Router ID of the router that originated the LSA. LS sequence number Detects old or duplicate LSAs. length This includes the 20 byte LSA header. 南京大学计算机系讲义 60
(1) Router-LSAs 南京大学计算机系讲义 61
(1) Router-LSAs bit E:When set, the router is an AS boundary router (E is for external). bit B:When set, the router is an area border router (B is for border). type Link ID Point-to-point to a transit network to a stub network Neighboring router s Router ID IP address of Designated Router IP network 南京大学计算机系讲义 62
(2) Network-LSAs 南京大学计算机系讲义 63
(2) Network-LSAs The network-lsa is originated by the network s Designated Router. The LSA describes all routers attached to the network, including the Designated Router itself. The LSA s Link State ID field lists the IP interface address of the Designated Router. Network Mask The IP address mask for the network. Attached Router The Router IDs of each of the routers attached to the network. R1 R2 R4 R3 南京大学计算机系讲义 64
(3) Summary-LSAs 南京大学计算机系讲义 65
(3) Summary-LSAs These LSAs are originated by area border routers. Summary-LSAs describe inter-area destinations. Type 3 summary-lsas are used when the destination is an IP network. When the destination is an AS boundary router, a Type 4 summary-lsa is used, and the Link State ID field is the AS boundary router s OSPF Router ID. 南京大学计算机系讲义 66
(4) AS-external-LSAs 南京大学计算机系讲义 67
(4) AS-external-LSAs These LSAs are originated by AS boundary routers, and describe destinations external to the AS. For these LSAs the Link State ID field specifies an IP network number. Network Mask The IP address mask for the advertised destination. Metric: The cost of this route. Forwarding address: Data traffic for the advertised destination will be forwarded to this address. 南京大学计算机系讲义 68
The Hello Protocol The Hello Protocol is responsible for establishing and maintaining neighbor relationships. Hello packets are sent periodically out all router interfaces. Bidirectional communication is indicated when the router sees itself listed in the neighbor's Hello Packet. On broadcast and NBMA networks, the Hello Protocol elects a Designated Router for the network. 南京大学计算机系讲义 69
南京大学计算机系讲义 70
On broadcast networks, each router advertises itself by periodically multicasting Hello Packets. This allows neighbors to be discovered dynamically. These Hello Packets contain the router's view of the Designated Router's identity, and the list of routers whose Hello Packets have been seen recently. All routers connected to a common network must agree on certain parameters (Network mask, HelloInterval and RouterDeadInterval). 南京大学计算机系讲义 71
On NBMA networks some configuration information may be necessary for the operation of the Hello Protocol. Each router that may potentially become Designated Router has a list of all other routers attached to the network. A router, having Designated Router potential, sends Hello Packets to all other potential Designated Routers when its interface to the NBMA network first becomes operational. This is an attempt to find the Designated Router for the network. If the router itself is elected Designated Router, it begins sending Hello Packets to all other routers attached to the network. 南京大学计算机系讲义 72
南京大学计算机系讲义 73
南京大学计算机系讲义 74
Neighbor states(1) Down the initial state there has been no recent information received from the neighbor. Attempt This state is only valid for neighbors attached to NBMA networks. It indicates that no recent information has been received from the neighbor, but that a more concerted effort should be made to contact the neighbor. This is done by sending the neighbor Hello packets at intervals of HelloInterval. Hello received Down Init ExStart 2-Way received start Attempt Hello received 1-Way received 2-Way Init: In this state, an Hello packet has recently been seen from the neighbor. ExStart: In this state, an Hello packet has recently been seen from the neighbor. 2-Way: communication between the two routers is bidirectional. 南京大学计算机系讲义 75
Events causing neighbor state(1) changes HelloReceived Start This is an indication that Hello Packets should now be sent to the neighbor at intervals of HelloInterval seconds. This event is generated only for neighbors associated with NBMA networks. 2-Way Received This is indicated by the router seeing itself in the neighbor's Hello packet. 1-Way Received An Hello packet has been received from the neighbor, in which the router is not mentioned. This indicates that communication with the neighbor is not bidirectional. 南京大学计算机系讲义 76
The Synchronization of Databases In a link-state routing algorithm, it is very important for all routers' link-state databases to stay synchronized. OSPF simplifies this by requiring only adjacent routers to remain synchronized. 南京大学计算机系讲义 77
南京大学计算机系讲义 78
Neighbor states(2) Exchange Loading Full In this state the router is describing its entire link state database by sending Database Description packets to the neighbor. In this state, Link State Request packets are sent to the neighbor asking for the more recent LSAs that have been discovered (but not yet received) in the Exchange state. In this state, the neighboring routers are fully adjacent. These adjacencies will now appear in router-lsas and network-lsas. ExStart negotiationdone Exchange ExchageDone Full Loading LoadingDone 南京大学计算机系讲义 79
Events causing neighbor state changes(2) NegotiationDone The Master/Slave relationship has been negotiated, and DD sequence numbers have been exchanged. This signals the start of the sending/receiving of Database Description packets. ExchangeDone ExStart negotiationdone Exchange ExchageDone Loading Done Full LoadingDone Loading 南京大学计算机系讲义 80
南京大学计算机系讲义 81
Border Gateway Protocol (BGP) 82
Border Gateway Protocol (BGP) For use with TCP/IP internets BGP messages are sent over TCP connections BGP messages Open: opens TCP connection to peer and authenticates sender Keep-alive: (1) ACKs OPEN request; (2) keeps connection alive in absence of UPDATES Update: (1) advertises new path; (2) withdraws old Notification: (1) closes connection; (2) reports errors in previous msg 南京大学计算机系讲义 83
Procedures of BGP Neighbor acquisition One router sends an Open message to another If the target router accepts the request, it returns a Keep-alive message Neighbor reachability The two routers periodically issue Keep-alive or Update messages to each other Network reachability Each router maintains a database of networks That it can reach and the list of ASs passed The router issues an Update message whenever a change is made to this database 南京大学计算机系讲义 84
BGP Messages 南京大学计算机系讲义 85
BGP Messages 3 common fixed-size fields in each header Marker (16 octets) Detect loss of synchronization between a pair of BGP speaker Authenticate incoming BGP messages Length (2 octets) Length of message in octets, including the header Type (1 octets) 1.Open, 2.Update, 3.Notification, 4.Keep-alive 南京大学计算机系讲义 86
Open Message Version (1 octet) Current BGP version (v4) My Autonomous System (2 octets) Identification of AS the sender belongs to Hold time (2 octets) Max time between Keep-alive and/or update messages BGP Identifier (4 octets) Identifier of the sender Opt parameter length (1 octet) Total length of the Optional parameter field in octet 8 16 Parm. Type Parm. Length Parameter Value (Variable) 南京大学计算机系讲义 87
Update Message (1) Unfeasible Routes Length (2 octets) Total length of withdraw routes in octets Withdrawn route (variable length) Alist of IP address prefixes, 2- tuple of the form <length, prefix> Each prefix identifies a network e.g. <10, D8CA> means 16 bits length, 216.202.0.0 network Total Path Attribute Length (2 octets) Total length of path attribute field in octets 南京大学计算机系讲义 88
Update Message (2) Path Attribute (variable length) A list of path attributes, each path attribute is a triple <attribute type, attribute length, attribute value> Attributes that apply to the particular router or route Network Layer Reachability Information (variable length) A list of IP address prefixes, each one is 2-tuple of the form <length, prefix> A single route through the internet 南京大学计算机系讲义 89
Defined Path Attributes (1) Well-known mandatory The attribute must be recognized by all BGP implementations. It must be sent in every UPDATE message. Well-known discretionary The attribute must be recognized by all BGP implementations. However, it is not required to be sent in every UPDATE message. Optional transitive It is not required that every BGP implementation recognize this type of attribute. A path with an unrecognized optional transitive attribute is accepted and simply forwarded to other BGP peers. Optional non-transitive It is not required that every BGP implementation recognize this type of attribute. These attributes can be ignored and not passed along to other BGP peers. 南京大学计算机系讲义 90
Defined Path Attributes (2) Origin ( Well-known mandatory ) Learned from IGP or EGP AS_Path ( Well-known mandatory ) A list of AS traversed, in ordered or unordered way Enables routing policy, such as security, performance, QOS, number of ASs, etc. Next_hop( Well-known mandatory ) IP address of the border router that are used as the next hop Not all routers implement BGP Responsible for informing outside routers of the route to other networks 南京大学计算机系讲义 91
Defined Path Attributes (3) Multi_Exit_Disc (MED) There may be multiple border points in one AS available to another AS MED is a metric value computed by certain routing policy within the AS It may be used by another BGP router to discriminate among multiple exit points T AS X Router A MED =50 MED =10 Router B AS Y In this case, it selects route used router A. Because MED value of router A is lower than router B s MED 南京大学计算机系讲义 92
Defined Path Attributes (4) Local_pref Should be included when the 2 BGP speakers located within the same AS It is used by a BGP speaker to inform other BGP speakers in its own autonomous system of the originating speaker s degree of preference for an advertised route. Atomic_Aggregate Informs others that the local system selected a more general route without specifying some interim specific routes Aggregator Contains the last AS number and IP address of the BGP router that formed the aggregate route 南京大学计算机系讲义 93
Keep Alive Message To tell other routers that this router is still here BGP speaker send Keep-Alive message periodically to keep connection 南京大学计算机系讲义 94
Notification Message (1) Message header error Authentication and syntax, subtypes: Connection Not Synchronized Bad Message Length Bad Message Type Open message error Syntax and option not recognized, Unacceptable hold time, subtypes: Unsupported Version Number Bad peer AS Bad BGP identifier Unsupported Optional Parameter, 南京大学计算机系讲义 95
Notification Message (2) Update message error Syntax and validity errors Hold time expired Connection is closed Finite state machine error Cease Any procedural errors: wrong message at wrong states e.g. got Open message at Connect state Used to close a connection when there is no error 南京大学计算机系讲义 96
BGP Routing Information Exchange Within AS, router builds topology picture using IGP Router issues Update message to other routers outside AS using BGP These routers exchange info with other routers in other AS Routers must then decide best routes 南京大学计算机系讲义 97