【発明の属する技術分野】
本発明は、通信帯域制御方式に関し、詳しくは通信トラヒックフローに対してある範囲で設定された帯域（スループット）を制御する通信帯域制御方式に関するものである。
【従来の技術】
従来、通信ネットワークは、主にメデイア毎に専用化して構成されていた。しかし、扱うメデイアの種類、ネットワークの規模が大きくなるに連れ、これらのネットワークは運用コストが膨大となり、必ずしも最適な通信ネットワークとは言えなくなってきている。更に、通信・情報処理技術の進展の他、インターネットで代表されるように利用者のニーズがデータ、音声、画像等のメデイアを同一ネットワークで通信できることが重要になってきている。
インターネットは、元来、コンピュータ間で通信するために構築されたネットワークであり、データ通信を主体にしたネットワークである。このため、いわゆる“ベストエフォート”形通信（特に転送時間の制約を設けず、通信相手に届けば良いという通信）サービスが主体である。
上述したようなニーズが生じ始めたために、通信品質サービス（ＱｏＳ）の概念が導入されつつあるが、可変長パケットを前提にした場合、未だ通信トラヒックをクラス別優先的に転送制御する程度が実用上のレベルである。固定長パケット（セル）では、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｍｉｓｓｉｏｎ Ｍｏｄｅ）に代表されるように正確な帯域制御が行いやすいため実用化されている。
また、可変長パケットを前提にした場合、提案レベルでは、通信トラヒックフロー毎に正確に帯域制御方法が下記参考文献で紹介されている。
「Ｄ．Ｓｔｉｉａｄｉｓ，Ａ． Ｖａｒｍａ，“Ｒａｔｅ−ＰｒｏｐｏｒｔｉｏｎａｌＳｅｒｖｅｒｓ：Ａ Ｄｅｓｉｇｎ Ｍｅｔｈｏｄｏｌｏｇｙ ｆｏｒ Ｆａｉｒ Ｑｕｅｕｅｉｎｇ Ａｌｇｏｒｉｔｈｍｓ，“ ＩＥＥＥ／ＡＣＭ ＴＲ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ，Ｖｏｌ．１６，Ｎｏ．２，Ａｐｒｉｌ１９９８」
この方法は、ＡＴＭ等で採用されているトークン制御の概念を発展させ、可変長のパケットの流量を設定されたトークン増加レートと経過時間によってトークン量を決定し、トークン量の最大なトラヒックフローに対して最優先的に転送し、パケット転送を完了すると、該当パケット長に応じたトークンを消費することになるので該当トラヒックフローのトークン量を減じる操作を行う。この操作の繰り返しによって、各トラヒックフローの帯域を制御していくものである。
しかし、この方法では以下に示す欠点がある。
すなわち、
ａ．トークン増加レートを一元的にすると、転送スループットを確保するため、その増加レートは“予想される”入力トラヒックの「平均レート以上」で定義することになる。しかし、一般に入力トラヒックは必ずしも明確ではなく、ある範囲で設定する必要があるが、上記方式ではその設定が困難である。
ｂ．トラヒックフローの設定にはスループットのほか、低遅延／長遅延許容設定が必要になることがある。この場合、低遅延には高いトークン増加レートを設定し、長遅延には低いトークン増加レートを設定する（但し、上記ａ．の条件をクリアすることは必要）。トークン増加レートを大きくすると、万一、過剰なトラヒックが入力された場合、前記設定したトークン増加レートまで転送することになり、最大転送レートの制限が困難になる。
【発明が解決しようとする課題】
本発明は、上記従来の事情に鑑み開発されたものであり、最大転送レート並びに最小転送レートを定義し（もちろん、入力レートが最小転送レート以下である場合は、その入力レートがトラヒックフローの転送レートに一致することになる。）、その範囲内で入力されたトラヒックフローの転送レートを効率よく制御する通信帯域制御方式を提供することを目的とする。
【課題を解決するための手段】
請求項１記載の通信帯域制御方式は、可変長パケットにおける通信帯域を制御する通信帯域制御方式において、制御対象となる複数のトラヒックフローについて、パケット受信時には受信経過時間と増加レートの積から送出可能なトークン量を求め、そのトークン量を記憶し、パケット送信時には、複数のトラヒックフローから１つのトラヒックフローを選択するために、前記送出可能なトークン量の最大値の探索によりトラヒックフローの送信パケットを決定し、送信パケットのデータ長を前記送出可能なトークン量から減算し、その減算結果を記憶し、送信完了後並びに受信完了後に前記送出可能なトークン量から新たな増加レートを決定することを特徴とするものである。
請求項２記載の通信帯域制御方式は、請求項１記載の通信帯域制御方式において、制御対象とするトラヒック入力フローに対して予め該トラヒックフローに設定した最小増加レート並びに最大増加レートの範囲内でトラヒック入力に応じて、送出可能なトークン量を計算し、そのトークン量からトラヒックフローの出力レートを決定することすることを特徴とするものである。
請求項３記載の通信帯域制御方式は、任意のトラヒックフローに対する最優先サービス、任意のトラヒックフローに対するベストエフォートサービス並びに複数のトラヒックフローに対する固定優先等価サービスの割付を、予め設定する送信可能なトークン量の最大値並びに最小値、増加レートの最大値並びに最小値の設定によって実現することを特徴とするものである。
このような発明によれば、予め設定したト−クン増加レートの最小値〜最大値の範囲内で複数の通信トラヒックフローを制御でき、万一、トークン増加レートの最大値を超える通信トラヒックが入力されても他の通信トラヒックフローへ遅延時間の増加、送信レートの低下等の悪影響を与えることなく、また、トークン増加レートの最小値を下回る通信トラヒックフローではもっとも優先的処理を行う通信帯域制御方式を提供することができ、更にまた、最優先サービス、ベストエフォートサービス並びに固定優先等価サービスを実現可能な通信帯域制御方式を実現することができる。
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
図１は本発明の実施の形態を示す構成概念図であって、パケット交換機を概念的に表している。複数の入り回線１から入力したパケットはパケット交換機２の中で所定の出回線３に交換され、出回線３から交換されたパケットが転送される。
パケット交換機２の中には、出回線３へ出力されるパケットの転送を制御する転送制御部４があり、この転送制御部４では到着したパケットの分類、パケットの転送順位の選択、パケットの転送制御を行う。転送制御部４は、送出すべきパケットを予め設定されたレートに従ってパケットを出回線３に送信することを制御するのが主要な機能である。
図２は図１に示す転送制御部４の内部構成を拡大した機能ブロック構成の概念図であって、出回線３毎に配備される。転送制御部４は、該転送制御部４で受信したパケットの分類を行う振分け部４−１、該振分け部４−１で振り分けられたパケットをパス４−２を通じて受信し、且つ、一旦蓄積する出力待ちキュー４−３、出力待ちキュー４−３から所定の選択アルゴリズムで出力待ちキュー４−３にあるパケットを選択する出力待ちキュー選択部４−４からなる。
パケット交換機２の中で転送制御４で受信したパケットは、パケットの主にヘッダ情報（アドレス、パケットのタイプ等）からどの出力待ちキュー４−３に入力するのかが判断される。判断した後、該パケットは所定の出力待ちキュー４−３に蓄積され、出力待ちキュー選択部４−４によって選択されるのを待つ。
図３は出力待ちキュー選択部４−４を詳細化したブロック構成図である。出力待ちキュー選択部４−４は、トークン量を記憶し、且つ、増減の計算を行うトークン量計算・蓄積部４−４−１、出力待ちキュー４−３に入れられるパケットの受信時刻と前回蓄積された時の時刻の差とそのときのトークン増加レートを乗じて、トークン増加量を計算するトークン増加量計算部４−４−２、残トークン量を比較し、最大の残トークン量を有する出力待ちキュー４−３を選択するトラヒックフロー選択部４−４−３、トラヒックフロー選択部４−４−３の指示により所定の出力待ちキュー４−３からのパケットの入力を許可するパケット送出制御部４−４−４からなる。
図３に示す例では、４つのトラヒックフローの例を示しているが、各トラヒックフローとも同一の機能ブロックから構成される。１つのトラヒックフロー（図３中、破線で囲まれた部分：トラヒックフローＡとする）を例にとって、以下に図３の構成の動作を概略説明する。
まず、パケットをパス４−２から受信した場合の処理について図６をも参照して説明する。パス４−２から受信したパケットは、最優先サービス又はベストエフォートサービスではなく（図６参照Ｆ１−１）、出力待ちキュー４−３が満杯でないかぎり、該出力待ちキュー４−３に一旦蓄積される。
なお、満杯のとき、そのパケットは廃棄されるが、廃棄方法については本発明の対象ではないため説明を省略する。
出力待ちキュー４−３に蓄積されると同時に該パケットの受信時刻をトークン増加量計算部４−４−２に記憶し（Ｆ１−２）、すでに記憶されている前回のパケット受信時刻との差を計算する。この計算結果は、パケットの到着の時間間隔に相当する。その後、トークン量計算・蓄積部４−４−１から得たトークン増加レートと前記時間間隔を乗じて、その時間間隔におけるトークン増加量を計算する（Ｆ１−３）、（Ｆ１−４）。
このトークン増加量は、トークン量計算・蓄積部４−４−１に伝えられ、トークン量計算・蓄積部４−４−１では残トークン量とこのトークン増加量を加算して、該パケット受信時点の新たな残トークン量として記憶する（Ｆ１−５）。すなわち、残トークン量を更新する。
新たなトークン増加レートは、予め設定された増加レートの最大値から増加レートの最小値の範囲の間で、残トークン量に応じて決定され（Ｆ１−６）（トークン増加レートの決定方法については後述する）、更新される（Ｆ１−７）。
前記更新された残トークン量は。トークン量計算・蓄積部４−４−１からトラヒックフロー選択部４−４−３に通知される。以上の動作がパケット受信に関する一連の処理である。
次に、パケットを送信する場合の処理について図７を参照して説明する。トラヒックフロー選択部４−４−３では、任意の４つのトラヒックフローにおいて出回線３にパケットが送信されたと同時に、トラヒックフロー毎のトークン量計算・蓄積部４−４−１から通知されている４つのトラヒックフローにおける残トークン量を比較し、その中から最大のものを選択する（Ｆ２−１）。選択した結果、例えば、トラヒックフローＡが選択されたとすると（Ｆ２−２）、その選択情報はパケット送出制御部４−４−４に通知される。
そして、この場合の処理が最優先サービス又はベストエフォートサービスではない（Ｆ２−３）場合、パケット送出制御部４−４−４では、該出力待ちキュー４−３からパケットのデータ長の情報を読み取り（Ｆ２−４）、トークン量計算・蓄積部４−４−１にそれを通知する。トークン量計算・蓄積部４−４−１では、残トークン量を読み出し、その情報から該パケットのデータ長分を減算する処理を行い（Ｆ２−５）、その値を新たな残トークン量として更新し、記憶する（Ｆ２−６）。また、その残トークン量から決定する新たなトークン増加レートを決定し（Ｆ２−７）、トークン増加レートを新トークン増加レートに更新する（Ｆ２−８）。
一方、パケット送出制御部４−４−４では、パケットを該出力待ちキュー４−３から取り出し、そのパケットを出回線３から送信する。以上がパケットを送信する一連の処理である。
なお、上記の受信並びに送信の動作説明では、簡単のため４つのフローの例を前提にした構成例を示したが、これは、論理的にはＮ個（１以上）のトラヒックフローにおいても同様のことが実現できる。
次に、残トークン量とトークン増加レートの関係について説明する。図４、図５は、残トークン量とトークン増加レートの関係づける例を示すものである。この例では、残トークン量に応じて残トークン量の最大値並びに最小値の間で残トークン量に応じてトークン増加レートを決定することを示している。トークン増加レートの決定における基本的な考え方は以下による。
残トークン量がトークン量の最大値に近づくことは、到着パケットのレートがトークン増加レートよりも小さい可能性が高いことを意味する。したがって、過剰になる可能性の低減、他への資源配分の公平性を考慮するとトークンを低めに設定することが望ましい。
残トークン量が最小トークン量に近づくことは、到着パケットのレートがトークン増加レートよりも大きい可能性が高いことを意味する。したがって、許容できる範囲（〜トークン増加レートの最大値）で、トークン増加レートを増加させることによって、パケットの転送遅延、パケットの損失等を低減させることが望ましい。
残トークン量の最大値並びに最小値は、複数トラヒックフローの中から公平にトラヒックフローを選択するのに用いるので、トラヒックフロー固有ではなくシステム固有である必要がある。
図４、図５は、上記の考え方に従った例である。この例では、残トークン量に応じて三つの領域に区分けし、それぞれの領域にトークン増加レートの最大値、トークン増加レートの中間値、トークン増加レートの最小値を設定している。領域を３分割にしている理由は、トークン増加を計算する際に用いるトークン増加レートを単純化し、トークン増加レートを求める計算負荷を軽減することが目的である。もちろん、計算負荷が問題にならなければ、トークン増加レートを残トークンの関数として線形的に決定する手法もとることは可能である。
次に、図６、図７を参照して、トークン量の増加レートの決定動作について説明する。
出力待ちキュー４−３に入力するパケットのレートがトークン増加レートの最大値と最小値の間であれば、残トークン量は過不足することなく、パケットは転送制御される。しかし、入力パケットの入力レートがトークン増加レートの最大値より大きい場合、残トークン量は不足する傾向になる。残トークン量が残トークン量の最小値以下になると、残トークン量が再び残トークン量の最小値を超えるまでパケットの送出は停止する。停止することによって、送出パケットの転送レートは設定されたトークン増加レートの最大値を超えない保証が得られる。長時間、このような状況になると、出力待ちキュー４−３に蓄積されるパケット数は増加し、最終的にはバッファは満杯状態になり、パケットを廃棄することになる。
一方、到着パケットの入力レートがトークン増加レートの最小値よりも小さい場合、前記とは反対に残トークン量は過剰気味になる。特にトークン量が過剰であるからといって、転送制御上、何ら制約はかからないが残トークン量の最大値から次に転送すべきトラヒックフローが決定されるのでどちらかというと優先的に転送される可能性が高くなる。長時間、このような状況が続くと、残トークン量は残トークン量の最大値を越えることになり、越えた分のトークンは廃棄される。
このようなときは、トークン増加レートの最小値でトークンが増加する。言い換えれば、このトラヒックフローは設定トークン増加レートに比べ十分余裕があるために、余裕分を他のトラヒックフローへ割り振る動作がシステム全体を有効に利用するためには好ましい動作と言える。以上の動作をまとめると下記（１），（２），（３）のようになる。
（１）残トークン量が不足しはじめた状態では、トークン増加レートの最大値でトークンを補充し、許容できる最大のスループットでパケットの送信制御を行う。
（２）残トークン量が過剰気味の状態では、トークン増加レートの最小値でトークンを補充する。これによって、他のトラヒックフローへのリソース割り当ての可能性が高くなるとともに、設定されたレート範囲内でパケットの送信制御を行える。
（３）残トークン量が（１），（２）の中間状態（残トークン量の過不足がない状態）では、トークン増加レートの最大値−最小値の範囲で適宜、決定する。
図８、図９にトラヒックフロー数を８（＃１乃至＃８）として、トラヒックシミュレーション（残トークン量の時間的変化例を明示）実施した結果例のグラフ及び表を示す。
ここで、残トークン量によって区別した三つの領域において、残トークン量＝１００〜３９９→トークン増加レートの最小値、残トークン量＝４００〜６９９→トークン増加レートの中間値、残トークン量＝７００〜１０００→トークン増加レートの中間値に設定している。
また、図９の表で示したように、総計入力レートは、０．９３（出回線の使用率も０．９３）であり、かなり高負荷の状態である。トラヒックフロー＃２並びにトラヒックフロー＃６は、トークン増加レートの最小値に比べ入力レートは他よりも高めに、その他のトラヒックフローについては入力レートはトークン増加レートの最小値〜最大値の間になっている。
なお、シミュレーションでは、パケットの到着分布並びにサービス時間分布はともに指数分布に設定した（以下、すべてのシミュレーションにおいて同様の条件である）。シミュレーション結果から、以下の事柄が確認される。
各トラヒックフローのうち、トラヒックフロー＃１、＃２並びに＃６は平均入力レートがトークン増加レートの最小値よりも小さいため、残トークン量の最大値の付近で収束している。特にトラヒックフロー＃２は、他トラヒックフローに比べ、トークン増加レートの最小値が入力レートよりも大きいため、残トークン量の最大値にはやく収束している。
トラヒックフロー＃３、＃４、＃５、＃７、＃８は入力レートがトークン増加レートの最小値と中間値の間にあるため、トークン増加レートの最小値と中間値の領域を交差しながら、収束している。
上記の結果は、残トークン量の時間的変化を示した結果だが、同一シミュレーション条件で統計的に各トラヒックフローにおける出力待ちキュー４−３における平均キュー長を比較すると図１０に示すようになる。平均キュー長は各トラヒックフロー＃１乃至＃８における出力待ちキューでの遅延時間と密接な関係を持つ。この結果から、トラヒックフロー＃２並びに＃６、すなわち、トークン増加レートの最小値に対して入力レートが低い場合、もっとも平均キュー長が短いことを示している。また、トラヒックフロー＃３、＃４のように入力レートが大きくなるに従い、平均キュー長が長くなることを示している。最小トークン増加レートの最小値が出力待ちキューにおける滞留時間、言い換えれば遅延時間に影響することを示している。
図１１、図１２に、図８、図９と同様にトラヒックフロー数を８として、トークン増加レートの最大値を超えるトラヒックフローが存在する場合について、正常な範囲で設定された入力トラヒックフロー（トークン増加レートの最大値〜最小値の範囲内の入力レート）への影響の有無を判断する結果例を示す。
図１２の表で示したように、トークン増加レートの最大値を超える入力レートを持つトラヒックフローは＃１並びに＃８であり、その他のトラヒックフローはトークン増加レートの最小値〜最大値の範囲内の入力レートである。総計入力レートは１．４５であり、過負荷な入力であり、出回線容量（１．０）を越える分（０．４５に相当する部分）はパケット廃棄が発生する。
なお、図１１のグラフは図８の場合と異なり、その縦軸は各トラヒックフローの出力レートを示している。上述以外のシミュレーション条件は、図８の場合と同一である。
図１３は図１０と同一シミュレーション条件のときの各トラヒックフローの平均待ちキュー長並びにパケット廃棄率の結果例を示している。これらの結果から、以下の事柄が確認される。
トラヒックフロー＃１並びにトラヒックフロー＃８の出力レートは０．１７〜０．１８付近に収束している。
他のトラヒックフローは、出力レートは入力レートと等しくなっている。
平均キュー長は、トラヒックフロー＃２〜トラヒックフロー＃７はほぼ同等で、且つ、小さい。しかし、トラヒックフロー＃１並びにトラヒックフロー＃８は出力待ちキュー最大まで達している。
パケット廃棄はトラヒックフロー＃１並びにトラヒックフロー＃８で発生しているが、他のトラヒックフローでは発生していない。
これらの結果から、過負荷になっているトラヒックフロー＃１並びにトラヒックフロー＃８の影響は、他のトラヒックフローには影響していないことが確認される。
なお、前記「トラヒックフロー＃１並びにトラヒックフロー＃８の出力レートは０．１７〜０．１８付近に収束している」際の出力レートの値は、トラヒックフロー＃２〜トラヒックフロー＃７までの総計レートが０．６５であるため、残りの許容レート分（＝１−０．６５）をほぼ等分にトラヒックフロー＃１並びにトラヒックフロー＃８に配分されたものと推定される。
次に、上述した実施の形態の応用として、任意のトラヒックフローに対する最優先サービスの割当方法について説明する。最優先サービスはどんな状態においても最優先されるサービスの割り付けであり、例えば、緊急を要するネットワークの制御情報等の転送に用いられることが想定される。
最優先サービスでは、残トークンの最大値以上の残トークン量を固定的に割り付けることで実現できる。固定的に残トークン量を割り付けるため、パケット送受信におけるトークン量に関する計算は不要にする。
すなわち、パケット受信時、既述した図６に示す処理フローチャートのＦ１−１において最優先サービスであると認識されると、トークン量の計算をすることなく処理が終了する。また、パケット送信時、既述した図７に示す処理フローチャートのＦ２−３で最優先サービスか否かをチェックされ、該出力待ちキュー４−３にパケットが存在する場合、送信処理が行われる。そのとき、最優先サービスでは、残トークン量の最大値より大きいため、必ず他のトラヒックフローよりも先にチェックされるので優先的に送信が行われることが保証できる。
また、次にベストエフォートサービスの割当法について説明する。ベストエフォートサービスは最優先サービスと相反するサービスであり、他のトラヒックフローの出力待ちキュー４−３に送信すべきパケットが存在せず、ベストエフォートサービスに割り付けられたトラヒックフローの出力待ちキュー４−３に送信するパケットが存在するとき、このサービスが行われる。
ベストエフォートサービスでは、最優先サービスとは異なり、残トークン量の最小値を残トークン量として固定的に割り付けることで実現する。固定的に残トークン量を割り付けるため、パケット送受信におけるトークン量に関する計算は、最優先サービスと同様、不要とする。すなわち、パケット受信時、図６に示す処理フローチャートのＦ１−１においてベストエフォートサービスであると認識されると、処理が終了する。また、パケット送信時、図７に示す処理フローチャートのＦ２−３でベストエフォートサービスか否かをチェックされ、該出力待ちキュー４−３にパケットが存在する場合、送信処理が行われる。そのとき、ベストエフォートサービスでは、残トークン量の最小値なので、それ以外のサービスのトラヒックフローがすべてチェックされた後にこのサービスに移るため、このトラヒックフローに対して最下位の優先順位で送信が行われる。
最後に、固定優先サービスと等価に実施できる固定優先等価サービスについて説明する。固定優先サービスはトラヒックフローに優先順位を付けて、優先順位の順にサービスを行うものである。
本実施の形態においては、優先順位の高いトラヒックフロー順に高いトークン増加レートの最小値を割り付けることによって実現する。これに伴い、最大トークン増加レートの最大値はトークン増加レートの最小値以上の値を設定する。
なお、固定優先の場合、トラヒックフローの入力レートには何ら制限を与えない（出回線容量により制限はあるが）ため、トークン増加レートの最小値はどのトラヒックフローにおいても入力レートよりも大きい値を与える。この設定によって、優先順位が高いほど、最大トークンにいる可能性が高くなり、優先的にパケットが送信できる条件を作ることができる。図６並びに図７に示した処理フローチャートにおいて、固定優先等価サービスを何ら意識することなく実行できる。
図１４に従来の固定優先サービス（図１４の点線グラフ）と対比させて、本実施の形態の固定優先等価サービス（図１４の実線グラフ）の平均出力待ちキュー長のシミュレーション結果を示す。この図１４から、固定優先等価サービスは固定優先サービスとほぼ同等なサービスが実現されていることがわかる。図１５は、この場合のトークン増加レートの設定値、平均入力レートの値を示す表である。
以上説明した本発明は、交換機、多重化装置、ルータ等通信ネットワークを構成する装置等に適用でき、特に、多くの通信トラヒックフローを同時、且つ、正確に帯域制御することができるので、今後ますます膨大化する可変長パケット、例えばＩＰネットワーク構成装置において大きい効果を期待できる通信帯域制御方式を提供できる。
【発明の効果】
本発明によれば、予め設定したト−クン増加レートの最小値〜最大値の範囲内で複数の通信トラヒックフローを制御でき、万一、トークン増加レートの最大値を超える通信トラヒックが入力されても他の通信トラヒックフローへ遅延時間の増加、送信レートの低下等の悪影響を与えることなく、また、トークン増加レートの最小値を下回る通信トラヒックフローではもっとも優先的処理を行う通信帯域制御方式を提供することができる。また、最優先サービス、ベストエフォートサービス並びに固定優先等価サービスを実現可能な通信帯域制御方式を提供することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態の通信帯域制御方式が適用されるパケット交換機の概念を示す説明図である。
【図２】本実施の形態の通信帯域制御方式を実現する転送制御部の内部構成を拡大した機能ブロック構成の概念を示す説明図である。
【図３】本実施の形態の出力待ちキュー選択部を詳細化したブロック図である。
【図４】本実施の形態の残トークン量とトークン増加レートの関係を示すグラフである。
【図５】本実施の形態の残トークン量とトークン増加レートとの関係を示す説明図である。
【図６】本実施の形態のパケット受信時の処理を示すフローチャート図である。
【図７】本実施の形態のパケット送信時の処理を示すフローチャート図である。
【図８】本実施の形態に基づいてモデル化したトラヒックシミュレーションの結果例（残トークン量の時間的な変化）を示すグラフである。
【図９】本実施の形態に基づいてモデル化したトラヒックシミュレーションの各フローの設定値を示す表である。
【図１０】本実施の形態に基づいてモデル化したトラヒックシミュレーションの結果例（各フロー（ＦＬ）の平均待ちキュー長、トークン増加レートの設定範囲）を示すグラフである。
【図１１】本発明の実施の形態に基づいてモデル化したトラヒックシミュレーションの結果例（増加レートの時間的な変化）を示すグラフである。
【図１２】本実施の形態に基づいてモデル化した図１１に示すトラヒックシミュレーションの各フローの設定値を示す表である。
【図１３】本実施の形態に基づいてモデル化したトラヒックシミュレーションの結果例（出力待ちキュー長並びにパケット廃棄率）を示すグラフである。
【図１４】本実施の形態に基づく固定優先等価モデルのトラヒックシミュレーションの結果例（平均出力待ちキュー長の統計的データ）を従来の固定優先モデルと対比して示すグラフである。
【図１５】本実施の形態に基づく固定優先等価モデルの各フローの設定値を示す表である。
【符号の説明】
１ 入り回線
２ パケット交換機
３ 出回線
４ パケット交換機内の転送制御部
４−１ 振分け部
４−２ パス
４−３ 出力待ちキュー
４−４ 出力待ちキュー選択部
４−４−１ トークン量計算・蓄積部
４−４−２ トークン増加量計算部
４−４−３ トラヒックフロー選択部
４−４−４ パケット送出制御部TECHNICAL FIELD OF THE INVENTION
The present invention relates to a communication band control method, and more particularly to a communication band control method for controlling a band (throughput) set within a certain range for a communication traffic flow.
[Prior art]
Conventionally, a communication network has been mainly configured exclusively for each medium. However, as the types of media to be handled and the scale of the networks increase, these networks have an enormous operation cost, and are not necessarily the most suitable communication networks. Furthermore, in addition to the progress of communication and information processing technology, it is important that the user needs to be able to communicate media such as data, voice, images, and the like on the same network as represented by the Internet.
The Internet is a network originally constructed for communication between computers, and is a network mainly for data communication. For this reason, the so-called “best effort” type communication (communication in which the transfer time is not limited and the communication is desirably delivered to the communication partner) is mainly used.
The concept of communication quality service (QoS) is being introduced due to the need described above, but when variable-length packets are assumed, it is still practical to control transmission of communication traffic preferentially by class. On the upper level. Fixed-length packets (cells) have been put to practical use because accurate band control is easy to perform, as typified by ATM (Asynchronous Transmission Mode).
On the premise of variable-length packets, at the proposed level, a bandwidth control method that is accurate for each communication traffic flow is introduced in the following references.
"D. Stiadis, A. Varma," Rate-Proportional Servers: A Design Methodology for Fair Queueing Algorithms, "IEEE / ACM TRon Network.
This method develops the concept of token control adopted in ATMs and the like, determines the amount of tokens according to the set token increase rate and elapsed time, and sets the flow of variable-length packets to the maximum traffic flow of the amount of tokens. On the other hand, when the packet transfer is performed with the highest priority and the packet transfer is completed, a token corresponding to the packet length is consumed, so that an operation for reducing the token amount of the traffic flow is performed. By repeating this operation, the bandwidth of each traffic flow is controlled.
However, this method has the following disadvantages.
That is,
a. If the token increase rate is unified, the increase rate is defined as “above the average rate” of “expected” input traffic in order to secure transfer throughput. However, generally, input traffic is not always clear and needs to be set within a certain range. However, it is difficult to set the input traffic in the above-mentioned method.
b. The setting of the traffic flow may require a low delay / long delay allowable setting in addition to the throughput. In this case, a high token increase rate is set for the low delay, and a low token increase rate is set for the long delay (however, it is necessary to clear the condition a.). If the token increase rate is increased, if excessive traffic is input, the traffic is transferred up to the set token increase rate, and it is difficult to limit the maximum transfer rate.
[Problems to be solved by the invention]
The present invention has been developed in view of the above-mentioned conventional circumstances, and defines a maximum transfer rate and a minimum transfer rate (of course, when the input rate is equal to or less than the minimum transfer rate, the input rate is determined based on the traffic flow transfer rate). It is an object of the present invention to provide a communication band control method for efficiently controlling the transfer rate of a traffic flow input within the range.
[Means for Solving the Problems]
The communication band control method according to claim 1 is a communication band control method for controlling a communication band in a variable-length packet, wherein a plurality of traffic flows to be controlled can be transmitted from a product of an elapsed reception time and an increase rate when receiving a packet. In order to select one traffic flow from a plurality of traffic flows at the time of transmitting a packet, the transmission packet of the traffic flow is searched for the maximum value of the transmittable token amount. Determining, subtracting the data length of the transmission packet from the transmittable token amount, storing a result of the subtraction, and determining a new increase rate from the transmittable token amount after transmission is completed and after reception is completed. It is assumed that.
The communication band control method according to claim 2 is the communication band control method according to claim 1, wherein a traffic input flow to be controlled falls within a range of a minimum increase rate and a maximum increase rate previously set for the traffic flow. It is characterized in that the amount of tokens that can be transmitted is calculated according to the traffic input, and the output rate of the traffic flow is determined from the calculated amount of tokens.
The communication bandwidth control method according to claim 3, wherein the number of transmittable tokens is set in advance by assigning a top priority service to an arbitrary traffic flow, a best effort service to an arbitrary traffic flow, and a fixed priority equivalent service to a plurality of traffic flows. Are set by setting the maximum value and the minimum value, and the maximum value and the minimum value of the increase rate.
According to such an invention, a plurality of communication traffic flows can be controlled within the range of the minimum value to the maximum value of the token increase rate set in advance, and the communication traffic exceeding the maximum value of the token increase rate is input by any chance. A communication bandwidth control method that does not adversely affect other communication traffic flows, such as an increase in delay time or a decrease in the transmission rate, and that performs the highest priority processing for communication traffic flows that are below the minimum value of the token increase rate. And a communication bandwidth control method capable of realizing a top priority service, a best effort service, and a fixed priority equivalent service can be realized.
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
FIG. 1 is a configuration conceptual diagram showing an embodiment of the present invention, and conceptually shows a packet switch. Packets input from a plurality of incoming lines 1 are switched to a predetermined outgoing line 3 in a packet switch 2, and packets exchanged from the outgoing line 3 are transferred.
In the packet switch 2, there is a transfer control unit 4 for controlling the transfer of the packet output to the outgoing line 3. The transfer control unit 4 classifies the arriving packet, selects the transfer order of the packet, and transfers the packet. Perform control. The main function of the transfer control unit 4 is to control transmission of packets to be transmitted to the outgoing line 3 according to a preset rate.
FIG. 2 is a conceptual diagram of a functional block configuration in which the internal configuration of the transfer control unit 4 shown in FIG. 1 is enlarged, and is provided for each outgoing line 3. The transfer control unit 4 classifies the packets received by the transfer control unit 4, and receives the packets distributed by the distribution unit 4-1 via the path 4-2 and temporarily stores the packets. The output queue 4-3 comprises an output queue selection unit 4-4 for selecting a packet in the output queue 4-3 from the output queue 4-3 by a predetermined selection algorithm.
For the packet received by the transfer control 4 in the packet switch 2, it is determined which output queue 4-3 is to be input, mainly from the header information (address, packet type, etc.) of the packet. After the determination, the packet is accumulated in a predetermined output queue 4-3 and waits for selection by the output queue selector 4-4.
FIG. 3 is a block diagram showing the output queue selection unit 4-4 in detail. The output queue selection unit 4-4 stores the token amount and calculates the increase / decrease. The token amount calculation / accumulation unit 4-4-1, the reception time of the packet put in the output queue 4-3 and the last time A token increment calculating unit 4-4-2 that calculates the token increment by multiplying the accumulated time difference by the token increment rate at that time, compares the remaining token quantities, and has the maximum remaining token quantity. A packet transmission control for permitting the input of a packet from a predetermined output waiting queue 4-3 according to an instruction of the traffic flow selecting unit 4-4-3 for selecting the output waiting queue 4-3 and the traffic flow selecting unit 4-4-3. Unit 4-4-4.
Although the example shown in FIG. 3 shows an example of four traffic flows, each traffic flow is composed of the same functional block. The operation of the configuration of FIG. 3 will be schematically described below by taking one traffic flow (portion surrounded by a broken line in FIG. 3: traffic flow A) as an example.
First, a process when a packet is received from the path 4-2 will be described with reference to FIG. The packet received from the path 4-2 is not the highest priority service or the best effort service (F1-1 in FIG. 6), and is temporarily stored in the output queue 4-3 unless the output queue 4-3 is full. You.
When the packet is full, the packet is discarded, but the discarding method is not the object of the present invention, and the description is omitted.
At the same time as being stored in the output queue 4-3, the reception time of the packet is stored in the token increment calculation unit 4-4-2 (F1-2), and the difference from the previously stored packet reception time is stored. Is calculated. This calculation result corresponds to the time interval of packet arrival. Thereafter, the token increment in the time interval is calculated by multiplying the token increment rate obtained from the token amount calculating / accumulating unit 4-4-1 by the time interval (F1-3) and (F1-4).
This token increase is transmitted to the token amount calculating / accumulating unit 4-4-1, and the token amount calculating / accumulating unit 4-4-1 adds the remaining token amount and the token increment to obtain the time when the packet is received. (F1-5). That is, the remaining token amount is updated.
The new token increase rate is determined in accordance with the remaining token amount in a range from the preset maximum value of the increase rate to the minimum value of the increase rate (F1-6). The information is updated (described later) (F1-7).
What is the updated remaining token amount? The token amount calculation / storage unit 4-4-1 notifies the traffic flow selection unit 4-4-3. The above operation is a series of processes related to packet reception.
Next, a process for transmitting a packet will be described with reference to FIG. In the traffic flow selection unit 4-4-3, at the same time when a packet is transmitted to the outgoing line 3 in any four traffic flows, the packet amount is notified from the token amount calculation / accumulation unit 4-4-1 for each traffic flow. The remaining token amounts in the two traffic flows are compared, and the largest one is selected (F2-1). As a result of the selection, for example, if the traffic flow A is selected (F2-2), the selection information is notified to the packet transmission control unit 4-4-4.
If the processing in this case is not the highest priority service or the best effort service (F2-3), the packet transmission control unit 4-4-4 reads information on the data length of the packet from the output waiting queue 4-3. (F2-4), the token amount calculation / accumulation unit 4-4-1 is notified of this. The token amount calculation / accumulation unit 4-4-1 reads the remaining token amount, performs a process of subtracting the data length of the packet from the information (F2-5), and updates the value as a new remaining token amount. And store it (F2-6). Further, a new token increase rate determined from the remaining token amount is determined (F2-7), and the token increase rate is updated to the new token increase rate (F2-8).
On the other hand, the packet transmission control unit 4-4-4 takes out the packet from the output waiting queue 4-3 and transmits the packet from the outgoing line 3. The above is a series of processes for transmitting a packet.
In the above description of the receiving and transmitting operations, for simplicity, an example of a configuration based on the example of four flows has been described. However, the same is true for N (one or more) traffic flows. Can be realized.
Next, the relationship between the remaining token amount and the token increase rate will be described. 4 and 5 show examples in which the remaining token amount is associated with the token increase rate. This example shows that the token increase rate is determined according to the remaining token amount between the maximum value and the minimum value of the remaining token amount according to the remaining token amount. The basic concept in determining the token increase rate is as follows.
When the remaining token amount approaches the maximum value of the token amount, it means that there is a high possibility that the rate of the arriving packet is smaller than the token increase rate. Therefore, it is desirable to set the token low in consideration of the possibility of excess and fairness of resource allocation to others.
When the remaining token amount approaches the minimum token amount, it means that there is a high possibility that the rate of arriving packets is higher than the token increase rate. Therefore, it is desirable to reduce the packet transfer delay, the packet loss, and the like by increasing the token increase rate within an allowable range (to the maximum value of the token increase rate).
Since the maximum value and the minimum value of the remaining token amount are used for fairly selecting a traffic flow from a plurality of traffic flows, they need to be system-specific rather than traffic-flow-specific.
4 and 5 are examples according to the above concept. In this example, the area is divided into three areas according to the remaining token amount, and the maximum value of the token increase rate, the intermediate value of the token increase rate, and the minimum value of the token increase rate are set in each area. The reason for dividing the region into three is to simplify the token increase rate used in calculating the token increase and reduce the calculation load for calculating the token increase rate. Of course, if the calculation load does not matter, it is possible to adopt a method of linearly determining the token increase rate as a function of the remaining tokens.
Next, the operation of determining the increase rate of the token amount will be described with reference to FIGS.
If the rate of packets input to the output queue 4-3 is between the maximum value and the minimum value of the token increase rate, the transfer control of the packets is performed without any excess or deficiency of the remaining token amount. However, when the input rate of the input packet is larger than the maximum value of the token increase rate, the remaining token amount tends to be insufficient. When the remaining token amount becomes equal to or less than the minimum value of the remaining token amount, the transmission of the packet is stopped until the remaining token amount exceeds the minimum value of the remaining token amount again. By stopping, it is ensured that the transfer rate of the outgoing packet does not exceed the maximum value of the set token increase rate. If such a situation occurs for a long time, the number of packets stored in the output queue 4-3 increases, and eventually the buffer becomes full and the packets are discarded.
On the other hand, when the input rate of the arriving packet is smaller than the minimum value of the token increase rate, the amount of remaining tokens becomes slightly excessive, contrary to the above. In particular, even if the token amount is excessive, there is no restriction on the transfer control, but since the traffic flow to be transferred next is determined from the maximum value of the remaining token amount, it is preferentially transferred. The likelihood increases. If such a situation continues for a long time, the remaining token amount exceeds the maximum value of the remaining token amount, and the excess token is discarded.
In such a case, the token increases at the minimum value of the token increase rate. In other words, since this traffic flow has a sufficient margin as compared with the set token increase rate, it can be said that the operation of allocating the margin to another traffic flow is a preferable operation for effectively utilizing the entire system. The above operations are summarized as (1), (2), and (3) below.
(1) When the remaining token amount starts to be insufficient, the token is replenished at the maximum value of the token increase rate, and the packet transmission is controlled at the maximum allowable throughput.
(2) When the remaining token amount is in an excessive state, tokens are replenished at the minimum value of the token increase rate. As a result, the possibility of allocating resources to other traffic flows is increased, and packet transmission control can be performed within the set rate range.
(3) In an intermediate state where the remaining token amount is (1) or (2) (a state in which the remaining token amount is not excessive or insufficient), the token increasing rate is appropriately determined within the range of the maximum value-minimum value of the token increase rate.
FIGS. 8 and 9 show graphs and tables of examples of the results of traffic simulation (specifying a temporal change in the remaining token amount) with the number of traffic flows being 8 (# 1 to # 8).
Here, in the three areas distinguished by the remaining token amount, the remaining token amount = 100 to 399 → the minimum value of the token increase rate, the remaining token amount = 400 to 699 → the intermediate value of the token increase rate, the remaining token amount = 700 to 1000 → set to the intermediate value of the token increase rate.
Further, as shown in the table of FIG. 9, the total input rate is 0.93 (the outgoing line use rate is also 0.93), and the load is considerably high. For traffic flows # 2 and # 6, the input rate is higher than the minimum value of the token increase rate, and for other traffic flows, the input rate is between the minimum value and the maximum value of the token increase rate. ing.
In the simulations, both the packet arrival distribution and the service time distribution were set to exponential distributions (hereinafter, the same conditions are used in all simulations). The followings are confirmed from the simulation results.
Of the traffic flows, traffic flows # 1, # 2, and # 6 converge near the maximum value of the remaining token amount because the average input rate is smaller than the minimum value of the token increase rate. In particular, in traffic flow # 2, the minimum value of the token increase rate is larger than the input rate as compared with the other traffic flows, so that the traffic flow # 2 quickly converges to the maximum value of the remaining token amount.
In traffic flows # 3, # 4, # 5, # 7, and # 8, since the input rate is between the minimum value and the intermediate value of the token increase rate, the traffic flow # 3, # 4, # 5, # 7, and # 8 crosses the region of the minimum value and the intermediate value of the token increase rate. , Has converged.
The above result shows the temporal change of the remaining token amount. FIG. 10 shows a statistical comparison of the average queue length in the output queue 4-3 in each traffic flow under the same simulation conditions. The average queue length is closely related to the delay time in the output queue in each of the traffic flows # 1 to # 8. This result indicates that the average queue length is the shortest when the input rate is low with respect to the traffic flows # 2 and # 6, that is, the minimum value of the token increase rate. Also, as shown in traffic flows # 3 and # 4, the average queue length increases as the input rate increases. This indicates that the minimum value of the minimum token increase rate affects the residence time in the output queue, in other words, the delay time.
In FIGS. 11 and 12, as in FIGS. 8 and 9, when the number of traffic flows is 8, and there is a traffic flow exceeding the maximum value of the token increase rate, the input traffic flow (token An example of the result of determining whether or not there is an influence on the input rate within the range between the maximum value and the minimum value of the increase rate will be described.
As shown in the table of FIG. 12, traffic flows having an input rate exceeding the maximum value of the token increase rate are # 1 and # 8, and the other traffic flows are within the range of the minimum value to the maximum value of the token increase rate. Input rate. The total input rate is 1.45, which is an overloaded input. Packets are discarded for portions exceeding the output line capacity (1.0) (corresponding to 0.45).
Note that the graph of FIG. 11 is different from that of FIG. 8, and the vertical axis indicates the output rate of each traffic flow. The simulation conditions other than those described above are the same as in the case of FIG.
FIG. 13 shows an example of the results of the average wait queue length and the packet discard rate of each traffic flow under the same simulation conditions as in FIG. From these results, the following matters are confirmed.
The output rates of traffic flow # 1 and traffic flow # 8 converge around 0.17 to 0.18.
For other traffic flows, the output rate is equal to the input rate.
The average queue length is almost the same for traffic flow # 2 to traffic flow # 7 and small. However, traffic flow # 1 and traffic flow # 8 have reached the maximum output queue.
Packet discarding occurs in traffic flows # 1 and # 8, but does not occur in other traffic flows.
From these results, it is confirmed that the influence of the overloaded traffic flows # 1 and # 8 does not affect other traffic flows.
Note that the output rate value when the “output rates of traffic flow # 1 and traffic flow # 8 converge around 0.17 to 0.18” is between traffic flow # 2 and traffic flow # 7. Since the total rate is 0.65, it is estimated that the remaining allowable rate (= 1-0.65) has been almost equally distributed to the traffic flows # 1 and # 8.
Next, as an application of the above-described embodiment, a method of allocating the highest priority service to an arbitrary traffic flow will be described. The highest-priority service is an assignment of a service that has the highest priority in any state, and is assumed to be used, for example, for transferring urgent network control information and the like.
The highest priority service can be realized by fixedly allocating the remaining token amount equal to or more than the maximum value of the remaining tokens. Since the remaining token amount is fixedly allocated, the calculation regarding the token amount in packet transmission / reception is not required.
That is, at the time of packet reception, if it is recognized that the service is the highest priority service in F1-1 of the processing flowchart shown in FIG. 6 described above, the process ends without calculating the token amount. Also, at the time of packet transmission, it is checked whether or not the service is the highest priority service in F2-3 of the processing flowchart shown in FIG. 7 described above, and if a packet exists in the output waiting queue 4-3, transmission processing is performed. At that time, in the highest priority service, since it is larger than the maximum value of the remaining token amount, it is always checked before other traffic flows, so that it is possible to guarantee that transmission is performed preferentially.
Next, the best effort service allocation method will be described. The best-effort service is a service that is inconsistent with the highest-priority service. Since there is no packet to be transmitted in the output queue 4-3 of another traffic flow, the output queue 4-4 of the traffic flow allocated to the best-effort service does not exist. 3 when there is a packet to send.
Unlike the highest priority service, the best effort service is realized by fixedly assigning the minimum value of the remaining token amount as the remaining token amount. Since the remaining token amount is fixedly allocated, the calculation regarding the token amount in packet transmission / reception is not required as in the case of the highest priority service. That is, at the time of packet reception, if it is recognized as the best effort service in F1-1 of the processing flowchart shown in FIG. 6, the process ends. Also, at the time of packet transmission, it is checked whether or not the service is the best effort service in F2-3 of the processing flowchart shown in FIG. 7, and if a packet exists in the output waiting queue 4-3, the transmission process is performed. At that time, in the best effort service, since the remaining token amount is the minimum value, since the traffic flow of all other services is checked, the service is transferred to this service, so that the traffic flow is transmitted with the lowest priority. Is
Finally, a fixed priority equivalent service that can be implemented equivalently to the fixed priority service will be described. The fixed-priority service assigns priorities to traffic flows and performs services in the order of priority.
In the present embodiment, this is realized by assigning the minimum value of the token increase rate in the order of the traffic flows with the highest priority. Accordingly, the maximum value of the maximum token increase rate is set to a value equal to or greater than the minimum value of the token increase rate.
In the case of fixed priority, there is no restriction on the input rate of the traffic flow (although there is a limit depending on the outgoing line capacity). Therefore, the minimum value of the token increase rate is set to a value larger than the input rate in any traffic flow. give. With this setting, the higher the priority is, the higher the possibility of being in the maximum token is, and it is possible to create a condition in which a packet can be transmitted preferentially. In the processing flowcharts shown in FIGS. 6 and 7, the fixed priority equivalent service can be executed without any consideration.
FIG. 14 shows a simulation result of the average output wait queue length of the fixed priority equivalent service (solid line graph in FIG. 14) of the present embodiment in comparison with the conventional fixed priority service (dotted line graph in FIG. 14). From FIG. 14, it can be seen that the fixed priority equivalent service realizes substantially the same service as the fixed priority service. FIG. 15 is a table showing the set value of the token increase rate and the value of the average input rate in this case.
The present invention described above can be applied to devices constituting a communication network such as a switch, a multiplexing device, a router and the like. In particular, since many communication traffic flows can be controlled simultaneously and accurately, the bandwidth will be increased in the future. It is possible to provide a communication band control method that can be expected to have a great effect in an ever-expanding variable-length packet, for example, an IP network device.
【The invention's effect】
According to the present invention, it is possible to control a plurality of communication traffic flows within a range from a minimum value to a maximum value of a predetermined token increase rate, and if communication traffic exceeding the maximum value of the token increase rate is input, Provides a communication bandwidth control method that does not adversely affect other communication traffic flows, such as an increase in delay time or a decrease in transmission rate, and performs the highest priority processing for communication traffic flows that are below the minimum value of the token increase rate. can do. Further, it is possible to provide a communication band control method capable of realizing a top priority service, a best effort service, and a fixed priority equivalent service.
[Brief description of the drawings]
FIG. 1 is an explanatory diagram showing the concept of a packet switch to which a communication band control method according to an embodiment of the present invention is applied.
FIG. 2 is an explanatory diagram illustrating a concept of a functional block configuration in which an internal configuration of a transfer control unit that realizes a communication band control method according to the present embodiment is enlarged.
FIG. 3 is a detailed block diagram of an output queue selection unit according to the embodiment;
FIG. 4 is a graph showing a relationship between a remaining token amount and a token increase rate according to the embodiment.
FIG. 5 is an explanatory diagram illustrating a relationship between a remaining token amount and a token increase rate according to the present embodiment.
FIG. 6 is a flowchart illustrating a process at the time of receiving a packet according to the present embodiment.
FIG. 7 is a flowchart illustrating a process at the time of transmitting a packet according to the present embodiment.
FIG. 8 is a graph showing an example of a result of a traffic simulation modeled based on the present embodiment (temporal change of the remaining token amount).
FIG. 9 is a table showing setting values of each flow of a traffic simulation modeled based on the present embodiment.
FIG. 10 is a graph showing an example of a result of a traffic simulation modeled based on the present embodiment (setting ranges of an average wait queue length and a token increase rate of each flow (FL)).
FIG. 11 is a graph showing an example of a result of a traffic simulation modeled based on the embodiment of the present invention (temporal change of increase rate).
FIG. 12 is a table showing set values of each flow of the traffic simulation shown in FIG. 11 modeled based on the present embodiment.
FIG. 13 is a graph showing an example of a result of a traffic simulation modeled based on the present embodiment (output queue length and packet discard rate).
FIG. 14 is a graph showing a result example of traffic simulation (statistical data of average output wait queue length) of a fixed priority equivalent model based on the present embodiment in comparison with a conventional fixed priority model.
FIG. 15 is a table showing set values of each flow of the fixed priority equivalent model based on the present embodiment.
[Explanation of symbols]
1 entering line
2 Packet switch
3 Outgoing line
4 Transfer control unit in packet switch
4-1 Sorting unit
4-2 pass
4-3 Output waiting queue
4-4 Output wait queue selector
4-4-1 Token amount calculation / storage unit
4-4-2 Token increase calculation unit
4-4-3 Traffic flow selector
4-4-4 Packet Transmission Control Unit