應用最後出現和滑動窗口技術確定最小和最大值的系統和方法

2023-05-09 04:39:31 4

專利名稱：應用最後出現和滑動窗口技術確定最小和最大值的系統和方法
技術領域：
本發明一般涉及計算系統和方法，尤其涉及一種利用一個最後出現表格和滑動窗口從一組抽樣參數值中獲得最小和最大值的系統和方法。本發明尤其適用於通過使用一種信元(cell)優先排序方案管理網絡信息傳輸的系統。
背景技術：
在需要對一組離散變量或參數值進行例行計算的許多系統中，有必要經常從這組參數值中計算最小和最大值。傳統的計算辦法是在存儲器中存儲所有這些參數值，分類這些參數值，然後從分類的參數值列表中得到最小和最大值。在新數據被不斷加入的系統中，這種傳統辦法就變得非常耗時，而且可能在存儲資源和計算開銷上成本太大。
在通信業界，例如，需要某些系統重複、且相對高速地執行最小和/或最大值確定。例如，有一種稱為異步傳輸模式(ATM)的特定通信技術，典型地使用多個轉換器或節點來促進源和目的端站點之間的信元快速傳輸。目前已開發了多種方案，用於區分將被一個特定節點接受的信元和將被該節點丟棄的信元。可能希望利用一種為每個信元分配優先標識符的分級(rating)方案優化節點接收的信元，以便優先標識符能指示該信元相對於該節點接收的其它信元的重要性。顯然，還希望在該節點實現一種信息採集策略，即開發一種高速、低開銷的最小和/或最大優先標識符確定程序。

發明內容
需要一種用於從一組數量隨時間而增多的值中確定最小和/或最大值的改進方案，而且需要一種要求的存儲空間和處理開銷都減小的方案。另外，還需要一種可在高速ATM交換中開發的方案。本發明滿足這些和其他需要。
本發明針對一種用於從多個抽樣參數值中確定最小和/或最大值的系統和方法。最後出現表格(TOLO-表)與滑動窗口或濾波器用來大大增強從落入滑動窗口內的多個抽樣參數值中確定最小和/或最大值的速度和效率。利用TOLO-表處理的抽樣參數值典型地為離散參數值，而且被限制到N個不同的可能值(例如，pi＝p1，p2，…，pN)。
TOLO-表典型地包括一個參數列，用於為每一個限定數量的離散參數值，例如整數或字母符號，存儲入口(entries)。TOLO-表還包括一個時間戳列，為存儲在參數列中定義的每個參數值相關的數據接收時間提供入口。或者，也可採用序號列，而不是時間戳列，用於存儲對應參數值出現或被接收的順序的序號輸入。每接收到一個參數值，與該參數值相關的時間戳或序號入口就刷新為當前時間或序號。最近或最後出現的一個特定參數值就能記錄在TOLO-表中。
可利用滑動窗口獲得在TOLO-表中維護的一組參數值的最小和/或最大值，滑動窗口的大小或持續時間可以調整。滑動窗口可基於時間或選擇的抽樣參數值數目確定。落入滑動窗口內的參數值被掃描以確定可應用參數值中的最小和/或最大值。TOLO-表還能夠精確地確定除了該最小和/或最大參數值，在滑動窗口內是否至少還出現一個特定參數值。
應用根據本發明原理的TOLO-表和滑動窗口確定最小和/或最大值的方法用途廣泛，尤其適用於ATM網絡應用。在ATM業務模型的一個實施例中，每個信元分配一個優先值，該優先值部分確定該信元相對於通過網絡發送的其他信元的重要性。網絡節點根據信元的優先級和該節點計算的門限優先級接受或丟棄一個新到達的信元。如果要求的話，網絡節點可通知信源該節點已計算的典型門限優先級，確定這個典型優先級的一種可能實現包括在一組計算的門限優先級中確定最高優先級。TOLO-表可用於確定這種信息。


通過閱讀下面的詳細描述以及參考附圖可更清楚本發明的其它方面和優點，其中圖1示意了根據本發明的一個實施例，利用TOLO-表和滑動窗口從一組參數值中確定最小和最大值的一種系統；圖2A-2B示意了一種滑動時間窗口，應用於一組抽樣參數值，以便確定在兩個不同時刻落入該窗口內的最小和/或最大值；圖3以流程圖形式示意了根據本發明的一個實施例，從一組參數值中確定最小和最大參數值的一般過程；圖4和圖5分別為示意從一組參數值中確定最小和最大參數值的可選過程的流程圖；圖6示意了根據本發明的一個實施例，在用戶/網絡接口和使用標稱比特率業務的網絡之間通信信元的一般過程的流程圖；圖7詳細示意了根據本發明的另一實施例，在用戶/網絡接口和使用標稱比特率業務的網絡之間發送信元的過程；圖8以流程圖形式示意了根據一個標稱比特率業務實施例，在網絡節點過濾信元的一般過程；圖9為根據標稱比特率業務在網絡節點過濾信元的一個系統實施例的方框圖；圖10為根據標稱比特率業務在網絡節點過濾信元的一個系統可選實施例的方框圖；圖11為示意一種實現NBR方法的ATM網絡實施例的方框圖；圖12示意了根據本發明的NBR業務的網絡負載狀態信元的一個實施例；圖13為在配置用於實現NBR方法的ATM網絡內一個代表性ATM節點的方框圖；圖14以流程圖形式示意了根據本發明的一種通用方法，藉此方法NBR狀態信元可用於為源端站點提供反饋以優化信元傳輸率；圖15-16描繪了對於4種特定的負載級別，作為優先級函數的平均信元丟失比Ploss的關係圖；圖17示意了比較恆定比特率連接與使用反饋源連接的仿真結果圖；以及圖18示意了來自每個反饋源作為時間函數的流量/容量。
具體實現方式在下面對各個實施例的描述中，參考構成本發明一個組成部分的附圖，而且在附圖中，是通過示意可實現本發明的各個實施例的方式示意的。應理解的是，也可使用其它實施例，而且可在不偏離本發明範圍的情況下對本發明進行各種結構和功能改進。
為解決各種類型和難度的技術問題，常需要從給定的一組離散參數值pi中確定最小和/或最大值。這些參數值典型地出自以固定或不定時間間隔t＝tj重複的某些測量或計算的結果，這種測量或計算結果又產生了一個抽樣參數值p＝p(t＝ti)，其中j＝0，1，2，…， 。在圖1中示意了一個用於從給定持續時間內的一組抽樣參數值中確定最小和最大值的系統實施例。
根據這個實施例，系統20產生參數值pi，其被傳送到系統20的輸出端21應理解的是，系統20通常代表任何能產生表示一個參數值或幅度的模擬或數位訊號的系統或設備。例如，系統20可為簡單溫度測量系統20，在系統20的輸出端21產生溫度值信號。進一步舉例，系統20還可表示一個通信系統或網絡，而在通信系統20的輸出端21提供的參數值pi可表示多種系統參數值中的一種。
系統20典型地不斷產生各種類型或大小的參數值pi。應理解的是，參數的索引可利用任何適當的系統和設備實現，而且具有各種格式。例如，一種適當系統可產生與索引格式p1，p2，p3，…，pN或p0，p1，p2，…，pN-1一致的參數值輸出數據，其中N表示不同或相同參數值的總數。參數值pi可以固定或不定時間間隔在系統20的輸出端21提供。傳送到系統20的輸出端21的參數值pi被計算單元22的輸入設備23接收。
計算單元22還包括緩衝區24，在緩衝區24內提供了一個TOLO-表。在一個實施例中，緩衝區24提供的TOLO-表包括一個參數表列26和一個時間戳列28。在另一實施例中，緩衝區24支持由參數表列26和序號列30定義的一個TOLO-表。計算單元22還包括一個滑動窗口單元32和控制器34。控制器34根據下面描述的方法協調緩衝區24和滑動窗口單元32的操作，以從落入滑動窗口單元32定義的一個滑動窗口內的參數表列26確定的抽樣參數值中確定最小和/或最大值。
在圖2A中示意了基於接收時間接收或排序的多個參數值pi。例如，參數值p5相關的接收時間或時間戳在時間上遲於參數值p6的。類似地，參數值p6相關的時間戳在時間上遲於參數值p3、p7、p1、p3和p8的時間戳。圖2所示的一組參數值中的最小或最大值可利用滑動窗口獲得，可調整滑動窗口以增加或減少落入滑動窗口範圍內的抽樣參數值的最大數量。滑動窗口可根據時間定義，如通過變量-t，或通過選擇一個抽樣數W定義。
圖2A-2B便於理解利用滑動窗口確定最小和最大值的基本概念。在圖2A中，滑動窗口36可根據時間定義，如典型地以秒為單位測量的時間-t，或通過抽樣數W定義，如5個抽樣。在時間t＝tj-1，滑動窗口36定義了一組抽樣參數值，包括參數值p1、p7、p3、p6和p5。根據與每個抽樣參數值相關的數值下標值，可看出，定義滑動窗口的該組參數值中最大參數值由MAX＝p7給出，而最小參數值由MIN＝p1給出。在下一時間點t1＝tj，如圖2B所示，滑動窗口36定義了一個時隙後一組不同於圖2A所示的參數值。落入圖2A所示的滑動窗口36內的抽樣參數值p1不再落入圖2B所示的滑動窗口36內。另外，有一個新接收的抽樣參數值p9落入圖2B所示的滑動窗口36內。利用圖2B所示位置的滑動窗口36在時刻t＝tj進行最小和最大值確定將產生變量MAX＝p9和MIN＝p3。隨著更多的抽樣參數值被接收，滑動窗口36可沿時間軸在任何方向繼續移動。
在存儲器設備中實現上述滑動窗口概念的最直接辦法為在存儲器中存儲最後W個抽樣，接著從總的W個抽樣中確定最小和最大抽樣值。這種確定可通過，例如首先分類這W個抽樣，接著選取最小和最大抽樣值作為所分類的抽樣表的兩個極值。當到達一個新抽樣時，最老的抽樣被丟棄，而且重複該分類和最小/最大值確定步驟。然而，當窗口的大小W很大時，就會出現問題。在這種情況下，需要大量的存儲空間存儲落入該窗口的大量抽樣，這導致存儲成本和實現難度增加。此外，分類和搜索大量抽樣所需的時間也將很長，這將使得處理時延令人無法接受。
根據本發明的原理操作的系統和方法在從一組抽樣參數值中確定最小和/或最大值時無需存儲、分類或處理大量的抽樣參數值。利用本發明的TOLO-表和滑動窗口方案能大大提高確定指定數量的抽樣參數值pI中最小和/或最大值的速度和效率。當抽樣參數值pi離散且限制到N個不同值(例如，pi＝p1，p2，…，pN)時，在此公開的方法尤為有利。因此，在處理期間存儲或緩衝抽樣參數值所需的存儲空間大為減小。
例如，系統的存儲器僅需要為緩衝N個參數值和相關數據分配存儲空間。可以理解的是，當滑動窗口36的大小W定義為包括大量的抽樣參數值，如W＝10,000個抽樣時，它可能採用例如8個可能值，傳統的實現方案將需要存儲器存儲所有10,000個抽樣參數值。而截然不同的是，根據本發明原理實現的TOLO-表只需存儲8個可能的參數值和少量的輔助數據。因此，TOLO-表方法僅需常規方案所需存儲空間的0.08％。
利用TOLO-表實現的處理效率的提高，部分歸因於只需存儲涉及N個離散抽樣參數值中每個參數值的有限信息。TOLO-表實現方案在一個實施例中僅需存儲，當N個抽樣參數值的每個參數值出入滑動窗口時的出現時間信息。作為實例，參考下面提供的表1，表1示意了一個TOLO-表，該表有一列包含所有可能的抽樣參數值pi，還有一個時間值ti列，對應一個給定的抽樣參數值pi的最後出現時間。
表1

