在包交換裝置中用於避免擁堵的方法和系統的製作方法

2023-05-22 15:09:36 2

專利名稱：在包交換裝置中用於避免擁堵的方法和系統的製作方法
技術領域：
本發明涉及在包交換裝置中避免擁堵的方法和系統，尤其是使用數據包丟棄技術來避免擁堵的方法和系統。
背景技術：
通過一個包交換裝置(比如，一個路由器)來支持的所有鏈路的集成鏈路帶寬通常比裝置的總交換能力高。這就引起位於包交換裝置入口(交換前)和出口(交換後)級的緩衝器中出現擁堵。擁堵甚至會在無阻塞交換結構(switch fabrics)上出現。通常可以使用緩衝來控制擁堵。然而，緩衝會造成數據包傳輸的延遲，因此，為了避免過度延遲，就需要開發更複雜的技術來解決擁堵。
一種用於控制擁堵的方案是尾部丟棄法，藉此，允許將數據包填充到出口緩衝器中，如果數據包來自交換結構而同時緩衝器容量已滿，就將數據包丟棄。然而，這種方法會造成多路數據流丟失數據包。高層協議會通過終止數據流並重新傳輸丟失信息的方法來對這種類型的數據包丟失做出反應。雖然擁堵本身被終止了，而最終的結果就是包交換裝置那種非常令人討厭的減速—加速—減速等等的工作方式。
在另一種傳統的擁堵控制算法中，出口級對每一個數據包採取一個行動，這種行動可以是使數據包排隊等待，也可以是將數據包丟棄。這種類型算法的一個例子是隨機初期丟棄(RED)算法。RED(隨機初期丟棄)算法的具體例子包括RED(隨機初期丟棄)算法(該算法在1998年4月的Internet Request For Comments(RFC)2309中進行了描述，特此引用)，以及BLUE算法(該算法在BLUEA New Class ofActive Queue Management Algorithms的第1-26頁進行了描述，Wu-chang Feng等著，特此引用)。數據包應該丟棄還是排隊等待的決定通過監控特定鏈路上出口緩衝器已充滿的程度，並相應地給數據包產生一個丟棄概率來進行確定。如果給數據包產生的隨機數字低於丟棄概率，數據包就被丟棄；否則將數據包放入出口緩衝器中。在這種方法中，出口緩衝器的擁堵可以通過出口緩衝器採取的行動來進行控制。
但是，由於延遲不丟棄的數據包增加的不穩定信號和等待時間以及發送要丟棄的數據包都需要大量地提供交換結構。因此，通過裝置出口丟棄數據包或者使數據包排隊等候的每一個行動(比如，一旦交換資源已經被用來交換數據包)，這些最終丟棄的數據包將消耗掉包交換裝置整個入口和交換級的資源。明顯地，以測量擁堵水平為基礎來做出決定，被使用裝置的存儲器和/或交換資源利用程度不可避免地效率低下。
因此，在工業上有必要開發一種能夠限制擁堵，同時又能夠在像路由器這樣的包交換裝置中有更大的資源利用效率的機制。
發明簡述本發明提供了一種用於在包交換裝置的入口級調節數據包流量的方法。特別地，將為裝置出口級的多個隊列中的每一個獲得帶寬利用率信息。根據帶寬利用率信息，為每個隊列計算「丟棄概率」。這個信息周期性地或者在其它控制的時間段傳輸到入口級，比如當丟棄概率出現極大變化時。然後入口級就能夠根據數據包要到達的隊列以及那個隊列的丟棄概率，繼續進行數據包到交換結構的可控傳輸或者停止進行傳輸。在這樣的方式中，甚至在擁堵有機會發生以前就被避免了。這就提高了帶寬的利用率，因為在入口級丟棄的數據包不會佔據裝置中的其它資源。
因此，本發明可以概括為利用一種調節通過一個裝置的數據包流的方法，該裝置設有包括多個輸入埠和多個輸出埠的交換結構；一個控制實體，該控制實體連接到輸入埠用於調節到入口的數據包流；以及多個出口隊列，該出口隊列連接到輸出埠用於臨時存儲從出口收到的數據包。該方法包括獲得有關出口隊列收到的數據包的帶寬利用率信息；從帶寬利用率信息中確定各出口隊列的丟棄概率；向控制實體提供各出口隊列的丟棄概率，供控制實體用來有選擇性的將數據包傳輸到交換結構的輸入埠。
在一個特定的實施例中，獲得有關出口隊列收到數據包的帶寬利用率信息包括為每一個輸出埠確定從該輸出埠收到連續數據包之間的平均空閒時間；為每一個輸出埠確定連接到該輸出埠的每個出口隊列單位時間收到業務流字節數的平均值，以及為每個輸出埠確定單位時間從該輸出埠收到非業務流字節數的平均值。
在一個特定實施例中，通過為某一出口隊列確定分配業務流帶寬，以及將該出口隊列收到的業務流字節數平均值與該出口隊列分配的業務流帶寬進行比較，就可以確定一個出口隊列的丟棄概率。如果該出口隊列收到的業務流字節數平均值比該出口隊列分配到的業務流帶寬更大(更小)，則該出口隊列的丟棄概率被設定為該出口隊列以前丟棄概率值的時間平均值與一個正(負)增加值之和。
在一個特定的實施例中，可以為每個出口隊列和數據包優先級的組合的丟棄概率進行計算。
在一個特定的實施例中，本發明的方法可以實現為計算機可讀儲存介質上的指令序列。
根據第二個主要的方面，本方法可以概括為丟棄概率計算模塊，該模塊包括一個分配處理實體，用於為每個出口隊列和一個與分配處理實體相連的概率處理實體確定一個分配的業務流帶寬，概率處理實體適合於從分配處理實體為每個出口隊列接收分配的業務流帶寬，還適合於從外部裝置中為每個出口隊列接收已收到業務流字節的平均值。
概率處理實體可以將每個出口隊列收到業務流字節的平均數與該出口隊列分配的業務流寬帶進行比較，並根據該出口隊列收到的業務流字節平均值比該出口隊列分配業務流帶寬是大還是小，將某一出口隊列的丟棄概率設定為該出口隊列以前丟棄概率值的時間平均值與或正或負的增加值之和。
根據第三個主要的方面，本方法可以概括為設有交換結構的一種裝置，該交換結構設有多個輸入埠和多個輸出埠，該交換結構適合於在該裝置的輸入埠和輸出埠之間交換數據包。該裝置還包括多個出口隊列，出口隊列與交換結構輸出埠中相應的一個相連，每個出口隊列都適合於(i)臨時存儲從相應交換結構出口收到的數據包，(ii)在出口隊列收到數據包的基礎上確定帶寬使用信息。
所述裝置還包括一個與出口隊列相連的丟棄概率計算模塊，該丟棄概率計算模塊適合於以帶寬使用率信息為基礎確定每個出口隊列的丟棄概率。所述裝置還包括一個與交換結構輸入埠和丟棄概率計算模塊相連的數據包接收部件，數據包接受部件適合於(i)接收傳輸到交換結構輸出埠的數據包；(ii)確認與每個收到的數據包相關的出口隊列；(iii)根據與每個收到數據包相關的出口隊列的丟棄概率，將收到數據包傳輸或者不傳輸到交換結構的一個輸入埠。
根據另一主要方面，本發明可以概括為一種調節通過一個裝置的數據包流量的方法，該裝置設有一個入口實體；一個出口實體；一個處理結構，該處理結構設在入口實體和出口實體之間；以及一個控制實體，該控制裝置用於在將數據包傳輸到入口實體之前對數據包進行處理。該方法包括獲得與出口實體的收到數據包相關的擁堵信息，並將擁堵信息提供給控制實體，供控制實體用來在數據包傳輸到入口實體之前對數據包進行處理。
通過對本發明優選實施例的說明和附圖的審查，本領域一般技術人員對本發明的這些和其它方面以及特點將更加清楚明了。
附圖簡述其中

