1、1Chapter 1Chapter 1Chapter 1 Congestion Control and Flow ControlCongestion Control and Flow ControlCongestion Control and Flow Control in Data Networks and Internetsin Data Networks and Internetsin Data Networks and Internets張滬寅張滬寅2 Introduction 擁塞發(fā)生在通過網(wǎng)絡傳輸?shù)姆纸M數(shù)量擁塞發(fā)生在通過網(wǎng)絡傳輸?shù)姆纸M數(shù)量開始接近開始接近網(wǎng)絡的網(wǎng)絡的分組處理能力時。

2、分組處理能力時。 Objective of congestion control: 目標是將網(wǎng)絡中的目標是將網(wǎng)絡中的分組數(shù)量分組數(shù)量維持在一定的水平之下，維持在一定的水平之下，以免發(fā)生擁塞。以免發(fā)生擁塞。3 隊列理論隊列理論( (Queuing Theory) ) 數(shù)據(jù)網(wǎng)絡是由一個隊列組成的網(wǎng)絡。數(shù)據(jù)網(wǎng)絡是由一個隊列組成的網(wǎng)絡。 如果分組到達的速率如果分組到達的速率大于等于大于等于分組傳輸?shù)乃俾剩犃蟹纸M傳輸?shù)乃俾?，隊列大小就不停地增長且分組經(jīng)歷的時延大小就不停地增長且分組經(jīng)歷的時延(Delay) 變得越來越變得越來越長。長。 If arrival rate transmission rate

3、4 隊列理論隊列理論( (Queuing Theory) ) 5 1.1 1.1 擁塞的結(jié)果擁塞的結(jié)果 達到飽和點時采用的兩種策略：達到飽和點時采用的兩種策略： 如果沒有緩存空間則如果沒有緩存空間則丟棄丟棄進入的進入的分組分組 分組到達太快來不及作路由處理分組到達太快來不及作路由處理 分組到達緩存速度快于從緩存輸出速率分組到達緩存速度快于從緩存輸出速率 達到達到飽合節(jié)點飽合節(jié)點對對其其相鄰節(jié)點實施流量控制相鄰節(jié)點實施流量控制措施措施 可能會導致?lián)砣麛U散到整個網(wǎng)絡可能會導致?lián)砣麛U散到整個網(wǎng)絡 參見下頁圖參見下頁圖6 10.1 10.1 擁塞的結(jié)果擁塞的結(jié)果57 1.1 1.1 擁塞的結(jié)果擁塞的結(jié)

4、果 1. 理想的性能理想的性能(Ideal Performance) 每個節(jié)點有每個節(jié)點有無限大的緩存無限大的緩存，又不存在與分組傳輸或，又不存在與分組傳輸或擁塞控制相關(guān)的額外開銷。擁塞控制相關(guān)的額外開銷。 網(wǎng)絡吞吐量隨著負載的增加而增加，直到供給負載網(wǎng)絡吞吐量隨著負載的增加而增加，直到供給負載等于網(wǎng)絡全部容量，歸一化的吞吐量對于更高的輸入負等于網(wǎng)絡全部容量，歸一化的吞吐量對于更高的輸入負載仍保持在載仍保持在1.0。 當供給負載等于網(wǎng)絡的全部容量時，分組時延增加當供給負載等于網(wǎng)絡的全部容量時，分組時延增加 網(wǎng)絡能力為吞吐量與時延之比網(wǎng)絡能力為吞吐量與時延之比 Power = throughpu

5、t / delay 吞吐量越大時延越大吞吐量越大時延越大 8 10.1 10.1 擁塞的結(jié)果擁塞的結(jié)果9 1.1 1.1 擁塞的結(jié)果擁塞的結(jié)果 2. 實際的性能實際的性能(Practical Performance ) 有限有限的緩存，每個分組的處理都有的緩存，每個分組的處理都有額外額外的的開銷開銷 若不進行擁塞控制，負載的增長會導致網(wǎng)絡進入若不進行擁塞控制，負載的增長會導致網(wǎng)絡進入中中等等的擁塞狀態(tài)；網(wǎng)絡吞吐量的增長速率的擁塞狀態(tài)；網(wǎng)絡吞吐量的增長速率慢于慢于負載的增長負載的增長速度（速度（A點）點） 負載負載不可能均勻不可能均勻地分布在整個網(wǎng)絡上地分布在整個網(wǎng)絡上 網(wǎng)絡試圖選擇網(wǎng)絡試圖選擇

