第五章網(wǎng)絡層

■網(wǎng)絡層關注的是如何將分組送達目的端，

沿路可能要經(jīng)過多個路由器。

■網(wǎng)絡層必須知道通信子網(wǎng)的拓撲結構，并

且選擇合適的路徑。

RouterCarrier'sequipment

\

H1H2

OProcessP2

ProcessP1Packet

5.1網(wǎng)絡層設計要點

5.1.1網(wǎng)絡層向傳輸層提供的服務

?網(wǎng)絡層應該向傳輸層提供哪種服務？

所提供的服務應該獨立于路由器技術

路由器的數(shù)量、類型和拓撲關系于傳輸層不可見

□傳輸層可以使用的網(wǎng)絡地址應該有一種統(tǒng)一的編址方案，可以跨

越多個LAN和WAN（異種網(wǎng)絡互連）

■兩個陣營：面向連接的服務or無連接服務

□Internet陣營

■網(wǎng)絡本質上來說是不可靠的，主機應該自己完成錯誤控制和流量控制

■網(wǎng)絡提供的服務很簡單（少量原語），但是不一定可靠

■每個分組必須攜帶完整的目標地址，每個分組在傳輸中相互獨立

□電話公司

■網(wǎng)絡應該提供可靠的，面向連接的服務，服務質量是最主要的因素。

■在數(shù)據(jù)傳輸之前應該建立連接，傳輸結束后釋放連接，路由選擇在連

接階段就確定了

■分組應該按序被遞交，差錯控制和流量控制應該由網(wǎng)絡解決

■核心問題：設計的復雜性應該放在哪里？

□用戶端設備日漸便宜，計算性能更高，并且用

戶的需求變化很大，因此網(wǎng)絡層的設計應該是

將簡單高效放在首位（傻瓜型網(wǎng)絡）

□用戶更喜歡可靠的服務，保證服務質量是網(wǎng)絡

層設計時最需要考慮的問題。因此網(wǎng)絡層的設

計應該是面向連接的，一旦連接建立成功，就

應該可以給用戶提供相應的服務質量

數(shù)據(jù)報的特點

■每個分組的尋路是獨立的，可以合理利用網(wǎng)絡資

源

■如果途中一個節(jié)點或一條鏈路發(fā)生故障，能給分

組重選路由

■分組頭需要包含地址字段，也會增加開銷

(overhead)

■各分組途經(jīng)的路徑可能不同，因此有可能出現(xiàn)先

發(fā)后到現(xiàn)象

■分組必須有生存時間限制，當生存期滿時，分組

則被拋棄，免得在網(wǎng)絡內死轉

5.1.2無連接服務的實現(xiàn)

■無連接的服務

□所有的分組(數(shù)據(jù)報，datagram)在網(wǎng)絡中的傳輸相互獨立

□每個分組需要攜帶完整的目的地址

□存儲-轉發(fā)模式(storeandforward)

ProcessP2

Dost.Line

虛電路的特點

■一條物理鏈路可以對應多條邏輯信道

■一條虛電路由各物理鏈路上的邏輯信道級聯(lián)而

成，占用了節(jié)點上的一條邏輯信道實際上就是占

用了該節(jié)點上緩存器內的一個存儲空間

■分組靠邏輯信道號(LCN)選擇路由，因LCN只

有局部意義，所以減少了分組頭標的開銷和處理

的復雜度

■能有效的防止擁塞

5.1.3面向連接服務的實現(xiàn)

■在發(fā)送數(shù)據(jù)之前，需要建立起來一條從源路由器到目標路由器之間的

跖徑，這個連鞍標為虛電路(VirtualCircuit,VC)

□虛電路必須在數(shù)據(jù)傳輸之前建立

□途徑的路由器要記錄該虛電路

□每個分組攜帶虛電路標識

ProcessP2

A'stableC*stableE*stable

H11C1A1E1C1F1

