(57)【特許請求の範囲】
【請求項１】
ある一連の転送データであるトラフィックフロー毎の送信待ちキューを有し、
前記トラフィックフロー毎の単位時間あたりに送信すべきデータ量を示す保証帯域と、前記トラフィックフロー毎に前記送信待ちキューから送信したデータ量とを管理し、
前記送信すべきデータ量を示す前記保証帯域に対する前記送信したデータ量によって表される前記保証帯域の達成度を求め、前記達成度が低いトラフィックフローのキューを優先的に選択して送信するようにした帯域保証送信方法。
【請求項２】
請求項１に記載の帯域保証送信方法であって、
単位時間毎に、各トラフィックフローの送信したデータ量及び保証帯域の達成度を管理する制御変数を再初期化することで、トラフィックフローの偏りを是正することを特徴とする帯域保証送信方法。
【請求項３】
請求項１又は２に記載の帯域保証送信方法であって、
平均データパケット長及び回線速度に基づいて、帯域保証の精度と制御変数の再初期化時間を調整することを特徴とする帯域保証送信方法。
【請求項４】
請求項１乃至３のいずれかに記載の帯域保証送信方法であって、
前記達成度は、トラフィックフロー毎のカウンタが一巡した回数であるラップアラウンド回数により管理することを特徴とする帯域保証送信方法。
【請求項５】
ある一連の転送データであるトラフィックフロー毎の送信待ちキューと、トラフィックフロー別に応じてデータをキューイングする送信待ちキューテーブルと、各トラフィックフロー毎に、単位時間あたりに保証する帯域幅をデータ数単位で管理する送信帯域保証テーブルと、各トラフィックフロー毎に単位時間内に送信したデータ数を管理する送信帯域値テーブルと、各トラフィックフロー毎に前記送信帯域値テーブルのラップアラウンド回数を管理する送信帯域値ラップアラウンド回数管理テーブルとを有するメモリと、
ネットワークに接続される入出力処理部と、
前記メモリに基づき、前記入出力処理部によるデータ送信を制御する制御部と
を備え、
前記制御部は、
前記トラフィックフロー毎の単位時間あたりに送信すべきデータ量を示す保証帯域と、前記トラフィックフロー毎に前記送信待ちキューから送信したデータ量とを管理し、
前記送信すべきデータ量を示す前記保証帯域に対する前記送信したデータ量によって表される前記保証帯域の達成度を求め、前記達成度が低いトラフィックフローのキューを優先的に選択して送信するようにした帯域保証送信装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信制御システムにおける帯域保証送信方法及び装置に関する。
【０００２】
【従来の技術】
従来、ネットワークのトラフィックが混雑すると、集中したトラフィックの優先度を優先度の高いものから低いものへと固定的に評価してデータ転送順序を決定していた。すなわち、優先度１(最高優先度)のトラフィックフローと優先度７(最低優先度)のトラフィックフローが同時に発生すると、優先度１のトラフィックフローが存在する限り優先度７のトラフィックフローの送信機会が無くなる場合があった。
【０００３】
【発明が解決しようとする課題】
上述のような従来技術では、集中したトラフィックフロー相互の優先度関係によって、転送順序が偶然決定する場合が多い。すなわち、優先度１と優先度７のトラフィックフローが同時に発生する場合、優先度７のトラフィックフローの転送時間は、優先度１のトラフィックフローを優先することにより優先度７のトラフィックフロー単体で送信される場合に比べて多くの時間を要する。このように、従来の技術ではトラフィックフローの集中具合によって転送時間が不安定になることがあり、アプリケーションが安定して動作しない場合があった。
【０００４】
本発明は、以上の点に鑑み、例えば以下のような目的を達成するものである。
・トラフィックフロー毎に、送信帯域を保証する送信処理スケジューリングを可能とすること。
・送信待ちキューにキューイングされたデータについて、最も保証帯域の達成度が低いトラフィックフローに最優先の送信スケジューリングを動的に行うことにより、送信待ちデータがある限り回線の空きなどの無駄が生じることがないようにすること。
・回線速度、平均パケット長に基づいて送信帯域を監視する単位時間を調整することにより、送信待ちキューの遅延時間と帯域保証の精度を調整すること。
【０００５】
【課題を解決するための手段】
本発明では、保証送信帯域をトラフィックフロー（ある一連のデータ）毎に「単位時間内に送信を保証すべき送信オクテット数」と「それに対する達成度」で管理する。送信処理は、トラフィックフロー毎に送信待ちキューを設け、各キュー毎に送信したオクテット数を管理し、送信を保証すべきオクテット数に対して送信したオクテット数の達成度が最も低いキューを優先的に選択して送信するスケジューリング方式とする。送信処理の際、トラフィックフローの偏りを是正するため、単位時間毎に送信オクテット数、達成度の制御変数をリセットする。また、帯域を保証しないトラフィックフローは、保証帯域を達成したトラフィックフローと同等に扱う。これにより、帯域を保証すべきトラフィックフローで保証帯域を達成していないトラフィックフローが存在しない場合は、保証帯域を達成したトラフィックフロー、または帯域を保証しないトラフィックフローのいずれかを回線に送信することができ、回線の空きの発生を防ぐことが可能となる。
【０００６】
本発明の第１の解決手段によると、
ある一連の転送データであるトラフィックフロー毎の送信待ちキューを有し、
前記トラフィックフロー毎の単位時間あたりに送信すべきデータ量を示す保証帯域と、前記トラフィックフロー毎に前記送信待ちキューから送信したデータ量とを管理し、
前記送信すべきデータ量を示す前記保証帯域に対する前記送信したデータ量によって表される前記保証帯域の達成度を求め、前記達成度が低いトラフィックフローのキューを優先的に選択して送信するようにした帯域保証送信方法を提供する。
【０００７】
本発明の第２の解決手段によると、
ある一連の転送データであるトラフィックフロー毎の送信待ちキューと、トラフィックフロー別に応じてデータをキューイングする送信待ちキューテーブルと、各トラフィックフロー毎に、単位時間あたりに保証する帯域幅をデータ数単位で管理する送信帯域保証テーブルと、各トラフィックフロー毎に単位時間内に送信したデータ数を管理する送信帯域値テーブルと、各トラフィックフロー毎に前記送信帯域値テーブルのラップアラウンド回数を管理する送信帯域値ラップアラウンド回数管理テーブルとを有するメモリと、
ネットワークに接続される入出力処理部と、
前記メモリに基づき、前記入出力処理部によるデータ送信を制御する制御部と
を備え、
前記制御部は、
前記トラフィックフロー毎の単位時間あたりに送信すべきデータ量を示す保証帯域と、前記トラフィックフロー毎に前記送信待ちキューから送信したデータ量とを管理し、
前記送信すべきデータ量を示す前記保証帯域に対する前記送信したデータ量によって表される前記保証帯域の達成度を求め、前記達成度が低いトラフィックフローのキューを優先的に選択して送信するようにした帯域保証送信装置を提供する。
【０００８】
【発明の実施の形態】
本発明の実施の形態を、以下に図面を用いて説明する。
【０００９】
（Ｉ）単位時間について
まず、保証帯域とそれに対する達成度を監視する「単位時間」について考察する。単位時間は、帯域保証の効果が十分得られるほどに長く、かつ、トラフィックフローの偏り(特定のトラフィックフローの集中)の影響を長く残さないほどに短い時間に設定する必要がある。
【００１０】
例えば、9,600ビット/秒の回線上に平均1,500オクテットのパケットを転送するシステムで単位時間を１秒に設定する場合を想定する。この場合、１パケットの転送で単位時間に送信可能なオクテット数を上回ることになり、帯域保証の効果は現れない（事実上のFirst In First Out方式になる)。つぎに、例えばこのような回線速度で平均パケット長のシステムにおいて単位時間を100秒に設定する場合を想定する。この場合、保証すべき保証帯域10％の96,000ビット/100秒のトラフィックフローが単位時間の最初に集中した場合、わずか８パケットの送信で保証帯域を達成してしまい、以降の90秒間は、保証帯域を達成していない他のトラフィックフローが存在する限り当該トラフィックフローの送信ができなくなり、トラフィックフローの偏りを長く残すとともに実用に耐えないシステムとなる。
【００１１】
以上より、本発明では、単位時間はシステムの平均パケット長と回線速度から、帯域保証の精度と送信待ちキューでの待ちによる遅延時間を考慮して、以下のプロセスで最適な値を決定する。
【００１２】
i)単位時間毎の回線のスループットに占める１パケットの割合の算出
例えば、9,600ビット/秒の回線上に平均1,500オクテットのパケットを転送するシステムで単位時間を１秒とすると、回線のスループットに占める１パケットの割合は、以下▲１▼式により125％となり、１パケットの転送が単位時間あたりの回線のスループットを超えているため、帯域保証の効果は現れない。
(1,500(オクテット)×8(ビット/オクテット))÷(9,600(ビット/秒)×1(秒(単位時間)))×100＝125(％)−▲１▼
【００１３】
また、例えば、9,600ビット/秒の回線上に平均1,500オクテットのパケットを転送するシステムで単位時間を100秒とすると、回線のスループットに占める１パケットの割合は、以下▲２▼式により1.25％となり、1.25％程度の精度での帯域保証が可能になる。ただし、既に述べたように送信待ちキューでの待ちによる遅延時間は約100秒になるケースもある。
(1,500(オクテット)×8(ビット/オクテット))÷(9,600(ビット/秒)×100(秒(単位時間)))×100＝1.25(％)−▲２▼
【００１４】
ii)帯域保証の精度と送信待ちキューの遅延時間の評価
i)で述べたとおり、単位時間は送信待ちキューの遅延を表し、単位時間の回線の送信スループットに占める１パケットの割合が帯域保証の精度を表す。また、単位時間と帯域保証の精度は互いに背反する関係にある。
【００１５】
以上を考慮し、回線速度(固定値)、平均パケット長(固定値)から、帯域保証の精度、送信待ちキューの遅延を算出/評価して単位時間を決定する。
【００１６】
上述i)の▲２▼式に示したように、9,600ビット/秒の回線上に平均1,500オクテットのパケットを転送するシステムで1％程度の精度の帯域保証を行うと送信待ちキューの遅延が大きくなりすぎる。仮に10％程度の精度の帯域保証を行うと、以下▲３▼式よりｔ＝12.5秒となり、送信待ちキューでの遅延時間は12秒程度になる。(1,500(オクテット)×8(ビット/オクテット))÷(9,600(ビット/秒)×ｔ(秒(単位時間)))×100＝10(％)−▲３▼
【００１７】
以上のように、互いに背反する帯域保証の精度と送信待ちキューの遅延を試算して、システムに最適な単位時間を決定する。
【００１８】
（ＩＩ）ハード構成
図１に、本発明を適用するシステムの構成図を示す。本発明の適用の一例としては、ＩＰネットワークにおけるネットワーク間接続装置の送信待ちキューに適用するケースが考えられる。
【００１９】
ネットワーク間接続装置１は、ネットワークとネットワークを接続するための装置である。ネットワーク間接続装置１は、ＣＰＵ２、メモリ３、入出力処理部４を備える。ネットワーク間接続装置１は、また、メモリ３上に各制御テーブル類５、送信待ちキュー６を保持して各ネットワーク間でのデータのルーティング処理を実行する。ネットワーク間接続装置１では、回線速度が異なるネットワーク同士を接続するケースがあり、回線速度の速いネットワークから回線速度の遅いネットワークにデータを送信する時に、データ送信時のデータ送信待ちが発生する場合がある。ネットワーク間接続装置１をはじめとする各ネットワーク機器では、一般にこれらのデータ送信待ちに対して「送信待ちキュー６」を用いて待ち制御を行う。本発明は、例えば、この「送信待ちキュー６」からデータを取り出すスケジューリング処理に適用することができる。
【００２０】
図２に、制御テーブル類５および送信待ちキュー６の説明図を示す。本発明では、処理に必要な以下のテーブル類を設ける。
(1)トラフィックフロー種別に応じてデータをキューイングする送信待ちキューテーブル２１を設ける。トラフィックフロー種別の決定は、例えばＩＰパケットのTOS値、送信元/宛先ＩＰアドレスに基づいて決定するなどが考えられる。
(2)各トラフィックフロー毎に、単位時間あたりに保証する帯域幅をオクテット数単位で管理する送信帯域保証テーブル２２を設ける。なお、オクテット数単位以外にも、ビット数等の適宜の値で管理することもできる。
(3)各トラフィックフロー毎に単位時間内に送信したオクテット数を管理する送信帯域値テーブル２３を設ける。なお、オクテット数以外にも、ビット数、割合等適宜の値で管理することができる。
(4）各トラフィックフロー毎に送信帯域値テーブル２３のラップアラウンド回数を管理する送信帯域値ラップアラウンド回数管理テーブル２４を設ける。ここで、カウンタなどが一巡することを、ラップアラウンド(wrap around)という。例えば、１バイトのカウンタを減算する場合、１→０→255で一巡となる。
(5)ラップアラウンド回数に応じて、どのキューにデータが存在するかを管理するキュー番号ビットマップテーブル２５を設ける。
【００２１】
以下に、本発明の処理方式を説明する。上述のような制御テーブル類５を用いて、以下に示す処理を行うことで、帯域保証制御を実現する。
【００２２】
（ＩＩＩ）処理概要
本実施の形態では、送信データをトラフィックフロー毎に送信待ちキューテーブル２１にキューイングする。そして、キューイングされているトラフィックフローのうち、保証帯域に対する送信帯域の達成度が最も低いトラフィックフローを優先して送信する。
【００２３】
本実施の形態では、達成度をキュー番号ビットマップテーブル２５で管理するようにした。なお、キュー番号ビットマップテーブル２５を設けずに、送信帯域値ラップアラウンド回数管理テーブル２４で管理するようにしてもよい。キュー番号ビットマップテーブル２５の配列の若番エントリ(ラップラウンド回数０)の達成度が低く、老番エントリ(ラップラウンド回数Ｍ)の達成度が高い。なお、最老番エントリは、帯域保証済みをあらわす。キュー番号ビットマップテーブル２５のエントリ内の各ビットは、トラフィックフローにマッピングできる。最老番エントリ(帯域保証済み)は、帯域を保証しないトラフィックフローを固定的に割り当てて、他のトラフィックフローがすべて保証帯域を達成した、又は、送るべき他のトラフィックフローが存在しない場合のみ送信するという制御にも使うことができる。キュー番号ビットマップテーブル２５は、２エントリ(保証帯域未達成エントリと保証帯域達成済みエントリ)の構成も可能であるが、その構成では保証帯域未達成のトラフィック相互の優先関係をきめ細かく制御できない。このため、保証帯域を数段階に分けてキュー番号ビットマップテーブル２５のエントリ番号にマッピングする。図２を例にとると、エントリ０番からエントリＭ−１番が保証帯域未達成エントリで、エントリＭ番が保証帯域達成エントリである。なお、ここでは、Ｍ以上については、ひとつのエントリＭ番でまとめて扱っているが、これに限らずＭ＋１番又は適宜のエントリとして記憶することもできる。
【００２４】
保証帯域を何段階に分けるかについては、段階が多ければきめ細かな制御が可能となるが、本実施の形態のように送信オクテット数に基づいて帯域を管理する場合には、回線速度と平均パケット長に基づいて決定するアプローチが一例として考えられる。例えば、保証帯域16,000オクテット/秒、平均パケット長が1,500バイトのシステムの場合、約１１パケットの送信で保証帯域を達成する。そこで、保証帯域を１１段階に分けることで１パケットの送信がトラフィックフロー間の１段階の優先度の差異(即ち、キュー番号ビットマップテーブル２５の値の１エントリの差異)となって現れることが期待できる。この場合、キュー番号ビットマップテーブル２５の値のＭは１２となる。
【００２５】
本発明では、また、上述のように帯域保証値を１１段階に分ける場合、(保証帯域÷１１)バイトを何回送信したかを管理するようにした。この管理を実現するため、トラフィックフロー毎に(保証帯域÷段階)値と、(保証帯域÷段階)値を何回送信したかを管理するテーブルを持つ。(保証帯域÷段階)値は、送信帯域保証テーブル２２(図2-▲２▼)と送信帯域値テーブル２３で管理する。何回送信したかは、送信帯域値ラップアラウンド回数管理テーブル２４で管理する。
【００２６】
例えば、保証帯域16,000オクテットのトラフィックフローでは、送信帯域保証テーブル２２と送信帯域値テーブル２３の該トラフィックフローに対応するエントリに、各々1500を設定する。送信帯域値ラップアラウンド回数管理テーブル２４の各エントリは、０で初期化し、あるトラフィックフローでパケットを送信するたびに送信帯域値テーブル２３の該エントリから送信オクテット長を減じて、ラップアラウンドが発生する毎に送信帯域値ラップアウンド回数管理テーブル２４の該エントリを＋１する。送信帯域値ラップアラウンド回数管理テーブルで管理しているトラフィックフロー毎のラップアラウンド回数は、保証帯域に対する達成度を表し、キュー番号ビットマップテーブル２５のエントリにマッピングすることができる。
【００２７】
本発明における処理としては、例えば、(1)制御テーブル類５の初期化処理、(2)送信要求の受付処理、(3)送信スケジューリング処理、(4)送信処理、(5)制御テーブル類５の再初期化処理に、大別することができる。
【００２８】
送信要求受け付け処理は、送信待ちキューテーブル２１のトラフィックフロー種別に対応するエントリに送信パケットをキューイングするとともに、送信帯域値ラップアラウンド回数管理テーブル２４の達成度(即ち、ラップアラウンド回数)に対応するキュー番号ビットマップテーブル２５のエントリのトラフィックフロー種別に対応するビットを１に設定して、当該キューにキューイングが発生していることを示す。送信スケジューリング処理は、キュー番号ビットマップテーブル２５の若番エントリから順にビットを検索して、ビットが１に設定されているトラフィックフローについて送信待ちキューテーブル２１からパケットを取り出して送信する。
【００２９】
送信処理は、送信帯域値テーブル２３の更新と、必要ならば送信帯域値ラップアラウンド回数管理テーブル２４とキュー番号ビットマップテーブル２５の更新を行う。さらに、送信スケジューリング処理が取り出したトラフィックフローに対応する送信帯域値テーブル２３のエントリから送信パケットのオクテット数を減じる。この際にラップアラウンドが発生する場合(即ち、送信パケット長が送信帯域値テーブル２３の当該エントリ値より大きいケース)は、当該エントリの初期値を送信帯域保証テーブル２２から取り出して、ラップアラウンド処理を行う(即ち、送信帯域保証テーブル２２の当該エントリ値をワーク変数に取り出し、ワーク変数から送信パケット長を減じたものを送信帯域値テーブル２３の当該エントリに設定する。)。さらに、送信帯域値ラップアラウンド回数管理テーブル２４のトラフィックフローに対応するエントリを加算し、キュー番号ビットマップテーブル２５の加算前のラップアラウンド回数エントリのトラフィックフローに対応するビットをオフし、加算後のラップアラウンド回数エントリのトラフィックフローに対応するビットをオンする。これにより、達成度が上がった(即ち、ラップアラウンド回数増加)ことで、送信優先度が下がる（即ち、キュー番号ビットマップテーブル２５のエントリが下がる。）。
【００３０】
（ＩＶ）処理詳細
本処理の詳細について、テーブル状態遷移図とフローチャートを用いて、以下の条件の例に沿って説明する。また、図３〜図５に、各処理による制御テーブル類５の状態遷移図（１）〜（３）を示す。
（例）
回線速度：9,600bps
平均パケット長：800バイト
単位時間：５秒
単位時間に送信可能なデータ量：6,000バイト
保証帯域達成の段階：６段階(６段目は保証帯域達成済み)
保証帯域の最大誤差：約13％((800×8)÷(9,600×5)×100)
トラフィックフロー種別と各帯域：フロー０→30％、フロー１→70％
【００３１】
なお、これら回線速度、単位時間、保証帯域達成の段階、トラフィックフロー毎の保証帯域などは、あらかじめ装置に設定しておくか、又は、外部からデータで渡すなどの手段を用いることができる。
【００３２】
(1)制御テーブル類５の初期化処理
図６に、制御テーブル初期化処理のフローチャートを示す。
【００３３】
まず、送信待ちキューテーブル２１の全エントリを０クリアする(ステップ400）。つぎに、送信帯域保証テーブル２２と送信帯域値テーブル２３の全エントリに、各トラフィックフローの単位時間の保証帯域÷(保証帯域達成の段階-1)を設定する。但し、未使用のエントリには、例えば０を設定するなどで使用中エントリとの区別がつくようにする（ステップ410）。本例では、単位時間あたり30％の帯域を保証するフロー０の設定値は以下の式により360となり、単位時間あたり70％の帯域を保証するフロー１の設定値は同様に840となる。
(((9,600×5)÷8)×0.3)÷(6-1)＝360
【００３４】
つぎに、送信帯域値ラップアラウンド回数管理テーブル２４の全エントリを０クリアする(ステップ420)。また、キュー番号ビットマップテーブル２５の全エントリを０クリアする(ステップ430）。
【００３５】
本例について初期化処理実行後の各種テーブル類の状態は、図３の状態番号▲１▼の通りとなる。
【００３６】
(2)送信要求の受付処理
図７に、送信要求受け付け処理のフローチャートを示す。ここでは、データの送信要求を受け付けると、データ毎に以下の処理が実行される。
【００３７】
まず、送信トラフィックフロー種別毎に、送信待ちキューテーブル２１の対応するエントリに送信データをキューイングする（ステップ500）。つぎに、キューイングするトラフィックフローが、帯域を保証すべきトラフィックフローかどうかを判定する（ステップ510）。これを判定するために、トラフィックフロー毎の保証帯域が０％に設定されていたら、帯域保証する必要はないとみなすなどの判定方法が考えられる。つぎに、帯域を保証すべきトラフィックフローである場合、変数χに送信帯域値ラップアラウンド回数管理テーブル２４の当該トラフィックフローに対応するエントリを取り出す（ステップ520）。変数χがＭ(キュー番号ビットマップテーブル２５の最老番エントリ)より大きい場合は（ステップ530）、変数χにＭを設定する（ステップ540）。帯域を保証しないトラフィックフローである場合も同様に変数χにＭを設定する（ステップ540）。つぎに、キュー番号ビットマップテーブル２５の変数χに対応するエントリの、当該トラフィックフローに対応するビットを１に設定する（ステップ550）。
【００３８】
本例について、フロー０のデータ４個、フロー１のデータ６個の送信要求を受け付けたときの各種テーブル類の状態は、図３の状態番号▲２▼の通りになる。
【００３９】
(3)送信スケジューリング処理
図８に、送信スケジュール処理のフローチャートを示す。本処理は、最初のデータ送信受付け直後または１データ送信完了時に、次の送信データを選択するために実行される。
【００４０】
まず、キュー番号ビットマップテーブル２５のエントリカウンタＩを０に初期化する（ステップ600）。ＩがＭ(段階)以下の場合は以下の処理(キュー番号ビットマップテーブル２５の変数Ｉ番目のエントリのビット’１’検索処理)を実行し、Ｍより大きい場合は処理を完了する(ステップ610）。ＩがＭ以下の場合、キュー番号ビットマップテーブル２５エントリのビットカウンタＪを０に初期化する（ステップ620）。なお、図2において、Ｉは縦方向のカウンタ（ラップアラウンド回数：０〜Ｍ）、Ｊは横方向のカウンタ（トラフィックフロー番号：０〜ｎ）をそれぞれ示す。Ｊがｎ(トラフィックフロー種別数)以下の場合は以下の処理を実行し、ｎより大きい場合はＩをカウントアップして、ステップ610に戻る（ステップ630、ステップ670）。Ｊがｎ以下の場合、キュー番号ビットマップテーブル２５のＩ番目のエントリ値を検索し、Ｊ番目のビットが非ゼロなら当該のトラフィック種別の送信処理にＩ、Ｊを渡して呼び出しを行い(ステップ650)、ゼロならＪをカウントアップして、ステップ630に戻る（ステップ660）。
【００４１】
(4)送信処理
図９に、送信処理のフローチャートを示す。ここでは、図８で示した送信スケジューリング処理からの要求にしたがって送信処理を実行する。
【００４２】
送信処理は、送信スケジューリング処理からキュー番号ビットマップテーブル２５のエントリカウンタＩとキュー番号ビットマップテーブル２５エントリのビットカウンタＪを指定して呼び出される（ステップ700）。つぎに、送信要求処理から指定されたトラフィックフロー番号(キュー番号ビットマップテーブルエントリのビットカウンタＪ)に従い、送信待ちキューテーブル２１の当該トラフィックフローのキューより１パケット送信する（ステップ710）。つぎに、送信データ長を送信帯域値テーブル２３の当該トラフィックフローのエントリから減算する(ステップ720）。送信帯域値テーブル２３がラップアラウンドしているかしていないかを判定し（ステップ730）、ラップアラウンドしていない場合は処理を終了し、ラップアラウンドしている場合は以下の処理を実行する。
【００４３】
まず、送信帯域値ラップアラウンド回数管理テーブル２４の当該トラフィックフローのエントリにラップアラウンドする回数を加算する（ステップ740）。この際、送信データ長カウンタが０から初期値になったらラップアラウンド１回発生と考え、当該カウンタの初期値は送信帯域保証テーブル２２の当該トラフィックフローのエントリから取得する。そして、キュー番号ビットマップテーブル２５のエントリカウンタＩに対応するエントリの当該トラフィックフローに対応するビットをオフする（ステップ750）。また、キュー番号ビットマップテーブル２５の更新後のラップアラウンド回数に対応するエントリの当該トラフィックフローに対応するビットをオンする（ステップ760）。
【００４４】
以上、(3)送信スケジューリング処理、(4)送信の処理に関して、図３〜図５の例を用いて説明すると以下の通りとなる。
(i)  図３の状態番号▲２▼では、キュー番号ビットマップテーブル２５からエントリ０のビット０を検出し、フロー０のデータを800バイト送信する（単位時間で6,000バイト送信可能なうち、800バイト送信）。これにより送信データ長カウンタは２ラップして280となり、送信帯域値テーブル２３と送信帯域値ラップアラウンド回数管理テーブル２４とキュー番号ビットマップテーブル２５を更新することで、各制御テーブル類５は状態番号▲３▼に示すような状態となる。
【００４５】
(ii)  図３の状態番号▲３▼では、キュー番号ビットマップテーブル２５からエントリ０のビット１を検出し、フロー１のデータを800バイト送信する（単位時間で6,000バイト送信可能なうち、1,600バイト送信）。これでは送信データ長カウンタのラップは発生せず、送信帯域値テーブル２３を更新することで、各制御テーブル類５は状態番号▲４▼に示すような状態となる。
【００４６】
(iii)  図４の状態番号▲４▼では、キュー番号ビットマップテーブル２５からエントリ０のビット１を検出し、フロー１のデータを800バイト送信する（単位時間で6,000バイト送信可能なうち、2,400バイト送信）。これにより送信データ長カウンタは１ラップして80となり、送信帯域値テーブル２３と送信帯域値ラップアラウンド回数管理テーブル２４とキュー番号ビットマップテーブル２５を更新することで、各制御テーブル類５は状態番号▲５▼に示すような状態となる。
【００４７】
(iv)  図４の状態番号▲５▼では、キュー番号ビットマップテーブル２５からエントリ１のビット１を検出し、フロー１のデータを800バイト送信する（単位時間で6,000バイト送信可能なうち、3,200バイト送信）。これにより送信データ長カウンタは１ラップして120となり、送信帯域値テーブル２３と送信帯域値ラップアラウンド回数管理テーブル２４とキュー番号ビットマップテーブル２５を更新することで、各制御テーブル類５は状態番号▲６▼に示すような状態となる。
【００４８】
(v)  図４の状態番号▲６▼では、キュー番号ビットマップテーブル２５からエントリ２のビット０を検出し、フロー０のデータを800バイト送信する（単位時間で6,000バイト送信可能なうち、4,000バイト送信）。これにより送信データ長カウンタは２ラップして160となり、送信帯域値テーブル２３と送信帯域値ラップアラウンド回数管理テーブル２４とキュー番号ビットマップテーブル２５を更新することで、各制御テーブル類５は状態番号▲７▼に示すような状態となる。
【００４９】
(vi)  図４の状態番号▲７▼では、キュー番号ビットマップテーブル２５からエントリ２のビット１を検出し、フロー１のデータを800バイト送信する（単位時間で6,000バイト送信可能なうち、4,800バイト送信）。これにより送信データ長カウンタは１ラップして160となり、送信帯域値テーブル２３と送信帯域値ラップアラウンド回数管理テーブル２４とキュー番号ビットマップテーブル２５を更新することで、各制御テーブル類５は状態番号▲８▼に示すような状態となる。
【００５０】
(vii)  図５の状態番号▲８▼では、キュー番号ビットマップテーブル２５からエントリ３のビット１を検出し、フロー１のデータを800バイト送信する（単位時間で6,000バイト送信可能なうち、5,600バイト送信）。これにより送信データ長カウンタは１ラップして200となり、送信帯域値テーブル２３と送信帯域値ラップアラウンド回数管理テーブル２４とキュー番号ビットマップテーブル２５を更新することで、各制御テーブル類５は状態番号▲９▼に示すような状態となる。
【００５１】
(viii)  図５の状態番号▲９▼では、キュー番号ビットマップテーブル２５からエントリ４のビット０を検出し、フロー０のデータを800バイト送信する（単位時間で6,000バイト送信可能なうち、6,400バイト送信。すなわち、本処理で単位時間内の処理を終了する。）。これにより送信データ長カウンタは２ラップして80となり、送信帯域値テーブル２３と送信帯域値ラップアラウンド回数管理テーブル２４とキュー番号ビットマップテーブル２５を更新することで、各制御テーブル類５は状態番号10に示すような状態となる。
【００５２】
以上で単位時間内の処理を完了するが、結果は、フロー０：2,400バイト送信(37.5%)、フロー１：4,000バイト送信(62.5%)であり、13%以内の誤差に収まっている。
【００５３】
(5)制御テーブル類５の再初期化処理
図１０に、制御テーブル類５の再初期化処理のフローチャートを示す。
【００５４】
この処理では、トラフィックの偏りを引きずらないように単位時間毎に制御テーブル類５をリセットする。まず、送信帯域値テーブル２３の全エントリに送信帯域保証テーブル２２の全エントリをコピーする（ステップ800）。つぎに、送信帯域値ラップアラウンド回数管理テーブル２４の各エントリを０クリアする（ステップ810）。さらに、キュー番号ビットマップテーブル２５のエントリ０にキュー番号ビットマップテーブル２５のエントリ０からエントリＭまでの論理和演算結果を設定する（ステップ820）。つぎに、キュー番号ビットマップテーブル２５のエントリ１からエントリＭまでに０を設定する(ステップ830）。また、キュー番号ビットマップテーブル２５のエントリ０のうち、帯域保証を行わないフローに対応するビットをオフする（ステップ840）。そして、キュー番号ビットマップテーブル２５のエントリＭのうち、帯域保証を行わないフローに対応するビットをオンする（ステップ850）。
【００５５】
本例について、制御テーブル類５再初期化後の各種テーブル類の状態は、図５の状態番号11の通りになる。
【００５６】
【発明の効果】
本発明は、以上のように、例えば以下のような効果を奏する。
・トラフィックフロー毎に、送信帯域を保証する送信処理スケジューリングを可能となること。
・送信待ちキューにキューイングされたデータについて、最も保証帯域の達成度が低いトラフィックフローに最優先の送信スケジューリングを動的に行うことにより、送信待ちデータがある限り回線の空きなどの無駄が生じることがないこと。
・回線速度、平均パケット長に基づいて送信帯域を監視する単位時間を調整することで、送信待ちキューの遅延時間と帯域保証の精度を調整できること。
【図面の簡単な説明】
【図１】本発明を適用するシステムの構成図。
【図２】制御テーブル類５および送信待ちキュー６の説明図。
【図３】各処理による制御テーブル類５の状態遷移図（１）。
【図４】各処理による制御テーブル類５の状態遷移図（２）。
【図５】各処理による制御テーブル類５の状態遷移図（３）。
【図６】制御テーブル初期化処理のフローチャート。
【図７】送信要求受け付け処理のフローチャート。
【図８】送信スケジュール処理のフローチャート。
【図９】送信処理のフローチャート。
【図１０】制御テーブル類５の再初期化処理のフローチャート。
【符号の説明】
１  ネットワーク間接続装置
２  ＣＰＵ
３  メモリ
４  入出力処理部
５  制御テーブル類
６  送信待ちキュー
【図１】
0004426010.tif 000002
【図２】
0004426010.tif 000003
【図３】
0004426010.tif 000004
【図４】
0004426010.tif 000005
【図５】
0004426010.tif 000006
【図６】
0004426010.tif 000007
【図７】
0004426010.tif 000008
【図８】
0004426010.tif 000009
【図９】
0004426010.tif 000010
【図１０】
0004426010.tif 000011