1、,第7章 非連接型快速分組交換,教學(xué)大綱要求：1.基本要求（1）掌握互聯(lián)網(wǎng)的概念及IP協(xié)議。（2）掌握互聯(lián)網(wǎng)的路由協(xié)議。（3）掌握高性能路由器的關(guān)鍵技術(shù)。2.重點、難點 重點：IP協(xié)議，路由協(xié)議。 難點：大容量高速路由器技術(shù)。3.說明 以講述IP分組交換技術(shù)為主,適當(dāng)介紹相關(guān)協(xié)議。,1,,本章重點討論非連接型分組交換的典型代表—互聯(lián)網(wǎng)中的IP技術(shù)。首先介紹IP協(xié)議，包括IP數(shù)據(jù)報格式、IP地址的表示方法、IP網(wǎng)路

2、由協(xié)議。然后在此基礎(chǔ)上講述高速路由器的結(jié)構(gòu)及實現(xiàn)快速分組交換的關(guān)鍵技術(shù)。,關(guān)于“非連接型快速分組交換”,2,,3,互聯(lián)網(wǎng)是指用路由器進行互連的互連網(wǎng)絡(luò)，這些互連的網(wǎng)絡(luò)往往具有不同的網(wǎng)絡(luò)類型，但互聯(lián)網(wǎng)在網(wǎng)絡(luò)層使用IP協(xié)議屏蔽了底層不同的互連網(wǎng)絡(luò)，使異構(gòu)的網(wǎng)絡(luò)看起來像一個統(tǒng)一的網(wǎng)絡(luò)。,7.1 互聯(lián)網(wǎng)的IP協(xié)議,,4,互聯(lián)網(wǎng)使用的IP協(xié)議族，除了IP協(xié)議之外，還有四個配套的協(xié)議：地址解析協(xié)議ARP，逆地址解析協(xié)議RARP，控制報文協(xié)議ICM

3、P，組管理協(xié)議IGMP。,網(wǎng)際層協(xié)議的組成,,7.1.1 IP數(shù)據(jù)報的格式 7.1.2 分類的IP地址 7.1.3 IP地址與硬件地址 7.1.4 地址解析協(xié)議ARP和逆地址解析協(xié)議RARP 7.1.5 IP層轉(zhuǎn)發(fā)分組的流程,,7.1.1 IP數(shù)據(jù)報的格式,互聯(lián)網(wǎng)網(wǎng)際層的協(xié)議數(shù)據(jù)單元稱為數(shù)據(jù)報。一個IP數(shù)據(jù)報由首部和數(shù)據(jù)兩部分組成。首部的前一部分長度固定，共20字節(jié)，是所有IP數(shù)據(jù)報必須具備的。在首部固定部分的后面是

4、一些可選字段，其長度是可變的（最大長度為40字節(jié)）。,,,5,,IP數(shù)據(jù)報首部中的各字段（一）,（1）版本（Version）占4bit，指IP協(xié)議的版本號。通信雙方使用的IP協(xié)議的版本必須一致。目前使用的版本是版本4和版本6 。（2）首部長度（Header Length）4 bit，可表示的最大數(shù)值是15個單位（一個單位為4字節(jié)），IP的首部長度的最大值是60字節(jié)。當(dāng)IP分組的首部長度不是4字節(jié)的整數(shù)倍時，必須利用最后一個填充字段加以

5、填充。（3）服務(wù)類型（Type of Service）占8 bit，用來獲得更好的服務(wù) ： 前三個比特表示優(yōu)先級，它可使數(shù)據(jù)報具有8個優(yōu)先級中的一個。 第4個比特是D比特，表示要求有更低的時延。 第5個比特是T比特，表示要求有更高的吞吐量。 第6個比特是R比特，表示要求有更高的可靠性（即在數(shù)據(jù)報傳送的過程中，被路由器丟棄的概率要更小些）。 第7個比特是C比特，表示要求選擇代價更小的路由。 最后一個比特目前尚未使

6、用。,6,,7,IP數(shù)據(jù)報首部中的各字段（二）,（4）總長度（Total Length） 總長度指首部和數(shù)據(jù)部分之和的長度，單位為字節(jié)?？傞L度字段為16 bit，因此數(shù)據(jù)報的最大長度可達65535字節(jié)（即64 KB） 將一個IP數(shù)據(jù)報裝入鏈路層幀的數(shù)據(jù)域時，數(shù)據(jù)報的總長度不能超過數(shù)據(jù)鏈路層的最大傳送單元MTU。如有超出，就必須對數(shù)據(jù)報中的數(shù)據(jù)進行分片，每一片都要加上首部，加上首部的數(shù)據(jù)片稱為分組。分組在網(wǎng)絡(luò)中傳送，在目的

7、主機將組成一個數(shù)據(jù)報的各分組重新組裝在一起。（5）標識（Identification） 占16 bit，是一個計數(shù)器，用來標識數(shù)據(jù)報。屬于同一個數(shù)據(jù)報的分組，具有相同的標識。（6）標志（Flag） 占3 bit，目前只有前兩個比特有意義。 ? 最低位記為MF，MF=1表示“本分組后面還有同一數(shù)據(jù)報的后續(xù)分組”。MF=0表示這是數(shù)據(jù)報的最后一個分組。 ? 中間的一位記為DF（Don’t Fragment），DF=1意思

8、是“不分片”，即該數(shù)據(jù)報只有一個分組。,,8,IP數(shù)據(jù)報首部中的各字段（三）,,9,（9）協(xié)議（Protocol）占8 bit，指出此數(shù)據(jù)報攜帶的數(shù)據(jù)使用何種協(xié)議，以便目的主機IP層將數(shù)據(jù)部分上交對應(yīng)協(xié)議處理 。,（10）首部校驗和（Header Checksum）只校驗數(shù)據(jù)報的首部，不校驗數(shù)據(jù)部分。在發(fā)送端，將IP數(shù)據(jù)報首部劃分為許多16 bit字的序列，用反碼算術(shù)運算將所有16 bit字相加后，將和的反碼寫入檢驗和字段。接收端收到數(shù)