H31C2A2E2C2F2

InOut

5.1.4虛電路子網(wǎng)和數(shù)據(jù)報子網(wǎng)

IssueDatagramsubnetVirtual-circuitsubnet

CircuitsetupNotneededRequired

AddressingEachpacketcontainsEachpacketcontainsa

thefullsourceandshortVCnumber

destinationaddress

StateinformationRoutersdonotholdEachVCrequiresrouter

stateinformationaboutconnectionstablespaceperconnection

RoutingEachpacketisRoutechosenwhenVC

routedindependentlyissetup;allpackets

followit

EffectofrouterfailuresNone,exceptforpacketsAllVCsthatpassed

lostduringthecrashthroughthefailed

routerareterminated

QualityofserviceDifficultEasyifenoughresources

canbeallocatedin

advanceforeachVC

CongestioncontrolDifficultEasyifenoughresources

canbeallocatedin

advanceforeachVC

■虛電路和數(shù)據(jù)報之間的折中

□路由器的內存空間和帶寬之間的平衡

□建立虛電路所需要的時間和地址解析的時間

□保證服務質量，在子網(wǎng)內避免擁塞

□網(wǎng)絡的健壯性

5.2路由算法

■要解決的問題：確定一個進來的分組該被傳送到哪一條輸

出線路上

■路由算法(routingalgorithm)

■對于數(shù)據(jù)報子網(wǎng)，路由器必須針對每一個到達的分組重新

選擇路徑；對于虛電路子網(wǎng)，在虛電路建立的時候確定路

徑，后續(xù)的數(shù)據(jù)分組必須沿著該路徑向前傳遞

■路由(routing)和轉發(fā)(forwarding)

■對路由算法的要求：正確性，簡單性，健壯性，穩(wěn)定性，

公平性和最優(yōu)性

■公平性vs.最優(yōu)性：吞吐量和平均分組時延

ABC

A'B'C

■路由算法的分類

口非自適應的算法(nonadaptivealgorithm)：

路由選擇預先在離線的情況下計算好，在網(wǎng)絡

啟動的時候下載到路由器上(靜態(tài)路由，static

routing)

□自適應的算法(adaptivealgorithm)：根據(jù)當

前的網(wǎng)絡拓撲結構、流量變化情況實時更新路

由表中的內容(動態(tài)路由，dynamicrouting)

5.2.1優(yōu)化原則

-對最優(yōu)路徑的一般性描述：最優(yōu)化原則

(optimalityprinciple)：如臬監(jiān)甬器J在從路由

器囹路由黯K的最優(yōu)路徑上，那么，從國J的最

優(yōu)路徑也必定沿著同樣的路由路徑

■匯集樹(sinktree)：從所有的源到一個指定目

標的最優(yōu)路徑的集合組成的以目標節(jié)點為根的樹

M0M0

5.2.2最短路徑路由（靜態(tài)）

■基本思路：建立一個子網(wǎng)圖，途中的每個節(jié)點代表一個路

由器，每條弧代表一條通信線路，為了在一對給定的路由

器之間選擇一條路由路徑，只需在途中找到節(jié)點之間的最

短路徑即可

■衡量路徑最短的方法

□跳數(shù)

□物理距離

□帶寬

□平均流量

通信開銷

□平均隊列長度

?Dijkstra算法求A到D的最短通路

最短通路為：A-B-E-F-H-D,權值為10

5.2.3擴散法（flooding）（靜態(tài)）

■每一個進來的分組將被發(fā)送到除了它進來的那條線路之外

所有的線路上

■產(chǎn)生大量的重復分組

□在分組頭中包含跳數(shù)計數(shù)器，每經(jīng)過一跳之后計數(shù)器減一，丟棄

計數(shù)器值為0的分組

□記錄哪些分組已經(jīng)被擴散了，避免再次發(fā)送。為每一個分組增加

序號。

