TWI222012B - Method and system for network processor scheduling outputs using disconnect/reconnect flow queues - Google Patents

Description

1222012 A7 _________B7 ____ 五、發明説明（1 ) 相關專利與專利申請之交叉參考 本發明係關於下列文件，且所有下列文件皆是讓渡給本 發明之受讓人，且在此提及該等文件以供感興趣者參考。 美國專利第5,724,348號，名稱爲“Efficient Hardware/Software Interface for a Data Switch”，於 1998 年 3 月3日公佈，且此專利在本文中有時候稱爲介面專利。 美國專利申請流水號09/330,968，於1999年6月11日申 凊’且名稱爲 “High Speed Parallel/Serial Link for Data Communications，’，有時候稱爲鏈路專利。 美國專利申請流水號09/384,691，於1999年8月27日申 請，發明者爲Brian Bass等人，名稱爲“Network Processor Processing Complex and Methods”，且在本文中有時候稱爲 網路處理單元專利，或NPU專利。 美國專利申請流水號09/ 546, 65 1，於2000年4月10日申 請，且名稱爲 “Method and System for Minimizing Congestion in a Network”。此專利在本文中有時候稱爲流程控制專利。 經濟部中央標準局員工消費合作社印裝 (請先閲讀背面之注意事項再填寫本頁) 美國專利申請流水號09/ 547, 280，於2000年4月1 1日申 請，名稱爲 “Unified Method and System for Scheduling and Discarding Packets in Computer Networks”。此專利在本文中 有時候稱爲封包捨棄專利。 美國專利申請流水號09/548, 907，於2000年4月13日申 請，名稱爲“Method and System for Network Processor

Scheduler”。此專利在本文中有時候稱爲排程器結構專利。 美國專利申請流水號09/548, 91 1，於2000年4月13日申 -4 - 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐） ~ 1222012 A7