6、低擁塞低擁塞區(qū)平衡負載，路由選擇產(chǎn)生額外開銷降區(qū)平衡負載，路由選擇產(chǎn)生額外開銷降低數(shù)據(jù)分組的容量低數(shù)據(jù)分組的容量 網(wǎng)上的網(wǎng)上的負荷進一步增加導致時延增長，最終使吞吐負荷進一步增加導致時延增長，最終使吞吐量降到量降到0（B點）點）10 10.1 10.1 擁塞的結(jié)果擁塞的結(jié)果11 1.2 1.2 擁塞控制擁塞控制( (Congestion Control ) ) 1.反壓反壓(Backpressure ) 請求請求源端源端減小向減小向目的目的站的數(shù)據(jù)發(fā)送速率站的數(shù)據(jù)發(fā)送速率 流量限制方向傳到各信源，限制新分組進入網(wǎng)絡流量限制方向傳到各信源，限制新分組進入網(wǎng)絡 選擇選擇流量大的鏈路采用反壓流量大的

7、鏈路采用反壓 用于用于逐跳流控逐跳流控的的面向連接面向連接的網(wǎng)絡的網(wǎng)絡 2.阻流分組阻流分組(Choke packet) 網(wǎng)絡中的擁塞節(jié)點產(chǎn)生的網(wǎng)絡中的擁塞節(jié)點產(chǎn)生的控制分組控制分組，它被傳回源節(jié)，它被傳回源節(jié)點以便限制通信量進入網(wǎng)絡，要求源端系統(tǒng)減小向目的點以便限制通信量進入網(wǎng)絡，要求源端系統(tǒng)減小向目的端系統(tǒng)的數(shù)據(jù)發(fā)送速率端系統(tǒng)的數(shù)據(jù)發(fā)送速率 阻流分組的例子：阻流分組的例子：ICMP的源站抑制的源站抑制 因因緩存溢出緩存溢出而丟棄數(shù)據(jù)包時，可用而丟棄數(shù)據(jù)包時，可用源站抑制方法源站抑制方法 12 1.2 1.2 擁塞控制擁塞控制( (Congestion Control ) ) 3.隱式擁塞信

8、令隱式擁塞信令(Implicit congestion signaling ) 源端通過源端通過傳輸時延增加傳輸時延增加和和分組丟失分組丟失檢測到擁檢測到擁塞后減少流量。由塞后減少流量。由端系統(tǒng)端系統(tǒng)完成，無需其他節(jié)點參完成，無需其他節(jié)點參與與 適合無連接或數(shù)據(jù)報方式的網(wǎng)絡適合無連接或數(shù)據(jù)報方式的網(wǎng)絡(IP) 適合面向連接的網(wǎng)絡適合面向連接的網(wǎng)絡(幀中繼網(wǎng)絡幀中繼網(wǎng)絡,LAPF控制協(xié)議控制協(xié)議)13 1.2 1.2 擁塞控制擁塞控制( (Congestion Control ) ) 4. 顯示擁塞信令顯示擁塞信令(Explicit congestion signaling ) 網(wǎng)絡會對網(wǎng)絡中正

9、形成的擁塞向端系統(tǒng)網(wǎng)絡會對網(wǎng)絡中正形成的擁塞向端系統(tǒng)發(fā)出警告發(fā)出警告，而端系統(tǒng)則，而端系統(tǒng)則應應采取措施采取措施降低對網(wǎng)絡的供給負擔。降低對網(wǎng)絡的供給負擔。 方向方向(Direction)：顯示擁塞：顯示擁塞信令信令信號可向信號可向2個方向傳送個方向傳送 反向反向(Backward)：通知：通知源站源站對與收到分組方向?qū)εc收到分組方向相反相反的流量采取擁的流量采取擁塞避免措施。塞避免措施。 反向信息：改變數(shù)據(jù)分組頭部某些位，或者是單獨發(fā)控制分組 前向前向(Forward)：通知：通知用戶用戶對與收到分組方向?qū)εc收到分組方向相同相同的流量采取措施，的流量采取措施，前向信息如上述。端系統(tǒng)可返回源端

10、或上層進行流量控制。前向信息如上述。端系統(tǒng)可返回源端或上層進行流量控制。 分類分類(Categories) 二進制二進制(Binary )：擁塞節(jié)點對轉(zhuǎn)發(fā)的數(shù)據(jù)分組某位置：擁塞節(jié)點對轉(zhuǎn)發(fā)的數(shù)據(jù)分組某位置1，源站收到，源站收到降低流量降低流量 基于信用量基于信用量(Credit-based ):表示表示允許源站允許源站發(fā)送的發(fā)送的字節(jié)數(shù)字節(jié)數(shù)或或分組數(shù)分組數(shù) 基于速率基于速率(rate-based) :在一邏輯連接上在一邏輯連接上源站源站發(fā)送的控制分組有明發(fā)送的控制分組有明確的確的數(shù)據(jù)率上限數(shù)據(jù)率上限14 1.2 1.2 擁塞控制擁塞控制( (Congestion Control ) ) 15