9、據(jù)報后，將首部的所有16 bit字（包括檢驗和的16比特）再使用反碼算術(shù)運算累加。將得到的和取反碼，結(jié)果為0則保留數(shù)據(jù)報，否則丟棄數(shù)據(jù)報。,IP數(shù)據(jù)報首部中的各字段（四）,,10,（11）源地址SA (Source Address) 占4字節(jié)。（12）目的地址DA (Destination Address) 占4字節(jié)。 源、目的地址字段都包括網(wǎng)絡(luò)地址和主機地址。,IP地址的可變部分包括多個選項字段。選項字段用來支持排錯、

10、安全、源路由、路由記錄、時間標記等功能。增加首部的可變部分是為了增加IP數(shù)據(jù)報的功能，但這同時也使得IP數(shù)據(jù)報的首部長度成為可變的。這就增加了每一個路由器處理數(shù)據(jù)報的開銷。實際上這些選項很少被使用。,IP數(shù)據(jù)報首部中的各字段（五）,,11,7.1.2 分類的IP地址,,12,IP地址的表示方法及特點,,13,7.1.3 IP地址與硬件地址,,14,7.1.4 地址解析及逆向地址解析協(xié)議,主機不知道IP地址對應(yīng)的硬件地址時，使用地

11、址解析協(xié)議ARP，ARP根據(jù)IP地址獲取硬件地址。過程為：1.主機A在局域網(wǎng)上廣播ARP請求，要求獲知主機B的IP地址對應(yīng)的硬件地址。2.局域網(wǎng)上的所有主機都會收到ARP請求分組。3.主機B識別ARP請求中自己的IP地址,向主機A發(fā)送ARP響應(yīng)分組,通知B的硬件地址。4.主機A收到ARP響應(yīng)分組后,在ARP緩存中寫入B的IP地址及對應(yīng)的硬件地址。,,15,ARP及RARP（續(xù)）,ARP解決同一個局域網(wǎng)上的主機或路由器IP地址映射

12、問題。 IP地址與硬件地址的映射表保存在ARP高速緩存器中，主機或路由器想要通過IP地址獲知硬件地址時，首先要查找地址映射表，如果沒有要求的地址映射關(guān)系，則發(fā)送ARP請求分組。 高速緩存中的每個映射地址項目都設(shè)置生存時間，以防止硬件地址改變致使表中的映射關(guān)系出錯。 為什么要用IP地址而不直接使用硬件地址？ 異構(gòu)網(wǎng)絡(luò)使用不同的硬件地址，要使他們相互通信必須進行復(fù)雜的硬件地址轉(zhuǎn)換。采用統(tǒng)一的IP地址就解決了這

13、個復(fù)雜問題。 RARP協(xié)議可以通過硬件地址獲知IP地址。,,16,7.1.5 IP層轉(zhuǎn)發(fā)分組的流程,（1）從分組的首部提取目的站D的IP地址，得出目的網(wǎng)絡(luò)地址為N；（2）若N就是與此路由器直接相連的某個網(wǎng)絡(luò)地址，則直接通過該網(wǎng)絡(luò)將分組交付給目的站D（這里包括將目的主機IP地址D轉(zhuǎn)換為具體的硬件地址，將分組封裝為MAC幀，再發(fā)送此幀）；否則，執(zhí)行（3）；（3）若路由表中有目的地址為D的特定主機路由，則將分組傳送給路由表中所

14、指明的下一跳路由器；否則，執(zhí)行（4）；（4）若路由表中有到達網(wǎng)絡(luò)N的路由，則將分組傳送給路由表中所指明的下一跳路由器；否則，執(zhí)行（5）；（5）若路由表中有一個默認路由，則將數(shù)據(jù)報傳送給路由表中所指明的默認路由器；否則，執(zhí)行（6）；（6）報告轉(zhuǎn)發(fā)分組出錯 。,,17,7.2無分類編址與最長前綴匹配,7.2.1 無分類編址CIDR 7.2.2 最長前綴匹配,分類IP地址面臨的問題： 1. B類地址1994年就分配完畢；

15、 2. 骨干網(wǎng)路由器中路由表表項數(shù)目急劇增長； 3. IPv4地址空間將被耗盡。 IETF使用無分類編址CIDR解決前兩個問題，使用IPv6解決第三個問題。,,18,7.2.1 無分類編址CIDR,無分類編址CIDR(Classless Inter-domain Routing)可以使用各種長度的網(wǎng)絡(luò)前綴代替分類地址中的網(wǎng)絡(luò)號，消除了傳統(tǒng)的A類、B類和C類地址概念，可以更加有效地分配IPv4的地址空間。

16、 CIDR的IP地址表示法如下： IP地址::＝{,} CIDR采用斜線記法表示IP地址：128.14.46.34/20. 斜線后的數(shù)字表示網(wǎng)絡(luò)前綴所占的比特數(shù)。,,19,無分類編址中的塊地址,CIDR將網(wǎng)絡(luò)前綴相同的連續(xù)IP地址組成CIDR塊。CIDR塊也可用斜線標記法表示，如128.14.32.0/20表示的地址塊共有212個地址。斜線前的數(shù)字表示地址塊的起始地址，斜線后的數(shù)字

17、表示網(wǎng)絡(luò)前綴的比特數(shù)。 最小地址 128.14.32.0 10000000 00001110 00100000 00000000 最大地址 128.14.47.255 10000000 00001110 00101111 11111111 一個地址塊可以表示很多地址，路由表可以使用地

18、址塊來查找目的網(wǎng)絡(luò)。 CIDR使用“掩碼”與IP地址逐位相與，來分離長度可變的網(wǎng)絡(luò)前綴，對于/20地址塊，掩碼是11111111 11111111 11110000 00000000（20個連續(xù)的1）。,,20,CIDR塊地址的其他表示方法,將點分制中低位中連續(xù)的0省略：10.0.0.0/10可簡 寫為10/10 。2. 直接使用二進制：例如，10.0.0.0/10可寫為： 00001010 00

