用於加權公平隊列的方法與系統的製作方法

2023-06-07 14:53:36

專利名稱：用於加權公平隊列的方法與系統的製作方法
技術領域：
本發明大體涉及在速率調整業務狀態中用於加權公平隊列的方法與系統，更具體地涉及為基於幀的業務提供加權公平隊列的方法與系統，其允許加權公平隊列調度器內對子類競爭的速率限制與速率保證的結合。
背景技術：
每個傳輸數據分組的計算機和通信網絡必須實施某種形式的調度以確保數據業務以特定速率通過該網絡進行傳輸。在任何已知的時刻，網絡可能具有包含等待通過該網絡傳輸的數據隊列的數十萬或甚至百萬個連接點。需要某種形式的調度來使得網絡組件以公平及時的方式處理這些數據隊列。一般，調度器通過與數據隊列相互作用來調度通過網絡的數據傳輸。調度器可以是層級的，其中所選子類還可以是調度器，但必須從其子類中選擇。該調度器確定從合格數據隊列或其它含有可用數據的合格子類調度器處數據傳輸的次序。通常，單獨的處理將數據排列到隊列中，但是該單獨的處理以聲明數據可用或子類合格的方式連接到調度。調度器定期地或基於請求地，選擇帶有可用數據的子類，以從該子類處傳輸數據。層級調度器設立從所選擇隊列處的數據的傳輸。圖1示出包括調度處理12的現有技術的數據系統10，其中數據路徑包括一系列數據隊列Ha、14b、Hc、14d和14e (共同被稱為數據隊列14)和復用(multiplexers) 16a、 16b(共同被稱為復用16)。儘管復用在圖1中顯示為物理單元，但是在一般可擴展的實施中復用物理上並不存在，而是隱含在調度器對用於傳輸的數據隊列14的選擇中。調度處理 12可從任何具有可用數據(「DA」)的數據隊列14中進行選擇；然而，由於實施其分層的本質，調度處理12必須請求子類調度器18從數據隊列14d和數據隊列14e (附圖有錯，附圖標記標為14a)中進行選擇。則子類調度器18選擇合適的數據隊列14d、14e。在該示例中， 調度處理12可直接選擇數據隊列14a、14b和14c。授權給Lyon的專利號為7，373，420的美國專利(以下稱為「『420專利」)公開了一種現有技術的加權公平隊列處理，在這裡引用參考該專利的全部內容。圖2闡明了 『420專利中的加權公平隊列處理，其包括反向信用度管理系統，使用分配給每個數據隊列的權重來確定給予哪個隊列信用度。總的說來，具有反向信用度管理的加權公平隊列(「WFQ-ICM」) 調度器20包括兩個附加處理WFQ信用度分配器22和傳輸選擇器M。傳輸選擇器M —般以輪轉方式進行操作，其中每個具有可用數據和正信用度的子類在傳輸數據處輪到。信用度處理22將信用度分配給子類，這些子類的當前信用度小於其可用數據量 (「ADA」)。每一子類在任一已知時刻累計的信用度量被記錄在子類信用度狀態資料庫沈中。每一子類的信用度量絕不會超出該子類的ADA。在任何時候，如果子類具有小於其ADA 的信用度，子類就被包括在爭取更多信用度的信用度分配器22中。傳輸選擇器M選擇具有正信用度計數的子類來傳輸數據。當子類傳輸數據時，在子類信用度狀態資料庫26中其當前信用度量中就會減少信用度，並且信用度被返回到信
6用度分配器22用於再分配給其它ADA大於信用度量的子類。信用度分配器22以子類消耗信用度相同的速率來分配信用度(也就是，沒有餘額)，因此，WFQ-ICM調度器20的關鍵條件是，無論何時系統都需要精確地了解有多少數據可用於從每個子類隨時的傳輸。該條件防止當子類具有可用數據時而被視為自身不合格，從而使得基於速率來確定合格的重複處理的實施實際上是不可能的。從根本上看，速率限制能夠迫使具有數據的子類停止傳輸或不具有原調度器可用的數據。該限制在層級調度器上還有很重的負擔，其中ADA包括有效地連接調度級間的調度處理的所有派生隊列，無論涉及多少層級。因此，需要的是一種用於含反向信用度管理的加權公平隊列的方法、系統和裝置， 該反向信用度管理可在速率調整業務狀態下使用。

發明內容
本發明有利地提供一種用於基於子類合格及信用度分配而在通信網絡中調度傳輸數據的方法與系統。通常，具有反向信用度管理的加權公平隊列的調度器可在速率型傳輸環境中使用，從而允許在加權公平隊列調度器內競爭的子類的速率限制與速率保證的結
I=I O根據本發明的一方面，用於在通信網絡中調度傳輸數據的系統包括信用度分配器和傳輸選擇器。所述通信網絡包括多個子類。所述傳輸選擇器通信地連接到信用度分配器。所述信用度分配器操作以將信用度分配給合格子類與含有負信用度計數的子類中的至少一個。每個信用度可收回用於數據傳輸。所述信用度分配器進一步操作來保持表示未分配的可用信用度總量的信用度結餘，用分配的信用度之比影響子類間的公平，以及從該信用度結餘中扣除已分配的信用度。所述傳輸選擇器操作來選擇用於退出隊列的至少一個合格和允許的子類，所述合格和允許的子類的偏向選擇是具有正信用度的合格和允許的子類，以及將信用度增加到與選擇用於退出隊列的數據量相對應的信用度結餘。根據本發明的另一方面，提供用於在通信網絡中為子類分配信用度的方法。每個信用度可收回用於數據傳輸量。信用度被分配到合格允許子類和帶有負信用度計數子類中的至少一個。表示未分配的可用信用度總量的信用度結餘被保持，且分配的信用度從該信用度結餘中扣除。根據本發明的另一方面，提供用於在通信網絡中信用度調度傳輸數據的方法。所述通信網絡包括多個子類。設立多個傳輸控制隊列用於退出隊列。每個傳輸控制隊列能夠包含相對應的合格子類的至少一個識別器，並且具有根據相對應的信用度計數需求限定的優先級。每個合格子類被分派到多個傳輸控制隊列中的一個。每個合格子類具有滿足其分派的傳輸控制隊列的信用度計數需求的信用度狀態。根據與該合格子類相對應的傳輸控制隊列的優先級，至少一個合格子類被選擇用於退出隊列。與退出隊列的數據量相對應的信用度被增加到該信用度結餘。每個合格和允許的子類在傳輸控制隊列中的一個中被表示。