11、1.3 1.3 通信量管理通信量管理( (Traffic Management ) ) 1. 公平性公平性(Fairness ) 最后到達首先丟棄的策略是最后到達首先丟棄的策略是不公平的不公平的，可以采用一些技術(shù)實，可以采用一些技術(shù)實現(xiàn)現(xiàn)公平性公平性(如如,每個隊列的緩存大小相同每個隊列的緩存大小相同) 2. 服務質(zhì)量服務質(zhì)量(Quality of Service ) 網(wǎng)絡擁塞時，不同需求的流量應得到的網(wǎng)絡擁塞時，不同需求的流量應得到的QoS的不同的不同 聲音，視頻：對時延敏感，對丟失不敏感聲音，視頻：對時延敏感，對丟失不敏感 文件傳送，郵件：對時延不敏感，對丟失敏感文件傳送，郵件：對時延不敏

12、感，對丟失敏感 交互計算：對時延和丟失都敏感交互計算：對時延和丟失都敏感 不同的流量應有不同的優(yōu)先級不同的流量應有不同的優(yōu)先級 3. 預留預留(Reservations) 策略：制訂一個策略：制訂一個通信量合約通信量合約，過量的通信量要么丟棄要么以，過量的通信量要么丟棄要么以盡力而為傳輸?shù)姆绞教幚肀M力而為傳輸?shù)姆绞教幚?16 1.4 1.4 分組交換網(wǎng)中擁塞控制分組交換網(wǎng)中擁塞控制 ( (Congestion Control in Packet-Switching Networks) ) 1. 從擁塞節(jié)點向一些或所有源點發(fā)送一個控制分組。從擁塞節(jié)點向一些或所有源點發(fā)送一個控制分組。 2. 依據(jù)

13、路由選擇信息。依據(jù)路由選擇信息。 3. 利用端到端的探測分組。利用端到端的探測分組。 4. 允許分組交換節(jié)點在分組經(jīng)過時添加擁塞信息。允許分組交換節(jié)點在分組經(jīng)過時添加擁塞信息。 17 1.5 1.5 幀中繼擁塞控制(Frame Relay Congestion Control ) 1. 流量速率管理流量速率管理(Traffic Rate Management ) 約定的信息速率約定的信息速率(Committed Information Rate ,CIR) 網(wǎng)絡認同的用于支持某個特定網(wǎng)絡認同的用于支持某個特定幀模式幀模式連接的速率，當網(wǎng)絡出連接的速率，當網(wǎng)絡出現(xiàn)擁塞時，首先丟棄超過現(xiàn)擁塞時，首

14、先丟棄超過CIR的連接所傳輸?shù)膸倪B接所傳輸?shù)膸?整體整體CIR節(jié)點的容量節(jié)點的容量 整體整體CIR也不應超過用戶也不應超過用戶-網(wǎng)絡接口上的物理數(shù)據(jù)率網(wǎng)絡接口上的物理數(shù)據(jù)率(接入速接入速率率) 利用利用兩個參數(shù)兩個參數(shù)進行流量速率管理進行流量速率管理 約定突發(fā)長度約定突發(fā)長度(Bc) 在測量間隔在測量間隔T內(nèi)網(wǎng)絡內(nèi)網(wǎng)絡同意同意傳輸?shù)淖畲髷?shù)據(jù)量傳輸?shù)淖畲髷?shù)據(jù)量 超量突發(fā)長度超量突發(fā)長度(Be) 在測量間隔在測量間隔T內(nèi)網(wǎng)絡內(nèi)網(wǎng)絡試圖試圖傳輸?shù)膫鬏數(shù)某^超過Bc的最大數(shù)據(jù)量的最大數(shù)據(jù)量18 1.5 1.5 幀中繼擁塞控制(Frame Relay Congestion Control )例：假設某

15、節(jié)點接入速度為例：假設某節(jié)點接入速度為64kb/s，該節(jié)點被指派的，該節(jié)點被指派的CIR 32kb/s, CIR的測量時間間隔的測量時間間隔T 500ms，幀長，幀長L 4000bit。 在時間在時間T內(nèi)，虛電路只能發(fā)送內(nèi)，虛電路只能發(fā)送CIRT/L 4個高優(yōu)先級的幀，個高優(yōu)先級的幀，其其DE 0。 由于由于CIR的數(shù)值只是接入速率的一半，因此用戶在的數(shù)值只是接入速率的一半，因此用戶在500ms內(nèi)再內(nèi)再發(fā)送發(fā)送4個低優(yōu)先級的幀，其個低優(yōu)先級的幀，其DE=1。1910.5 10.5 幀中繼擁塞控制幀中繼擁塞控制( (Frame Relay Congestion Control ) )18 201