19、xxxxxx xxxxxxxx xxxxxxxx，3. 在網(wǎng)絡(luò)前綴后加星號*，如：00001010 00﹡ ，星號﹡表示IP地址中的主機號，可以是任意值 。,使用CIDR可以有效地利用IPv4地址空間，相比有分類的編址方式，可以有效地節(jié)省IP地址。,,21,CIDR塊地址的分配舉例,,22,7.2.2 最長前綴匹配,使用CDIR后，路由表的每個表項由目的地址的網(wǎng)絡(luò)前綴和下一跳地址組成。 當(dāng)路由表中包含一個網(wǎng)絡(luò)和它的子網(wǎng)時，使

20、用網(wǎng)絡(luò)前綴查找會得到不止一個匹配結(jié)果，應(yīng)該從匹配結(jié)果中選擇最長前綴匹配的路由。 在前面的例子中，大學(xué)下屬的四系希望把分組直接轉(zhuǎn)發(fā)給四系，而不經(jīng)大學(xué)的路由器。假設(shè)收到目的地址為D=206.0.71.130，將D和路由表中（大學(xué)，四系）這兩個項目的掩碼逐比特相“與”： 將D和11111111 11111111 11111100 00000000逐比特相“與”=206.0.68.0/22 匹配。 D

21、和11111111 11111111 11111111 10000000逐比特相“與”=206.0.71.128/25 匹配。 根據(jù)最長前綴匹配原理，應(yīng)選擇后者，將收到的分組轉(zhuǎn)發(fā)給四系。,,23,7.3 互聯(lián)網(wǎng)的路由協(xié)議,互聯(lián)網(wǎng)采用的路由選擇策略主要是自適應(yīng)的、分布式路由選擇策略。 互聯(lián)網(wǎng)的路由協(xié)議，包括路由選擇算法和路由信息傳送及處理協(xié)議。路由選擇算法常用的是Dijkstra提出的“最短路徑算法”。這里

22、將重點討論幾種常用的路由信息傳送及處理協(xié)議，也就是討論路由表中的路由表項是怎樣產(chǎn)生和更新的。,7.3.1 路由協(xié)議概述7.3.2 自治系統(tǒng)內(nèi)部路由協(xié)議RIP7.3.3 自治系統(tǒng)內(nèi)部路由協(xié)議OSPF7.3.4 自治系統(tǒng)間的路由協(xié)議,,24,7.3.1 路由協(xié)議概述,互聯(lián)網(wǎng)采用分層次的路由選擇策略，這是因為：（1）互聯(lián)網(wǎng)的規(guī)模非常大，如果讓所有的路由器知道所有的網(wǎng)絡(luò)應(yīng)怎樣到達，則這種路由表將非常大，所有這些路由器之間交換路

23、由信息所需的帶寬就會使互聯(lián)網(wǎng)的通信鏈路飽和。（2）許多單位不愿意外界了解自己單位網(wǎng)絡(luò)的布局細節(jié)和本部門所采用的路由協(xié)議，但又希望連接到互聯(lián)網(wǎng)上。 為此，整個互聯(lián)網(wǎng)被劃分為許多自治系統(tǒng)，一般簡稱為AS。一個自治系統(tǒng)是一個較小的互聯(lián)網(wǎng)，其最重要的特點就是自治系統(tǒng)有權(quán)自主地決定在本系統(tǒng)內(nèi)應(yīng)采用何種路由協(xié)議。,,25,互聯(lián)網(wǎng)把路由協(xié)議劃分為兩大類： (1) 內(nèi)部網(wǎng)關(guān)協(xié)議IGP(Interior Gateway Proto

24、col) 更確切的稱為“自治系統(tǒng)內(nèi)部的路由協(xié)議”，目前這類路由協(xié)議使用得最多，如RIP和OSPF協(xié)議。 (2) 外部網(wǎng)關(guān)協(xié)議EGP(External Gateway Protocol) 更確切的稱為“自治系統(tǒng)之間的路由協(xié)議”，在外部網(wǎng)關(guān)協(xié)議中目前使用最多的是BGP-4。 自治系統(tǒng)之間的路由選擇也叫做域間路由選擇（interdomain routing），而在自治系統(tǒng)內(nèi)部的路由選

25、擇叫做域內(nèi)路由選擇（intradomain routing）。,IGP 和 EGP,,26,,自治系統(tǒng)和網(wǎng)關(guān)協(xié)議,關(guān)于名詞“路由器”和“網(wǎng)關(guān)”。,,27,7.3.2 自治系統(tǒng)內(nèi)部路由協(xié)議RIP,RIP（Routing Information Protocol）是一種分布式的基于距離向量算法的路由協(xié)議(內(nèi)部網(wǎng)關(guān)協(xié)議)，是互聯(lián)網(wǎng)的標準協(xié)議之一，其最大優(yōu)點就是簡單。,一、工作原理,RIP的“距離”定義 ：從一路由器到直接連接的網(wǎng)絡(luò)的距離定義為

26、1；從一路由器到非直接連接的網(wǎng)絡(luò)的距離定義為所經(jīng)過的路由器數(shù)加1。 RIP協(xié)議的“距離”也稱為“跳數(shù)”（hop count），因為每經(jīng)過一個路由器，跳數(shù)就加1。 RIP允許一條路徑最多只能包含15個路由器?？梢奟IP只適用于規(guī)模較小的自治系統(tǒng)。,,28,路由信息的交換,RIP的特點是每一個路由器都要不斷地和其它一些路由器交換路由信息。那么，與哪些路由器交換信息？交換什么信息？在什么時候交換信息？ RIP規(guī)

