北郵計算機學院：THE

NETWORK

LAYER第5章網絡層Part

I基本理論框架第

5

章 網絡層5.1

網絡層的設計要點5.2

路由算法5.3

擁塞控制5.4

服務質量5.5

網絡互聯5.6

網絡層IP協議北郵計算機學院：5.1

NETWORK

LAYER

DESIGN

ISSUE網絡層的基本概念網絡層的目標：將分組從源端沿著網絡路徑送到目標端。北郵計算機學院：End

toEnd

VS

Point

to

Point為什么要創建網絡層？北郵計算機學院：網絡層指明端到端的總體路徑方向，數據鏈路層腳踏實地地一條一條鏈路的實現。北郵計算機學院：Store-and-Forward

Packet

Switching5.1.1轉發，分組交換硬件結構轉發的方式Services

Provided

to

Transport

Layer5.1.2

網絡層提供的服務北郵計算機學院：Connectionless

Service5.1.3

無連接的服務TransportNetworkDatalink北郵計算機學院：無連接：數據報服務的特點H1H2

H4ADBH6EH1

向H5

發送分組H5CH3分組交換網H2

向H6

發送分組路徑可能變化網絡隨時接受主機發送的分組（即數據報）網絡為每個分組獨立地選擇路由。提供數據報服務的特點H1H2

H4ADBH6E網絡盡最大努力地將分組交付給目的主機，但網絡對源主機沒有任何承諾。H5CH3分組交換網提供數據報服務的特點H1H2

H4ADBH6E網絡不保證所傳送的分組不丟失也不保證按源主機發送分組的先后順序以及在時限內必須將分組交付給目的主機H5CH3分組交換網提供數據報服務的特點H1H2

H4ADBH6E當網絡發生擁塞時網絡中的結點可根據情況將一些分組丟棄H5CH3分組交換網提供數據報服務的特點H1H2

H4ADBH6E數據報提供的服務是不可靠的，它不能保證服務質量。實際上“盡最大努力交付”的服務就是沒有質量保證的服務。H5CH3分組交換網Connection-Oriented

Service5.1.4

面向連接：虛電路服務的特點H1H2H4ADBH6EH1

要和H5

通信主機H1

先向主機H5

發出一個特定格式的控制信息分組，要求進行通信，同時尋找一條合適路由。若主機H5

同意通信就發回響應，然后雙方就建立了虛電路。虛電路H1

向H5

發送的所有分組都沿此虛電路傳送。H5CH3分組交換網提供虛電路服務的特點H1H2H4ADBH6E同理，主機H2

和主機H6

通信之前，也要建立虛電路。H5CH3分組交換網提供虛電路服務的特點H1H2H4ADBH6E在虛電路建立后，網絡向用戶提供的服務就好像在兩個主機之間建立了一對穿過網絡的數字管道。所有發送的分組都按順序進入管道，然后按照先進先出的原則沿著此管道傳送到目的站主機。H5CH3分組交換網提供虛電路服務的特點H1H2H4ADBH6E到達目的站的分組順序就與發送時的順序一致，因此網絡提供虛電路服務對通信的服務質量QoS

(Quality

of

Service)有較好的保證。H5CH3分組交換網數據報服務和虛電路服務優缺點的歸納對比的方面虛電路服務

數據報服思路可靠通信應當由網絡來保證可靠通信應由用戶主機來保證連接的建立必須有不目的站地址每個分組都有目的站的全地址僅在連接建立階段使用，每個分組使用短的虛電路號北郵計算機學院：數據報服務和虛電路服務優缺點的歸納對比的方面虛電路服務

數據報服分組的轉發每個分組獨立選路由進行轉發屬于同一條虛電路的分組均按照同一路由進行轉發當結點出故障時所有通過出故障的結點的虛電路均不能工作故障結點可能丟分組，一可能會發生變北郵計算機學院：數據報服務和虛電路服務優缺點的歸納對比的方面虛電路服務

