• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    部分本案揭露提供一種方法，供於進行網路流量之排程。該方法包含：在一個會多路傳輸複數個輸入節點到一輸出節點的節點層級結構中的一目前節點上，從複數個下層級節點中選擇一獲勝節點；取得從獲勝節點提供的第一參數，第一參數係與獲勝節點相關聯；至少部分基於第一參數，判斷與目前節點相關聯的第二參數；以及提供與目前節點相關聯的第二參數至節點層級結構中的一上層級節點，以在上層級節點進行排程。為判斷與第一節點相關聯的第二參數，在一個實施例中，該方法包含使用第一參數，於一具儲存與第一參數相關聯之第二參數的查尋表中，查找一條目。
    公开号:TW201304460A
    申请号:TW101117871
    申请日:2012-05-18
    公开日:2013-01-16
    发明作者:Sarig Livne；Vitaly Sukonik；Einat Ophir
    申请人:Marvell World Trade Ltd；
    IPC主号:H04L47-00
    专利说明:
    網路流量排程系統及其方法、電腦程式及電腦程式產品【相關申請案】
    本案主張引用美國臨時申請專利案號61/487,518「Network Traffic Scheduler and Associated Method,Computer Program and Computer Program Product」之優先權，其申請於5月18日2011年。本案引用上述提案之全部公開內容。
    本發明係關於一種用於進行網路流量排程之方法、其網路系統以及進行其網路流量排程之程式；具體而言，本發明係關於一種可配置網路流量排程之方法、其網路系統以及進行其網路流量排程之程式。
    在此提供之先前技術的目的在於提供本案發明之上下文。此處所描述之先前技術並非係本案之發明者間接或直接承認為本案發明的先前技術。
    在通訊網路的流量排程中，大量輸入所造成的流量往往需要被多路傳輸至一輸出。此外，在一個例子中，與上述輸入相關聯的用戶可分別簽署有指定相應頻寬、延遲和訊號抖動的服務協議。流量排程接著需要進行配置，以使用戶的體驗可滿足該些服務協議。
    各方面的本公開提供一種方法，用於進行網路流量之排程。該方法包含：在一個多路傳輸複數個輸入節點到一輸出節點的節點層級結構中的一目前節點，從複數個下層級節點中選擇一獲勝節點；取得從獲勝節點所提供的第一參數，第一參數係與獲勝節點相關聯；至少部分基於第一參數，判斷與目前節點相關聯的第二參數；以及提供與目前節點相關聯的第二參數至節點層級結構中的一上層級節點，以在上層級節點進行排程。
    為判斷與第一節點相關聯的第二參數，在一個實施例中，該方法包含使用第一參數，於一具儲存與第一參數相關聯之第二參數的查尋表中，查找一條目(Entry)。在一個例子中，該方法包含使用第一參數，於複數個預定義查尋表其中之一，查找該條目。在另一個例子中，該方法包含使用第一參數，於一可組態查尋表中，查找該條目。
    為取得從獲勝節點提供的第一參數，該方法包含取得作為在獲勝節點的流量排程函數的第一參數。
    在一個實施例中，節點層級結構多路傳輸一網路系統之複數個入口埠至輸出節點。在另一實施例中，節點層級結構多路傳輸複數個輸入節點至該網路系統之一出口埠。在另一實施例中，節點層級結構多路傳輸複數個封包佇列至輸出節點。
    為判斷第二參數，在一個示例中，該方法包含基於獲勝節點之一資格參數判斷目前節點之一資格參數。在另一個例子中，該方法包含至少部分基於具包含下層級節點之傳遞優先次序的第一參數，判斷與目前節點相關聯的第二參數。在另一示例中，該方法包含基於第一參數以及目前節點之內部參數，判斷與目前節點相關聯的第二參數。在另一示例中，該方法包含基於第一參數以及目前節點之一最小表徵儲存桶參數及一最大表徵儲存桶參數，判斷與目前節點相關聯的第二參數。
    各方面的本公開提供一種網路系統。該網路系統包含一節點層級結構、一排程模組以及一排程參數控制模組。節點層級結構組態成會多路傳輸複數個輸入節點到一輸出節點。排程模組組態為，在節點層級結構的一目前節點上，從複數個下層級節點中選擇一獲勝節點，該獲勝節點將會被轉發到一高層節點至目前節點。排程參數控制模組組態以取得從獲勝節點提供的第一參數，第一參數是與獲勝節點相關聯、以至少部分基於第一參數判斷與目前節點相關聯的第二參數、以及以提供與目前節點相關聯的第二參數給節點層級結構中的一上層級節點，以在上層級節點進行排程。
    各方面的本公開提供一種電腦可讀取之非暫時性媒介儲存的程式指令，用於使一處理器執行網路流量排程之操作。該操作包含：在一個多路傳輸複數個輸入節點到一輸出節點的節點層級結構中的一目前節點，從複數個下層級節點中選擇一獲勝節點；取得從獲勝節點提供的第一參數，第一參數係與獲勝節點相關聯；至少部分基於第一參數，判斷與目前節點相關聯的第二參數；以及提供與目前節點相關聯的第二參數至節點層級結構中的一上層級節點，以在上層級節點進行排程。
    圖1是根據本案的一個實施例揭露了一種網路系統100中的網路流量排程器1的示意圖。網路流量排程器1根據一節點層級結構進行網路流量之排程。節點層級結構包含複數個輸入節點5以接收網路流量、一輸出節點2以輸出網路流量、以及複數個中間節點3(A)-3(P)以形成網路流量。
    該網路系統100可以是任何合適的網路系統。在一個例子中，網路系統100是一個資料中心，其中包含頂部機架(Top of Rack、TOR)交換機和匯聚交換機。TOR交換機被耦合到各種服務器、驅動器、中央處理單元(Central Processor Units、CPU)等等，並且匯聚交換機從TOR交換機聚集流量並提供給如一個核心交換機。
    在另一例子中，網路系統100是一個切換裝置，諸如路由器、網路交換機等。切換裝置包含：複數個入口埠(ingress ports)、一個或複數個網路處理器、交換機結構以及複數個出口埠(egress ports)。入口埠組態為接收網路流量。網路處理器組態為處理網路流量。交換結構組態為切換網路流量。出口埠組態為輸出網路流量。
    在另一例子中，網路系統100是以單一積體電路(Integrated Circuit、IC)晶片實現。IC晶片包含：複數個輸入/輸出(Input/Output、I/O)引腳，其可組態為接收網路流量，並可以組態為輸出網路流量。IC晶片還包含一網路處理器，以處理所接收到的網路流量，並指導網路流量至合適的I/O引腳。
    另外，根據本揭露的一方面，網路流量排程器1可以配置來管理網路系統100中不同的部分的網路流量，如入口流量管理(ingress traffic management)以及出口流量管理(egress traffic management)等。
    網路流量排程器1組態為根據節點層級結構來管理網路流量。節點層級結構中的節點被佈置於複數個層次級(hierarchy levels)。在圖1的例子中，節點層級結構具有倒置樹狀結構，且輸出節點2為該樹狀結構的根，以及輸入節點5為樹狀結構的葉。具體而言，輸入節點5被佈置於節點層級結構最下層級的輸入層級(input level)15，輸出節點2被設置於節點層級結構中最上層級的輸出層級(output level)10，而中間節點3(A)至3(P)被佈置在輸入層級15及輸出層級10之間的中層級11至14。每一個輸入節點5及中間節點3(A)至3(P)是連接於較上層級的單一上層級節點，並且每個輸出節點2及中間節點3(A)至3(P)是連接於至少一個且有較下層級之下層級節點。
    在一個實施例中，每個輸入節點5對應到一個佇列(queue)，用於存儲與一個資料源或資料接收器相關聯的資料，如一個用戶或一個用戶特定的服務。這些資料可以是單一資料封包(data packet)或資料報(datagram)，如IP資料封包、非同步傳輸模式訊框(Asynchronous Transfer Mode、ATM)、訊框中繼協議資料單元(Frame Relay Protocol Data Units、Frame Relay PDU)、乙太網資料封包或任何其他的封包切換資料。另外，在一個實施例中，幾個單獨的資料封包可以被組合在一起，以更容易處理。換句話說，資料是被網路流量排程器1選出以每次單一資料會被移出佇列，其中每個資料單元可包含一個單一的資料封包，或每個資料單元可包含複數個資料封包的一個包裹。
    雖然在這裡示出的層次結構的所有輸入節點都被設置在相同的輸入層級15中，節點層級結構也可以被安排成將該些輸入節點配置於輸出層級10下的不同層級11至15上。
    不管輸入節點5是組態於哪裡，有複數個中間節點3是組態於輸入節點5及輸出節點2之間，以達成資料之排程及形成。
    示出的節點層級結構顯示說明選擇程序，其中輸入節點5其中之一會被選上，以供應資料至網路流量排程器1的輸出節點2。在一個實施例中，節點層級結構中的節點是對應於網路系統100的實體組件。在另一個實施例中，並非有任何實體組件是對應於節點層級結構中的節點，而是藉由使用軟體及/或硬體來實現該節點層級結構。舉例而言，節點層級結構可被實現為一個網路處理器、特定應用程式積體電路(Application-Specific Integrated Circuit、ASIC)、現場可編程門陣列(Field-Programmable Gate Array、FPGA)或中央處理單元(CPU)在執行軟體指令。
    根據本揭露的一個方面，網路流量排程器1組態為提供一所期望的連接性服務，如藉由確保頻寬是符合用戶服務級別的協議。服務級別的協議規定服務品質的參數，如最小頻寬(minimum bandwidth)、最大頻寬(maximum bandwidth)、延遲性(latency)、訊號抖動(jitter)以及與一用戶間的傳輸或接收流量之丟失機率(loss probability)。各用戶可使用不同的服務級別協議。
    輸出節點5所提供出來的資料可被提供給排程及移出佇列使用，從而一選定的資料單元會從輸入節點5被移出，並被轉移到輸出節點2上。該選擇程序係藉由使用節點層級結構的中間節點3(A)至3(P)來控制網路流量排程器1所確定的資料之出列。在一個實施例中，每一個中間節點3(A)至3(P)及輸出節點2中將會選擇下層級節點其中之一來作為一個獲勝節點，且節點層級結構中節點的運作整體來講會選擇一個獲勝地輸入節點5，以使獲勝輸入節點5到輸出節點2之間的中間節點形成一由獲勝中間節點組成的路徑。因此，一個資料單元在獲勝輸入節點上是被移出佇列，並轉移到輸出節點2。雖然圖1顯示的節點層級結構公開了使用六個層級10-15，只要輸入節點5及輸出節點2之間設有中間節點(例如，3(A)至3(P))，即可使用任何數量的級別。
    根據本公開的一個方面，節點層級結構中的每個節點包含各種排程參數，用於排程之控制，且在一節點上，基於下級節點之獲勝節點，有些排程參數可動態性的被調整。在圖1的例子中，中間節點3(D)包含一排程模組120以及一排程參數更新模組140。排程模組120選擇下級中間節點3(G)-3(I)中其中之一來作為一個獲勝節點。基於該獲勝節點的排程參數，該排程參數更新模組140將更新中間節點3(D)的排程參數。在一個例子中，當中間節點3(G)是獲勝節點時，排程參數更新模組140會基於中間節點3(G)的排程參數來更新該中間節點3(D)的排程參數。然後，該中間節點3(D)的排程參數會被提供給上層級的節點，如中間節點3(A)，致使能在上層級節點進行排程。
    值得注意的是，排程參數更新模組140可以使用任何合適的技術，基於較下層級之獲勝節點的排程參數，諸如一個或複數個查尋表、演算法、程式及內容可尋址存儲器(CAM)等，以判斷中間節點3(D)的排程參數。
    根據本揭露的一個方面，查尋表可提供基於較下層級節點之排程參數來判斷中間節點3(D)之排程參數上的彈性。在一個實施例中，一個查尋表包含複數個條目(Entry)對應於下層級獲勝節點之排程參數的每一個組合，然後每個條目存儲對應於下層級獲勝節點之排程參數之該組合的中間節點(D)之排程參數。該查尋表可以被用來實現中間節點3(D)之排程參數與下層級節點之排程參數之間的任何關係。在一些實例中，該關係可藉由使用其他技術，如演算法、方程等方式來實現。
    此外，在一個例子中，中間節點3(D)包含複數個查尋表，分別對應於該中間節點3(D)之排程參數與下層級獲勝節點之排程參數之間的不同關係。該中間節點3(D)可以選擇預想要的關係之查尋表中之一。該中間節點3(D)可在初始化過程中選擇該查尋表，或者可以動態的改變到一個不同的查尋表，例如，當網路流量場景有變化。
    在一個實施例中，中間節點3(A)-3(P)使用相同的查尋表。在另一實施例中，在同一層級的中間節點使用相同的查尋表，且在不同的層次結構中的中間節點是使用不同的查尋表中。在另一個實施例中，在操作過程中中間節點3(A)-3(P)可以獨立地選擇適當的查尋表。
    圖2是揭露圖1的節點層級結構之中間節點3的邏輯組件的一示意圖。該中間節點3被連接到至少一個下層級別的節點27a-i，以及一個上層節點28。下層級節點可以是輸入節點5或其它中間節點3。上層節點28可以是輸出節點2或其它中間節點3。
    該中間節點3包含：一組態成會選擇一個所述至少一個下層級節點27a-i作為一個獲勝節點之排程模組20，該獲勝節點將被轉發到上層級節點28；以及一排程參數更新模組40，用於基於中間節點3更新排程參數。
    為了能進行選擇，中間節點3可以利用下層級節點27a-i之一個或複數個排程參數30a-i及/或在中間節點3的內部參數。
    其中一個參數是一個資格參數(eligibility parameter)，其是與每個下層級節點27a-i相關聯的一個標誌(flag)。資格參數表示下層級節點27a-i是否有被允許可被選擇。
    另一個參數是與每個下層級節點27a-i相關的排程優先次序。排程優先次序可用來處理對延遲敏感(delay sensitive)及高優先次序之流量(high priority traffic)。在一個實施例中，3位元被用於排程優先次序，其共於排程優先次序8個可能的值。其他數目的排程優先次序也可以被使用。在一個例子中，配置排程優先次序給節點層級結構中的所有節點為一種處理對延遲敏感的流量之方法。
    另一個參數是傳遞優先次序(propagated priority)，也與每個下層級節點27a-i具相關聯。傳遞優先次序是被傳遞到上層級節點，從而被進一步往上傳遞。在一用戶排程層次結構中，傳遞優先次序可用於處理對延遲敏感的流量。在一個例子中，輸入節點之一個高傳遞優先次序可於節點層級結構中往上傳遞至輸出節點僅次下方的一中間節點。然後，根據節點層級結構，在輸入節點的流量被排入較小延遲的排程。
    此外，在一個實施例中，內部狀態參數被排程模組20使用，致使能從下層級節點27a-i中選擇一個贏家。
    排程模組20可基於各種參數使用任何合適的排程技術，如動態權值循環排序(Deficit Weighted Round Robin、DWRR)等類式的技術，來執行排程。
    在一個例子中，一個循環排序機制可以用來實現下層級節點27a-i之間的公平性。在一個實施例中，項循環排序機制是被默認套用於各級別及優先次序中。在另一實施例中，當節點具有顯著不同的大小的資料封包時，動態權值循環排序是用來減少訊號抖動(jitter)。
    DWRR是加權公平佇列(Weighted Fair Queuing、WFQ)的一種實施例子。於工作節約狀態下，它提供一種方式可公平地共享頻寬，並通過權重允許頻寬比例組態。在超額配置的情況下，DWRR是特別有用的。在一個超額配置的情況下，至少一部份時間頻寬的需求是高於可用的頻寬。
    DWRR排程的頻寬係不同於從使用如表徵儲存桶實現(如下文所述)等整形方式得到的頻寬；即使保持準確的比率，從DWRR排程形成的頻寬仍可以隨著時間而變化。超額配置的情況係基於統計多路傳輸，且這會造成不同長度及不同嚴重程度上的擁塞情況。然而，於很長一段時間中，該演算法會造成該些彼此在競爭有限的頻寬資源的節點之頻寬比例是準確的。
    在循環排序機制及DWRR中，一內部狀態是被保持於排程模組20中，例如，致使能知道哪個下層級節點27a-i是最後被服務到的。
    一旦一個獲勝的下層級節點已被排程模組20選上時，排程參數更新模組40會，基於獲勝之下層級節點的排程參數，判斷並更新中間節點3之排程參數。在圖2的示例中，排程參數更新模組40包含一狀態計算模組22、一查尋表24、一資格組合器21以及一內部狀態參數模組25。這些元件是耦接在一起，如圖2所顯示。
    狀態計算模組22會取得一組輸入參數，其中，輸入參數包含與獲勝節點相關聯的排程參數，如資格、排程優先次序、傳遞優先次序等等。此外，在一個示例中，內部狀態參數模組25提供中間節點3的內部狀態參數給狀態計算模組22。
    此外，相較於具有較低傳遞優先次序佇列之子節點(child nodes)，中間節點3較偏好具有較高傳遞優先次序佇列之下層級節點。這使得對延遲敏感的資料被更快的服務到。傳遞優先次序佇列之傳遞方式可以每個節點，或以每層級被選擇性的配置。查尋表之使用將更詳細解釋如下。
    內部狀態參數25可，例如，是雙表徵儲存桶資料25，以基於服務級別協議被用於最小及最大之頻寬整形(shaping)。舉例而言，最低承諾的頻寬可使用一最小表徵儲存桶來處理，並且被稱為最低頻寬，例如，由一個位元表示。一多餘的頻寬可使用一最大表徵儲存桶來處理，並且被稱為最大頻寬，例如，由一個位元表示。因此，中間節點使用最小頻寬來做頻寬之保證，並且用最大表徵儲存桶來形成頻寬速率。
    最小表徵儲存桶是用來控制該保證的頻寬。此頻寬是在除了被超額申請使用外的其他任何情況下被提供。最大表徵儲存桶是用來限制一特定的節點於一特定的最大頻寬。在其他節點沒有資料，但仍可以防止一較低層節點使用所有可用的頻寬且違反它的服務級別協議的狀況下，或它消耗較上層級的中間節點的頻寬(表徵)並非理想的動作且該頻寬將在以後的時間需使用於更重要的流量時，此限制是必要的。相較於符合最大表徵儲存桶之節點，符合最小表徵儲存桶之節點會被首選(嚴格優先次序、strict priority)。在每個中間節點，所有的最低節點(符合最小表徵儲存桶之該些節點)會較最大節點(不符合最小表徵儲存桶，但符合最大表徵儲存桶之該些節點)先被服務到。此方案可確保最小頻寬在最大頻寬前被提供。
    藉由使用輸入參數，狀態計算模組22可通過在一查尋表24中找到一個匹配行列來取得輸出參數31。輸入參數被用作為一個鍵或地址，以尋找該輸出參數31。該查尋表24被構成能適用於輸入參數的所有組合。
    舉例而言，如果狀態計算的輸入參數是為傳遞優先次序(3位元)、最小表徵儲存桶(1位元)以及最大表徵儲存桶(1位元)，會有5位元是供給輸入參數，這等於有2ˆ5=32種輸入參數之可能的組合。查尋表24並可使用該輸入參數為表格鍵(table key)，並可能在這個例子中有32行，以涵蓋輸入參數之所有可能的值。此外，亦可使用具有萬用字元的聯想存儲器(associative memory with wildcards)來減少行數，並且仍能涵蓋輸入參數之所有可能的值。
    輸出參數例如可以包含傳遞優先次序(3位元)，預定優先次序(3位元)以及資格(一位元)。亦可輸出兩個位元來分別更新上層級節點之最小表徵儲存桶及最大表徵儲存桶。在本示例中，輸出參數因此可包含七個或九個位元。
    需要注意的是，本發明提出的每個參數的位元數目僅僅是示例，在每個實施例可以被自由地選擇每個參數為任何合適的位元數目。
    查尋表24因此係為輸入參數之每個值定義輸出參數，而實際上是提供一種可靈活定義一個函數f的方式，其中輸出參數=f(輸入參數)。
    提供給上層級節點28之輸出參數31中的至少一些是被用作為上層級節點28之輸入參數，除非該上層級節點是輸出節點2。
    輸出參數31中的一個參數可以是資格參數。資格參數可藉由資格計算組合器21被計算出來。在一個例子中，資格計算組合器21將查尋表中的該匹配行與獲勝節點的資格結合在一起，以判斷用於輸出的資格參數。在一個例子中，資格計算組合器21在一乘法器中或藉由使用“AND”閘，以將查尋表中匹配行找到的資格參數與獲勝節點之輸入資格參數進行一“AND”運算。
    獲勝節點的一標識32也會被提供給上層級節點。藉由此方式，每個層級的獲勝節點之標識會於層次結構中被往上傳遞，最終以使整個層次結構中的一個獲勝節點被判斷出來。
    圖3顯示圖2中中間節點3的查尋表是如何被狀態計算模組22選出來的示意圖。該中間節點3包含複數個預定義查尋表24a-n。因此，每一個預定義查尋表係定義狀態計算之一函數。每個中間節點3組態為會於預定義查尋表24a-n中選擇現用有效者。被選定的查尋表將會在判斷輸出參數時被使用。此配置設定可以是完全靜態的。相對地，也可以組態在開機時執行，或可根據需求動態式的被重新配置，此一方式可能在每個資料單元之佇列移出後執行。該動態之選擇可由一外部控制裝置來控制。此外，亦可不用選擇所需的查尋表，而是將查尋表的內容進行改變，以實現所需的功能。換句話說，在此樣的實施例中，該查尋表是一個可自由組態的表格。
    通過這種可選擇行為的狀態計算，可供全新層次的彈性/靈活性。藉由使用查尋表，函數的選擇可於所有中間節點中均勻地分別於節點層級結構中的每個層級或分別於每個單獨的中間節點被進行。
    圖4顯示一方法之流程圖，其方法係於圖2中的中間節點執行。此方法可於圖1中的每個中間節點中進行，且可以硬體及/或軟體中實現。
    在S40中，選擇較低層級其中之一個節點來作為一個獲勝節點，以其後將被傳遞至上層級節點。此選擇係如上述描述進行的，並參照排程模組20。
    在S41中，如上所述基於狀態計算模組22，取得一組輸入參數。輸入參數可以包含輸入資料，如排程參數，該輸入參數係與獲勝節點及相對中間節點之任選的內部狀態資料相關聯。
    在S42中，如上所述，在查尋表中，藉由使用輸入參數作為密鑰查尋一個匹配行，以取得輸出參數。
    在S43中，將在S42中取得的輸出參數提供給上層級節點。
    在S44中，更新內部狀態資料，如最小表徵儲存桶及最大表徵儲存桶參數。此步驟可相對整個網路流量排程中獲勝輸入節點被選擇時進行，或可相對一獲勝下層級節點被選擇時進行。
    圖5顯示包含電腦讀取手段之一電腦程式產品50的一個例子。這台電腦讀取手段可儲存一電腦程式51，其可使一控制器執行本案所描述的實施例的方法。在此例子中，電腦程式產品50為一種光學碟片，如CD(Compact Disc、光碟片)、DVD(Digital Versatile Disc、數位影音光碟)或藍光光碟(Blu-Ray disc)。正如上所述，電腦程式產品50亦可以被實施為網路流量排程器的存儲器。雖然這裡示意性地將電腦程式51描繪為所顯示之光碟片上的軌道，電腦程式51可藉由任何適合電腦程式產品50的方式被儲存。
    本發明已由上述相關實施例加以描述，然而上述實施例僅為實施本發明之範圍。必須指出的是，已揭露之實施例並未限制本發明之範圍。相反地，包含於申請專利範圍之精神及範圍之修改及均等設置均包含於本發明之範圍內。
    1‧‧‧網路流量排程器
    2‧‧‧輸出節點
    3(A)~3(P)‧‧‧中間節點
    5‧‧‧輸入節點
    10‧‧‧輸出層級
    11~14‧‧‧中層級
    15‧‧‧輸入層級
    20‧‧‧排程模組
    21‧‧‧資格計算組合器
    22‧‧‧狀態計算模組
    24、24a~24n‧‧‧查尋表
    25‧‧‧內部狀態參數模組
    27a~27i‧‧‧下層級節點
    28‧‧‧上層節點
    30a~30i‧‧‧排程參數
    31‧‧‧輸出參數
    32‧‧‧標識
    40‧‧‧排程參數更新模組
    50‧‧‧電腦程式產品
    51‧‧‧電腦程式
    S40~S44‧‧‧步驟
    100‧‧‧網路系統
    120‧‧‧排程模組
    140‧‧‧排程參數更新模組
    圖1顯示一網路流量排程器之邏輯層級結構的實施例之示意圖；圖2顯示圖1的邏輯層級結構之一中間節點的邏輯元件之示意圖；圖3顯示如何圖2的中間節點之一狀態計算模組可選擇一查尋表之示意圖；圖4顯示在圖2的中間節點中進行的一方法之流程表的示意圖；以及圖5顯示一包含電腦讀取手段之電腦程式產品的一個例子的示意圖。
    1‧‧‧網路流量排程器
    2‧‧‧輸出節點
    3(A)~3(P)‧‧‧中間節點
    5‧‧‧輸入節點
    10‧‧‧輸出層級
    11~14‧‧‧中層級
    15‧‧‧輸入層級
    100‧‧‧網路系統
    120‧‧‧排程模組
    140‧‧‧排程參數更新模組
    权利要求:
    Claims (22)
    [1] 一種用於網路流量排程之方法，包含：在一多路傳輸複數個輸入節點到一輸出節點的節點層級結構的一第一節點，從複數個第一級節點中選擇一第二節點；取得從該第二節點提供的第一參數，該第一參數與該第二節點相關聯；至少部分基於該第一參數，判斷與該第一節點相關聯的第二參數；以及提供與該第一節點相關聯的該第二參數至該節點層級結構中的一第二級節點，以在該第二級節點進行排程。
    [2] 如請求項1所述之方法，其中至少部分基於該第一參數，判斷與該第一節點相關聯的該第二參數進一步包含：使用該第一參數，於一具儲存與該第一參數相關聯之該第二參數的一查尋表中，查找一條目。
    [3] 如請求項2所述之方法，其中使用該第一參數，於該查尋表中，查找該條目進一步包含以下至少其一：使用該第一參數，於複數個預定義查尋表其中之一，查找該條目；以及使用該第一參數，組態於一可組態查尋表中，查找該條目。
    [4] 如請求項1所述之方法，其中取該得從該第二個節點提供的該第一參數進一步包含：取得作為在該第二節點的一流量排程函數的該第一參數。
    [5] 如請求項1所述之方法，其中在該多路傳輸複數個輸入節點到該輸出節點的節點層級結構的該第一節點上，從複數個第一級節點中選擇該第二節點進一步包含以下至少其一：在該多路傳輸一網路系統之複數個入口埠至該輸出節點的該節點層級結構中，從複數個第一級節點中選擇該第二節點；在該多路傳輸複數個輸入節點至一網路系統之一出口埠的該節點層級結構之該第一節點，從該複數個第一級節點中選擇該第二節點；以及在該多路傳輸複數個封包佇列(packet queues)至該輸出節點中的該第一節點上，從該複數個第一級節點中選擇該第二節點。
    [6] 如請求項1所述之方法，其中至少部分基於該第一參數，判斷與該第一節點相關聯的該第二參數進一步包含：基於該第二節點之一資格參數判斷該第一節點之一資格參數。
    [7] 如請求項1所述之方法，其中至少部分基於該第一參數，判斷與該第一節點相關聯的該第二參數進一步包含：至少部分基於具包含該第一級節點之傳遞優先次序的該第一參數，判斷與該第一節點相關聯的該第二參數。
    [8] 如請求項1所述之方法，其中至少部分基於該第一參數，判斷與該第一節點相關聯的該第二參數進一步包含：基於該第一參數以及該第一節點之內部參數，判斷與該第一節點相關聯的該第二參數。
    [9] 如請求項8所述之方法，其中基於該第一參數及該第一節點之該內部參數，判斷與該第一節點相關聯的該第二參數進一步包含：基於該第一參數以及該第一節點之一最小表徵儲存桶(token bucket)參數及一最大表徵儲存桶參數，判斷與該第一節點相關聯的該第二參數。
    [10] 如請求項8中所述之方法，進一步包含：當該第二節點被選中時，更新該第一節點的該內部參數。
    [11] 如請求項1所述之方法，其中該第一節點是一目前節點、該第二節點是一獲勝節點(winning node)、該輸出節點為該節點層級結構中最高層級、該第一級節點為在該節點層級結構中較該目前節點低的層級、以及該第二級節點在該節點層級結構中較該目前節點高的層級。
    [12] 一種網路系統，包含：一節點層級結構，組態以多路傳輸複數個輸入節點至一輸出節點；一排程模組，組態以在該節點層級結構的一第一節點，從複數個第一級節點中選擇一第二節點；以及一排程參數控制模組，組態以取得從該第二節點提供的該第一參數，該第一參數與該第二節點相關聯、以至少部分基於該第一參數判斷與該第一節點相關聯的第二參數、以及提供與該第一節點相關聯的該第二參數至該節點層級結構中的一第二級節點，以在該第二級節點進行排程。
    [13] 如請求項12中所述之網路系統，其中該排程參數控制模組包含一查尋表，且該排程參數控制模組係組態以使用該第一參數，在一具儲存與該第一參數相關聯之該第二參數的該查尋表中，查找一條目。
    [14] 如請求項13所述之網路系統，其中該排程參數控制模組包含複數個預定義的查尋表，且該排程參數控制模組從複數個預定義查尋表其中之一選擇為進行查尋作業的該查尋表。
    [15] 如請求項13所述之網路系統，其中該排程參數控制模組包含一可組態查尋表。
    [16] 如請求項12所述之網路系統，其中該節點層級結構的該輸入節點對應於該網路系統之一入口埠。
    [17] 如請求項12所述之網路系統，其中該節點層級結構的輸出節點對應於網路系統之一出口埠。
    [18] 如請求項12所述之網路系統，其中該節點層級結構的該輸入節點對應於複數個封包佇列。
    [19] 如請求項12所述之網路系統，其中該排程參數控制模組係組態以基於該第一參數以及該第一節點之該內部參數，判斷與該第一節點相關聯的該第二參數。
    [20] 如請求項19所述之網路系統，其中該排程參數控制模組係組態以基於該第一參數以及該第一節點之一最小表徵儲存桶參數及一最大表徵儲存桶參數，判斷與該第一節點相關聯的該第二參數。
    [21] 如請求項12所述之網路系統，其中該第一節點是一目前節點、該第二節點是一獲勝節點(winning node)、該輸出節點為該節點層級結構中最高的層級、該第一級節點在該節點層級結構中較該目前節點低的層級、以及該第二級節點在該節點層級結構中較該目前節點高的層級。
    [22] 一種非暫時性電腦可讀取媒介，係儲存用於使一處理器執行網路流量排程之操作的程式指令，該操作包含：在一多路傳輸複數個輸入節點到一輸出節點的節點層級結構中的一目前節點，從複數個下層級節點中選擇一獲勝節點；取得從獲勝節點提供的第一參數，該第一參數係與該獲勝節點相關聯；至少部分基於該第一參數，判斷與該目前節點相關聯的第二參數；以及提供與該目前節點相關聯的該第二參數至該節點層級結構中的一上層級節點，以在該上層級節點進行排程。
    类似技术:
    公开号 | 公开日 | 专利标题
    TWI593253B|2017-07-21|網路流量排程系統及其方法、電腦程式及電腦程式產品
    US10178053B2|2019-01-08|Programmable broadband gateway hierarchical output queueing
    US8230110B2|2012-07-24|Work-conserving packet scheduling in network devices
    US6810426B2|2004-10-26|Methods and systems providing fair queuing and priority scheduling to enhance quality of service in a network
    US7474668B2|2009-01-06|Flexible multilevel output traffic control
    EP2695334B1|2019-08-07|Packet scheduling method and apparatus
    US7986706B2|2011-07-26|Hierarchical pipelined distributed scheduling traffic manager
    EP1774714B1|2012-09-05|Hierarchal scheduler with multiple scheduling lanes
    US7394808B2|2008-07-01|Method and apparatus for implementing scheduling algorithms in a network element
    US8897292B2|2014-11-25|Low pass filter for hierarchical pipelined distributed scheduling traffic manager
    CN106302227B|2019-12-17|混合网络流调度方法和交换机
    MXPA05012863A|2006-06-23|Sistema y metodo para planeacion con base en tiempo.
    US10447608B2|2019-10-15|Packet scheduling using hierarchical scheduling process with priority propagation
    US8379518B2|2013-02-19|Multi-stage scheduler with processor resource and bandwidth resource allocation
    US10110515B2|2018-10-23|Packet scheduling using hierarchical scheduling process
    US9973437B2|2018-05-15|Apparatus to achieve quality of service | without requiring fabric speedup
    Hu et al.2010|Dynamic queuing sharing mechanism for per-flow quality of service control
    US20090154483A1|2009-06-18|A 3-level queuing scheduler supporting flexible configuration and etherchannel
    US7813283B1|2010-10-12|Circuit and method for arbitration
    Chrysos et al.2014|Tandem queue weighted fair smooth scheduling
    US9424088B1|2016-08-23|Multi-level deficit weighted round robin scheduler acting as a flat single scheduler
    Martinez et al.2009|Hardware implementation study of the Deficit Table egress link scheduling algorithm
    同族专利:
    公开号 | 公开日
    CN103548303A|2014-01-29|
    US20120294317A1|2012-11-22|
    US9042220B2|2015-05-26|
    EP2525534A1|2012-11-21|
    WO2012156824A1|2012-11-22|
    CN103548303B|2017-02-08|
    EP2525534B1|2018-04-18|
    TWI593253B|2017-07-21|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US6487213B1|1998-01-05|2002-11-26|Polytechnic University|Methods and apparatus for fairly arbitrating contention for an output port|
    US6667984B1|1998-05-15|2003-12-23|Polytechnic University|Methods and apparatus for arbitrating output port contention in a switch having virtual output queuing|
    US6901074B1|1998-12-03|2005-05-31|Secretary Of Agency Of Industrial Science And Technology|Communication method and communications system|
    US7477650B2|2003-10-02|2009-01-13|Alcatel Lucent|Method and apparatus for frame-aware and pipelined hierarchical scheduling|
    US7460544B2|2004-12-29|2008-12-02|Intel Corporation|Flexible mesh structure for hierarchical scheduling|
    WO2006129789A1|2005-06-02|2006-12-07|Nec Corporation|スイッチ装置、スイッチング方法およびスイッチ制御用プログラム|
    US8130648B2|2006-01-04|2012-03-06|Broadcom Corporation|Hierarchical queue shaping|
    US8824287B2|2008-04-24|2014-09-02|Marvell International Ltd.|Method and apparatus for managing traffic in a network|
    US7969884B1|2008-05-09|2011-06-28|Nortel Networks Limited|Method and system for weight and rate scheduling|
    US8027346B1|2008-05-29|2011-09-27|Avaya Inc.|Method and system for scheduler dominated merge of state changes|
    US7995597B2|2008-10-14|2011-08-09|Nortel Networks Limited|Method and system for weighted fair queuing|
    US7986706B2|2009-04-29|2011-07-26|Telefonaktiebolaget Lm Ericsson|Hierarchical pipelined distributed scheduling traffic manager|
    CN101729412B|2009-11-05|2012-03-14|北京超图软件股份有限公司|地理信息服务的分布式层次集群方法和系统|
    US8391305B2|2009-12-30|2013-03-05|International Business Machines Corporation|Assignment constraint matrix for assigning work from multiple sources to multiple sinks|US10680957B2|2014-05-28|2020-06-09|Cavium International|Method and apparatus for analytics in a network switch|
    US9871733B2|2014-11-13|2018-01-16|Cavium, Inc.|Policer architecture|
    US9769075B2|2015-04-01|2017-09-19|Honeywell International Inc.|Interference cognizant network scheduling|
    US9762501B2|2015-04-01|2017-09-12|Honeywell International Inc.|Systematic hybrid network scheduling for multiple traffic classes with host timing and phase constraints|
    US9769082B2|2015-04-01|2017-09-19|Honeywell International Inc.|System and method for network bandwidth, buffers and timing management using hybrid scheduling of traffic with different priorities and guarantees|
    WO2020009989A1|2018-07-05|2020-01-09|Mythic, Inc.|Systems and methods for implementing an intelligence processing computing architecture|
    法律状态:
    2021-04-21| MM4A| Annulment or lapse of patent due to non-payment of fees|
    优先权:
    申请号 | 申请日 | 专利标题
    US201161487518P| true| 2011-05-18|2011-05-18||
    EP11166496.7A|EP2525534B1|2011-05-18|2011-05-18|Network traffic scheduler and associated method, computer program and computer program product|
    [返回顶部]