圖1是設有本發明實施例的隨機數據包丟棄功能的一個包交換裝置的框圖；圖2是圖1裝置中丟棄概率計算模塊實施例的框圖。
優選實施例詳述參考圖1，圖中顯示了本發明實施例的包交換裝置，該裝置以入口級獲得的擁堵信息為基礎，通過在入口級傳輸或者不傳輸數據包來避免信息擁堵的發生。
在一個實施例中，包交換裝置100是一種多級路由器，而且出口級可以是多級路由器的中間級或者最後級。能在包交換網絡中與鄰近的裝置(比如，路由器或者節點)相連的裝置100包括一個交換結構102，交換結構102設有多個輸入埠104和多個輸出埠106。交換結構102的輸入埠104與一組輸入線路卡108相連，交換結構102的輸出埠106與一組輸出線路卡110相連。在線路卡為雙向線路的實施例中，輸入線路卡108和輸出線路卡110可以沒有差別。同樣，在多級路由器中，輸出線路卡110將作為路由選擇的下一級。
輸入線路卡108適合於從外部實體中接收數據包流，並將它們提供給交換結構102的輸入埠104。每個輸入線路卡108可以通過一個總線結構105與交換結構102的一個、兩個或者多個輸入埠104相連。輸出線路卡110適合於從交換結構102的輸出接口106接收數據包流並將它們轉發到網絡下遊臨近的路由器或者節點上。每個輸出線路卡110都設有一個、兩個或者多個物理接口，與交換器102的輸出埠106中的每一個相對應。每個輸出線路卡110上的接口通過輸出線路卡110能共同使用的總線結構107與交換結構102上相應的輸出埠106相連。在圖示實施例中，有四個標記為I0、I1、I2、I3的接口，兩個接口位於兩個輸出線路卡110中的每一個上面。然而，顯而易見還能夠採用其他布置方式，本發明不受任何接口、輸出線路卡110數量或者接口在輸出線路卡110上的布置方式的限制。
典型地，數據包由首部和有效負載構成，而且還與優先級關聯(或者優先權或服務級別)。首部通常確定數據包的優先級(如果可用)以及數據包發送的目的地節點。收到一個特定數據包的輸入線路卡108將它的目的地節點轉換成交換結構102的目的地輸出埠，比如106x，並且將這個目的地輸出埠106x的標識插入到數據包的首部。利用在數據包的首部所指定的目的地輸出埠106x的標識，數據包就通過適當的總線105被提供給交換結構102的一個輸入埠104。交換結構102負責確保數據包確實出現在要求的目的地輸出埠106x。具有一個(通過輸出線路卡的總線107)連接到目的地輸出埠106x的接口的輸出線路卡110從數據包的首部將目的地輸出埠106x的標識去掉，以數據包最初的形式將其轉發到網絡上臨近的路由器或者節點上。在這種方式中，數據包被移動到更靠近它的目的地節點。在多級路由器的情況下，輸出線路卡就代表了路由選擇的下一級。
在一個實施例中，同那種其輸出線路卡110能夠傳輸到裝置100外面的交換結構相比，交換結構102能夠以更高的速率向每個輸出線路卡110提供信息。這是為了允許輸出線路卡110來緩衝超出的帶寬，並就如何路由緩衝數據包做出明智的決定。在另外的實施例中，嚴格的講，如果裝置100中數據包發送的速率與能夠通過一個與輸出線路卡110相連的外部裝置進行控制的速率匹配或者比這個速率小，出口實體就沒有必要是隊列。
不管在裝置100出口是否需要緩衝能力，在出口線路卡110上的接口都包含一個出口實體。在一個實施例中，每個輸出線路卡110上的每個接口都與一個、兩個或者多個構成出口實體部件的出口隊列112相連。出口隊列被用來臨時存儲通過適當總線107從交換結構102的相應輸出埠106發送來的數據包流中的數據包。出口隊列112可以說是作為與它們相連的物理接口充當虛擬接口或者虛擬埠。應當提及的是在多級路由器中，相對於路由選擇的後面級，出口隊列112實際上是入口隊列。
在圖示實施例中，每個接口上有兩個出口隊列112，分別標記為Q0，Q1。因此，接口I0與它自己的出口隊列Q0，Q1，而接口I1與它自己的出口隊列Q0，Q1等等相連。但是，可以理解的是還可以有其它布置方式，而且本發明並不局限於每個接口上出口隊列112的任何特定數量。此外，在數據包有不同優先級的情況下(比如，P0和P1)，出口隊列112可以在優先級的基礎上劃分為相應的一組子隊列113。應當認識到的是子隊列113並不要求全體都是一樣的深度，對於每個出口隊列112也不需要具有相同的子隊列113數目。
根據本發明的一個實施例，還為每個接口設有一個出口業務流管理器(ETM)114。每個出口業務流管理器114包括適當的電路、軟體和/或者控制邏輯用於從每個收到的首部去掉目的地輸出標識以及用於確定將收到的數據包放到哪個接口、哪個出口隊列112和子隊列113。顯然可以理解的是在本發明的其它實施例中，每個輸出線路卡110設有一個輸出業務流管理器，這樣，每個出口業務流管理器114將直接連接到與總線107相對應的一個通路中。
向哪個接口發送一個收到的數據包，要在收到數據包首部中指定的信息(比如目的地節點)的基礎上做出決定。向哪個出口隊列112插入收到的數據包，要在收到數據包首部中指定的信息(比如虛擬埠標識符)的基礎上做出決定。向哪個子隊列113插入收到的數據包，要在收到數據包首部中指定的信息(比如優先級)的基礎上做出決定。
為了說明的目的，假定每個接口實際設有一個出口業務流管理器114，每個這樣的出口業務流管理器114都額外設有電路、軟體和/或控制邏輯，用於監控從交換結構102的相應輸出埠106收到的數據包目的地和數量。在這個信息的基礎上，出口業務流管理器114產生表明擁堵的信息。
擁堵信息可能包括帶寬利用率信息，比如接口Ii上收到數據包之間的平均空閒時間(記做AIT(Ii)-平均空閒時間)；接口Ii收到非業務流字節平均值(記做ARNB(Ii)-收到非業務流字節平均值)；與接口Ii關聯的每個出口隊列Qε{1120，1121}的每個優先級Pε{1130，1311}收到業務流字節平均值(記做ARTB(Ii，Q，P)-平均收到業務流字節)。
可選地，擁堵信息還可以包括對每個出口隊列112深度的測量值或者每個隊列可變性的測量值。為了說明的目的，假定擁堵信息是帶寬利用率信息，該信息由位於一個給定出口線路卡110上的每個出口業務流管理器114產生，這樣的信息被提供給公共丟棄概率計算模塊(DPEM)120，該公共丟棄概率計算模塊有輸出線路卡110共用。(另外一個方法是，為輸出線路卡110上的每個出口業務流管理器114設有一個單獨的DPEM 120)。
位於給定輸出線路卡110上的DPEM 120包括電路、軟體和/或控制邏輯，用於為每個與位於給定出口線路卡110上的每個接口關聯的出口隊列112和子隊列113計算丟棄概率。因此，根據設有DPEM 120的出口線路卡上的接口數量，每個DPEM 120將為一個、兩個或者多個接口計算丟棄概率。為了便於標記，接口Ii，隊列112q和子隊列113P的丟棄概率將被記做DP(Ii，112q，113p)。
每個DPEM 120通過一個控制鏈路122與每個輸入線路卡108中的一個或者多個數據包接收單元(PAUs)118相連。從一個給定DPEM120連接到輸入線路卡108的控制鏈路攜帶有每個隊列和優先級的組合的丟棄概率，所述每個組合是對於與包含DPEM 120的輸出線路卡110關聯的每個接口可能的組合。由於這個工作由位於每個輸出線路卡110中的每個DPEM 120完成，所以位於每個輸入線路卡108中的每個PAU 118就可以為每個可能的接口、隊列和子隊列組合獲取丟棄概率。由特定DPEM 120傳輸的丟棄概率就可以以廣播信息的形式進行發送。交換結構102實際上被用做一個通道，用來將丟棄概率DP(I，Q，P)從DPEM 120運送到PAUs 118的。
現在考慮位於一個特定輸入線路卡108上的PAU 118，這個裝置被用來在數據包傳輸到交換結構102的相應輸入埠104之前處理數據包流。PAU 118的功能之一就是以每個數據包的接口和輸入隊列(如果適用，還有優先級)為基礎，以及與接口、輸出隊列(如果適用，還有優先級)的組合相聯繫的丟棄概率為基礎，通過使用數據包的隨機丟棄功能來避免信息擁堵。雖然用來說明的實施例中交換結構102的每個輸入埠104顯示了一個PAU 118，但是在某些實施例中，給每個輸入線路卡108都設一個PAU 118，或者設置唯一的一個布置在輸入線路卡108中的PAU 118，這樣是非常有利的。
用來處理一個特定數據包流的PAU 118設有合適的電路、軟體和/或控制邏輯，用於確定每個收到數據包目的地輸出埠。這個目的地輸出埠與輸出線路卡110之一上的一個接口(比如，Ii)相對應。此外，PAU 118還包括合適的電路、軟體和/或控制邏輯，用於確定輸出業務流管理器114要將收到的數據包插進去的輸出隊列112(比如，112q)，所述輸出業務流管理器114關聯於與目的地輸出埠相對應的接口。此外，如果一個收到的數據包具有幾個優先級中的一個，那麼，PAU 118還包括合適的電路、軟體和/或控制邏輯，用於確定數據包的優先級以及要確定數據包要插入到的子隊列(比如，113p)。基於這種信息並且基於丟棄概率DP(Ii，112q，113p)，PAU 118做出是要丟棄收到的數據包還是繼續向交換結構102傳輸的決定。
為了做出是否丟棄收到的具有接口Ii、輸出隊列112q和子隊列113p特徵的數據包的決定，PAU 118包括合適的電路、軟體和/或控制邏輯，用於為收到的數據包產生一個隨機如數字R並將R與丟棄概率DP(Ii，112q，113p)進行比較。比如說，如果R低於DP(Ii，112q，113p)，那麼數據包就被丟棄，否則數據包就被發送到交換結構102的相應輸入埠104。另外一種方法是，如果隨機數字R比丟棄概率DP(Ii，112q，113p)高，就將數據包丟棄。術語「隨機數字」在這種意義上就是指包括一個由偽隨機或者擬隨機技術產生的數字。
在它決定確實要將收到數據包轉發到交換結構102的情況下，PAU118包括合適的電路、軟體和/或控制邏輯，用於將目的地輸出埠的標識插入到數據包首部，並將數據包轉發到交換結構102的相應輸入埠104，這時數據包的首部規定了目的地輸出埠的標識。但是，在它決定要丟棄收到數據包的情況下，數據包不會傳輸到交換結構102，而將完全地被丟棄，或者發送到一個用於存放丟棄數據包的單獨的存儲庫。非常具有優勢的是，不傳輸的數據包不會消耗交換結構102中的資源或者PAU 118擁堵管理裝備中的資源，提高了資源的利用率。
現在來描述通過與接口I0關聯的輸出業務流管理器114來產生帶寬利用值(比如，AIT(I0)，ARBN(I0)和ARBT(I0，Q，P))。第一，關於AIT(I0)值，它指示接口I0的總帶寬利用率。如果使用了長度固定的數據包，那麼總帶寬利用率就可以通過計算每秒鐘到達出口業務流管理器114的數據包數量來直接進行測量。在這種情況下，就不需要計算平均空閒時間。但是，如果使用了可變長度數據包，優選地，總寬帶利用率通過計算連續收到數據包時非傳輸時間間隔的平均值來進行間接測量。這個時間是指數據包與數據包之間的平均空閒時間。
如果一個字中的專用比特被用來顯示那個字是否在它所在的數據包中距離最後一個字有一定數目的字，那麼就便於實現測量數據包之間的平均空閒時間的方法。這樣一種用於用信號指示數據包即將結束的技術在授予給Norman等人、申請號為09/870,776的美國專利申請中進行了描述，該專利申請日期為2001年5月31日，轉讓給本發明的受讓人，特此引用。
與接口I0關聯的出口業務流管理器114也為Qε{1120，1121}，Pε{1130，1131}產生ARTB(I0，Q，P)值，該值是為接口I0表示發送到每個出口隊列和子隊列組合的業務流字節數平均值。一個業務流字節從屬於一個必須滿足特定的面向用戶的質量服務標準的數據包。換言之，業務流字節屬於必須避免信息擁堵的數據包。為了計算每個ARTB(I0，Q，P)值，出口業務流管理器114包括合適的電路、軟體和/或控制邏輯，用於分析每個到來數據包的首部，並且從首部的信息中確定讓數據包前往哪個出口隊列112，以及數據包優先級。
另外，與接口I0關聯的出口業務流管理器114也產生ARNB(I0)值，該值表示了在接口I0收到的非業務流字節數的平均值。一個非業務流字節屬於沒有附帶面向用戶服務質量標準的數據包中的字節。為了計算ARNB(I0)值，出口業務流管理器114包括合適的電路、軟體和/或控制邏輯，用於分析每個到來數據包的首部，並且從首部的信息中確定數據包是業務流數據包還是非業務流數據包。顯而易見的是，對於每個數據包，只在計算ARNB(I0)值和ARTB(I0，Q，P)值的過程中對數據包部首進行一次分析。
參考圖2，現在詳細描述適合為每個有效的I，Q，P組合計算丟棄概率DP(Ii，112q，113p)的丟棄概率計算模塊(DPEM)120的例子。特別地，圖示的與一個出口線路卡110關聯的DPEM 120包括一個總計(aggregation)處理實體208，一個利用率處理實體210，一個分配處理實體220，一個概率處理實體230，以及一個外推處理實體240。
總計處理實體208從與接口I0關聯的出口業務流管理器114接收ARNB(I0)和AIT(I0)值，從與接口I1關聯的出口業務流管理器114接收ARNB(I1)和AIT(I1)值。總計處理實體208根據其輸入確定收到的非業務流字節(標記為ARNB)的總計平均值，以及帶寬梯度(標記為BWGR)。ARNB和BWGR值被提供給利用率處理實體210。ARNB值的計算可以通過加上由於i＝0和i＝1而增加的ARNB(Ii)值來得到。BWGR值的計算可以通過以下方式完成。
為了得到一個總平均空閒時間，對每個接口測量的平均空閒時間AIT(I0)，AIT(I1)求平均值。然後將總平均空閒時間與一組預設閾值進行比較。在一個實施例中，每個接口的總平均空閒時間首先與臨界最小平均閾值時間(記作T1)進行比較。如果它小於T1，那麼這種情況就表明交換結構102中帶寬的超臨界利用。因此，設定帶寬梯度值(BWGR)來表明在入口側迫切需要縮小帶寬。
然而，如果總平均空閒時間不小於T1，那麼就讓它與預設最小平均閾值(標記為T2)進行比較。如果總平均空閒時間比T2小，那麼這種情況表明了非臨界性擁堵，非臨界性擁堵消耗了交換結構102的緩衝空間。因此，設定帶寬梯度值(BWGR)表明在入口側需要適當的縮小帶寬。
如果總平均空閒時間不比T2小，那麼就將它與預設最大平均閾值(標記為T3)進行比較。如果總平均空閒時間比T3大，那麼這種情況就表明交換結構102中帶寬利用率不足。因此，設定帶寬(BWGR)來表明在入口側需要增加帶寬。
最後，如果總平均空閒時間介於T2和T3之間，那麼這種情況表明交換結構102中的帶寬的使用不需要進行補償。因此，設定帶寬梯度值(BWGR)表明在入口側既不需要增加帶寬，也不需要減少帶寬。
應當指出的是，閾值T1、T2和T3可以在各種參數如帶寬利用率，還有隊列深度和帶寬的可變性(猝發性)的基礎上進行動態調節。
利用率處理實體220從總計處理實體208中收到BWGR值(比如，帶寬梯度)和ARNB值(比如，平均收到非業務流字節)。以其輸入為基礎，利用率處理實體210為業務流數據包確定一個總利用帶寬，然後把總利用帶寬以BWAVAIL值(可利用帶寬)的形式提供給分配處理實體220。BWAV值的計算按照以下步驟進行利用率處理實體對所有數據包(業務流數據包和非業務流數據包)可以利用的總帶寬保留內部記錄，記做AGG_AVAIL。如果BWGR值表明在入口側的帶寬需要增加，於是AGG_AVAIL通過預設步長值來增加入口側帶寬，直到最大可利用總帶寬；如果BGWR值表明入口側的帶寬需要縮小，那麼AGG_AVAIL就通過預設步長值縮小入口側帶寬，降到一個最小可利用總帶寬；如果BGWR值表明出口側的帶寬既不需要增加也不需要縮小，那麼AGG_AVAIL保持不變；如果BWGR值表明在入口側迫切需要縮小帶寬，那麼AGG_AVAIL設定到一個預設(低)值。
其次，從AGG_AVAILA的結果中減去ARNB值就得到BWAVAIL值，BWAVAIL值是只有業務流數據包可以利用的總帶寬。在本發明的一個實施例中，增加和減少操作中的步長值都可以設為最小可利用總帶寬的百分率。因為縮小帶寬比增加帶寬更重要，所以增加操作的步長值要低於縮小操作中的步長值。
分配處理實體220除了從利用率處理實體210中以BWAVAIL值的形式收到業務流數據包可利用總帶寬以外，還收到平均字節數的顯示值，如果丟棄概率為零，就應當為輸出線路卡上的每個輸出隊列112接收平均字節數顯示值。這個信息從外推處理實體240中以多個ARTBDP0(I，Q)值(比如，如果丟棄概率為0的平均收到業務流字節)的形式進行接收，其中Iε{I0，I1}和Qε{1120，1121}。隨後，在外推處理實體240內容中將對每個ARTBDP0(I，Q)值的計算進行詳細描述。
以其輸入為基礎，分配處理實體220為每個有效的I，Q組合的業務流字節分配帶寬。這個計算結果以給I和Q的組合分配帶寬值的形式(記作BWALLOC(I，Q)—分配的帶寬)提供給概率處理實體230。
BWALLOC(I，Q)值的計算按照以下方式進行分配處理實體220首先確定為每個I和Q的組合分配的帶寬是否滿足要求。這可以通過將以前的BWALLOC(I，Q)值與相應的ARTBDP0(I，Q)值進行比較來完成。因此，將分配的帶寬與I和Q組合能夠收到的最大可能帶寬進行比較。
如果BWALLOC(I，Q)值超過ARTBDP0(I，Q)值，那麼就要縮小BWALLOC(I，Q)值，比如，縮小一個固定的量，或者以一個依賴於BWALLOC(I，Q)值與ARTBDP0(I，Q)值之差的因子來縮小BWALLOC(I，Q)值。另一方面，如果BWALLOC(I，Q)值小於ARTBDP0(I，Q)值，那麼BWALLOC(I，Q)的值就要增加，比如，增加一個固定的量，或者以一個依賴於BWALLOC(I，Q)值與ARTBDP0(I，Q)值之差的因子來增加BWALLOC(I，Q)值。BWALLOC(I，Q)值的增加或者縮小值被提供給概率處理實體230。
應當指出的是，另外一個實施例中，「不改變」的結果將應用到特定的BWALLOC(I，Q)值中，該實施例同樣在本發明的範圍內。還應當指出的是，當從概率處理實體210上收到數據時，為了確保在同一線路卡上，檢查BWALLOC(I，Q)在整個I和Q範圍內的總和不會超過該線路卡的BWAVAIL值是非常有利的。
概率處理實體230，除了從分配處理實體220接收(Iε{I0，I1}和Qε{1120，1121})的BWALLOC(I，Q)值，還從外推處理實體240接收(Iε{I0，I1}和Qε{1120，1121}以及Pε{1130，1131})的ARTBDP0(I，Q，P)值，從與接口I0關聯的出口業務流控制器114接收(Qε{1120，1121}以及Pε{1130，1131}的)ARTB(I0，Q，P)值，從與接口I1關聯的出口業務流管理器114接收(Qε{1120，1121}以及Pε{1130，1131}的)ARTB(I1，Q，P)值。
以其輸入為基礎，概率處理實體230為每個有效的I，Q，P組合產生丟棄概率DP(I，Q)P)，在這種情況下為Iε{I0，I1}和Qε{1120，1121}以及Pε{1130，1131}產生。為給定I值(比如i)和Q值(比如q)對所有的P值計算丟棄概率DP(I，Q，P)可以按照以下方式進行首先，對所有的P值計算ARTB(I，q，p)的總和。這就得到一個數量，該數量表示了與接口Ii關聯的出口隊列112q收到業務流字節的總平均數量，可以記做TARTB(i，q)。為了確定是否分配了比需要的更大的帶寬，將這個數量與BWALLOC(i，q)進行比較。因為當分配的帶寬與實際使用的帶寬相匹配的時候，就會產生最優的資源利用效率，兩個參數的差提供了一個誤差的信號，要使這個差別變為零。在這個階段，可以採取一種簡單的方法和一種更加複雜的方法。下面先描述簡單的方法，然後描述更加複雜的方法。
在分配帶寬比總平均使用帶寬大的情況下，在簡單方法中，丟棄概率DP(i，q，P)將對一個或者多個P降低(取決於使用了intserv還是diffserv模型)，使得在入口處丟棄的數據包更少，最終造成了TARTB(i，q)的增加。相反地，如果平均總帶寬小於實際使用帶寬，丟棄概率DP(i，q，P)將對一個或者多個P增加(取決於使用了intserv還是diffserv模型)，使得大量數據包在入口處被丟棄，最終造成了TARTB(i，q)的減少。用於增加丟棄概率DP(i，q，P)的幅度將不同於縮小的幅度。
重複以上過程，直到分配的帶寬處於總平均使用帶寬的一定範圍內。有利的是，這種方法避免了一定程度的信息擁堵。但是，收斂將花費相對較長的時間。這是因為在改變丟棄概率和業務流字節數的平均值發生相應改變之間的大量時間都浪費了。此外，如果丟棄概率在業務流字節數的平均值被檢測到之前就改變了，那麼就可能「超過」最終丟棄概率，而最終丟棄概率將允許分配的帶寬位於總平均使用帶寬的一定範圍之內。為了減少收斂的時間，可以求助於一種更複雜的方法。
在更複雜的方法中，每個P的丟棄概率的淨增加/減少量是一個迭代過程的結果，它取決於(i)丟棄概率(記作ADP(I，q，P)並被提供給外推處理實體240)的時間平均值；(ii)一個臨時丟棄概率(記作DPtemp(i，q，P)；(iii)收到業務流臨時平均字節數(記作ARTBtemp(i，q，P))。
在初始化時，臨時丟棄概率DPtemp(i，q，P)設定為以前的DP(i，q，P)值，收到業務流臨時平均字節數ARTBtemp(i，q，P)設定為以前的收到業務流字節ARTB(i，q，P)的平均數。與前面一樣，這個迭代過程的起點是通過比較分配帶寬BWALLOC(i，q)和使用的平均總帶寬TARTB(i，q)來確定是否需要增加或者降低丟棄概率。取決於是否需要增加或者減少丟棄概率，來對一個或者多個P的臨時丟棄概率值做出相應的改變。
在這一點上，收到業務流字節臨時平均字節數ARTBtemp(i，q，P)被改變了，但是在相反的方向上。因此，臨時丟棄概率的增加與收到業務流平均臨時平均字節數相對應，而臨時丟棄概率的降低與收到業務流平均臨時平均字節數的增加相對應。利用每個收到業務流平均臨時字節數的新值，將對所有P的ARTBtemp(i，q，P)值全部相加，就計算出了使用的臨時平均總帶寬TARTBtemp(i，q)。將TARTBtemp(i，q)的值與BWALLOC(i，q)值進行比較，比較的結果就表明了分配帶寬是否比期望的總平均使用帶寬大。
改變一個或者多個P的臨時丟棄概率DPtemp(i，q，P)的步驟、重新計算ARTBtemp(i，q，P)對整個P的值的步驟以及計算TARTBtemp(i，q)值的步驟都可以多次重複。在一個實施例中，一直重複這個步驟直到TARTBtemp(i，q)值處於所需要的BWALLOC(i，q)值範圍內。一個可選方案是，將這個步驟重複固定的次數或者直到臨時丟棄概率實現收斂。在經過需要的重複次數以後，在任何情況下，每個丟棄概率DP(i，q，P)都設定為相應臨時丟棄概率DPtemp(i，q，P)的當前值，並將丟棄概率提供給輸入線路卡中的PAUs。在這種方法中，就可以預測由於丟棄概率的變化而造成的帶寬利用率的變化，以便更快地得到所需要的帶寬利用率。
對DPtemp(i，q，P)和ARTBtemp(i，q，P)的值可以使用不同的初始步長，初始步長可以是一個固定值。對於ARTBtemp(i，q，P)值，初始步長可以是一個取決於的值，在每次(或者第N次)迭代中以2的冪次方減小。在每次(或者每第N次)迭代過程中，相對於它們以前的值來為DPtemp(i，q，P)和ARTBtemp(i，q，P)的增加或降低來減少步長，這樣是很有利的。舉個不作為限制的例子，減少量可以是對數的(比如2的冪次方)。
應當認識到的是，通過將丟棄概率不僅作為帶寬利用率的函數，還作為其它參數的函數關係，所述參數是比如出口隊列112和/或子隊列的深度、發送到每個接口出口隊列和/或子隊列的單個數據流的帶寬變化性(猝發性)，就能夠推動本領域一般技術人員提高概率處理實體230的性能。一個數據流的猝發性可以看作是那個數據流帶寬的導數。
外推處理實體240除了從概率處理實體230接收ADP(I，Q，P)值以外，還從出口業務流管理器114接收ARTB(I，Q，P)值，即每個有效的I，Q，P組合的平均收到字節數。如果丟棄概率為零，外推處理實體240就以其輸入為基礎為每個有效的I，Q，P組合計算收到業務流字節的平均數。這些值以ARTBDP0(I，Q，P)值的形式被提供給概率處理實體230。
ARTBDP0(I，Q，P)值的計算按照以下方式進行給定每個有效的I，Q，P組合的收到業務流字節數的平均值，並且給定相同的I，Q，P組合的平均丟棄概率，如果丟棄概率為零，就通過外推計算收到業務流字節數的平均值。特別地，ARTBDP0(I，Q，P)＝ARTB(I，Q，P)/(1-ADP(I，Q，P))。如果更經常地收到ARTB(I，Q，P)值而非ADP(I，Q，P)值，那麼一旦收到ARTB(I，Q，P)值，就要讀取相應的ADP(I，Q，P)值並且計算相應的ARTBDP0(I，Q，P)。
另外，外推處理實體240還對那些與一個共用接口和出口隊列相關聯的所有優先級的ARTBDP0(I，Q，P)值求總和，得到給定I，Q組合的接收字節平均數以及該I，Q組合效率最低情況下收到的字節。外推處理實體240以該I，Q組合的ARTBDP0(I，Q)值的形式將這個信息提供給分配處理實體220。因此，ARTBDP0(I，Q)＝(ARTBDP0(I，Q，P))p，其中(X)p表示一系列X(P)在整個P值範圍內總和。
在一些實施例中，這樣是有利的限制將DP(I，Q，P)值傳輸到PAUs 118的速度以限制通過交換結構02的非業務流字節，同時還限制丟棄概率改變後由於更長的反應時間所引起的不穩定性。對於一個給定的(I，Q，P)三元組的新丟棄概率，不論何時當它從原先的值改變一個超過預設絕對值或者相對值的量時都可以被發送出去，而不用以更高的速率進行更新。這個預設值是可編程的。這個預設值對同一接口的一個輸出埠到下一個輸出埠或者從一個出口隊列112到下一個隊列可以各不相同，或者對於同一接口I和出口隊列Q組合，從一個子隊列113到下一個子隊列也不相同。在另外的實施例中，只要同-(I，Q)組合的所有丟棄概率中的一個變化超出了預設絕對值或者相對值，全部丟棄概率就會被發送出去。在丟棄概率沒有實質性差別的情況下設有一個定時器，使得丟棄概率值至少按照每秒中的預設時間次數將概率值發送到PAUs 118。
此外，根據本發明的一個實施例，為每個輸出埠、與該輸出埠關聯的出口隊列、以及優先級的組合單獨產生一個丟棄概率。在其它的實施例中，一個數據包的優先級沒有考慮到是丟棄還是轉發一個數據包的決定中去，因此，一個單一的丟棄概率將與每個有效的輸出埠和出口隊列的組合關聯。
而且，前面已經提到過，在決定不傳輸收到的數據包的情況下，數據包可能完全從存儲器中丟棄或者被發送到一個存儲丟棄數據包的單獨存儲庫。在另外的實施例中，沒有傳輸到處理結構的數據包可以沿著一個備用通道重新發送。
在又一實施例中，要丟棄的數據包被「標記」為「可丟棄數據」，直到需要使用該數據包在存儲器中佔用的空間時，才將該數據包丟棄。在這種方法中，如果導致數據包被打上「標記」的擁堵減輕，數據包會取消標記並繼續發送到交換結構。「標記」的數據包的特性可以規定在數據包的首部。在再一實施例中，被標記的數據包仍然可通過交換結構來傳輸，但是標記可以用做發給高層應用程式的信號，必須迅速降低某個數據流。
顯而易見，雖然上述說明提到了「丟棄」概率，但這並不意味著數據包就真正根據這種概率被丟棄了。一個例子是不傳輸到交換結構102的包被存儲在一個單獨的存儲器中或者記錄下來供以後參考。因此，術語「丟棄概率」可以看作是指非傳輸概率的更寬泛的概念。根據數據包發送到的出口隊列的「丟棄」概率，PAU 118做出傳輸或者不傳輸收到數據包的決定。
本領域一般技術人員應理解的是前面所述關於路徑接收單元118、丟棄概率計算模塊120、利用率處理實體210、分配處理實體220、概率處理實體230和外推處理實體240功能性的全部或部分可以作為預編程的硬體或者固件元件(比如，專用集成電路(ASICs)，電可擦可編程只讀存儲器(EEPROMs)，等等)，或者其它相關元件來執行完成。
在本發明的其它實施例中，前面所述關於路徑接收單元118、丟棄概率計算模塊120、利用率處理實體210、分配處理實體220、概率處理實體230和外推處理實體240功能性的全部或部分可以作為軟體來實現，所述軟體由一系列通過數字計算機來執行程序指令構成，數字計算機包括一個處理器和與通信總線相連的一個存儲器。這種存儲器包括數據和程序指令。為了執行規範中描述的功能塊，處理器適合於處理數據和程序指令。為此在圖中對操作進行了描述。
程序指令能被存儲在一個固定、有明確形狀並且計算機系統可讀的媒體中，(如，可移動磁碟，CD-ROM，ROM，或者硬碟)，或者將程序指令遠程存儲，但通過由傳輸媒體連接到網絡的數據機或者其它接口設備(如通道轉接器)可以傳輸到計算機系統。傳輸媒體可以是有明確形狀的媒體(如光纖或者模擬傳輸線)或者是使用無線技術完成的媒體(如微波、紅外線或者其他傳輸方法)。
本領域一般技術人員顯然能夠理解，程序指令可以用許多程式語言寫成，和很多計算機體系結構或者作業系統一起使用。比如，有些實施例可以在過程程式語言(如「C語言」)或者面向對象的程式語言(比如「C++」或「JAVA」)中完成。
本發明的實施例已經進行了描述和說明，本領域的技術人員顯然能夠理解，可以對本發明進行各種修改和變化可以對本發明做出修改、變化而不脫離本發明的範圍，如同權利要求書要求的那樣。
權利要求
1.一種調節通過一個裝置的數據包流的方法，所述裝置設有至少包括一個輸入埠和至少一個輸出埠的一個處理結構；一個控制實體，所述控制實體與所述至少一個輸入埠相連以調節傳輸到那裡的數據包流；以及多個出口隊列，所述出口隊列至少與一個輸出埠相連以臨時存儲從那裡收到的數據包，所述的方法包括獲得有關出口隊列收到數據包的帶寬利用率信息；從帶寬利用率信息中確定每個出口隊列的丟棄概率；為控制實體提供每個出口隊列的丟棄概率，供控制實體用來有選擇地將數據包傳輸到處理結構的至少一個輸入埠。
2.如權利要求1所述的方法，其特徵在於，獲得關於出口隊列處收到數據包的帶寬利用率信息包括從至少一個業務流管理實體接收所述帶寬利用率，業務流管理實體設在出口隊列和至少一個輸出埠之間。
3.如權利要求1所述的方法，其特徵在於，每個數據包或者由多個業務流字節或者由非業務流字節組成，並且，獲得關於出口隊列處收到數據包的帶寬利用率信息還包括為所述至少一個輸出埠中的每一個特定埠確定連接到該特定輸出埠的每個出口隊列每單位時間收到的業務流字節平均值。
4.如權利要求3所述的方法，其特徵在於，從帶寬利用率信息中為一個特定的出口隊列確定丟棄概率包括為所述特定出口隊列確定一個分配業務流帶寬；將所述特定出口隊列的收到業務流字節平均值與該出口隊列的分配業務流帶寬進行比較；以及如果所述特定出口隊列的收到業務流字節平均值比該出口隊列的分配業務流帶寬大，增加該出口隊列的丟棄概率；如果所述特定出口隊列的收到業務流字節平均值比該出口隊列的分配業務流帶寬小，降低該出口隊列的丟棄概率。
5.如權利要求3所述的方法，其特徵在於，從帶寬利用率信息中為一個特定的出口隊列確定丟棄概率包括為所述特定出口隊列確定一個分配業務流帶寬；將所述特定出口隊列的收到業務流字節平均值與該出口隊列的分配業務流帶寬進行比較；以及如果所述特定出口隊列的收到業務流字節平均值比該出口隊列的分配業務流帶寬大，就將該出口隊列的丟棄概率設為該出口隊列以前的丟棄概率的時間平均值與一個正的增加值之和；如果所述特定出口隊列的收到業務流字節平均值比該出口隊列的分配業務流帶寬小，就將該出口隊列的丟棄概率設為該出口隊列以前的丟棄概率的時間平均值與一個負的增加值之和。
6.如權利要求3所述的方法，其特徵在於，為一個特定的出口隊列確定丟棄概率包括(a)將臨時收到業務流字節平均值設定為收到業務流字節的平均數；(b)將臨時丟棄概率設定為所述特定出口隊列以前丟棄概率值的時間平均值；(c)為所述特定出口隊列確定一個分配業務流帶寬；(d)將臨時收到業務流字節平均值與所述特定出口隊列的分配業務流帶寬進行比較；(e)如果臨時收到業務流字節平均值比所述特定出口隊列的分配業務流帶寬大，就給臨時丟棄概率加上一個正的概率增加值，並且給臨時收到業務流字節平均值增加一個負的帶寬增加值；(f)如果臨時收到業務流字節平均值比所述特定出口隊列的分配業務流帶寬小，就給臨時丟棄概率加上一個負的概率增加值，並且給臨時收到業務流字節平均值增加一個正的帶寬增加值；(g)將所述特定出口隊列的丟棄概率設定為臨時丟棄概率。
7.如權利要求6所述的方法，還包括執行步驟(d)，(e)和(f)一個預定的次數。
8.如權利要求6所述的方法，還包括執行步驟(d)，(e)和(f)，直到臨時收到業務流字節平均值在所述特定出口隊列分配業務流帶寬所需要的範圍內。
9.如權利要求8所述的方法，還包括測量所述特定出口隊列的深度並執行步驟(d)，(e)和(f)，直到所述特定出口隊列的深度在所需的範圍內。
10.如權利要求9所述的方法，還包括測量所述特定出口隊列深度的可變性，並執行步驟(d)，(e)和(f)，直到所述特定出口隊列深度的可變性在所需要的範圍內。
11.如權利要求6所術的方法，還包括執行步驟(d)，(e)和(f)，直到所述特定出口隊列的臨時丟棄概率收斂到一個需要的精確度。
12.如權利要求6所述的方法，其特徵在於，為所述特定出口隊列確定一個分配業務流帶寬包括如果所述特定出口隊列的丟棄概率為零，則確定在出口隊列將收到的業務流字節平均值；以及如果所述特定出口隊列的丟棄概率為零，而且如果出口隊列將收到的業務流字節平均值大於該隊列的分配業務流帶寬，則為該出口隊列的分配業務流帶寬加上一個正的增加值；如果所述特定出口隊列的丟棄概率為零，而且如果出口隊列將收到的業務流字節平均值小於該隊列的分配業務流帶寬，則為該出口隊列的分配業務流帶寬加上一個負的增加值。
13.如權利要求6所述的方法，還包括為所有連接到所述特定輸出埠的出口隊列確定可用的業務流帶寬；為所有連接到所述特定輸出埠的出口隊列確定分配的總業務流帶寬；其中，只有當分配給連接到所述特定輸出埠的所有出口隊列的總業務流帶寬小於連接到該輸出埠的所有出口隊列的可用業務流帶寬時，才執行給所述特定出口隊列分配業務流帶寬增加一個正的增加值這個步驟。
14.如權利要求13所述的方法，其特徵在於，為連接到輸出埠的所有出口隊列確定一個可用業務流帶寬包括確定帶寬梯度，該帶寬梯度表明了與所述特定輸出埠相連的所有出口隊列的可用業務流帶寬增加或者降低的速率；按照與梯度帶寬的函數關係增加或者降低與所述特定輸出埠相連的所有出口隊列的可用業務流帶寬。
15.如權利要求14所述的方法，其特徵在於，獲得與出口隊列處收到數據包相關的帶寬利用率信息還包括為所述至少一個輸出埠中的每一個特定埠確定從所述特定輸出埠單位時間收到的非業務流字節平均值，並且還在於，為連接到所述特定輸出埠的所有出口隊列確定一個可用業務流帶寬還包括為連接到所述特定輸出埠的所有出口隊列確定一個總鏈路容量；將最大可用業務流帶寬設定為所述總鏈路容量與所述非業務流字節平均值之差；其中，連接到所述特定輸出埠的所有出口隊列的可用業務流帶寬不會超過最大可用業務流帶寬。
16.如權利要求15所述的方法，其特徵在於，如果所述特定出口隊列的丟棄概率為零，確定在該出口隊列將收到的業務流字節平均值還包括計算該出口隊列每個時間單位收到業務流字節平均值和該出口隊列以前丟棄概率值的時間平均值的一個函數。
17.如權利要求16所述的方法，其特徵在於，所述函數是以下兩項的商(i)所述特定出口隊列每個時間單位收到的業務流字節平均值，(ii)所述特定出口隊列以前丟棄概率值的時間平均值與整體時間的差。
18.如權利要求6所述的方法，還包括如果所述特定出口隊列的丟棄概率為零，確定在該出口隊列將收到的業務流字節平均值；以及執行步驟(d)，(e)，(f)至少兩次；其中，如果出口隊列為零，正的寬帶增加量是所述特定出口隊列將收到的業務流平均數的第一部分，所述第一部分隨著步驟(f)的執行將減少；並且其中，如果出口隊列為零，負的寬帶增加量是所述特定出口隊列將收到的業務流平均數的第二部分，所述第二部分隨著步驟(e)的執行將減少。
19.如權利要求18所述的方法，其特徵在於，正的概率增加值具有隨著步驟(e)的執行而減少的一個值，並且，負的概率增加值具有隨著步驟(f)的執行而減少的一個值。
20.如權利要求14所述的方法，其特徵在於，獲得與所述出口隊列收到的數據包有關的帶寬利用率信息包括為所述至少一個輸出埠中的每個特定輸出埠確定從該輸出埠收到連續數據包之間的平均空閒時間。
21.如權利要求20所述的方法，其特徵在於，確定一個帶寬梯度包括將從所述特定輸出埠收到的連續信息包之間的平均空閒時間與一個第一閾值進行比較；以及如果從所述特定輸出埠收到的連續信息包之間的平均空閒時間低於第一閾值，設定帶寬梯度來為連接到所述特定輸出埠的所有出口隊列指示可用業務流帶寬中的一個第一降低速率。
22.如權利要求21所述的方法，還包括將從所述特定輸出埠收到的連續信息包之間的平均空閒時間與一個小於第一閾值的第二閾值進行比較；以及如果從所述特定輸出埠收到的連續信息包之間的平均空閒時間低於第二閾值，設定帶寬梯度來為連接到所述特定輸出埠的所有出口隊列指示可用業務流帶寬中的一個第二降低速率，其中，所述第二降低速率比所述第一降低速率大。
23.如權利要求22所述的方法，還包括將從所述特定輸出埠收到的連續信息包之間的平均空閒時間與一個第三閾值進行比較；以及如果從所述特定輸出埠收到的連續信息包之間的平均空閒時間高於第三閾值，設定帶寬梯度來為連接到所述特定輸出埠的所有出口隊列指示可用業務流帶寬中的一個增加速率。
24.如權利要求23所述的方法，還包括確定多個出口隊列中存儲器利用率的程度；以及編程將第一、第二和第三閾值中至少一個表示成所述存儲器利用率程度的函數。
25.如權利要求1所述的方法，其特徵在於，所述處理結構的至少一個輸出埠為多個輸出埠，並且，多個輸出埠中的每個埠都分別與多個出口隊列中的一個隊列相連接。
26.如權利要求1所述的方法，其特徵在於，所述處理結構的所述至少一個輸出埠中的至少一個分別與多個出口隊列中的一個隊列相連接。
27.如權利要求1所述的方法，其特徵在於，將每個出口隊列的丟棄概率提供給控制實體是在可編程的基礎上來進行操作。
28.如權利要求1所述的方法，還包括記錄每個出口隊列在選擇時間的丟棄概率；探測是否有一個預定幅度的變化在至少一個出口隊列的丟棄概率中出現；其中，只有探測到有至少一個預定幅度的變化在一個特定出口隊列的丟棄概率中出現，才能執行將所述特定出口隊列的丟棄概率提供給控制實體。
29.如權利要求1所述的方法，還包括記錄每個出口隊列在選擇時間的丟棄概率；探測是否至少有一個預定幅度的變化在至少一個出口隊列的丟棄概率中出現；其中，在下面兩種情況下執行將一個特定出口隊列的丟棄概率提供給控制實體的步驟(i)探測到有至少一個預定幅度的變化在所述特定出口隊列的丟棄概率中出現；或者(ii)經過預定的時間後，不管是否探測到有至少一個預定幅度的變化在所述特定出口隊列的丟棄概率中出現。
30.如權利要求1所述的方法，還包括對於每個收到數據包，控制實體確定收到數據包前往哪個出口隊列，並在數據包要傳輸到的那個出口隊列的丟棄概率的基礎上，確定將收到的數據包傳輸還是不傳輸到處理結構。
31.如權利要求30所述的方法，其特徵在於，在數據包要傳輸到的那個出口隊列的丟棄概率的基礎上，將收到的數據包傳輸到處理結構還是不進行傳輸包括為收到的數據包產生一個隨機數；將隨機數與收到數據包要傳輸到的那個出口隊列的丟棄概率就比較；以及在比較的基礎上將收到的數據包傳輸或者不傳輸到處理結構。
32.如權利要求31所述的方法，其特徵在於，不傳輸一個收到的數據包包括丟棄數據包。
33.如權利要求31所述的方法，其特徵在於，不傳輸一個受到的數據包包括將數據包標記為可丟棄數據包。
34.如權利要求31所述的方法，其特徵在於，不傳輸一個收到的數據包包括在一個存儲位置存儲收到的數據包並將數據包標記為可丟棄數據包，並且，傳輸一個數據包包括只傳輸沒有被標記為可丟棄的數據包。
35.如權利要求34所述的方法，其特徵在於，不傳輸一個收到的數據包還包括確定在出口隊列中是否存在擁堵減輕的情況；以及如果在出口隊列中存在擁堵減輕的情況，就確定是否存儲位置要被用來存儲其它數據包，如果不是，就不再標記數據包為可丟棄數據包。
36.一種計算機可讀的存儲介質，包括程序指令，用來在一個計算裝置執行中執行權利要求1中定義的方法。
37.一個用來在一個裝置中使用的丟棄概率計算模塊，該裝置設有(i)一個處理結構，設有至少一個輸入埠和至少一個輸出埠；(ii)一個控制實體，與所述至少一個輸入埠相連，用來調節流入到該埠的數據包；(iii)多個出口隊列，與所述至少一個輸出埠相連，用來臨時存儲從出口收到的數據包，所述丟棄概率計算模塊包括用於獲得在出口隊列收到數據包帶寬利用率信息的裝置；用於從帶寬利用率信息中確定每個出口隊列的丟棄概率的裝置；以及用來向控制實體提供每個出口隊列丟棄概率的裝置，供控制實體用來有選擇地將數據包傳輸到處理結構的所述至少一個輸入埠。
38.一個用來在一個裝置中使用的丟棄概率計算模塊，該裝置設有(i)一個處理結構，設有至少一個輸入埠和至少一個輸出埠；(ii)一個控制實體，與所述至少一個輸入埠相連，用來調節流入到該埠的數據包；以及(iii)多個出口隊列，與所述至少一個輸出埠相連，用來臨時存儲從出口收到的數據包，所述丟棄概率計算模塊包括一個分配處理實體，用於為每個出口隊列確定一個分配的業務流帶寬；以及一個與分配處理實體相連的概率處理實體，所述概率處理實體適合於從分配處理實體中為每個出口隊列接收分配業務流帶寬，還適合於從一個外部實體中為每個出口隊列接收業務流字節的平均值，概率處理實體可用於將每個出口隊列的收到業務流字節平均值與所述特定出口隊列的分配業務流帶寬進行比較；根據所述特定出口隊列收到業務流字節的平均值是比該出口隊列的分配業務流帶寬更大還是更小，將出口隊列的丟棄概率設定為該出口隊列以前丟棄概率值的時間平均值與一個正的或者負的增加值的和。
39.一種計算機可讀的存儲介質，包括一個程序單元，該程序單元供一個計算裝置用來實現權利要求38中的丟棄概率計算模塊。
40.一種裝置，包括一個處理結構，該處理結構設有至少一個輸入埠和至少一個輸出埠，所述處理結構適合於從至少一個輸入埠接收數據包並將處理過的數據包轉發到至少一個輸出埠；多個出口隊列，每個出口隊列與處理結構上所述的至少一個輸出埠之一相連，每個出口隊列適合於(i)臨時存儲從處理結構的相應輸出埠收到的數據包；(ii)在出口隊列收到數據包的基礎上確定帶寬利用率信息；一個丟棄概率計算模塊，與出口隊列相連，所述丟棄概率計算實體適合於在帶寬利用率信息的基礎上，確定每個出口隊列的丟棄概率；一個數據包接收單元，該數據包接收單元與處理結構的至少一個輸入埠相連，並且與丟棄概率計算模塊相連，所述數據包接收單元適合於(i)接收輸送到處理結構中所述至少一個輸出埠的數據包；(ii)確定每個收到數據包關聯的出口隊列；(iii)在每個收到數據包的出口隊列的丟棄概率的基礎上，或者將所述數據包傳輸或者不傳輸到處理結構的所述至少一個輸入埠之一。
41.如權利要求40所述的裝置，其特徵在於，所述至少一個輸出埠是多個輸出埠，所述裝置還包括多個輸出線路卡，每個輸出線路卡與處理結構的所述多個輸出埠的一個獨特的子集相連；其中，丟棄概率計算模塊的一部分設在每個輸出線路卡上；其中，丟棄概率計算模塊設在一個特定輸出線路卡上的那一部分就是丟棄概率計算模塊中與處理結構的多個輸出埠的所述子集連接的那部分，而所述處理結構是所述特定輸出線路卡所連接的處理結構。
42.如權利要求41所述的裝置，其特徵在於，所述至少一個輸入埠是多個輸入埠，還包括多個輸入線路卡，每個輸入線路卡與處理結構的所述多個輸入埠的一個獨特的子集相連；其中，數據包接收單元的一部分設在每個輸入線路卡上。
43.如權利要求40所述的裝置，其特徵在於，處理結構是一個交換結構。
44.一種調節通過一個裝置的數據包流的方法，該裝置設有至少包括一個輸入埠和至少一個輸出埠的一個處理結構；一個控制實體，該控制實體與至少一個輸入埠相連以調節傳輸到那裡的數據包流；以及多個出口隊列，所述出口隊列至少與一個輸出埠相連以臨時存儲從那裡收到的數據包，每個數據包帶有從一組優先級選擇出的相應優先級，所述方法包括獲得有關出口隊列收到數據包的帶寬利用率信息；從帶寬利用率信息中確定與每個輸出隊列和每個優先級關聯的丟棄概率；向控制實體提供每個出口隊列和優先級關聯的丟棄概率，供控制實體用來有選擇地將數據包傳輸到處理結構的至少一個輸入埠。
45.如權利要求44所述的方法，還包括對於每個收到的數據包，控制實體確定收到的數據包前往哪個出口隊列，還確定該數據包的優先級，以及在收到數據包前往的出口隊列的丟棄概率和數據包的優先級的基礎上，是將收到數據包傳輸還是不傳輸到處理結構。
46.一種調節通過一個裝置的數據包流的方法，該裝置設有一個入口實體、一個出口實體、一個位於入口實體和出口實體之間的處理結構、以及一個控制實體，該控制實體適合於在將數據包傳輸到入口實體之前對數據包進行處理，所述方法包括獲得有關出口實體收到數據包的擁堵信息；以及將擁堵信息提供給控制實體，供控制實體用來在數據包傳輸到入口實體之前對數據包進行處理。
47.如權利要求46所述的方法，還包括對於控制實體收到的每個數據包，在擁堵信息的基礎上將收到數據包傳輸或者不傳輸到入口實體。
48.如權利要求47所述的方法，其特徵在於，不將收到數據包傳輸到入口實體包括丟棄收到的數據包。
49.如權利要求47所述的方法，其特徵在於，不將收到數據包傳輸到入口實體包括在一個存儲位置存儲數據包。
50.如權利要求47所述的方法，其特徵在於，不將收到數據包傳輸到入口實體包括沿著一個備用線路重新傳輸數據包。
51.如權利要求46所述的方法，還包括對於控制實體收到的每個數據包，在擁堵信息的基礎上，在收到數據包傳輸到入口實體之前或者對數據包進行標記或者不進行標記。
52.如權利要求51所述的方法，還包括在出口實體處接收被標記的數據包以探測擁堵信息。
53.如權利要求46所述的方法，其特徵在於，獲得在出口實體收到的有關數據包的擁堵信息還包括確定一個丟棄概率。
54.如權利要求53所述的方法，還包括為控制實體收到的每個數據包產生一個數量值；將數量值與丟棄概率進行比較；以及在所述比較步驟結果的基礎上，將收到的數據包傳輸或者不傳輸到入口實體。
55.如權利要求54所述的方法，其特徵在於，數量值是一個隨機的數字。
56.如權利要求46所述的方法，其特徵在於，擁堵信息包括帶寬利用率信息。
57.如權利要求46所述的方法，其特徵在於，出口實體包括多個出口隊列，並且，擁堵信息還包括每個出口隊列的佔用率。
58.如權利要求57所述的方法，其特徵在於，出口實體包括多個出口隊列，並且，擁堵信息包括每個出口隊列佔用率的可變性。
全文摘要
一種用於調節通過一種裝置比如帶有交換結構的路由器的數據包流的方法、裝置和計算機可讀的存儲介質。為設在裝置的出口級的多個隊列中的每一個隊列收集擁堵信息，比如帶寬利用率統計數字。根據帶寬利用率的統計數字，為每個隊列計算一個「丟棄概率」。這個信息被周期性地或者按照其它的一個控制時間周期，比如當丟棄概率發生巨大變化時，傳輸到入口級。根據數據包要到達的隊列以及該隊列的丟棄概率，入口級將數據可控制地傳輸到交換結構或者不進行傳輸。在這種方式中，甚至在擁堵有機會發生以前就已經避免了擁堵的出現。這將提高帶寬的利用率，因為在入口級被丟棄的數據包就不會佔用裝置中的其它資源。
文檔編號H04L12/56GK1593044SQ02819147
公開日2005年3月9日 申請日期2002年9月24日 優先權日2001年9月27日
發明者史蒂夫·羅尚, 理察·S·諾曼, 羅賓·布瓦萬 申請人:超級晶片有限公司