表1所示的TOLO-表包括每個可能參數值pi的行入口，即，p＝p1，p2，…，pN。每接收到一個新的抽樣參數值pi，對應該新抽樣參數值pi的出現時間ti就刷新為當前時間tc。注意，如果使用基於時間的滑動窗口，時間戳ti可為真實時間。
根據本發明的另一實施例，以及如下表2所示，TOLO-表可定義為包括一個用於定義所有可能參數值pi的列，以及一個對應參數值被接收的時間順序的相關列，該列在此稱為序號。
表2

每接收到一個新參數值pi，對應該參數值的序號ni就刷新為當前序號ni。通過利用上面描繪的任意一種類型的TOLO-表(表示定義抽樣參數值排序的兩種不同方式)，可確定一個特定的離散參數值pi的最後出現時間tI、或最後出現序號ni。另外，上述的任意一種方案可用於確定是否接收到一個特定參數值，如通過再檢查TOLO-表內維護的對應該討論的特定參數值的時間戳或序號信息。
當希望確定滑動窗口內的最小或最大值時，掃描整個TOLO-表以確定哪個參數值pi落入當前定義的窗口內。接著可從這些參數值確定最小和最大值。因此，TOLO-表能準確地計算在滑動窗口內是否至少出現了一個參數值pi。這個信息足以確定該窗口內的最小和/或最大參數值。
在確定大量離散參數值pi的最小和/或最大參數值時實現的處理效率的大為提高是以執行複雜的統計計算為代價實現的，如計算平均值和中值是利用該方法無法得到的。然而，在要求快速確定最小和最大值以及要求減小存儲空間的系統和方法中，無法執行複雜的統計計算顯然不代表在很多應用中限制很大，因為這種複雜的計算經常都不需要。
現在參考圖3，圖3以流程圖形式示意了根據本發明的一個實施例，利用TOLO-表從一組離散參數中確定最小和最大值的實現。假定抽樣參數值是從一個外部源定期或不定期接收的。還假定已定義TOLO-表對參數值pi可採用的每個可能值都包括一個表入口。當接收到一個值為pi的新抽樣參數時，在步驟40，當前接收時間tc存儲於TOLO-表中，而且與保留用於該參數值pi的參數列入口相關。在系統工作期間這個過程重複出現，且抽樣參數值pi以固定或不定間隔接收。在處理期間的某個時刻，如在步驟44請求確定存儲於TOLO-表、且落入一個預定大小的滑動窗口內的參數的最小和/或最大值。在請求確定最小和最大值的時刻，如步驟46所示，計數器變量i設置為i＝0，而時間變量tc設為tc＝當前時間。在步驟48，變量MAX設為MAX＝p0(即，最小參數值)，而變量MIN設為MIN＝pN-1(即，最大參數值)。注意，在這個示例中，假定參數值的索引由pi給出，其中i＝0，1，2，…，N-1。
根據這個實施例的TOLO-表，滑動窗口的尺寸定義為-t，這可根據秒、分鐘或其它測量時間定義。典型地通過使用指針或其它已知掃描方式，典型地通過使用指針或其它已知的掃描方式，從步驟50開始掃描TOLO-表，以確定有其它哪個時間輸入ti落入與當前時間tc有關的滑動窗口內(即，窗口大小＝Sw＝tc--t)。如果在步驟50，與TOLO-表中第一參數值輸入p0相關的時間戳t0落入該窗口內(即，t0＞tc--t)，那麼，該參數值輸入的值p0與變量MIN相比較。如果p0確定為小於變量MIN，則變量MIN在步驟52設為MIN＝p0。如果發現p0大於變量MAX，則變量MAX在步驟54設為MAX＝p0。計數器變量i的值在步驟56接著設為i＝i+1＝1。
如果計數器變量i不大於或等於TOLO-表中參數值輸入總數(由變量N表示)，那麼對TOLO-表中的其餘參數值輸入重複步驟50-56。指針遞增遍歷了TOLO-表中的所有N個參數值輸入後，在步驟58被測試，在步驟60返回相應的最小和最大變量MIN和MAX。一旦在步驟44接收到執行該過程的另一請求，就重複執行圖3描繪的最小/最大值確定過程。應理解的是，執行最小/最大值確定過程可與考慮到達的新抽樣參數值pi的接收和存儲步驟40和42同時進行。
應理解的是，在此描述的TOLO-表方法無論如何不限制為確定最小和/或最大整數值的應用中。這個方法可處理任何類型的參數，只要這個參數有一個確定的可能離散值集合與之相關，而且可以排序。這種值可為，例如實數或字母符號。還應理解的是，TOLO-表方法不應限制為使用單個窗口或窗口尺寸固定的應用中。相反，這種方法可應用於幾個窗口同時工作以及具有不同尺寸或持續時間的窗口同時工作。此外，如同前面討論的，TOLO-表方法可用於確定在一個特定的滑動窗口內哪幾個參數值已被接收或沒有接收到。
為進一步示意本發明的各個方面，下面提供應用各種類型的TOLO-表的幾個實例。應理解的是，在此描述的示意性實施例僅提供用於示意，並不表示對本發明的範圍和精神的限制。
實例#1在第一個實例中，假定一個設備，如溫度計，測量某一參數，如房間的溫度T。還假定溫度計能測量的溫度精度在1F內，而且溫度僅在溫度值的最大範圍內變化，如在70F和75F之間變化。由此，可能的幾個溫度測量值被限制到一組6個離散溫度值(即，T＝70F 71F 72F 73F 74F和75F)。還可假定溫度是以某一不定時間間隔測量的，而且相對於起始時刻0秒，時間向前遞增。
下面提供的表3表示一個溫度數據表，包括一個測量時間列，顯示序號為i的測量時間ti，以及與該測量序號i相關的測量溫度值Ti。表3描繪了總共10個溫度測量值，假定這些溫度值是在起始時間t1＝0s和t10＝165s之間接收的。
表3

如果，例如定義滑動時間窗口的大小或持續時間為30s，我們希望利用表3的數據確定ti＝120s時的最小和最大溫度，那麼在時刻ti＝120s時對應的TOLO-表如下表4所示。
表4

上表4所示的TOLO-表包括6個離散溫度值Ti，以及對應的溫度值Ti的最後出現時刻ti。每測量或接收一個溫度測量值Ti，就標記接收時間ti對應TOLO表中這個溫度值。例如當時刻ti＝45s時，溫度測量值為Ti＝72F，那麼Ti＝72F的最後出現時間就從ti＝15s刷新為ti＝45s。當希望確定時刻ti＝120s時的最大和最小溫度時，可啟動圖3描繪的最小/最大值確定過程。下面提供的表5示出了作為迭代序號i的函數的參數值MIN和MAX。為示意清晰起見，上表4描繪的TOLO-表已結合到表5中。
表5