經濟部智慧財產局員工消費合作社印製 1222012 A7 -------—---- ’ 五、發明說明（3 ) 料通’與適用於此種網路通訊之路由器與交換機之基本 知識。尤其’本説明假設讀者熟悉網路架構之國際標準組 織（“ISO”）模型，其中分割網路運作成爲許多層。基於ls〇 模型之典型架構自第一層（有時候稱爲“ L丨，，）延伸，其中第 一層是實體通道或媒體，信號經由第一層向上傳送通過第 一層（或“L2”），第三層（或“L3”），依此類推至第七層，且 第七層是程式設計成爲常駐於一連接至網路之電腦系統之 應用層。在本文中，將該等層稱爲L1，L2，L3是意指網路 架構之對應層。本説明也是基於用於網路通訊之稱爲封包 及訊框之位元_的基本瞭解。 就今日之網路運作之觀點來看，頻寬考量（或系統在—單 位時間内可處理之資料數量）愈來愈重要。通過網路之流量 正在增加，無論是在流量之數量與多樣性方面。曾經，某 些、’罔路主要疋用於某種通訊流量，例如電話網路之語音與 資料傳輸網路之數位資料。當然，除了語音信號以^卜7電 話網路也可承載有限數量之“資料，，（例如發話方號碼與受話 方號碼，以進行選徑與計費），但是某些網路之主要用途， 在過去一段時間，實質上是用於均句封包。 由於網際網路（鬆散連接電腦之一公用網路，有時候稱爲 全球資訊網或“WWW”），與出現於私有資料傳輸網路之網際 網路之内部類似物（有時候稱爲企業網路），之日漸風行而 導致流量之大幅增加。網際網路與企業網路涉及遠端:置 間之大量資訊之傳輸，以滿足對於遠端資訊存取與浮現應 用之不斷成長之需求。網際網路開放爆炸性數量之遠端資 -6- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公爱) -------- ·裝--------訂---------^9. (請先閱讀背面之注意事項再填寫本頁〕 1222012

、發明說明（ 經濟部智慧財產局員工消費合作社印製 =位於地理上分散之區域之極多使料，且致能多種新 :，例如電子商務，而電子商務導致網路之負載大幅择 二其他應用，例如電予郵件，樓案傳輸，與資料庫存ς 、步增加網路之負載，而某些網路由於高位準之網 量已受到扭曲。 現在語音與資料流量也聚合於網路。資料目前是經由網 際網路（藉由網際網路協u ΙΡ)免t來傳輸，而語音流量 遵循最低成本之路徑。一些技術，例如藉由IP來傳送 m曰（VoIP)與藉由非同步傳輸模式或atm來傳送語音 (VoATM)或藉由訊框傳輸來傳送語音（v〇FR)，皆是現在^ 兄之m q流量傳輸之具有成本效益的替代方案。當這些服 務轉夂時’業界將考量一些因素，例如改變之成本結構， 〃處理器間之資釩傳輸之服務成本與服務品質間的折衷考 〇 服務品質方面包含容量或頻寬（在一時間週期内可處理多 少資訊），回應時間（處理一訊框需花費多少時間），與處理 之彈性（其是否回應於不同之協定與訊框組態，例如不同之 封裝或訊框標頭方法）。使用一資源之使用者將考量服務品 質以及服務成本，並視展現之情況而定來進行折衷。最好 允許使用者選擇多種不同之優先權或排程演算法，而由使 用者來決定是否他想要（並支付相關之費用）一保證之頻 寬，取大努力，或一保證頻寬，但對於尖峰頻寬只需盡最 大努力。除此之外，最好一用以指配頻寬之系統具有一系 統，以藉由拒絕使用者獲得超過使用者所選與付費之容 本紙張尺度適用中國國家標準（CNS)A4規格（210 x 297公釐） irT •裝--------訂--------- (請先閱讀背面之注咅？事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 丄222012 五、發明說明（5 量，來執行使用者所選之優先權與頻寬。 二以如技術之系統以多種方式來處理來自一處理系統 心輸出資訊單元。一建議是使用一輪流排程器，以致一組 ^列獲得公平待遇。另一種系統運用許多不同位準之優先 權’且每一種優先權具有一佇列。在此種系統中，一絕對 優^權受到實現，其中最高優先權之工作最先受到處理， 取低"k先權之工作可能永遠無法受到服務。排程輸出之 另一方法涉及多個優先權表列。這也稱爲使用一階層式封 包排裎系統。甚至有一些系統使用許多不同之排程方法， 藉由使用不同排程技術之組合，來決定資訊單元傳輸至一 資料傳輸網路之順序。 其他系統使用以一輪流方式來建構之加權優先權技術_該 技術基於一定義服務位準之演算法來服務所有佇列，其中 :仔列义到服務之頻率南於其他仵列。即使此種加權優 先權系統仍會提供服務給一持續超出所指配之服務位準之 使用者，繼續服務，雖然較不頻繁，甚至當其超出所指配 之服務位準時，而使系統很難實施一服務位準策略。 當決定服務那些顧客時考量封包或訊框之大小可增加— 公平性量度至一服務系統，因爲處理大訊框之使用者佔用 較多之系統容量，且因此相較於處理小訊框之使用者，應 接收較不頻繁之服務。一些以前技術之系統當指配資源時 會考量傳輸之大小，但其他系統則不會。一些通訊系統使 用一均句，固定大小之封包，使得封包大小之考量變成不 必要，但是其他通訊系統當指配資源時則未考量封包之大 -8 - 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） : 裝--------訂--------- (請先閱讀背面之注意事項再填寫本頁} 1222012 A7

小。 其他以前技術系統係針對處理具有一相同大小之資1w (請先閱讀背面之注意事項再填寫本頁} π，例如所謂之非同步傳輸模式（或ATM)系統，以致各= 疋目如或未來之資訊單元之優先權時，資訊單元之大J、 爻到考慮。一具有加權驅動式排程器之ATM系統，是在〆 則技術領域爲眾所知，用以排程一 ATM系統輸出之該等解 決方案之一。 在任何此種系統中，最好涵蓋一些系統限制，例如iI 訊框大小爲何，指配某一保證頻寬給一顧客，且同時提: 一機制以提供下列額外特點：涵蓋超過保證之頻寬之=峰 輸入，且同時防止一系統參數之大量與持續超出，且仍然 高效率及公平地使用網路處理器之容量以提供輸出至資^ 傳輸網路。 經濟部智慧財產局員工消費合作社印製 最好具有一系統，且該系統對於允許所要之不同種領與 位準之服務具有最大彈性。例如，一些使用者想要最12 頻寬，其他使用者可能想要最小之頻寬，但允許叢發，而 其他人可能對於一經濟型服務感到興趣，其中提供“最大努 力”服務，並要求或未要求最小頻寬，且對於頻寬或叢發大 小之任何限制必須可由排程系統來實施。最好—排程系統 可具有一簡單及高效率系統之該等特點之任何特點咬全部 特點，其中涵蓋可變封包長度，並提供一加權公平佇列系 統以指配未使用之頻寬，但是不幸的是，此種系統不存在 於以前技術。 最好也具備下列功能：當一流程佇列斷連及再連時，則 -9- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公复） x^2〇i2 五、 發明說明（ 7 經濟部智慧財產局員工消費合作社印製 相車又於流程佇列未受到斷連及再連之 ^ 達成較佳之優先權或位置。 ^，热法在佇列中 另外，當計算排程時，最好一簡單與合 建構’以避免相關於-複雜計算之硬體：：率之系統受到 計算是用以在一給定流程受到服務之a ’其中該複雜 置。 寸找一新排程位 因此，用以處理資料封包以傳輸至— 統具有不好之缺點與限制，其中該等缺點 之多功能性或系統之運作速度皆會造成影響、。 ；系 發明摘要 曰 本發明藉由下列方式來克服以前技 制：提供簡單，但高效率之方式來處理=統…與 >、客、… 乃八术處理一處理系統所輸出 訊早元或訊框，及導引訊框至輸出琿以分派至一 傳輸網路4發明特別適用於—系統，其中來自多個使 者之可變長度封包受到處理，且其中對於至少一些使用 提供一服務位準承諾。 本發明允許提供多種服務位準合約或承諾給系統之不 使用者。換句話説，一最小保證頻寬可提供給一使用者 而同時其他使用者則使用共享頻寬，可允許一尖峰頻寬^ 持一段有限之持續時間，且最大叢發服務位準可提供給使 用者’其中所有前述服務皆受到程式設計，並不會干擾 供給其他使用者之服務。 本發明具有下列優點··其允許頻寬資源之高效率使用 並允許服務位準承諾獲得實現，且同時允許任何剩餘頻 系 統 限 出 用者 同 維 提 寬 -10- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公爱） ^22012 經濟部智慧財產局員工消費合作社印製 A7 B7 五、發明說明（8 ) 受到高效率及公平使用。 本發明也具有下列優點：實施資源指配，且同時涵蓋叢 發。換句話説，使用者可依照一叢發率來傳送某一數量2 ，量，其中該叢發率超過其之定義頻寬一段有限時間，但 是，如果使用者如此做一段過長之時間，則不准使用者傳 送超過其之正常頻寬，直到其彌補該過度使用爲止。這是 藉由針對一個別使用者之流程佇列之系統“信用，，來達成， 其中該系統信用是當使用者未使用其之全部頻寬時所累積 之信用。 “、 本發明允許一簡單計算，在不執行除法之下，以支援一 雙到服務流程之一彳宁列新位置的計算。 本發明也具有下列優點：一旦斷連與再連，一給定流程 無法藉由其之斷連來達成一改良之位置。 本發明使用一槽距離來調整訊框之大小與佇列加權，以 允許迅速及輕易算出下一位置。 本發明也維持叢發使用之一行進分數，並計算及維持一 可用之“信用，，來允許合理之叢發，但對於使用率則實施系 統限制。 h 本發明也具有下列優點：提供一推入堆疊，其中排程於 一給定時槽或循環之服務之最後一請求獲得優先權。這是 基於下列假设：排程於稍後時間之使用者必須具有一更合 之優先權’且相較於服務一較低優先權之使用者之類似延 遲，服務該使用者之任何延遲將導致一更大百分率之延 遲。使用此後進先出（LIFO)系統來實現時槽請求允許系統 -11 - 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ' ''— • : 裝--------訂--------- (請先閱讀背面之注意事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 1222012 五、發明說明（9 ) 使得感知之服務延遲最小化，其中該服務延遲是以當系統 過載時連續服務間之正常區間之百分率來表示，換句話 説，其在排程時間具有多於其可處理之工作。 附圖之簡單説明 在陳述以前技術之一些限制及缺點，與本發明之一些目 標及優點之後，根據用以展示本發明之一改良選徑系統與 方法之附圖的下列詳細説明，熟悉相關領域者應可明瞭其 他目標與優點，其中： 圖1是一介面裝置之方塊圖，其中包含説明於Npu專利之 嵌入型處理器組，以展示一適用於實施本發明之DN排列系 統與排程器； 圖2是圖1所示種類之一嵌入型處理器組之方塊圖，其中 DN排列器（與其包含之排程器）有助於理解本發明； 圖3展示，根據本發明之較佳實例，在圖2之排程器中排 程可變長度封包之一系統； 圖4展不，根據本發明之較佳實例，用於圖3之排程系統 之一時間型日暦； 圖5展示用於圖3-4之排程器之排程運作的流程圖； 圖6顯示一圖形’其中展示圖4之時框如何具有不同之時 間解析度； 圖7顯示用於本發明之最大叢發規定； 圖8- 13是本排程器之各種元件之流程圖，其中包含針對 計算下一綠時間之圖8及9，針對計算及更新叢發大小信用 之圖10及11，與顯示藉由佇列控制區塊之老化以避免得利 -12- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） 丨*--^--------裝--------訂--------- (請先閱讀背面之注意事項再填寫本頁) 1222012 五、發明說明（1〇) 於斷連及再連之圖12及13 ; 圖14顯示一根據本發明之較佳實例之wfq日暦，且 曆適用於本發明之排程器；且 ^ 9

