Microsoft Word - Final_project

Size: px

Start display at page:

Download "Microsoft Word - Final_project"

壤陈
5 years ago
Views:

1 Comparisons of Tahoe, Reno, New Reno, and Sack TCP using NS-2 Simulation 姓名 : 張毓琦學號 : M Course : 高等計算機網路文章架構 : 1. 動機與目的 2. 介紹 Tahoe, Reno, New Reno, Sack and Vegas 3. 模擬方法與環境 ( 一 ) 4. 模擬方法與環境 ( 二 ) 5. TCP-Tahoe Reno New Reno Sack 效能分析 6. 分析 TCP-Tahoe Reno New Reno Sack Vegas 之 Congestion window 7. 探討本身實作與參考 paper 實作彼此之差異 1. 動機與目的 : 研究與探討 Tahoe, Reno, New Reno, Sack and Vegas 此四個 TCP 版本的機制與彼此差異之所在 ; 並透過 NS2(network simulator) 這套軟體, 分析各個 TCP 版本在不同 packet loss 情形之機制, 亦即分析只有一個封包遺失以及多個封包遺失等情況下, 不同版本的 TCP 其 congestion window 的變化, 以及對網路傳輸效能之影響參考 Simulation-based Comparisons of Tahoe, Rent, and SACK TCP 此 paper 之模擬環境, 並嘗試用 NS2 做出與其相同結果或相同意義的模擬與分析 2. 介紹 Tahoe, Reno, New Reno, Sack and Vegas 2.1 Tahoe TCP Tahoe 主要有三個機制去控制 flow 和 congestion window: slow start (SS), congestion avoidance (CA), and fast retransmit(fs) SS 機制 : 當 connection 建立時, 把 congestion window 的 size 初始化, 並設為一個 MSS(maximum segment size), 同時把 ssthresh (slow start threshold) 設為 64 (assuming 1KB packet) CA 機制 : 為了在發生雍塞的情形下控制流量 TCP Tahoe 使用 Additive Increase Multiplicative Decrease (AIMD) 此機制 AIMD: 只要有一個 packet loss 就認為網路發生雍塞,Tahoe 會把 ssthrsh 設為目前的 congestion window 的一半並且回到 SS 的狀態, 之後 congestion window 繼續以指數成長 ; 當到達 ssthresh 時 congestion window 會以線性成長來避免雍塞 FS 機制 : 當收到三個重複的 ack 而不必等到 Retransmit Timeout(RTO), 會認為 packet loss 並且馬上重傳 2.2 Reno TCP Reno 除了包含了 Tahoe 的三個機制 (SS,CA,FS),Reno 多了另外一個機制稱為 : Fast Recovery(FR);FR 機制 : 當 Reno 收到三個重複的 ack 或是超過了 RTO 且

2 尚未收到某個封包的 ack,reno 會認為有封包遺失了, 並且認定網路發生雍塞, Reno 會把 ssthresh 設為目前 congestion window 的一半, 但並不會回到 SS 的狀態而是設定 congestion window 為 ssthresh, 之後 congestion window 則維持線性成長以 Fig.1 為說明, 在 round 8 的時候發生了封包遺失, 因此 Reno 把 ssthresh 設為目前 congestion window 的一半亦即是 6,Reno 的 congestion window 並且從 6 開始線性成長 (Fig.1 黑線部分 ) Figure New Reno New Reno 跟 Reno 在只有一個封包遺失的情況下, 其機制是一樣的當同時有多個 packet 遺失時,Reno 會重新傳遞一個發現遺失之封包, 並且跳離 Fast Recovery 的階段, 當 Reno 發現仍舊有其它的封包遺失時,Reno 才會進入 Fast Recovery; 當多個封包遺失時 Reno 必須等待一個 RTO 才能重傳一個遺失的封包, 因此在同一個 congestion window 中有多個封包遺失時,Reno 必須等待多個 RTO, 才能回到 Fast Recovery New Reno 遇到上述的問題並不跳出 Fast Recovery, 當重新重送第一個遺失的封包之後, 會收到 ack 要求下一個遺失的封包 ( 所謂的 partial ack) 此時 New Reno 會重傳第二遺失的封包並且預測後面的封包皆已經遺失並且馬上重傳, 因此不用等待更多的 RTO 2.4 Sack Sack 會在 ack header 的 TCP option field 中清楚告知哪些區段的封包以經被正確收到, 亦即指出已經正確接收區段的第一包封的序號以及最後一封包的序號 ; 當多個封包遺失時,ack header 的 TCP option field 會有多個區段指出哪些區段已經正確收到因此可以明確判斷出那些遺失封包的序號, 並且重傳不同於 New Reno 的預測方式,New Reno 會有已經正確接收的封包再被重新重送 ; 而 Sack 能明確指出哪些封包是遺失的, 因此不會有上述的情狀發生 2.5 Vegas