數據報服服務質量能夠實現擁塞控制能夠實現北郵計算機學院：數據報服務和虛電路服務優缺點的歸納對比的方面虛電路服務

數據報服務分組的順序總是按發送順序到達目的站時不一定到達目的站按發送順序端到端的負責差錯處理和可以由分組交換網由用戶主機負責也可以由用戶北郵計算機學院：ROUTING

ALGORITHMS5.2

路由算法

路由算法的概念

最優化的原則

距離矢量路由

鏈路狀態路由

分級路由北郵計算機學院：基本概念－路由器的兩個動作

轉發(forwarding)每個分組到達的時候，在路由表中查找該分組所對應的輸出路徑。

路由選擇(routing)使用路由算法。負責填充和更新路由表。北郵計算機學院：Routing

Algorithm路由算法北郵計算機學院：理想的路由算法北郵計算機學院：Non-adaptive

an路由算法的分類ptive如何恰當使用？北郵計算機學院：The

Optimality

Principle5.2.1

最優化原則如果I，J，K的最佳路由是r1+r2，則當I把分組交給J時，J一定會沿著r2把分組轉發出去。想想看：最優化原則，對于計算機網絡中的分組轉發有什么作用？北郵計算機學院：計算機學院：匯集樹(Sink

Tree)Shortest

PathRouting5.2.2

最短路徑路由算法北郵計算機學院：計算機學院：智能科學與網絡工程系：智能科學與網絡工程系：智能科學與網絡工程系：智能科學與網絡工程系：透明網橋的“武功秘笈”北郵計算機學院：擴散算法（Flooding）屬于靜態路由算法基本思想事先不需要任何網絡信息；

路由器把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發送。將來會有多個分組的副本到達目的地端，最先到達的，可能是走了“最優”的路徑。北郵計算機學院：146235擴散算法：結點1與6之間的通信，Step1124356擴散算法：Step

2124356擴散算法：Step

3好大的水啊！

（Flooding）算法的優點是什么？不需要事前知道任何網絡的拓撲信息；所有的網絡路徑都被嘗試過；第一個到達的分組走的路徑可能是最優的。算法的主要問題是什么？產生大量重復分組。想想看？如何消除：過時的/重復的分組？你該出手了！北郵計算機學院：源端收到分組時，在每個分組的頭部增加一個計數器。此后，每經過一跳該計數器減1，為0時丟棄。計數器的初值＝最佳路徑的跳數/子網的直徑；每個路由器記錄收到已經擴散過的分組，從而避免再次發送這些分組。源端在每個分組中放置一個序號；記錄{源端地址，序號}；每個路由器將得到的同一源端的分組的最大序列號分組記錄下來，小于該序號的丟棄。決北郵計算機學院：方選擇性擴散算法（1）623154236154選擇性擴散算法（2）1236選擇性擴散算法（3）54選擇性擴散算法（Selective

Flooding）選擇性擴散算法是擴散法的一種改進。能夠消除多余的分組。擴散算法的應用情況對路由器和線路的資源過于浪費，實際的網絡很少直接采用；具有極好的健壯性，可用于軍事應用；作為衡量標準評價和初級拓撲消息獲得方式應用于其它路由算法。北郵計算機學院：動態路由算法距離矢量路由算法鏈路狀態路由算法北郵計算機學院：Distance

Vector

Routing5.2.4

距離矢量路由算法北郵計算機學院：源站點1：利用中間站點2到達目的站點2。源站點1：利用中間站點3到達目的站點2。智能科學與網絡工程系：源站點1：利用中間站點4到達目的站點2。智能科學與網絡工程系：計算機學院：智能科學與網絡工程系：求：源站點1，目的站點3，分別利用2，3，4。智能科學與網絡工程系：使用距離矢量算法試著扮演一次路由器吧！離跳北郵計算機學院：B

1

BC

0

-D

1

DB

0

-C

1

C初始時，路由器中的路由表只有到相鄰路由器的信息“C”表示“從本路由器B到C路由器”“1”表示“距離是1”“-”表示“直接交付”C.