圖！5顯示排程運作之邏輯之流程圖，其中該等排 應用於圖3 - 4之排程器。 T 較佳實例之詳細説明 在較佳實例之下列説明中，目前發明者所知之實現 明之最佳建構將詳細受到説明ϋ，該説明意欲做爲 對一特定實例之本發明概念之廣泛，一般説明，而非音欲 限制本發明於該實例所展示之概念，尤其是因爲熟悉:目關 技術領域者應可認知，參照該等圖形所展示及説明之特定 結構的許多變型與改變。 經濟部智慧財產局員工消費合作社印製 圖1展不一介面裝置晶片之方塊圖，該介面裝置晶片包含 基板10與整合於該基板之多個子裝置。該等子裝置是配置 成爲一上部組態與一下部組態，其中“上部，，組態（有時候稱 爲“進入’’）意謂相關於自資料傳輸網路輸入 進入晶片)之資料之該等元件，而“下部”(有二= 出”）組態意謂功能爲，以一向外方式（離開晶片或向下及進 入網路），傳送資料自晶片至資料傳輸網路之該等元件。資 料流程遵循上部與下部組態之對應配置；因此，圖1之系統 中存在一上部資料流程與一下部資料流程。上部或進入組 態組件包含一排列/解排列/排程器up (EDS-up)邏輯16， 多個多工MAC-UP (PMM-UP) 14,交換機資料移動器_up (SDM-UP) 18,交換機介面（SIF) 20,資料校準串列鏈路a -13- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） 1222012 A7 B7 五、發明說明（11 (DASL- A) 22與資料校準串列鏈路B (DASL_ B) 24。資料 鏈路更％整説明於前所參考之鏈路專利，且如果要更加瞭 解系統之此部份，請參考該文件。應可理解，雖然本發明 <較佳實例使用更完整説明於該專利之資料鏈路，但是其 他系統也可有利地用於本發明，尤其是支援相當高速之資 料流程與系統需求之系統，因爲本發明未受限於該等特定 輔助裝置，例如用於較佳實例之資料鏈路。 描述於系統之下部（或送出）組態之該等元件包含資料鏈 路DASL-A 26與DASL-B 28，交換機介面SIF 30，交換機 資料移動器SDM-DN 32，排列/解排列/排程器EDS-DN 34 與用於送出之多個多工MAC PMM-DN 36。基板1〇也包含 多個内部靜態隨機存取記憶體元件（s_ RAM)，一流量管理 排程器（TRAFFIC MGT SCHEDULER，也稱爲送出排程器） 40，與一較詳細説明於前所參考之npu專利之嵌入型處理 器組12。一介面裝置38藉由對應之DMU匯流排耦接至PMM 14，36。介面裝置38可爲適合用以連接至L1電路之任何硬 體裝置，例如乙太實體（ENET PHY)裝置，或非同步傳輸模 式設框裝置（ATM FRAMER)，其中前述二裝置皆是爲眾所 知且在業界通常可用於此目標之裝置範例。介面裝置之類 別與大小是由，至少一部份，本晶片與其之系統所連接之 網路媒體來決定。多個外部動態隨機存取記憶體裝置（D RAM)與一 S· RAM可供晶片使用。 雖然本文針對一些網路來特別説明，其中在相關交換與 選徑裝置以外之一般資料流程通過導電體，例如安裝於建 -14- 本紙張尺度適用中國國家標準（CNS)A4規格（210 x 297公釐） (請先閱讀背面之注意事項再填寫本頁) ▼裝---- 1T---------^^^1 - 經濟部智慧財產局員工消費合作社印製 1222012 五、發明說明（12 ) 築物之接線與電纜，但是本發明意欲其之交換機與元件也 可應用於無線環境。例如，本文所揭示之媒體存取控制 (MAC)組件可利用適當之射頻裝置來取代，例如利用 技術來製造等裝置，且該等射頻裝置將使所揭示之裝 置可直接連接至一纟線網路。當此種技術受到適當運用 時、，熟悉適當技術領域者可整合該等射頻組件至本文所揭 示之VLSI結構。此外，射頻或其他無線回應裝置，例如么工 外線（IR)回應裝置，可與本文所揭示之其他組件安裝於'一 翼以構成-叉換裝置，其中該交換裝置適用於無線網路裝 置0 經濟部智慧財產局員工消費合作社印製 箭號展示圖1所展示之介面系統内之一般資料流程 ENET PHY區塊38，經由DMU匯流排，所接收之來自— Ethernet MAC 14之資料訊框或訊息（有時候也稱爲封包或 資訊單元）是由EDS_UP裝置16置放於内部資料儲存緩衝器 訊框可辨識成爲正常訊框或導引訊框，而該等訊框接 著相關於多個處理器之隨後處理之方法與位置。在輸入單 元或訊框受到嵌入型處理器組之多個處理器之一處理器處 理之後，完成之資訊單元傳送至交換機，以傳送至一網路 處理器义進入側。-旦資訊單元在網路處理器之進入例受 到接收，則該等資訊單元受到嵌入型處理器組之多個處理 器（-處理器處理’且當該送出處理完成時，該等資訊單 元是由排程器40排程以離開處理單元1G，及經由pMM_DN 多工MAC 36與實體層38轉移至資料傳輸網路。 圖2是-可有利運用本發明之處理系統1〇〇之方塊圖。在 -15 本紙張尺度適用中國國豕標準（CNS)A4規格（21〇 X 297公爱 1222012 A7

經濟部智慧財產局員工消費合作社印製 1222012 A7 ____ B7 五、發明說明（15) 包含4時框。每一時框包含512時槽。每一時槽包含指向流 程佇列之一LIFO指標堆疊。任二時槽間之距離是頻寬之一 量度，且該値決定於時框。在較佳實例中，如圖4所示，每 一時框之間存在一縮放因數16。在較佳實例中，一持續時 間爲150奈秒之scheduler—tick受到選擇，因此在時框〇, 槽之距離表示在150奈秒内移動512位元組之頻寬，或大約 每秒270億位元，而在時框3, 一時槽之距離表示在心“斗毫 秒内移動512位元組之頻寬，或大約每秒6·67百萬位元。 -實例所用之每-時框之時槽數目與時框之數目是硬體 成本與設計複雜度之一折衷，且未意欲限制本發明之範 疇。熟悉相關技術領域者應可明瞭，在不脱離本發明之精 神之下，時框之各種組合，時框間之縮放因數與每一時框 之時槽數目皆可受到改變。 目前時間暫存器是-維持目前排程器系統時間之値之暫 存器。在每一 scheduler-tick中，此暫存器遞增一次。在較 佳實例中，目前時間暫存器之範園是選擇成爲以時間爲基 礎之排程器之範圍的四倍。當比較目前時間也發現於㈣ ㈣控制區塊之時間戳記欄位之一搁位（亦即 或NeXtGreenTime)時，這使得一目前時間捲繞可受到決 定。 / 運作 圖5以流程圖型態來顯示本發明之排程器之運作。目 標是用以顯示每一時框内之服務位置。在|曰 scheduler_tick中，目前指標所顯示之時槽受到檢視。 ---τ--------裝--------訂---------^9. (請先閱讀背面之注意事項再填寫本頁) -18· A7