3 使用 RTT(Round trip time) 測量網路狀況的壅塞控制演算法, 藉由比較預期的效能和實際的效能以決定是否增加或減少壅塞視窗的值 Vegas 修改了 fast retransmit(fs),fast retransmit(fs),congestion avoidance (CA) Modified Fast Retransmit: 當收到一個重覆 ACK 時, 便會特別去檢查 RTT 是否有大於 Timeout, 若有, 則不用等待有 3 個重覆的 ACK, 就直接重送 Modified slow start : cwnd 的值大約在經過兩個 RTT 時間後才會增加一倍 vegas 將佇列長度維持在 α 與 β 之間, 若佇列長度超過此區間, 則將由 slow-start 進入 congestion avoidance Modified congestion avoidance: Diff=expected-actual= When basertt=minimum of all measured RTT linearly increases during nextrtt,diff<α Congestion window= linearly decreases during nextrtt, Diff>β unchange, α<diff<β Diff 的值即是連線路徑 bottleneck 的佇列長度, 該版本的 tcp 主要希望將佇列長度維持在 α 與 β 之間, 並依據 Diff 來調整 slow start threshold 3. 模擬方法與環境 ( 一 ) 3.1 執行環境 : 作業系統 :Window XP + Cygwin 模擬工具 : ns 網路拓樸 :Fig 網路傳輸狀況 : 三條 TCP 從 S1 到 K1, 其中兩條是 background traffic, 我們只觀察其中一條, 亦即其它兩條 background traffic 不改變, 而只對要觀察那條 TCP 做 TCP 版本的變化 Figure 封包遺失設計 : 我們設計一個錯誤模組在 Link (R1,K1), 讓從 R1 傳送到 K1 的封包會有一個 Loss rate; 一個模擬中此條 Link 上每個封包的遺失機率是一樣的 (uniform) 而 S1 到 R1 此 Link 並不會有封包遺失的情況 3.5 模擬設計之意義 : 在現實的網路中, 較常出現的情況是 Link 與 Link 彼此間的差異 ; 此差異是指 Link 的品質而不考慮頻寬與 Propagation delay, 如 : 遺失率等我們藉由調整 Loss rate, 達成封包遺失率高與封包遺失率低之情況,

4 在不同遺失率的情況下來觀察各版本 TCP 其 congestion window 的變化與傳輸效能 4. 模擬方法與環境 ( 二 ) 4.1 執行環境 : 作業系統 :Window XP + Cygwin 模擬工具 : ns 網路拓樸 :Fig 網路傳輸狀況 : 設定一條觀察的 TCP 從 S1 到 K1, 在設定一條 CBR 從 R1 到 K1 4.4 封包遺失之設計 : 藉由控制 CBR 的發動時間與傳輸速率來使 R1 的 queue 溢滿, 進而以 droptail 的方式丟棄 TCP 的封包 4.5 模擬設計之意義 : 觀察五個 TCP 版本在相同的 background traffic 之下, 其 Congestion window 的變化 5. TCP-Tahoe Reno New Reno Sack 效能分析針對 Link-(R1,K1) 上的 loss rate, 分別測試了 Loss rate 為在四種不同的 loss rate 下觀察四個版本 TCP 其 congestion window 與 data throughput Figure 3 Figure 4 Figure 5 Figure7 分別是在 loss rate 為的情況下 Tahoe Reno New Reno Sack 其 congestion window 的變化 ; 其中 X 軸為封包序號 mod 60,Y 軸為模擬的時間單位為秒, 紅點代表 node K1 正確收到的封包, 而綠點則表示 S1 收到來自 K1 的 ack 封包同時統計出模擬期間 K1 總共收到正確的資料封包數量, 由於 TCP 其資料封包大小皆為 1040 bytes, 因此正確收到的資料封包亦即為 Throughput

