差異化服務流的自動擁塞避免的方法和設備的製作方法
2023-05-24 17:48:11 2
專利名稱：差異化服務流的自動擁塞避免的方法和設備的製作方法
技術領域：
本發明總體涉及數據處理領域，更具體來說，涉及一種實現通信網絡上差異化服務流的自動擁塞避免的方法和設備。
背景技術：
利用網際網路協議(IP)，網絡設備之間利用分組進行通信。每個分組可含有各種具有不同長度的消息。因為不是所有的分組都具有相同的優先級，故網際網路標準委員會已經提出了一種通過在網際網路分組的頭標中使用6位來區分分組的方法。這被稱為差異化服務或DiffServ。為了實行差異化服務，路由設備必須讀取這些頭標位並提供一種以不同於低優先級通信量的方式處理高優先級通信量的方法。
網際網路任務組已經定義了監視和控制入局通信量的標準。這是通過使用兩種控制方法完成的單速率雙顏色標記和雙速率雙顏色標記，RFC2698/RFC2697。無論哪一種方法，都對照同一個流上的分組的歷史檢查入局分組。如果某入局流超過某些定義的界限，該分組就被作黃色標記。如果分組超過一個上限，則該分組被作紅色標記。如果沒有超過界限，顏色是綠色。綠色、黃色或紅色可隨分組一起被發送到下一個中繼段(hop)，以幫助下一個中繼段決定傳送該分組還是丟棄該分組。
如果路由器中有足夠的帶寬，就沒有理由丟棄黃色或紅色分組。然而，如果路由器出現擁塞，則紅色和黃色分組應當是首先要被丟棄的分組。評論請求(RFC2698/RFC2697)規定，紅色的丟棄率應大於或等於黃色的丟棄率，黃色的丟棄率應大於或等於綠色的丟棄率。
差異化服務試圖把入局網際網路分組分類成流，並在路由器出現擁塞時，需要以不同的機率從每個流中丟棄紅色和黃色分組。如何計算丟棄機率並保持它們與系統同步是一個手工嘗試和錯誤過程。
多年來已經提出過各種方法來按照一些丟棄機率隨機地丟棄分組。一個現在還在使用的方法叫隨機早丟棄(RED)。通過設置必須在發生擁塞前設置的系統參數，可以產生一個丟棄機率。另一個改進了的通用方法叫做加權隨機早丟棄。加權隨機早丟棄方法試圖通過在不從多個源丟棄分組的情況下使有些線路或路徑的優先級更高而對RED做出一些改善。再者，在設置系統以處理丟棄機率時採用了手工方式。這兩種方法都採用了閾值監視，然後應用一個由系統管理員提供的丟棄率。然而， 哪一種方法都沒有考慮差異化服務信息。哪一種方法都不是動態的，就是說，這些方法不提供基於系統使用率的丟棄率。
國際商業機器公司(位於美國紐約Amonk)已經開發了一個更新的方法，叫做帶寬分配技術。帶寬分配技術(BAT)方法提供一種自動的系統來根據系統使用率處理分配晶片或系統的帶寬資源。BAT方法運用控制理論來產生一個對擁塞作出反應的自動系統。
在BAT方法中，給定流的傳輸率Ti可以由下列公式確定if fi＜＝mini then Ti(t+Dt)＝min(1，Ti(t)+0.125)else if(fi＞maxi)then Ti(t+Dt)＝0.857*Ti(t)elseif B＝1 Ti(t+Dt)＝min(1，Ti(t)+Ci*E(t))else Ti(t+Dt)＝max(0，Ti(t)-Di*fi(t))值fi代表向一個網絡路由器輸入的任何給定線路或信道i傳輸的字節量。Ti是任何給定輸入i的傳輸機率。Ti(t+Dt)代表在進行計算後開始的下一個周期的傳輸率。Ti(t)代表對應剛剛被傳輸的內容的先前的傳輸率。傳輸機率Ti的值在0於1之間。Mini代表傳輸機率Ti將不會被降低到的下限或者保障水平。將在取樣時間值上所傳輸的字節fi與mini值比較，以確定該流是否低於該下限或保障水平。
maxi代表信道能傳輸的字節的上限或最大數。將在取樣本時間值上所傳輸的字節fi與maxi值比較，以確定該流是否高於該上限或最大水平。如果某信道超過這個數，則降低該信道的傳輸率。
B代表一個表示過度帶寬的控制信號。如果路由設備沒有看到擁塞，則將值B設置為真或1。分組被允許流進和流出而無任何分組被丟棄。然而，當檢測到擁塞時，則將值B設置為0。
Ci代表一個遞增常數，當輸入流在最小和最大之間並且沒有擁塞時被使用。Ci被用來允許額外的分組進入系統。值E代表過度帶寬的一個歷史，取值範圍在0和1之間。如果路由器只在短時間擁塞，E將接近於1。然而，如果已經長時間發生擁塞，E將接近或等於0。
Di代表一個丟棄係數或遞減常數，被用來減少在擁塞期間進入系統的分組的數量。值Dt是一個把字節數帶入用於給定流的帶寬的百分率的複數。丟棄係數Di取值範圍寬，含有一個比例值和一個指數值。積Di*fi(t)要求大量的位，指數的複雜性要求浮點和指數功能。
這些公式有兩個功能，前兩行監視幀進入的速率並把分組或流劃分為低於最小值、高於最小值或介於兩者之間。這兩行起控制器的作用。
公式中的第三行」else」涉及擁塞避免。最後的else子句以行」ifB＝1」開始，被定義為過度帶寬，換言之，路由器沒有經受阻塞。如果B＝1，則傳輸機率是min(1，Ti(t)+Ci*E(t)。這意味著線性遞增常數Ci乘以時間E(t)上過度帶寬值的積被加到當前傳輸機率Ti(t)。
最後一行在B＝0時開始，傳輸速率是max(0，Ti(t)-Di*fi(t)，意思是傳輸率是當前速率減常數Di*fi，其中fi是所傳輸的字節量。
如圖3中所示，現有技術的BAT方法有以下特點。當擁塞發生時，流的傳輸機率Ti會降低。當擁塞結束時，傳輸速率升回到100％，此時不再遇到擁塞。儘管BAT方法提供了對其它結構的改進，BAT方法還沒有被用於實現差異化服務流的自動擁塞避免。
需要一種改進的機制來實現用於通信網絡中的差異化服務流的自動擁塞避免。
發明內容
本發明的主要目的是提供一種實現用於通信網絡中的差異化服務流的自動擁塞避免的方法和設備。本發明的其他重要目的是提供沒有副面影響並克服現有技術結構許多缺點的實現差異化服務流的自動擁塞避免的方法和設備。
簡而言之，提供一種實現用於通信網絡中的差異化服務流的自動擁塞避免的方法和設備。代表擁塞信息的帶寬控制信號被識別。響應所識別的帶寬控制信號，計算流的雙傳輸機率。雙傳輸機率包括第一顏色的第一傳輸機率和第二顏色的第一傳輸機率。識別分組的標記顏色。所標記的分組顏色和所計算的雙傳輸機率被選擇性地用於作出分組丟棄決定。
從以下對附圖中所示的本發明的最佳實施例的詳細說明中可以更好地理解本發明以及上述和其它優點。
圖1是表示用於實現本發明的用於差異化服務流的自動擁塞避免的設備的示意框圖；圖2是表示由圖1的用於實現本發明的用於寬帶分配技術的差異化服務流的自動擁塞避免的方法的機率策略制訂器所執行的示例性步驟的流程圖；圖3是表示現有技術的用於實現擁塞避免的帶寬分配技術的系統響應的示意圖；圖4、5和6是表示圖2的用於實現本發明的用於差異化服務流的自動擁塞避免的設備的系統響應的示意圖；圖7是表示本發明的電腦程式產品的框圖。
最佳實施例詳述以下參看圖1，圖中所示的用於實現本發明最佳實施例的用於差異化服務流的自動擁塞避免的裝置在總體上用標註符100表示。自動擁塞避免設備包括分類單元102、標記器104、帶寬計算單元106、丟棄決定單元108、機率策略制訂器110和擁塞信息112。每個被接收幀或分組被分類裝置102根據幀或分組的頭標中攜帶的位的子集分類為屬於某個流。標記器104對照相同流上的分組的歷史檢查入局分組。標記器104按照RFC2698/RFC2597中所述的方法標記分組的顏色。如果入局流超過某個定義的界限，該分組就被作黃色標記。如果分組超過一個上限，該分組就被作紅色標記。如果沒有超過界限，顏色是綠色。標記器104把綠、黃或紅一種分組顏色和流號作用於丟棄決定裝置108。帶寬計算裝置106隻逐個流地測量流顏色的輸入帶寬且只有一個值用於計算fi，供以後計算。
按照最佳實施例的特點，機率策略制訂器110向每個流兩次應用BAT公式，以啟動對差異化服務流的自動擁塞避免。對每個流，對應紅色應用一次BAT公式，然後對應黃色應用一次。將單獨的紅色和黃色常數Ci和Di設置成黃分組以比紅分組更慢的速率減少傳輸，並且黃分組傳輸速率比紅分組更快地增加。不使用最小值和最大值，因為，在確定分組的顏色時，標記器104已經確定該分組是綠、黃還是紅的，並且已經相應地標記了該分組。
按照最佳實施例的特點，機率策略制訂器110含有兩組常數Ci和Di，並為每個流計算黃和紅兩種不同顏色的Ti。擁塞信息112由BAT公式中的值B表示。分類裝置102確定流號和前一個顏色，以便作出丟棄決定。丟棄決定單元108在最佳實施例中得到加強。丟棄決定單元108從機率策略制訂器單元110接收兩個丟棄機率，一個是黃的丟棄機率，一個是紅的丟棄機率，並用這兩個丟棄機率來決定是否將幀或分組發送到系統的其餘部分上。
參看圖2，圖中顯示的用於實現本發明的用於寬帶分配技術的差異化服務流的自動擁塞避免的方法中由機率策略制訂器110所執行的示例性步驟。雙機率制定器110例如以流Ti開始，從i＝0至511循環，這是由帶寬計算單元106提供的，如框200中所示。雙機率制定器110檢查被擁塞信息112應用的過度帶寬的控制信號B是否等於1，如判斷框202所示。如果路由裝置100看不到擁塞，則值B被設定為真或1。然後如框204所示，雙機率制訂器110計算在B＝1時紅的和黃的傳輸機率Ti(red)和Ti(yellow)，計算公式如下Ti(red)＜＝Ti(red)+Ci(red)*ETi(yellow)＜＝Ti(yellow)+Ci(yellow)*ECi(red)和Ci(yellow)分別代表當沒有擁塞時所用的紅分組和黃分組的遞增常數。Ci(red)和Ci(yellow)允許額外的分組進入系統。Ci(yellow)是一個比Ci(red)大的值，這樣，在一段時間的擁塞後，黃分組返回100％容量的速度快於紅分組。值E代表過度帶寬的歷史，取值在0和1之間；當擁塞時間較短時，E接近於1，當擁塞長時間發生時，E接近或等於0。
另一方面，當檢測到擁塞時，值B是0。然後如框206中所示，機率制訂器110計算在B＝0時紅的和黃的傳輸機率Ti(red)和Ti(yellow)，計算公式如下Ti(red)＜＝Ti(red)+Di(red)*fiTi(yellow)＜＝Ti(yellow)+Di(yellow)*fiDi(red)和Di(yellow)分別代表在擁塞期間用來減少進入系統的分組的數量的紅分組和黃分組的丟棄係數或遞減常數。Di(red)是一個比Di(yellow)大的值，這樣，在擁塞期間後，紅黃比紅分組更快地被丟棄。值fi代表為該流傳輸的字節量。這就完成了機率策略制訂器110的為流Ti的雙傳輸機率計算，如框208中所示。
丟棄決定單元108取得流號和已經被標記器104標記過的分組顏色，並用機率策略制訂器110所提供的機率Ti(red)和Ti(yellow)決定是否應丟棄該分組。
參看圖4、5和6，圖中表示用於實現本發明的用於差異化服務流的自動擁塞避免的設備100的示例性系統響應圖。如圖4和5中所示，根據分組的顏色的不同，分組以不同的速率被丟棄。這是使用所述雙丟棄機率的結果。
圖4顯示一旦一段時間遇到擁塞時設備100所具有的系統響應。遇到擁塞時，紅分組比黃分組更快地被丟棄。當擁塞時期過後，黃分組將比紅分組更快地返回到100％。
圖5顯示如果擁塞持續時設備100所具有的系統響應。如圖所示，隨著持續的擁塞，所要發生的將是丟棄，隨後的一小段時間，被允許進入系統的幀稍微上升，直到再次發生擁塞。在某一點後黃色幀達到某種平衡，如圖5中所示。如果系統被過度預訂，紅色幀將被丟棄，直到黃色幀達到平衡。如果系統被嚴重過度預訂，黃色幀最終也達到0％。
圖6表示分組根據流的優先級以不同的速率被丟棄。每個流可有不同的機率。如圖所示，在擁塞區期間，高優先級的流比低優先級的流減少得慢一點。然後在擁塞區之後，高優先級的流比低優先級的流增加得快一點。
參看圖7，該圖表示本發明的製成品或電腦程式產品700。電腦程式產品700包括記錄介質702，諸如軟盤、以光學讀取的緊緻盤或CD-ROM為形式的大容量只讀存儲器、磁帶、諸如數字或模擬通信鏈路之類的傳輸類介質、或類似的電腦程式產品。記錄介質702在介質702上存儲有程序裝置704、706、708、710，用於實現帶圖1設備100的最佳實施例的用於差異化服務流的自動擁塞避免的方法。
由程序裝置704、706、708、710所定義的程序指令序列或一個或多個相關模塊的邏輯組合體指令設備100實現最佳實施例的用於差異化服務流的自動擁塞避免。
儘管是結合附圖所示的實施例的細節說明了本發明，但這些細節並非是要限制如後附的權利要求書所要求的本發明範圍。
權利要求
1.一種實現差異化服務流的自動擁塞避免的方法，包含以下步驟識別一個帶寬控制信號，所述帶寬控制信號代表擁塞信息；響應所述識別的帶寬控制信號，計算流的雙傳輸機率；所述雙傳輸機率包括第一顏色的第一傳輸機率和第二顏色的第一傳輸機率；識別分組的標記顏色；以及選擇性地用所述分組的所述標記的顏色和所述計算的雙傳輸機率來作出分組丟棄決定。
2.權利要求1所述的方法，包括以下步驟存儲在所述帶寬控制信號指示無擁塞時在雙傳輸機率計算步驟中使用的第一和第二遞增常數。
3.權利要求2所述的方法，其中，所述第一和第二遞增常數由對應紅分組和黃分組的Ci(red)和Ci(yellow)來代表。
4.權利要求3所述的方法，其中，所述雙傳輸機率計算步驟包括由下式表示的計算所述紅色的第一顏色的所述第一傳輸機率的步驟Ti(red)＜＝Ti(red)+Ci(red)*E，和由下式表示的計算所述黃色的第二顏色的所述第二傳輸機率的步驟Ti(yellow)＜＝Ti(yellow)+Ci(yellow)*E；其中值E代表過度帶寬的歷史，取值在0和1之間。
5.權利要求3所述的方法，其中，所述第一遞增常數Ci(red)的值小於所述第二遞增常數Ci(yellow)。
6.權利要求1所述的方法，包括以下步驟存儲在所述帶寬控制信號指示擁塞時雙傳輸機率在計算步驟中使用的第一和第二遞減常數。
7.權利要求6所述的方法，其中，所述第一和第二遞減常數由對應紅分組和黃分組的Di(red)和Di(yellow)來代表。
8.權利要求7所述的方法，其中，所述第一遞減常數Di(red)的值大於所述第二遞減常數Di(yellow)。
9.權利要求7所述的方法，其中，所述雙傳輸機率計算步驟包括由下式表示的計算所述紅色的第一顏色的所述第一傳輸機率的步驟Ti(red)＜＝Ti(red)-Di(red)*fi，和由下式表示的計算所述黃色的第二顏色的所述第二傳輸機率的步驟Ti(yellow)＜＝Ti(yellow)-Di(yellow)*fi；其中fi代表為該流傳輸的字節量。
10.一種實現差異化服務流的自動擁塞避免的設備，包括機率策略制訂器，用於接收帶寬控制信號並響應所述帶寬控制信號而計算流的雙傳輸機率；所述雙傳輸機率包括第一顏色的第一傳輸機率和第二顏色的第一傳輸機率；所述機率策略制訂器存儲在所述帶寬控制信號指示無擁塞時計算所述雙傳輸機率中所使用的第一和第二遞增常數；所述機率策略制訂器存儲在所述帶寬控制信號指示擁塞時計算所述雙傳輸機率中所使用的第一和第二遞減常數；以及接收分組顏色並連接到所述機率策略制訂器的丟棄決定邏輯，它接收包括所述第一顏色的所述第一傳輸機率和所述第二顏色的所述第二傳輸機率的所述雙傳輸機率並作出分組丟棄決定。
11.權利要求10所述的設備，其中，所述被存儲的第一和第二遞增常數由對應紅分組和黃分組的Ci(red)和Ci(yellow)來代表；並且，所述第一遞增常數Ci(red)的值小於所述第二遞增常數Ci(yellow)。
12.權利要求11所述的設備，其中，存儲在所述帶寬控制信號指示無擁塞時計算所述雙傳輸機率中所使用的第一和第二遞增常數的所述機率策略制訂器包括由下式計算所述紅色第一顏色的所述第一傳輸機率Ti(red)＜＝Ti(red)+Ci(red)*E，和由下式計算所述黃色第二顏色的所述第二傳輸機率Ti(yellow)＜＝Ti(yellow)+Ci(yellow)*E；其中值E代表過度帶寬的歷史，取值在0和1之間。
13.權利要求10所述的設備，其中，所述第一和第二遞減常數由對應紅分組和黃分組的Di(red)和Di(yellow)來代表，並且，所述第一遞減常數Di(red)的值大於所述第二遞減常數Di(yellow)。
14.權利要求13所述的設備，其中，存儲在所述帶寬控制信號指示擁塞時計算所述雙傳輸機率中所使用的第一和第二遞減常數的所述機率策略制訂器包括由下式計算所述紅色第一顏色的所述第一傳輸機率Ti(red)＜＝Ti(red)-Di(red)*fi，和由下式計算所述黃色第二顏色的所述第二傳輸機率Ti(yellow)＜＝Ti(yellow)-Di(yellow)*fi；其中fi代表為該流傳輸的字節量。
15.一種實現差異化服務流的自動擁塞避免的電腦程式產品，所述電腦程式產品包括存儲在計算機可讀介質上的計算機可執行指令，其中，所述指令被自動擁塞避免設備執行時使自動擁塞避免設備執行以下步驟識別一個帶寬控制信號，所述帶寬控制信號代表擁塞信息；響應所述識別的帶寬控制信號，計算流的雙傳輸機率；所述雙傳輸機率包括第一顏色的第一傳輸機率和第二顏色的第一傳輸機率；識別分組的標記顏色；以及選擇性地用所述分組的所述標記的顏色和所述計算的雙傳輸機率來作出分組丟棄決定。
16.權利要求15所述的電腦程式產品，其中，所述指令被自動擁塞避免設備執行時使自動擁塞避免設備執行以下步驟存儲在所述帶寬控制信號指示無擁塞時在雙傳輸機率計算步驟中使用的第一和第二遞增常數。
17.權利要求16所述的電腦程式產品，其中，所述被存儲的第一和第二遞增常數由對應紅分組和黃分組的Ci(red)和Ci(yellow)來代表；並且，所述第一遞增常數Ci(red)的值小於所述第二遞增常數Ci(yellow)。
18.權利要求15所述的電腦程式產品，其中，所述指令被自動擁塞避免裝置執行時使自動擁塞避免設備執行以下步驟存儲在所述帶寬控制信號指示擁塞時在雙傳輸機率計算步驟中使用的第一和第二遞減常數。
19.權利要求18所述的電腦程式產品，其中，所述第一和第二遞減常數由對應紅分組和黃分組的Di(red)和Di(yellow)來代表，並且所述第一遞減常數Di(red)的值大於所述第二遞減常數Di(yellow)。
全文摘要
提供一種實現用於通信網絡中的差異化服務流的自動擁塞避免的方法和設備。識別一個代表擁塞信息的帶寬控制信號。響應所述識別的帶寬控制信號，為每個流計算雙傳輸機率。雙傳輸機率包括第一顏色的第一傳輸機率和第二顏色的第一傳輸機率。識別分組的標記顏色。選擇性地用分組的標記顏色和所計算的雙傳輸機率來作出分組丟棄決定。
文檔編號H04L12/56GK1505348SQ20031011792
公開日2004年6月16日 申請日期2003年11月26日 優先權日2002年11月27日
發明者M·D·貝洛斯, M D 貝洛斯 申請人:國際商業機器公司