一種受約束排隊系統的調度方法

2023-06-14 19:03:21

專利名稱：：一種受約束排隊系統的調度方法
技術領域：
：網絡通訊系統與應用今日的Internet不但在規模上，而且在容量上都迅速增長。此外，近期有一個趨勢是將快速包交換機如ATM交換機作為新一代路由器的底層硬體。因此極需設計一種可滿足不同網絡環境的包交換機體系結構。採用該體系結構生產的包交換機可以部署在從接入網到骨幹網的不同位置。為達到此目的，採用的交換機體系結構必須要有很好的擴展性。交換機的擴展性主要決定於所用的排隊策略，即供排隊之用的緩衝區所處的位置及其組織機制。一般地，排隊方案可分為輸入端排隊、中央排隊、輸出端排隊或前者間之組合。在各種方案中，輸入端排隊具有最好的擴展性。然而，一個輸入端排隊之交換機達到高性能的關鍵是設計一個高效調度方法來調度排隊中的數據包從輸入端到輸出端間的傳送。本文給出(我們命名為)DSP的高效動態調度方法(在第5節中描述)。該方法可用來對在輸入端排隊交換機中的數據包進行調度。然而，該方法的應用並不僅僅局限於輸入端排隊交換機。其應用包括有線網和無線網、電子網和光纖網，等等。我們以下的討論從一個受約束排隊系統模型開始。一個NxM的受約束排隊系統有N個發送源和M個目的站。該受約束排隊系統中的時間被離散成以時間段為單位。到達該系統發送源的數據包(顧客)在他們被調度傳送到目的站以前將在發送源的緩衝區排隊。數據包僅在時間段的開始到達該系統的發送源。到達發送源後的數據包將在各個時間段內被DSP方法調度它們傳送到相應目的站的次序。依據此次序，各個數據包將在各時間段的結束被傳送到相應目的站。各個數據包的傳送時間以時間段為單位來衡量。如不加說明，每個數據包的傳送時間假設為一個時間段。每個數據包的傳送延遲定義為其到達相應發送源及目的站的時間間隔。再者，有限的互連網絡資源僅在以下限制被滿足的情況下可同時建立連接多個發送源及多個目的站間的路徑限制1任何時間，這些同時建立的路徑相互間沒有共同的發送源和目的站。在同一時間到達該受約束排隊系統的不同發送源的數據包有可能要被送到相同的目的站，其結果是造成對發送源和目的站的競爭。這些競爭必須用某種方法來解決。在競爭中獲勝的包將沿著建立的路徑被傳送到它們的目的站。而在競爭中失敗的包則進入緩衝區排隊，以候下次調度。用來組織排隊的機制及解決對發送源和目的站的競爭的方法是影響該受約束排隊系統的關鍵因素。解決對發送源和目的站的競爭是該受約束排隊系統所用調度方法的主要任務。具體地，每個隊列中的數據包以它們的目的站優先級來進行排隊。因此在每個隊列中排頭的數據包具有該隊列中所有數據包的最高目的站優先級。任何時間段裡，僅於各個隊列中排頭的數據包在滿足以下限制的情況下可被調度傳送到其目的站限制2在每個時間段裡，每個發送源最多可以傳出一個數據包。限制3在每個時間段裡，每個目的站最多可以接收一個數據包。詳細地，在每個時間段的開始，調度方法對各個隊列中排頭的數據包進行調度。然後在每個時間段的結束，被調度方法所選中的數據包將被傳送到它們的目的站。例子圖1給出的是一個3×3的受約束排隊系統。圖2給出了在一個受約束排隊系統中的調度及傳送操作的時序關係。與其它同領域中的方案一樣，我們假設每個發送源緩衝區中的數據包按它們的目的站來進行組隊。即是，要送到同一個目的站的數據包組成一條獨立的隊列。此組隊方式可有效解決困擾先進先出隊列的所謂隊頭堵塞問題。(在先進先出排隊方式中，每個發送源維持一條隊列來對所有到達該發送源的數據包提供緩衝。)調度方法根據排隊中的數據包狀態來進行調度。以上所述的受約束排隊系統是一系列網絡的抽象模型，例如，輸入端排隊的交換機、波分光纖網、無線網及等等。我們的命為DSP的創造性動態調度方法可以控制每個數據包的延遲。為達此目的，現存的研究已在輸入端排隊交換機的環境裡作了一些努力及設計了一些方法。不同方法間的區別主要在於如何從排隊中的數據包狀態來獲得所需的調度信息。與其它方法不同的是，我們的DSP方法是唯一的且是創造性的。主要表現在其所達到的高效、高性能、低複雜度以及易於物理實現。現階段已有多個對一種稱之虛擬輸出端排隊交換機的輸入端排隊交換機的調度方法[文獻1，3，4，6，7，8，9，10，11，12，13，14，15，16，17，18，19]。根據它們可否控制各個數據包通過交換機的延遲，這些現存的方法大體上可分為兩大類。一個NxM的虛擬輸出端排隊交換機實際上也是一個受約束排隊系統。在一個虛擬輸出端排隊交換機中，每個輸入端(亦即是發送源)有一個緩衝儲存區。該(物理)緩衝區由M個(邏輯)隊列組成。每個隊列對應一個輸出端(亦即是目的站)，即該隊列被單獨用來容納所有從該發送源到所對應的輸出端的數據包。該交換機的輸入端和輸出端間以一個交換網絡相連。調度方法的任務是在每個時間段裡根據所排隊數據包的狀態來控制交換網絡以建立傳送相應被選中數據包的路徑。大部分現存的方法都以提高交換機的吞吐量為目標，僅極少數幾個可以控制各個數據包通過該交換機的延遲。然而，這幾個方法都難以實現。在文獻中，每個時間段裡對排隊數據包的調度通常被描述成根據系統當前的負載矩陣來找出一個配對矩陣。負載矩陣及配對矩陣中的行和列分別對應被調度虛擬輸出端排隊交換機的輸入端和輸出端。負載矩陣的每個元素是一個二元式(Wi，Wo)，該二元式中的Wi和Wo分別代表對應隊頭數據包的優先級。不失一般性，一個為「0」的元素代表其所對應的隊列為空。如果Wi和Wo總是相等的，二元式(Wi，Wo)可用一個標量W來表示。根據一個負載矩陣所找出的配對矩陣由值為「0」或「1」的元素組成。每個配對矩陣滿足以下限制限制4每行或每列最多可有一個「1」。由配對矩陣中值為「1」的元素所構成的行和列間的一一映射可用以控制交換網絡來建立相應之路徑。顯然，據此建立之路徑滿足限制1。根據負載矩陣來找配對矩陣是圖論中的一個典型匹配問題[文獻2]。以所找出的配對矩陣依其性質可分為最大的、最優的或穩定的。在圖論中，各種匹配問題已被研究得相當透澈。對將之應用到虛擬輸出端排隊交換機而言，主要任務是如何定義各隊頭數據包的優先級。不同的定義可導致截然不同的方法複雜度和交換機性能。在已有的方法中，穩定配對方法具有最好的可調性以及對數據包通過該交換機的延遲進行控制的最強能力。但這些方法的複雜度很高，不能付諸實用。本發明給出了對一種受約束排隊系統的快速調度方法，即DSP方法。該方法創造性地動態計算在排隊顧客的發送源和目的站優先級，以達對該系統進行高速的配對調度。該調度方法可廣泛應用到實際的高效受約束排隊系統中，如用以實現高性能大規模的數據交換機或路由器。該受約束排隊系統可作為一系列通訊系統如交換機，無線網絡和波分光纖網絡等等的抽象模型。DSP調度方法設計可用於虛擬輸出端排隊交換機的調度方法是一個近期內急待解決的問題。不幸的是，現存的方法不但複雜而且難於實現，因而導致較差的交換機性能。本節給出可用於高速虛擬輸出端排隊交換機的DSP方法。該方法具有一般性，其應用並不僅僅局限於輸入端排隊交換機，還可用於包括有線網和無線網、電子網和光纖網等等的網絡。首先，我們列出一些用以簡明後隨論述的符號接著，我們的DSP方法給出如下第一步初始化；第二步將對應每個目的站的隊頭數據包按其目的站優先級來進行從高到低的排序第三步對每個目的站已排序的隊頭數據包的發送源優先級進行處理，以維持這些隊頭數據包間發送源優先級的非減性；第四步根據各隊頭數據包的狀態，找出一個發送源和目的站間的最大配對。(一個配對是最大的若且唯若任何未配對的發送源和目的站間沒有可供調度的數據包。)該最大配對滿足以下條件如果數據包Cij未被配對，則至少有一個被配對的數據包優先級比Cij高。該被配對的數據包或在發送源i，或要送到目的站j；第五步根據建立的配對，傳送相應的數據包到其目的站；第六步調整新隊頭數據包的優先級；第七步調整未配對數據包的優先級；以上所示的DSP方法執行以下兩個任務任務1在每次調度的開始，推導出排隊中的數據包的發送源和目的站優先級，即SP和DP；任務2根據排隊中的數據包的發送源和目的站優先級，通過循環的配對過程來對發送源和目的站進行配對。一個名為SDP的處理器被用來計算數據包的發送源和目的站的優先級。如果一個發送源和一個目的站(在任務2中)被配對，一條連接該發送源和目的站的路徑將被建立用以傳送相應的隊頭數據包。為敘述簡單起見，當我們說一個數據包Cij被配對時，其意指第i個發送源與第j個目的站被配對。用於DSP方法中第四步的最大配對過程有兩種作法配對法1在每次循環中，數據包Cij將被配對，如果(i)Cij在所有未配對及排隊於第i個發送源的隊頭數據包中有最高的發送源優先級，和(ii)Cij在所有未配對及要傳送到第j個目的站的隊頭數據包中有最高的目的站優先級。配對法2在每次循環中，數據包Cij將被配對，如果(i)Cij在所有未配對及排隊於第i個發送源的隊頭數據包中有最高的發送源優先級，和/或(i)Cij在所有未配對及要傳送到第j個目的站的隊頭數據包中有最高的目的站優先級。給出的DSP方法可用任何程序語言實現及應用到任何所述的受約束排隊系統。現存的基於穩定配對方法的調度方法有以下的缺陷1.所有的數據包的長度被假設是固定的。現存的方法沒有提供對變長數據包的處理。2.現存的穩定配對方法的複雜度是Ω(N2)[文獻5]。對為高速交換機而設計的方法而言，該複雜度未免太高。3.現存的方法中對各數據包優先級的計算具有難以實現的高複雜度。以上所列現存方法的三大缺陷是設計一個高性能方法時所必須克服的。為達此目的，我們已通過對穩定配對方法在輸入端排隊交換機(請記住，虛擬輸出端排隊交換機實際上是一種輸入端排隊交換機)的特定環境裡的應用進行了深入的研究。此外，定長的和變長的數據包被以統一的方式進行調度。我們的調度方法對每個數據包分配三個變量VSP、SP及DP。每個數據包對應的SP和DP變量值分別代表該數據包的發送源和目的站優先級。不失一般性，我們假設越小的SP和DP變量值分別代表的發送源和目的站優先級越大。各數據包的發送源和目的站優先級代表對應的數據包在解決發送源和目的站競爭時的優先次序。VSP是一個輔助變量，其具體用途稍後再述。如何定義和計算每個數據包的目的站優先級不是本發明的內容。我們所要解決的是如何動態地從各數據包的DP來推導出其SP。在對這一最關鍵問題的處理上，我們的方法是與眾不同的。具體表現在其所達到的性能上，主要有1.高速度一個調度方法的複雜度由兩大部分組成，即是，配對方法和計算每個數據包的發送源及目的站優先級。與現存的方法相比，我們的調度方法有極低的複雜度。2.對服務質量的有力支持對服務質量提供支持的能力強弱對未來的交換機系統是其性能的一個主要指標。我們的調度方法可控制每個數據包的傳輸延遲，因而為設計不同的服務質量保證方法提供最大的自由度和最大的支持。3.易於實現我們的方法可減低其所調度系統的實現難度。4.良好的擴展性我們的方法可用於從小到大、不同規模的約束排隊系統。而其方法複雜度僅隨系統規模的增大而緩慢增長。5.可分布性我們的方法可以分布的形式來實現。其分布實現可進一步降低被調度系統的實現和維護難度。下面結合附圖對本發明作進一步詳細的描述。圖1所示的是一個有3個發送源S1[4]、S2[5]、S3[6]和3個目的站D1[8]、D2[9]、D3[10]的受約束排隊系統模型。發送源和目的站間以一個互連網絡[7]相連。每個編號的方框代表一個正在排隊的數據包。方框內的編號代表該數據包的目的站。隊列[1]、[2]、[3]分別用以緩衝儲存從發送源[4]到目的站[8]、[9]、[10]的數據包。每個隊頭數據包是其所在隊列的最高優先級數據包。圖2所示的是在一個受約束排隊系統中的調度及傳送操作的時序關係。如圖所示，在每個時間段的開始，調度方法對各個隊頭數據包進行調度；然後在每個時間段的結束，被調度方法所選中的隊頭數據包將被傳送到它們的目的站。DSP方法可用串行、並行、流水線、軟體、固件、硬體或其組合的方式來實現。從8.1至8.3節中，我們給出一個對第5節中所述DSP方法的軟體實現。以下先給出一個基於隊頭數據包的發送源和目的站優先級的循環最大配對方法。然後再解決DSP方法中最困難也是最關鍵的部分，即，對各個隊頭數據包的發送源和目的站優先級的計算。在8.4節中，我們給出DSP的體系結構設計及硬體實現。在上一節中，我們給出了兩個配對方法，即配對法1和2。在每個時間段的開始，配對方法找出發送源和目的站間的配對。然後在每個時間段的結束，相應該配對的隊頭數據包將被傳送到它們的目的站。以上的配對方法可有不同的實現。具有相同效能的方法可以各種形式來實現，只要被以上的配對方法配對的發送源和目的站也被該方法所配對。一個並行最大配對方法在此我們給出對以上配對方法的一個並行實現。在方法的開始，所有的發送源和目的站都是未配對的。以下的兩個步驟將被重複直到min(N，M)次循環已經被執行或沒有新的配對可能被建立。步驟1每個未配對的目的站對其在先前的循環中未曾請求過的隊頭數據包中具有最高目的站優先級的包所在的發送源發出請求；步驟2每個被請求的發送源依以下情況進行答覆情況1如果該發送源是未配對的，該發送源將和發出請求的目的站配對。情況2如果該發送源是已配對的且請求中的目的站的發送源優先級比配對中的目的站的為高，則將當前的配對撤除並與請求中的目的站建立一個新的配對。對發送源和目的站優先級的不同定義可導致用以上配對方法調度的受約束排隊系統具有不同的特性。以下我們接著討論如何計算每個數據包的發送源和目的站優先級。每個排隊中數據包的發送源和目的站優先級被配對方法用來解決對發送源和目的站的競爭。在本文中，我們不對如何計算每個數據包的目的站優先級加以任何限制。換言之，每個數據包的目的站優先級可以任何方法來計算。以下的討論中，我們將集中在如何從每個數據包的目的站優先級推導出其發送源優先級。每個數據包被賦予一個輔助變量VSP。該輔助變量用以儲存為推導出每個數據包的發送源優先級而所需之信息。一個用來儲存與每個數據包相關之調度信息的數據結構示例如下STRUCTPSI1{INTDP；INTSP；INTVSP；}；數學意義上，存儲於PL[j]中的第i個包的DP，SP和VSP可用(類似於PASCAL程序設計語言中的)結構操作符分別表達為PL[j][i].DP，PL[j][i].SP和PL[j][i].VSP。計算各個數據包的SP和VSP變量值有多種方法，這裡我們僅給出兩個例子，即，SDP1和SDP2處理器。SDP1處理器第一種計算每個數據包Cij的SP和VSP變量值的方法如下情況1如果Cij是一個新到的數據包，其SP和VSP變量值初始化為0。情況2如果Cij是一個隊頭數據包，則按以下情況區別處理情況2.1如果PL[j]中的第k個(三元式所對應的)數據包已被傳送到目的站j，則將該包從PL[j]中刪除。對每個h＝k+1，k+2，……|PL[j]的三元式，如果PL[j][k].DP＜＝PL[j][h]，則三元式PL[j][h]的SP和VSP變量值將加一。情況2.2在Cij被傳送到其目的站j後，原在隊列Q(i，j)中緊隨其後的數據包Cij』的SP和VSP變量值將被加上Cij的VSP變量值。如果已加上Cij的VSP變量值後的Cij』的SP變量值小於Cij的SP變量值，則將Cij』的SP變量值設成Cij的SP變量值。情況2.3對所有的PL[j]表，如果PL[j][k].SP＜PL[j][k-1].SP，其中k＝2，3，……，|PL[j]|，則將PL[j][k].SP設成PL[j][k-1].SP。情況3在每S個時間段的結束(S＞1)，所有隊頭數據包的SP和VSP變量值都減一。SDP2處理器另一種計算每個數據包Cij的SP和VSP變量值的方法如下情況1如果Cij是一個新到的數據包，其SP和VSP變量值初始化為0。情況2如果Cij是一個隊頭數據包，則按以下情況區別處理情況2.1如果PL[j]中的第k個(三元式所對應的)數據包已被傳送到目的站j，則將該包從PL[j]中刪除。對每個h＝1，2，……k-1的三元式，如果PL[j][h].DP＜＝PL[j][k]，則三元式PL[j][h]的SP和VSP變量值將減一。情況2.2在Cij被傳送到其目的站j後，原在隊列Q(i，j)中緊隨其後的數據包Cij』的SP和VSP變量值將被加上Cij的VSP變量值。如果已加上Cij的VSP變量值後的Cij』的SP變量值小於Cij的SP變量值，則將Cij』的SP變量值設成Cij的SP變量值。情況2.3對所有的PL[j]表，如果PL[j][k].SP＜PL[j][k-1].SP，其中k＝2，3，……，|PL[j]|，則將PL[j][k].SP設成PL[j][k-1].SP。情況3在每S個時間段的結束(S＞＝1)，所有隊頭數據包的SP和VSP變量值都加上S-1。在SDP1和SDP2中，對數據包的SP和VSP變量值加上或減去某個值實際上是對各個隊頭數據包的優先級進行動態的調整。在加或減中所用的具體值並不重要。用不同的值來進行加減同樣可以達到同樣的目的。結合了數據結構PSI1的DSP方法構成了對所述受約束排隊系統的一種通用調度方法。換言之，不管如何定義各個數據包的目的站優先級，DSP方法都可用來對排隊中的數據包進行調度。然而，DSP方法及其數據結構PSI1在某些情況下可進一步簡化。例如，每個隊列對其內的數據包以先進先出的形式進行服務。在先進先出隊列的情況下，我們不再需要PSI1中的輔助變量VSP來(從數據包的目的站優先級)推導數據包的發送源優先級，因而輔助變量VSP可被刪去。據此可將PSI1簡化為以下的PSI2STRUCTPSI2{INTDP；INTSP；}；在以上的討論裡，我們一直假設所有數據包的長度是固定的。因此將每個被調度出去的隊頭包傳送到其目的站所需的時間也是不變的。然而在有些情況下，各數據包的長度是可變的。因而導致其傳送所需的時間也是可變的。對變長數據包的調度通常要求每個包的傳送過程是連續的。亦即是對任何數據包Cij，一旦被調度傳送到其目的站，它的傳送過程不可被其它從發送源i到目的站j的數據包所中斷。然而，數據包Cij的傳送過程可以被除此而外的數據包所中斷。我們的DSP方法只需作極小的改動就可以達到上述對變長數據包的調度要求。所作的改動如後當數據包Cij在時間t被調度傳送到其目的站，如果與Cij同隊列另有一個數據包Cij』早於t開始其傳送，則Cij』繼續其傳送過程，而Cij將等待下次被調度。實現DSP調度方法可有多種硬，軟體體系結構，不能一一列舉。以下所舉的僅是一個典型實現。任何對DSP調度方法的實現並不要求受該典型實現所限。在方法運行的開始，所有的發送源和目的站都是未配對的。SDP處理器計算出各個隊頭數據包的發送源和目的站優先級，並據此為所有的M個目的站構造M個PL表。一個名為排序器的器件將對每個PL表中的隊頭數據包按其目的站優先級來進行從高到低的排序，即，按照每個三元式中的DP變量值從低到高來排序(我們已在前面假設越小的DP變量值代表的目的站優先級越大)。該排序器可以任何軟體，固件，串行或並行硬體的形式來實現。一旦M個PL表被建立後，我們可用二叉插入法來對要加入到一個PL表中的新隊頭數據包以每個時間段加入一個的形式完成。在完成每個PL表的排序後，DSP處理器將對該PL表中的所有隊頭數據包的SP變量值進行處理，以使每個PL表中的隊頭數據包的SP變量值是非減的。此任務可通過比較每個數據包和位於其前的數據包的SP變量值，如當前數據包的SP變量值小於位於其前的數據包的SP變量值，則將當前數據包的SP變量值設成位於其前的數據包的SP變量值(參見第8.2節中的SDP1/2設計)。經此處理後，每個PL表中從表頭到表尾的各個數據包的SP變量值將是非減的。接著，配對器將根據各個隊頭數據包的DP和SP變量值來進行發送源和目的站間的配對。按照配對結果，互連網絡將建立發送源和目的站間的路徑來傳送被配對的隊頭數據包。之後，SDP處理器將調整所有(包括新的和舊的)隊頭數據包的發送源和目的站優先級(參見第8.2節中的SDP1/2設計)。本發明給出了一種受約束排隊系統的調度方法。該種受約束排隊系統是一系列網絡的抽象模型，例如，輸入端排隊的交換機、波分光纖網、無線網及有線網等等。我們所提出的創造性調度方法由高效動態的局部配對方法和數據包優先級的計算過程所組成。與現存的其它調度方法相比，我們的方法不但更加靈活及具有更好的性能，同時也易於在高速環境下的實現。權利要求(1)一個NxM受約束排隊系統有N個發送源(或稱輸入端)、M個目的站(或稱輸出端)、一個交換網絡和該系統的調度方法，其特徵在於一種新型高效動態調度方法用局部增量方法來計算排隊顧客(或稱數據包)相應的發送源和目的站的優先級以達到對顧客的快速配對調度及傳輸服務。(2)根據權利要求1所述的調度方法，其特徵在於用以下七個步驟達到對顧客的快速調度及傳輸服務第一步初始化，以建立優先級數據結構並使系統處於調度狀態；第二步將對應每個目的站的隊頭數據包按其目的站優先級來進行從高到低的排序；第三步對每個目的站已排序的隊頭數據包的發送源優先級進行處理，以維持這些隊頭數據包間發送源優先級的非減性；第四步根據各隊頭數據包的狀態，找出一個發送源和目的站間的最大配對，該最大配對滿足以下條件如果一個數據包未被配對，則至少有一個被配對的數據包的優先級比該數據包的優先級高，該被配對的數據包與該未被配對的數據包或有相同的發送源，或有相同的目的站；第五步根據建立的配對，傳送相應的數據包到其目的站；第六步完成傳送後，調整新隊頭數據包的優先級；第七步調整未配對數據包的優先級。(3)根據權利要求2所敘述的調度方法，其特徵在於每個發送源對其要送到各目的站的數據包都根據它們的目的站優先級進行單獨的排隊，每個隊頭數據包是該隊列中的最高優先級數據包。(4)根據權利要求2所敘述的數據包排隊方案，其特徵在於每個數據包的目的站優先級可以任何方法來計算。(5)根據權利要求2所敘述的調度方法的第一步，其特徵在於(i)建立儲存對應於每個隊頭數據包的優先權信息的三元數據結構SP、DP和VSP，(ii)建立創建各目的站優先級表的數據結構。(6)根據權利要求2所敘述的調度方法的第二步，其特徵在於將所有的隊頭數據包按其所屬目的站進行分組，將每組內的隊頭數據包按其目的站的優先級來進行從高到低的排序以構成一個目的站優先級表。(7)根據權利要求6所敘述的排序操作，其特徵在於排序操作可用軟體、固件、硬體或其組合來實現。(8)根據權利要求2所敘述的調度方法的第一步、第三步、第六步和第七步，其特徵在於一個優先權處理器可被組成來產生可供調度方法使用的調度信息。(9)根據權利要求8所敘述的優先權處理器，其特徵在於這種優先權處理器的一種操作步驟如下(i)將每個新到的數據包的SP和VSP變量值初始化為0；(ii)每個隊頭數據包的優先級按以下情況區別處理(a)在該數據包已傳送到其目的站後，則將該數據包所對應的三元數據結構刪除，並將所有於目的站優先級表裡位於其後的所有數據包的SP和VSP變量值都加一；(b)在該數據包已傳送到其目的站後，原在其相應隊列中緊隨其後的數據包的SP和VSP變量值都加以該數據包的VSP變量值，如果已加上該數據包的VSP變量值後的SP變量值仍然小於該數據包的SP變量值，則將緊隨其後數據包的SP變量值設成該數據包的SP變量值；(c)對每個目的站優先級表，如其中任一數據包的SP變量值小於位於其前的數據包的SP變量值，則將該數據包的SP變量值設成位於其前的數據包的SP變量值。(iii)在每S個時間段的結束(S＞＝1)，所有隊頭數據包的SP和VSP變量值都減一。(10)根據權利要求8所敘述的優先權處理器，其特徵在於優先權處理器的另一種操作步驟如下(i)將每個新到的數據包的SP和VSP變量值初始化為0；(ii)每個隊頭數據包的優先級按以下情況區別處理(a)在該數據包已傳送到其目的站後，則將該數據包所對應的三元數據結構刪除，並將所有於目的站優先級表裡位於其前的所有數據包的SP和VSP變量值都減一；(b)在該數據包已傳送到其目的站後，原在其相應隊列中緊隨其後的數據包的SP和VSP變量值都加以該數據包的VSP變量值，如果已加上該數據包的VSP變量值後的SP變量值仍然小於該數據包的SP變量值，則將緊隨其後的數據包的SP變量值設成該數據包的SP變量值；(c)對每個目的站優先級表，如其中任一數據包的SP變量值小於位於其前的數據包的SP變量值，則將該數據包的SP變量值設成位於其前的數據包的SP變量值；(iii)在每S個時間段的結束(S＞＝1)，所有隊頭數據包的SP和VSP變量值都加上S-1。(11)根據權利要求9或10所敘述的優先權處理器的操作步驟中的(i)，其特徵在於對每個新到的數據包的VSP變量值進行初始化，在各數據包的VSP變量值用相同的具體值進行初始化時，該具體值可為任意常數。(12)根據權利要求9或10所敘述的優先權處理器的操作步驟中的(c)，其特徵在於該操作可用任意方法來維護每個目的站優先級表中的隊頭數據包間的發送源優先級的非減性。(13)根據權利要求9或10所敘述的優先權處理器的操作步驟中的(a)和(iii)，其特徵在於對數據包的SP和VSP變量值加上或減去某個值而使各個隊頭數據包的優先級進行動態的調整時，這些被加以或減去的數值可為其它任意合理的數值。(14)根據權利要求2所敘述的調度方法的第四步，其特徵在於根據各隊頭數據包的狀態，用任意一個最大配對方法來找出一個發送源和目的站間的最大配對。(15)根據權利要求14所敘述的最大配對方法，其特徵在於一種最大配對的方法如下在每次循環配對中，如果一個未配對隊頭數據包具有其所在發送源的未配對隊頭數據包中最高的發送源優先級並且該數據包在所有未配對及要傳送到其對應目的站的隊頭數據包中有最高的目的站優先級，那麼此數據包將被配對。(16)根據權利要求14所敘述的最大配對方法，其特徵在於另一種最大配對的方法如下如果一個未配對隊頭數據包具有其所在發送源的未配對隊頭數據包中最高的發送源優先級或者該數據包在所有未配對及要傳送到其對應目的站的隊頭數據包中有最高的目的站優先級，那麼此數據包將被配對。(17)根據權利要求15或16所敘述的最大配對方法，其特徵在於一種並行的最大配對方法將使以下的兩個操作步驟重複直到min(N，M)次循環已經被執行或沒有新的配對可能被建立步驟1每個未配對的目的站對其在先前的循環中未曾請求過的隊頭數據包中具有最高目的站優先級的包所在的發送源發出請求；步驟2每個被請求的發送源依以下情況進行答覆情況1如果該發送源是未配對的，該發送源將和發出請求的目的站配對；情況2如果該發送源是已配對的且請求中的目的站的發送源優先級比配對中的目的站的為高，則將當前的配對撤除並與請求中的目的站建立一個新的配對。(18)根據權利要求2中的第五步，其特徵在於各被配對的數據包在同一時間段內傳送到其對應的目的站。(19)根據權利要求2方法中的第六步，其特徵在於一種調整新隊頭數據包的優先級的方法是用插入排序法來對要加入到一個目的站優先級表中的新隊頭數據包以每個時間段加入一個的形式完成。(20)根據權利要求19將一個新隊頭數據包加到其對應的目的站優先級表的方法，其特徵在於可以應用任何插入排序法，包括二叉插入排序法。(21)根據權利要求2所敘述的操作，其特徵在於各操作不但可以對定長數據包進行，也可以應用到變長數據包上。(22)根據權利要求21所敘述的對變長數據包的應用，其特徵在於一種方法是當一個數據包在某時間段內被調度要傳送到其目的站時，如果另有一個與該被調度數據包同隊列的數據包早於該時間段開始其傳送但尚未傳送完畢，則此另一數據包在該時間段內繼續其傳送過程，而該被調度的數據包則等待下次再被調度。(23)根據權利要求2所敘述的操作，其特徵在於各操作可用串行、並行、流水線、軟體、硬體、固件或它們的組合的方式來實現。(24)根據權利要求23所敘述的實現方式，其特徵在於該實現方式可以是集中的，也可以是分布的。(25)根據權利要求1所敘述的受約束排隊系統，其特徵在於該受約束排隊系統可用來實現一系列的網絡系統，包括輸入端排隊的交換機、路由器、波分光纖網、無線網及有線網等。(26)根據權利要求5所敘述的數據結構，其特徵在於在先進先出隊列的情況下，我們不再需要輔助變量VSP來從數據包的目的站優先級推導數據包的發送源優先級，因而輔助變量VSP可被刪去，簡化為以下的二元數據結構DP及SP，而建立相應的目的站優先級表所需的數據結構也可作出相應的改動。(27)根據權利要求2所敘述的調度方法，其特徵在於當應用到權利要求26所敘述的二元數據結構上時，所有對VSP的操作可被刪去。(28)根據權利要求2所敘述的調度方法，其特徵在於該調度方法可控制每個數據包的傳輸延遲，因而為設計不同的數據包傳輸服務質量保證方法提供最大的自由度和最大的支持。全文摘要本發明給出了一種受約束排隊系統的調度方法。一個NxM受約束排隊系統(圖0)有N個發送源(4)、(5)、(6),M個目的站(8)、(9)、(10),一個交換網絡(7)和該系統的調度方法(11)。該系統中的時間被離散成時間段。到達該系統發送源的數據包(或稱顧客)在發送源的緩衝儲存區內(1)、(2)、(3)內排隊等候被調度傳送。我們的創造性調度方法動態地計算各排隊顧客的發送源和目的站優先級並據此進行高速的配對調度。該調度方法可廣泛應用到實際的高效受約束排隊系統如高性能大規模的交換機中。文檔編號H04L12/56GK1277509SQ9910799公開日2000年12月20日申請日期1999年6月9日優先權日1999年6月9日發明者顧鈞,農革申請人:顧鈞,農革