1

CD.

0

-BCA

DABCDB

1

BC

0

-D

1

D1：各個路由器各自重新測量到鄰居的距離；2：然后把自己上一狀態的路由表去掉轉發項，項變成距離表發送出去。B

0

-C

1

CC.

1

CD.

0

-B

0C

1B

1C

0D

1C

1D

0第一次交換開始：BCA

D路由器B

收到相鄰路由器C

的距離表B

1C

0D

1B.0

-C.

1

CD.

2

C更新后C

說：“我到D

的距離是1。”因此

B現在也可以到D，距離是2，經過C。”B

0

-C

1

CB

1

BC

0

-D

1

DB

0C

1C.

1

CD.

0

-BCA

DB

0C

1C

1D

0路由器C

收到相鄰路由器

B和D的距離表B

1C

0D

1B.

0

-C.

1

CD.2

CB

0

-C

1

CB

1

BC

0

-D

1

DC.

1

CD.

0

-更新后B

1

BC

0

-D

1

DABCDB

1C

0D

1路由器

D收到相鄰路由器C

的距離表B.

0

-C.

1

CD.2

CB

0

-C

1

CB

1

BC

0

-D

1

DC.

1

CD.

0

-C

1D

0更新后B

1

BC

0

-D

1

DB

2

C1

C0

-ABCDB

0

-C 1

CD 2

CB

1

BC

0

-D

1

DB

2

CC 1

CD 0

-最終所有的路由器的路由表都更新了對鏈路故障的反應好事傳千里，壞事不出門！!一個靠鄰居“

”活著的路由協議北郵計算機學院：一個好消息，A鏈路修好了！ABCDB

0

-C 1

CD 2

CB

1

BC

0

-D

1

DB

2

CC 1

CD 0

-初始時：BCDB

0

-C 1

CD 2

CB

1

BC

0

-D

1

DB

2

CC 1

CD 0

-A思考：A需要多久才能獲得全網的路由信息？B需要多久才能知道可達A的路由信息？C需要多久才能知道可達A的路由信息？D需要多久才能知道可達A的路由信息？初始時：BCDB

0

-C 1

CD 2

CB

1

BC

0

-D

1

DB

2

CC 1

CD 0

-AA0-B1BC2BD3BA0-B1BC2BD3BA0-B1BC2BD3BA1AB0-C1CD2CA1AB0-C1CD2CA1AB0-C1CD2CB1BC0-D1DB2CC1CD0-B2CC1CD0-A2BB1BC0-D1DA2BB1BC0-D1DA3CB2CC1CD0-總結：對鏈路“好消息”的反應很快！網絡再次收斂的速度很快！正所謂：好事快馬加鞭傳千里！北郵計算機學院：一個壞消息，A路由器壞了！ABCD北郵計算機學院：A0-B1BC2BD3BA1AB0-C1CD2CA2BB1BC0-D1DA3CB2CC1CD0-BCDA思考：B需要多久才能知道不可達A的路由信息？C需要多久才能知道不可達A的路由信息？D需要多久才能知道不可達A的路由信息？B:A

1C:A

2A0-B1BC2BD3BA1AB0-C1CD2CA2BB1BC0-D1DA3CB2CC1CD0-C卻通過“距離表”說：別著急，我能到達A，嘿嘿！A

B

C

D第一次交換時：B、C、D仍把自己的路由表改成距離表，發送。第一次交換后：C和D的路由表不變。一開始，B得知了壞消息：“我無法到A

！！！B

收到C

的更文后，誤認為可經過C

到達A，于是更新自己的路由表，說：“我到A

的距離是

3，下一跳經過C”。然后再等待下次的交換時，將此更新給C。C:A

2D:A

3計數到無問題1

AB

C

1DCNA1AC1CD2CBtimeDCNA2BB1BD1DDCNA3CB2CC1CCDDCNA∞-C1CD2CDCNA2BB1BD1DDCNA3CB2CC1CDCNA3CC1CD2CD