參考表5和圖3，當前時間變量tc設置為tc＝120s，而窗口大小-t設置為-t＝30s，這個大小包含了120s和90s之間範圍內的時間參數值，而且變量MAX和MIN分別設置為70F和75F。為TOLO-表中的每個溫度值Ti執行在從步驟50開始的循環過程內定義的過程步驟。考慮第一溫度參數值T0＝70F，對應的最後出現時間t0由NULL值給出。最後出現時間參數t0的NULL值指示溫度值T0＝70F從未出現，因此未出現在定義的滑動窗口內。由此計數器變量i在步驟58加1，而且在步驟50測試下一溫度參數值Ti＝71F。
若計數器變量i設置為i＝1，可看出溫度T1＝75F最後出現在t1＝94s，這就落入了滑動窗口內。由於在步驟52，參數值T1＝71F小於變量MIN＝75F，因此變量MIN設為MIN＝71F。由於變量MAX的當前值MAX＝70F小於71F，因此MAX值設為MAX＝71F。計數器變量i設為i＝2。由於在步驟58，i＝2不等於或大於N＝6，對下一溫度值T2＝72F重複步驟50。由於與溫度參數T2＝72F相關的時間戳t2＝45s不在該滑動窗口內，因此計數器變量i遞增為i＝3。可看出，T3＝73F的最後出現時間為t3＝101s，落入到滑動窗口內。由於73F大於變量MAX＝71F，因此變量MAX設為MAX＝73F。
由於73F不小於變量MIN＝71F，變量MIN值不改變。隨著序號i遞增到i＝4，可確定時間參數t4＝105s落入該滑動窗口內。由於74F大於變量MAX＝73F，變量MAX設為MAX＝74F，而且變量MIN不改變。計數器變量i接著遞增到i＝5。由於時間參數t5＝25s沒有落入滑動窗口內，溫度t5＝75F被忽略，而且計數器變量i遞增為i＝6。由於在步驟58測試到i＝6大於或等於N＝6，循環過程返回，並在步驟60返回變量MIN和MAX的值為MIN＝71F和MAX＝74F。
實例#2根據另一實施例，抽樣參數值的序號，而不是參數值的接收時間，可用於定義滑動窗口。在前面的實例#1中，滑動窗口基於時間定義(即-t＝30s)。在這個實例中，滑動窗口基於預選的抽樣參數值數確定，如2個抽樣。在上表2中曾討論過，參數值的序號表示參數值按時間順序被接收的次序或位置。由此，測量的溫度值現在由表5或6的第一列表示，表示基於接收次序的抽樣參數值序號。
前面參考圖3描述的最大/最小值確定過程通常可與下表6所示的TOLO-表一起應用，但判定一個特定溫度Ti是否落入滑動窗口內現在是依據抽樣參數值的序號，而不是參數值的時間戳。利用表6所示的TOLO-表，假定還想根據上表3提供的測量溫度值確定時刻t＝120s的最小和最大溫度值。
表6

