TWI263429B - System and method for correlated token bucket shapers - Google Patents

Description

1263429

五、發明說明（1) 【發明所屬之技術領域】 本發明係有關於-種符記儲存調節器之系統及方法 特別是有關於一種相關式符記儲存調節器之系統及方法 【先前技術】 §月參照弟一圖，其為一習知符記儲存調節器之系統示 意圖。在本範例中係以三組符記儲存調節器所組成之系统 做說明’然不限於此。符記產生器（token generat〇r) 110、120及130分別產生對應的符記（t〇ken) 118、128及 138，而此符記1 18、128及138係分別對應儲存於符記儲存 區（token pool) 112、122及132。其中符記儲存區112的 流虿等級（t r a f f i c c 1 a s s)係對應於符記產生器丨丨〇的流量 等級，藉此提供存放符記產生器丨丨〇所產生的複數個符記 11 8 ’同理’類似的對應關係存在於符記儲存區丨2 2與符記 產生器1 2 0之間及符記儲存區1 3 2與符記產生器1 3 0之間， 因此符記儲存區1 2 2及1 3 2分別提供存放符記產生器1 2 〇所 產生的複數個符記1 2 8及符記產生器1 3 0所產生的複數個符 記138。而封包佇列（packet queue) 114、124及134係分 別對應於符記儲存區11 2、1 22及1 3 2，換句話說，當封包 "ί 丁列11 4 4人傳送一封包貧料時，則須取得符記儲存區1 1 2所 儲存的一符記11 8才可將此封包資料輸出於網路傳輸線丨J 6 上’而類似的操作關係存在於封包佇列1 24與符記儲存區

1263429 五、發明說明（2) 1 2 2所儲存的符記1 2 8及封包佇列1 3 4與符記儲存區1 3 2所儲 存的符記1 3 8之間。因此，一符記產生的速率（通常與流量 等級成正比）往往決定一網路資料傳輸的速率。上述之相 關應用技術可參考 Ε· P. Rathgeb， ’’Modeling and performance comparison of policing mechanisms for ATM networks，丨丨 IEEE J· Sel· Areas Commun·，vol. 9, no· 3， pp. 325-334， April 1991. 'Traffic management specification, version 4.0， ATM Forum/95-0013R8， Oct· 1995. 、 J. Heinanen and R.

Guerin,丨丨 A single rate three color marker，丨丨 ietf， rfc 2697， Sept· 1999· 、T· Finland and R· Guerin， nA two rate three color marker,” ietf, rfc 2698，

Sept· 1 999·、Α· K· Parekh and R· G· Gallager，丨丨 A generalized processor sharing approach to flow control in integrated services networks: The single-node case," IEEE/ACM Trans. Networking, vol. 1, no. 3， pp· 344-357， June 1993·及J· C. R Bennett and H· Zhang，丨丨 WF2Q: Worst-case fair weighted fair queueing，丨丨 IEEE Infocom，March 1 996· 等資料’此部份皆為習知之技術應用，故在此不再累述。 請再參照第一圖，假設當封包彳宁列1 2 4的封包個數遠 多於符記儲存區1 22所儲存之符記1 28的個數時，此狀況表 示封包彳宁列1 2 4所屬的流量等級係處於傳輸延遲的情況，

1263429

五、發明說明（3) 若在此同時，封包佇列114因沒有任何的封包需要傳送， 且此情，已持續一段時間，則符記儲存器112可能會因符 舌己產生器1 1 0持續加入的符記丨丨8而使得 ⑴，進而造成符記產生器110之後所產生子的符記118 :ΐ f 1 ng)，此狀況表示封包仔列114所屬的流 里#級係處於傳輸空閒（idle)的情況。 ，觀上述，在現有的文獻中，不論是多流級 , traJfrclasses) ^ ^ ^ * 論或改進上述所產生的情;兄，因此寥 於以上所述之符記儲存調節器之 需要持續發展新的改良李雜及古土、，±石决的缺點貝有 最二:分享各流量的傳輸頻寬、如何維持各 机里的最小傳輸頻寬以及如 士 域必然會遭遇的問題，& 各付§己4 ’疋此技術領 也疋本發明所要解決的問題。 【發明内容】 鐘於上述之發明择旦& 器之系統及方法；藝中的符記儲存調節 本發明提供-種相關式以傳輸頻寬等問題。 此改良習知技藝中的諸項^存调即益之系統及方法，藉 本發明提供一種相關式符記儲存調節器之系 統，藉此

$ 7頁 1263429 五、發明說明（4) 分享各流量等級之間的頻寬，㈣& 寬給低流量等級的頻寬。 +阿机ϊ等級的頻 本么月提供一符圮放置模組，並依各 況，，置/儲存各流量等級的符記，藉^健存區的狀 的頻寬。 ’政利用各符記 本發明提供一種相關式符記儲存調節 分旱各流量等級之間的頻寬。 °°之方法，藉此 根據 Is之糸統 記，其中每一該 符記；複 以上所 包含 一符記放 儲存的一 存區之一 流量等級 存區之流 溢滿。 數個符 置模組 符記儲 適當的 係等於 量等級 述，本發明提供一種相關式符 符=符記產生器，用以m;;:;: 子。己產生态係以一週期時間產 記：存區，用以對應儲存該些符記對2 收該些符記，並在任一該符記所對應 將該符記儲存於該些符記； 寸3己儲存區’其中該適當的符記儲存區之 及/或低於該符記所對應儲存的該符 ，且該適當的符記儲存區之儲存空間尚未 本發明更提供一種相關式符記儲存調節器 B ·接收複數個符記，其中該歧符 / ，匕 器所對姦4 Λ —何‘你由複數個符記產生 、心生，u及對應儲存該些符記於複數個符記儲存