1222012 五、發明說明（彳6 ) 發現β時槽是空的，則目前指標可前進至下一非空時槽， 或則進至對應於目前時間之時槽。請注意，因爲時槽間之 距離會隨著時框而變，所以目前指標是以不同速度來通過 每一時框，且同時“緊跟，，目前時間。如果發現該時槽不是 二的，則一候選流程佇列時框受到發現。每一時框獨立決 定是否發現一候選流程佇列時框。如圖4所示，一候選流程 仲列日暦是藉由使用-絕對優先權選擇法在該等候選時框 中選擇，其中編號最小之時框最先受到選擇。如圖4所示， 選擇順序是： (1) 時框0 (2) 時框1 (3) 時框2 (4) 時框3 最終之流程佇列選擇發生於該等日曆之間，如排程器結 構專利所述。當一候選流程佇列時框受到選擇時，自lif〇 堆疊中解排列該流程佇列指標。該流程佇列受到檢視及服 務，如排程器結構專利所述。如果在此解排列動作之後， 發現目前指標所顯示之時槽不是空的，則目前指標維持不 變。如果在此解排列動作之後發現目前指標所顯示之時样 是空的，則目前指標可前進至下一非空時槽，或前進至對 應於目前時間之時槽，或前進至一時槽，其中流程彳宁列服 務動作在該時槽中移動受到解排列之流程佇列。目前指# 受到移動該等可能距離中之最短距離。 圖3所示之排程器系統包含多個流程210，以時間爲基礎 -19- 本紙張尺度適用中關家標準（CNS)A4規格（210 X 297公^ --- ^·1--------tr--------- (請先閱讀背面之注意事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 經濟部智慧財產局員工消費合作社印製 1222012 A7 --- - B7__ 五、發明說明（17 ) 乏日曆220，230，250，加權公平佇列（WFQ)日曆24〇，與 標的埠佇列260。 ^ 流私2 10是用以維持時框之有序表列之控制結構，其中該 等時框基於指配來共用相同之系統特徵，換句話説，相關 使用者所選及付費之服務位準。該等特徵包含最小頻寬， 尖峰頻寬，最大努力頻寬與最大叢發大小服務品質（Q〇s)需 求。除了爲支援通訊系統之Q〇S而設定之流程佇列以外，較 佳實例需要針對下列目的定義之流程佇列：捨棄訊框（亦即 過滤之流量），與自網路處理器系統之送出至進入之訊框資 料的捲繞。 以時間爲基礎之日曆220，230，250是用以排程具有最小 頻寬及最大努力尖峰速率需求之封包。如圖3所示，以時間 爲基礎之三日曆是用以達成此目的：二日曆22〇，23〇是用 於最小頻寬，而第三曰暦250是用以限制流程佇列至一最大 努力最大尖峰速率（尖峰頻寬整形）。以時間爲基礎之二曰 臀220 ’ 230 ( —日曆220是辨識成爲低延遲服務或LLS，且 另一曰曆230是辨識成爲正常延遲服務或NLS)提供最小頻 寬’且可支援一最小頻寬q〇s類別内之不同服務類別（亦即 低延遲與正常延遲）。 加權公平佇列（WFQ)日曆240是用於最大努力服務，與最 大努力尖峰服務（當與該二以時間爲基礎之日曆220，230之 一曰曆共同受到使用時）。另外，WFQ曰曆240支援一佇列 加權’以允許支援一最大努力服務QoS類別内之不同服務類 別。在較佳實例中，存在4〇個此種WFQ佇列，而此數目對 -20- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ΊΡΤ --------裝--------訂--------- (請先閱讀背面之注咅P事項再填寫本頁) 1222012 經濟部智慧財產局員工消費合作社印製 A7 五、發明說明（18 ) 應於支援之媒體埠（輸出埠）之數目。選擇4〇個此種埠是硬 體成本與設計複雜度間之折衷，而非意欲限制本發明之範 轉。 在前所提及之每一該等日曆中，一指標（一流程識別）是 用以表示一流程佇列在該日曆内之位置。因此，流程〇在日 曆220中具有其之流程識別221，流程i在日曆23〇中具有流 程識別232並在WFQ 24〇中具有流程識別241，且流程 在日曆230中具有流程識別231並在日曆25〇中具有流程識別 25 1，其中所有流程識別皆是藉由箭號顯示於圖3。另外， 了把沒有，有一或二此種指標指向存在於此系統之多個日 暦之單一流程佇列。一般而言，一日曆之指標不表示未受 到啓始化或空之流程㈣。#一指向一流程仔列之指標（或 一流程識別）存在於系統之一特定日曆時，該流程佇列可稱 爲“位於”該特定日暦。 標的料列是用以維持-些訊框之有序表列之控制結 構，其中孩等訊框具有相同之埠目的地與優先權。在較佳 實例中，每一媒體埠（或輸出埠）獲得提供2優先權以允許支 援不同服務類別：一所謂之高優先權標的埠佇列，與一所 明（低優先權標的埠佇列。2優先權之選擇是硬體成本與設 計複雜度之折衷，而非意欲限制本發明之範疇。另外，'較 佳實例包含一分離之捲繞佇列272與一捨棄埠佇列27()。 以時間爲基礎之三曰曆220，23〇與25〇之每一曰曆皆包含 多個時框，且如圖3所示每一日曆包含四時框，其中該等時 框疋以重疊艾矩形來表示。圖4展示四時框，3⑽， -21 - 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） *----------裝 ---------訂--------- (請先閱讀背面之注咅？事項再填寫本頁) 1222012 A7 _____B7 ______ 五、發明說明（19 ) 與308以及一該等時框之一典型時序配置，其中第一時框 302 (標示爲epoeh〇)具有一排程器間隔之步階（在此情形中 (請先閱讀背面之注咅？事項再填寫本頁) 每150奈秒允許512位元組），第二時框3〇4具有16倍於第一 時框302之步階，且相對於第二時框3〇4，第三時框3〇6具有 相同比率，而相對於第三時框3〇6，第四時框3〇8具有相同 比率。以此方式，第一時框3〇2具有一高優先權（其受到排 程以接受服務之頻率是第二時框3〇4之16倍），進而產生一 服務優先權階層，其中該階層具有相關之成本遞增。一目 前指標（例如，針對時框302之312)相關於每一時框，以提 供一關於處理目前位於佇列之何處之指標。因爲本系統通 過諸時框會導致目前指標遞增，處理之方向是自較低時框 至較高時框。目前時間320與一排程器間隔330也展示於圖 4，且前二裝置驅動時鐘32〇以及驅動每一時框内之步階。 優先權選擇是一絕對優先權選擇，而此意謂，因爲在任 何區間只有-時框可受到服務，所以具有最高優先權之時 框受到服務。如果每一該等時框之目前指標指向_資料流 私，則編號最小之時框（ep〇ch0)將受到服務。如果時框〇無 需服務，則時框丨受到服務，接著_2受到服務，依此類 推。 經濟部智慧財產局員工消費合作社印製 圖6展示圖4之每-該等時框之位元的時間解析度。換句 話説，其告訴你目料間儲存器（一 23_位元計數器）之那些 位元相關於下文所述之每一該等時框。 圖7展示來自使用者之通訊之參數。所用之頻寬描緣於γ 抽’而時間則描繪於錄。使用者可指配—以箭號35〇來標 -22· 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） " -—- 經濟部中央標準局員工消費合作社印製 1222012 A7 --- - B7_____ 五、發明説明（21 ) 礎’決定佇列之下一服務之順序。 當一封包排列於一流程佇列，且該流程佇列加入一 WFQ 時，如前文參考之排程器結構專利所述，圖3tWFQ 240内 之位置是依照下列方式之一方式來決定。 1 ·增加至WFQ日曆之目前指標所顯示之位置。 2·增加至一位置，其中該位置緊接WFQ日曆之目前指標 所顯不之位置之前。 3 ·使用流程佇列之加權，QD，以決定自目前指標所顯示 之位置算起之距離。 在較佳實例中，流程佇列之加權是用以決定自目前指標 所顯不之位置算起之距離，其中流程佇列將位於該位置。 該距離可計算如下： 時槽距離= Min(QD* S)，1) 其中S是一可爲任何正整數値之縮放因數。在較佳實例 中，縮放因數S是16。 _§前時間至NextGreenTime之轉換