■選擇性擴散：路由器將進來的分組只輸出到那些大概方向

正確的線路上

■擴散法應用：軍事，分布式數(shù)據(jù)庫，無線網(wǎng)絡，作為其它

路由算法的度量標準（擴散法總是選擇最短的路徑）

524距離矢量路由(distance

vectorrouting)(動態(tài))

■工作原理：每個路由器維護一張表，表中列出了當前已知的到每個目

標的最佳距離以及所使用的線路。通過鄰居(neighbors)間相互交

換信息，路由器不斷更新它們內部的表

■表項包含兩個部分

□為了到達該目標路由器而首選使用的輸出線路

□到達該目標路由器的時間估計值或距離估計值

■每隔Tms,每個路由器向它的鄰居發(fā)送一個列表，其中包含它到每一

個目標路由器的估計值；同時，它也從每一個鄰居獲得一個類似的表

■假設路由器A知道它到鄰居X的“距離”為m,當它從X收到一個列表，

其中X1表示從X到i的“距離”，則路由器A就知道，如果它把分組轉發(fā)給

鄰居X,則該分組可以經(jīng)過Xj+m的“距離”到達路由器i

■路由器對每一個鄰居都執(zhí)行類似的計算，就可以發(fā)現(xiàn)最佳的路由

■在計算的過程中不使用老的路由表

example：

□JA8,JI10,JH12,JK6

□FromA,I,H,KtoG:AG18,IG31,HG6,KG31

□ThebestpathisJHG:12+6=18

Newestimated

delayfromJ

ToAIHK|Line

A02420218A

B1236312820A

C2518193628I

D402782420H

E147302217I

F2320194030I

G183163118H

H

172001912H

—

210142210I

J9117100——

K24222206K

L29339915K

JAJIJHJK~V~；

delaydelaydelaydelayNew

isisisisrouting

810126table

k_____________________________________J

VforJ

Vectorsreceivedfrom

J'sfourneighbors

(b)

■無窮計算問題

□對好消息反應迅速,對壞消息反應遲緩

ABcDEABcDE

..----■...----■

?■??Initially1234Initially

1■■?After1exchange3234After1exchange

12??After2exchanges3434After2exchanges

123?After3exchanges5454After3exchanges

1234After4exchanges5656After4exchanges

7676After5exchanges

7878After6exchanges

??■■

回(b)

525鏈路狀態(tài)路由(linkstate

routing)(動態(tài))

■1979年之前，ARPANET一直距離矢量路由，由

于收斂速度慢，后來被鏈路狀態(tài)路由替代

■鏈路狀態(tài)路由的思想：每一臺路由器都

□發(fā)現(xiàn)它的鄰居節(jié)點，并獲知網(wǎng)絡地址

□測量到鄰居節(jié)點的延遲或開銷

□構造一個分組，包含它所剛剛知道的消息

□將這個分組發(fā)送到其它所有的路由器

計算出到其它每一個路由器的最短路徑

■發(fā)現(xiàn)鄰居節(jié)點：在每一條點到點線路上發(fā)

送一個特殊的HELLO分組，線路另一端的

路由器應該回送一個應答說明它是誰（用

一個全局唯一的名字）

■當兩個或多個路由器在一個LAN中的時候,

將LAN模型化為一個虛擬節(jié)點

(b)

■測量線路開銷

每一個路由器要知道它到各個鄰居節(jié)點的延遲

□在線路上發(fā)送一個ECHO分組，另一端收到后立即應答

發(fā)送端計算往返時間，從而得到一個合理的延遲估計

值

■考慮負載影響：定時器在ECHO分組入隊時啟動

-不考慮負載影響：定時器在ECHO分組到達隊列頭部時候啟動

考慮負載影響可以優(yōu)化系統(tǒng)性能，但是也可能造成路

■創(chuàng)建鏈路狀態(tài)分組

□創(chuàng)建狀態(tài)分組：發(fā)送方標識+序列號+年齡+鄰

