實時網絡業務量準入與調度方法
2023-05-10 12:25:36 1
專利名稱：實時網絡業務量準入與調度方法
技術領域：
本發明涉及一種分組交換安排，特別是一種在選中範圍內確定分組間延遲的分組交換安排。
背景技術：
以前以最早到期日(EDD)調度器完成對實時流的調度。EDD調度器是為通過系統的分組提供延遲差異的機制。每個信道都有一個相關遲延邊界。通過將延遲邊界與到達時間相加，在特定時間抵達的特定類別的分組將被賦予最終期限標籤。然後，按照其最終期限標籤的升序轉發分組。這種安排的不足之處在於，具有較小延遲邊界的信道將趨向於壟斷輸出信道的空閒容量，獲得比具有較長延遲邊界的同等信道更大的平均傳輸帶寬。
本發明的目的是至少在一定程度上解決上述一個或多個問題，或者至少向公眾提供有用的備選方案。
發明內容
本發明的一種形式在於一種分組交換安排，其中包括第一裝置，適用於存儲每個輸入信道的選定最大分組間延遲；第二裝置，用於存儲與輸出信道上可用的比特率成正比的第一數值以及與每個輸入信道相關聯的多個第二數值，每個第二數值均與相應輸入信道上可能的最大分組大小成正比，同時與該相應輸入信道的選定最大比特率成反比；第三裝置，適用於選擇輸入信道，該輸入信道已獲準加入輸入信道組，這組信道中的任何一個均被允許通過輸出信道傳輸分組，如果最後被選信道的內涵物(inclusion)不會導致每個選中輸入信道的第二數值的總和進入或超出上述第一數值的選定範圍；第四裝置，用於從輸入信道組中選擇信道，用於通過上述輸出信道傳送分組，所述第四裝置還適用於僅選擇那些可以確保輸入信道所經歷的分組間延遲不大於該信道的選中最大分組間延遲的信道。
優選地，第一數值是信用值，等於任意輸入信道的最大可測算延遲與輸出信道的比特率相乘。
優選地，第二數值是信用值，其計算方法是將以比特為單位的選定輸入信道可允許的最大分組大小與任意輸入信道的最大可測算延遲相乘，然後除以該信道的選定最大分組間延遲。
優選地，選擇傳送分組的信道的裝置的特徵還在於在任何給定時間量子期間，已經被選中的輸入信道不會再次被選中，當存在另一具有要發送分組的輸入信道時，在所述時間量子期間，不選擇該信道。
優選地，選擇傳送分組的信道的裝置包括作為當前時間量子期間發送分組的候選的輸入信道的第一隊列和在下一時間量子之前不能作為發送分組的候選的輸入信道的第二隊列，在當前時間量子終止時，將被選擇為許可傳送分組的信道從第一隊列移動到第二隊列中，而將第二隊列中的所有信道移動到第一隊列中。
優選地，選擇傳送分組的信道的裝置還包括裝置，當其被移動到第一隊列中時，以與該信道的最大允許延遲成正比的數值，時間標記每個輸入信道；裝置，按照時標值，對隊列進行排序，指針能夠沿已排序隊列移動，選擇所指向的信道以允許通過輸出信道傳送分組。
優選地，所述時標等於當前時間加上該輸入信道的最大允許延遲值。
優選地，指針只能轉換時間標記顯示是處於當前狀態的信道。
本發明還在於一種分組交換方法，包括以下步驟存儲每個輸入信道的選定最大分組間延遲；計算與輸出信道上可用的比特率成正比的第一數值以及與每個輸入信道相關聯的多個第二數值，每個第二數值均與相應輸入信道上可能的最大分組大小成正比，同時與該相應輸入信道的選定最大比特率成反比；選擇輸入信道，該輸入信道已獲準加入輸入信道組，這組信道中的每一個均被允許通過輸出信道傳輸分組，當最後被選信道的內涵物(inclusion)不會導致每個選中輸入信道的第二數值的總和進入或超出上述第一數值的選定範圍；實現從輸入信道組中對信道的選擇，以便通過上述輸出信道傳送分組，實現僅對那些可以確保輸入信道所經歷的分組間延遲不大於該信道的選中最大分組間延遲的信道的選擇。
優選地，第一數值是信用值，等於任意輸入信道的最大可測算延遲與輸出信道的比特率相乘。
優選地，第二數值是信用值，其計算方法是將以比特為單位的選定輸入信道可允許的最大分組大小與任意輸入信道的最大可測算延遲相乘，然後除以該信道的選定最大分組間延遲。
優選地，在任何給定時間量子期間，已經被選中的輸入信道不會再次被選中，當存在另一具有要發送分組的輸入信道時，在所述時間量子期間，不選擇該信道。
優選地，將作為當前時間量子期間發送分組的候選的輸入信道放入第一隊列和將在下一時間量子之前不能作為發送分組的候選的輸入信道放入第二隊列，在當前時間量子終止時，將被選擇為許可傳送分組的信道從第一隊列移動到第二隊列中，而將第二隊列中的所有信道移動到第一隊列中。
優選地，所述方法包括當其被移動到第一隊列中時，以與該信道的最大允許延遲成正比的數值，時間標記每個輸入信道；按照時標值，對隊列進行排序，利用能夠沿已排序隊列移動的指針，選擇所指向的信道以允許通過輸出信道傳送分組。
優選地，所述時標等於當前時間加上該輸入信道的最大允許延遲值。
優選地，指針只能轉換時間標記顯示是處於當前狀態的信道。
為了更好地理解本發明，現在，將參照附圖，對根據本發明的優選實施例進行更為全面的描述。然而，應當理解的是，特定的實施例只體現了本發明的一種形式。
圖1示出了此系統的方框圖。
圖2示出了此系統的初始狀態。時間是1000ms，系統中有5個信道有多個待傳送的分組。
圖3示出了1000ms時間量子後的系統。兩個在先前時間量子中發送了分組的信道根據其最大延遲重新調度它們的信道。
圖4示出了1003ms時間量子後，但完成信道重新調度之前的系統。
圖5示出了1003ms時間量子後，但開始1004ms時間量子前的系統。
具體實施例方式
輸入鏈路17攜帶有多條試圖訪問輸出鏈路18的信道。基於信用的系統(credit-based system)被用來決定是否允許某個信道進入系統，也就是說，賦予訪問輸出鏈路的權利。信用總數與最大可測延遲(可任意選擇)與系統輸出比特率的乘積相等。這個值由軟體模塊15計算並存儲。
每個信道都有一定數量的信用(credit)，由信道識別模塊13計算並存儲。信用數值等於以比特為單位的存儲在數組11中的該信道最大分組大小乘以最大可測延遲再除以存儲在數組10中的信道可承受的最大分組間延遲，將其存儲在數組12中。
這些數值將通過信道仲裁模塊14。當存儲在模塊15中的全部系統信用少於或等於所有信道的信用值時，系統可以滿足所有信道的要求。信道仲裁模塊存儲可接受信道的集合。
另外，給出被系統接受的輸入信道的現有集合，如果新信道的最大分組大小已知，那麼就能夠計算系統可以為新輸入信道提供的最大分組間延遲邊界。相反，如果指定新信道的最大分組間延遲，則可以容易地計算新信道的最大可允許分組大小。
調度模塊16選擇允許用來傳送分組的信道，以便確保滿足每個信道的分組間延遲要求，同時不會僅僅因為該要求，而給要求低延遲的信道額外的帶寬。下面，對該操作進行描述。
系統中存在兩個指針
T(103)-當前內核時間指針。具有當前內核時間值。由內核以離散時間量子的方式進行更新。
P(104)-信道處理指針。它指向下一個要進行處理的信道。它包含具有最早時標的信道的時標值。
實時信道被許可進入系統，同時以數值(T+信道最大延遲)進行時間標記，然後按照時標的升序插入隊列(108)中。因此，具有最大延遲為2ms的信道將以數值T+2ms進行時間標記。
根據下面將要加以討論的規則，P指向下一傳送信道。
P被設定為永遠指向具有最早時標的信道。維持兩個隊列調度隊列(108)，針對在當前時間量子期間，即在T值變化之前，適合被選擇的信道；以及等待隊列(105)。當被選擇發送分組時，這個信道就會被從調度隊列移出，放入等待隊列中。在T值變化之前，這一信道不會被再次重新調度。這確保了每個信道都能平等地工作，在想要發送更多信息分組時，其逐漸獲得比其他等價實時信道更低的優先級。
當檢測到T值的變化時，所有在隊列中的信道都會根據新的T值被重新調度。以這種方式，以前的T值變成了現在的，在上一個時間量子中未被選擇的傳送信道將會比之前被選擇的信道具有較小的時標。
有時，系統能夠發送調度隊列中的所有信道的分組，在這種情況下，所有信道將處於等待隊列。如果系統得到發送分組的另一請求，則系統應當以相關時標，將所有信道從等待隊列恢復到調度隊列中。
有時，由於負擔過重或者T值實際超過一個或多個信道的時標，系統可能無法對信道進行處理。這意味著調度器將無法滿足這些信道實時延遲要求的需要。在這種情況下，P值將會被重新調整，指向具有最小時間標記的信道，並且儘量達到T值。調度器將用具有最低時間標記的信道發送分組。然後，這些信道將會被轉入等待隊列，而其它信道得到處理。在下一次處理時，根據新的T值，「遲到」信道將被按照普通信道一樣被對待。有分組要傳送的信道不會得到更高的優先級，因為其以T+信道延遲得以插入，而得到的數值肯定會大於T值。因此，P值的出現將會使系統有機會首先調度「遲到」的信道。
在實時調度器會丟棄遲到分組的實施例中，系統將會跳過先前的步驟，丟棄遲到信道中的分組，然後立即根據新的T值，對其進行重新調度。
參照附圖，下列情況可能發生假設所有的分組正在以最大傳送單位或分組大小(MTU)進行傳輸，系統每毫秒可以傳送兩個MTU大小的分組。存在5個信道信道A的最大延遲邊界為2ms信道B的最大延遲邊界為2ms信道C的最大延遲邊界為4ms信道D的最大延遲邊界為4ms信道E的最大延遲邊界為4ms如圖2所示，信道D(106)和信道E(107)處於等待隊列(105)中。這意味著在1000ms時隙中有兩個分組已經被傳送了。由於系統每毫秒只能傳送兩個分組，時間進入1001ms。
在圖3中，信道D和E肯定會在時間順序表(207)中被置後。由於它們是4ms信道，而當前的時間T為1001ms(205)，它們進入了列表中的1005ms(209)部分。指針P(206)將會指向列表中下一個進行傳送的信道。列表中的兩個信道將被允許在1001ms時隙中傳送分組。這是信道A(201)和信道B(200)。
在圖4中，我們看到信道A(307)和信道B(308)已經傳送完它們的分組，正處於等待隊列中。
在圖5中，時間已經向前推進了1ms。信道A(401)和B(400)被重新排序在列表中，處理繼續。
在另一個實施例中(未示出)，延遲的較低邊界大於0，P值等於當前內核時間加上最小延遲邊界值。這一實施例在分組間延遲需要更大確定性的時候使用，用以減少抖動。P值將不會超過T值，也就是說，表示發送信道的指針永遠不會沿調度隊列移動超過其時標是當前時間的項。
權利要求
1.一種分組交換安排，其中包括第一裝置，適用於存儲每個輸入信道的選定最大分組間延遲；第二裝置，用於存儲與輸出信道上可用的比特率成正比的第一數值以及與每個輸入信道相關聯的多個第二數值，每個第二數值均與相應輸入信道上可能的最大分組大小成正比，同時與該相應輸入信道的選定最大比特率成反比；第三裝置，適用於選擇輸入信道，該輸入信道已獲準加入輸入信道組，這組信道中的任何一個均被允許通過輸出信道傳輸分組，如果最後被選信道的內涵物(inclusion)不會導致每個選中輸入信道的第二數值的總和進入或超出上述第一數值的選定範圍；第四裝置，用於從輸入信道組中選擇信道，用於通過上述輸出信道傳送分組，所述第四裝置還適用於僅選擇那些可以確保輸入信道所經歷的分組間延遲不大於該信道的選中最大分組間延遲的信道。
2.根據權利要求1所述的分組交換安排，其特徵在於第一數值是信用值，等於任意輸入信道的最大可測算延遲與輸出信道的比特率相乘。
3.根據上述任一權利要求所述的分組交換安排，其特徵在於第二數值是信用值，其計算方法是將以比特為單位的選定輸入信道可允許的最大分組大小與任意輸入信道的最大可測算延遲相乘，然後除以該信道的選定最大分組間延遲。
4.根據上述任一權利要求所述的分組交換安排，其特徵在於第四裝置的特徵還在於在任何給定時間量子期間，已經被選中的輸入信道不會再次被選中，當存在另一具有要發送分組的輸入信道時，在所述時間量子期間，不選擇該信道。
5.根據上述任一權利要求所述的分組交換安排，其特徵在於第四裝置包括作為當前時間量子期間發送分組的候選的輸入信道的第一隊列和在下一時間量子之前不能作為發送分組的候選的輸入信道的第二隊列，在當前時間量子終止時，將被選擇為許可傳送分組的信道從第一隊列移動到第二隊列中，而將第二隊列中的所有信道移動到第一隊列中。
6.根據權利要求5所述的分組交換安排，其特徵在於第四裝置還包括裝置，當其被移動到第一隊列中時，以與該信道的最大允許延遲成正比的數值，時間標記每個輸入信道；裝置，按照時標值，對隊列進行排序，指針能夠沿已排序隊列移動，選擇所指向的信道以允許通過輸出信道傳送分組。
7.根據權利要求6所述的分組交換安排，其特徵在於所述時標等於當前時間加上該輸入信道的最大允許延遲值。
8.根據權利要求6所述的分組交換安排，其特徵在於指針不會沿調度隊列移動超過其時標是當前時間的條目。
9.一種分組交換方法，包括以下步驟存儲每個輸入信道的選定最大分組間延遲；計算與輸出信道上可用的比特率成正比的第一數值以及與每個輸入信道相關聯的多個第二數值，每個第二數值均與相應輸入信道上可能的最大分組大小成正比，同時與該相應輸入信道的選定最大比特率成反比；選擇輸入信道，該輸入信道已獲準加入輸入信道組，這組信道中的每一個均被允許通過輸出信道傳輸分組，當最後被選信道的內涵物(inclusion)不會導致每個選中輸入信道的第二數值的總和進入或超出上述第一數值的選定範圍；實現從輸入信道組中對信道的選擇，以便通過上述輸出信道傳送分組，實現僅對那些可以確保輸入信道所經歷的分組間延遲不大於該信道的選中最大分組間延遲的信道的選擇。
10.根據權利要求9所述的分組交換方法，其特徵在於第一數值是信用值，等於任意輸入信道的最大可測算延遲與輸出信道的比特率相乘。
11.根據權利要求9或10所述的分組交換方法，其特徵在於第二數值是信用值，其計算方法是將以比特為單位的選定輸入信道可允許的最大分組大小與任意輸入信道的最大可測算延遲相乘，然後除以該信道的選定最大分組間延遲。
12.根據權利要求9、10或11所述的分組交換方法，其特徵還在於在任何給定時間量子期間，已經被選中的輸入信道不會再次被選中，當存在另一具有要發送分組的輸入信道時，在所述時間量子期間，不選擇該信道。
13.根據權利要求9、10、11或12所述的分組交換方法，其特徵在於將作為當前時間量子期間發送分組的候選的輸入信道放入第一隊列和將在下一時間量子之前不能作為發送分組的候選的輸入信道放入第二隊列，在當前時間量子終止時，將被選擇為許可傳送分組的信道從第一隊列移動到第二隊列中，而將第二隊列中的所有信道移動到第一隊列中。
14.根據權利要求13所述的分組交換方法，其特徵在於包括當其被移動到第一隊列中時，以與該信道的最大允許延遲成正比的數值，時間標記每個輸入信道；按照時標值，對隊列進行排序，利用能夠沿已排序隊列移動的指針，選擇所指向的信道以允許通過輸出信道傳送分組。
15.根據權利要求14所述的分組交換方法，其特徵在於所述時標等於當前時間加上該輸入信道的最大允許延遲值。
16.根據權利要求14所述的分組交換方法，其特徵在於指針不會沿調度隊列移動超過其時標是當前時間的條目。
全文摘要
公開了一種分組交換系統，包括一種用於確定具有分組間延遲要求的實時信道能否進入該系統的方法。也提供了一種用於根據這些分組間延遲要求，對信道進行調度以發送分組的方法和裝置。還公開了用於對分組設置選定抖動要求的變體。
文檔編號H04L12/56GK1618215SQ02827668
公開日2005年5月18日 申請日期2002年12月2日 優先權日2001年11月30日
發明者埃米爾·蒂勒, 奇·肯特·拉姆, 西蒙·喬利 申請人:進揚網績有限公司