C

NA

2

BB

1

BD

1

DDCNA3CB2CC1CDCNA3CC1CD2CDCNDCNA3CB2CC1CDCNA5CC1CD2CDCNDCNA5CB2CC1CDCNA5CC1CD2CDCNA

4

B

A

4

B

A

6

BB

1

B

B

1

B

B

1

BD

1

D

D

1

D

D

1

DDCNA5CB2CC1CDCNA7CC1CD2CDCNA6BB1BD1DDCNA7CB2CC1C這樣不斷更新下去，計數到無窮。這就是好消息得快，而壞消息得慢。網絡出故障的時間往往需要較長的時間(例如數分鐘)。這是RIP

的一個主要缺點。1234如何解決上述問題？先想想：導致上述問題的本質原因是什么？北郵計算機學院：如何解決上述問題？跳數水平分割帶毒1值：頭疼治頭，腳痛治腳；2轉：的治水標平又分要割治本！北郵計算機學院：計數到無窮的問題BC1AD1規定一個最大距離（跳數）：16，當距離＝

16時，認為網絡是不可達的！！！DCNA1AC1CD2CBtimeDCNA2BB1BD1DDCNA3CB2CC1CCDDCNA∞-C1CD2CDCNA2BB1BD1DDCNA3CB2CC1CDCNA3CC1CD2CD

C

NA

2

BB

1

BD

1

DDCNA3CB2CC1CDCNA3CC1CD2CDCNDCNA3CB2CC1CDCNA5CC1CD2CDCNDCNA5CB2CC1CDCNA5CC1CD2CDCNA

4

B

A

4

B

A

6

BB

1

B

B

1

B

B

1

BD

1

D

D

1

D

D

1

DDCNA5CB2CC1CDCNA7CC1CD2CDCNA6BB1BD1DDCNA7CB2CC1C這樣不斷更新下去，計數到無窮。正常情況B:

A

1B

說：“我到A

的距離是1”“我有一條到A的路由”記住，我是！BCDA正常情況B:

A

1A

2

B我得到了到A的路由消息！我要做個標記C

說：“我到A

的距離是2，是經過B。”將來我不能向B告知網1的任何消息。這是“水平分割”技術。BCD這是由B告訴AA

∞

-A

∞

BB

說：壞消息：“我無法到達A

了！！！C說：沒關系，我能到達！！！C

在收到

B

的更

文之前，還發送原來的報文，雖然這時

C

并不知道A

出了故障，但報文是加了毒性逆轉的形式。這是：水平分割＋毒性逆轉！BCDA水平分割VS水平分割＋毒性逆轉Bad

news

is

better

than

no

news!北郵計算機學院：作業：分析網絡協議的有效性普通的距離矢量協議；使用帶水平分割的距離矢量協議；使用水平分割＋毒性逆轉方法。BCABCD

DA北郵計算機學院：5.2.5

鏈路狀態路由算法（Link

State

Routing）鏈路狀態路由算法

OSPF

IS-IS北郵計算機學院：算法的基本操作問候問候數據庫描述數據庫描述數據庫描述數據庫描述鏈路狀態請求鏈路狀態更新鏈路狀態確認確定可達性達到數據庫的同步新情況下的同步北郵計算機學院：1.發現鄰居結點，并學習它們的網絡地址OO確定可達性北郵計算機學院：2.測量到各鄰居節點的延遲或者開銷ECHOECHO測量鄰居開銷北郵計算機學院：3.創建鏈路狀態分組創建鏈路狀態分組北郵計算機學院：4.

使用擴散法發布鏈路狀態分組鏈路狀態分組鏈路狀態分組鏈路狀態分組鏈路狀態分組鏈路狀態分組鏈路狀態分組擴散發布達到數據庫的同步北郵計算機學院：4.

使用擴散法發布鏈路狀態分組北郵計算機學院：使用的是可靠的擴散法t更文ACK報文RRt3RRt1t2t4開動腦筋：存在的問題（1）如果序列號回轉了，則可能會產生