居列表，對于每個鄰居，需要給出到這個鄰居

的延遲

創(chuàng)建狀態(tài)分組的時機：定期創(chuàng)建；當某些重要

的事件發(fā)生時

A

Seq.

Age

B4

E5

(a)(b)

■發(fā)布鏈路狀態(tài)分組

基本思路：使用擴散法發(fā)布鏈路狀態(tài)分組。路由器記錄看到的所

有（源路由器，序列號）對，利用分組中的序列號，確定進入的

分組是一個新的分組還是重復分組，如果是新的分組，則除了它

進來的線路，向在其它線路轉發(fā)；如果是重復分組，則丟棄。如

果到達分組的序列號較小，則認為是過期分組，丟棄

■序列號回轉

■路由器崩潰造成記錄丟失

■序列號破壞

□采用32位的序列號，防止序列號回轉

□在每個狀態(tài)分組中保留一個年齡域（age）,每秒鐘該域值減一,

當年齡值為0時，丟棄該信息

□當一個鏈路狀態(tài)分組被擴散到一個路由器中的時候，并不是立即

把它加入到發(fā)送隊列中，而是在一個保留區(qū)中保留一段時間，如

果在這段時間內有同源的狀態(tài)分組到達，則根據(jù)其序列號，丟棄

重復分組或者老的分組

□所有的鏈路狀態(tài)分組都要被確認

SendflagsACKflags

SourceSeq.AgeACFACFData

A2160011100

F2160110001

E2159010101

C2060101010

D2159100011

■計算新路由路徑

獲得全部鏈路狀態(tài)分組的路由器，可以構造出

完整的子網(wǎng)圖

利用Dijkstra算法可以計算到所有目標的最短路

徑

5.2.6分級路由

?網(wǎng)絡規(guī)模增長一路由器的路由表成比例增長

□更多的路由器內存

更長的路由表搜尋時間

□更多的帶寬

■路由器被劃成區(qū)域(region),每個路由器知道如何將分

組路由到區(qū)域內的目標地址，但是不知道其它區(qū)域的內部

結構

優(yōu)點：節(jié)省路由器表空間

□缺點：有可能增加路徑長度

對于有N個路由器的子網(wǎng)，最優(yōu)級數(shù)為InN,每個路由器要求elnN

個表項

Fulltablefor1AHierarchicaltablefor1A

Dest.LineHopsDest.LineHops

Region1Region21A————1A——

J，市、、/"2A2BX\1B1B11B1B1

—m)1C1C11C1C1

2A1B221B2

\、1QX\2C2D

、、J、-2B1B331C2

2C1B341C3

2D1B451C4

3A1C3

3B1C2

4A1C3

4B1C4

Region3Region4Region5

4C1C4

5A1C4

5B1C5

5C1B5

5D1C6

5E1C5

(a)(b)(c)

5.2.7廣播路由

■廣播(broadcasting)

L源端給每一個目標端發(fā)送一個分組

□擴散法

多目標路由

□生成樹或匯集樹

逆向路徑轉發(fā)

B

⑻(C)

528多播(multicasting)路由

多播：給網(wǎng)絡中的一個組發(fā)送消息

組管理

□組創(chuàng)建和銷毀

新用戶加入和離開

多播路由

□每個路由器計算一棵生成樹，覆蓋其他所有路由器

□生成樹的修剪

■鏈路狀態(tài)路由

-逆向路徑轉發(fā)

1

1

(d)

5.2.9移動主機路由

■移動主機(mobilehost)

□遷移主機(migratoryhost)

□漫游主機(roaminghost)

■假設

□每個主機有一個永遠不變的永久性主場所(homelocation)

□每個主機有一個永久性的主機地址，用于確定主場所

■外部代理(foreignagent)：記錄所有當前正在訪問該區(qū)域的移動主機