16、0.5 10.5 幀中繼擁塞控制幀中繼擁塞控制( (Frame Relay Congestion Control ) ) 211.5 1.5 幀中繼擁塞控制幀中繼擁塞控制( (Frame Relay Congestion Control ) ) 2. 使用顯示信令的擁塞避免使用顯示信令的擁塞避免(Congestion Avoidance with Explicit Signaling) 對于解決擁塞問題應對于解決擁塞問題應可控制可控制和和公平的公平的方式方式 顯示擁塞避免技術(shù)的兩種策略：顯示擁塞避免技術(shù)的兩種策略： 擁塞情況的出現(xiàn)是擁塞情況的出現(xiàn)是緩慢的緩慢的，且絕大多數(shù)擁塞發(fā)生在，且絕大多數(shù)

17、擁塞發(fā)生在網(wǎng)絡的網(wǎng)絡的出口節(jié)點出口節(jié)點上上 前向顯示擁塞避免前向顯示擁塞避免(forward explicit congestion avoidance) 擁塞在擁塞在內(nèi)部內(nèi)部節(jié)點迅速增長，要求采取節(jié)點迅速增長，要求采取果斷果斷的措施來的措施來防止擁塞防止擁塞 反向顯示擁塞避免反向顯示擁塞避免(backward explicit congestion avoidance)221.5 1.5 幀中繼擁塞控制幀中繼擁塞控制( (Frame Relay Congestion Control ) ) 顯示信令中的顯示信令中的兩個位兩個位(BECN，F(xiàn)ECN) 反向顯示擁塞指示反向顯示擁塞指示(Back

18、ward Explicit Congestion Notification) 對與對與接收幀相反方向上的流量接收幀相反方向上的流量起作用起作用 指出在這條邏輯連接上傳輸?shù)闹赋鲈谶@條邏輯連接上傳輸?shù)目赡芸赡軙龅綋砣麜龅綋砣?前向顯示擁塞指示前向顯示擁塞指示(Forward Explicit Congestion Notification) 對與對與接收幀方向相同的流量接收幀方向相同的流量起作用起作用 指出在這條邏輯連接上傳輸?shù)膸赋鲈谶@條邏輯連接上傳輸?shù)膸呀?jīng)已經(jīng)遇到了擁塞遇到了擁塞 23 1.6 Flow Control and Error Control 1.6.1 Flow Contr

19、ol 1. Flow Control 限制數(shù)據(jù)發(fā)送的數(shù)量或發(fā)送速率限制數(shù)據(jù)發(fā)送的數(shù)量或發(fā)送速率 Reasons: 源站源站發(fā)送發(fā)送PDUs的速率的速率超過超過了了目的站目的站對分組頭部的對分組頭部的處理能力處理能力 目的端的高層協(xié)議用戶接收數(shù)據(jù)緩慢目的端的高層協(xié)議用戶接收數(shù)據(jù)緩慢 目的站需要目的站需要轉(zhuǎn)發(fā)數(shù)據(jù)流轉(zhuǎn)發(fā)數(shù)據(jù)流，故源站不可發(fā)送太快，故源站不可發(fā)送太快，目目的端要限制的端要限制入流量入流量以便與以便與出流量出流量匹配匹配 24 2. 在多個協(xié)議層次上實施的流量控制在多個協(xié)議層次上實施的流量控制 多條多條X.25虛電路虛電路(第三級第三級)復用到一條復用到一條LAPB的數(shù)據(jù)鏈的數(shù)據(jù)鏈路上

20、路上(屬于屬于X.25第二級第二級) 多條多條TCP連接復用到一條連接復用到一條HDLC鏈路鏈路 在高級別邏輯連接上，一個邏輯連接上流量控制的在高級別邏輯連接上，一個邏輯連接上流量控制的實施與其它級上邏輯連接上的流量控制無關(guān)實施與其它級上邏輯連接上的流量控制無關(guān) 高級連接上的通信量高級連接上的通信量總和總和在低級別上受到進一步的在低級別上受到進一步的流量控制流量控制 1.6 Flow Control and Error Control25 1.6 Flow Control and Error Control26 3. 流量控制的范圍流量控制的范圍(Flow Control Scope) 一跳的