。解決辦法：使用32位序號；

即使每秒鐘產生一個鏈路狀態分組，也需要137年才可能發生回轉。北郵計算機學院：開動腦筋：存在的問題（2）如果：路由器

后，序號重置；或者序號出錯；解決方法增加（age）域，每秒鐘減1，為零則丟棄。鏈路狀態包到達后，延遲一段時間，并與其它已到達的來自同一路由器的鏈路狀態包比較序號，丟棄重復包，保留新包；鏈路狀態包需要應答；北郵計算機學院：從E發來的鏈路狀態包有兩個，一個經過EAB，另一個經過EFB；從D發鏈路狀態包有兩個，一個經過DCB，另一個經過DFB；北郵計算機學院：5.計算到每個其它路由器的最短路徑每個路由器都獲得了自己的路由拓撲圖

據Dijkstra算法計算最短路徑;生成自己的路由表北郵計算機學院：鏈路狀態算S）和距離矢量算法（DV）的比較路由信息的復雜性

LS路由信息向全網發送N節點，E個連接的情況下，每個節點發送O(nE)的報文

DV僅在鄰居節點之間交換北郵計算機學院：鏈路狀態算

S）和距離向量算法（DV）的比較收斂（Convergence）速度

LS

使用最短路徑優先算法，算法復雜度為O(n**2)n個結點（不包括源結點），需要n*(n+1)/2

次比較

使用更有效的實現方法，算法復雜度可以達到O(nlogn)

可能存在路由振蕩（oscillations）

DV收斂時間不定

可能會出現路由循環count-to-infinity問題北郵計算機學院：鏈路狀態算

S）和距離向量算法（DV）的比較健壯性:如果路由器不能正常工作會發生什么?LS結點會廣播錯誤的鏈路開銷每個結點只計算自己的路由表DV結點會廣播錯誤的路徑開銷每個結點的路由表被別的結點使用，錯誤會

到全網北郵計算機學院：作業2：北郵計算機學院：Hierarchical

Routing5.2.6

分級路由為路由器減負北郵計算機學院：不使用分級路由使用分級路由分級路由假設某個子網中有720臺路由器.如果不使用分級路由方法：每個路由器中的表項為720項；如果采用兩個分級，分成24個區域，每個區域30個路由器：30

本地表項

23

表項如果采用三個分級，分成8個群，每個群包含9個區域，每個區域包含10個路由器，則：10

本地表項8

個本地群中的區域項7群作業3：2,3,6,7,9,10,14,22北郵計算機學院：關于路由表的預備知識路由表的結構（

）北郵計算機學院：用圖表示廣域網的例子12341結點邊243北郵計算機學院：每一個結點的轉1243目的站下一跳

1

直接233343對結點

1

的轉

的第一個項目的解釋：若到達結點

1

的分組的目的地址是結

則下一跳就是直接交付而不必再轉發的主機，結點。結點1

的轉北郵計算機學院：1243目的站下一跳

13

2直接3344對結點

2

的轉

的第一個項目的解釋：若到達結點

2

的每分組一的個目的結c

地點址的是結轉點主機，則下一跳就應轉發到結點3結點2

的轉北郵計算機學院：在路由表中使用默認路由12431直接233343結點1

的轉目的站 下一跳這三個項目的“下一跳”都是轉發到“3”（結點3）。可以合并以結點

1

和結點

2

中的轉 為例來北郵計算機學院：在路由表中使用默認路由12431默認直接3結點1

的轉目的站 下一跳默認路由北郵計算機學院：在路由表中使用默認路由124312343直接34結點2

的轉目的站 下一跳這兩個項目的“下一跳”都是轉發到“3”（結點3）。可以合并北郵計算機學院：在路由表中使用默認路由使用默認路由使轉更加簡潔，可減少查找轉的時間。124324默認直接43結點2

的轉目的站 下一跳默認路由北郵計算機學院：CONGESTION

CONTROL