第8頁 1263429 五 區 發明說明（5) 將該ίϊ:!一該符記所對應儲存的-符記儲广「 其中兮ί存於該些符記儲存區之H — 滿時’ 符適當的符記儲存區之流量耸幼孫二的付記儲存區， tσ己所對應儲存的爷符 里4、，及係專於及/或低於該 符勾处‘ 仔]4付冗儲存區之流詈笠紐 己儲存區之儲存空間尚未溢滿。4、，及，且該適當的 【實施方式】 細插述外，本私二：! w I砰細描述如下。然而’除了詳 本發明的r η 還可以廣泛地在其他的實施例施行，且 且，為楹：不受限定，其以之後的專利範圍為準。並 部分：更清楚的描述及更容易理解本發明，圖示内各 度之::;依照其相對尺寸繪圖，某些尺寸與其他相關尺 列已經被誇張；不相關之細節部分也未完全繪出， 乂永圖示的簡潔。 音明參照第二圖，其為本發明之一較佳實施例的系統示 2 m j在本實施例中係以三組相關式符記儲存調節器所組 之系統做說明，然不限於此。符記產生器2 1 0、2 2 0及 30 ’係用以週期產生對應的符記218、228及238。其中， ^述產生符記218、228及238之週期，可以是彼此相同、 3分相同，或者是彼此不同，而符記218、228及238的流 里等級係分別對應於符記產生器21 〇、220及230的流量等 級’且符記產生器210、220及230的流量等級，可以是彼

第9頁 1263429 五、發明說明（6) ΐ”：分㈣，或者是彼此不同。-般而言，流量等 二4问/則子有愈多的網路資源，例如較高的網路頻寬 即產生符記之週期較短）、較佳的傳輸品質等。 〇符記放置模組240，接收符記218、228及238，並對庳 =存=符記儲存區212、222及232，藉此提供對應的封包 I歹’ 4、224及234傳送封包於網路傳輸線216、226及236 、、备鉍二I危當符記儲存區212因符記218儲存的速度大於所 :、&、、又而造成溢滿時（即先前所謂之傳輸空閒的情 j六。付°己放Ϊ模組則將之後所產生的符記2 1 8放置於符記 儲存區2 2 2，藉此合直炫$ 9 1 Ο α Αμ ^ 區？99沾泣旦够刀子付5己2 1 8所此承載的頻寬給符記儲存 :$抓里專級；而當符記儲存區222也溢滿時，則將之 承載的頻寬給符記儲存區2 32的流量等級；而當符 :己儲存區232也溢滿時，則將之後所產生的符記218丢= = 一 Ϊ合的符記儲存區之情況，因而此適合 =付j存區在此情況下係一空項目（empty 土㈣。同 嘴乾二=Ϊ儲Ϊ區222因符記21 8及222的儲存速度大於所 W斤速又冰而造成溢滿時（即先前所謂之傳輸空閒的情 ϊ V,：;：" ί ： ： ：] II ^ 後所產生的符記228丢棄，即所謂的找 τ ^將之 儲存區之情況’因而此適合的符記儲存區在久:= 1263429

在此要特別說明的是 F、、兴、分η 士 田视$导級較高的一蒋今仲十 滿時’則流量等級相 己錯存 量等級所溢滿的符用以儲存相等或較高流 明示音丄用二二記儲存區所示的符記數量僅為二 T-之用’並非用以限定其等之儲存數量。 巧兄 請 圖。在 些符記 關係包 記產生 同、部 大之流 應儲存 包含相 付記儲 適當的 係等於 量等級 參照第三圖，其為本發明 步驟叫η …,十知月之較佳實施例的流程 ::310 ’付,己放置模組接收複數個符 合相πS堃，王斋所對應產生，而對應產生的 :相同流Ϊ專級的關係。在本實施例中 态所對應產生一符記之一 $ a _ 人 分相同，或者是姚h门 間可以是彼此相 j次者疋彼此不同。一般而言，頻甯兩花俞 量等級，其產生傳却夕、网&人_ 頭見而禾〜 ' 週J愈短。在步，