21、范圍一跳的范圍 在兩個直接連接的中間系統(tǒng)之間，流量控制可在鏈路級實施在兩個直接連接的中間系統(tǒng)之間，流量控制可在鏈路級實施 網(wǎng)絡接口網(wǎng)絡接口 端系統(tǒng)與一個網(wǎng)絡之間的接口鏈路上，可在網(wǎng)絡協(xié)議層實施端系統(tǒng)與一個網(wǎng)絡之間的接口鏈路上，可在網(wǎng)絡協(xié)議層實施 進網(wǎng)到出網(wǎng)進網(wǎng)到出網(wǎng) 在進網(wǎng)到出網(wǎng)節(jié)點在進網(wǎng)到出網(wǎng)節(jié)點間間 端到端端到端 端系統(tǒng)之間，可在端系統(tǒng)之間，可在TCP連接和數(shù)據(jù)鏈路層上進行實施連接和數(shù)據(jù)鏈路層上進行實施 1.6 Flow Control and Error Control27 1.6 Flow Control and Error Control28 1.6 Flow Control and

22、 Error Control 1.6.2 Error Control 1.差錯控制技術(shù)的用途：恢復丟失和損壞的數(shù)據(jù)。差錯控制技術(shù)的用途：恢復丟失和損壞的數(shù)據(jù)。 2.差錯控制技術(shù)原理：包括差錯檢測以及差錯控制技術(shù)原理：包括差錯檢測以及PDU重傳。重傳。 3.差錯控制和流量控制在一個單一的機制中差錯控制和流量控制在一個單一的機制中一同實現(xiàn)一同實現(xiàn)。 4.可在多種協(xié)議級別上實現(xiàn)，差控與流控一樣可在多種協(xié)議級別上實現(xiàn)，差控與流控一樣 。29 3 techniques at link level: Stop-and-wait Go-back-N Selective-reject 后二種是滑動窗口的特例！

23、后二種是滑動窗口的特例！ 1.6 Flow Control and Error Control30 Sequence of Frames reasons： 理由如下：理由如下： 接受端的緩存大小可能有限。接受端的緩存大小可能有限。 傳輸數(shù)據(jù)越長，出錯的可能性越大，較小的幀可能傳輸數(shù)據(jù)越長，出錯的可能性越大，較小的幀可能更快的檢測出差錯，需重傳的數(shù)據(jù)量也較小。更快的檢測出差錯，需重傳的數(shù)據(jù)量也較小。 在共享媒體上，要避免一個站占據(jù)媒體時間過長，在共享媒體上，要避免一個站占據(jù)媒體時間過長，以免造成其他發(fā)送站很長的時延。以免造成其他發(fā)送站很長的時延。 1.6 Flow Control and Err

24、or Control31 1.7 Performance of ARQ 1.7.1 停止等待停止等待ARQ (Stop and Wait ARQ) 1. 無差錯停止等待流控無差錯停止等待流控(Error-Free Stop and Wait) T = Tframe + Tprop + Tproc + Tack + Tprop + Tproc 發(fā)送數(shù)據(jù)的總時間可以表達為發(fā)送數(shù)據(jù)的總時間可以表達為nT，其中，其中T是發(fā)送一個是發(fā)送一個幀和收到一個確認并準備發(fā)送下一幀的時間幀和收到一個確認并準備發(fā)送下一幀的時間 Tframe傳送一幀的時間，即發(fā)送端將所有位都發(fā)出的時間傳送一幀的時間，即發(fā)送端將所有位

25、都發(fā)出的時間 Tprop 發(fā)送端和接收端之間的傳播時延發(fā)送端和接收端之間的傳播時延 Tproc 每個站的處理時間每個站的處理時間 Tack 傳送一個確認的時間傳送一個確認的時間 假定假定Tproc和和Tack都相對較小都相對較小 T = Tframe + 2Tprop 32 假定幀是定長大小，則停止等待流量控制允許數(shù)據(jù)假定幀是定長大小，則停止等待流量控制允許數(shù)據(jù)以每以每T秒一幀的速率傳送，秒一幀的速率傳送，T近似為：近似為： T Tframe + 2Tprop 表示每表示每T T秒一幀的速率傳送秒一幀的速率傳送 吞吞吐量吐量(Throughput) = 1/T = 1/(Tframe + 2T

26、prop) frames/sec 如果一個幀可以在如果一個幀可以在Tframe秒內(nèi)傳送完，該鏈路的秒內(nèi)傳送完，該鏈路的實際實際數(shù)據(jù)率數(shù)據(jù)率為：為： 1/ Tframe frames/sec 歸一化吞吐量歸一化吞吐量S可以表示為：可以表示為：S吞吐量吞吐量/實際數(shù)據(jù)率實際數(shù)據(jù)率 1/(Tframe + 2Tprop) Tframe 1 1/ Tframe Tframe + 2Tprop 1 + 2a 其中：其中：a = Tprop / TframeS = 1.7 Performance of ARQ 33 2. Stop-and-Wait ARQ with Errors P =單個幀出現(xiàn)差錯的概