27、定：（1）每個路由器只與相鄰路由器交換信息。（2）交換的信息是當(dāng)前本路由器所知道的全部路由信息，即自己的路由表。（3）按固定的時間間隔交換路由信息。當(dāng)網(wǎng)絡(luò)拓撲發(fā)生變化時，及時向鄰路由器通告變化后的路由信息。 路由表中最主要的信息是：到某個網(wǎng)絡(luò)的距離（即最短距離），以及應(yīng)經(jīng)過的下一跳地址。路由表更新的原則是找出到每個目的網(wǎng)絡(luò)的最短距離。這種更新算法又稱為距離向量算法。,,29,RIP采用特定格式的報文來傳送路由信息。

28、距離向量算法的基礎(chǔ)是：設(shè)X是結(jié)點A到B的最短路徑上的一個結(jié)點。若將路徑A→B拆成兩段路徑A→X和X→B，則每一段路徑A→X和X→B也都分別是結(jié)點A到X和結(jié)點X到B的最短路徑。 RIP協(xié)議讓所有路由器都和自己的相鄰路由器不斷交換路由信息，并不斷更新其路由表，使得從每一個路由器到每一個目的網(wǎng)絡(luò)的路由都是最短的。 這里應(yīng)注意：雖然所有的路由器最終都擁有了整個自治系統(tǒng)的全局路由信息，但由于每一個路由器的位置不同，

29、它們的路由表是不同的。,二、距離向量算法,,30,,,,距離向量算法的路由表舉例,圖中給出了一個簡單的網(wǎng)絡(luò)拓撲，共有6個網(wǎng)絡(luò)通過6個路由器互連。路由表中的每一行包括：目的網(wǎng)絡(luò)、最短距離、下一跳路由器。,,31,RIP報文由首部和路由部分組成。新版本RIP2和RIP1的首部相同，但路由部分不同。,三、RIP協(xié)議的報文格式,,RIP的首部占4個字節(jié)，其中的命令字段指出報文的意義。例如1表示“請求路由信息”；2表示對“請求路由信息”的響應(yīng)或主

30、動發(fā)出的“路由更新”報文。后部的“必為0”是為了填滿4字節(jié)。,,32,RIP2報文中的路由部分由若干個路由信息元素組成。每個路由信息元素需要20個字節(jié)。地址族標識符字段用來標識所使用的地址協(xié)議。路由標記填入自治系統(tǒng)的號碼。再后面指出某個網(wǎng)絡(luò)地址、該網(wǎng)絡(luò)地址的掩碼、下一跳路由器地址以及到此網(wǎng)絡(luò)的距離。 一個RIP報文的最大長度是504字節(jié)。如路由信息元素的數(shù)目超過25，則必須再用一個RIP報文來傳送。 RI

31、P存在的一個問題是：“好消息傳播得快，而壞消息傳播得慢”。為了使壞消息傳播得更快些，可以采取多種措施。例如，讓路由器記錄收到某特定路由信息的接口，而不讓同一路由信息再通過此接口向反方向傳送。,RIP2報文中的路由部分,,33,OSPF（Open Shortest Path First）譯為開放最短路徑優(yōu)先?！伴_放”表明OSPF協(xié)議是公開發(fā)表的，“最短路徑優(yōu)先”是因為使用了Dijkstra的最短路徑算法。 OSPF

32、的版本OSPF2已成為互聯(lián)網(wǎng)標準協(xié)議。 OSPF最主要的特征是使用分布式的鏈路狀態(tài)協(xié)議(Link State Protocol)，而不是RIP的距離向量協(xié)議。,7.3.3 自治系統(tǒng)內(nèi)部路由協(xié)議OSPF,RIP協(xié)議的缺點限制了網(wǎng)絡(luò)的規(guī)模，對于規(guī)模較大的自治系統(tǒng)應(yīng)當(dāng)使用OSPF協(xié)議。,一、OSPF協(xié)議的基本特點,,34,和RIP協(xié)議相比，OSPF的三個要點如下： （1）每個路由器向本自治系統(tǒng)中所有路由器發(fā)送路由信息。這里使

33、用的方法是洪泛法（flooding），路由器通過所有輸出端口向所有相鄰的路由器發(fā)送信息。（2）發(fā)送的路由信息是與本路由器相鄰的所有路由器的鏈路狀態(tài)。所謂“鏈路狀態(tài)”就是說明本路由器都和哪些路由器相鄰，以及該鏈路的“度量”（代價）。OSPF將這個“度量”用來表示費用、距離、時延、帶寬等。（3）只有當(dāng)鏈路狀態(tài)發(fā)生變化時，路由器才用洪泛法向所有路由器發(fā)送此信息。,OSPF 的三個要點,,35,由于各路由器之間頻繁地交換鏈路狀態(tài)信息，所有的

34、路由器最終都能建立一個鏈路狀態(tài)數(shù)據(jù)庫（link-state database），這個數(shù)據(jù)庫實際上就是全網(wǎng)的拓撲結(jié)構(gòu)圖。這個拓撲結(jié)構(gòu)圖在全網(wǎng)范圍內(nèi)是一致的。每一個路由器使用鏈路狀態(tài)數(shù)據(jù)庫中的數(shù)據(jù)，使用Dijkstra算法，生成自己的路由表。 RIP的每一個路由器雖然知道到所有的網(wǎng)絡(luò)的距離以及下一跳路由器，但卻不知道全網(wǎng)的拓撲結(jié)構(gòu)。 OSPF的鏈路狀態(tài)數(shù)據(jù)庫能較快地進行更新，使各個路由器能及時更新其路由表。O

