中科大計(jì)算機(jī)網(wǎng)絡(luò)課件

1、Chapter 14Upon completion you will be able to:Unicast Routing Protocols:RIP, OSPF, and BGP Distinguish between intra and interdomain routing Understand distance vector routing and RIP Understand link state routing and OSPF Understand path vector routing and BGPObjectives 1單播路由協(xié)議路由問(wèn)題描述為：給定一組路由器和連接路由器

2、的一組鏈路，尋找一條從源路由器到目的路由器的最佳路徑。最佳路徑：從源路由器到目的路由器的代價(jià)最小的路徑。路由優(yōu)化較多考慮的目標(biāo)是最小化分組延遲和最大化吞吐量，但這是一對(duì)矛盾。作為折衷，大多數(shù)網(wǎng)絡(luò)最小化分組跳數(shù)。路由表是由路由算法建立起來(lái)的一張表，通常包含了分組轉(zhuǎn)發(fā)路徑上下一跳地址的信息。路由協(xié)議用于在路由器之間交換網(wǎng)絡(luò)狀態(tài)信息，以便動(dòng)態(tài)地更新路由表。214.1 INTRA- AND INTERDOMAIN ROUTINGRouting inside an autonomous system is referred to as intradomain routing. Routing betwe

3、en autonomous systems is referred to as interdomain routing. 3Figure 14.1 Autonomous systems4Figure 14.2 Popular routing protocols514.2 DISTANCE VECTOR ROUTINGIn distance vector routing, the least cost route between any two nodes is the route with minimum distance. In this protocol each node maintai

4、ns a vector (table) of minimum distances to every nodeThe topics discussed in this section include:Initialization Sharing Updating When to Share Two-Node Loop Instability Three-Node Instability 6Figure 14.3 Distance vector routing tables7Figure 14.4 Initialization of tables in distance vector routin

5、g8In distance vector routing, each node shares its routing table with its immediate neighbors periodically and when there is a change.Note:9Figure 14.5 Updating in distance vector routing10Figure 14.6 Two-node instability11Figure 14.7 Three-node instability1214.3 RIPThe Routing Information Protocol

6、(RIP) is an intradomain routing protocol used inside an autonomous system. It is a very simple protocol based on distance vector routing. The topics discussed in this section include:RIP Message Format Requests and Responses Timers in RIP RIP Version 2 Encapsulation 13Figure 14.8 Example of a domain

7、 using RIP14Figure 14.9 RIP message format15Figure 14.10 Request messages16Figure 14.11 shows the update message sent from router R1 to router R2 in Figure 14.8. The message is sent out of interface 130.10.0.2.Example 1See Next SlideThe message is prepared with the combination of split horizon and p

8、oison reverse strategy in mind. Router R1 has obtained information about networks 195.2.4.0, 195.2.5.0, and 195.2.6.0 from router R2. When R1 sends an update message to R2, it replaces the actual value of the hop counts for these three networks with 16 (infinity) to prevent any confusion for R2. The

9、 figure also shows the table extracted from the message. Router R2 uses the source address of the IP datagram carrying the RIP message from R1 (130.10.02) as the next hop address.17Figure 14.11 Solution to Example 118Figure 14.12 RIP timers19A routing table has 20 entries. It does not receive inform

10、ation about five routes for 200 s. How many timers are running at this time?Example 2SolutionThe 21 timers are listed below: Periodic timer: 1 Expiration timer: 20 5 = 15 Garbage collection timer: 520Figure 14.13 RIP version 2 format21Figure 14.14 Authentication22RIP uses the services of UDP on well

11、-known port 520.Note:2314.4 LINK STATE ROUTINGIn link state routing, if each node in the domain has the entire topology of the domain, the node can use Dijkstras algorithm to build a routing table.每一個(gè)點(diǎn)有整個(gè)Domain全局的拓?fù)?The topics discussed in this section include:Building Routing Tables 24Figure 14.16

12、Link state knowledge25Figure 14.15 Concept of link state routing26Figure 14.17 Dijkstra algorithm27Figure 14.18 Example of formation of shortest path tree28Table 14.1 Routing table for node A2914.5 OSPFThe Open Shortest Path First (OSPF) protocol is an intradomain routing protocol based on link stat

13、e routing. Its domain is also an autonomous system. 開(kāi)放最短路徑優(yōu)先The topics discussed in this section include:Areas 區(qū)域Metric 度量Types of Links 鏈路類(lèi)型 Graphical Representation 圖形表示法 OSPF Packets OSPF分組Link State Update Packet 鏈路狀態(tài)更新分組Other Packets 其他分組Encapsulation 封裝30Figure 14.19 Areas in an autonomous sys