27、率單個幀出現(xiàn)差錯的概率 1 1 P (Nx是由于出現(xiàn)差錯，每個幀需要傳輸?shù)钠骄螖?shù)是由于出現(xiàn)差錯，每個幀需要傳輸?shù)钠骄螖?shù)) 發(fā)送成功一幀所需的平均時間發(fā)送成功一幀所需的平均時間 T = Nx (Tframe + 2Tprop) 歸一化吞吐量歸一化吞吐量 S = Tframe / Nx (Tframe + 2Tprop) 1 1 - P Nx (1 + 2a) (1 + 2a)S =Nx= 1.7 Performance of ARQ 343.Error-Free Sliding Window ARQ 1.7 Performance of ARQ 35 1.7 Performance of A

28、RQ 36線路的吞吐量取決于窗口大小線路的吞吐量取決于窗口大小W和和a的值的值 Case 1: W 2a + 1 對幀對幀1的確認在的確認在A消耗完其窗口消耗完其窗口前前就到達了就到達了A。A可以可以不停地連續(xù)傳輸。不停地連續(xù)傳輸。 Case 2: W 2a +1 A在在t=W時刻就耗盡了它的窗口，直到時刻就耗盡了它的窗口，直到t= 2a +1時刻前時刻前都不能再發(fā)送幀。都不能再發(fā)送幀。 1.7 Performance of ARQ 37Normalized Throughput 1 W 2a+1 S = W W 2a+1 2a + 1 1.7 Performance of ARQ 384.

29、Selective Reject ARQ 1 - P W 2a + 1 S = W(1 - P) W 2a +1 2a + 1P：單個幀出錯的概率。：單個幀出錯的概率。 1.7 Performance of ARQ 395. Go-Back-N ARQ 1 - P W 2a + 1 1 + 2aPS = W(1 - P) W RD / 4 此連接上可得到最大可能的吞吐量 S = 4W W RD / 4 W與RD/4的比率 RD 1.8 TCP Flow Control 45 1.8 TCP Flow Control 46 1.8.1 窗口大小對性能的影響窗口大小對性能的影響(3) TCP連接要

30、考慮的因素：連接要考慮的因素： 許多許多TCP連接連接復用復用到同一個網(wǎng)絡接口上，每條連接只分到可到同一個網(wǎng)絡接口上，每條連接只分到可得容量的一部分，得容量的一部分，降低了降低了R因子因子的大小并因此降低了傳輸效率的大小并因此降低了傳輸效率 許多許多TCP連接連接跨越跨越多個網(wǎng)絡，多個網(wǎng)絡，D是穿過每個是穿過每個網(wǎng)絡的時延網(wǎng)絡的時延加上加上在每個在每個路由器路由器上經(jīng)受的上經(jīng)受的時延時延，路由器時延經(jīng)常是主要成分，尤其，路由器時延經(jīng)常是主要成分，尤其在擁塞時在擁塞時 如果源端如果源端TCP實體處連接的數(shù)據(jù)率實體處連接的數(shù)據(jù)率R超過超過從源端到目的端某從源端到目的端某一跳的數(shù)據(jù)率，一跳的數(shù)據(jù)率，

31、這一跳這一跳將會是數(shù)據(jù)傳輸?shù)钠款i，從而使將會是數(shù)據(jù)傳輸?shù)钠款i，從而使D增加增加 若報文段丟失進行若報文段丟失進行重傳重傳，也會降低吞吐量，影響程度的大小，也會降低吞吐量，影響程度的大小取決于重傳策略取決于重傳策略 1.8 TCP Flow Control 47 1.8.2 重傳策略重傳策略(Retransmission Strategy) 1. TCP的差錯控制方案的差錯控制方案 TCP 完全依靠確認應答，當確認在給定的一個完全依靠確認應答，當確認在給定的一個超時超時時段時段中沒有到達時就進行重傳中沒有到達時就進行重傳 在兩種情況下，報文段應該重傳在兩種情況下，報文段應該重傳 1. 報文段中攜

32、帶的報文段中攜帶的效驗和效驗和讓接受端檢測到報文有讓接受端檢測到報文有差錯差錯，隨即，隨即丟棄這個報文，不會發(fā)丟棄這個報文，不會發(fā)ACK 2. 報文段報文段沒有達到目的地沒有達到目的地，不會發(fā)，不會發(fā)ACK 1.8 TCP Flow Control 48 1.8.2 重傳策略重傳策略(Retransmission Strategy) 2. 定時器定時器(Timers) 對發(fā)送出去的每個報文段都要設置一個對發(fā)送出去的每個報文段都要設置一個定時器定時器 如果在收到一個報文段的確認之前定時器就超時了，如果在收到一個報文段的確認之前定時器就超時了，發(fā)送方必須重傳發(fā)送方必須重傳 (1) 關(guān)鍵設計問題為關(guān)