35、SPF的更新過程收斂得快是其重要優(yōu)點。,OSPF 的路由表,,36,為了使OSPF能夠用于規(guī)模很大的網(wǎng)絡(luò)，OSPF將一個自治系統(tǒng)再劃分為若干個更小的范圍，叫作區(qū)域(Area)。劃分區(qū)域的好處是將洪泛法交換鏈路狀態(tài)信息的范圍局限于每一個區(qū)域，這就減少了整個網(wǎng)絡(luò)上的通信量。 為了使每一個區(qū)域能夠和本區(qū)域以外的區(qū)域進行通信，OSPF使用層次結(jié)構(gòu)的區(qū)域劃分。在上層的區(qū)域叫作主干區(qū)域，主干區(qū)域的作用是用來連通其它在下層的區(qū)域。從其

36、它區(qū)域來的信息都由區(qū)域邊界路由器(area border router)進行概括。在主干區(qū)域內(nèi)還要有一個路由器專門和本自治系統(tǒng)外的其它自治系統(tǒng)交換路由信息，這樣的路由器叫做自治系統(tǒng)邊界路由器。,OSPF 區(qū)域的劃分,,37,二、OSPF 報文,,,38,類型1 問候報文，用來發(fā)現(xiàn)鄰站和確定鄰站可達性。類型2 數(shù)據(jù)庫描述報文，向鄰站給出自己的鏈路狀態(tài)數(shù)據(jù)庫中的所有鏈路狀態(tài)項目的摘要信息。類型3 鏈路狀態(tài)請求報文，向?qū)Ψ秸埱蟀l(fā)送某些鏈路

37、狀態(tài)項目的詳細信息。類型4 鏈路狀態(tài)更新報文，用洪泛法對全網(wǎng)更新鏈路狀態(tài)。這種報文是最復(fù)雜的，也是OSPF協(xié)議最核心的部分。路由器使用這種報文將其鏈路狀態(tài)通知給鄰站。類型5 鏈路狀態(tài)確認報文，對鏈路更新報文的確認。 OSPF規(guī)定，每兩個相鄰路由器每隔10秒鐘要交換一次問候報文。這樣就能確知哪些鄰結(jié)點是可達的。其它的四種報文都是用來進行鏈路狀態(tài)數(shù)據(jù)庫的同步。,五種類型的OSPF報文,,39,三、從鏈路狀態(tài)數(shù)據(jù)庫得到路由

38、表,,每一種網(wǎng)絡(luò)都可能帶有多個路由器。下圖是包括路由器、局域網(wǎng)和廣域網(wǎng)三種網(wǎng)絡(luò)連接的一個自治系統(tǒng)的網(wǎng)絡(luò)拓撲。每一條鏈路的旁邊標注了“代價”（距離、時延等）。,,40,OSPF通過各路由器之間交換鏈路狀態(tài)信息，得出鏈路狀態(tài)數(shù)據(jù)庫?？梢杂孟聢D所示的有向圖表示該數(shù)據(jù)庫。其中每一個路由器、局域網(wǎng)或廣域網(wǎng)都抽象為一個結(jié)點，而每條鏈路用兩條不同方向的邊表示。,,鏈路狀態(tài)數(shù)據(jù)庫,,41,每個路由器中的路由表可從鏈路狀態(tài)數(shù)據(jù)庫導(dǎo)出。例如，要計算路由器F

39、的路由表，可先算出如下圖所示的以F為根的最短路徑樹，根據(jù)最短路徑樹就很容易地得出路由表來。,,,,,A,B,D,F,E,G,I,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,W4,5,L1,3,4,12,7,8,6,16,W5,W1,8,W2,W3,3,L2,4,W6,12,2,最短路徑樹和路由表,,42,7.3.4 自治系統(tǒng)間的路由協(xié)議,,,43,一、路徑向量路由選擇法,RIP中應(yīng)用的距離向

40、量協(xié)議和OSPF中采用的鏈路狀態(tài)協(xié)議作為域間路由協(xié)議都不是很有效，都存在各種各樣的問題。 BGP的關(guān)鍵特性是它采用了一種叫做路徑向量路由選擇的技術(shù)。它舍棄了“距離”、“鏈路狀態(tài)”等路由度量信息，只是簡單地提供一個路由器要跨越哪些自治系統(tǒng)到達各個網(wǎng)絡(luò)的路徑信息。 這個方法與距離向量算法有兩點不同：（1）路徑向量方法不包括距離或代價的估計值；（2）每個路由信息塊列出路由器沿著某路徑到達目的網(wǎng)絡(luò)要經(jīng)過的所有自治

41、系統(tǒng)。,,44,二、邊界網(wǎng)關(guān)協(xié)議,BGP的設(shè)計目標是使不同自治系統(tǒng)中的BGP路由器能夠互相協(xié)作、交換路由信息（在該標準中路由器稱為網(wǎng)關(guān)）。協(xié)議的運行要交換一些報文，這些報文通過TCP連接傳送。下面給出了BGP-4 報文的一覽表。,BGP包括三個功能性過程： ● 鄰站捕獲 （ 發(fā)送Open ，響應(yīng) Keepalive ） ● 鄰站可達性 （ 周期性發(fā)送 Keepalive ） ● 網(wǎng)絡(luò)可達

42、性 （ 廣播發(fā)送 Update ）,,45,鄰站捕獲：不同自治系統(tǒng)的相鄰路由器，稱為鄰站。它們之間需要交換路由信息。為此，首先必須執(zhí)行鄰站捕獲過程。為實現(xiàn)鄰站捕獲，一個路由器向另一個路由器發(fā)送Open報文，后者可以接受也可以拒絕前者的請求。如果接受，它就回送一個Keepalive報文以示響應(yīng)。 鄰站可達性：鄰站的每一方都需要確信對方仍然存在且致力于保持鄰站關(guān)系。為此，兩個路由器都要周期性地向?qū)Ψ剿蚄eepalive報文。網(wǎng)絡(luò)可達性