參考表3，可看出在時刻t＝120s，最後抽樣溫度值的序號為i＝7。如果假定滑動窗口的大小為2個抽樣(即W＝2)，那麼可看出，序號為i＝6和i＝7的溫度值落入滑動窗口內。可通過首先分別設置變量MIN和MAX為75F和70F啟動圖3的一般過程。從上表6提供的TOLO-表中可看出，當i＝0、i＝1或i＝2時，沒有一個測量的溫度(即T0、T1和T2)落入滑動窗口內(即n＝6或n＝7)。接著，當計數器變量i設為i＝3與溫度T3＝73F相關，這個溫度值的最後出現落入窗口內，而且變量MIN和MAX均設為73F。
當變量i遞增為i＝4時，還出現溫度T4＝74F，因此變量MAX設為74F。最後，當i＝5時，最後出現的溫度值T5＝75F落入滑動窗口範圍外。一旦完成了最小/最大值確定過程，變量MIN＝73F和MAX＝74F返回作為最小和最大溫度值。注意，如果滑動窗口的大小在這個實例中設為W＝3個抽樣值，那麼最小和最大溫度值將與上面的實例#1獲得的值相同。
本領域的技術人員知道，上述利用TOLO-表和滑動窗口的最小/最大值確定方法用途廣泛，尤其適用于于高速應用中。在例如ATM網絡的網絡通信系統中，離散信元可具有一個相關優先值，這個優先值部分確定該信元相對於通過網絡發送的其它信元的重要性。例如，一個網絡節點常執行一種評估過程，藉此過程，新到達的信元典型地基於其相關的優先權或被接受或被丟棄。這種接受可基於，例如比較信元的優先級與該網絡節點計算的門限優先級。由於在大部分的信元優化方案中，信元優先值離散，而且有範圍限制，因此網絡節點可根據本發明的原理實現最大/最小確定過程，以確定在一組給定抽樣的門限優先級範圍內確定最小和/最大門限優先級。
為示意起見，下面描述的業務概念可視為簡單綜合媒體接入(SIMA)業務模型。SIMA業務模型結合了ATM的基本特性與在稱為標稱比特率(NBR)業務的新業務概念中定義的附加8個優先級。通常，NBR業務便於在不同連接中簡單和有效地劃分網絡容量，以及對使用這種連接的用戶收取費用。
為示意與利用SIMA業務模型實現的網絡相關的各種優點，下面簡要描述各種常規ATM業務模型。常規ATM業務結構典型地提供多種預定的服務質量類別，通常稱為業務類。每種業務類包括多個服務質量(QoS)參數，用於定義各個業務類的特徵。換句話說，一個指定的業務類以一個ATM性能參數子集規定的方式為ATM虛擬連接(VCC或VPC)提供性能。在下面參考的ATM論壇技術規範中定義的業務類包括，例如，恆定比特率(CBR)類，實時可變比特率(rt-VBR)類，非實時可變比特率(nrt-VBR)類，未定比特率(UBR)類，以及有用比特率(ABR)類。
恆定比特率業務類別用於支持在連接存在期間要求固定數量帶寬的實時應用。一種特定的服務質量被協商以提供CBR業務，其中QoS參數包括峰值信元率(PCR)、信元丟失率(CLR)、信元傳輸時延(CTD)以及信元時延變化(CDV)的特徵。傳統的ATM業務管理方案確保用戶約定的QoS得以維持，以支持例如實時應用，如電路仿真以及話音/視頻應用，這些應用嚴格限制時延變化。
非實時VBR業務類別用於支持非實時應用，其中產生的網絡業務量可具有頻繁數據突發的特徵。類似地，實時可變數據率業務類可用於支持「突髮型」網絡業務條件。Rt-VBR業務類與nrt-VBR業務類的不同之處在於，前者用於支持實時應用，如話音和視頻應用。實時和非實時VBR業務類都具有峰值信元率(PCR)、可支持信元率(SCR)以及最大突發大小(MBS)的特徵。
未定比特率(UBR)業務類常稱為「盡最大努力業務」，這是因為它不規定與業務有關的服務保證。因此，UBR業務類用於提供非實時應用，包括傳統的計算機通信應用，如文件傳輸和e-mail。
可用比特率(ABR)業務類提供用於通過使用反饋機制控制業務率為用戶分配可用帶寬。反饋機制允許信元傳輸率得以改變以控制或避免業務擁塞，以及更有效地利用可用帶寬。資源管理(RM)信元優先於數據信元的發送，其從源發送到目的地並返回源，以便為源提供業務信息。
儘管上述的當前ATM業務結構顯然至少在概念級上提供面臨通信業的許多問題的有利解決方案，但當前定義的ATM要求實現一種複雜的業務管理方案，以滿足在當前考慮的各種ATM技術規範和建議中明確表達的目標。為有效管理網絡中的業務流，常規ATM業務管理方案必需評估大量的業務條件指示，包括業務類別參數、業務參數、服務質量參數以及類似參數。在標題為B-ISDN中的業務控制和擁塞控制的ITU-T建議I.371中，以及在由ATM論壇技術協會出版的業務管理技術規範V4.0(af-tm-0056.000，1996年4月)中提供了這種參數和其它ATM業務管理考慮的部分列表，一種重要的網絡業務考慮為，在一個特定的虛擬連接中當前可用的帶寬大小。除了ABR業務類，現有的ATM業務類別不建議採用這種網絡負載信息。ABR業務類提供可用帶寬的動態分配以響應返回給用戶的網絡負載信息。
然而，ABR業務類別提供一種複雜的反饋信息設置，包括當前信元率、顯式速率、最小信元率、方向指示、擁塞指示以及其它指示。這種複雜分類增加了業務類別結構的難度。而且，定義用於ABR業務類別的反饋機制便於分配限制在定義的最小信元率和峰值信元率之間的帶寬。因此，信元率確保繼續存在，這就增加了業務管理方案的難度。此外，常規ATM業務類別，包括ABR業務類別，不提供確定網絡負載條件，以及根據這些網絡負載條件管理信元傳輸率的技術解決方案。
與這些常規ATM業務模型相反的是，SIMA業務模型提供一種概念上不難實現的網絡結構和方法。實現SIMA業務模型的網絡還在帶寬過載期間提供有效的網絡容量分集，同時為用戶提供難度最小和時延可忽略不計的網絡負載信息。包含SIMA業務模型基本模式的網絡無需執行許多傳統和沉重的業務管理功能，包括業務描述、服務質量參數、服務類別、連接接納控制(CAC)或使用參數控制(UPC)。
所有這些功能有效地被兩個自主單元執行的功能替代在用戶/網絡接口提供的測量單元，以及在網絡節點提供的信元日程設定和緩衝單元。SIMA業務概念從用戶的觀點來看簡單且好理解，因為沒有預定的業務或質量參數與每個連接相關，而且對使用連接的收費僅基於NBR值和連接持續時間。
典型的SIMA業務實現使用兩種主要的組成部分接入節點和核心網節點，它們具有截然不同的功能職責。例如，可以是用戶/網絡接口的接入節點，執行測量每個連接的業務量的任務，而在核心網節點，業務控制功能無需知道有關各個連接特性的任何事情。
SIMA業務模型的精巧簡化為基礎設施硬體和軟體的製造商提供了明顯的優勢。例如，ATM交換和交叉連接可利用單個信元日程設定和緩衝單元、交換結構以及路由功能建立。通過使用ATM虛擬路徑或IP交換技術，可減小路由任務的難度。另外，分組丟棄和優先反饋功能也可包含於信元日程設定和緩衝單元中，而不會給它們的自主性帶來負面影響。而且網絡節點的簡單實現可使得相對便宜、大容量的網絡設施成為可能。
較為複雜的SIMA業務設施單元涉及接入節點。這種接入節點典型地包括一個測量單元，用於實時測量每個連接的業務流，以及包括一個計算單元，用於確定分配給每個信元的優先權。這些附加特徵的實現難度應不大於在常規ATM網絡中實現UPC的難度。
本發明用於在此公開的NBR系統中提供優先反饋信息可能更為有利，以便信元供給單元能規範其信元傳輸速率(CTR)以及實現可接受的信元丟失概率。有關連接門限級別的某些信息被周期性刷新且反饋回信元發送單元。每個ATM節點計算一個典型的許可優先級，該優先級可被插入到信源使用的特殊狀態信元中以檢測該連接。
在本發明的一個實施例中，通過維持可能的最高優先權，而不超出虛擬連接節點接受的最壞情況下允許的優先權，這個反饋特徵被用於優化CTR。因此，本發明能提供優先級反饋(PLfb)，通知源端系統連接節點仍接受的典型優先級。
為提供優先級反饋，在連接的每個節點確定允許的優先級(Pla)。優先級反饋級PLfb記錄了從源到目的地的最壞情況Pla，它被存儲作為一個狀態信元欄位。本發明的一個實施例可用於有效地確定在該連接上當前接受的最低允許優先權值(即，最高允許優先「級別」PLfb)。
後續ATM節點比較該特殊狀態信元中的PLfb與在該節點接受(即，在該節點未被丟棄)的當前優先級Pla。如果該狀態信元包括的PLfb值大於該節點的當前允許優先級，那麼該狀態信元的PLfb被一個對應該節點Pla值的新的、較小值替代。連接目的地由此接收該連接的最小PLfb，它指示什麼是典型的最高優先級PL(對應最低優先權)，能成功穿過連接而不會丟棄信元。目的地單元接著發送這個網絡負載信息返回信源，這使得用戶能調整CTR以減小後續發出的數據信元在該連接節點被信元丟棄後丟失的可能性。
現在參考圖6，圖6示出了在用戶/網絡接口和網絡之間通過NBR業務連接傳輸信息的通用方法。首先用戶與網絡運營商協商或選擇(140)一個標稱比特率，這可在建立連接之前或連接建立時執行。在一個實施例中，用戶通知網絡運營商需要一個預期的NBR，且為用戶分配一個請求的連接帶寬。網絡運營商根據這個實施例，在建立或釋放NBR之前無需執行分析核心網節點中存在的當前網絡負載條件。在一個可選實施例中，網絡運營商在建立或釋放NBR之前執行確定網絡負載狀態的任務，儘管這個任務在支持NBR業務的適當大小的網絡中是不必執行的。
基於一個特定應用，用戶選擇(142)一個實時或非實時網絡連接。確定每個信元的優先級(PL)(指示該信元相對於其它信元的重要性或緊要性)的過程，涉及在UNI測量(144)所選擇的實時或非實時連接的實際或測量的比特率(MBR)。每個信元的優先級是在UNI利用MBR和NBR之比確定(146)的。
在UNI計算完畢每個信元的優先級後，這些信元被發送(148)到網絡，如到網絡的一個節點。一旦從UNI發送的信元到達，網絡節點執行信元過濾過程，由此節點確定是接受還是丟棄一個特定信元。信元過濾過程涉及確定(150)網絡節點的一個或多個緩衝區或存儲器的狀態以確定緩衝區或存儲器的佔用級別。節點根據該信元的優先級以及節點緩衝區的狀態接受或丟棄(152)一個信元。滿足節點所確定的過濾標準的信元被接受、緩衝以及最終以與該連接預期的服務質量一致的方式被發送(154)到該網絡另一節點或其它網絡。
圖7-8示意了一種根據NBR業務方法實施例的調度和緩衝信元的過程。現在參考圖7，用戶與網絡運營商建立(160)一個NBR。儘管不要求，但希望首先設置業務類別(162)為非實時(nrt)業務類別作為預設設置。基於一個特定應用，用戶可請求一個實時(rt)業務類別(164)，這可由用戶直接設置，或典型地通過用戶的申請或通信軟體設置。如果用戶請求一個實時連接，那麼從用戶的UNI發送的每個信元在信元信頭集合中將具有業務類別比特，指示該信元的有效負載包含實時信息(170)。注意，在基於NBR概念實現的網絡環境中，期望實時業務類別連接實質上能支持任何實時應用，而無需指定特定的信元傳輸時延(CTD)和信元時延變化(CDV)參數。由此，設置信元信頭的CTD和CDV比特為適當值以滿足連接實時業務請求的常規過程均可省略。
如果用戶不請求實時業務連接，預設的非實時業務類別條件仍有效。因此，每個信元信頭的rt/nrt業務類別比特設置用於指示該信元的有效負載包括非實時信息(166)。注意，在此公開的NBR業務不採用常規ATM業務管理方案使用的信元丟失優先(CLP)方案。因此，信元信頭中的CLP比特可用於區別實時和非實時有效負載。
在上述的實施例中，通過連接傳輸的每個信元被指定為實時信元或非實時信元，如通過適當地設置信元信頭的rt/nrt業務類別比特來指定。在一個可選實施例中，根據用戶的請求，一個連接可指定為實時或非實時連接，而且通過這種連接傳輸的信元不必各自分配一個實時或非實時狀態。對於一個給定連接的每個節點，例如，一旦一個信元到達該節點，則可執行表查詢過程，以確定該信元是與實時還是與非實時連接相關。因此，根據這個實施例，不必保留一個信元信頭比特用於區分實時和非實時信元。
以上述方式設置rt/nrt業務類別信頭比特後，測量(174)將在UNI和網絡之間傳輸的一個特定信元的實際比特率。由於事實上，實際的比特率隨著時間變化很大，UNI的測量單元利用求平均測量原理來確定實際或瞬時比特率MBRi。
一般來講，UNI通過在持續時間適合於該特定連接(例如實時或非實時連接)的一個測量周期內取該連接的實際或瞬時比特率的近似值，測量(174)一個信元(如信元i)的實際比特率。瞬時比特率MBRi可利用一種已知技術確定。
已確定(174)測量的第i個信元的比特率NBRi後。利用該測量比特率MBRi和標稱比特率NBR計算第i個信元的優先級。根據一個實施例，假定利用具有8個優先級的信元優化方案可將一個信元與其它信元區分開。為指示8個優先級中哪個優先級歸屬於一個特定信元，為此每個信元分配3個比特。
根據當前ATM技術規範，ATM信元指定為具有固定大小幀的傳輸單元，包括5位元組的信頭和48位元組的有效負載。應理解的是，為指定信元優先級必需在信元信頭分配3個比特，可請求使用當前定義的ATM信頭比特。舉例來說，可使用總共由4比特構成的當前一般流量控制(GFC)欄位。在這種情況下，可分配3個比特用於指定信元優先級，而另一比特可指定為rt/nrt業務類別比特。根據另一實施例，違背採用5位元組信頭的ATM技術規範，可分配其它信頭比特用於指示8個優先級中的一個級別和rt/nrt業務類別。
由此，其它信頭比特可重新定義以表示信元優先級和業務類別指示。或者，指定信元優先級和/或業務級別所要求的一個或多個比特可位於當前定義的ATM信元信頭外。需要對現有的ATM信元信頭定義作小的改動大大抵消了因應用NBR業務方案帶來的優勢，如大大減小了網絡和業務管理開銷和難度。
應理解的是，優先級數可小於8個或大於8個。舉例來說，如果假定為指示一個信元的優先級分配了4個信元信頭比特，那麼可定義多達24(即2n-bits)或16個優先級。在NBR業務環境中增加優先級數，使得網絡運營商在管理網絡業務時能更好地調整一個特定連接的帶寬。獲得這種更高的業務控制水平的代價是實現更大數量的優先級需要附加信元信頭比特。
優先級計算單元利用計算的MBRi值和NBR值確定(176)每個信元(如信元i)的優先級。根據一個實施例，並假定當第i個信元被發送到網絡時測量比特率為MBRi，那麼信元i的優先級(PIi)可利用下述公式計算x=4.5+1n(MBRi/NBR)1n(2)]]> 其中 表示x的整數部分。下面根據一個同時提供NBR和傳統ATM業務連接的實施例討論，優先級零PL＝0保留用於使用保證帶寬和服務質量的普通ATM業務的連接。因此，可修改上面的公式[1]，以在產生PL＝1和PL＝7之間範圍內的信元優先級，以便如果1＜x＜7， 表示x的整數部分。應理解的是，優先值的順序可不同於在此描述的方案，但不偏離本發明的範圍或精神。例如，可以定義，優先值「7」對應最高優先權，而優先值「0」對應最低優先權。
由上面的公式[1]應用可看出，如果一個連接佔用的網絡容量超過連接的協商NBR值，那麼信元i的優先級至少為4。還可看出，如果UNI的瞬時比特率小於協商的NBR值，那麼PL至多為4。根據這個實施例的優先級方案因此允許用2步調整一個連接使用的相對容量。從上面的公式[1]可看出，對於100kbit/s的NBR，MBR高於566kbit/s將導致PL為7，而MBR低於8.8kbit/s將導致PL為0。
在信元信頭中分配的3個優先級比特設置(178)用於從UNI傳輸的每個ATM信元。ATM信元接著被發送(180)到由信元信頭中提供的節點尋址信息識別的目標網絡節點j。
注意，如果用戶不滿意該連接的服務質量，用戶可在至少3個備用方案中選擇。首先，用戶可選擇保持平均比特率不改變，但減小業務過程的變化。第二，用戶可選擇減小平均比特率或增加標稱比特率。然而，增加NBR通常將導致速率較高的連接成本隨之增加。最後，用戶可重新選擇網絡運營商。
在圖8中以流程圖形式示意了一種根據本發明一個實施例，網絡節點處理包含從UNI接收的優先級信息的信元的通用方法。圖9示意了用於實現圖8所示方法的網絡節點各個組成部分的實施例。假定已在UNI中處理了一個信元(如信元i)，而且信元中包含以上述方式得到的優先級信息。
信元i從UNI傳輸到一個網絡節點並在該節點的濾波器188接被收。存儲管理器189檢查存儲器190的狀態(181)以確定存儲器190的佔用量。存儲管理器189根據存儲器190的佔用狀態確定(182)允許的優先級(PLa)。一般來說，存儲管理器189建立一個高允許優先權，當存儲器190的佔用級別很高時(即，幾乎沒有可用的存儲位置)，這個高優先權將轉換為低允許優先「級別」，例如PLa＝0或2。當存儲管理器189確定存儲器190有足夠容量接收新信元時，存儲管理器189建立一個低允許優先權，它將轉換為一個高允許優先「級別」，例如PLa＝6或7。本領域的技術人員知道，計算PLa也可基於未被佔用的緩衝空間，而不基於已佔用緩衝空間，這不會偏離本發明的精神。
如果信元i的優先級大於存儲管理器189確定(183)的允許優先級PLa，那麼濾波器188丟棄(184)信元i。如果另一方面，信元i的優先級等於或小於允許優先級PLa，則濾波器188接受(185)信元i。存儲管理器189協調信元i傳送(186)到存儲器190，並刷新連接存儲管理器189的一個索引表191，以便為新接受的信元i包含一個新索引表入口。在一個實施例中，索引表191在存儲器190中存儲接受的信元i的位置，而且存儲一個信元類型指示，指定信元i是實時信元還是非實時信元。因此，存儲器190可存儲實時和非實時信元。
通過給予實時信元比非實時信元更高的優先權，存儲管理器189協同索引表191管理信元從存儲器190傳送到其輸出端的操作。舉例來說，一旦確定在存儲器190中存儲了rt信元和nrt信元，存儲管理器189在向外發送任何nrt信元之前先傳送所有rt信元到存儲器190的輸出端。
根據圖10示意的另一實施例，存儲管理器189確定實時緩衝(rt-緩衝)193和非實時緩衝(nrt-緩衝)194的狀態。存儲管理器189以一種類似於前述的方式，根據rt-緩衝193和nrt-緩衝194的狀態確定濾波器188的允許優先級PLa。如果信元i的優先級大於允許優先級PLa，則濾波器188丟棄信元i。另一方面，如果信元i的優先級等於或小於允許優先級PLa，則濾波器188接受信元i。
根據另一實施例，網絡節點可應用一種緩衝過濾方案，這種方案基於信元分組，而不是基於單個信元執行過濾功能。舉例來說，上述的過濾過程可應用於每個分組的第一信元。如果第一信元被節點丟棄，那麼緊跟第一信元的該分組其它所有信元也將被丟棄。然而，如果一個分組的第一信元被接受，那麼屬於該分組的所有其它信元的優先權可增大，例如通過改變優先級從PL＝5到PL＝3實現。即使增加一個優先級，如從PL＝4增大為PL＝3，也認為是足以確保只有極少分組被部分發送。
信元類型檢測器192從濾波器188接收被接受的信元，信元i，並確定信元i是rt-信元還是nrt-信元。如前所述，信元i的信頭包括一個信頭比特，如CLP比特，指示信元i是rt-信元還是nrt-信元。信元類型檢測器192一旦確定了信元i的業務類型，就傳送信元i到rt-緩衝區193或nrt-緩衝區194。存儲管理器189以一種類似於圖8和圖9描述的方式，協調分別來自rt-緩衝區193和nrt-緩衝區194的rt-信元和nrt-信元的輸出，且給予rt-信元優先權。
根據本發明的另一實施例，為增強網絡擴展和業務控制，希望請求每個網絡用戶購買一個最大NBR。最大NBR值目的是基本上保持恆定。另外，希望請求每個用戶選擇一個適當的瞬時NBR，這個瞬時NBR應不大於所選擇的最大NBR。選擇一個適當的瞬時NBR通常涉及在價格和服務質量之間折衷平衡。用戶檢測的服務質量大部分取決於3個參數，即NBR、平均比特率以及業務變化量。儘管用戶可改變任何一個這些參數，網絡在啟動信元傳輸時需要了解的唯一信息是NBR和連接的業務類別(實時或非實時)。
根據本發明的另一實施例，SIMA業務模型用於提供NBR和傳統ATM業務連接。應理解的是，提供連接保證的傳統ATM業務可用於一定用途。然而，對於事實上所有實時和非實時應用，期待本發明的NBR業務提供的服務質量將滿足或超過用戶的期望。
提供NBR和傳統ATM業務的SIMA業務請求網絡運營商為每個常規ATM連接，或可能為每個虛擬路徑提供專門的UPC設備。利用傳統ATM業務連接發送的所有信元被指定最高優先權PL＝0和指定實時(rt)業務類別。根據這種方案，優先級零保留用於使用保證帶寬和服務質量的普通ATM業務的連接。因此，修改上面的優先權確定公式[1]以產生在PL＝1和PL＝7之間的信元優先級，以便如果1＜x＜7， 表示x的整數部分。注意，如果網絡運營商想標註過多信元為CLP＝1信元，那麼可標記這些信元一個較低優先級，例如PL＝6。
可能與傳統ATM不一致表現在，對於每個ATM信元需要3個比特用於確定信元優先權，或者，如果在信元信頭中使用當前信元丟失優先權CLP，則需2個比特。另外，需要1個比特用於區分實時和非實時連接。rt/nrt業務比特可以，但不要求包含於所有信元中。可以使用總共由4個比特構成的當前一般流量控制(GFC)欄位。在這種情況下，其中3個比特可分配用於指定信元優先級，而另一比特可指定為rt/nrt業務類別比特。
圖11示意了實現NBR方法的一個ATM網絡200實施例的方框圖。用於描述的示例性ATM網絡200被描繪為具有兩個中間ATM節點202和204的網絡。然而，本領域的技術人員知道，本發明同樣可在各種網絡結構中實現，如在從區域網(LAN)到諸如網際網路的全球擴散區域網絡(GAN)範圍內的網絡中使用的多點、星型、環型、環路、網狀網技術。
網絡200包括源端系統206，用於發送數字信息到目的端系統208。在這種網絡中發送的信息在通往目的時典型地通過各個網絡節點，如節點202和204。這些節點表示網絡數據通信單元，如路由器、交換器或復用器。連接端系統和節點的為電路連接，提供通過數字信息的工具。連接鏈路210，212和214表示用於從源端系統206發送到目的地208的數據連接，而連接鏈路216，218和220表示提供回程信息的連接。
圖11還示意了在實現NBR方法的ATM網絡200中的ATM信元流程。隨著數據通過ATM信元流沿連接210，212和214發送到目的端系統208，網絡負載信息可經由連接216，218和220返回源端系統206。NBR系統基於優先權工作，由此導致提供的NBR網絡負載信息為優先級信息。有關該節點當前允許優先級的信息提供給源端系統206，以提供狀態和允許優化信元傳輸率(CTR)。
在本發明的一個實施例中，網絡負載信息以從源端系統206周期性發出的特殊ATM狀態信元的形式提供給源端系統206。狀態信元在包含於連接的正常MBR計算的意義上為部分正常連接信元流，而且狀態信元優先級是以前面根據圖7描述的方式計算的。圖11示意了根據本發明，狀態信元在從源端系統206前進到目的端系統208時，在6個不同間隔看到的典型進程。分別在時刻t＝1到t＝6描繪狀態信元222a-f，其對應狀態信元穿過一個連接時的位置/時間關係。
現在參考圖12，圖12示出了根據本發明的網絡負載狀態信元250的一個實施例。ATM標準定義ATM信元為固定大小的信元，長53位元組，其中包含5位元組的信頭和48位元組的有效負載。狀態信元250在ATM標準信元後形成，包括5位元組的信頭252和48位元組的有效負載254。在狀態信元250的有效負載部分254內，有一對優先級反饋(PLfb)信元，標記為PLfb，f欄位256(前向優先級反饋)和PLfb，b欄位258(後向優先級反饋)，用於在狀態信元250分別從源傳輸到目的和從目的傳輸到源時存儲優先級信息。PLfb，f欄位256採集了當前從源到目的被接受的最低允許優先權值(即，最高允許優先「級別」，PLfb)識別的連接上的最壞情況PLa。在一個實施例中，源端系統206首先設置PLfb，f欄位256為最低優先級，對應優先級值「7」。
當每個節點接收到狀態信元250，就檢測連接輸出鏈路上的當前負載水平。一個特定節點上的負載條件標記為PLfb，n，這表示最高優先權，由此表示對ATM節點為最低允許優先級PLa。該節點上的當前負載條件PLfb，n與PLfb，f欄位256中可用的值相比較，在此PLfb，f欄位256反映在該連接的一個節點上識別的最低允許優先級PLa。若PLfb，n＜PLfb，f，則PLfb，f欄位256中的值減小，以反映識別到該連接上這個點的最低允許優先級，因此，這個值遞減以等於該節點的PLa值。若PLfb，n＞PLfb，f，該節點不改變PLfb，f欄位256中的值。
每個網絡節點基於信元信頭252中的識別信息檢測狀態信元250。在ATM信頭欄位中有一個3比特的有效負載類型(PT)欄位260用於區分攜帶用戶信息的信元有效負載與攜帶管理信息的信元有效負載。圖12中信頭252的PT欄位260用於區分狀態信元250和一個標準數據信元。在PT欄位260中任何希望的比特組合可用於識別狀態信元250。或者，在信頭250另一位置上的一個獨立比特可用於區分狀態信元250和一個標準數據信元。
目的端系統208接收到狀態信元250後，返回狀態信元250到源端系統，使其能檢測在PLfb，f欄位256中採集的值。在本發明的一個實施例中，PLfb，f欄位256中的值被置於如PLfb，b欄位258所示的後向優先級反饋欄位。這使得當狀態信元250從目的端系統208傳輸到源端系統206時，PLfn，f欄位256能以類似於源-目的狀態採集的方式採集優先級狀態信息。結果，目的端系統設置PLfb，f欄位256為最低優先權，對應優先級值「7」，而且狀態信元250被發送回網絡以返回源端系統206。在返程期間，PLfb，f欄位256將再次採集網絡負載狀態信息，這一次是用於從目的端系統208到源端系統206的採集。存儲在PLfb，b欄位258中的之前採集的負載信息將保持靜態，用於在源端系統206進行分析。
源端系統206的配置方式使得不能在預定的時間周期內接收狀態信元將導致信元傳輸率自動降低。這是基於假設一個狀態信元的丟失指示鑑於信元傳輸率太高，這個狀態信元被丟棄，因此信元傳輸率應降低。
在本發明的另一實施例中，可在有效負載254中提供幾對PLfb，f/PLfb，b欄位。這可提供給用戶關於各個參數(如各個時間周期)的網絡負載條件信息。例如，第一、第二和第三對PLfb，f/PLfb，b欄位可分別在最後100ms、10s和10min的期間內提供網絡負載條件。
現在參考圖11和下表7，描述計算前向優先級反饋PLfb，f256和後向優先級反饋PLfb，b258的一個實例。
表7

