一種邊界到邊界的擁塞感知的三色標記器
2009-01-01 00:00:00周雄偉馬費成余以勝榮輝桂
計算機應用研究 2009年2期
（1.武漢大學 信息管理學院， 武漢 430072; 2. 華南理工大學 電子商務系， 廣州 510006）
摘 要：
通過對基本的流量標記，特別是在CATC、CASR3CM和ITSW3CM研究的基礎上提出了擁塞感知的流量標記器CATSW3CM。理論分析和仿真實驗表明，CATSW3CM與CATC相比，不僅提高了AS TCP流的平均吞吐量，而且增強了吞吐量的穩定性，提高了AS TCP流之間占用帶寬的公平性，并且更為簡單，具有很好的擴展性。
關鍵詞：區分服務; 確保服務; 擁塞感知; 包標記
中圖分類號：TP393 文獻標志碼：A
文章編號：1001-3695(2009)02-0648-04
Based on edge-to-edge congestion aware three color marker
ZHOU Xiong-wei1，MA Fei-cheng1， YU Yi-sheng2， RONG Hui-gui1
(1.School of Information Management， Wuhan University， Wuhan 430072， China; 2. Dept. of Electronic Commerce， South China University of Technology， Guangzhou 510006， China)
Abstract:Based on researching packet marker， especially CATC， CASR3CM and ITSW3CM， designed anew marker which is called as CATSW3CM (congestion aware time slide window three color marker). The theory analysis and simulation results indicates that CATSW3CM not only improves the throughput of AS TCP flowand the stability of the throughput， but also improves the fairness of bandwidth sharing between AS TCP flows than CATCandCASR3CM. What’s more，it also improves the throughput of AS TCP flow， it is simpler and more scalable than CASR3CM.
Key words：differentiated services; assured services(AS); congestion aware;packet marking
0 引言
確保服務(AS)[1]是區分服務網支持超過因特網的盡最大努力的一種重要服務。確保服務是從統計上保證用戶的帶寬，傾向于給客戶最小的流量保證，即目標速率。確保服務實現機制非常簡單，在邊緣路由器根據用戶的流規格將數據包標記為不同的丟棄優先級，而在核心路由則采用主動隊列管理(AQM)算法機制，如RED、CHEOKE、CSFQ、BLUE、ECHOKE等[2~6]經典算法。在發生擁塞時，AQM首先丟棄低優先級的數據包，盡量保護高優先級的數據包，從而達到為不同用戶提供不同級別服務的目的。因此，確保服務依靠在邊緣路由通過流量調節器(TC)執行的包標記策略和在核心路由的隊列管理策略來實現[7，8]。
在Internet上通過TCP協議傳輸流幾乎占了總個鏈路的95%。但TCP 流由于其擁塞自適應的特點導致對丟包很敏感，網絡擁塞對其吞吐量影響很大[9]，因此提高TCP流在網絡擁塞中的流量公平性成為當前的研究熱點[10~12]。許多研究者都從主動隊列管理轉到通過包標記區分服務網的邊界來提高網絡流量的公平性的研究[13~19]。其中文獻[13]提出邊界到邊界的反饋機制和能夠預先積極感知擁塞的智能標記器(CATC)。該標記器利用控制機制提供的擁塞因子(congestion factor，CF)來反映TCP流的動態變化，使其為TCP流提供確保服務。本文主要就是在利用文獻[13]提出的邊界到邊界擁塞感知機制以及研究一些較新的相關標記器基礎上，設計了一個改進的基于邊界到邊界擁塞感知的三色標記器CATSW3CM。
1 流量標記器及其性能分析
1. 1 CATC及其性能分析
CATC[13]的基本思想是采用DiffServ網絡邊界到邊界(edge-to-edge)的擁塞反饋控制機制，在標記中兼顧了網絡擁塞對TCP流的影響。在這個體系結構中，發送端邊界路由器通過向接收端邊界路由器發送探測包，便能獲知所經過的路徑中是否發生擁塞，能夠比端到端的擁塞反饋控制機制更好地了解DiffServ域的網絡狀況來進行包標記，從而使得該標記器考慮當前網絡的擁塞變化，并相應地動態增加或減少標記概率。
但在文獻[15]中發現CATC的主要缺陷是發送端邊界路由器得到的擁塞信息由于傳輸延遲，往往不能準確地反映網絡的實際擁塞狀況。如果網絡擁塞(或不擁塞)持續時間較長，那么這種影響是有限的。文獻[15]中的一系列實驗表明CATC在保障AS TCP 流的目標速率方面有較好的效果。但Internet上數據的本質是突發的，這種突發本質往往會導致短暫的突發擁塞，此時CATC的性能就會大大下降。
1. 2 ITSW3CM及其性能分析
ITSW3CM是Sun等人[10]在TSW3CM[14]基礎上進行的一個改進的標記器，通過對TSW3CM的區間進行重新劃分，使得標記為YELLOW的聚集流包的概率與目標速率cir成比例，提高網絡中聚集流超過帶寬時的聚集流共享的公平性。
在ITSW3CM激勵源服從它們的服務速率，并保護TCP友好流不受UDP非適應流的侵略。但是文獻[16，19]發現ITSW3CM中，當cir 1. 3 CASR3CM及其性能分析 為了改進CATC的缺陷，文獻[15]提出了擁塞感知的單速率三色標記 (CASR3CM)。CASR3CM引入了變量par記錄前一個數據包到達時的平均速率。通過將par和avg_rate進行比較，可以感知流速是在增加還是在減小以便及早發現擁塞。CASR3CM提高了在遇到頻繁短暫擁塞時保障AS TCP流目標速率的能力、AS流吞吐量及其穩定性。 通過分析可以發現，CASR3CM為了及早發現擁塞，需要額外記錄每個流的par信息，在路由器維持活動流的狀態信息會給路由器帶來額外的開銷，使算法復雜度增加，不利于擴展。另外，實際上在區分服務網中，當avg_rate＜cir時，在TSW3CM和ITSW3CM中，它們不管出不出現擁塞都會全部標記為GREEN來保證區分服務的QoS。而CATSW3CM會出現當沒有發生擁塞并且avg_rate＜cir的流時，可能把更多的包標記為YELLOW、RED來對其進行懲罰性的處理。這本質上會違背區分服務提供QoS。同時CASR3CM標記包時思想很復雜，其中根據擁塞的反饋機制計算標記概率，在實際標記時情況很復雜，不像CATC全部把該概率標記為IN來直接反映擁塞感知的作用，并沒有明顯地起到反映擁塞感知的標記作用。 2 CATSW3CM CATSW3CM主要是綜合利用CATC、CASR3CM和ITSW3CM的優點進行改進。設計的主要目標是：a)利用DiffServ網絡邊界到邊界的擁塞反饋控制機制，在標記器中充分考慮網絡擁塞對TCP流的影響，實現AS達到或接近目標速率；b)減少標記器對網絡短暫突發擁塞的影響，提高對AS流吞吐量的穩定性；c)進一步加大對非適應流的懲罰力度而對TCP友好流進行保護的機制，提高標記器對AS流按目標速率的比例公平共享鏈路帶寬。 CATSW3CM利用三色標記的思想，把到達包標記為GREEN、YELLOW 和RED三個不同的優先級。同時CATSW3CM也利用CATC中通過DiffServ網絡邊界到邊界擁塞反饋控制機制中反映網絡擁塞信息的擁塞因子來反映TCP流的動態變化。CATSW3CM中計算標記概率mp時與CASR3CM一樣用目標速率總和cir_total代替CATC中的cir_max，并對表達式作適當修改，以適應三色標記器的需要。mp具體的標記器算法如下： For each packet arrival avg_rate=Estimated avg traffic sending rate; if (avg_rate<=cir) mark the packet GREEN; else if (cir mp=mp+(avg_rate/cir-1)*(1+cf*(cir/cir_total)); with probability mp the packet is marked as YELLOW; with probability (1-mp) the packet is marked as GREEN; else if (avg_rate>pir) mp=mp-(avg_rate/cir-1)*(1+cf*(cir/cir_total)); with probability mp the packet is marked as YELLOW; with probability (1-mp) the packet is marked as RED; CATSW3CM通過三個不同的區段進行標記：當avg_rate＜cir時全部標記為綠色，這能滿足區分服務對QoS的保證；當avg_rate在cir與pir之間時，一般網絡剛好處于區分服務的服務等級預訂狀態，因此把到達包以更大概率mp標記為YELLOW，以概率1-mp標記為GREEN；當avg_rate＞pir時，事實上網絡已經超過了區分服務的服務等級預訂，則把到達包以更小的概率mp標記為YELLOW，而把包以其他大部分的概率1-mp標記為RED對其進行懲罰。CATSW3CM既利用CATC采用的DiffServ網絡邊界到邊界的擁塞反饋控制機制反應網絡擁塞對TCP流的影響，又充分利用ITSW3CM的思想加大對非適應流的懲罰力度而保護TCP友好流的機制。與CASR3CM相比，利用雙速率進行標記不用記錄每個流的信息，使其更簡單且具有很好的擴展性能。 標記概率如圖1所示。其中k=avg_rate/cir。 從圖1可以看出，CATSW3CM通過對于TCP流在不同的速率區段采取不同的懲罰力度，很好地消除了TSW3CM和ITSW3CM的不合理區段。當avg_rate＜cir時全部標記為綠色，就能更好地保護帶寬競爭力弱的流的目標帶寬，即使在發生擁塞時也把這些帶寬競爭力較弱的流標記為GREEN包，從而提高這些流的吞吐量，增加帶寬分配的公平性；當cir CATSW3CM根據cir和pir兩個速率來標記到達的包，不同于CASR3CM和CATC只根據一個cir速率來標記到達的包，它可以充分利用網絡的帶寬，提高網絡對于AS流的吞吐量。同時如1.3節分析的CASR3CM標記包時思想很復雜，而CATSW3CM則根據擁塞的反饋機制計算mp，在標記時不管在哪種情況下都以mp標記為YELLOW，非常明顯地反映擁塞的狀態對包進行不同的標記，完全符合CATC提出的擁塞感知的標記思想。 3 CATSW3CM性能分析 為了驗證CASR3CM的有效性，筆者在網絡仿真軟件NS2[20]上實現了CATC、CASR3CM和CATSW3CM，并進行了一系列實驗結果比較分析。實驗的網絡拓撲如圖2所示。在實驗中S1到S2表示源，D1到D2表示接收者。假設所有的中間域都具有區分服務能力。在網絡中控制包流總是有超過其他流的最高優先權。中間路由器有RIO相似的機制提供區分服務和基于狀態標志的標記控制包。所有的路由器都具有ECN[21]功能。圖中的體系結構所有從R1到R5的鏈路帶寬都相同，標記器放置在邊緣路由器R1。R1是控制包發送者，R5是控制接收者。在區分服務域中，R2和R4是邊緣路由器，R3是核心路由器。在所有的實驗中使用FTP大批數據轉發TCP流量。實驗中用到 3. 1 只有TCP流情況下保障AS TCP流目標速率的能力 該實驗中，分別考察AS TCP流的目標速率未完全預訂和過分預訂兩種情況。實驗的數據流由兩個AS TCP 聚流（分別由六個單流組成）和一個BE TCP 聚流（由九個單流組成）組成。實驗數據如表2、3所示。其中：Rt1和Rt2分別表示兩個AS TCP聚流的目標速率；Ra1和Ra2表示其分別獲得的實際速率；BE TCP 表示盡力而為的TCP流所獲得的速率。 從表2中可以看出，在AS TCP流未過分預訂的情況下，CATSW3CM和CATC都能達到它們的目標速率，并且其實際獲得的速率比目標速率要大；而CASR3CM也基本上能接近它們的目標速率，但實際獲得的速率都沒有達到目標速率。這完全證實了對CASR3CM性能分析的缺陷：CATSW3CM會出現在沒有出現擁塞且avg_rate＜cir的流時，可能把更多的包標記為YELLOW、RED來對其進行懲罰性的處理，這本質上會違背區分服務對QoS保證的能力，使得其實際獲得的速率比它們的目標速率要小一些。而在按目標速率的比例公平共享帶寬方面，CATSW3CM明顯優于CATC而與CASR3CM相當。對于總的目標速率，CATSW3CM總的實際獲得速率要比CASR3CM和CATC總的實際獲得速率要大一些，CATSW3CM搶占了更多的BE TCP流的帶寬。數據目標速率為3Mbps AS TCP流的吞吐量—時間關系如圖3所示。 從圖3可以看出，CATC在發生擁塞時由于其標記概率變化過大，使得AS TCP流吞吐量的變動幅度波動很大；而CATSW3CM和CASR3CM使得AS TCP流的吞吐量的穩定性大大增加。在AS TCP流過分預訂的情況下性能比較如表3所示。 表3在AS TCP流過分預訂的情況下性能比較 從表3可以看出，當AS TCP流過分預訂時，在保證獲得目標速率方面CATSW3CM明顯優于CATC和CASR3CM：CATSW3CM的實際獲得速率基本上更接近它們的目標速率，而CATC和CASR3CM的實際獲得速率與它們的目標速率相差還是較大。數據目標速率為8 Mbps AS TCP流的吞吐量—時間關系如圖4所示。 從圖4可以看出，在擁塞嚴重的情況下，CATSW3CM和CASR3CM的AS TCP流的吞吐量比CATC要穩定得多；且CATSW3CM的AS TCP流的實際吞吐量明顯比CASR3CM和CATC都要大。 3. 2 含有BE UDP流情況下保障AS TCP流目標速率能力 實驗的數據流由兩個AS TCP 聚流（分別由六個單流組成）、一個BE TCP 聚流（由九個單流組成）和一個BE UDP流組成，其發送速率也是3 Mbps。結果如表4所示。表4的數據表明，CATSW3CM、CASR3CM和CATC進行標記時，BE UDP流的出現對AS TCP流的影響都很大。CATSW3CM在保護TCP流方面明顯優于CASR3CM和CATC。CATSW3CM隨著優先權流目標速率的增加，不可控的UDP流的吞吐量下降要比CASR3CM和CATC快。對于同一組實驗，CATSW3CM的BE UDP流占有的帶寬都比CASR3CM和CATC小。因此，CATSW3CM在出現BE UDP流的情況下能很好地保護AS TCP流，使其實際吞吐量接近目標速率，使得AS TCP流享用到更多的帶寬。同時CATSW3CM和CASR3CM在兩個AS TCP聚流之間也能夠相對公平地按目標速率的比例享用瓶頸帶寬。數據目標速率為6 Mbps AS TCP流的吞吐量—時間關系如圖5所示。 表4 在出現BE UDP流的情況下性能比較 從圖5可以看出，即使出現BE UDP流情況下，與CATC相比， CATSW3CM和CASR3CM也使得AS TCP流吞吐量的穩定性大大增加；且CATSW3CM的AS TCP流的實際吞吐量明顯比CATC大，比CASR3CM的也稍微大一些。 3. 3 含AS UDP流情況下保障AS TCP流目標速率的能力 實驗的數據流由兩個AS TCP聚流（分別由六個單流組成）、一個BE TCP 聚流（由九個單流組成）及一個AS UDP流組成。AS UDP流的目標速率為3 Mbps，其發送速率也是3 Mbps，結果如表5所示。 表5 在出現ASUDP流的情況下性能比較 表5中數據表明，CATSW3CM、CASR3CM和CATC進行標記時，AS UDP流總是能夠達到或接近其目標速率，而AS TCP流只有當其總的目標速率較低時才能夠達到目標值（如表5中第1、2組數據），其中CASR3CM的實際速率比目標速率還要??；一旦兩個TCP聚流的總的目標速率較高時，它們的ASTCP流都不能達到甚至接近目標值。 即使兩個TCP聚流的總目標速率較高時，在CATSW3CM中兩個AS TCP聚集流的實際速率都比CATC和CASR3CM的要大。隨著AS TCP流的總的目標速率增大，其中的BE TCP流逐漸減少為零，在一定程度上保證了AS TCP流目標速率的服務。另外，CATSW3CM和CASR3CM在確保AS TCP流按比例享用瓶頸帶寬方面性能相當，并都優于CATC，且總的TCP流吞吐量也比CATC要好一些。數據目標速率為8 Mbps AS TCP流的吞吐量—時間關系如圖6所示。 從圖6可以看出，即使出現AS UDP流的情況，與CATC相比， CATSW3CM和CASR3CM也都使得AS TCP流的吞吐量的穩定性大大增加；且CATSW3CM的AS TCP流的實際吞吐量明顯比CATC要大，比CASR3CM的也稍微大一些。 4 結束語 本文在研究CATC、CASR3CM和ITSW3CM的基礎上提出了改進的擁塞感知的CATSW3CM。CATSW3CM利用邊界到邊界的擁塞感知反饋控制機制以及加大對非適應流的懲罰力度而保護TCP友好流的思想，使得CATSW3CM與CATC相比不僅提高了AS TCP流的平均吞吐量，而且增強了吞吐量的穩定性，并提高了AS TCP流之間按目標速率的比例占用帶寬的公平性。其與CASR3CM相比，提高了AS TCP流的平均吞吐量，并保持CATC的復雜度，具有良好的擴展性。 參考文獻： [1]HEINANEN J， BAKER F， WROCLAWSKI J. IETF RFC 2597， Assured forwarding PHB group[S].1999. [2]FENG Wu-chang， SHIN K G， KANDLUR D D. The BLUE active queue management algorithms[J]. IEEE/ACM Trans on Networking， 2002，10(4):513-528. [3]LIN Dong， MORRIS R. Dynamics of random early detection[C]//Proc ofACM SIGCOMM’97. New York: ACM Press， 1997:127-131. [4]PAN Rong， PRABHAKAR B， CHOKE P K. A stateless active queue management scheme for approximating fair bandwidth allocation[C]//Proc of IEEE INFOCOM 2000. 2000. [5]STOICA I， SHENKER S， ZHANG Hui. Core-stateless fair queue: achieving approximately fair bandwidth allocations in high speed networks[J]. IEEE/ACM Trans on Networking， 2003，11(1):33-46. [6]王建新，周雄偉，楊湘.一種懲罰非適應流的無狀態主動隊列管理算法[J]. 系統工程與電子技術，2006，26(12):1935-1939. [7]BLAKE S，BLACK D，CARLSON M， et al. IETF RFC 2475， An architecture for differentiated services[S]. IETF， 1938. [8]NICHOLS K， JACOBSON V，ZHANG L.IETF RFC 2638， A two-bit differentiated services architecture for the Internet[S]. 1999. [9]YEOM I， REDDY A L N.Modeling TCP behavior in a differentiated services network[J]. IEEE/ ACM Trans on Networking，2001，9 (1): 31-46. [10]SU Hong-jun， ATIQUZZAMAN M.ITSWTCM: a new aggregate maker to improve fairness in DiffServ[J]. Computer Communication， 2003，26(9):1018-1027. [11]ZHANG Ming， WANG R， PETERSON L， et al. Probabilistic packet scheduling:achieving proportional share bandwidth allocation for TCP flows[C]//Proc of IEEE INFOCOM2002. 2002. [12]FENG Wu-chang， KANDLUR D， SAHA D， et al. Adaptive packet marking for maintaining end-to-end throughput in a differentiated-services Internet[J]. IEEE/ACM Trans on Networking， 1999，7(5):685-697. [13]KUMAR K， ANANDA A L， JACOB L.Using edge-to-edge feedback control to make assured service more assured in DiffServ networks[C]//Proc ofIEEE LCN 2001.2001. [14]FANG W， SEDDIGH N， NANDY B. IETF RFC 2859， A time sli-ding window three colour marker (TSW3CM)[S].2000. [15]姜明，吳春明，朱淼良.區分服務中一種擁塞感知的單速三色標記算法[J].電子學報，2004，32(1):69-74. [16]劉正藍，朱淼良.基于邊界到邊界的帶寬估計的數據包標記器[J].通信學報，2003，24(8):12-21. [17]HAO Jun-rui， YU Shao-hua. An innovation three color marker in DiffServ networks[C]//Proc of IMSCCS2006. 2006. [18]LIN Kuan-cheng， HUANG Y H， TSAI C S， et al. Improving fairness in DiffServ networks using adaptive aggregate markers[J]. IEICE Trans on Information and Systems， 2007，90(6): 990-993. [19]劉正藍，朱淼良，董亞波.區分服務中一種TCP友好的公平數據包標記算法[J].電子與信息學報，2004，26(3):466-472. [20]VINT Project U. C. Berkeley/LBNL， NS2: network simulator[EB/OL].(2006).http://www.isi.edu/nsnam/ns. [21]CLARK D D， FANG Wen-jia. Explicit allocation of best-effort packet delivery service[J]. IEEE/ ACM Trans on Networking， 1998， 6(4):362-373.
