用於帶優先級的分組網的方法和路由選擇器的製作方法

2023-09-23 07:12:15 4

專利名稱：用於帶優先級的分組網的方法和路由選擇器的製作方法
技術領域：
本發明與在為數據分組選擇路由時按優先級別對分組排序的方法和設備有關。


圖1示出了移動系統中本發明所涉及的一些部分。移動臺MS通過無線接口Um與基站收發信臺BTS通信。這些基站收發信臺受屬移動業務交換中心MSC管轄的基站控制器BSC控制。受一個基站控制器BSC控制的子系統，包括那些受這系統控制的基站收發信臺BTS，稱為基站子系統BSS。交換中心MSC與基站子系統BSS之間的接口稱為A接口。移動系統的在A接口的MSC那側的部分稱為網絡子系統NSS。基站控制器BSC與基站收發信臺BTS之間的接口稱為Abis接口。移動業務交換中心MSC連接入呼和出呼，執行與公眾電話交換網PSTN的交換機類似的功能。此外，MSC還執行只屬移動通信這類的功能，如在圖1中未單獨示出的網絡用戶寄存器配合下對用戶位置的管理之類。
數字移動通信系統中所用的傳統無線電連接是一種電路交換連接，也就是說分配給用戶的連接資源在整個呼叫期間一直是保留著的。通用分組無線業務GPRS是一種為諸如GSM系統那樣的數字移動通信系統設計的新業務。這種分組無線業務可參見ETSI規範TC-TR-GSM02．60和03．60。分組無線業務使得為移動臺MS的用戶提供有效利用無線電資源的分組型無線連接成為可能。對於分組交換連接，無線電資源只是在需發送語音或數據時才予保留。語音或數據集中在一些具有一定長度的分組內。在一個這樣的分組通過無線接口Um發送後，如果發送方當時還沒有新的分組需立即發送，那麼這個無線電資源就釋放給其他用戶使用。
圖1所示系統包括一個獨立的GPRS服務提供節點，即SGSN15，用來控制網絡側分組數據業務的運作。這種控制包括，例如，將移動臺接入和脫開系統，更新移動臺位置，以及為數據分組發送到正確目的地編選路由。在本申請中，「數據」廣義地表示任何在數字移動通信系統中傳送的信息，例如編碼成數字形式的語音、在計算機之間傳送的數據、傳真數據等。SGSN節點可以與基站收發信臺BTS、基站控制器BSC或移動業務交換中心MSC結合，也可以是獨立的。SGSN節點與基站控制器BSC之間的接口稱為Gb接口。
諸如控制信令和語音或其他數據的信息在分組網內以GPRS·幀發送。每個幀F包括一個幀頭1和一個數據部2。(此外，通過特別是無線接口發送的幀通常還有用來同步的不同比特模式，但幀的這種部分對於本發明來說是非本質的。)為了使系統可以知道是哪個移動臺發送了這個幀，幀頭1包括一個標識移動臺的標識符，例如是暫時性邏輯鏈路標識符TLLI。當一個移動臺在GPRS網內登記時，網就給這個移動臺一個TLLI標識符，在GPRS連接期間使用。一旦GPRS連接建立以後，這個TLLI標識符就能重新指配給其他移動臺使用。
在幀頭1中，有時還能使用一個網絡層服務接入點標識符NLSI和TLLI標識符，以指出移動臺所用的應用協議。
在分組無線網中，可以想像這樣一種情況一個用戶利用個人計算機PC通過分組網10、數據網11、路由器13和區域網LAN與另一個計算機14通信。一個長的數據傳輸或幾個短的連續的數據傳輸在計算機PC和14之間例如用網際網路FTP協議進行。同時，計算機PC的用戶或其他用戶發起一個交互式會話，例如用網際網路Telnet協議。如果每個交互式會話的這些分組必需在連接的各節點上等待這個長時間的數據傳輸結束，那麼在交互式會話中響應時間就會長得使這種業務不合實際要求。
網絡運營者通常規定了幾種不同的業務質量QoS，使得在較高業務質量情況下的傳播延遲(可能還有分組丟失概率)小於較低業務質量情況。在本發明中，與業務質量關聯的最重要參數是傳播延遲。運營者可以規定例如三種業務質量，而為每種業務質量規定了兩個傳播延遲TAVE和T95，其中前者(TAVE)為分組在運營者的網內的平均傳播延遲，而後者(T95)為所發送的分組中有95％的分組的延遲都不會超過的延遲。業務質量與傳播延遲之間的對應關係可以如以下表1所示。
表1業務質量與傳播延遲之間的典型對應關係業務質量　　TAVE(ms)　　　　T95(ms)1　　　　　400　　　　　　6002　　　　　500　　　　　　8003　　　　　600　　　　　　1200(顯然，這些值只是作為例示而已。業務質量可以多於三種，算術平均可以用中值代替，95％也可以用其他百分比代替。)網絡運營者的問題是業務量在每天的各段時間內變化相當大，而且是隨機的。業務量還呈現連續的，通常是顯著的增大。用戶一般要與運營者籤定有關業務質量和與業務質量相應的最大延遲的要求的合同。當業務量增大時(偶然或永久性地)，用戶所經受到的延遲就會超過按所述業務質量設定的最大值。這樣，用戶就會要求運營者必需部署更多的通信資源。隨著用戶數和業務量的增大，不斷會出現這種情況。對於運營者來說，最好是儘量充分利用現有的傳輸容量，從而可以推遲新的投入，以便以後利用這些資金獲得更新的技術。
本發明就是考慮到上述情況提出的。因此，本發明的目的是提供一種為分組進行路由選擇的方法和設備，使得運營者的網絡在運營者和用戶之間的合同遵從表1所示時提供最佳的傳輸容量。
本發明的目的是採用特徵如在各獨立權利要求中所述的方法來達到的，而從屬權利要求揭示了本發明的優選實施例。
本發明的基本思想是如果某個分組的傳播延遲已經超過最大傳播延遲T95，那麼這個分組就能不再以運營者會對所述分組履行自己職責那種方式加以保存。這種情況發生在路由器中的業務量超過了路由器的傳輸容量的時候。如果運營者試圖公平地對待所有用戶，等同地延遲所有分組，這就很可能導致運營者對大多數用戶都履行不了自己職責。情況可能會是例如只有總數的90％的分組能在時間少於延遲T95內發送。於是，幾乎所有用戶都會感到運營者沒有履行自己的職責。對於運營者(和大多數用戶)來說，較可取的是將那些可用資源以可滿足合同條件(即不超過傳播延遲)方式分配給一系列用戶和連接。在這種情況下，路由器首先將資源分配給那些仍然能在合同所規定的傳播延遲內發送的分組。按照一個實施例，路由器甚至可以捨棄一個不再能在商定的傳播延遲內發送的分組，從而使資源能更有效地分配給那些仍然能在商定的時間內發送的分組。捨棄的分組然後送至一個更高的協議層，使接收方請求發送方重發這些丟失的分組。
下面將結合附圖參照各優選實施例對本發明進行更詳細的說明。在這些附圖中圖1示出了一個移動通信系統中與本發明有關的各個部分；圖2為示出如何將各分組排入一個隊列的方框圖；以及圖3為例示本發明工作情況的流程圖。
參見圖1，分組網中的支持節點SGSN 15起著路由器的作用，將需通過基站系統BSC-BTS轉發給移動臺MS和與它連接的計算機PC的數據緩存入一個隊列。由於無線接口Um形成一個明顯的瓶頸，因此在SGSN節點15就形成一個隊列。現在參見圖2，在路由器15接收到分組F時，就確定了分組的優先級別。方框20例示了這種功能。一種簡單的方式是可以根據在用戶合同中規定的業務質量QoS直接確定優先級別。或者，用戶也可以根據連接和／或應用確定優先級別。用戶可以根據在幀F的幀頭1中發送的TLLI標識符加以標識。TLLI標識符標識了移動臺和SGSN節點之間的每個連接。應用可以TCP協議的埠編號清楚地加以標識。在圖2中，分組處理例示成為每個優先級指定一個隊列，作為例子在圖2中示出了總共有7個的隊列Q1-Q7。在本申請中，「隊列」意味著任何可以獲得與將各分組實際排入不同隊列相同的效果的排列情況。就使用存儲器而言，只保存一些與不同隊列中的各分組有關的指針可能是比較經濟的。一個隊列例如能以連結表的形式實現，表中所列的每個元都含有一個指向下一個和／或上一個元的指針。此外，分組到達路由器的分組特定時間也存儲在路由器內。
為每個優先級規定一個第一傳播延遲門限值T1和一個比T1高的第二門限值T2。第一門限值T1與平均傳播延遲TAVE關聯。類似，第二門限值T2與95％傳播延遲T95關聯。然而，除了路由器，其他地方，特別是在無線電路徑上，也要使分組延遲。但是，其他那些延遲通常基本上是不變的，因此可以從延遲TAVE和T95中減去以實驗估計的這些不變部分。如果所估計的在路由器外的延遲為T0，則T1=TAVE-T0，T2=T95-T0。
例如相應優先級的各分組的平均值，最好是移動平均，可以用作對分組傳播延遲的一種估計。傳播延遲的另一種估計例如是有關分組的實際延遲。
圖3例示了一種實現本發明的開創性思想的可能方法。所謂「分組齡期」、「老分組」和「新分組」都是與分組F在路由器內已等待的時間有關。就各分組來看，在步驟30，選擇某個優先級中最老的分組F。這例如可這樣實現為每個優先級指定各自的FIFO隊列，如圖2所示，將分組加到隊列的尾端而從隊列的始端取出。在步驟31，如果這個分組的齡期高於本優先級的第二門限值T2，就在下個步驟32捨棄所述分組F。在步驟33選擇下個優先級。如果在步驟31這個分組的齡期不高於T2，就進至步驟34，將這個分組的齡期與本優先級的第一門限值T1進行比較。如果步驟34的比較結果是所述分組F的齡期高於本優先級的第一門限值T1，就在步驟35至少發送本優先級中的一個分組。分組相繼發送直到這個分組中的最老的分組的齡期低於本優先級的第一門限值T1，然後再選擇下一個優先級。
上述優先級別可以是與在用戶合同中所規定的業務質量相同，也可以是在連接開始和／或期間根據具體連接要求商定。
業務質量可以在分組網上通過為每個分組配置一個指示業務質量的代碼來通知路由器。由於在GPRS規範中規定了四種業務質量，因此用兩個比特就可以加以標識。或者，也可以用一個獨立的指示業務質量改變的消息來發出有關一個新的業務質量的信號。這個消息發送給一個位於連接的某處的路由器，這個路由器就會將改變了的業務質量存入它的存儲器。
在每個分組都配有一個指示業務質量的代碼時，連接上的每個節點都可以作出有關優先級別的判決。優先級別很容易用一個2比特的標識符加以改變，而不需要另外發送一個指示業務質量的消息。各個分組的優先級別很容易改變，而不用首先發送例如一個提高優先級別的消息，再在發送分組後發送一個降低優先級別的消息。
在改變業務質量時發送一個獨立的指示這種改變的消息的情況下，就不必為每個分組設置一個指示業務質量的代碼。這樣做有另一個優點，計費比較簡單，因為作為計費標準的業務質量的改變是用一個獨立的消息通知的。
發給同一個移動臺的各個分組通常沒有在會話期間改變業務質量的機制，所以業務質量通常在用戶登記需要利用GPRS連接時規定。
作為代替在步驟34逐個確定分組的齡期的步驟，可以是從所述優先級發送預定數量的分組，當然這數量不超過本優級中的分組數。圖2中的參數Ki例示了從每個隊列一次發出的數據量。與現有技術的用單個隊列進行路由選擇相比，如果採用多個隊列Qi而參數Ki不變，業務質量將得到改善。如果參數Ki例如根據業務質量加以調整，使得從高優先級隊列一次發出的數據量大於從低優先級隊列一次發出的數據量，那麼業務質量可以得到進一步改善。隊列Q2例示了在這個隊列中除了量Ki的數據外尚有少量數據的情況。這樣，一次性地傳輸掉整個隊列Q2顯然可改善有關應用的操作，但又不對其他用戶和／或應用有多大損害。對於這種超過Ki的適當門限值例如為30至50％。相應，Q4例示了一個隊列只有少量數據的情況。如果在傳輸長隊列前先傳輸掉這樣的短隊列，就可以縮短平均等待時間。
類似，作為代替在步驟31和32逐個確定需要捨棄的那些分組的齡期的步驟，可以是從所述優先級捨棄同一連接中的所有分組，因為較高的網絡層的協議在任何情況下都是要重發這些分組的。
路由器通常用數字存儲器和處理器實現。為了實現本發明所提出的方法及其各種變型只需改變路由器中處理器的軟體即可。以上雖然是結合GPRS網中的節點舉例對按照本發明為分組進行路由選擇的情況作了說明，但對於熟悉本技術領域的人員來說顯然清楚類似的路由器可用於任何其他通信系統。因此本發明及其實施方式並不局限於以上所舉各例，所有按照本發明精神實現的種種變型都應屬於本發明專利保護範圍之內。
權利要求
1．一種為在分組網路由器內的各分組(F)選擇路由的方法，其特徵是所述方法包括下列步驟為這些分組(F)規定一些優先級，而對於每個優先級，規定一個第一傳播延遲門限值(T1)和一個高於第一門限值(T1)的第二傳播延遲門限值(T2)；從每個優先級中選擇最老的分組(F)；確定所述分組(F)的傳播延遲的估計(E)，如果該估計高於本優先級的第二門限值(T2)，就降低所述分組(F)的優先等級，再選擇下一個優先級；如果傳播延遲的估計(E)高於本優先級的第一門限值(T1)，就發送所述優先級的至少一個分組(F)，然後選擇下一個優先級。
2．一種如在權利要求1所述的方法，其特徵是在所述發送步驟中發送預定數量的分組(F)，然而不超過所述優先級所含有的分組數。
3．一種如在權利要求1中所述的方法，其特徵是在所述發送步驟中發送所述分組(F)直至傳播延遲的估計(E)小於所述優先級的第一門限值(T1)。
4．一種如在以上任何一項權利要求中所述的方法，其特徵是所述降低分組(F)的優先等級是通過捨棄所述分組來實現的。
5．一種如在以上任何一項權利要求中所述的方法，其特徵是所述優先級是根據相應連接的業務質量(QoS)確定的。
6．一種如在以上任何一項權利要求中所述的方法，其特徵是所述第一門限值(T1)是為優先級確定的平均傳播延遲(TAVE)減去所估計的在網絡其他部分分組的傳播延遲(T0)，而所述第二門限值(T2)是為優先級規定的大多數分組的延遲不得超過的傳播延遲(T95)減去所估計的在網絡其他部分分組的傳播延遲(T0)。
7．一種如在以上任何一項權利要求中所述的方法，其特徵是所述估計(E)用的是與所述分組(F)相應的優先級的各分組的傳播延遲的平均值，最好是移動平均值。
8．一種如在權利要求1至6中任何一項權利要求中所述的方法，其特徵是所述估計(E)用的是所述分組(F)的傳播延遲。
9．一種如在以上任何一項權利要求中所述的方法，其特徵是所述分組網是一個GPRS網，而所述路由器是所述GPRS網的SGSN和／或GGSN節點。
10．一種用於分組網的包括接收和發送分組(F)的裝置的路由器，其特徵是所述路由器還包括為每個分組(F)指定一個優先級使得每個優先級都相應有一個第一門限值(T1)和一個高於第一門限值(T1)的第二門限值(T2)的裝置(20)；從每個優先級中選擇最老的分組(F)和確定傳播延遲的估計(E)的裝置(30，36)；對傳播延遲的估計(E)高於相應優先級的第二門限值(T2)的情況作出響應降低所述分組(F)的優先級別和選擇下一個優先級的裝置(32，33)；以及配合發送裝置、對傳播延遲的估計(E)高於相應優先級第一門限值(T1)而低於相應優先級第二門限值(T2)的情況作出響應選擇至少一個分組的裝置(34，35)。
全文摘要
本發明提出了一種在為數據分組進行路由選擇時按優先級別安排分組的方法和設備。為各分組(F)規定一些優先級,而為每個優先級規定一個第一門限值(T1)和一個較高的第二門限值(T2)。結合每個分組,選擇給定優先級的最老的分組(F),如果這個分組老於本優先級的第二門限值(T2),就捨棄所述分組(F),而選擇下一個優先級。如果所述分組(F)老於本優先級的第一門限值(T1),就發送這個優先級的至少一個分組,直至這個優先級中最老的分組不老於本優先級的第一門限值(T1),再選擇下一個優先級。
文檔編號H04L12/56GK1205146SQ97191389
公開日1999年1月13日 申請日期1997年10月7日 優先權日1996年10月8日
發明者米科·奧爾科寧, 薩米·胡斯科 申請人:諾基亞電信公司