如圖11示意，分別在時刻t＝1到t＝6示出了狀態信元222a-f。上表7示意了PLfb，f256和PLfb，b258與時刻t＜1到t＝6在節點202和204的允許優先級PLa相比較。在時刻t＜1，PLfb，f被初始化最低優先權，從而具有預置的優先級值「7」。在時刻t＝1，狀態信元222a從源端系統206發送到ATM節點202，此刻PLfb，f值仍為「7」。由於節點202的PLa值為「5」，狀態信元222b內的PLfb，f256在時刻t＝2被減為值「5」，以反映該連接的當前最壞情況PLa值。節點204在時刻t＝3的PLa值為「6」，大於當前狀態的PLfb，f256，其值為「5」。因此，PLfb，f256在時刻t＝3保持不變，此時狀態信元222c返回ATM節點204。
在時刻t＝3和t＝4之間，PLfb，f256被置於後向優先級反饋欄位PLfb，b258。在時刻t＝4，狀態信元222d因此包括PLfb，b欄位258，其存儲值「5」，對應源-目的連接的最壞情況允許優先級。由於節點204的PLa值仍為「6」。狀態信元222e的PLfb，f256在時刻t＝5仍保持值「5」不變。然而，在t＝2和t＝3之間的某個時刻，節點202的PLa值從「5」變為「4」，使信元222f中的PLfb，f256也減小為值「4」。從表7可看出，PLfb，b258在返程期間(即t＝4到t＝6)仍保持靜態，以便可向源端系統206報告源-目的PLfb，f。
圖13為一個ATM節點300的方框圖，它代表配置用於NBR方法的ATM網絡200中任何一個節點202、204或附加節點。每個節點可具有來自其它節點或端站點的多個輸入，通常視為鏈路302。轉換器304接收包含復用信息流的每個鏈路302，並在輸入端和輸出端之間重組信息流，這在技術上是公知的。在圖13的實例中，轉換器304接收鏈路308上的信元306a，並在其輸出端提供信元306b。
ATM節點300確定(310)信元306b是標準數據信元還是配置用於NBR方法的狀態信元。在一個實施例中，這是通過比較一個已知值與在信頭252的有效負載類型(PT)欄位260中的一個有效負載類型值實現的。若信元306b不是NBR狀態信元，則為標準ATM信元，其被傳送到信元日程設定和緩衝電路312(一般在圖9和圖10描述)，電路312根據信元的優先級和當前緩衝佔用水平接受和丟棄信元。若信元306b為NBR狀態信元，則根據當前允許優先級PLa在信元306c中適當地設置(314)Pfb，f欄位256。
連接ATM節點300的每個鏈路的各個PLa值都存儲於存儲表316中。當PLa小於當前駐留在PLfb，f欄位256中的值時，PLfb，f欄位256被設置(314)為一個等效於表316中PLa值的值。否則，PLfb，f欄位256保持不變。不管PLfb，f欄位256是否被修改，狀態信元306d都提供給信元日程設定和緩衝電路312，以像任何標準ATM信元一樣被過濾和緩衝。信元在輸出鏈路318輸出節點300，在此示出的這個實例中的狀態信元306e經鏈路320返回節點300。在一個實施例中，信元調度和緩衝電路312提供用於節點的每個輸出端，以便每個信元調度和緩衝電路312與該節點的其它信元調度和緩衝電路(未示出)相互獨立工作。
在圖14中以流程圖形式示意了根據本發明一個實施例的一種通用方法，藉此方法NBR狀態信元可用於為源端站點提供反饋以便能優化信元傳輸率。狀態信元從源端系統206被傳輸(400)到端目的系統208。中間節點，如圖11中的節點202和204，檢測(402)在源端由用戶發送的狀態信元。允許優先級PLa作為PLfb，n存儲(404)於每個中間節點。在當前節點前穿過的所有節點上識別的最高允許優先級可從狀態信元的PLfb，f欄位256中得到，它們可接著與每個節點的PLfb，n相比較(406)。若PLfb，n＞PLfb，f，節點不改變(408)PLfb，f欄位256中的值。若PLfb，n＜PLfb，f，PLfb，f欄位256中的值設置(410)為反映識別到連接中這個點的最低允許優先級，因此這個值減小以等於該節點的PLfb，n。
狀態信元在通往目的地的過程中可能經歷更多節點(412)。當有更多中間節點位於狀態信元的路徑上時，每個中間節點必須檢測(402)狀態信元，由此設置PLfb，f欄位256(404、406、408、410)。當從源到目的地不再有其它中間節點時，狀態信元以及當前負載指示PLfb返回(414)源端系統。在本發明的一個實施例中，在信元離開目的端系統208之前，PLfb，f欄位256中的值被置於後向優先級反饋欄位PLfb，b258。這使得在返回連接中能在PLfb，f欄位256採集到新網絡負載信息，而不破壞在源-目的連接中採集的網絡負載信息。
當源端系統206接收到返回的狀態信息時，能修正其當前業務參數以優化信元傳輸。當返回的狀態指示信元業務量相對低時(416)，用戶可降低新發出的ATM數據信元的優先權，以反映在該連接的每個節點將可能接受的優先級。類似地，當信元業務量顯然相對高時(420)，用戶可增大新發出的數據信元的優先權(422)。這使得能調整數據信元在沿連接的任何節點處不會被丟棄的置信(confidence)度。返回的狀態因此用於使用戶調整離開源端系統206到網絡的信元傳輸率(CTR)。
在下面的實例#3中，提供了一種根據本發明的原理，利用TOLO-表和滑動窗口技術確定轉換器的優先級反饋PLfb的實例。在這個示例中，最小PLa值被認為是接受的最低優先級PLa(即，最高優先權)，這指示確保在該周期接受信元所要求的門限優先級。此外，通過使用基於序號的滑動窗口的TOLO-表可獲得最小優先級值PLa。
實例#3假設信元以固定間隔到達ATM節點，而且8個離散優先級(即，整數0-7)表示有效的優先級值。還假設在這個實例中，每個優先級測量PLa分配一個序號i，而且在某個時刻tc，最近的抽樣優先級值PLa如下表8所示。進一步假設，在計算完抽樣i＝134的優先級後，ATM節點將確定最後10個抽樣的最小PLa值。表8