NextGreenTime是WFQ日曆240用以提供尖岭頻寬整形（連 同尖峰頻寬整形日曆）之時間戳記攔位。轉換目前時間成爲

NextGreenTime(在較佳實例中爲 NxtGT. V，NxtGT· E)需要 檢視流程佇列控制區塊之尖峰服務速率攔位。 在較佳實例中，PSD. E之値是用以決定NxtGT. V欄位之目 前時間所用之位元，如下所示： -24- 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐） J--------- (請先閱讀背面之注意事項再填寫本頁) 訂 1222012 A7 B7 PSD.E 0 1 2 3 目前時間位元 8至0 12至4 16至8 20 至 12 五、發明說明（22 ) 目前時間位元 8至〇 12至4 16至8 20 至 12

NxtGT.E是設定成爲等於之値。 jj^RedTime或NextGreenTime盥目前時間間之比較（遲於 比較） 在較佳實例中，下列步驟包含一方法，且該方法允許一 來自流程佇列控制區塊之時間戳記與目前時間之比較。 1.自目前時間中選擇位元來執行此比較。此設定需要檢 視要受到比較之時間戳記（NextRedTime* NextGreenTime) 之“dot E”攔位。 dot E 0 1 2 3 2.爲決定是否一“A”遲於“B，，，首先形成3之二補數，且 接著相加該結果與A，並忽略來自該運算之任何進位。各, 結果不是零，且該結果之最高有效位元是〇時，則 Β，否則Β遲於Α。 、 轉換NextRedTime或NextGreenTime成爲一以』^曰，爲芙礎 之日曆之一位，冒 土 25- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ----;---------裝--------訂--------- (請先閱讀背面之注咅？事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 1222012 A7 _B7_ 五、發明說明（23 ) 流程佇列控制區塊之時間戳記欄位充當一方法之一部 份，其中防止一流程佇列達反其之服務參數。在較佳實例 中，“ dot E”欄位顯示時框且“ dot V”欄位顯示自時框内之 位置0算起之距離。 當一流程達反尖峰速率時之NexTGreenTime計算（使用

NextGreenTime做爲基底） 在較佳實例中，當一流程達反其之尖峰速率時， NextGreenTime之計算是藉由檢視BCI來決定，其中決定封 包長度（以位元組爲單位），尖峰服務速率，與 NextGreenTime之目前値。在圖8中，FL表示藉由BCI來決定 之訊框之位元組長度。該等程序區塊説明如下。 程序2是，當NextGreenTime與尖峰服務速率之縮放因數 (dot E)相同時，一時槽距離計算（Temp)。 程序4是，當尖峰服務速率之縮放因數大於 NextGreenTime之縮放因數時，一時槽距離計算（Temp)。 程序5是，當尖峰服務速率之縮放因數小於 NextGreenTime之縮放因數時，一時槽距離計算（Temp)。 程序7是，當時槽距離（Temp)大於目前縮放因數之容量 (在較佳實例中，dot V値不能超過5 11)時，NxtGT. V與 NxtGT.E値之計算。 程序10是，當時槽距離（Temp)允許目前縮放因數之降低 時，NxtGT. V與NxtGT. E値之計算。因爲縮放因數愈小，則 時間基底愈準確，所以這樣較好。 程序11是，當時槽距離（Temp)無需或未允許目前縮放因 -26- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） (請先閱讀背面之注意事項再填寫本頁) _ --------訂·----- 經濟部智慧財產局員工消費合作社印製 1222012

經濟部智慧財產局員工消費合作社印製 五、發明說明（24 ) 數之改變時，NxtGT. V値之計算。NxtGT.E之値維持不變。 皇_·一流程未立反尖;^速率時之NexTGreenTime計算（使用 ϋ前時間做爲基底） 在較佳實例中，當一流程未達反其之尖峰速率時， NextGreenTime之計算是藉由檢視BCI來決定，其中決定封 包長度（以位元組爲單位），尖峰服務速率，與目前時間， 且展示於圖9。該等程序區塊説明如下。在圖9中，FL表示 藉由BCI來決定之訊框之位元組長度。 考王序21是一時槽距離計算（Temp)。 基於尖峰服務速率所用之縮放因數，程序區塊23，25， 27與29藉由目前時間暫存器之位元來指配基底時間之値 (BaseT) ° NextGreenTime將是藉由時槽距離，縮放因數與 基底時間來決定。 程序3 1是’當時槽距離（Temp)大於目前縮放因數之容量 (在較佳實例中，dotV値不能超過511)時，NxtGT. V與 NxtGT.E値之計算。 程序34是，當時槽距離（Temp)允許目前縮放因數之降低 時，NxtGT· V與NxtGT.E値之計算。因爲縮放因數愈小，則 時間基底愈準確，所以這樣較好。 程序35是，當時槽距離（Temp)無需或未允許目前縮放因 數之改變時，NxtGT. V與NxtGT.E値之計算。 MBS賺取信用之針笪 在較佳實例中，一在使用中（QinUse= 1)並具有非零之最 大叢發欄位之流程佇列，當該流程佇列是空的時，可赚取 -27- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ---s---------裝--------訂---------^9. (請先閱讀背面之注咅？事項再填寫本頁) 1222012

