非連接型快速分組交換

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

2、由協(xié)議。然后在此基礎(chǔ)上講述高速路由器的結(jié)構(gòu)及實(shí)現(xiàn)快速分組交換的關(guān)鍵技術(shù)。,關(guān)于“非連接型快速分組交換”,2,,3,互聯(lián)網(wǎng)是指用路由器進(jìn)行互連的互連網(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ò)看起來(lái)像一個(gè)統(tǒng)一的網(wǎng)絡(luò)。,7.1 互聯(lián)網(wǎng)的IP協(xié)議,,4,互聯(lián)網(wǎng)使用的IP協(xié)議族，除了IP協(xié)議之外，還有四個(gè)配套的協(xié)議：地址解析協(xié)議ARP，逆地址解析協(xié)議RARP，控制報(bào)文協(xié)議ICM

3、P，組管理協(xié)議IGMP。,網(wǎng)際層協(xié)議的組成,,7.1.1 IP數(shù)據(jù)報(bào)的格式 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ù)報(bào)的格式,互聯(lián)網(wǎng)網(wǎng)際層的協(xié)議數(shù)據(jù)單元稱為數(shù)據(jù)報(bào)。一個(gè)IP數(shù)據(jù)報(bào)由首部和數(shù)據(jù)兩部分組成。首部的前一部分長(zhǎng)度固定，共20字節(jié)，是所有IP數(shù)據(jù)報(bào)必須具備的。在首部固定部分的后面是

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、和11111111 11111111 11111111 10000000逐比特相“與”=206.0.71.128/25 匹配。 根據(jù)最長(zhǎng)前綴匹配原理，應(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、將重點(diǎn)討論幾種常用的路由信息傳送及處理協(xié)議，也就是討論路由表中的路由表項(xiàng)是怎樣產(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)采用分層次的路由選擇策略，這是因?yàn)椋海?）互聯(lián)網(wǎng)的規(guī)模非常大，如果讓所有的路由器知道所有的網(wǎng)絡(luò)應(yīng)怎樣到達(dá)，則這種路由表將非常大，所有這些路由器之間交換路

23、由信息所需的帶寬就會(huì)使互聯(lián)網(wǎng)的通信鏈路飽和。（2）許多單位不愿意外界了解自己?jiǎn)挝痪W(wǎng)絡(luò)的布局細(xì)節(jié)和本部門所采用的路由協(xié)議，但又希望連接到互聯(lián)網(wǎng)上。 為此，整個(gè)互聯(lián)網(wǎng)被劃分為許多自治系統(tǒng)，一般簡(jiǎn)稱為AS。一個(gè)自治系統(tǒng)是一個(gè)較小的互聯(lián)網(wǎng)，其最重要的特點(diǎn)就是自治系統(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)的標(biāo)準(zhǔn)協(xié)議之一，其最大優(yōu)點(diǎn)就是簡(jiǎn)單。,一、工作原理,RIP的“距離”定義 ：從一路由器到直接連接的網(wǎng)絡(luò)的距離定義為

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

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

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

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

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

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

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

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

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

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

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

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

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

39、的路由表，可先算出如下圖所示的以F為根的最短路徑樹，根據(jù)最短路徑樹就很容易地得出路由表來(lái)。,,,,,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é)議都不是很有效，都存在各種各樣的問(wèn)題。 BGP的關(guān)鍵特性是它采用了一種叫做路徑向量路由選擇的技術(shù)。它舍棄了“距離”、“鏈路狀態(tài)”等路由度量信息，只是簡(jiǎn)單地提供一個(gè)路由器要跨越哪些自治系統(tǒng)到達(dá)各個(gè)網(wǎng)絡(luò)的路徑信息。 這個(gè)方法與距離向量算法有兩點(diǎn)不同：（1）路徑向量方法不包括距離或代價(jià)的估計(jì)值；（2）每個(gè)路由信息塊列出路由器沿著某路徑到達(dá)目的網(wǎng)絡(luò)要經(jīng)過(guò)的所有自治

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

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

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

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

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

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

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

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

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

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

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

52、 由于許多地址的內(nèi)部有許多零，可以采用零壓縮表示，且全為零的組可以省略，而用一對(duì)冒號(hào)代替。這樣上述地址可以寫成：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é)長(zhǎng)得多，徹底解決了地址空間不足的問(wèn)題。(2) IPv6簡(jiǎn)化了分組的基本首部（減為8個(gè)字段）。(3) IPv6通過(guò)分組的擴(kuò)展首部更好的支持選項(xiàng)功能。(4) IPv6在安全性方面有較大改進(jìn)。認(rèn)證和保密是IPv6的關(guān)鍵特征。(5) IPv6在改善QoS方面有較多的準(zhǔn)備。分組首部的業(yè)務(wù)類別和流標(biāo)記字段可以支持資源預(yù)留、區(qū)分服務(wù)等改善QoS的措施。,,54,IPV6與IPv4是不兼容的，在目前的互聯(lián)網(wǎng)中使用IPv4的結(jié)點(diǎn)數(shù)量非常巨

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

55、4分組運(yùn)載IPv6分組通過(guò)IPv4的網(wǎng)絡(luò)(IPv6 over IPv4)。在這種情況下IPv4分組所經(jīng)過(guò)的路徑就是運(yùn)載IPv6分組的“隧道”。,二、從IPv4向IPv6過(guò)渡,,路由器是互聯(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ò)采用的交換機(jī)制,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個(gè)階段：1）單機(jī)集中式總線結(jié)構(gòu)；2）單機(jī)分布式共享總線結(jié)構(gòu)；3）單機(jī)分布式Crossbar結(jié)構(gòu)；4）多機(jī)互連集群結(jié)

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

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

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

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ā)過(guò)程,,在輸入端口中得不到及時(shí)處理，或者發(fā)生輸出端口沖突的分組在輸入緩存中存儲(chǔ)。當(dāng)交換網(wǎng)絡(luò)發(fā)送分組的速率大于輸出鏈路速率時(shí)，分組在輸出緩存存

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

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

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

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

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

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

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

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