43、：每個路由器要保持一個數(shù)據(jù)庫，其中記錄可達的子網(wǎng)及到達該子網(wǎng)的優(yōu)選路由。只要這個數(shù)據(jù)庫的內(nèi)容發(fā)生變化，路由器就要向?qū)崿F(xiàn)BGP的其它路由器發(fā)送一個Update報文。,BGP的功能性過程,,46,下圖為一個BGP路由器的集合，假設(shè)路由器F到D的的路徑是FGCD，其鄰居給它完整路徑信息，為了簡便，只將目的地D的信息列出如下：,送給F的信息來自B：“我使用 BCD”來自G：“我使用 GCD”來自 I：“我使用 IFGCD”來自E：“我使

44、用 EFGCD”,路由器F檢測哪條路徑是最佳的，馬上丟棄從I和E來的路徑。然后在B和G之間選用距離最短的路徑。 BGP很容易解決困擾其它算法的無窮計算問題。,BGP路由選擇舉例,,47,7.4 下一代互聯(lián)網(wǎng)的網(wǎng)際協(xié)議IPv6,互聯(lián)網(wǎng)的巨大成功使得互聯(lián)網(wǎng)的覆蓋范圍和用戶數(shù)迅猛增長，同時也暴露了現(xiàn)行的網(wǎng)際協(xié)議IPv4存在的問題和即將出現(xiàn)的問題，IETF早在1992年就著手開發(fā)IP新版本，現(xiàn)正式稱為IPv6。

45、IPv6提供了極大的地址空間，增加了地址分配的靈活性；在安全性方面有較大改進；在改善QoS方面有較多的準備。,7.4.1 IPv6 分組的格式7.4.2 IPv6 地址7.4.3 從 IPv4 到 IPv6,,48,7.4.1 IPv6分組的格式,IPv6分組由基本首部(Base Header)和載荷(Payload)部分組成(如下圖)。載荷部分包括可選的擴展首部(Extension Header)和數(shù)據(jù)（Data）部分。,

46、IPv6分組基本首部的長度固定為40字節(jié)，其長度是IPv4分組首部的兩倍，但字段數(shù)減到8個。右圖示出了IPv6分組基本首部的結(jié)構(gòu)。,一、IPv6分組的基本首部,,49,(1) 版本 占4bit。它指明協(xié)議的版本號，IPv6該字段是6。(2) 業(yè)務(wù)類別 占8bit。用于標識和區(qū)分不同的業(yè)務(wù)類型或IPv6分組的優(yōu)先級。(3) 流標記 占20bit。一個流由非零的20bit流標記及其源地址與目的地址惟一地標識。(4) 載荷長度 占16

47、bit。它指明IPv6分組跟在基本首部后面的擴展首部和數(shù)據(jù)部分的長度(字節(jié)數(shù))。(5) 下一個首部 占8bit。它標識緊接在基本首部后面的下一個首部的類型。(6) 跳數(shù)限制 占8bit。防止IP分組在網(wǎng)絡(luò)中無限期地存在下去。(7) 源地址（SA） 占128bit。這是發(fā)送分組的站點的IP地址。(8) 目的地址（DA） 占128bit。最終接收分組的站點的IP地址。,基本首部各個字段的功能,,50,IPv6將原來IPv4分組首部的

48、選項功能放在擴展首部中，并將有些擴展首部留給路徑端點的主機去處理，而分組傳送途中經(jīng)過的路由器都不處理這些擴展首部(逐跳選項首部和路由選擇首部除外)，這樣就能顯著提高路由器的處理效率。 目前，IPv6有以下六種擴展首部，它們分別是： ① 逐跳選項首部，承載由沿途路由器處理的選項信息； ② 路由選擇首部，包含IPv6分組去往目的結(jié)點的途中將要經(jīng)過的中間結(jié)點的清單 ，用于源路由方式； ③ 分片首部，用于IP

49、數(shù)據(jù)報的分片傳送 ； ④ 認證首部，用于安全； ⑤ 封裝安全載荷首部； ⑥ 目的結(jié)點選項首部， 承載由分組的目的結(jié)點處理的選項 。,二、IPv6分組的擴展首部,,51,7.4.2 IPv6地址,IPv6的地址空間幾乎是無限的，與IPv4一樣，IPv6的地址也是分配給結(jié)點的每個接口，而不是分配給結(jié)點本身。這里的結(jié)點，指的是運行IPv6協(xié)議的端結(jié)點（主機）和中繼結(jié)點（路由器）。不同的是，IPv6允許單個接口可以有多個不同

50、的單播地址，對應(yīng)于一個結(jié)點接口的任何單播地址都可以用來標識那個結(jié)點。 采用長地址，加上每個接口有多個地址可以改善路由選擇的效率。較長的IP地址允許地址的匯聚，按照網(wǎng)絡(luò)的層次、業(yè)務(wù)運營商、地理范圍、不同的企業(yè)等進行匯聚。這樣的匯聚將縮小路由表的規(guī)模，從而加快路由表項的查找。每個接口有多個地址，這些地址分別匯聚在不同運營商的地址空間，將使用戶能夠通過同一接口使用多個運營商提供的業(yè)務(wù)。,,52,IPv6分組的目的地址有如下三種

51、基本類型：（1）單播(Unicast)地址 標識單個結(jié)點的接口。（2）多播(Multicast)地址 標識一組接口（一般屬于不同的結(jié)點）。（3）任播(Anycast)地址 標識一組接口（一般屬于不同的結(jié)點）。 IPv6地址采用了一種新的符號來表示。128bit的地址碼分成8組，每組含4個十六進制數(shù)，它們之間用冒號隔開。例如 8000:0000:0000:0000:0123:4567:89AB:CDEF

52、 由于許多地址的內(nèi)部有許多零，可以采用零壓縮表示，且全為零的組可以省略，而用一對冒號代替。這樣上述地址可以寫成：8000::123:4567:89AB:CDEF,IPv6地址類型和地址的表示,,53,7.4.3 從 IPv4 到 IPv6,一、IPv6與IPv4的比較,IPv6克服了IPv4存在的不足，增加了新的功能，與互聯(lián)網(wǎng)的其它協(xié)議兼容。IPv6的主要特征歸納如下：(1) IPv6分組首部的地址字段為16字節(jié)，比IPv4