本發明的更完整的理解以及伴隨的優點和其中的特徵，通過參考下述的描述並結合附圖將會更容易理解，其中圖1是示例現有技術數據調度處理的框圖2是具有反向信用度管理的示例現有技術加權公平隊列數據調度處理的框圖；圖3是具有根據本發明原理構成的反向信用度管理的示例加權公平隊列數據調度處理的框圖；圖4是根據本發明原理構成的示例信用度分配器的框圖；圖5是根據本發明原理的示例信用度分配器處理的流程圖；圖6是根據本發明原理在響應合格轉換時，示例信用度處理的流程圖；圖7是高加權子類的示例現有技術一維加權交錯輪轉循環輪轉調度處理的框圖；圖8是根據本發明原理構成的高加權子類的示例二維加權交錯輪轉循環輪轉調度處理的框圖；圖9是具有根據本發明原理構成的四個優先級的示例二維加權交錯輪轉循環輪轉調度處理的框圖；圖10是具有根據本發明原理構成的示例基本傳輸選擇器的框圖；圖11是具有根據本發明原理構成的示例改進的傳輸選擇器的框圖；圖12是根據本發明原理的加權公平隊列子類的示例傳輸選擇處理的流程圖；和圖13是根據本發明原理在響應增加的信用度和合格轉換時，示例傳輸選擇處理的流程圖。
具體實施例方式在詳細描述根據本發明的示例實施例之前，應該注意的是，實施例主要涉及設備部件和處理步驟的結合，所述設備部件和處理步驟涉及實現一種用於為基於幀的傳輸提供加權公平隊列的系統和方法，其允許對在加權公平隊列調度器內的子類速率限制和速率保證的結合。相應地，系統和方法的組件在恰當的地方通過附圖中的常規符號表示，為了不使那些對能受益於此處描述的本領域的普通技術人員來說明顯清楚的細節影響本發明，只顯示了那些對恰當理解本發明的實施例有關的具體細節。如這裡使用的，相關術語，諸如「第一」和「第二」、「頂部」和「底部」等等，可能僅僅用來將一個實體或元件從另一個實體或元件中區別開來，而不必然地需求或暗指這些實體或元件之間的任何物理或邏輯關係或順序。「根」結點是指加權公平隊列樹中的最高級結點，或層級加權公平隊列樹的分支中的最高結點。特定結點的「派生」是任何低於提及結點級別的結點，提及結點的衍生可追溯回該提及結點。類似地，特定結點的「父類」是任何高於提及結點級別的結點，提及結點的衍生可追溯回該提及結點。術語「子類」、「子類結點」或 「子類」是指任何調度樹中結點的直接派生。通常，當討論特定結點的關係時，術語「子類」 是指低於提及結點一個級別的結點(調度器結點或隊列)。並且，任何從具有更高級結點派生出來的結點可稱為「子類結點」或「子類」。本發明的一個實施例有利地提供用於具有反向信用度管理的加權公平隊列的系統、方法和裝置，該反向信用度管理可在速率型傳輸環境中使用。所述系統和方法允許在加權公平隊列調度器內競爭子類的速率限制和速率保證的結合。當子類返回未使用的信用度時，信用度結餘機制可允許信用度保存。先前，未使用的信用度由信用度分配系統分配，而不了解子類將在其速率限制內保持多久且繼續具有數據來傳輸。另外，不同於現有技術，本發明的實施例允許子類在合格和不合格間切換，從而提供具有速率限制的子類的簡易結合。現在參考圖3，具有根據本發明的原理構成的改進的反向信用度管理 (「WFQ-ICM-Plus」)的示例加權公平隊列調度器觀包括傳輸選擇器30、信用度分配器32 和子類信用度狀態資料庫；34。傳輸選擇器30從所有用於傳輸數據的合格子類中選擇子類。單獨的合格處理36確定子類是否合格地用於傳輸選擇。合格處理36操作的詳細情況超出了本發明的範圍；相關的描述僅僅是合格處理36確定哪些子類合格用於選擇。以最簡單的形式，合格處理只是子類處的可用數據。以更複雜的形式，可用數據可包括層級中各層的速率限制。這會影響不同於現有技術的性能，因為具有負信用度的子類可能被傳輸選擇器30選擇來用於傳輸。另外，本發明的實施例提供另一處理的可能性，即立即終止 (instantaneously disabling)先前合格的子類，這在現有技術中是不可能的。信用度分配器32包括含系統所有剩餘信用度的信用度結餘(「CB」)38。信用度分配器32是一種加權公平處理，該處理將來自信用度結餘38的信用度分配給所有合格子類和所有具有負信用度的子類。信用度分配器32追蹤每個子類在任何已知時刻累積在子類信用度狀態資料庫；34中的信用度量。不同於現有技術的WFQ-ICM調度器，本發明的實施例有利地不需要系統精確地了解有多少數據是可用。相反，所有信用度分配器32必須了解的就是，子類是「合格的」。信用度分配器32可將信用度分配給任一合格子類。因此，諸如速率形成機這類幹擾處理可容易地結合本發明的實施例來進行操作。理論上，子類可接收許多該子類當前可用或合格用於將來發送的數據量的更多的信用度。然而，一旦子類從「合格」轉換到「不合格」，則該子類先前獲得的所有信用度就會被清除且被返回到信用度結餘38。傳輸選擇器30選擇合格子類來傳輸數據。通常，子類選擇偏向於具有更高信用度計數的子類。因此，具有高的正信用度計數的子類比具有低的正信用度或甚至負信用度計數的子類更可能被選擇來用於傳輸。當子類傳輸數據時，在子類信用度狀態資料庫34中信用度從其當前信用度量中減少，且該信用度被返回到信用度結餘38用於再分配給其它合格子類和負結餘子類。現有技術的WFQ-ICM調度器不允許從具有負信用度計數的子類處傳輸，而允許實現從正信用度計數開始的幀傳輸。然而，因為現有技術並不允許無效或不合格的子類在獲得信用度後進行傳輸，所以這裡不需要上述性能。現在參考圖4，顯示了示例信用度分配器32的簡化實施。通常輪轉信用度分配器 40以數據傳輸從調度器觀退出的同樣速率將信用度分配給合格和負信用度子類。換句話說，來自傳輸選擇器30的傳輸機會可觸發信用度分配器32的信用度分配機會。在一次信用度分配循環期間，每個合格子類和負信用度子類在該循環中分配到多個與其權重值相對應的條目。當每個子類到達輪轉(「RR」)分配隊列42的前端時，循環中的每個子類就得到一個信用度。換句話說，一次RR輪轉循環為每個子類分配一個「信用度」。因此，對於一次全信用度循環，每個子類「i」(表示為子類D被分配Wi個信用度，其中「K」是子類i的權重值。為每個子類i分配&個信用度所需要的RR輪轉循環的次數是 K。當每個子類i已被分配κ個信用度時，信用度循環結束。因此，信用度循環的長度出於具有最大Wi的子類。當子類已接收到該循環的完全加權時，該子類被暫時置於加權超出隊列44中來等待，並且直到下一信用度循環才實施進一步的信用度分配。
在先前的WFQ-ICM調度器中，信用度分配精確地以與傳輸相同的速率進行，因此決不會有未完成的信用度結餘38。可用於分配的信用度是那些從傳輸選擇器30中返回的 {曰用度。相反，如果有必要的話，本發明的實施例允許信用度分配器32攜帶正信用度結餘 32。由於信用度先前合格的子類變得不合格但具有正信用度，所以信用度結餘32可以變得非常大。為了補償這個潛在的大信用度結餘，信用度分配器32不需要如被分配給子類的信用度字節數(表示為「M」)那樣分配從傳輸選擇器30引進的精確的信用度字節數(表示為「N」)。因此，當信用度結餘38包含過剩信用度時(S卩，CB >0)，信用度分配器32就會僅僅通過提高分配給RR分配隊列42的完全輪轉循環輪轉輪轉循環的信用度量，從而M > N，來加速信用度分配。換句話說，對於RR輪轉循環，信用度分配器32在循環期間將M個信用度字節分配給每個子類。任何過剩信用度可被傳送到下一 RR輪轉循環。在另一方面，如果信用度結餘38降到零而M增加，但是由於M*F = N則分配頻率(「F」)會減小，從而允許繼續為每個子類分配M個信用度字節直到該RR輪轉循環結束。提高為RR輪分配的信用度數可確保維持子類間的公平。在分配增加的M個信用度字節中值得注意的兩個例外是通過被分配到M個信用度字節而超出其加權的子類僅被分配其加權的差額，以及不合格用於傳輸但是收集信用度以返回到零信用度的子類絕不會被分配到多於需要返回到零信用度的信用度量。無論是基於控制隊列、基於向量還是一些其它的方法，信用度分配器的其它實施例還可通過提高信用度分配的「標準」速率來加速信用度分配，類似這裡描述的本發明的原理。參考圖5，提供了描述在響應分配信用度機會時由信用度分配器32執行的步驟的示例操作流程圖。在圖5中，信用度分配器32由傳輸選擇器30觸發一次來傳輸N個數據字節(步驟S100)，但是可選擇實施可具有實現同樣步驟的定期性觸發。重要的是要注意， 在本發明的可選擇實施例中，信用度分配器32可了解實際的總傳輸字節計數，從而信用度可在多個N字節或部分N字節中分配。應該注意的是，下面的處理並不闡述合格轉換，而在下文參考圖5來進一步考慮合格因素。如果信用度分配器32不在RR輪轉循環的開始處(步驟S102)，即，信用度已被分配給當前RR隊列中的某個子類，該處理選擇當前RR隊列前端的子類i來為其分配信用度 (步驟S104)。在這種情況下，就要使用信用度分配值M的先前狀態。然而，如果信用度分配器32準備開始新的RR輪轉循環時(步驟S102)，即，已經完成先前的RR輪轉循環，則信用度分配器32判斷信用度分配循環是否需要繼續還是需要全新的信用度循環(步驟S106)。 如果這是信用度循環的開始，則RR隊列被選擇來用於調度(步驟S108)。直到此時，僅僅討論了支持單個RR隊列的調度處理，因此步驟S108將對調度參數進行復位且再次開始處理RR隊列的所有子類。然而，如下文關於圖8的描述，當前發明的典型實施例提供多個區別於多個優先子類的RR隊列，其中，步驟S108可選擇用於處理的不同RR隊列。如果不在信用度循環的開始處，則不需要新的RR隊列。回到判定模塊S106，如果正開始信用度循環，則信用度分配器32確定是否存在過剩信用度結餘(步驟S110)，這種情況下可產生多於單個傳輸事件的信用度(N)。如果存在過剩信用度結餘，則信用度分配器32進入加速信用度分配循環(步驟SlU)，其中在當前 RR輪轉循環中，該信用度分配事件和該信用度分配的其餘事件期間的信用度分配量(M)大於信用度分配事件間傳輸的信用度(N)，S卩，M > N。否則，如果當前沒有信用度結餘(步驟 S114)，則在該信用度分配事件和該RR輪的其餘事件期間分配的信用度量設置為等於信用度分配事件間通常傳輸的信用度量，即，M = N(步驟S114)。注意，當前發明的其它實施例在判定SllO可使用不同的閾值N，例如CB >x字節，其中χ是用於將滯後(hysteresis)加入判定中以加速信用度分配的靜態或動態數值。通過選擇當前RR隊列前端的子類i來開始信用度分配(步驟S104)。如果信用度結餘大於或等於在當前RR輪轉循環期間分配給每個子類的信用度量(步驟S116)，即， CB >= M，則子類，分配到小於其在該信用度循環中的剩餘加權以及在該RR輪轉循環期間分配到的信用度量(步驟S118)，M。分配給子類i的信用度量從信用度結餘中扣除(步驟 S120)，且該RR輪轉循環進行到該RR隊列中的下一子類(步驟S122)。回到判定模塊S116，只要信用度結餘大於子類i的剩餘加權(步驟SlM)，則子類 i被分配到其剩餘的信用度加權(步驟SU6)。分配給子類i的信用度量從信用度結餘中扣除(步驟S120)，且該RR輪轉循環進行到該RR隊列中的下一子類(步驟S122)。然而，如果子類i的剩餘加權大於信用度結餘(步驟SlM)，則沒有信用度被分配且當前信用度分配事件結束，RR隊列前端的剩餘子類i用於下一信用度分配事件。現在參考圖6，提供了描述在響應子類合格狀態的轉換時由信用度分配器32執行步驟的示例操作流程圖。信用度分配器32檢測子類1合格狀態的轉換(步驟SU8)。合格轉換可由單獨的處理(調度器內或調度器外)通知，例如，通過設置或清除該轉換子類的標誌、發送事件，或發送信息。如果子類i從不合格轉換到合格(步驟S130的「是」分支) 且子類i已在信用度系統中(步驟S132的「是」分支)，則信用度分配器32僅僅清除子類i 的等待移除標誌(步驟S134)。如下文描述的步驟S150，當返回到正確的狀態時，等待移除標誌被設置來用於請求子類從信用度分配器32中移除。子類i仍然可以接收由其在RR隊列中的加權和次序確定的信用度。然而，如果子類i當前不在信用度系統中(步驟S132的 「否」分支)，且子類i還未收到大於該信用度循環中其加權i的信用度(步驟S136的「否」 分支)，則子類i被排列到該RR隊列的尾端(步驟S138)且子類i在當前信用度循環的下一輪中接收信用度。如果在當前信用度循環中子類1已經大於其加權(步驟S136的「是」分支)，則子類i被排列到加權超出隊列的尾端(步驟S140)且子類i直到下一信用度循環才接收信用度。回到判定框S130，如果該轉換子類不是新的合格子類，則子類轉換到不合格狀態。 如果新的不合格子類i當前具有正信用度或沒有信用度(步驟S142)，即，信用度i > = 0， 則任何過剩信用度都被返回到信用度結餘(步驟S144)且子類i的信用度計數被設置為零 (步驟S146)。子類i則從該信用度系統中移除(步驟S148)。應該注意的是，從信用度系統中的移除最容易通過等待子類以其方式進行到RR隊列的前端以及在其RR輪轉循環期間移除子類，而不是通過為子類分配信用度來實現。該方法是一種移除標誌的潛在使用。然而，替代的實施例可提供一旦放棄其信用度給信用度結餘就立即允許新的不合格子類i從系統中移除。在回到判定框S142，如果新的不合格子類具有負信用度，即，信用度i =當前RR。因此，D被移至加權超出隊列50 中等待直到該信用度循環結束。類似地，給C信用度，則C被移至加權超出隊列50的尾端。 最後，給B和A信用度，則B和A都被移至RR隊列48的尾端。在循環3期間，給B —個信用度且給A —個信用度。在循環4期間，給B —個信用度且給A —個信用度，然而，已接收到為信用度循環的信用度加權的子類B被移至加權超出隊列50的尾端，在RR隊列48中只留下A。在其餘RR輪轉循環期間，例如，循環5-10，每次循環都為子類A分配一個信用度。該一維WIRR的實際信用度分配序列是DCBA, DCBA, ΒΑ, BA, A, A, A, A, A, A0因此，在該信用度分配序列的一部分中，子類A有7個連續分配。該堆棧序列對系統產生的潛在穩定性問題是，當子類A非常迅速地累計信用度時，子類A運行完所有數據。本發明的實施例通過引進新的二維WIRR調度器改進了 WIRR調度處理，從而促進高加權子類信用度分配的平穩調度。圖8提供了根據本發明的原理構成的示例二維WIRR 調度器52的框圖。二維WIRR調度器52採用多個RR隊列而不是單個RR隊列，RR隊列表示寬帶或加權類。第一維調度是寬帶類，其中WIRR信用度循環在同一寬帶類的子類間提供公平。第二維調度是寬帶類之間的，其中與第一維調度器一起作用的RR隊列間的加權交錯可實現與寬帶類相關聯的寬帶復用(multiplier)。二維WIRR調度器52可包括至少兩組具有相關加權超出隊列的RR隊列，其中每個隊列「i」被配置為具有寬帶復用「η/』的寬帶類。子類可基於WIRR輪轉循環的調整加權 (後來更多)在RR隊列內交錯，且可通過服務整個WIRR循環間的隊列的次序在RR隊列間交錯。在該第二維調度器中，具有Iii復用(multiplier)的RR隊列i被執行Iii次，次數就是整個WIRR循環那樣多的次數乘1(表示為xl)隊列。例如，在圖8的二維WIRR調度器 52中，具有4復用的高優先(「HP」)RR隊列M、HP加權超出隊列56、具有1復用的低優先 (「LP」)RR隊列58，以及LP加權超出隊列60。對於該LP隊列的每一 WIRR信用度循環執行，HP隊列54WIRR信用度循環被執行4次。只要該模式是工作保存持的，執行RR隊列的固定模式是可接受的，就是說即使RR 隊列中的一些沒有包含合格子類也可做出有用調度決定。例如，對於具有含x4復用的HP 隊列M以及含xl復用的LP隊列58的二維WIRR調度器52，信用度分配模式是HP、HP、HP、 HP、LP、重複。用於WIRR信用度循環的加權由第二維復用進行調整，其中該調整的加權等於全加權除以Ili。
例如，在圖8的二維WIRR調度器52中使用關於圖7的上述討論中使用的同樣的加權和子類，子類被排列從而A和B在HP隊列M中，且C和D在LP隊列58中。子類A具有調整的加權2. 5從而其全加權仍然是10 (例如，調整的加權*復用=全加權；2. 5*4 = 10)。 同樣，B具有調整的加權1來映射其全加權4(例如，1*4 = 4)。因為LP隊列58的復用是 1，所以C和D保持其原加權2。在該二維WIRR的第一 WIRR信用度循環期間，只有HP隊列M運行。因此，在WIRR 輪轉循環1期間，信用度分配器分配給B—個信用度並分配給A兩個信用度，而保存子類A 的剩餘加權0. 5。在WIRR信用度循環2期間，再一次，只有HP隊列M運行，但是這時，分配給B —個信用度並分配給A三個信用度(如，該循環的加權2. 5+剩餘加權0. 5 = 3個信用度)。第三WIRR輪轉循環是WIRR輪轉循環1的重複，其中B接收一個信用度，且A接收兩個信用度還剩餘0. 5個信用度。第四WIRR循環是WIRR循環2的重複，其中B分配到一個信用度且A分配到三個信用度。第五即最後的WIRR輪轉循環使得LP隊列58中的子類C 和D每個都接收兩個信用度。因此，二維WIRR調度器52的每個全信用度循環的有效信用度分配次序是HHHHL (ΒΑ, A)，(ΒΑ, A, A)，(ΒΑ, A)，(ΒΑ, A, A)，(DC, DC)。應該注意的是，最大的連續分配被減少到三個A分配，小於現有技術一維WIRR 46 的最大連續分配的一半。應該注意的是，該過程可由單個加權超出隊列實施，因為一次只使用一個RR隊列。非0(1)算法，即，具有計算複雜性的分層調度器，而不是使用通常已知的「大0」標記的0 (1)，當不需要擴展時可滿足第二維。如上述顯示的，強大交錯限制了最大加權子類的連續分配長度。儘管在上文已描述了信用度分配器，但可以想像的是，本發明的二維WIRR 調度器52可通過傳輸選擇器30來用於傳輸隊列的調度退出隊列的處理。二維WIRR的概念可擴展來實施多於兩個優先級的系統中。圖9提供了具有由四個優先RR隊列表示的四個優先級的WIRR調度器62的框圖高優先(「HP」)隊列64、中間優先(「MP」)隊列66、低優先(「LP」)隊列68和極低優先(「VLP」)隊列70。隊列間的固定復用被選擇來提供大動態範圍的調度。例如，假設任一 RR隊列中任一子類的最大調整的權重值是8而最小調整的權重值是1，則任一子類的最大總加權是4096 (84)。基於加權來計算隊列選擇，因此當所有隊列都包含子類時，在每585個調度事件中，HP隊列64被選擇 512次，MP隊列66被選擇64次，LP隊列68被選擇8次，且VL隊列70被選擇1次。WIRR 調度器62處於工作保存，因此不選擇沒有包含子類的隊列。計算或設置的信用度分配模式應該試圖最大地為更大加權隊列分配調度機會。另外，每次隊列被選擇時就應該執行完整的標準WIRR輪。圖9描述的隊列加權是說明性的不表示加權RR隊列的唯一策略。例如， 不同的加權策略可選擇均勻地改變隊列權重，而不是圖示的指數方式。另一策略是可實施動態隊列權重(復用)，該復用根據系統中活躍子類的權重來進行改變。信用度分配器32通過提高信用度分配速率，也就是在圖5中被描述為M > N的信用度分配加速(「CDA」)，來對非零信用度結餘做出反應。CDA方法將同一信用度循環中多個RR循環合成為通過該RR隊列的單個處理過程。這在任一單個寬帶類的信用度循環內實現，因此並不明確地涉及第二維調度。該方法需要RR輪轉循環開始和結束的了解，且計算
13CDA或每個RR輪轉循環開始處M的大小。在CDA循環中組合的RR輪轉循環數量一般是2 (M =2)。還可以了解的有價值的是，當信用度結餘38特別大時將M提高到4，M潛在地被設置為與信用度結餘38相比較的閾值。可選擇的實施例通過在當前信用度循環中分配每個子類全部的剩餘權重，從而將 RR循環的最大數量合成為單個過程，因此結束該WIRR信用度循環。還有另一實施例則計算RR輪轉循環中涉及的子類數量，且將加速設置為1+CB/ 「子類數量」，從而有效地清除了通過當前RR隊列的單個過程中的信用度結餘38。CDA方法允許在加速的RR輪轉循環中間時通過跳過機會使得信用度分配速率返回到常態。換句話說，如果M是2且信用度結餘38已返回到零，則只需給其他每個機會分配信用度，例如，MxNxO. 5 = N0繼續加速的測試是簡單的-只要信用度結餘大於M和剩餘加權i之間的最小值，則RR隊列的前端處子類i可被分配信用度。信用度分配加速(「CDA」)可由RR輪轉循環在任一優先級處執行。CDA在RR輪轉循環開始處觸發。RR輪轉循環開始處選擇的加速因子，M，應用於整個RR輪轉循環。應該避免為子類分配小於或等於1的調整權重，因為只有調整權重> 1的子類才能參與這種形式的加速。信用度循環中剩餘權重小於CDA指定信用度的子類只接收其剩餘權重(即， 加速機會丟失或部分丟失)。現在將注意從信用度分配器32轉移而轉向根據本發明原理構成的對方傳輸選擇器30。現有的反向信用度管理(「ICM」)調度器只包含只為帶正信用度的子類服務的一個傳輸隊列。子類根據例如輪轉次序被選擇來用於傳輸且排列在該傳輸隊列尾端。則該隊列前端處的子類被選擇來進行傳輸。圖10示出根據本發明原理構成的示例基本傳輸控制結構72。根據本發明的一個實施例，基本傳輸控制結構72包括三個單獨的傳輸控制隊列正隊列74、負隊列76和極負隊列78。合格傳輸的所有子類，例如含可用數據，存在於傳輸控制隊列中的一個。基於嚴格的優先系統，優先選擇器80選擇三個傳輸控制隊列中的一個來傳輸。換句話說，包含子類的最高優先傳輸控制隊列總是在較低優先傳輸控制隊列之前被選擇。在每個傳輸控制隊列內，以簡單的輪轉方式選擇子類，即，無權重。傳輸機會觸發相應的信用度分配機會。基於子類具有的信用度量，子類被分類成傳輸控制隊列。當子類的信用度結餘改變時，子類在傳輸控制隊列間動態地移動。具有大於零的信用度計數的子類被置於正隊列 74中。如果不是用於系統的「信用度傾倒」方面，那麼當子類變成不合格時，期望的反應將是，只有來自正信用度隊列74的子類傳輸。因為本發明允許信用度傾倒(其中，信用度結餘大於N)，所以所有活動子類所持有的所有信用度總數可以是負數。具有負信用度計數的子類被置於負隊列76中。標準正傳輸隊列74和負傳輸信用度隊列76包含具有標準信用度計數的子類。正傳輸隊列74中的子類接收比傳輸稍多的信用度，而負傳輸隊列76中的子類接收比傳輸稍少的信用度。如果不合格不是信用度結餘38的觸發擾動，則從標準正傳輸隊列74處的傳輸是標準模式的操作。然而，直到子類的信用度計數可由信用度分配器32恢復時，許多子類將在傳輸之後保持在負傳輸隊列76。可預見的是，由所有活動子類持有的當前信用度總數可以是負數，因此一些具有負信用度計數的子類有時必須傳輸，進一步減少它們的信用度計數。然而，具有大量傳輸的子類，儘管是負數，可分離出來以減少瞬時不公平。因此，閾值，例如傳輸媒介的最大傳輸單元的負數，被設置用於將含低於閾值的負信用度結餘的子類置於極負隊列78中。從極負隊列78處的傳輸在可請求特別關注的信用度分配器32中提出極大剩餘信用度結餘38。極負隊列78防止子類螺旋下降到極低信用度結餘，除非所有子類都螺旋下降。從極負隊列78處的傳輸表明不良的信用度結餘38，這時該系統是不穩定的。可實施來使信用度結餘38免於附加增長的應急措施是降低傳輸信用度消耗率(例如，消耗用於傳輸的N/4個而不是N個信用度)。當一些數據以N消耗傳輸且其它數據以N/4消耗傳輸時，消耗傳輸數據的中斷可在加權公平算法中引入誤差，但是這是防止信用度結餘38無限增長的簡單實施。如圖11所示，附加實施例使用更先進的傳輸控制結構82。這個先進的傳輸控制結構82將上述討論的三個傳輸控制隊列與附加隊列結合，該附加隊列可選擇地用於更靈活的調度變化和全新的特徵。例如，傳輸控制結構82可將嚴格優先子類，如包含語音數據分組的子類，與通過最高優先支路控制隊列84的加權公平隊列子類結合。先進的傳輸控制結構82和上述討論的方法允許優先調度與最小消耗的加權公平隊列的結合。其它可選擇的傳輸控制隊列可包含極正隊列86和未知的子類隊列88。極正隊列 86可防止由於傳輸系統中的阻塞而產生的信用度計數中的突出部分，從而提高信用度結餘的穩定性。儘管極正隊列86是可選擇的，但是當不含優先傳輸的高加權子類可迅速設立信用度時，該隊列可起到期望的功能。大信用度存儲對系統穩定性來說是危險的，因為如果子類變得不合格，信用度就會突然地傾倒回信用度結餘38。如果任一子類具有大信用度計數， 則傳輸選擇器30應該查詢子類來確定該子類是否危險地達到了上信用度閾值。上信用度閾值可由系統設計員根據傳輸媒介的規範來設置，包含諸如當前業務流量這樣的參數。如果子類超出該上信用度閾值，則該子類應該被移至極正隊列86以接收優先服務。未知的子類隊列88容許這樣的可能性子類對未被當前調度器吸收(已知)的原調度器來說是已知的。如果當前調度器被選擇用於調度且不含其它合格子類，則該未知的子類隊列88提供需要的子類。參考圖12，提供了示例可操作流程圖，該圖描述了在選擇加權公平隊列子類期間由傳輸選擇器30執行的步驟。傳輸選擇器30確定該子類是否是新選擇(步驟S152)。如果不是，作為先前選擇，傳輸選擇器30繼續從與之前選擇相同的隊列和/或子類傳輸幀(步驟S154)。如果選擇是新選擇(步驟S152)，則傳輸選擇器30選擇含當前子類的最高優先傳輸隊列來用於退出隊列(步驟S156)，並且從傳輸隊列的前端選擇子類1用於傳輸(步驟 S158)。在子類已被選擇來用於傳輸後，傳輸選擇器30從子類i的總可用信用度(信用度 》中扣除掉傳輸的字節量(「N」)(步驟S160)。當傳輸選擇器30達到傳輸結束時(步驟 S162)，如果子類i不再是合格的(步驟S164)，則子類i從傳輸系統中移除(步驟S166)，即子類i對傳輸選擇器30不再是可見的。然而，如果子類^乃然合格(步驟S164)，則子類i 重新排列到適於子類i的信用度剩餘量的傳輸隊列的尾端(步驟S168)。現在參考圖13，提供了示例可操作流程圖，該圖描述了響應增加的信用度和合格轉換時由傳輸選擇器30執行的步驟。傳輸選擇器30確定子類i是否是新子類(步驟S170)， 意味著子類i當前不在傳輸選擇器排隊系統中。如果子類i不是新的且傳輸選擇器30確定子類i不再是合格的(步驟S172)，則如果子類i當前不傳輸數據(步驟S174)，則子類i從傳輸系統中移除(步驟S176)。否則，如果子類i當前傳輸(步驟S174)，則傳輸選擇器30現在不作出反應。該反應在將作為圖12中部分退出隊列處理時發生。回到判定框S172，如果子類i合格且信用度i表明子類已收到足夠的新信用度來改變優先級(步驟S178)，只要子類i當前不傳輸數據(步驟S180)，則子類i從當前傳輸隊列中移除(步驟S182)且被排列到信用度i量指示的傳輸隊列尾端(步驟S184)，即更高優先傳輸隊列。另外，回來參考判定框S170，如果子類i是新子類，則傳輸選擇器30簡單地將子類 i排列到信用度i量指示的傳輸隊列尾端(步驟S184)。本發明可由硬體、軟體或軟硬體的組合來實現。任何類型的計算系統、或其它適於執行這裡描述的方法的設備都適於實現此處所描述的功能。硬體與軟體的一般組合可以是專用計算機系統，該系統具有一個或多個處理部件及存儲在存儲介質上的電腦程式，當程序被加載和執行時，該存儲介質可對計算機系統進行控制，從而執行這裡描述的方法。本發明也可嵌入電腦程式產品中，該產品包括所有實現這裡所描述方法的特徵，且當該電腦程式產品在計算系統加載時可以執行這些方法。存儲介質涉及任何非易失性存儲設備和易失性存儲器設備。本申請中的電腦程式或應用是指旨在使具有信息處理能力的系統直接或在進行以下任何一種或兩種處理後完成特定功能的，以任何一種語言、代碼或符號編寫的一組次序的任何表達形式A)轉換成另一種語言、代碼或符號；B)以不同材料形式再現。另外，值得注意的是，如果沒有相反的提及，所有附圖並不是按比例的。根據上述說明各種修改和變化是可能的且不偏移本發明的範圍和精神的，本發明的範圍和精神只由下面的權利需求限制。
權利要求
1.一種用於在通信網絡中調度傳輸數據的系統，該通信網絡具有多個子類，所述系統包括信用度分配器可操作來為合格子類和負信用度計數的子類中的至少一個分配信用度，每個信用度可被收回用於一些數據傳輸；用分配的信用度之比影響子類間的公平； 保存表示未分配的可用信用度總量的信用度結餘；和從所述信用度結餘中扣除分配的信用度；和與所述信用度分配器通信連接的傳輸選擇器，所述傳輸選擇器可操作來 選擇用於退出隊列的至少一個合格和允許的子類；所述合格和允許的子類的偏向選擇是具有正信用度的合格和允許的子類；和將信用度增加到與選擇用於退出隊列的數據量相對應的信用度結餘。
2.根據權利需求1所述的系統，進一步包括可操作來確定每個子類的合格狀態的合格更新器，其中基於不同於所述信用度分配器影響的與加權公平不同的準則，合格狀態表示子類是否合格用以傳輸數據，包括速率限制、連續分配限制和數據可用性中的至少一個。
3.根據權利需求1所述的系統，其中所述信用度分配器進一步可操作來一旦子類變成不允許和不合格的子類中的至少一個，則從先前合格和允許的子類中清除所有正信用度；和將所述清除的信用度增加到所述信用度結餘用於再分配。
4.根據權利需求1所述的系統，其中所述信用度分配器具有至少一個輪轉控制隊列， 所述輪轉控制隊列包含合格子類和正信用度計數子類中的至少一個子類的至少一個識別器，其中所述信用度分配器進一步可操作來在第一輪轉控制隊列中為子類交錯分配信用度； 在輪轉循環的第一輪轉控制隊列中為每個子類分配一個信用度； 重複輪轉循環直到每個子類被分配到與該子類的加權相對應的信用度量； 當該子類被分配與該子類的加權相對應的信用度量時，從所述第一輪轉控制隊列中移除每個子類；和響應為每個子類分配與該子類的權重相對應的信用度量，從而將所述子類返回到所述第一輪轉控制隊列中。
5.根據權利需求4所述的系統，其中所述信用度分配器具有第二維加權交錯調度器以提供多個輪轉控制隊列，每個輪轉控制隊列包含合格子類和正信用度計數子類中的至少一個子類的至少一個識別器，每個輪轉控制隊列表示寬帶類和加權類中的至少一個，且每個輪轉控制隊列接收復用，其中所述信用度分配器進一步可操作來交錯選擇用於信用度分配的輪轉控制隊列，其中每個輪轉控制隊列被選擇與其復用相對應的循環；選擇用於信用度分配的第一輪轉控制隊列；在第一輪轉控制隊列中為子類分配信用度，其中每個子類被分配與每個輪轉控制隊列循環分配給該子類的加權相對應的信用度量，且其中以循環的模式在子類間分配信用度； 以交錯的次序來選擇含剩餘循環的輪轉控制隊列，直到完成所有循環；和在所述選擇的輪轉控制隊列中輪流為識別的子類分配信用度。
6.根據權利需求1所述的系統，其中所述信用度分配器進一步可操作來 保存信用度分配和數據傳輸之間的結餘；以近似等於標準數據傳輸率的速率來分配信用度；和響應具有未完成的信用度結餘，從而提高分配信用度的速率。
7.根據權利需求6所述的系統，其中所述信用度結餘在開始輪轉循環之前是過剩的， 所述信用度分配器進一步可操作來通過在單循環中為每個子類分配多個信用度，從而提高通過將多個輪轉循環合成為一個輪轉循環來為合格子類分配信用度的速率；和其中過剩包括超出設置的閾值，超出比一個傳輸事件消耗的信用度量還多的信用度量，以及大於零中的一個。
8.根據權利需求1所述的系統，其中所述傳輸選擇器具有數個用於退出隊列的傳輸控制隊列，每個傳輸控制隊列包含合格子類的至少一個識別器，且每個傳輸控制隊列具有根據請求的信用度計數需求限定的優先級；和所述傳輸選擇器進一步可操作來將每個合格子類分派到數個傳輸控制隊列中的一個， 每個合格子類具有滿足其分派的傳輸控制隊列的信用度計數需求的信用度狀態。
9.根據權利需求8所述的系統，其中所述傳輸控制隊列包括正傳輸隊列、負傳輸隊列和極負傳輸隊列，其中正傳輸隊列和負傳輸隊列之間的第一信用度計數閾值等於零； 負傳輸隊列和極負傳輸隊列之間的第二信用度計數閾值等於所述通信網絡的最小傳輸單元的負數；具有比負傳輸隊列還高的優先級的正傳輸隊列；和具有比極負傳輸隊列還高的優先級的負傳輸隊列。
10.根據權利需求9所述的系統，其中所述傳輸控制隊列進一步包括極正傳輸隊列、支路隊列和未知子類隊列中的至少一個具有最高優先級的支路隊列，且其中所述支路隊列不會將信用度返回到信用度結餘； 具有比正傳輸隊列、負傳輸隊列和極負傳輸隊列還高的優先級的極正傳輸隊列；和包含具有未知信用度狀態的合格和允許的子類且具有最低優先級的未知子類隊列。
11.根據權利需求9所述的系統，其中所述傳輸選擇器進一步可操作來通過將信用度增加到與選擇用於退出隊列的一部分數據相對應的信用度結餘，從而減少在從極負傳輸隊列處傳輸數據時消耗的信用度。
12.一種用於在通信網絡中為子類分配信用度的方法，每個子類可收回用於一些數據傳輸，所述方法包括為合格和允許的子類和負信用度計數子類中的至少一個子類分配信用度； 保存表示未分配的可用信用度總量的信用度結餘；和從所述信用度結餘中扣除分配的信用度。
13.根據權利需求12所述的方法，進一步包括一旦子類變成不允許和不合格子類中的至少一個，則從先前合格和允許的子類中清除所有正信用度；和將所述清除的信用度增加到所述信用度結餘用於再分配。
14.根據權利需求12所述的方法，進一步包括實施具有多個輪轉控制隊列的二維加權交錯的循環調度器，每個輪轉控制隊列包含合格子類和正信用度計數子類中的至少一個子類的至少一個識別器，每個輪轉控制隊列表示寬帶類和加權類中的至少一個，且每個輪轉控制隊列接收復用；交錯選擇用於信用度分配的輪轉控制隊列，其中每個輪轉控制隊列被選擇與其復用相對應的循環；選擇用於信用度分配的第一輪轉控制隊列； 為在所述第一輪轉控制隊列中識別的子類分配信用度； 輪流選擇含剩餘復用加權的輪轉控制隊列，直到完成所有循環；和輪流為在所述第一輪轉控制隊列中識別的子類分配信用度。
15.根據權利需求14所述的方法，其中根據每個子類的調整權重值，為在選擇的輪轉控制隊列中識別的子類分配信用度；和其中通過一組所有循環的每個子類的總權重值等於其調整的權重值乘以其循環隊列的復用。
16.根據權利需求12所述的方法，其中所述信用度結餘大於選擇用於信用度分配事件間退出隊列的數據量，所述方法進一步包括實施包含一個或多個子類的一個或多個輪轉控制隊列，所述子類用於在合格和允許的子類中的一個和負信用度結餘的子類間進行交錯信用度分配；和通過為通過輪轉控制隊列的全循環的每個子類分配多個信用度，從而將附加的信用度通過將多個循環合成為一個循環來分配給輪轉控制隊列中的子類。
17.一種用於在通信網絡中調度傳輸數據的方法，所述通信網絡具有多個子類，所述方法包括設立數個用於退出隊列的傳輸控制隊列，每個傳輸控制隊列能夠包含相對應的合格子類的至少一個識別器，且每個傳輸控制隊列具有根據相對應的信用度計數需求限定的優先級；將每個合格子類分派到數個傳輸控制隊列中的一個，每個合格子類具有滿足其分分派的傳輸控制隊列的信用度計數需求的信用度狀態；根據與該合格子類相對應的傳輸控制隊列的優先級來選擇至少一個用於退出隊列的合格子類；將信用度增加到與退出隊列的數據量相對應的信用度結餘；和其中每個合格和允許的子類以傳輸控制隊列表示。
18.根據權利需求17所述的方法，其中所述傳輸控制隊列包括正傳輸隊列、負傳輸隊列和極負傳輸隊列，其中正傳輸隊列和負傳輸隊列之間的第一信用度計數閾值等於零； 負傳輸隊列和極負傳輸隊列之間的第二信用度計數閾值等於所述通信網絡的最小傳輸單元的負數；具有比負傳輸隊列還高的優先級的正傳輸隊列；和具有比極負傳輸隊列還高的優先級的負傳輸隊列。
19.根據權利需求18所述的方法，其中所述傳輸控制隊列進一步包括極正傳輸隊列和支路隊列具有比正傳輸隊列、負傳輸隊列和極負傳輸隊列還高的優先級的極正傳輸隊列；和具有最高優先級的支路隊列且其中所述支路隊列處的傳輸並不將信用度返回到信用度結餘。
20.根據權利需求18所述的方法，其中所述傳輸控制隊列進一步包括未知子類隊列， 所述未知子類隊列包含在吸收當前調度器的信用度狀態之前由原調度器激活的合格子類。
全文摘要
用於在通信網絡中調度傳輸數據的系統，包括信用度分配器和傳輸選擇器。該通信網絡包括多個子類。該傳輸選擇器通信地連接到信用度分配器。該信用度分配器操作來為合格的子類和負信用度計數的子類中的至少一個分配信用度。每個信用度可收回，用於數據傳輸。信用度分配器進一步操作來用分配的信用度之比影響子類間的公平，保存表示未分配的可用信用度總量的信用度結餘，以及從該信用度結餘中扣除分配的信用度。傳輸選擇器操作來選擇用於退出隊列的至少一個合格和允許的子類，所述合格和允許的子類的偏向選擇是具有正信用度的合格和允許的子類，以及將信用度增加到與選擇用於退出隊列的數據量相對應的信用度結餘。
文檔編號H04L29/02GK102246462SQ200980150306
公開日2011年11月16日 申請日期2009年10月13日 優先權日2008年10月14日
發明者布拉德利·D.·維納布爾斯 申請人:北電網絡有限公司