該些符記於複數個符圮俅在 驟320 T η 4曰& 己儲存區，而對應儲存的關係 冋流量等級的關係，並在任一 碲仔扪 尨Ρ、*、史η士 》 付目己所對應儲存的〆 存&溢滿％，將该符記儲存於該些 ^& /*.Jy r— 4+ _L. _ 付 °己儲存區之 ^己儲存區。其巾該適當的符記料 及/或低於該符記所對應儲存的該符記儲存|區里之流 ’且戎適當的符記儲存區之儲存空間尚未溢滿；而

第11頁 1263429 五、發明說明（8) 當該適當的符記儲存區係一空項目（empty item)時，丟棄 該符記。 以上所述僅為本發明之較佳實施例而已，並非用以限 定本發明之申請專利範圍；凡其他為脫離本發明所揭示之 精神下所完成之等效改變或修飾，均應包含在下述之申請 專利範圍。

第12頁 1263429 圖式簡單說明 以及 第一圖係習知符記儲存調節器之系統示意圖； 第二圖係本發明之一較佳實施例的系統示意圖 第三圖係本發明之一較佳實施例的流程圖。 主要部分之代表符號： 110 112 114 116 118 240 120 122 124 126 128 130 132 134 136 138 210 212 214 216 218 2 2 0、2 3 0 符記產生器 222、232 符記儲存區 2 2 4、2 3 4 封包佇列 2 2 6、2 3 6 網路傳輸線 228 、 238 符記 符記放置模組

第13頁

Claims (1)

1263429 六、申請專利範圍 1 · 一種相關式符記儲存調節器之糸統’該相關式符—己儲存 調節器之系統包含： ： 複數個符記產生器（t 〇 k e n g e n e r a t 〇 r )，用L…a π M產生複數 個符記（token) ’其中每一該符記產生器係以—週期時 間產生一對應的符記； ° τ 複數個符記儲存區（t 〇 k e η ρ ο ο 1 )，用以對廉紗— J馬儲存該些符 吕己，以及 一符記放置模組（token placement module)，接收今此 符記，並在任一該符記所對應儲存的一符記儲存區^ (ful 1 )時，將該符記儲存於該些符記儲存區之一 符記儲存區。 、田幻 2·如申清專利範圍第丨項所述之相關式符記儲存調節器之 系、、充更包含該付圯放置模組儲存該些符記於該些符記 所對應儲存的該複數個符記儲存區。 3 · ^申月專利範園第1項所述之相關式符記儲存調節器之 系"更包含在忒適當的符記儲存區係一空項目（empty ，該符記放置模組丟棄（^%&1^丨叫）該符記。 4·如申請專利範園第1項所述之相關式符記儲存調節器之 ，其中每一該符記產生器產生該的符記之該 期時間係彼此不同。

第14頁 1263429 六、申請專利範圍 5.如申請專利範圍第1帛所述之相_式符記儲存調節器之 ’其中每—該符記產生器產生應的符 期時間係彼此相同。 "％ 6·如申請專利範圍第1項所述之相關式符記儲存調節器之 糸統，其中該對應的符記係包含流量等級（士^“卜 class)的對應。 7·如申請專利範目第1項所述之相Μ式符記儲存調節器之 糸統’其中該適當的符記儲存區之流量等級係等於該符 ，所對應儲存的該符記儲存區之流量等級，且該適當的 付記儲存區之儲存空間尚未溢滿。 8. 如申請專利範圍第1項所述之相關式符記儲存調節器之 糸^中該適當的符記儲存區之流量等級係低於該符 ，所對應健存的該符記儲存區之流量等級，且該適 付記儲存區之儲存空間尚未溢滿。 9. 關式符記儲存調節器之方法，該相關式符記儲存 调即态之方法包含： 個冗記(token)，其中該些符記係由複數個符 ，§6η6ΓΜ〇Γ)所對應產生·，以及 忒些付圮於複數個符記儲存區（token pool)， 並在4 -料記㈣應儲存的—符記儲存區溢滿（full)

第15頁 — —* 1263429 六、申請專利範圍 時，將該符記儲存於該些符記儲存區之一適當的符記儲 存區。 1 0.如申請專利範圍第9項所述之相關式符記儲存調節器之 方法，更包含在該適當的符記儲存區係一空項目 (empty item)時，丟棄（discarding)該符記。 1 1 ·如申請專利範圍第9項所述之相關式符記儲存調節器之 方法，其中每一該符記產生器所對應產生一符記之一 週期時間係彼此不同。 1 2 ·如申請專利範圍第9項所述之相關式符記儲存調節器之 方法，其中每一該符記產生器所對應產生該符記之該 週期時間係彼此相同。 1 3 ·如申請專利範圍第9項所述之相關式符記儲存調節器之 方法，其中對應產生係包含流量等級（t r a f f i c c 1 a s s ) 的對應。 1 4.如申請專利範圍第9項所述之相關式符記儲存調節器之 方法，其中對應儲存係包含流量等級的對應。 1 5.如申請專利範圍第9項所述之相關式符記儲存調節器之 方法，其中該適當的符記儲存區之流量等級係等於該

第16頁 1263429 六、申請專利範圍 符記所對應儲存的該符記儲存區之流量等級，且該適 當的符記儲存區之儲存空間尚未溢滿。 1 6 ·如申請專利範圍第9項所述之相關式符記儲存調節器之 方法，其中該適當的符記儲存區之流量等級係低於該 符記所對應儲存的該符記儲存區之流量等級，且該適 當的符記儲存區之儲存空間尚未溢滿。

第17頁