5 Figure 3

6 Figure 4

7 Figure 5

8 Figure 6

9 Table 1 : 當 loss rate 低時 ( 同時在 Figure 3 觀察只有一個封包遺失時 ),Reno New Reno Sack 比 Tahoe 效能稍稍好點 ; 主要原因在於 Fast recovery 的機制 Loss rate=0.001 Throughput (packets) Tahoe Reno New Reno Sack Table 1 Table 2: 在 loss rate 為時 ( 在 Figure 4 觀察到模擬期間有兩個封包的遺失 ), Tahoe 與 Sack 效能是相似的, 而 Reno 與 New Reno 較差 ; 原因在於 Reno 等待的兩個 RTO 且跳出 Fast recovery, 而 New Reno 則無跳出 Fast recovery, 所以 New Reno 效能比 Reno 稍好 Loss rate=0.005 Throughput (packets) Tahoe Reno New Reno Sack Table 2 Table 3: 在 loss rate 為 0.01 時 ( 在 Figure 5 觀察到模擬期間有三個封包的遺失 ), 由於 Reno 等待三個 RTO 因此效能低落, 而 Sack 比 New Reno 稍好些 ; 原因在於 Sack 的 ack 比 New Reno 少 ;,Sack 與 New Reno 稍微比 Tahoe 好 ; 原因也是在 Fast recovery Loss rate=0.01 Tahoe Reno New Reno Sack Throughput (packets) Table 3 Table 4: 當 loss rate 為 0.05 時 ( 在 Figure 6 觀察到模擬期間有四個封包的遺失 ), 四個版本的 TCP 效能是接近的 ; 原因在於封包遺失率過高時,Tahoe Reno New-Reno Sack 都是長時間處於 congestion window 為 2 到 4 左右的情況, 因此彼此效能所差無幾 Loss rate=0.05 Tahoe Reno New Reno Sack Throughput (packets) Table 4

10 6. 分析 TCP-Tahoe Reno New Reno Sack Vegas 之 Congestion window 6.1 One packet loss Tahoe: NS 版本, 一開始的 cnwd 皆為 2; 在 cnwd 為 8 的時候, 封包 14 遺失, 因此下個回合 cnwd 成長到 16, 但是 sliding-window 在發送封包 28 之後, 發現封包 14 已經有三個重複的 ack 因此先重送封包 14, 再傳送 29 30; 下一個回來 cnwd 又回到 2 個 mms, 因此發送封包 31 32; 且 ssthresh 為 _(8+7)/2_ =7; 當 cnwd 成長到 7 之後開始線性成長 Reno: 當封包 14 遺失, 其回到 FS, 因此 cnwd 減為 8; 之後開始線性成長

11 New-Reno: 在一個封包遺失的情況下跟 Reno 的機制是一模一樣的 Sack: 在只有一個封包遺失的情況下,Sack 與 Reno 其機制只差別在於重複的封包的在 header 上會記載封包 14 遺失而非 ack 封包 13, 因為其 cnwd 是變化是一樣的

12 Vegas: 藉由第一個重複的封包其 RTT 時間, 判斷出要重傳封包 14; 之後依照 Modified slow start 與 Modified congestion avoidance, 其 cnwd 穩定成長 6.2 Two packet losses Tahoe: 封包 14 遺失, 回到 SS 且 ssthresh 為 7, 又發現封包 16 遺失馬上重傳 ; 當 cnwd 為 7 時, 又開始線性成長

13 Reno: 封包 14 遺失,cnwd 減為 7; 又在發現封包 16 遺失, 因此 cnwd 減為 3, 時間為三秒時左右開始線性成長 New-Reno: 發現封包 14 遺失時 cnwd 為 7; 再次發現封包 16 遺失時並沒有馬上跳出 FS 的階段 ; 等到封包 16 重傳並且收到 ack 之後, 保持 cnwd 為 7, 因此封包 36 到 42 進入 queue 的時間是相近的