33、鍵設計問題為(Key Design Issue): 如何確定重傳定時器的取值如何確定重傳定時器的取值 時間時間太小太小: 會造成許多不必要的重傳而浪費了網(wǎng)絡容量會造成許多不必要的重傳而浪費了網(wǎng)絡容量 時間時間太大太大: 協(xié)議對于報文段丟失的反應就會很遲緩協(xié)議對于報文段丟失的反應就會很遲緩 1.8 TCP Flow Control 49 (2) 確定重傳定時器取值的確定重傳定時器取值的兩種策略兩種策略(Two Strategies): 定時器應該設定為一個比定時器應該設定為一個比往返時延往返時延(發(fā)送報文段，接收發(fā)送報文段，接收ACK)稍大稍大的值的值 但是往返時延會發(fā)生變化，并且時延的統(tǒng)計特性

34、會隨互聯(lián)網(wǎng)但是往返時延會發(fā)生變化，并且時延的統(tǒng)計特性會隨互聯(lián)網(wǎng)狀況的變化而變化狀況的變化而變化 可采用的兩種策略是：可采用的兩種策略是： 1. 固定的定時器固定的定時器(Fixed timer) 2. 自適應自適應(Adaptive) 1.8 TCP Flow Control 50 (3) 自適應方案存在的問題自適應方案存在的問題(Problems with Adaptive Scheme) 對等的對等的TCP實體進行實體進行累積確認累積確認，并不立即確認一個報文段，并不立即確認一個報文段 如果一個報文段被重傳如果一個報文段被重傳過過，發(fā)送方無法了解收到的，發(fā)送方無法了解收到的ACK是是對對最

35、初最初傳輸?shù)倪€是對重新傳輸?shù)拇_認傳輸?shù)倪€是對重新傳輸?shù)拇_認 互聯(lián)網(wǎng)的狀態(tài)可能互聯(lián)網(wǎng)的狀態(tài)可能突然突然發(fā)生變化發(fā)生變化 1.8 TCP Flow Control 51 1.8.3 自適應重傳定時器自適應重傳定時器(Adaptive Retransmission Timer) 關(guān)注關(guān)注最近最近的報文段時延模式估計目前的往返時延。將的報文段時延模式估計目前的往返時延。將定時器設置為一個比估計的往返時延定時器設置為一個比估計的往返時延大一些大一些的值的值 平均往返時間平均往返時間(Average Round-Trip Time) K + 1 1 RTT(i) K + 1 i = 1 K 1 K + 1