53、的4字節(jié)長得多，徹底解決了地址空間不足的問題。(2) IPv6簡化了分組的基本首部（減為8個字段）。(3) IPv6通過分組的擴展首部更好的支持選項功能。(4) IPv6在安全性方面有較大改進。認證和保密是IPv6的關(guān)鍵特征。(5) IPv6在改善QoS方面有較多的準備。分組首部的業(yè)務(wù)類別和流標記字段可以支持資源預(yù)留、區(qū)分服務(wù)等改善QoS的措施。,,54,IPV6與IPv4是不兼容的，在目前的互聯(lián)網(wǎng)中使用IPv4的結(jié)點數(shù)量非常巨

54、大。因此，從IPv4發(fā)展到IPv6，只能采取逐步演進，即共存過渡的策略。下面介紹兩種向IPv6過渡的策略。（1）雙協(xié)議棧 在完全過渡到IPv6之前，使一部分路由器裝有兩個協(xié)議棧，一個IPv4和一個IPv6。雙協(xié)議棧路由器既能與IPv6系統(tǒng)通信，又能與IPv4系統(tǒng)通信。當(dāng)然，有的主機也可以裝雙協(xié)議棧，它們既可接入IPv4網(wǎng)絡(luò)，也可接入IPv6網(wǎng)絡(luò)。（2）隧道技術(shù) 這種方法的基本思想是：將IPv6分組裝入IPv4分組的數(shù)據(jù)部分，由IPv