下表9提供的TOLO-表是通過刷新對應ATM節點已接收的PLa值的序號i維護的。
表9


在這個實例中，假設滑動窗口定義為大小為5個抽樣(即，W＝5)。因此，通過假設，圖4描繪的最小值確定過程是在已計算了優先級值PLa＝134後才啟動的，滑動窗口定義為包括抽樣130，131，132，133和134。通過首先設置變量MIN為MIN＝7啟動最小值確定過程。將計數器變量i設置為i＝0，可看出對應的優先級值由PLi＝0＝0給出。由於這個事件最後出現在滑動窗口外，變量MIN保持為MIN＝7。當計數器變量i遞增為i＝1時相同結果出現。當計數器變量i遞增為i＝2時，對應的優先級值由PLi＝2＝2給出，這出現在滑動窗口內(即，序號i＝132)。變量MIN接著設置為MIN＝2。
此時，如果使用的圖4描繪的一般過程，那麼最小值確定過程可以結束，因為之前就已發現優先級PLi＝0＝0和PLi＝1＝1落入滑動窗口外，而且其餘的優先級值必須大於當前MIN值。下表10列舉出了在執行最小值確定過程期間變量MIN的狀態。
表10

如果圖3描繪的通用方法用於評估所有8個PLa值，那麼將返回相同的最小值，即MIN＝2。注意，通過分別應用圖4和圖5描繪的實現，可獲得一種用於從一組抽樣參數值確定最小或最大值的更有效方案。應注意在實現圖4和圖5描繪的方法時，TOLO-表的組織結構假定為參數值的排序為pi＜pi+1。如果無法假定參數值這樣排列，那麼應掃描TOLO-表中的所有參數值。
在大小為W的滑動窗口內接受的最小優先級PLa值與每個信元中攜帶的PLfb，f值相比較。PLfb由此可根據下面的數學公式確定PLjh＝Min[(PLa)W] [2]其中，W表示依據抽樣參數值數的滑動窗口大小。注意，滑動窗口的大小W可設置為任何希望的值以提供變化的精度。
為示意起見，而不是限制，下面提供實例示意在不同優先級時NBR或SIMA連接的服務質量與流量之間的關係。下面的實例說明了根據本發明的一個實施例，相鄰優先級在QoS上的差異，如與PL＝4相關的QoS與PL＝3的QoS相比較。注意，對從其用戶/網絡接口發送的信元請求一個較高優先權的用戶典型地收取較高的費用。舉例來說，如果用戶想對每個信元得到高一級的優先權而不改變實際比特率，對該用戶的收費將加倍。因此所得到的連接服務質量應提高，以便至少某些用戶願意支付額外的費用。
實例#4根據這個示例，給定下面的假設和考慮。假設有多個相同的業務源，它們產生的業務量不受網絡中當前或之前的負載條件影響。下述的業務參數假定為鏈路容量為C＝1，這適用於歸一化的實例；峰值比特率MBRMAX＝0.1，這表示鏈路容量C的10％；在突發(或分組)的ON概率＝0.2；以及平均突發持續時間＝1,000時隙(即，平均分組大小＝100個信元)。另外，假設有一個ON/OFF上層，而且這個層的平均ON周期和OFF周期均為100,000個時隙。實時緩衝區93包含200個信元位置，而非實時緩衝區94包含5,000個信元位置。注意，ON/OFF上層試圖模擬連接的業務過程，其中確定連接數量在技術上理解為建立一個隨機過程。例如，如果假設用戶總數由變量x表示，那麼平均連接數為x/2。尤其是連接數可理解為二項式分配。因此，100,000個時隙表示一個連接的平均保持時間，還表示用戶可實現的平均空閒周期。結果，只有在連接層和分組層連接都有效，用戶才發送信元。可獲得時間比例參數，