ALGORITHMS5.3網絡擁塞控制網絡開始擁堵了！北郵計算機學院：網絡擁塞：網絡性能曲線吞吐量擁塞無擁塞控制死鎖（吞吐量=0）提供的負載輕度擁塞0北郵計算機學院：擁塞（Congestion）擁塞網絡資源上有太多的分組時，將會導致網絡性能下降。對資源需求的總和>可用資源資源：鏈路容量、交換節點中的緩存和處理機速度等。擁塞產生的原因低帶寬線路多個輸入對應一個輸出節點緩沖容量太小結點處理機速度不高北郵計算機學院：擁塞的策略：決不只針對某個因素改善擁塞！！！若結點緩存容量太小，到達結點的分組無空間暫存；若增大結點緩存容量，而鏈路容量和處理機速度未提高，分組排隊會很長，導致時延增大，可能因超時發送端進行重發，發出的分組，擁塞更加；提高結點處理機速度，增大鏈路容量，故然可以改善這段的擁塞，但可能只是將瓶頸轉移到其他地方。因此，針對某個因素的解決方案，只能對提高網絡性能起到一定的好處，甚至僅僅是轉移了影響性能的瓶頸。北郵計算機學院：擁塞控制與流量控制的差別

擁塞控制（congestion

control）需要確保通信子網能夠承載用戶提交的通信量，是一個全局性過程，涉及主機、路由器等很多

因素；

流量控制（flow

control)與點到點的通信量有關，主要解決快速發送方與慢速接收方的問題，是局部過程，一般都是基于反饋進行控制的。北郵計算機學院：擁塞和流量控制的區別擁塞控制所起的作用吞吐量擁塞理想的擁塞控制實際的擁塞控制無擁塞控制死鎖（吞吐量=0）提供的負載輕度擁塞0北郵計算機學院：5.3.1

擁塞控制的通用原則有兩種思路防患未然型亡羊補牢型北郵計算機學院：兩種思路Open

loop（開環方法）試圖采用良好的設計來解決問題，本質是從一開始就保證不會發生擁塞問題。一旦網絡系統啟動運行起來，就不需要中途做修正。Closed

loop（閉環方法）基于返回環路的概念基礎之上：Explicit

feedback

（顯式反饋）Implicit

feedback（隱式反饋）北郵計算機學院：5.3.2

開環方法：擁塞預防策略閉環控制策略三個步驟：監視系統，檢測到何時何地發生了擁塞將該信息傳遞到能夠采取行動的地方調整系統的運行，以改正問題。北郵計算機學院：1.監視系統，檢測是否發生擁塞擁塞控制使用的度量標準丟棄的分組所占的百分比（缺少緩沖區空間）平均隊列長度超時和重傳分組的數量平均分組延遲和分組延遲的標準方差北郵計算機學院：2.將擁塞信息傳輸到能夠采取行動的地方擁塞信息的傳輸方法（隱式和顯示反饋）給流量源發送一個分組，告知擁塞的發生；在分組中增加一個位或一個域，檢測到擁塞時，路由器填充該位，在它所有的輸出分組中填充

該域，以告警它的鄰居主機或路由器周期性地向外發送探詢分組，顯示地詢問有關擁塞狀況，然后在有問題的區域中，可以利用這些信息來路由流量。北郵計算機學院：3.

調整系統的運行目的：擁塞消息將最終導致主機采取適當的行動來減輕擁塞。謹慎的調整時間尺度：系統不會產生劇烈震蕩擁塞機制要及時有效。北郵計算機學院：5.3.3

虛電路子網中的擁塞控制，??

控制（admission

control）??

基本思想：一旦發生擁塞，在問題解決之前不允許建立新的虛電路；??

另

法是發生擁塞后可以建立新的虛電路，但要繞開發生擁塞的地區；北郵計算機學院：資源預留策略（虛電路子網）資源預留：建立虛電路時，主機與子網達成協議，子網根據協議在虛電

為此連接預留資源。