36、 K + 1ARTT(K + 1) = = ARTT(K) + RTT(K + 1) 1.8 TCP Flow Control 52 1.8.3 自適應重傳定時器自適應重傳定時器(Adaptive Retransmission Timer) 基于一個時間序列的基于一個時間序列的過去值預測過去值預測其其下一個值下一個值有一種常有一種常用的技術(shù)即用的技術(shù)即指數(shù)平均指數(shù)平均。 平滑往返時間估值平滑往返時間估值(Smoothed Round-Trip Time ) SRTT(K + 1) = SRTT(K) + (1 ) RTT(K + 1) = 2SRTT(K-1)+ (1- )RTT(K)+(1-

37、 )RTT(K+1) =(1- )RTT(k+1)+ (1- )RTT(K)+ 2 (1- ) RTT(k-1) + k(1- )RTT(1) 常數(shù)常數(shù)0 1 觀察值越陳舊，在平均值中計入的就越少觀察值越陳舊，在平均值中計入的就越少 1.8 TCP Flow Control 53 1.8 TCP Flow Control =0.5 =0.87554 1.8 TCP Flow Control 55 3. RFC 793 重傳定時器時間重傳定時器時間 RTO(K + 1)= SRTT(K + 1)+ 公式的問題：公式的問題： RTO(K + 1) =Min(UB, Max(LB, SRTT(K +

38、 1) UB, LB: 預先選定的定時器值的固定上限值和下限值 Example values for , : 0.8 0.9 1.3 2.0 1.8 TCP Flow Control 56 動態(tài)選路可通過將動態(tài)選路可通過將負載均勻分布負載均勻分布到交換機和鏈路上到交換機和鏈路上來幫助緩解擁塞的目的來幫助緩解擁塞的目的 但這種措施但這種措施只在處理不平衡負載的只在處理不平衡負載的短期短期通信量集聚通信量集聚的情況時有效的情況時有效 最終最終擁塞擁塞只能通過只能通過將將進入進入互聯(lián)網(wǎng)的互聯(lián)網(wǎng)的數(shù)據(jù)總量限制數(shù)據(jù)總量限制為為互聯(lián)網(wǎng)可以承載的量的互聯(lián)網(wǎng)可以承載的量的方法控制方法控制 ICMP源站抑制報文

39、手段原始，但不是有效的手段源站抑制報文手段原始，但不是有效的手段能控制擁塞能控制擁塞 RSVP可能在控制擁塞上會起作用，但離可能在控制擁塞上會起作用，但離廣泛廣泛實施實施還有一段距離還有一段距離 1.8 TCP Congestion Control 57 基于基于TCP/IP的互聯(lián)網(wǎng)中擁塞控制是復雜而困難的的互聯(lián)網(wǎng)中擁塞控制是復雜而困難的 IP是一個是一個無連接無連接、無狀態(tài)無狀態(tài)的協(xié)議，它沒有提供檢測的協(xié)議，它沒有提供檢測更不用說控制擁塞的機制更不用說控制擁塞的機制 TCP只提供只提供端到端端到端流量控制，流量控制，間接推測間接推測擁塞，而且擁塞，而且網(wǎng)絡或互聯(lián)網(wǎng)中網(wǎng)絡或互聯(lián)網(wǎng)中時延時延可變

40、且可變且很長很長，對網(wǎng)絡狀況了解并不，對網(wǎng)絡狀況了解并不可靠可靠 各各TCP實體之間實體之間并沒有相互合作并沒有相互合作的分布式算法將它的分布式算法將它們聯(lián)結(jié)在一起，不可能將總流量維持在一定水平上，更們聯(lián)結(jié)在一起，不可能將總流量維持在一定水平上，更可能可能相互競爭資源相互競爭資源 1.8 TCP Congestion Control 58 1.8.4 TCP Flow and Congestion Control TCP實體可以發(fā)送數(shù)據(jù)的速率，取決于對以前報文實體可以發(fā)送數(shù)據(jù)的速率，取決于對以前報文段確認的段確認的ACK的速率所確定，并可攜帶新的的速率所確定，并可攜帶新的信用量信用量 ACK到

41、達速率是由到達速率是由源端源端與與目的端目的端之間之間往返路徑往返路徑上的上的瓶頸瓶頸所確定的；所確定的；TCP能自動感知網(wǎng)絡瓶頸并對其流量作能自動感知網(wǎng)絡瓶頸并對其流量作出調(diào)整，它稱為出調(diào)整，它稱為TCP自同步行為自同步行為 瓶頸可能是瓶頸可能是目的端目的端也可能是也可能是互聯(lián)網(wǎng)互聯(lián)網(wǎng) 源端無法知道瓶頸是源端無法知道瓶頸是目的端目的端(流量控制流量控制)還是還是互聯(lián)網(wǎng)互聯(lián)網(wǎng)(擁塞控制擁塞控制) 互聯(lián)網(wǎng)上的瓶頸是由擁塞造成，源端應比互聯(lián)網(wǎng)上的瓶頸是由擁塞造成，源端應比ACK速率速率更慢更慢的速率傳輸報文段，以緩解擁塞的速率傳輸報文段，以緩解擁塞(擁塞控制擁塞控制) 由目的端流控造成的由目的端流

42、控造成的低低速率，則發(fā)方速率，則發(fā)方TCP實體應以實體應以該速率傳播該速率傳播(流量控制流量控制) 1.8 TCP Congestion Control 59 1.8 TCP Congestion Control 60 1.8 TCP Congestion Control 61 1.8.5 重傳定時器管理重傳定時器管理(Retransmission Timer Management) 三種技術(shù)用于解決重傳定時器三種技術(shù)用于解決重傳定時器(RTO)的計算問題：的計算問題： (1) RTT 方差估計方差估計 (2) 指數(shù)指數(shù)RTO 退避退避 (3) Karn算法算法 1.8 TCP Congestion Control 62 1. RTT方差估算（方差估算（Jacobson算法）算法） 3種高方差的來源種高方差的來源 如果如果TCP連接上的數(shù)據(jù)率連接上的數(shù)據(jù)率較低較低，傳輸時延傳輸時延與與傳播時傳播時間間的比值相對的比值相對較大較大。而且。而且IP數(shù)據(jù)報大小的變化引起的數(shù)據(jù)報大小的變化引起的時時延的方差延的方差也很大，也很大，SRTT估算值會受到數(shù)據(jù)特性而不是網(wǎng)估算值會受到數(shù)據(jù)特性而不是網(wǎng)絡特性的很大影響絡特性的很大影響 負