章渺，吳建平，徐恪
(清華大學 計算機科學與技術系，北京 100084)
收稿日期：2002-11-04
基金項目：國家自然科學基金資助項目（69725003, 90104002, 60203025）
作者簡介：章渺（1976-），男（漢），浙江，博士研究生。E-mail: zm@csnet1.cs.tsinghua.edu.cn
通訊聯系人：徐恪，講師。E-mail: xuke@csnet1.cs.tsinghua.edu.cn
文 摘: 傳輸控制協議(TCP)是目前在Internet 上使用最廣
泛的傳輸協議。理論和試驗表明TCP 連接在壹些情況下是
不公平的，這些情況包括多擁塞網關、不同的往返延遲和
不同報文大小等。該文提出壹種“顯式公平控制”(EFC)
算法來解決這個問題，其主要思想是通過在網關和端系統
都增加機制來單獨進行公平控制。在TCP 的報文頭中增加
壹個“速率標簽”來攜帶目前的發送速率，網關可以使用
報文頭中的這個信息對報文區別對待。試驗結果表明EFC
算法可以有效的改善TCP 連接的公平性。該文還討論了如
何在Internet 中逐步使用EFC 算法。
關鍵詞：傳輸控制協議(TCP)；公平性；擁塞控制
中圖分類號: TP393
傳輸控制協議(TCP)是目前Internet 中主要使
用的傳輸協議。TCP 的壹些設計特性使得TCP 連
接在壹些環境中無法達到公平。TCP 中使用的
AIMD算法[1]在反饋延遲不同的情況下無法達到壹
個公平的平衡點。TCP 使用的“二值反饋”機制在
多擁塞網關的環境下也可以導致不公平的出現。研
究表明，壹個經過多個擁塞網關的連接只能得到非
常低的吞吐量[2]。
Floyd 提出“Constant-Rate”(CR)窗口增加算
法[2]來改善TCP 連接在不同往返延遲(RTT)環境下
的公平性。每個連接增大窗口的量為a ?RTT ，
其中a 是壹個常數。New-ECN[3]在改善公平性方
面也使用了類似的思路。CR 和New-ECN 算法都
只修改端系統，這使得它們很容易在實際網絡中使
用，但都無法解決多擁塞網關環境中的不公平問
題。Fair queue[4]和FRED[5]通過在網關中增加機制
來改善公平性。它們不需要改變端系統的算法，但
在實現上需要使用“單流信息”，在算法的擴展性
上存在問題。
本文提出壹個“顯式公平控制”算法(EFC:
Explicit Fairness Control)來改善TCP 的公平性。其
主要思想是：通過在端系統和網關中都增加機制來
單獨進行公平控制。在TCP 報文頭中增加壹個“速
率標簽”(Rate-Tag)來表明TCP 連接當前的發送速
率；網關根據發送速率的不同對報文進行區別對
待。在算法的設計中，盡量對當前的體系結構只做
簡單的修改，從而使EFC 算法可以在Internet 中逐
步推廣使用。
1 背景
圖1 顯示了壹個多擁塞網關的典型拓撲結構，
其中擁塞的網關為1a, 2a, ?, na。假設pi 是在網
關ia 處的報文丟失概率，那麽連接0 的丟失概率
為：
== - -
n
i
i P p
1
0 1 (1 ) .
如果假設p p p p n = = ...= = 1 2 ，而且p 的值很
小，那麽：
P =1- (1- p) n ? np 0 . (1)
由於連接0 和其它連接相比經歷更多的報文
丟失，在其它條件相同的情況下它的性能要比其它
連接更差。在實際網絡中，壹個經過多擁塞網關的
連接很有可能經歷更大的傳播延遲(propagation
delay)和排隊延遲(queuing delay)，這樣它的性能會
進壹步降低。
在TCP 建模方面的研究為更加準確的評價不
同往返延遲和多擁塞網關對TCP 公平性的影響提
供了條件。TCP 的壹個速率公式為[6]：
S 1a 1b 2a 2b na nb 0
S1 S2 Sn
0
1 2 n
D1 D2 Dn
D0
圖1 網絡拓撲1
2
) (1 32 )
8
3
(3
3
2 p p 2
p
t
p
R
s
T
RTO + +
= , (2)
其中：T 是TCP 的發送速率，s 是報文大小，R 是
往返延遲，p 是穩定狀態下的丟失概率，tRTO 是TCP
重傳時鐘的值。式(2)給出了發送速率的上限。當p
很小時，式(2)可以簡化為：
3
2 p
R
s
T = . (3)
如果2 個連接具有同樣的報文大小和丟失概
率，但有不同的往返延遲R0 和R1，它們的吞吐量
關系為：
0
1
1
0
R
R
T
T
= . (4)
對於多擁塞網關，如果使用式(1)，並且不考
慮往返延遲的差別，圖1 中連接1 和連接0 吞吐量
的比值為n 。
式(3)還揭示了報文大小對於TCP 公平性的影
響。對於兩個往返延遲和報文丟失率相同的連接，
如果它們的報文大小不同，它們的吞吐量之間也是
不公平的，並且有以下關系：
1
0
1
0
s
s
T
T
= , (5)
其中s0 和s1 分別是兩個連接的報文大小。
2 EFC 算法的設計
EFC 算法有兩個主要設計特點。第壹，在網
關中使用了單獨的公平控制機制。由網關計算所有
通過網關連接的“公平份額”。如果壹個連接的發
送速率超過“公平份額”，就使用某種擁塞控制機
制(如Adaptive RED[7])對這個連接的報文進行處
理；如果發送速率低於“公平份額”，這個連接的
報文將不受任何影響的轉發。第二，網關通過報文
中攜帶的“速率標簽”來獲得每個連接的發送速率。
通過在報文中攜帶速率信息，可以避免在網關中保
存“單流信息”，從而使算法具有很好的可擴展性。
2.1 端系統的機制
為實現EFC 算法，只需要在TCP 的發送端進
行簡單的修改，在TCP 的接收端不需要任何修改。
在TCP 的發送端，當發送壹個報文時，在報文頭
中攜帶壹個“速率標簽”來表示連接當前的發送速
率。在擁塞避免階段，TCP 連接的速率由擁塞窗口
的大小(Wcwnd)和往返延遲大小(R)來決定。Rate-Tag
的值為：
V = Wcwnd / R.
在Rate-Tag 的計算中，有兩點需要註意。首
先，擁塞窗口大小可以報文或者以字節為單位。如
果以字節為單位，報文大小不同的TCP 連接之間
的公平性也可以得到改善。其次，EFC 算法的性能
依賴於RTT 測量的準確性。目前TCP 的實現中，
RTT 的測量精度大約為100ms，這個測量精度還比
較粗糙。提高RTT 測量的精度會增加系統的處理
開銷，在實現中需要在處理開銷和公平性的要求之
間進行權衡。
在使用EFC 算法時，應該使用“顯式擁塞通
知”(ECN)[8]作為擁塞的反饋信號。如果把報文丟
失作為反饋信號，丟失報文中的速率信息將不能到
達下遊的網關，從而影響下遊網關“公平份額”計
算的準確性。
2.2 網關的機制
圖2 顯示了網關處的EFC 算法。當壹個報文
到達時，網關從報文頭的Rate-Tag 中獲得連接的
發送速率，然後使用EWMA(Exponential Weighted
Moving Average)方法計算得到發送速率的平均值。
同時，網關使用Adaptive RED 計算得到報文的標
記概率Prob。如果報文中攜帶的發送速率大於計算
得到的平均速率，就以概率Prob 標記報文；否則，
收到的報文將不受影響的轉發。在我們的實現中，
wr 被設定為和wq 相同的值（wq 是Adaptive RED 中
計算平均隊列長度使用的權重）。
EFC 算法只用於改善公平性，它必須和其它
以效率為目標的網關機制***同工作。目前EFC 算
法已應用於壹種“主動隊列管理算法”(AQM:
Active Queue Management)－Adaptive RED 中。
EFC 算法也可以和其它AQM 算法壹起工作。
for each packet arrival
calculate average rate avg_rate:
avg_rate = avg_rate * (1 – wr) + rate * wr
if (rate > avg_rate)
with probability Prob:
mark the arriving packet
else // rate ? avg_rate
no action
Saved Variables:
avg_rate: average sending rate of all TCP connections
Fixed Parameters:
wr: weight used in calculating avg_rate
Other:
rate: sending rate in the Rate-Tag
Prob: marking probability calculated by Adaptive RED
圖2 網關處的EFC 算法
3
3 模擬驗證
使用ns-2 模擬驗證EFC 算法的性能。修改了
TCP Reno 的代碼，使TCP 的報頭中包含Rate-Tag。
試驗比較了使用EFC算法和不使用EFC算法的結
果。使用Fairness Index [1]衡量試驗達到的公平性。
Fairness Index 的定義為
( )
( )
( ) 2
2
=i
i
n x
x
F x .
3.1 試驗1
使用圖1 的拓撲結構驗證EFC 算法在多擁塞
網關環境下的性能。每個鏈路的帶寬為16Mb/s，
報文大小為1kB。在擁塞網關處使用了Adaptive
RED 算法，並按文[7]推薦的值來設定參數。使用
了10 個擁塞網關。從Si到Di (i = 0, 1, …, 10)各建
立20 個TCP 連接。這些連接在0s 時啟動，在200s
時關閉。為了減少RTT 不同對試驗結果的影響，
將從Si 到Di 的延遲都設為63ms。
統計S0 到D0 的吞吐量(T0)和從S1 到D1 的吞吐
量(T1)，並計算在網關1a 的Fairness Index 值(F)。
表1 總結了試驗1 的結果。在不使用EFC 算法時，
T0 不到T1 的1/6。從式(1)得到，對n 個擁塞網關來
說吞吐量的比例大約是n 。從S0 到D0 所經歷的
更長的排隊延遲使這個比例變的更大。在使用EFC
算法後，TCP 連接的公平性得到明顯改善，Fairness
Index 的值從0.648 增長到0.948。
3.2 試驗2
試驗2 用於驗證EFC算法在不同RTT 情況下
的性能。試驗的拓撲結構如圖3 所示，鏈路的帶寬
為16Mb/s。在網關R1 處使用了Adaptive RED，其
參數設置和試驗1 相同。從Si到Di (i = 0, 1)各建立
20 個TCP 連接。從S0到D0 的延遲設定為50ms，
從S1 到D1 的延遲設定為150ms。
試驗2 的結果總結在表2 中。在不使用EFC
算法時，試驗結果和式(4)的結論很壹致，吞吐量
和RTT 的值成反比。使用EFC 算法後，TCP 連接
的公平性得到改善，Fairness Index 的值從0.825 增
長到0.960。
3.3 試驗3
試驗3 用於驗證EFC 算法在不同報文大小情
況下的性能。使用圖3 所示的拓撲，從Si 到Di 的
延遲設為50ms。從Si 到Di (i = 0, 1)各建立20 個
TCP 連接。從S0 到D0 的連接其報文大小設定為
0.5kB，從S1 到D1 的連接其報文大小設定為1.5kB。
表3 反映了試驗3 的結果，其中吞吐量以字節
為單位統計。在不使用EFC 算法時，吞吐量和報
文的大小成正比。在使用EFC 算法後，TCP 的公
平性得到改善，Fairness Index 的值從0.803 增長到
0.986。
4 EFC 算法的過渡機制
由於EFC 算法對目前的網絡體系結構沒有進
行重大的修改，它可以逐步在網絡中推廣使用。我
們可以將EFC 的基本算法進行擴展，用於處理包
含Rate-Tag 報文和不包含Rate-Tag 報文的混合流
量。這個擴展算法如圖4 所示。包含Rate-Tag 的
報文使用EFC 算法處理，在計算平均速率只針對
包含Rate-Tag 的報文進行。對於不包含Rate-Tag
的報文按照概率Prob? k 標記，k 的取值在0 和1
之間。通過引入k 來改善包含Rate-Tag 的連接和不
包含Rate-Tag 的連接之間的公平性。如果不包含
Rate-Tag 的連接也按照概率Prob 標記，那麽從總體
上，它們的標記概率將大於包含Rate-Tag 的連接。
但是，k 的取值是壹個問題。圖5 顯示了在穩
定狀態下TCP 擁塞窗口的變化。TCP 的擁塞窗口
R1 R2
S0
S1
D0
D1
圖3 網絡拓撲2
表1 試驗1
分類 T0/pkt T1/pkt F
不使用EFC 51492 339217 0.648
使用EFC 146854 237111 0.948
表2 試驗2
分類 T0/pkt T1/pkt F
不使用EFC 289411 107093 0.825
使用EFC 237111 146854 0.960
表3 試驗3
分類 T0/MB T1/MB F
不使用EFC 100.655 298.684 0.802
使用EFC 176.094 223.776 0.986
for each packet arrival
if packet has Rate-Tag
process the packet with Rate-Tag algorithm
else // no Rate-Tag
with probability Prob? k:
mark the arriving packet
Fixed Parameters:
k: coefficient for adjusting marking probability; 0< k <1
Other:
Prob: marking probability calculated by Adaptive RED
圖4 EFC 算法的過渡機制
4
在W 和W/2 之間振蕩，平均的窗口大小是
4
3
W。
假設T 是窗口變化的周期，在壹個周期內，擁塞窗
口大於
4
3
W 時發送的報文個數為：
W W T W
T
N = + = ?
16
7
)
4
3
(
2 2
1
1
在壹個周期內發送的總報文個數為：
W T W
W
N = ?T ? + = ?
4
3
)
2
(
2
1
假設網關的報文標記概率為p ，那麽對於使用
Rate-Tag 的連接，總的報文標記概率為：
p p p
N
N
p 0.6
12
7
'= 1 = ?
從上面的分析可以得到，k 的取值約為0.6。然而，
試驗結果顯示，k 的取值應該更大。下面，通過試
驗進壹步確定k 的取值。
再次使用圖3 所示的拓撲結構。從S0 到D0，
創建20 個包含Rate-Tag 的TCP 連接。從S1 到D1，
創建20 個不包含Rate-Tag 的TCP 連接。在網關
R1 處使用圖4 中的算法，對k = 0.6, 0.7, …, 1.0 的
情況分別進行了試驗，試驗結果如表4 所示。k 的
取值在0.7 和0.9 之間時，公平性的指標較好。進
壹步考慮，包含Rate-Tag 的連接最好可以獲得更
多的帶寬，這樣將鼓勵用戶使用EFC 算法。目前
我們選擇k = 0.8。
5 總結
本文在擁塞控制算法的公平性方面進行了研
究，提出壹種算法EFC來改善TCP 連接的公平性。
EFC 算法通過在端系統和網關中增加機制來單獨
進行公平性的控制。EFC 算法在TCP 報文頭中增
加“速率標簽”，網關可以根據這個信息使連接速
率收斂到“公平份額”。試驗結果表明，EFC 算法
在多擁塞網關、不同RTT 和不同報文大小的情況
下都可以改善TCP 連接的公平性。本文還討論了
如何在Internet 中逐步推廣使用EFC 算法，並提出
壹種過渡機制來處理包含Rate-Tag 和不包含
Rate-Tag 報文的混合流量。
參 考 文 獻 (References)
[1] Chiu D, Jain R. Analysis of the increase and decrease
algorithms for congestion avoidance in computer
networks[J]. Computer Networks and ISDN Systems,
1989, 17(1): 1-14.
[2] Floyd S. Connections with multiple congested gateways
in packet-switched networks part 1: one-way traffic[J].
Computer Communication Review, 1991, 21(5): 30-47.
[3] Hamann T, Walrand J. A new fair window algorithm for
ECN capable TCP (new-ECN)[A]. Sidi M. Proceedings
of INFOCOM'2000[C]. Tel Avlv, Israel: IEEE
Communications Society, 2000. 1528-1536.
[4] Demers A, Keshav S, Shenker S. Analysis and
simulation of a fair queueing algorithm[J].
Internetworking: Research and Experience, 1990, 1(1):
3-26.
[5] Lin D, Morris R. Dynamics of random early detection[J].
ACM Computer Communication Review, 1997, 27(4):
127-137.
[6] Padhye J, Firoiu V, Towsley D, et al. Modeling TCP
throughput: a simple model and its empirical
validation[J]. ACM Computer Communication Review,
1998, 28(4): 303-314.
[7] Floyd S, Gummadi R, Shenker S. Adaptive RED: An
Algorithm for Increasing the Robustness of RED’s
Active Queue Management[EB/OL].
http://www.icir.org/floyd/papers/adaptiveRed.pdf,
August 2001.
[8] Floyd S. TCP and explicit congestion notification[J].
ACM Computer Communication Review, 1994, 24(5):
10-23.
表4
k T0/pkt T1/pkt F
0.6 143979 256233 0.927065
0.7 169983 230260 0.977822
0.8 202740 197397 0.999822
0.9 225859 174225 0.983617
1.0 256529 143477 0.926031
擁塞窗
口大小
W
W/2
時間
圖5 穩定狀態下TCP 擁塞窗口的變化