問題是：是任何時刻都使用資源預留嗎？還是只在發生擁塞時？北郵計算機學院：5.3.4

數據報子網中的擁塞控制

(1

)

funew

uold

(0,1)，

e.g.

87.5%U:平均利用率f:

瞬時利用率北郵計算機學院：警告位（The

Warning

Bit）路由器當輸出線路達到告警狀態時，路由器將發送出去的分組頭部設置告警位。目的地當分組到達目的地時，告警位被到ACK分組中，發給源端。源端隨著帶有警告位的確認分組不斷回來時，源端不斷的降低它的傳輸速率

當帶有警告位的確認分組減少到規定值時，源端增加它的傳輸速率

由于沿途的路由器都可能設置警告位，所以只有當所有的路由器都排除了問題之后，流量才能增加上去。抑制分組（

Choke

Packets

）路由器路由器給源端返回一個抑制分組，并 原分組的目標地址；原來的分組被打上一個標記，防止沿途其他路由器又重復產生抑制分組源端主機收到抑制分組后，將發送到指定目標的流量減少X百分比隨后到達的具有相同目的地抑制分組被忽略一段間隔后，繼續如果又有抑制分組，則進一步降低發送流量；如果沒有抑制分組，則增加流量主機可以調節流量，例如利用一個窗口第一次可以導致流量減少到原來的50%,第二此可以減少到25%......

快速減少，緩慢增加逐級跳（hop-by-hop）抑制分組產生原因在高速、長距離的網絡中，由于源主機響應太慢，抑制包算法對擁塞控制的效果并不好，可采用逐跳抑制包算法。基本思想抑制包對它經過的每個路由器都起作用；能夠迅速緩解發生擁塞處的擁塞；上游路由器要求有 的緩沖區；AB

CDFE北郵計算機學院：锏級的方法黔驢技窮之時….北郵計算機學院：5.3.5

負載丟棄（load

shedding）原則上述算法都不能消除擁塞時，路由器只得將包丟棄；針對不同服務，可采取不同丟棄策略

隨機丟棄

Wine

&Milk

E.g.

file

transfer,

multimedia

Requires

cooperation

from

the

senders

分組帶有優先級,

…r

to

send

than

the

high-priority

E.g.

algorithms

for

compressing

The

low-priority

packets

being

cheones,

…

RED

(Random

Early

Detection)

Drop

packets

before

the

situation

hase

hopeless

How

should

the

router l

the

source

about

theproblem?

Send

a

choke

packet

Just

discard

the

selected

packet

Sources

respond

to

lost

packets

by

slowing

down

their

transmission

rate時，為何總要從網絡上看緩存，緩存？想知道其中的奧秘嗎？北郵計算機學院：5.3.6

抖動（jitter）控制抖動：分組到達時間的變化量被稱為抖動。路由器對抖動的控制方法來得晚的，加快其轉發速度；

提早到達的，讓分組在緩沖區中多逗留一會。目的地接收端對抖動的控制方法緩存，盡可能多的收集分組。北郵計算機學院：5.4

服務質量(QoS)流(Flow)：從源端到目的地端的分組流。北郵計算機學院：服務質量的四個衡量參數