■本地代理(homeagent)：記錄主場所在這個區(qū)域，但是當前正在訪問其他

區(qū)域的主機“

■注冊

外部代理周期性的向外廣播一個分組，宣布它的存在和地址，供

新來的移動主機識別。移動主機也可以主動查詢外部代理的存在

移動主機向外部代理請求注冊(主地址、MAC地址等)

外部代理和移動主機的本地代理聯(lián)系，告訴它：你有一部主機在

我這里

移動主機對安全信息進行檢查，并通知外部代理

外部代理收到確認后，完成移動主機的注冊

■發(fā)給移動主機的分組被發(fā)往該移動主機的主場所

(stepl)

■主場所的本地代理查找移動主機的新場所以及外部代理的

地址(step2)

■本地代理將分組封裝到一個外送分組的凈荷中，發(fā)給外部

代理，由外部代理從中提取分組，遞交給移動主機(隧

道)(steB35

■同時本地代理告訴發(fā)送方外部代理地址，以后的分組都直

接發(fā)送到外部代理(step4)

1.Packetissenttothe

mobilehost'shomeaddress

4.Subsequentpacketsare

tunneledtotheforeignagent

3.Senderisgivenforeign

agent'saddress,

2.Packetistunneledtothe

foreignagent

5.2.10AdHoc網(wǎng)絡中的路由

■AdHoc網(wǎng)絡：每個節(jié)點包含一個路由器和

一個主機，并且節(jié)點兩兩相鄰

□網(wǎng)絡拓撲在不停的發(fā)生變化

□路由器本身的位置也在變化

■固定網(wǎng)絡中的路由算法不再適用

■AODV(AdhocOn-demandDistance

Vector)

■路徑發(fā)現(xiàn)

同樣可以用圖來表示一個Adhoc網(wǎng)絡：節(jié)點代

表一個主機+路由器，如果兩個節(jié)點在它們的

半徑范圍內可以直接通信的話，則這兩個節(jié)點

之間就存在一條弧，假設所有的連接都是對稱

的

每個節(jié)點維護一張表，表項以目標節(jié)點為關鍵

字，說明將分組遞交給哪個鄰居才能到達目標

□只有在需要的時候才開始尋找路徑（按需）

Rangeof

A'sbroadcast

■A構造的ROUTEREQUEST分組

□源地址

□請求ID,每個節(jié)點單獨維護的本地計數(shù)器

□目標地址

□源序列號，區(qū)分新老路徑

□目標序列號

□跳計數(shù)

SourceRequestDestinationSourceDest.Hop

addressIDaddresssequence#sequence#count

■當ROUTEREQUEST分組到達節(jié)點后

二在本地的歷史表中查找（源節(jié)點，請求ID）對，如果

是重復分組，則丟棄，處理結束；如果不是重復分

組，將（源節(jié)點，請求ID）寫入歷史表，以便將來識

別重復分組

□在路由表中查找該分組的目標地址，如果找到較新的

通往該目標的路徑的話，給源節(jié)點送回一個ROUTE

REPLY分組（通過目標序列號）

如果在路由表中沒有找到較新的路徑，增加跳計數(shù)，

重新廣播ROUTEREQUEST分組，同時從分組中提取

數(shù)據(jù)，構造逆向路由表，便于以后應答分組可以回到

源節(jié)點。同時啟動定時器，定時器到期的話，該表項

被刪除

如果沿途都沒有節(jié)點知道目標節(jié)點的路徑，則ROUTE

REQUEST分組最終到達目標節(jié)點，目標節(jié)點向源節(jié)點

發(fā)送ROUTEREPLY分組作為應答

SourceDestinationDestinationHop

Lifetime

addressaddresssequence#count

■回程中每個節(jié)點將分組的信息加入本地路

由表

□如果目前還沒有通往該目的節(jié)點的路由路徑

在ROUTEREPLY中的目標序列號比本地路由

器中的序列號大（更新的消息）

□序列號相等，但是新的路徑更短

■可以利用IP分組中的TTL域減少廣播分組的

數(shù)量

■路徑維護

□節(jié)點N的活動鄰居(activeneighbor)：對于每一個可

能的目標節(jié)點，在最近的AT秒內曾經(jīng)給N發(fā)送過到達該

目標的分組的鄰節(jié)點

□節(jié)點N建立一個以目標節(jié)點為關鍵字的路由表，每一個

表項包括：到達該目標的輸出節(jié)點、到達該目標的跳

計數(shù)、最近的目標序列號以及針對該目標的活動鄰居

NextActiveOther

Dest.hopDistanceneighborsfields

AA1F,G

BB1F,G

CB2F

EG2

FF1A,B

GG1A,B

HF2A,B

1G2A,B

⑻

■節(jié)點N定期的向鄰居廣播HELLO消

息，希望鄰居做出應答，如果沒有

應答，則認為該鄰居之間的連接已

經(jīng)斷開

■N在它的路由表查找那些目標的路由

路徑用到了該不可達的鄰居，對于

每一條這樣的路徑，N都要通知對應

的活動鄰居，告訴它們經(jīng)過N的路徑

不再有效，應該從路由表中清除

■遞歸，直到所有依賴于該失效節(jié)點

的路徑全部從路由表中清除為止

■e.g.G節(jié)點離開

D發(fā)現(xiàn)后，發(fā)現(xiàn)到達E、G、I的路由依

賴G,而其對應的活動鄰居是A和B

D通知A、B說G不在了，A、B從而更新

自己的路由表，去掉經(jīng)過D到達E、G、

I的表項

D從自己的路由表中清除E、G、I的表

項

5.2.11對等網(wǎng)絡中的節(jié)點查詢

■對等網(wǎng)絡(peer-to-peernetwork)

□特點：完全分布式，所有節(jié)點都是對稱的，網(wǎng)絡沒有中心控制，

也沒有層次組織

問題：在缺少中心數(shù)據(jù)庫或中心索引的情況下，一個用戶如何找

到一個包含了他想要的信息的節(jié)點

■chord

□n個用戶

□每個用戶保存一些記錄和一些索引信息供其他用戶使用

每個用戶都有一個IP地址，通過一個hash函數(shù)可以映射為一個m

位的數(shù)值(通常，一個IP地址可以轉換為一個160位的數(shù)值，成為

節(jié)點琮識符nodeidentifier)

所有功。個節(jié)點標識符按照升序方式組成一個圓環(huán)，其中一些節(jié)點

有實際網(wǎng)絡節(jié)點對應，一些則沒有對應

□successor(k)函數(shù)：在圓上，從節(jié)點k開始沿著順時針

方向遇到的第一個實際節(jié)點的節(jié)點標識符

□鍵(key)：用hash函數(shù)對記錄的名字進行散列處理，

得到一個160位的值

□記錄的擁有者建立(name,my-ln-address)的關聯(lián)，

請successor(hash(name))保存這一對關聯(lián)信息，同名

的多條記錄的關聯(lián)信息將保留在同一個節(jié)點上

□數(shù)據(jù)庫的索引值被隨機的分布在節(jié)點上

希望查找name的用戶，先通過hash(name)得到一個鍵

值k,然后使用successor(k)找旬保存其關聯(lián)信息的節(jié)

點IP地址

發(fā)請求的節(jié)點向其后續(xù)節(jié)點發(fā)送一個分組，包含其IP地

址和待查記錄的key,該分組沿著環(huán)向前傳播，知道到

達被查詢的節(jié)點標識符的后續(xù)節(jié)點，如果該及談但有

匹配的信息，則將name和IP的關聯(lián)關系發(fā)送回去

■

■指取表(fingertable)

m個表項，每個表項指向一個不同的實際節(jié)點

□每個表項兩個域：start和successor(start)的IP地址

■節(jié)點k上第i個表項的兩個域

□start=k+2'(mod2m)

□successor(start[i])的IP地力上

(a)(b)

5.3擁塞控制算法

■擁塞(congestion)：當一個子網(wǎng)或者子網(wǎng)的一部分中出

現(xiàn)太多分組的時候，網(wǎng)絡性能開始下降

□輸入分組太快，路由器沒有足夠的內存存儲

□慢速的處理器

Packetssent

■擁塞和流控(flowcontrol)

□擁塞控制的任務是保證子網(wǎng)能夠承載所達到的流量，是一個全局

性的問題

?流控只與特定的發(fā)送方和特定的接收方之間的點到點流量有關，

它的任務是確保一個快速的發(fā)送方不會持續(xù)的以超過接收方接收

能力的速率傳輸數(shù)據(jù)，是一個局部的問題

5.3.1擁塞控制的通用原則

■開環(huán)(openloop)：試圖用良好的設計解決問題，本質

是從一開始就保證問題不會發(fā)生，一旦系統(tǒng)啟動并運行起

來，就不需要中途修正

何時接受新的流量

何時丟棄分組，丟棄哪些分組

□在網(wǎng)絡不同點上執(zhí)行的調度策略

不考慮網(wǎng)絡當前狀態(tài)

■閉環(huán)(closeloop)

□建立在反饋環(huán)路的概念基礎上

□監(jiān)視系統(tǒng)，檢測何時何地發(fā)生擁塞

□將信息傳遞到能夠解決問題的地方

□調整系統(tǒng)的運行，以改正問題

■監(jiān)視系統(tǒng)，檢測何時何地發(fā)生擁塞

□缺少緩沖空間丟棄分組所占百分比

□平均隊列長度

□超時和重傳分組數(shù)量

平均分組延遲以及分組延遲的標準方差

■將信息傳遞到能夠解決問題的地方

□向數(shù)據(jù)源報告

□路由器填充擁塞警告域

□主機或路由器發(fā)送探詢分組，主動探測

■調整系統(tǒng)的運行，以改正問題

□增加資源

□降低系統(tǒng)負載

5.3.2擁塞預防策略

LayerPolicies

Transport?Retransmissionpolicy

?Out-of-ordercachingpolicy

?Acknowledgementpolicy

?Flowcontrolpolicy

?Timeoutdetermination

Network?Virtualcircuitsversusdatagraminsidethesubnet

?Packetqueueingandservicepolicy

?Packetdiscardpolicy

?Routingalgorithm

?Packetlifetimemanagement

Datalink?Retransmissionpolicy

?Out-of-ordercachingpolicy

?Acknowledgementpolicy

?Flowcontrolpolicy

5.3.3虛電路子網(wǎng)中的擁塞控制

■準入控制(admissioncontrol)：一旦出現(xiàn)擁塞

信號，就不再創(chuàng)建任何虛電路，直到擁塞解除為

止

■使新的虛電路繞開擁塞的區(qū)域

■虛電路的資源預留(有可能浪費帶寬)

(a)(b)

5.3.4數(shù)據(jù)報子網(wǎng)中的擁塞控制

■路由器可以監(jiān)視它的輸出線路和其它資源的利用

率

u=QU0|d+(1-Ct)f(0<f<1,0<U<1)

■當以超過特定閾值的時候，進入警告狀態(tài)。對每

一個進入的分組，路由器檢查它的輸出線路是否

處于警告狀態(tài)

□警告位

抑制分組(chokepacket)

□逐跳(hop-by-hop)抑制分組

BCBC

5.3.5負載脫落(loadshedding)

■路由器因為來不及處理分組時，只要將這些分組

丟棄即可

■丟棄的分組取決于所運行的應用類型

■應用程序在分組中標明分組優(yōu)先級，以確定分組

的重要性

■隨機的早期檢測：在路由器耗盡所有的緩沖器空

間之前就開始丟棄分組(RED：RandomEarly

Detection,隨機的早期檢測)

5.3.6抖動控制

■抖動（jitter）：分組到達時間的變化量

■提早到達的分組，多遲延一會兒再發(fā)出去；遲到的分組,

則盡快的發(fā)送出去

■偏離預定時間越遠的分組越早被發(fā)送出去

s

OxJ

o

e

d

j

ooj

uu

。o

o一l

eo

e

ltHighjitter

uzjltte

MinimumDelayDelay

delay

(dueto

speedof

light)(a)(b)

5.4服務質量

5A1需求

■流(flow):從一個源到一個目標的分組流

■流的服務質量(QualityofService,QoS)

可靠性、延遲、抖動、帶寬

ApplicationReliabilityDelayJitterBandwidth

E-mailHighLowLowLow

FiletransferHighLowLowMedium

WebaccessHighMediumLowMedium

RemoteloginHighMediumMediumLow

AudioondemandLowLowHighMedium

VideoondemandLowLowHighHigh

TelephonyLowHighHighLow

VideoconferencingLowHighHighHigh

■依據(jù)QoS對數(shù)據(jù)流的分類

□位速率為常數(shù)（電話）

□位速率可變的實時應用（壓縮的視頻會議）

位速率可變的非實時應用（Internet電影）

最大可用位速率的應用（文件傳輸）

5.4.2獲得好的服務質量所使用的技

術

■過度提供資源

00

潮IIIg

-*-?Gapinplayback

I1IIIIIIIIIIIIII

05101520

Time(sec)

■流量整形(Trafficshaping)

□突發(fā)性的數(shù)據(jù)是造成擁塞的主要原因

□流量整形(customerside)：開環(huán)方法，使得用戶端以更加平滑的方式

發(fā)送數(shù)據(jù)anopenloopmethod,itforcesthepacketstobetransmittedat

amorepredictablerate(averagerate,burstiness),widelyusedinATM

networks.’

□流量策略Trafficpolicing(networkside):tomonitoratrafficflow.

■漏桶算法

□常數(shù)時間的單服務器排隊系統(tǒng)

□將主機內用戶進程發(fā)送出來的一個不均勻分組流變成了網(wǎng)絡上的一個均

勻分組流，把突發(fā)變得平滑，從而極大的降低了擁塞的幾率

(a)(b)

■令牌桶算法（tokenbucketalgorithm）

漏捅中保存令牌，令牌每AT秒產(chǎn)生一個

□只有抓住并銷毀一個令牌，一個分組才能發(fā)送

□令牌桶算法允許空閑的主機將許可權保留下來（直到到達桶的最

大容量n）以便將來使用，多達n個分組的突發(fā)數(shù)據(jù)可以被一次發(fā)

送出去（漏捅算法不允許），使得輸出流中也存在突發(fā)

對于主機，令牌桶滿了后會丟棄令牌，而不會丟棄分組（指示主

機停止），對于路由器，則有丟棄分組的可能

NetworksNetworks

(a)(b)

a

)---s

0

，二，Oo

lllllllllllllllllllll

IIIIIIIIIIIIIIIIHIIII

lllllllllll陽lllllllllllllllllllll

IIIIIIIIIIIIIIKIIIIIIIlllllllllllllllllllll

2HI2lllllllllllllllllllll

15.M

0B

MM/2

BMfBs5

/BseM

s/ecB

esc(

ces

fcofe

ro2ofrc

6r2f

2M32o

B3m3lllllllllllllllllllllllr

m-sllllllllllllll4

ssme(D0

eescCm

ccelllllllllllllls

fce

roc

8

8lllllllllllllllllllllll

m

2s

Met-zl

Bclllllllllllllllllllllllm

/2

sI(DCD

e

cIw

flllllllllllllllllllllll

「o1on

1

9

0

m

s

e■lllllllllllllllllllllll

c