14、tem內(nèi)部路由器 (Internal router) 區(qū)域邊界路由器 (Area border router) 主干路由器 (Backbone router) AS邊界路由器 (AS boundary router)31Figure 14.20 Types of links鏈路類(lèi)型 點(diǎn)對(duì)點(diǎn)鏈路 轉(zhuǎn)接鏈路 殘樁鏈路 虛擬鏈路32Figure 14.21 Point-to-point link33Figure 14.22 Transient link34Figure 14.23 Stub link35Figure 14.24 Example of an AS and its graphical r

15、epresentation in OSPF36Figure 14.25 Types of OSPF packets共有5種不同的LSA：路由器鏈路網(wǎng)絡(luò)鏈路匯總鏈路到網(wǎng)絡(luò)匯總鏈路到AS邊界路由器外部鏈路37Figure 14.26 OSPF common header 公共首部38Figure 14.27 Link state update packet39Figure 14.28 LSA general header40Figure 14.29 Router link41Figure 14.30 Router link LSA42Table 14.2 Link types, link iden

16、tification, and link data43Give the router link LSA sent by router 10.24.7.9 in Figure 14.31.Example 3SolutionThis router has three links: two of type 1 (point-to-point) and one of type 3 (stub network). Figure 14.32 shows the router link LSA.See Next SlideSee Figure 14.3244Figure 14.31 Example 345F

17、igure 14.32 Solution to Example 346Figure 14.33 Network link47Figure 14.34 Network link advertisement format48Give the network link LSA in Figure 14.35.Example 4Solution.See Next SlideSee Figure 14.3649Figure 14.35 Example 450Figure 14.36 Solution to Example 451In Figure 14.37, which router(s) sends

18、 out router link LSAs?Example 5SolutionAll routers advertise router link LSAs. a. R1 has two links, N1 and N2.b. R2 has one link, N1.c. R3 has two links, N2 and N3.See Next Slide52Figure 14.37 Example 5 and Example 653In Figure 14.37, which router(s) sends out the network link LSAs?Example 6Solution

19、All three network must advertise network links: a. Advertisement for N1 is done by R1 because it is the only attached router and therefore the designated router. b. Advertisement for N2 can be done by either R1, R2, or R3, depending on which one is chosen as the designated router. c. Advertisement f

20、or N3 is done by R3 because it is the only attached router and therefore the designated router.54Figure 14.38 Summary link to network55Figure 14.39 Summary link to network LSA56Figure 14.40 Summary link to AS boundary router57Figure 14.41 Summary link to AS boundary router LSA58Figure 14.42 External

21、 link59Figure 14.43 External link LSA60Figure 14.44 Hello packet61Figure 14.45 Database description packet62Figure 14.46 Link state request packet63Figure 14.47 Link state acknowledgment packet64OSPF分組格式OSPF使用5種類(lèi)型的分組：?jiǎn)柡蚍纸M：節(jié)點(diǎn)使用該分組建立鄰居關(guān)系，測(cè)試鄰居的可達(dá)性。（包含本節(jié)點(diǎn)信息及已知鄰居的清單）數(shù)據(jù)庫(kù)描述分組：當(dāng)節(jié)點(diǎn)收到一個(gè)新鄰居的問(wèn)候分組時(shí)，發(fā)送數(shù)據(jù)庫(kù)描述分組，分組中

22、僅包含數(shù)據(jù)庫(kù)中每一行的標(biāo)題。鏈路狀態(tài)請(qǐng)求分組：由需要一條或幾條特定路由的路由器發(fā)送。鏈路狀態(tài)更新分組：路由器使用該分組通告它的鏈路狀態(tài)。鏈路狀態(tài)確認(rèn)分組：用于對(duì)收到的鏈路狀態(tài)更新分組進(jìn)行確認(rèn)。OSPF分組被封裝在IP數(shù)據(jù)報(bào)中傳輸，OSPF協(xié)議提供確認(rèn)機(jī)制以實(shí)現(xiàn)流量控制和差錯(cuò)控制。65距離向量路由選擇/鏈路狀態(tài)路由選擇： 限制可縮放性當(dāng)運(yùn)行區(qū)域的跳數(shù)稍微多了一些時(shí)，距離向量路由選擇就變得不穩(wěn)定。鏈路狀態(tài)路由選擇需要非常大的資源來(lái)計(jì)算路由表，同時(shí)由于使用flooding的方式，會(huì)產(chǎn)生很大的通信量。引入了第三種路由選擇協(xié)議，路徑向量路由協(xié)議。6614.6 PATH VECTOR ROUTINGPat

23、h vector routing is similar to distance vector routing. There is at least one node, called the speaker node, in each AS that creates a routing table and advertises it to speaker nodes in the neighboring ASs. 路徑向量路由選擇The topics discussed in this section include:Initialization Sharing Updating 67Figure 14.48 Initial routing tables in path vector routing68Figure 14.49 Stabilized tables for four autonomo