可靠性(reliability）

延遲(delay)

抖動(jitter)

帶寬(bandwidth)北郵計算機學院：服務質量需求的嚴格程度5-30北郵計算機學院：ATM

網絡:流的分類依據對QoS的需求，可將流分為：

Constant

bit

rateephony

Real-time

variable

bit

rate

compressed

conferencing

Non-real-time

variable

bit

rate

watching

a

movieover

the

Internet

Available

bit

rate

filetransfer北郵計算機學院：5.4.2獲得好的服務質量的技術緩沖，流量整形等北郵計算機學院：1.Buffering（緩沖，在接收方）Smoothing

the

output

stream

bybuffering

packets.北郵計算機學院：2.Traffic

Sha（流量整形）流量整形用于調節數據的平均速率和突發性；與流量控制（滑動窗口協議）是有重要區別的！！！漏桶算法（The

Leaky

Bucket

Algorithm）基本思想將用戶發出的不平滑的數據分組流轉變成網絡中平滑的數據分組流；可用于固定分組長的協議，如ATM；也可用于可變分組長的協議，如IP，使用字節計數；

無論負載突發性如何，漏桶算法強迫輸出按平均速率進行。北郵計算機學院：漏桶算法示意圖流量整形前的輸入流量整形后的輸出(漏桶大小為1MB)北郵計算機學院：令牌桶算法（The

Token

Bucket

Algorithm）漏桶算法不夠靈活，因此加入令牌機制；基本思想：漏桶存放令牌，每T秒產生一個令牌，令牌累積到超過漏桶上界時就不再增加。分組傳輸之前必須獲得一個令牌，傳輸之后刪除該令牌；漏桶算法與令牌桶算法的區別流量整形策略不同漏桶算法不允許空閑主機積累發送權，以便以后發送大的突發數據；

令牌桶算法允許積累發送權，最大為桶的大小。丟棄的對象不同漏桶中存放的是數據，桶滿了丟棄數據分組；令牌桶中存放的是令牌，桶滿了丟棄令牌，不丟棄數據分組。北郵計算機學院：如何計算“以最大速率發送突發數據的持續時間”的方法突發時間長度為S；令牌桶的容量為C字節，令牌的到達速率為p字節/秒，最大的輸出速率為M字節/秒

則在長度為S秒的最大速度突發過程中，字節的數量為MS，則

MS

=

C+pS

S＝

C/(M-p)北郵計算機學院：(c)

250

KB(d)

500

KB(e)

750

KB.令牌桶＋漏桶在令牌桶后加一個漏桶，實現更平滑的整形效果網絡最大速率>漏桶的速率>令牌到達速率令牌桶的容量=500KB

漏桶速率=10MB/s10S=21.74*25+(S-21.74)*2S=62.51ms（書后習題28）最大分組長度為1000字節，令牌桶速率為每秒10MB，令牌桶的大小為1M字節，最大傳輸速率為每秒50MB，請問以最大速度傳輸的突發數據會持續多長時間？北郵計算機學院：(書后習題27）在一個6Mbps的網絡上，有一臺主機通過一個令牌桶進行流量調整。令牌桶的填充速率為1Mbps。初始時候它被填充到8Mb的容量，請問該計算機以6Mbps的全速率可以傳輸多長時間？北郵計算機學院：判斷題：使用令牌桶和漏桶算法時，都會有突發數據輸出？北郵計算機學院：5.5

網絡互連同類型的網絡互聯是少數派。學習的重點是互連的方法。北郵計算機學院：互聯網的基本概念北郵計算機學院：網絡互聯的示例

LAN-LAN

LAN-WAN

WAN-WAN

LAN-WAN-LAN北郵計算機學院：5.5.2如何連接網絡在上在對等層轉換北郵計算機學院：5.5.2如何連接網絡應用層：應用網關

傳輸層：傳輸網關網絡層：路由器數據鏈路層：網橋和交換機物理層：集線器和中繼器數據鏈路層5應用層4傳輸層3網絡層2

數據鏈路層1物理層Bridge

&

RouterBridge

VS

RouterBridge(Switch):MAC

addressRouter:Layer-3

address

（如IP地址）欲知詳情，且聽下節分解！！網絡提供了兩種類型的服務：－面向

（虛電路）－面向無連接（數據報）下面將針對這兩種服務分別研究互聯的方法北郵計算機學院：5.5.3

級聯虛電路（Concatenated

Virtual

Circuits）??

工作過程（與虛電路子網工作過程相似）??

建立連接??

當目的主機不在子網內時，則在子網內找一個離目的網絡最近的路由器，與之建立一條虛電路；??

該路由器與外部網關建立虛電路；??

該網關與下一個子網中的一個路由器建立虛電路；??

重復上述操作，直到到達目的主機。??

傳輸數據??

相同連接的包沿同一虛電路按序號傳輸；??