用於實時和非實時連接αrt＝0.025αnrt＝0.001在這個實例中，假設了8種不同的連接類型其中4種為實時連接，另4種為非實時連接。而且，用鏈路容量C＝1標準化的4個不同NBR值假設為0.2，0.1，0.05和0.025。在MBRMAX＝.1時，對應這些NBR值的優先值分別為3，4，5和6。然而，應注意，不是所有信元都分配這些確切的優先級，而且尤其是通過非實時連接，由於求平均測量原理的作用許多信元能獲得更好的優先值。在下表11中提供了具有不同優先級的信元分配方式(以百分比表示)表11

在圖15中，示出了對於4種特定負載級r，作為優先級函數的平均信元丟失比Ploss的關係圖。特別地，線-800表示每種連接類型(即實時和非實時連接類型)中9個連接的總平均負載級別為0.72。線-802描繪了對於每種連接類型的10個連接，平均負載級別為0.80。此外，線-804表示對於每種連接類型的11個連接，平均負載級別為0.88，而線-806表示對於每種連接類型的12個連接，平均負載級別為0.96。注意，在線-802指示負載級別為0.80的情況下，實時和非實時信元的信元丟失比Ploss分別由點線和折線表示。
給定例如一種業務方案，運營商想為優先級4的信元提供10-6的信元丟失比，那麼總負載可近似為0.75。假設這個平均信元丟失比足以用於大部分視頻應用中。給定相同的業務負載條件，對應Ploss≈10-4的優先級5可滿足許多話音應用的要求，而對應Ploss≈3·10-3的優先級6，如果存在一個適當的分組丟棄方案，則適用於TCP/IP類型的文件傳輸。
然而應強調，相鄰優先級之間的信元丟失率差強烈地依賴於提供的業務過程，尤其是NBR或SIMA業務固有的控制環路。當用戶感覺服務質量不如意時，例如，用戶能夠而且應該改變連接的實際比特率或標稱比特率。在任意一種情況下，優先級的分配也將改變。然而，如果這種現象被暫時忽略，可進一步通過下面的簡化假設理解優先級分配的基本行為如果假設與測量周期和緩衝大小相比所有業務量改變很慢，那麼可採用一種眾所周知的、常規ATM方案來近似信元丟失率，但是還另外要求考慮8種NBR優先級。
如果優先級為k的信元丟失率由Ploss，k表示，而且優先級別0-k的信元平均丟失率由P*loss，k表示，那麼忽略緩衝效應的下述公式提供Ploss,k*=j;j>cPr{k*=j}(j-c)k*c]]>Ploss，0＝Ploss，0*Ploss,0=k*Ploss,k-k-1*Ploss,k-1*k*-k-1*for k=1...7----[3]]]>其中，λ*k表示優先級0-k的所有信元的瞬時比特率水平，ρ*k表示這些信元產生的平均負載，而c表示電路容量。概率Pr{λ*k＝λj}可利用已知的卷積技術直接計算出來。
實例#5為進一步示意，再列舉一個實例，假設採用實例#4描述的相同信源，但沒有長的ON和OFF周期。由於在實例#4中為長周期，峰值速率總是確定信元優先級。由於緩衝區典型地無法過濾任何業務量變化，在實例#5中允許的負載要比實例#4中的原始情況低得多。
在圖16中示意了對於不同負載級別r，作為優先級函數的信元丟失比之間的關係圖。假設在圖16中，由實現820,822,824描繪的每個連接的峰值信元率為0.1，由折線-826描繪的每個連接的峰值信元率為0.2，而由點線-828描繪的每個連接的峰值信元率為0.05。
圖16示出了應用公式[3]獲得的不同優先級的信元丟失概率，由3條實線820、822和824繪製。另外，由點線-828和折線-826分別表示兩種稍微不同的業務量情形。改變業務量變化的效果在圖16中被反映。業務量變化的實際改變為加倍或減半比特率和NBR值的直接結果。
在包含NBR/SIMA業務概念的網絡中，如果運營商保持QoS的優先級4不變，那麼增大業務量變化將有兩種主要效果。首先，允許的負載級別以如同常規ATM的方式減小；其次，相鄰優先級之間的信元丟失率上的差異減小。為基於圖15和16粗略估計QoS，可以假設，如果優先級4提供的信元丟失概率為10-6，那麼，信元丟失概率將近似為10-4-10-3，而優先級5依賴於總的業務量變化。可假設優先級為3的信元丟失比小於10-9，除非業務量變化相當顯著。
儘管上面的實例示意了QoS和優先級之間的關係，但試圖精確地確定相鄰優先級之間的允許負載或信元丟失差異還不成熟，除非能評估用戶對不同QoS和使用收費的反應。在NBR/SIMA業務環境中，可在一定意義上自動確定基於不同QoS級別的收費清單。例如，如果優先級4和5之間的信元丟失比差別很小，由於優先級5的收費較低，就可假設某些連接將從優先級4轉移到優先級5。這種變化顯然指示優先級4的信元丟失比降低，而優先級5的信元丟失比增大。因此，可合理地假設這種形式的轉移將繼續存在，直到QoS差別對應一般用戶期望的一種合理收費結構。
對於在忙時相對於閒時自動出現的收費差別也提出了類似考慮。例如，對於一定的QoS，在高負載期間收取較高費用，而在低負載期間收取較低費用就顯得合情合理。然而，希望避免採取一種對於一定的NBR在忙時和閒時收費不同的收費策略，這也可避免增加這種收費方案的難度。自然出現的「供求」影響可自動平衡忙時和閒時之間的負荷。希望如果用戶對忙時和閒時察覺到的QoS差別不滿意，那麼就可激勵用戶在忙時和閒時分別支付不同的費用。
實例#6另一種重要的傳輸控制形態是修正和調整信元傳輸率，或類似地修正和調整測量比特率(MBR)。有可能提供能改變其比特率、其相應連接上的當前負載條件信息的信源。這個實例提供了這些連接的性能概述。
在本例中，採用在前面的實例#4和#5中描述的信源產生的背景業務過程。還假設每種類型有10個連接，從而提供平均背景負載r＝0.080。還有3種信源(下文中稱為反饋源FBS1，FBS2和FBS3能根據經由網絡狀態信元接收的反饋信息調整傳輸速率。假設所有這些反饋源的NBR為0.01。
反饋源相互之間很相似，除了用於確定PLfb信息的時間周期不同。準確地說，反饋源FBS1的時間周期為10,000個時隙；FBS2為30,000個時隙，而FBS3為100,000個時隙。為比較反饋源，還討論3種固定比特率的連接(源連接C4，C5和C6)，它們具有下述參數(鏈路容量＝1)表12

