吉比特無源光網絡嚴格優先級加權輪詢調度機制的製作方法
2023-10-26 07:04:57
專利名稱：吉比特無源光網絡嚴格優先級加權輪詢調度機制的製作方法
技術領域：
本發明一般地涉及用於信令伺服器的單級調度機制，並且更特別地涉及吉比特無源光網絡嚴格優先級加權輪詢調度機制。
背景技術：
目前，數據分組網絡需要調度以滿足服務質量的要求。用來適應優先級和加權兩者的調度機制目前需要多級調度以分開地考慮優先級和權重的每個級。調度難點在於不斷變化的指定優先級和權重的百分比。目前硬體的實現需要具有每個級為嚴格優先級或加權的多級調度機制。
因此，需要的是一種靈活的單級調度器。更特別地，需要的是一種軟體實現的嚴格優先級加權輪詢調度器，它可以提供單級調度機制，根據優先級、權重或優先級和權重的組合進行調度。基於同一目的地(由分配Id識別)的調度器的多輸出或邏輯分割是本發明所提供的主要靈活性。
發明內容
吉比特無源光網絡的業務量控制需要使用調度器來滿足服務質量的要求。一個數據分組可以具有一個邏輯輸出埠(分配Id)、一個相關的優先級、一個權重或優先級和權重這兩者。目前在硬體中確定一個適當的調度權重需要多級調度來分開地說明優先級和權重。本發明提供該機制以允許在單級調度器中要評估的權重和邏輯輸出埠、優先級的組合。
要調度和路由的數據分組進入一個隊列用於業務量控制。與該數據分組相關的且業務量控制所需的信息存儲在一個帶寬分配表(BAT)中。本發明的單級調度器利用來自帶寬分配表的信息來作出調度決定。與數據分組相關的帶寬分配表數據包括用來識別數據分組的索引、稱為分配Id的數據分組要路由到那裡的目的地址、優先級、初始權重、增量權重以及塊計數。
帶寬分配表的索引是用來標識數據分組的值。該索引可以與稱為埠Id的進入標識符相關。
帶寬分配表中的數據分組的目的地址是用來標識數據分組路由的值。目的地址稱為分配Id。同一目的地址可以用於多於一個的數據分組。如果多於一個的數據分組被路由到同一目的地址，則需要進行調度以控制業務量。
帶寬分配表中的數據分組的優先級是最高優先級0和最低優先級7之間的值。如果多於一個的數據分組具有同一目的地址，則應為向該目的地址路由的每個數據分組指定不同的優先級水平以允許調度。
如果多於一個的數據分組具有同一地址和同一優先級水平，則需要帶寬分配表中的數據分組的初始權重。在這種情況下，應為每個數據分組指定權重以允許調度。
在由隊列已接收到數據分組的幀尾之後，增加帶寬分配表中的數據分組的增量。
當由隊列已接收到數據分組的幀尾時，帶寬分配表中的數據分組的塊計數累計在隊列中已接收到的字節數。
由嚴格優先級加權輪詢調度器計算的數據分組的指定權重是數據分組的初始權重加上乘以塊計數後的增量。
數據分組傳輸的指定次序稱為隊列順序。首先基於嚴格優先級為要發送到共同目的地址的數據分組指定隊列順序，然後通過為具有同一優先級的數據分組指定權重來為要發送到共同目的地址的數據包指定隊列順序。
傳輸授予是對從隊列向目的地址分配ID傳輸數據分組的認可。
在一個實施方式中，用於嚴格優先級加權輪詢調度的方法包括選擇一組具有共同目的地址的帶寬分配表填充條目，每個填充條目與一個接收的數據分組相關，以及為所選組中每個帶寬分配表條目確定一個調度權重，該調度權重首先通過優先級確定並且然後通過指定權重來確定。
在一個實施方式中，用於嚴格優先級加權輪詢調度的方法包括接收一個數據分組，該數據分組包括目的地址、優先級和初始權重，構造與接收的數據分組相關的帶寬分配表條目，該帶寬分配表條目包括目的地址、優先級和初始權重，在接收到相關的數據分組後，以預定值增加帶寬分配表中的增量，對接收的數據分組中的字節數進行計數，將帶寬分配表中的塊計數設置為所計的相關的接收數據分組中的字節數，向相關的接收數據分組的帶寬分配表條目添加增量，向相關的接收數據分組的帶寬分配表條目添加塊計數，選擇一組具有共同目的地址的帶寬分配表填充條目，每個填充條目與接收的數據分組相關，通過將增量乘上塊計數並且將乘積加到相關的接收數據分組在帶寬分配表中的初始權重，來計算接收的數據分組的指定權重，其中在相關的接收數據分組的幀尾之後發生指定權重的計算，為所選組中每個帶寬分配表條目確定調度權重，該調度權重首先通過優先級確定並且然後通過指定權重來確定，如果發生溢出將具有相同目的地址和共同優先級的所選條目的指定權重重置為0，以及接受數據分組傳輸授予並傳輸具有最小調度權重的數據分組。
在另一個實施方式中，一種包括用於嚴格優先級加權輪詢調度機制的指令的計算機可讀介質，包括在接收到數據分組後以預定值增加帶寬分配表中的增量，對接收的數據分組中的字節數進行計數，將帶寬分配表中的塊計數設置為所計的相關的接收數據分組的字節數，通過將增量乘上塊計數並且將乘積加到相關的接收數據分組在帶寬分配表中的初始權重來計算接收的數據分組的指定權重，以及為所選組中每個帶寬分配表條目確定調度權重，該調度權重首先通過優先級確定並然後通過指定權重來確定，選擇一組具有共同目的地址的帶寬分配表填充條目，每個填充條目與接收的數據分組相關聯，其中，在接收到相關的接收數據分組的幀尾之後發生指定權重的計算，如果發生溢出將用於具有相同目的地址和共同優先級的所選條目的指定權重重置為零，接受數據分組傳輸授予並發送具有最小調度權重的數據分組。
在又一個實施方式中，嚴格優先級加權輪詢調度機制具有計算機可讀介質，該計算機可讀介質包括這樣的指令，用於在帶寬分配表中構造與接收的數據分組相關的條目，該條目具有索引、目的地址、優先級、初始權重、增量和塊計數，用於指定用於帶寬分配表條目的索引，用於確定帶寬分配表條目的優先級，用於分配帶寬分配表條目的初始權重，用於在接收到相關的數據分組後以預定值增加帶寬分配表條目的增量，以及將帶寬分配表條目的塊計數設置為相關的接收數據分組的字節數。
在又一個實施方式中，一種系統適於提供嚴格優先級加權輪詢調度，該系統包括存儲器和處理器，該存儲器具有其中從進入的埠標識符接收數據分組的隊列，該存儲器具有帶寬分配表，該帶寬分配表具有包括索引、目的地址、優先級、初始權重、增量和塊計數的條目，該條目與接收的數據分組相關，該處理器諸如是計算機處理器，可與存儲器中的隊列和帶寬分配表通信地連接，其中處理器選擇一組具有共同目的地址和優先級的帶寬分配表條目，其中在隊列中接收到數據分組後處理器以預定值增加帶寬分配表的增量，其中處理器對接收的數據分組中的字節數進行計數，其中處理器將帶寬分配表的塊計數設置為所計的接收數據分組中的字節數，其中處理器通過將增量乘上塊計數並且將乘積加到接收數據分組的初始權重來計算接收數據分組的指定權重，其中處理器為所選組中每個帶寬分配表條目確定調度權重，該調度權重首先通過優先級確定並然後通過指定權重來確定，其中在隊列中接收到相關的接收數據分組的幀尾後發生由所述處理器對所述指定權重的所述計算，其中如果發生溢出就將用於具有相同目的地址和共同優先級的所選條目的指定權重重置為零，其中處理器接受來自存儲器的隊列的數據分組傳輸授予並且其中處理器從存儲器的隊列傳輸具有最小調度權重的數據分組。
圖1描述了一個根據本發明的一個優選實施方式的第一嚴格優先級加權輪詢調度系統；圖2描述了一個根據本發明的一個優選實施方式的第二嚴格優先級加權輪詢調度系統；圖3描述了一個根據本發明的一個優選實施方式的帶寬分配表；圖4描述了一個根據本發明的一個優選實施方式的軟體流程塊；圖5描述了一個根據本發明的一個優選實施方式的第三嚴格優先級加權輪詢調度系統。
具體實施例方式
現在參照圖1，一種用於嚴格優先級加權輪詢(SPWRR)調度的方法藉助於一個本發明的系統10實現，該系統10包括多個將在下面進行描述的塊或模塊。這些塊或模塊為軟體、硬體、固件和/或軟體、硬體和/或固件的組合。要進行調度和路由的數據分組22、24和26進入一個隊列或SPWRR調度器12以便進行業務量控制。與數據分組相關並且是業務量控制所需要的信息存儲在一個帶寬分配表(BAT)14中。進入的數據分組從標為埠ID16、18和20的進入埠標識符到達隊列。這些數據分組具有優先級。SPWRR調度器12通過接口與BAT連接以便確定該數據分組的一個調度權重。一旦計算出調度權重，數據分組就依次被路由至標為分配ID28、30和32的目的地址。
現在參照圖2，圖2更詳細地描述了一個用於嚴格優先級加權輪詢(SPWRR)調度的系統40，該系統包括多個塊和模塊。這些塊或模塊為軟體、硬體、固件和/或軟體、硬體和/或固件的組合。當在隊列中或SPWRR調度器42接收到相關數據分組56、58、60、62和64的幀尾時，本發明將在帶寬分配表44中的增量加上預定數值。塊計數由在數據分組中的字節數構成，並且該值被加入到相關數據分組的BAT中。進入的數據分組具有一個初始權重。通過將增量和塊計數的乘積加入到初始權重，來計算相關數據分組的分配權重。
SPWRR調度器42首先依據優先級然後依據分配的權重，選擇一組具有共同目的地址的非空帶寬分配條目。具有一個共同目的地址分配ID和共同優先級的帶寬分配條目稱為一個加權輪詢(WRR)組66。如果出現溢出情形，則將分配給具有共同目的地址的非空帶寬分配條目，WRR組，的權重設置為0。
嚴格優先級加權輪詢機制可以根據優先級和應用的權重確定隊列順序。首先根據優先級選擇隊列順序，如果超過1個以上的條目具有同樣的優先級水平，則然後根據所分配的權重選擇隊列順序。接收到傳輸授予以後，掃描分配給同個目的地址(分配Id)72、78和80的表條目，並且根據優先級和分配的權重對隊列順序進行選擇。優先級和分配的權重允許對調度權重進行計算。同一個目的地址組內的最低調度權重值具有下次進行調度的最高優先級。當在進入埠標識符(埠Id)46、48、50、52和54上接收到數據分組時，對字節數進行計算並且匯總為塊計數。一旦在進入標識符中接收到的數據分組已經將幀尾發送出去，就通過將乘以塊計數的增量加到初始權重中，對所分配的權重進行更新。如果分配的權重導致溢出，則將所有分配到同一個目的地址的同樣優先級的條目的分配權重重置為0。如果該條目定義為嚴格優先極，則將增量設置為0。數據分組被路由到68、70、74和76以到合適的目的地址分配Id。
本發明的調度算法將在下面進行描述。優選地，該算法包含在計算機可讀介質中或軟體中，但也可以包含在固件中並且通過硬體實現。
該算法包括下述步驟1.等待分配Id_x的傳輸授予，並且進入到步驟2；2.選擇帶寬分配表條目；a.其已經填充，b.其分配Id等於分配Id_x，c.其具有最小優先級(在與a和b條件匹配的其它條目中)，3.如果發現條目則更新表面權重；a.更新表面權重＝初始權重+增量，b.如果出現溢出，則對選擇加權輪詢組中的所有條目的權重進行重新設置(具有相同分配id_x和相同優先級的條目)。
c.從隊列發送數據分組4.到步驟1現在參照圖3，塊和模塊為軟體、硬體、固件和/或軟體、硬體和/或固件的組合。帶寬分配表90包含確定隊列順序和數據分組路由所需要的信息。索引92是對隊列中的每個數據分組進行識別的值。每個隊列可以與進入埠標識符相關。
BAT中的每個條目與目的地址分配Id94相關。同樣的目的地址可以由一個以上的條目使用。任何時候當一個以上的條目被路由到同一個目的地址，應當利用優先級96或者分配的權重或者兩者都利用，以便確定數據分組之間的帶寬共享。如果沒有相關的目的地址分配Id94，則在條目中使用默認值255。
當一個以上的數據分組被路由到同一個目的地址時，應當對調度機制進行指定。如果使用了基於優先級的機制，則每個條目應當被分配給不同的優先級水平。如果一個以上的條目需要具有相同的優先級，則應當在同一個優先級中對每個條目的分配權重進行指定。最高的優先級水平指定為0，最低的優先級水平指定為7，而默認的優先級設置為0。
當一個以上的數據分組被路由到具有同樣優先級水平的同一個目的地址時，這個組的條目稱為加權輪詢組，並且使用嚴格優先級加權輪詢調度機制來確定調度。默認的初始權重值98由硬體設置為0。優選地，當硬體使用該值來表示權重值時，不對該值進行修改。分配的權重與具有同樣目的地址和同樣優先級的其它數據分組的分配權重相關。
當在隊列中接收到相關數據分組的幀尾時，帶寬分配表中的增量100增加一個預定值。塊計數102用來累計隊列已經接收到的塊的數量。塊單元表示隊列已經接收到的字節的具體數量。當隊列接收到幀尾時，塊計數和增量相乘並且其結果與初始權重相加，從而確定分配的權重。這個計算保證了隊列能夠對整個幀進行發送，因為分配的權重直到幀尾才進行更新。這個計算減少了在光線路終端上需要的碎片支持的數量，並且滿足了隊列的帶寬權重要求。因為增量和塊計數相乘，所以路由的數據分組的大小應當相應地依大小排列以便減少溢出的數量。
本發明的嚴格優先級輪詢調度機制包括計算機可讀介質，該計算機可讀介質包括用於構造與接收的數據分組相關的帶寬分配表90中的條目的指令。該條目包括索引92、目的地址(分配Id)94、優先級96、初始權重98、增量100和塊計數102。嚴格優先級加權輪詢調度機制包括指令，該指令用於指定帶寬分配表條目的索引、確定帶寬分配表條目的優先級、分配帶寬分配表條目的初始權重、當接收到相關數據分組時以預定值增加帶寬分配表條目的增量、以及將帶寬分配表條目的塊計數設置為相關的接收數據分組的字節數。
現在參照圖4，圖4描述了用於嚴格優先級加權輪詢調度的方法110。嚴格優先級加權輪詢調度器接收包括目的地址、優先級和初始權重的數據分組(112)。用包括目的地址、優先級和初始權重的條目構成BAT。接受數據分組的傳輸授予(114)，並且從具有共同目的地址的填充條目選擇出一組BAT(116)。當接收到相關數據分組時以預定值增加BAT中的增量(118)，並且對接收到的數據分組的字節數進行計數(120)。將BAT中的塊計數設置為所計的相關的接收數據分組的字節數，並且將增量添加到接收到的相關數據分組的BAT條目。將塊計數添加到相關的接收數據分組的帶寬分配表條目。
接下來，通過將增量乘上塊計數並且將該乘積加上所接收的相關數據分組在帶寬分配表中的初始權重，對接收到的數據分組的分配的權重進行計算(122)。當隊列中接收到相關數據分組的幀尾之後，對分配的權重進行計算。確定所選組中每個帶寬分配表條目的調度權重。該調度權重首先通過優先級確定，然後通過分配的權重確定(124)。如果發生溢出，則將所選擇的具有同樣目的地址和優先級的條目的分配權重重置為0(126)。接收數據分組的傳輸授予(114)並且傳輸具有最小調度權重的數據分組(128)。
現在參照圖5，本發明的SPWRR調度系統130包括多個塊或模塊，這些塊或模塊為軟體、硬體、固件和/或軟體、硬體和/或固件的組合。
存儲器134包含進入隊列136將要進行調度和路由以便進行業務量控制的一組數據分組。該存儲器包括從進入埠標識符接收數據分組的隊列，並進一步包括BAT 138，該BAT 138包括與數據分組相關的並且為業務量控制所需的信息，該信息存儲在BAT中。進入的數據分組從進入埠標識符埠Id140、142和144到達隊列。數據分組具有優先級。SPWRR調度器152用接口與BAT進行連接，以便確定數據分組的調度權重。一旦計算出調度權重，數據分組便被路由到目的地址分配ID146、148和150。
處理器132可通信地連接到BAT和隊列。該處理器處理SPWRR調度152的指令，以便對網絡中的數據分組的業務流進行路由和調度。
雖然本發明的系統的示意實施例已經在附圖中進行了說明，並且在前面的詳細描述中進行了描述，但是應當理解，本發明並不限於所披露的實施例，而是可以有許多的重新布置、修改和替換而不脫離由下面的權利要求書列出並限定的本發明的精神。例如，本發明的性能可以全部地和/或部分地由一個或多個管理處理器、現場伺服器或網絡伺服器模塊實現。同時，這些性能也可以在當前的方式或分布式方式下實現，或者通過能夠提供和/或接收調度信息的任何設備實現。另外，雖然本說明書中以一種具體的方式進行了描述，但是各種模塊或塊可以重新放置，而不脫離本發明的範圍。例如，由BAT和隊列實現的功能可以是它們自已所包含的功能。進一步而言，雖然本說明書中以一種具體的方式進行了描述，但是本發明可以使用更多或更少數量的隊列、調度器、BAT、進入埠標識符和目的地址。另外，可以使用更少或更多數量的數據分組並且為了實現本發明這種數據分組可以包括已知的補充信息，以便實現本發明，向本發明提供附加的已知特徵，並且/或使得本發明更加有效。
權利要求
1.一種用於嚴格優先級加權輪詢調度的方法，包括接收數據分組，該數據分組包括目的地址、優先級和初始權重；構造與所述接收的數據分組相關的帶寬分配表條目，所述帶寬分配表條目包括所述目的地址、所述優先級和所述初始權重；在接收到所述相關的數據分組時，以預定值增加所述帶寬分配表中的增量；對所述接收的數據分組中的字節數進行計數；將所述帶寬分配表中的塊計數設置為所計的所述相關的接收數據分組中的字節數；以及通過將所述增量乘上所述塊計數並且將該乘積加上所述相關的接收數據分組在所述帶寬分配表中的所述初始權重，計算所述接收的數據分組的指定權重，其中在接收到所述相關的接收數據分組的幀尾之後發生所述指定權重的計算。
2.根據權利要求1所述的方法，包括確定用於所選組中每個帶寬分配表條目的調度權重，所述調度權重首先通過所述優先級確定並然後通過指定權重來確定。
3.根據權利要求1所述的方法，包括如果發生溢出，就將用於具有相同目的地址和共同優先級的所選條目的所述指定權重重置為零。
4.根據權利要求1所述的方法，包括接受所述數據分組傳輸授予。
5.根據權利要求1所述的方法，包括傳輸具有最小調度權重的所述數據包。
6.一種適於提供嚴格優先級加權輪詢調度的系統，包括存儲器，其具有其中從引入的埠標識符接收數據分組的隊列，所述存儲器具有帶寬分配表，所述帶寬分配表具有包括索引、目的地址、優先級、初始權重、增量和塊計數的條目，所述條目與所述接收的數據分組相關；和處理器，可通信地連接到所述存儲器中的所述隊列和所述帶寬分配表，所述處理器適於選擇一組具有共同目的地址和優先級的帶寬分配表條目；在所述隊列中接收到所述數據分組時以預定值增加所述帶寬分配表的增量；對所述接收的數據分組中的字節數進行計數；將所述帶寬分配表的塊計數設置為所計的所述接收數據分組中的字節數；通過將所述增量乘上所述塊計數並且將所乘乘積加上所述接收數據分組的所述初始權重，來計算所述接收數據分組的指定權重；以及確定用於所選組中每個帶寬分配表條目的調度權重，所述調度權重首先通過優先級確定並然後通過所述指定權重來確定。
7.根據權利要求6所述的系統，其中在所述隊列中接收到所述相關的接收數據分組的幀尾時發生由所述處理器對所述指定權重的所述計算。
8.根據權利要求6所述的系統，其中如果發生溢出，所述處理器就將用於具有相同目的地址和共同優先級的所選條目的所述指定權重重置為零。
9.根據權利要求6所述的系統，其中所述處理器接受對從所述存儲器中的隊列傳輸所述數據分組的授予。
10.根據權利要求6所述的系統，其中所述處理器從所述存儲器中的隊列傳輸具有最小調度權重的所述數據包。
全文摘要
一種用於嚴格優先級加權輪詢調度的系統、方法和計算機可讀介質，包括選擇一組具有共同目的地址的帶寬分配表填充條目，每個填充條目與接收的數據分組相關，以及確定用於所選組中每個帶寬分配表條目的調度權重，該調度權重首先通過優先級確定並然後通過指定權重來確定。
文檔編號H04L12/56GK1773962SQ20051012017
公開日2006年5月17日 申請日期2005年11月10日 優先權日2004年11月10日
發明者梅默特·策基·克萊佐格盧, 戴維·格雷戈裡·埃克阿德 申請人:阿爾卡特公司