A 五、發明説明（25 ) 符！己。當—封包排列至該空流程件列時，腦〜仙搁位攻 到更新。爲決定赚取之符記之數目，如版仍咖與目前二 間受到檢視，且展示於圖1〇。 以NeXtRedTimeK用之縮放因數爲基礎，在程序區塊 3〇2 ’ 303，305與307中目前時間之位元受到選擇，以產生 一縮放時間（TimeA)，來用於決定該流程佇列已空了多 間。 ^ 決策區塊308決定是否TimeA遲於NextRedTime時間戳記襴 位所顯不之時間。藉由使用NextRedTime以達成此目的要 求，在流程佇列之下一可能排程時間之後，流程佇列維持 空白。如果TimeA未遲於NextRedTime，則不採取任何進— 步動作。 決策區塊309處理計時器捲繞情形，且允許持續時間 (TimeT)之計算，且在該持續時間内流程佇列在程序區塊 3Π與310中累積符記。 程序區塊313’ 315與316是MBSCredit. V之最終計算。決 策區塊312與314決定是否，由於用以定義MBS欄位之縮放 因數，TimeT需要調整。 !用之MBS信用之計算 經濟部中央標準局員工消費合作衽印製 1----Φ! (請先閱讀背面之注意事項再填寫本頁) MBSCredit之新値是藉由MBSCredit之目前値，用以決定 訊框長度之BCI，與持續服務速率來決定。使用持續速率是 由於當計算MBS値時所使用之方法（該方法免除方程式之複 雜除法）。在較佳實例中，MBSCredit可爲負値。該等程序 區塊説明於下文。在圖11中，FL表示藉由BCI來決定之訊框 •28- 本紙張尺度適用中國國家標準（CNS〉A4規格（210X297公釐） 1222012 A7 五、發明說明（26 ) 之位元組長度。 程序區塊402 ’ 404與405決定用於長度爲ρχ之訊框之符祀 數目。決策區塊401與403是用以決定是否，由於用以定義 MBSCredit攔位之縮放因數，Temp需要調整。 程序區塊406藉由所用之符記數目來調整MBSCredit V^ 値0 流程佇列控制區塊老化 使用縮放因數於流程佇列控制區塊可降低用於時間戳記 搁位之維護所為之硬體。爲準確決定何時一時間戳記過老 而不再相關，需要一方法來顯示該時間戳記與餘値襴位是 無效的。圖12與13展示一用以標示時間戳記不再有效之流 程佇列控制區塊之方法。 一目前在使用中（QinUse= 1)之所有流程佇列控制區塊之 表列增加至排程器結構專利所述之排程器系統。熟悉本技 術領域者應可理解有許多方式可用以維護此種表列。 在較佳實例中’時間戳記之dot V欄位延長2位元。當時 間戳記欄位受到更新時，該等額外位元是自目前時間指標 取得。自目前時間指標取得之該等位元是藉由d〇t E攔位之 値來決定，如圖6所示，且顯示如下： I Ί 裝-------訂--------- C請先閲讀背面之注意事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 dot E 所用之目1 0 10至9 1 14 至 13 2 18 至 17 3 22 至 21 -29- 本紙張尺度適用中國國家標準（CNS)A4規格（21〇 X 297公釐） 1222012 經濟部智慧財產局員工消費合作社印製 A7 五、發明說明（27 ) 一計時器是用以決定何時檢查流程伶列控制區塊之程序 發生。請參看圖12，該方法開始於檢查一 “老化服務間 隔”。當此爲眞時，程序繼續並自老化表列5〇2中選擇一流 程仔列控制區塊（q C B)。程序前進至5 0 3以檢查選擇之流程 佇列控制區塊之QinUse欄位。 如果流程作列控制區塊未在使用中，則程序返回至$ 〇 1， 並等候下一服務間隔，否則程序繼續，並檢查持續服務速 率襴位504與QinRed欄位505。如果流程佇列具有一指定之 持續服務速率，且流程佇列不是位於LLS或NLS曰曆 (QinRed=0)，則在506中決定是否出現老化。針對 “TestAge”所採取之動作説明於下文。 如果流程佇列未具有一指定之持續服務速率，則在5〇7中 檢查尖峰服務速率欄位。如果沒有尖峰服務速率受到指 定，則程序在501中繼續並等候下一服務間隔。如果一尖+ 服務速率受到指定’則流程仵列控制區塊受到檢視，以決 定是否流程佇列位於一 WFQ日暦508，或位於尖岭頻寬整形 日暦509。如果流程佇列不是位於前述二日曆，則程序返回 至501，否則在510中決定是否出現老化。針對“ 丁如八#，，所 採取之動作説明於下文。