表12中的信源設置使得信源的發送速率稍小於接近下一較高優先級的門限。例如，利用上面的公式[1]，比特率/NBR比等於1.5將導致信元優先級為5(5.08的整數部分)，而比特率/NBR比為1.4產生信元優先級4(4.98的整數部分)。在這個實例中，反饋源已設置為相同比特率值，目的是優化使用網絡容量。
在圖17中，示意了比較固定比特率連接與利用反饋源的連接的仿真結果圖。信元丟失比繪製在縱軸850上，作為繪製在橫軸852上的接受比特率/NBR的函數。該圖示意了當以較低的優先級值(即，以較高優先權)發送信元時，固定比特率源C4 854、C5 856和C6 858獲得更好的丟失與流量關係的特性。然而，結果指示，利用來自狀態信元的反饋信息調整速率的反饋源在背景業務量改變緩慢的情況下很有用。反饋源FB1870、FB2 872和FB3 874可適應各種變化，而固定比特率源無法利用網絡的負載變化。若背景業務量快速變化，反饋源無法適應過快的變化，導致信元丟失比增大。
圖17還示意了使用一種通常作為一種NBR＝0.01的TCP源876的信源。這種信源在接收到有關丟失信元的信息時，將其傳輸速率減半，如果在長達10,000個時隙的時間周期內沒有接收到有關丟失信元的信息，則將其傳輸率增加10％。比較顯式出，這種信源比相應的反饋源丟失更多的信元。希望這種信源對變化的反應減慢。
要考慮的另一方面涉及在容量突然改變的周期期間調整連接的能力，以及將如何管理不同反饋連接之間的容量劃分。現在參考圖18，來自每個信源的流量/容量(縱軸900)表示為時間(橫軸902)的函數。圖18提供了4個反饋源(FB1 904、FB2 906、FB3 908和FB4 910)發送信元到一個網絡節點的實例，其中FB1 904和FB2 906的NBR＝0.25，而FB3908和FB4 910的NBR＝0.0625。在對應30,000時隙的時刻，一個勻速(uniform)信源開始發送，如階躍函數912所示，且在NBR＝0.333時信元率PCR＝0.333。在對應60,000時隙的時刻，該信源終止發送信元。
從圖18可看出，反饋源(FB)能根據該連接上的負載階躍函數912調整傳輸率。當階躍源912開啟時，所有反饋源的流量降低大致相同。當階躍源關閉時，反饋源恢復其原始流量。
應當理解的是，可對上面討論的各個實施例進行各種改進和添加，而不偏離本發明的範圍。因此，本發明的範圍應不受上面討論的特定實施例的限制，而應僅由下面陳述的權利要求書和等效要求書定義。
權利要求
1.一種用於確定由一個系統產生的多個離散參數值中的最小值或最大值的方法，包括存儲一組代表該系統可產生的所有可能參數值的特有參數值；從該系統以固定或不定時間間隔接收參數值；存儲一個最後出現標識符，以響應該組特有參數值中的一個特定參數值等於一個接收的參數值；確定一個窗口的大小與最後出現標識符的範圍相關；以及確定該窗口內定義的被接收參數值的最小或最大值。
2.根據權利要求1的方法，其中最後出現標識符包括一個時間戳標識符，以表示該特定參數值被接收的時間，而且該窗口的大小定義為一個測量時間。
3.根據權利要求1的方法，其中最後出現標識符包括一個序號標識符，以表示該特定參數值被接收的次序，而且該窗口的大小根據最後出現的次序來定義。
4.根據權利要求1的方法，其中存儲最後出現標識符發生在從系統接收一個參數值之後。
5.根據權利要求1的方法，其中確定最小值或最大值與從系統接收參數值和存儲最後出現標識符同時發生。
6.根據權利要求1的方法，其中定義窗口包括根據預先定義的窗口大小修正該窗口大小。
7.根據權利要求1的方法，其中離散參數值包括任何整數、實數或字母值。
8.一種用於確定由一個系統產生的多個離散參數值中的最小值或最大值的裝置，包括一個存儲器，用於存儲一個代表該系統可產生的所有可能參數值的特有參數值表，以及存儲一個與每個特有參數值相關的最後出現標識符；一個輸入設備，用於從該系統以固定或不定時間間隔接收參數值；以及一個處理器，協調存儲最後出現標識符，以響應確定該輸入設備接收的參數值與該表格的相關特有參數值之間是否等同，並計算所接收參數值的最小值和最大值，該接收的參數值與在具有這樣大小的窗口內定義的最後出現標識符相關，即該窗口的大小與最後出現標識符的範圍相關。
9.根據權利要求8的裝置，其中處理器在輸入設備從該系統接收一個參數值後，協調存儲最後出現標識符。
10.根據權利要求8的裝置，其中處理器在從系統接收參數值和存儲最後出現標識符的同時，計算最小值或最大值。
11.根據權利要求8的裝置，其中處理器根據預先定義的窗口大小協調修正窗口大小，以響應一個修正指令。
12.一種用於為在源設備和目的設備之間定義的網絡連接獲取網絡負載信息的方法，包括為沿該網絡連接定義的網絡節點確定一個門限優先級，該門限優先級被網絡節點用作接受或丟棄通過該網絡連接接收的信元的基礎；存儲一個表格，該表格包含一個由該網絡節點認可的與每個門限優先級相關的最後出現入口；對於該網絡節點確定的相關門限優先級刷新最後出現入口；以及利用該表格的最後出現入口，在一個指定的持續時間內或一個指定數量的信元接收事件中，為該網絡節點計算最壞情況的門限優先級；從而，為該網絡節點指示最壞情況的門限優先級的信息被發送到源設備，而源設備對從源設備隨後輸出的信元調整信元優先級，以響應最壞情況的門限優先級信息。
13.根據權利要求12的方法，其中在該網絡節點存儲和刷新表格。
14.根據權利要求12的方法，其中計算最壞情況的門限優先級包括，計算在指定的持續時間內或指定數量的信元接收事件中確定的門限優先級中的最小門限優先級。
15.根據權利要求12的方法，其中計算最壞情況的門限優先級包括，計算在指定的持續時間內或指定數量的信元接收事件中確定的門限優先級中的最大門限優先級。
16.根據權利要求12的方法，其中計算最壞情況的門限優先級包括定義一個窗口，其大小對應指定的持續時間或指定數量的信元接收事件；以及從相關最後出現入口落入該窗口內的門限優先級中確定一個最低門限優先級。
17.根據權利要求12的方法，其中計算最壞情況的門限優先級包括定義一個窗口，其大小對應於指定的持續時間或指定數量的信元接收事件；以及從相關最後出現入口落入該窗口內的門限優先級中確定一個最高門限優先級。
18.一種用於為在源設備和目的設備之間定義的網絡連接獲取負載信息的裝置，包括一個存儲器，在沿該網絡連接定義的一個網絡節點處用於支持一個表格，該表格包含一個該網絡節點認可的與每個門限優先級相關的最後出現入口，門限優先級被該網絡節點用作接受或丟棄通過網絡連接接收的信元的基礎；以及一個在該網絡節點處設置的處理器，與存儲器相互作用為該網絡節點計算一個門限優先級，並刷新與計算的門限優先級相關的最後出現入口；該處理器利用該表格的最後出現入口為網絡節點，計算一個指定持續時間內或指定數量的信元接收事件中最壞情況的門限優先級；從而，為該網絡節點指示最壞情況的門限優先級的信息被結合到狀態信元中，而且源設備對從源設備隨後輸出的信元調整信元優先級，以響應結合到狀態信元中的最壞情況門限優先級信息。
19.根據權利要求18的裝置，其中處理器通過從指定的持續時間內或指定數量的信元接收事件中確定的門限優先級計算一個最小門限優先級，來計算最壞情況的門限優先級。
20.根據權利要求18的裝置，其中處理器通過從指定的持續時間內或指定數量的信元接收事件中確定的門限優先級計算一個最大門限優先級，來計算最壞情況的門限優先級。
21.根據權利要求18的裝置，其中處理器通過從相關最後出現入口落入大小對應指定的持續時間或指定數量的信元接收事件的窗口內的門限優先級中確定一個最小門限優先級，來計算最壞情況的門限優先級。
22.根據權利要求18的裝置，其中計算最壞情況的門限信元優先級包括，從相關最後出現入口落入大小對應指定的持續時間或指定數量的信元接收事件的窗口內的門限優先級中確定一個最大門限優先級。
全文摘要
一種利用最後出現表(TOLO－表)與滑動窗口或濾波器從多個抽樣參數值中確定最小和/或最大值,以大大提高在從落入該滑動窗口內的多個抽樣參數值中確定最小和/或最大值時的速度和效率的系統和方法。TOLO－表典型地包括一個參數列,用於存儲每個有限數量的離散參數值的入口,還包括一個時間戳列,為存儲在該參數列中定義的每個參數值相關的數據接收時間提供入口。
文檔編號G06F7/02GK1346461SQ99816513
公開日2002年4月24日 申請日期1999年3月24日 優先權日1999年3月24日
發明者朱西·路圖, 卡勒維·吉爾基 申請人:諾基亞網絡有限公司