14 Sack: 接受端收到封包 15 時會回傳 ack 告知封包 14 遺失, 收到封包 17 時會回傳 ack 明確告知封包 16 遺失, 封包 36 到 42 其 cnwd 為 7 之後開始線性成長 Vegas: 藉由第一個重複的封包其 RTT 時間, 判斷出網路雍塞情況, 因此自動緩慢成長 cnwd 而造成在相同的 background traffic 下其它的版本的 TCP 有封包遺失, 而 Vegas 卻無封包遺失, 之後依照 Modified slow start 與 Modified congestion avoidance, 其 cnwd 穩定成長 6.3 Three packet looses

15 Tahoe: 發現封包 7 遺失以後馬上重傳遺失以後馬上重傳且此時 ssthresh 為 7, 並且回到 SS 狀態, 因此傳送 15 16, 再次發現封包 7 遺失, 傳送封包 8 9; 再次發現封包 10 遺失而, 重送 ; 之後 cnwd 之後發現 ack 封包 16, 因此發送 17~22, 此時 cnwd 為 7, 之後繼續線性成長 Reno: 發現多個連續封包遺失, 跳出 FS 並且 ssthresh 為 7; 一開始 cnwd 為 2( 封包 15 16), 之後 cnwd 達到 ssthresh 亦即 7 之後開始線性成長

16 New-Reno: 發現多個連續封包遺失, 設定 ssthresh 為 7; 一開始 cnwd 為 2( 封包 15 16), 發現封包 7 遺失預期封包 8 與 9 也遺失因此重傳, 之後 cnwd 達到 ssthresh 亦即 7 之後開始線性成長 Sack: 重新傳送封包 7 之後, 收到 ack 發現封包 8 遺失, 重新傳送之後又收到 ack 發現封包 10 遺失 ;ssthresh 變為 4 之後 cnwd 之後開始線性成長

17 Vegas: 藉由第一個重複的封包其 RTT 時間, 判斷出網路雍塞情況, 因此自動緩慢成長 cnwd 而造成在相同的 background traffic 下其它的版本的 TCP 有封包遺失, 而 Vegas 卻無封包遺失, 之後依照 Modified slow start 與 Modified congestion avoidance, 其 cnwd 穩定成長 6.4 Four packet losses Tahoe: 封包 7 重新重送之後 ( 此時 ssthresh 為 7),cnwd 從 2 指數成長到 4, 當 cnwd 到 7 時開始線性成長

18 Reno: 發現多個連續封包遺失, 跳出 FS 並且 ssthresh 為 7; 一開始 cnwd 為 2( 封包 15 16), 之後 cnwd 達到 ssthresh 亦即 7 之後開始線性成長 New-Reno: 封包 7 遺失預測封包 8 與 9 也已經遺失因此重送, 發現封包 10 遺失預測後面也遺失, 自動重送封包

19 Sack: 重新傳送封包 7, 發現封包 8 遺失, 重新重送封包 8 9, 發現封包 10 遺失發送封包 10~13, 此時 ssthresh 為 4, 因此 cnwd 到 4 之後開始線性成長 Vegas: 藉由第一個重複的封包其 RTT 時間, 判斷出要重傳封包 5; 之後依照 Modified slow start 與 Modified congestion avoidance, 其 cnwd 穩定成長 7. 探討本身實作與參考 paper 實作彼此之差異在 Simulation-based Comparisons of Tahoe, Rent, and SACK TCP 此 paper 中, 主要是探討 congestion window 的變化, 因此設計為四個版本 TCP 掉的封包序號以及數量皆為相同去觀察其變化 ; 而得到重要的結論為 : 當連續封包遺失的情況下 Sack 表現最優異而本實作不同點在於觀察 Link 上封包遺失率的高低, 對四個 TCP 版本之影響 ; 得到重要的結論為 : 封包遺失率低時,Tahoe 表現最差 ; 而封包遺失率中等時,Reno 表現最差 ; 而在封包遺失率高的情況下, 此四個 TCP 版本的效能是差不多的 ; 同時發現 Sack 為相對於其他三個版本是最穩定的

20 而在網路雍塞突然發生時,Vegas 是最穩定的, 因為其多了 RTT 的判斷等新機制

穨control.PDF

穨control.PDF TCP congestion control yhmiu Outline Congestion control algorithms Purpose of RFC2581 Purpose of RFC2582 TCP SS-DR 1998 TCP Extensions RFC1072 1988 SACK RFC2018 1996 FACK 1996 Rate-Halving 1997 OldTahoe