TestAge，如圖13所示，是做爲流程佇列控制區塊之時間 戳記攔位之輸入，與目前時間。其返回以處理QinUse欄位 之狀態之更新。在流程圖5中，此結果是用於512與513，以 更新流程作列控制區塊，及自老化表列中移除流程件列控 制區塊。 -30- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） —：---------裝--------訂--------- (請先閱讀背面之注咅？事項再填寫本頁) 1222012 經濟部智慧財產局員工消費合作社印製 A7 B7__ 五、發明說明（28 ) 請回到圖13，TestAge程序使用縮放因數e來決定，目前 時間之那些位元組是用以決定是否時間戳記欄位太老而無 法維持之有效性。區塊600至606完成此工作。 在606與607中繼續，dot V攔位之高順序位元（如前文所定 義並展示於圖3之MM位元）與目前時間之選定位元受到比 較。6 0 7與6 0 8之測試決定是否相關於時間戳記之時框，自 最後一次受到更新算起，已捲繞超過一次。如果多於一捲 繞已發生，則時間戳記不再可使用，且時間戳記欄位是藉 由設定QinUse位元成爲零之動作來標示成爲無效，否則 QinUse位元維持不變（區塊609，610)。 加權公平佇列（WFQ)日曆是用於所謂之‘‘最大努力，，服 務，且當與以時間爲基礎之日曆一起受到使用時，一所謂 之“最大努力尖峰，，服務。換句話説，一最大努力服務未取 得保證之頻寬（其中每單位時間可提供X位元之頻寬），而是 與其他使用者競爭在保證頻寬顧客受到滿足以後剩餘之頻 寬。這是一低於保證頻寬之服務位準，且通常遠較便宜。 所謂之“最大努力尖峰，，服務，對於超過使用者訂購之保證 服務位準之一資源需求，提供剩餘頻寬之競爭性共享。所 以使用者可購買每秒10百萬位元之服務，以及一額外之尖 峰每秒5百萬位元之最大努力服務，以獲得具有總計每秒j 5 百萬位元之尖峰服務速率之服務（最後每秒5百萬位元，只 有在其是可供使用，且一與加權公平佇列之其他使用者之 公平共享允許之下，方會受到提供）。 另外，WFQ日曆支援一佇列加權，且該佇列加權可支援 -31 - 本紙張尺度適用中國國家標準（CNS)A4規格（21〇 X 297公釐） ； 裳--------訂---------^9. (請先閱讀背面之注意事項再填寫本頁) 1222012 A7 B7 五 經濟部中央標準局員工消費合作社印製 發明説明（29 ) 一最大努力服務QoS類別内之不同服務類別。在本文中，/ 佇列加權是一相對性優先權，且該優先權是基於一給定使 用者之服務位準來指配給该使用者。作列加權相關於參戶系 此系統所述之加權公平佇列系統之服務間的延遲大小。在 較佳實例中，如圖3所示，存在40個此種WFQ日曆，對應於 支援之媒體埠之數目。40個此種埠之選擇是一任意設計遽 擇’其中涉及硬體成本與設計複雜度間之折衷，而非意欲 限制本發明之範_。 如排程器結構專利所述，一週期（或時鐘區間）是定義成 爲一 scheduler—tick ;這等於150或165奈秒，視受到存取之 硬體之回應時間而定，但是這可爲較大或較小之週期，視 叹计參數與硬體功能而定。在一 scheduler—tick中，一流程 佇列雙到選擇以接受服務。當具有最小頻寬規定（持續服務 速率）之所有流程仔列不需要服務（亦即，排程器所管理之 剩餘頻寬可供WF Q日暦使用）時，所述之選擇演算法導致 WFQ日曆受到選擇。換句話説，如果以時間爲基礎之佇列 2 2 0 ’ 2 3 0受到排程並有資訊要傳送，則他們是在每一時鐘 區間内受到服務；否則，WFQ佇列240是在時鐘區間内受到 服務。相對於以時間爲基礎之排程器，其中網路處理器之 總體最小頻寬可受到管理，每一 WFQ曰曆管理針對一標的 埠之最大努力頻寬。WFQ日曆或佇列240之目標是與競爭之 流私佇列公平共車此最大努力頻寬。這是藉由下列方式來 元成·考慮一受到選擇以接受服務之流程仵列所傳送之位 元組數目，與基於所傳送之位元組之數目，在該日曆内自 -32- \紙張尺度適财關家標準（CNS〉A#規格（21GX297公羡） Ί— -II -- ·· - -1 - - I m —in —I! II 广请先閲讀背希之注意事項真填寫本買〕 1222012 經濟部智慧財產局員工消費合作社印製 A7 五、發明說明（3〇 ) 其目前位置開始移動該流程佇列—距離。換句話説，在一 —uler—tic_間一流程傳送之位元組愈多，在下一服務 ^前日暦愈移動向上（且愈多干擾流程，因而愈長之週 期）〇 ^幸又佳實例中，如圖14所示，一 WFQ日麼2術包含512 、㈢每時槽包含一指向流程仵列之LIFO指標堆疊。用 於一實例之時槽數目是硬體成本與設計複雜度間之折衷， 而非意欲限制本發明之範嘴。 仍請參看圖14，目前時間暫存器是—維持目前排程器系 、充時間之値（暫存益。在每_触中此暫存器遞 增-次。在較佳實例中，目前時間暫存器之範圍是選定成 爲以時間爲基礎之曰曆之四倍。當比較目前時間與發現於 泥程仔列控制區塊之該等時間戳記欄位之-欄位（亦即 NextG⑽Time)時’這允許決目前時間捲繞。 目前指標是用以顯示WFQ日曆内之服務位置。相對於以 時間爲基礎之曰曆，目前指標無關於排程器系統時間。 運作 如圖15之流私圖所不，在每一 期間，每一 標的埠仵列之狀態首先受到檢視。每一該等㈣作列相關 於一對^因此WFQ埠〇相關於_較高優先權埠〇與—較低 優先權埠〇。如果標的埠仵列之臨限値在線262已受到超 越，則WFQ日暦在scheduler—触期間不會採取進一步動作 (此系統採用-種回壓來限制輸出，以防止系統無法處理之 訊框焚到傳出）。如果標的痒仵列之臨限値尚未受到超越， -33 - ‘紙張尺度適用中關家標準（CNS)A4規彳i (21G x 297公髮_ ^ 裝--------訂---- (請先閱讀背面之注意事項再填寫本頁) 經濟部智慧財產局員工消費合作社印製 1222012 五、發明說明（31 貝j目則心彳承所顯不心時槽接著受到檢視。如果發現該時槽 疋工的’則目則指標可前進至下—非空時槽以尋找一候選 流程仔列WFQ。如果發現所有時槽皆是空的，則目前指標 未又到改，交，且未發現候選Wfq。如果在此一日曆内發現 篇時槽疋非空的，則儲存於此時槽之流程佇列位址是針對 此蜂〈候選WFQ。該等4〇個WFQ日曆之每一曰曆同樣能夠 找到一針對其之相關標的埠佇列之候選wfq。 視輒的埠臨限値之目標是控制用以指配封包自WFq曰 暦至標的埠佇列之速率。因爲在附著之媒體所指定之速率 下標的埠佇列將耗盡，所以檢視標的埠之狀態是否超過臨 限値提供一機制，以確保未依照一超過標的埠之媒體頻寬 之速率來指配封包給標的埠。在較佳實例中，臨限値是定 義成爲位元組之量度，且臨限値應設定成爲至少針對該媒 體所定義之最大傳輸單元（MTU)，以確保正確運作。 因爲本發明之一目標是提供一結合最小頻寬之最大努力 頻寬排程之方法，其中單一流程佇列同時位於一以時間爲 基礎之日曆與一 WFQ日曆，前述機制爲正確運作所必需。 最終之流程佇列選擇發生於所有日曆之間（以時間爲基礎 之日曆與WFQ日暦），如前所參考之排程器結構專利所述。 當一流程件列WFQ日暦受到選擇時，該流程彳宁列指標自 LIFO堆疊受到解排列。該流程仵列受到檢視及服務，如排 程器結構專利所述。如果在此解排列動作之後發現目前指 標所顯示之時槽不是空的（亦即至少還有一輸入項存在於該 時槽），則目前指標未受到進一步修改。如果在此解排列動 -34 ‘紙張尺度適用中國國家標準（CNS)A4規格（210 x 297公釐）