55、4分組運載IPv6分組通過IPv4的網(wǎng)絡(luò)(IPv6 over IPv4)。在這種情況下IPv4分組所經(jīng)過的路徑就是運載IPv6分組的“隧道”。,二、從IPv4向IPv6過渡,,路由器是互聯(lián)網(wǎng)核心設(shè)備，完成分組的路由選擇和轉(zhuǎn)發(fā)功能。本節(jié)主要介紹高性能(大容量、線速）路由器的分組轉(zhuǎn)發(fā)技術(shù)。,7.5 路由器體系結(jié)構(gòu)及關(guān)鍵技術(shù),7.5.1 路由器體系結(jié)構(gòu)的發(fā)展7.5.2 路由器的基本結(jié)構(gòu)7.5.3 高性能路由器關(guān)鍵技術(shù)概述7.5.

56、4 線速緩存技術(shù)7.5.5 路由快速查找技術(shù)7.5.6 高性能路由器內(nèi)部交換網(wǎng)絡(luò)結(jié)構(gòu)7.5.7 路由器內(nèi)部交換網(wǎng)絡(luò)采用的交換機制,55,本節(jié)的主要內(nèi)容,,7.5.1 路由器體系結(jié)構(gòu)的發(fā)展,從網(wǎng)絡(luò)接口卡NIC輸入的分組，存入共享緩存，CPU為分組選擇路由，分組再經(jīng)總線到NIC輸出。,路由器的體系結(jié)構(gòu)發(fā)展經(jīng)歷了4個階段：1）單機集中式總線結(jié)構(gòu)；2）單機分布式共享總線結(jié)構(gòu)；3）單機分布式Crossbar結(jié)構(gòu)；4）多機互連集群結(jié)

57、構(gòu)。,56,CPU與總線是制約單機集中式總線結(jié)構(gòu)路由器性能的瓶頸，這種結(jié)構(gòu)的交換容量通常小于0.5Gb/s。,一、單機集中式總線結(jié)構(gòu),,二、單機分布式共享總線結(jié)構(gòu),57,,前面三代路由器結(jié)構(gòu)的變遷，是系統(tǒng)逐步并行化的過程，先從集中式處理到與主板分離的多個線卡的并行處理，然后到多條數(shù)據(jù)通道的并行傳輸。,58,三、單機分布式Crossbar結(jié)構(gòu),線卡間分組的交換由crossbar完成。crossbar中，不同的輸入端口可以同時向不同的輸出端

58、口傳送分組，分組并行傳送的能力得到提高。這種結(jié)構(gòu)的系統(tǒng)容量達幾十到上百Gb/s。,,四、多機互連的集群結(jié)構(gòu),多臺路由器按照一定的結(jié)構(gòu)連接在一起，可以擴展接口的數(shù)量，提高交換容量。但是需要占用接口來進行路由器之間的互連，而且這種連接方式不便于管理。,59,如果路由器可以根據(jù)需求進行交換容量的在線擴展，則可以解決路由器交換容量和需求之間的尖銳矛盾。于是可擴展的路由器結(jié)構(gòu)應(yīng)運而生。在這種路由器體系結(jié)構(gòu)中，多個機柜可以通過內(nèi)部連接整合成一個新的

59、大型路由器，或者叫做路由器集群。,,,60,7.5.2 路由器的基本結(jié)構(gòu),路由器分為路由選擇部分和分組轉(zhuǎn)發(fā)部分，路由選擇部分的作用是執(zhí)行路由協(xié)議，建立和更新路由表。分組轉(zhuǎn)發(fā)部分包括交換網(wǎng)絡(luò)和輸入、輸出端口，完成分組的轉(zhuǎn)發(fā)。,,每個輸入端口都有一個轉(zhuǎn)發(fā)表，轉(zhuǎn)發(fā)表從路由表中得到。轉(zhuǎn)發(fā)表的每個表項包含要到達的目的網(wǎng)絡(luò)地址、相應(yīng)的輸出端口號、MAC地址。轉(zhuǎn)發(fā)表常用硬件實現(xiàn)，以確保高速轉(zhuǎn)發(fā)。 輸入端口對輸入的分組要依次進行物理

60、層、數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層的處理。如果分組是攜帶路由信息的分組，則將分組送至路由選擇部分處理，如果分組是數(shù)據(jù)分組，根據(jù)分組首部目的IP地址查轉(zhuǎn)發(fā)表，決定分組的輸出端口。 交換網(wǎng)絡(luò)把分組輸出到相應(yīng)的輸出端口。輸出端口將分組裝幀，在物理層完成處理后，以比特流輸出。,61,路由器結(jié)構(gòu)及分組轉(zhuǎn)發(fā)過程,,在輸入端口中得不到及時處理，或者發(fā)生輸出端口沖突的分組在輸入緩存中存儲。當(dāng)交換網(wǎng)絡(luò)發(fā)送分組的速率大于輸出鏈路速率時，分組在輸出緩存存

61、儲。,62,路由器中的輸入/輸出緩存,分組在路由器的輸入端口和輸出端口都可能會在隊列中排隊等候處理。若輸入或輸出隊列發(fā)生溢出，就會造成分組的丟失。,,63,7.5.3 高性能路由器關(guān)鍵技術(shù)概述,高性能路由器，主要是指大容量、線速路由器。 對于高性能路由器來說，其高速處理能力幾乎貫穿路由器的每一個實現(xiàn)環(huán)節(jié)，如路由表的查找、內(nèi)存的訪問、分組的調(diào)度等。 新一代高性能核心路由器的體系結(jié)構(gòu)通常都是基于集群結(jié)構(gòu)設(shè)計的

62、，內(nèi)連網(wǎng)絡(luò)的性能直接影響路由器集群的整體交換性能。為了減小分組在內(nèi)連網(wǎng)絡(luò)中經(jīng)歷的時延，可以采用不同的交換機制，目前研究較多的交換機制包括分組交換、蟲孔交換和虛切通交換。 下面將詳細敘述高性能路由器涉及的關(guān)鍵技術(shù)問題。這些技術(shù)包括線速緩存、轉(zhuǎn)發(fā)表快速查找、內(nèi)連網(wǎng)絡(luò)結(jié)構(gòu)及交換機制等。,,路由器輸入鏈路速率的不斷提高，給緩存器提出兩個要求：讀寫速率高和存儲容量大。 輸入鏈路速率為40G/s，分組長度為40字節(jié)時，存

63、儲器讀寫一個分組的時間是4ns。 緩存器的容量要能滿足網(wǎng)絡(luò)內(nèi)擁塞控制機制的要求：互聯(lián)網(wǎng)中源端對于擁塞控制的響應(yīng)時間為端到端往返時間RTT。設(shè)路由器輸入鏈路的速率為R，在此期間，路由器收到的比特數(shù)可能會達到R×RTT。為防丟失，緩存器容量應(yīng)為R×RTT。當(dāng)R=40G/s，RTT=0.25s時，需要緩存器容量為1.25G字節(jié)。 SRAM速率快、容量小，DRAM容量大、速率低。,64,7.5.

64、4 線速緩存技術(shù),,對DRAM數(shù)據(jù)線并行擴展時，不同的DRAM塊地址總線是相同的。圖中一次向一個地址要讀寫320字節(jié)的數(shù)據(jù)。一次有可能向DRAM塊中寫入兩個分組。但如果兩個分組要寫入兩個隊列，就不能使用一個地址。為解決這一問題，需要采用DRAM/SRAM混合結(jié)構(gòu)。,65,DRAM的并行讀寫,通過對多塊DRAM的并行讀寫，可以提高DRAM的讀寫速率。,,66,SRAM/DRAM混合結(jié)構(gòu),SRAM和DRAM都分為Q個隊列，SRAM與DRA

65、M之間的數(shù)據(jù)寬度b=2RT 。,使用混合結(jié)構(gòu)，可以分隊列存儲分組。SRAM可線速讀寫，用來暫存分組，輸入的分組先寫入SRAM尾部隊列，再由SRAM寫入DRAM。輸出分組時，先把分組從DRAM讀出到SRAM頭部隊列，再由SRAM輸出。,,67,7.5.5 路由快速查找技術(shù),隨著路由器接口速度的不斷提高，使用軟件方法實現(xiàn)高速路由查找越來越困難。目前已經(jīng)廣泛使用的STM-16(2.5Gbps)和STM-64(10Gbps)接口要求路由查找速

66、度達到每秒幾千萬次，因此，需要用硬件實現(xiàn)高速路由查找。 查找路由表，就要讀存放路由表的存儲器，讀存儲器需要時間，減少查表過程中讀存儲器的次數(shù)，是提高查找速度的關(guān)鍵。 下面介紹2種基于硬件的路由查找技術(shù)： 1）基于DRAM的路由查找算法－DIR-24-8-BASIC算法 ； 2）基于CAM的路由查找算法 。,,DIR-24-8-BASIC算法 (1),第二個表稱為TBLlon

67、g，存儲所有長度大于24的網(wǎng)絡(luò)前綴。長度小于24位網(wǎng)絡(luò)前綴查第一個表得出下一跳路由器，長度大于24位的網(wǎng)絡(luò)前綴要分別查兩個表。,68,,采用兩級DRAM表來實現(xiàn)路由查找。第一個表稱為TBL24，存儲所有長度小于等于24的網(wǎng)絡(luò)前綴，該表有224個表項，地址范圍從0.0.0到255.255.255。,,DIR-24-8-BASIC算法 (2),如果網(wǎng)絡(luò)前綴的長度大于等于24，TBL24中表項的第1位為1，后15位給出指向TBLlong表的指

68、針。查TBL24時，使用分組目的地址的前24位作為TBL24的讀地址。查TBLlong時，把查TBL24得到的指針乘256再加上分組目的地址的后8位作為TBLlong讀地址。,69,互聯(lián)網(wǎng)99%的網(wǎng)絡(luò)前綴長度小于等于24，絕大部分路由只需查一次表。網(wǎng)絡(luò)前綴長度小于24，TBL24中表項的第1位為0，后15位給出下一跳信息。,,DIR-24-8-BASIC算法 (3),70,A=10.54/16 ，A的網(wǎng)絡(luò)前綴為16位，在TBL24中一共