經濟部智慧財產局員工消費合作社印製 1222012 A7 B7__ 五、發明說明（32 ) 作之後發現目前指標所顯示之時槽是空的，則目前指標將 前進至下一非空時槽。如果發現所有時槽皆爲空的，則目 前指標未受到改變。 熟悉本技術領域者應可理解，一 WFQ日曆使得所有指配 給他之流程佇列共享可用之頻寬。另外，藉由指配一加權 給一流程佇列，指配給每一流程佇列之頻寬之相對比例可 受到改變。這是藉由一位置之計算來完成，其中一受到服 務之非空流程佇列置放於該位置。一低加權因數對於一給 定之訊框長度提供更頻繁之服務，而此意謂相關之流程針 對下一服務沿“階梯”向上移動之距離，短於一高加權因數 針對相同之訊框長度所移動之距離。同樣地，一提供較短 Λ框之流程沿階梯向上移動之距離，大於一具有相同加權 因數但提供較短訊框之流程向上移動之距離，而此意謂具 有較短訊框之流程將接受較頻繁之服務，在相同之優先權 或加權因數之下。 WFO距離計笪 一距離計算是定義成爲一流程佇列在日曆内自其受到解 排列之位置開始受到移動之時槽數目。在較佳實例中， WFQ曰曆之距離計算具有下列型態： 時槽距離=Max(Min(((訊框長度）*QD*K)， max—distance)，1) 其中時槽距離是一整數，訊框長度是以位元組爲單位來測 量’ QD是指定於流程佇列控制區塊之佇列加權， max 一 distance是定義成爲日曆之時槽數目減一，且κ是一指 -35- 本紙張尺度適財關家標準x 297公¥)_ -T---------裝--------訂--------- (請先閱讀背面之注意事項再填寫本頁) 1222012 五、發明說明（33 配給標的埠之縮放因數。κ之規定是藉由標的埠之MTU， WFQ日暦之時槽數目，與所要之QD範圍。對於較佳實例， 建議使用下列之K値： MTU (位元組）κ 2048 9216 64分之一 256分之一 經濟部智慧財產局員工消費合作社印製 16384 1024 分之一 在不脱離本發明之精神下，可選擇其他之尺値。 藉由較佳實例之前述説明並參考附圖，熟悉相關技術領 域者應可明瞭本發明之許多修改。例如，基於訊框大小之 加權及儲存之加權因數可藉由其他公式來取代。一日曆内 <時槽數目與每一埠之日曆數目可受到改變，以涵蓋系統 之架構。在不脱離本發明之精神之下，時框之數目與他們 之每一步階之距離，目前時間暫存器之大小， scheduler一 tick率皆可受到改變。此外，在不脱離本發明之 精神之下，可對於系統建構與優先權系統進行許多變更， 且各種演算法可用以決定優先權。另外，本發明之一些特 點可在無對應使用其他特點之下受到使用。因此，較佳實 例之前述説明應視爲只是做爲本發明之原理之示範，而# 本發明之限制。 —4--------·裝——訂--------- (請先閱讀背面之注意事項再填寫本頁) -36-

Claims (1)

1222012 ΐ __號巾請案 AS 中文申請專利範圍替換本(93年2月）％ li： ^ L A ____ S8s 六、申請專利範圍 1· 一種移動資訊單元之裝置，包含： 一以時間為基礎之日曆，該日曆以關於多個來源之儲 存資訊為基礎，處理在一資料通訊系統中自該等多個來 源傳送至多個目的地之資訊單元； 一無關於時間之日曆，該日曆以關於多個來源之儲存 資訊為基礎，處理在一資料通訊系統中自該等多個來源 傳送至多個目的地之其他資訊單元；與 一週期性產生一信號之計時器，該信號移動單一資訊 單元自該等曰曆之一曰曆至一輸出目的地，其中該單一 資訊單元是以儲存之規則為基礎來選擇。 2·如申請專利範圍第丨項之裝置，其中該無關於時間之日 曆處理資訊單元流程，置放每一流程於一仵列，及在服 務該流程之後，移動該流程至該佇列之一不同位置，且 進一步包含一機制，以決定是否一流程已在該以時間為 基礎之日曆中具有一位置，及防止一在該以時間為基礎 之曰曆中已具有此種位置之流程，由於斷連與再連，在 該以時間為基礎之日曆中獲得一更佳位置。 3·如申請專利範圍第丨項之裝置，其中該無關於時間之日 曆處理資訊單元流程，置放每一流程於一佇列，且提供 一序列之訊框以等候移動，一加權因數與每一訊框之^ 小，與一機制，其中該機制，在該無關於時間之日曆移 動一訊框之後，基於該訊框之加權因數與訊框大小^ 算對應之流程之一新位置。 w 4. 一種置放資料流程之方法，包含下列步驟：

成單元在一資料通訊系統中自多個來源傳送至多 個目白h 士丄. 、、、也時，依序置放資料流程於佇列以接受服務； 、、、疋否一資料流程在該等件列中具有一先前位置； ^ 果為資料流程在該等佇列中具有一先前位置，則決 疋是否—π r 、 可雙到指配之新位置優於該先前位置； 果可爻到指配之該新位置並未較優，則使用該先前 r置來處理該流程；與 t果琢先前位置未優於可受到指配之該新位置，則使 疼新位置來處理該流程。 A移動資訊單元之方法，包含下列步驟： 個=資訊單兀在一資料通訊系統中自多個來源傳送至多 、的地時，依序置放資料流程於佇列以接受服務； 資：收關於準備就緒可供處理之每一資訊單元之優先權 母一貧訊单元之優先權資訊為基礎，置放等 ==供處理之每—資訊單S於許多❹㈣列之一 … 其中一佇列是以時間為基礎，而另一佇列 是無關於時間； 力廿列 系列之時鐘循環之每一循環 對於 集合為基礎來選擇該等停列之-件二處儲理存7則 對於-系列之時鐘循環之每一循環，以 礎自-選定之仵列選擇-資訊單元以進行處理：為基 傳送所選之資訊單元至一目的地。 ’與 如申請專㈣圍第5項之方法，其中對於U之時鐘

本紙張尺度適财® S家料(CNS) A^i72l〇X297公發）

撰:〈ί、循％ ’以—演算法為基礎自—選定之佧列中 ' 貝訊單元以進行處理之該步驟進一步包含：自一 加f公平㈣來進行選擇，且以資訊單元之大小與選定 早元之加權因數為基礎，計算該加權公平佇列之一 新位置。 移動資訊單元之方法，包含下列步驟： 當資訊單元在一資料通訊系統中自多個來源傳送至多 固目的地時’依序置放資料流程於仵列以接受服務； 以儲存I規則為基礎，決定是否允許—資料流程之尖 峰叢發傳輸，其中包含： 計算一資料流程之一啟始信用； 隨著時間之流逝，且當資料之流動率維持低於針對 孩資料流程所建立之一臨限值時，增加該信用； 隨著時間之流逝，且當資料之流動率超過該臨限值 時’降低該信用；且 使用該信用值來決定是否尖峰叢發傳輸可在任何給 定時間受到允許。 -3- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 1222012 第090106410號申請案 ； 中文圖式替換頁(93年2月） % : 心

1222012 第090106410號申請案 中文圖式替換頁(93年2月)

Scheduler Tick 330 丨320 ^目前指標 C 流程織別 後進先出 cn ………丨丨……………. ,岑商：3 」νφ=4096*150 命 #7512谇>貧 '— 目前指標 r G 流程識別’ |後進先出 ϋΐ —Λ '306 ;命2 f ®"256Μ50 命 f>/512^;£*f '—1目前指標 r C 流狂織別 後進先出 ΟΊ «λ \π^ί r孟^ 丨I f3&!=16*50 命 #7512 命·；d —目前指標 - 3f2、 r C 流程織別 αι \πωο^ 丨答i»oi 哞课N150命f>/512谇