(57)【要約】【課題】イーサネット（登録商標）フレーム等の可変長パケットを多重又はスイッチングする通信システムに適用される可変長パケットの帯域制御装置に関し、各ユーザ／トラヒック間の公平性を保ったまま、未使用帯域の発生を防ぎ、ネットワークの帯域の有効利用を図る。【解決手段】ＶＩＤ＝１〜ＶＩＤ＝ｎの複数のキューに格納された可変長の各パケットデータを、重み付け読み出しテーブル１３−１に従い、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出して送出する。その際、送信権を与えられたキューから、１回の送信権で送出可能なバイト数未満のパケットデータを送出した場合に、残余のバイト以下のパケットが他のキューに存在するかを、パケット有無検索部１−４により、パケット情報管理テーブル１−３から順番に検索し、存在する場合、該残余バイトで他のキューのパケットデータを読み出し送出する。【選択図】      図１
2004153482.tif 000002
【特許請求の範囲】
【請求項１】
複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、
前記重み付けラウンドロビンにより送信権を与えられたキューから、１回の送信権で送出可能なバイト数未満のパケットデータを送出した場合に、
１回の送信権で送出可能なバイト数から実際に送出したパケットデータのバイト数を差し引いた残余のバイトを使用して、他のキューのパケットデータを読み出し送出する手段と、
前記残余のバイトを使用してパケットデータを読み出す他のキューを、所定の順番で順次選択する手段と、
を備えたことを特徴とする可変長パケットの帯域制御装置。
【請求項２】
複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、
前記重み付けラウンドロビンにより送信権を与えられたキューから、１回の送信権で送出可能なバイト数に等しくなるか又はそのバイト数を超過するかの何れかの条件を満たすまで、当該キューの後続のパケットデータを読み出し送出する手段を備えたことを特徴とする可変長パケットの帯域制御装置。
【請求項３】
前記１回の送信権で送出可能なバイト数を超過するまで、パケットデータを読み出し送出した場合に、該超過して読み出した超過バイト数を各キュー対応に保持する手段と、
前記各キュー対応に保持した超過バイト数を元々の１回の送信権で送出可能なバイト数から差し引いたバイト数を、次回に与える各キューへの送信権による送出可能バイト数として設定する手段と、
１回の送信権で送出可能なバイト数を超過することなく、全パケットデータを読み出し終えたキューに対して、前記超過バイト数の値をゼロにリセットする手段と、
を備えたことを特徴とする請求項２に記載の可変長パケットの帯域制御装置。
【請求項４】
グループ化された複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、
送信権を与えられたキューからパケットデータを送出し、該キューの１回の送信権で送出可能なバイト数に残余がある場合に、該送信権を与えられたキューと同一グループ内の他のキューから、１回の送信権で送出可能なバイト数に等しくなるか又はそのバイト数を超過するかの何れかの条件を満たすまで、当該キューの同一グループ内の他のキューのパケットデータを読み出し送出する手段を備えたことを特徴とする可変長パケットの帯域制御装置。
【請求項５】
前記同一グループの他のキューから、１回の送信権で送出可能なバイト数を超過するまでパケットデータを読み出し送出した場合に、該超過して読み出した超過バイト数を各グループ単位に保持する手段と、
送信権を与えられたキューからパケットデータを送出し、該キューの１回の送信権で送出可能なバイト数に残余がある場合に、該残余のバイト数から、前記各グループ単位に保持した超過バイト数を差し引いた値が正である場合、その差し引いた値を、同一グループ内の他のキューの送出可能バイト数として設定する手段と、
前記１回の送信権で送出可能なバイト数を超過することなく、同一グループ内のキューの全パケットデータを読み出し終えたグループに対して、該グループ単位の超過バイト数の値をゼロにリセットする手段と、
前記残余のバイト数から前記各グループ単位に保持した超過バイト数を差し引いた値がゼロ以下である場合、該グループ単位に保持した超過バイト数から、該残余のバイト数を差し引いた値を、次回のグループ単位の超過バイト数として保持する手段と、
を備えたことを特徴とする請求項４に記載の可変長パケットの帯域制御装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、イーサネット（登録商標）フレーム等の可変長パケットを多重又はスイッチングする通信システムに好適に適用される可変長パケットの帯域制御装置に関する。
【０００２】
これまで、広域性と高信頼性とが要求されるコア網は、ＳＤＨ（Ｓｙｎｃｈｒｏｎｏｕｓ  Ｄｉｇｉｔａｌ  Ｈｉｅｒａｒｃｈｙ  ）やＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）技術を適用したネットワークが主に用いられてきた。ところが、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）の世界的な急速な普及により、イーサネットスイッチを始めとするＬＡＮ機器の低価格化が進み、大規模企業ユーザを含む大多数のエンドユーザがイーサネット技術を用いたＬＡＮを導入するようになり、アクセス網やコア網にも、安価にネットワーク構築が可能なイーサネット技術を利用した通信サービスネットワークが普及してきた。
【０００３】
イーサネット技術をベースにした通信サービスネットワークの全体構成を図１２に示す。同図において、１２−１は企業体等の各ユーザ毎にそれぞれＬＡＮによって構築されるユーザ網である。１２−２はＦＴＴＨ（Ｆｉｂｅｒ  Ｔｏ  Ｔｈｅ  Ｈｏｍｅ  ）、ＯＮＵ（Ｏｐｔｉｃａｌ  Ｎｅｔｗｏｒｋ  Ｕｎｉｔ）又はＤＳＵ（Ｄｉｇｉｔａｌ  Ｓｅｒｖｉｃｅ  Ｕｎｉｔ）などにより、ユーザ網１２−１と加入者終端装置１２−５とを接続するアクセス網である。
【０００４】
また、１２−３は、イーサネット技術を利用し、コアスイッチ１２−４によりネットワークを構成し、アクセス網１２−２に接続される加入者終端装置１２−５を収容するコア網である。本発明は、図中のコアスイッチ１２−４を始め、イーサネット技術を使用する全てのスイッチ装置や多重装置に適用可能である。
【０００５】
ユーザが要求する通信サービスのトラヒックには、ＷＥＢページ閲覧、電子メール、ＩＰ電話など様々なサービスがある。これらの通信サービスのトラヒックを収容するスイッチや多重装置は、トラヒック種別又はサービス品目（ユーザ単位）に応じた優先制御を行わなければならない。
【０００６】
このため、ユーザ／トラヒック毎に帯域保証や遅延保証を行う技術が種々提案されている。ネットワーク内で、ユーザ／トラヒック毎に帯域保証を行う方式として、各ユーザ／トラフィック毎に重み付けを設定し、該重み付けに従って周期的にトラヒックデータの読み出し制御を行う重み付けラウンドロビン（ＷＲＲ：Ｗｅｉｇｈｔｅｄ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）方式や、一定周期毎にトラヒックデータの読み出し可能バイト数を分配するトークン方式などがある。
【０００７】
【従来の技術】
図１３に従来の重み付けラウンドロビン（ＷＲＲ）による読み出し制御部のモデルを示す。図１３において、キューの単位は、バーチャルＬＡＮや、送信元ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）アドレスなど、帯域制御を行う単位であれば、どのようなものでもよく、ここでは、バーチャルＬＡＮ単位に帯域制御を行う例について説明する。
【０００８】
図１３に示す重み付けラウンドロビン（ＷＲＲ）の読み出し制御部では、バーチャルＬＡＮ単位に帯域制御を行うため、各バーチャルＬＡＮ毎に個別キューを備え、入力されたパケットデータ（トラヒックデータ）を各バーチャルＬＡＮ毎の個別のキューへ振り分ける。なお、ＶＩＤは各バーチャルＬＡＮの識別情報（識別番号）である。
【０００９】
また、重み付けラウンドロビン（ＷＲＲ）の読み出し制御において、重み付け読み出しテーブル１３−１を具備し、この重み付け読み出しテーブル１３−１のエントリーに、パケットデータを読み出すキューの識別情報（ＶＩＤ）を格納し、読み出し制御部は、該重み付け読み出しテーブル１３−１のエントリーを順番に巡回しながら読み出し、読み出したエントリーの識別情報（ＶＩＤ）のキューからパケットデータを読み出す。
【００１０】
ここで、重み付け読み出しテーブル１３−１へのエントリー数が多いキューほど、パケットデータの読み出しの機会が増えるため、帯域が増大する。また、重み付け読み出しテーブル１３−１の１回のエントリーアクセス期間に、キューから読み出すことができるバイト数が、１回のキュー読み出しに与えられる送出可能バイト数となる。
【００１１】
図１４に従来の重み付けラウンドロビン（ＷＲＲ）による読み出し制御の例を示す。同図に示すように、或る識別情報（ＶＩＤ）のキューへ、Ｘバイト及びＹバイトの２つのパケットデータが入力された後、この識別情報（ＶＩＤ）のキューの読み出し順番が回って来たとする。
【００１２】
このとき、当該キューには２つのパケットが溜まっている状態である。ここで、各キューに与えられた１つのエントリー（１回の送信権）で読み出し可能なバイト数をＡバイトとし、（Ｘバイト＋Ｙバイト）＞Ａバイト、であったとする。
【００１３】
ここで、Ａバイトの読み出し可能バイト数に対して、Ｘバイト及びＹバイトの２パケットを読み出して送出してしまうと、｛（Ｘバイト＋Ｙバイト）−Ａバイト｝分だけ、余分にパケットデータ送出することになるため、従来技術では、最初に到着したＸバイトのパケットデータのみを読み出し、次のＹバイトのパケットデータは、次回の送信権が与えられたときの読み出し機会に送出していた。
【００１４】
図１５に従来の重み付けラウンドロビン（ＷＲＲ）による未使用帯域の発生例を示す。Ｘバイト＜Ａバイト、であった場合、（Ａバイト−Ｘバイト）分の残余帯域が発生するが、従来の重み付けラウンドロビン（ＷＲＲ）による読み出し制御では、各キュー間の公平性を保つために、残余帯域分を詰めて次のエントリーのキューを読み出すことをせず、図１５に示すように、パケット間ギャップを未使用帯域として処理していた。
【００１５】
そのほかの本発明に関連する先行技術として、広域ネットワークなどの他のネットワークを横断して伝送する加入者構内のネットワーク又はサブネットワーク（代表的にはイーサネット）を発信元とする通信に対して、要求があり次第帯域幅を選択的に割り当てることができる加入者端点装置について下記の特許文献１に開示されている。
【特許文献１】
特表２００２−５２６９７９号公報
【００１６】
【発明が解決しようとする課題】
従来の重み付けラウンドロビン（ＷＲＲ）方式では、ユーザ／トラフィック間の通信の公平性を実現するために、可変長のイーサネットのパケットを送出する場合、与えられた送信権による送出可能バイト数から、実際の送出パケットデータのバイト数を差し引いた残余のバイト数が、次に送出するパケットデータのバイト数に満たない場合は、そのパケットを送出しないこととしていたため、その帯域は未使用帯域となり、ネットワークの帯域が有効に利用されないという欠点があった。
【００１７】
本発明は、重み付けラウンドロビン（ＷＲＲ）方式を用いたイーサネットフレームのスイッチ装置又は多重装置等において、各ユーザ／トラヒック間の公平性を保ったまま、未使用帯域の発生を抑えて、ネットワークの帯域の有効利用を図ることを目的とする。
【００１８】
【課題を解決するための手段】
本発明の可変長パケットの帯域制御装置は、（１）複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、前記重み付けラウンドロビンにより送信権を与えられたキューから、１回の送信権で送出可能なバイト数未満のパケットデータを送出した場合に、１回の送信権で送出可能なバイト数から実際に送出したパケットデータのバイト数を差し引いた残余のバイトを使用して、他のキューのパケットデータを読み出し送出する手段と、前記残余のバイトを使用してパケットデータを読み出す他のキューを、所定の順番で順次選択する手段と、を備えたものである。
【００１９】
また、（２）複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、前記重み付けラウンドロビンにより送信権を与えられたキューから、１回の送信権で送出可能なバイト数に等しくなるか又はそのバイト数を超過するかの何れかの条件を満たすまで、当該キューの後続のパケットデータを読み出し送出する手段を備えたものである。
【００２０】
また、（３）前記１回の送信権で送出可能なバイト数を超過するまで、パケットデータを読み出し送出した場合に、該超過して読み出した超過バイト数を各キュー対応に保持する手段と、前記各キュー対応に保持した超過バイト数を元々の１回の送信権で送出可能なバイト数から差し引いたバイト数を、次回に与える各キューへの送信権による送出可能バイト数として設定する手段と、１回の送信権で送出可能なバイト数を超過することなく、全パケットデータを読み出し終えたキューに対して、前記超過バイト数の値をゼロにリセットする手段と、を備えたものである。
【００２１】
また、（４）グループ化された複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、送信権を与えられたキューからパケットデータを送出し、該キューの１回の送信権で送出可能なバイト数に残余がある場合に、該送信権を与えられたキューと同一グループ内の他のキューから、１回の送信権で送出可能なバイト数に等しくなるか又はそのバイト数を超過するかの何れかの条件を満たすまで、当該キューの同一グループ内の他のキューのパケットデータを読み出し送出する手段を備えたものである。
【００２２】
また、（５）前記同一グループの他のキューから、１回の送信権で送出可能なバイト数を超過するまでパケットデータを読み出し送出した場合に、該超過して読み出した超過バイト数を各グループ単位に保持する手段と、送信権を与えられたキューからパケットデータを送出し、該キューの１回の送信権で送出可能なバイト数に残余がある場合に、該残余のバイト数から、前記各グループ単位に保持した超過バイト数を差し引いた値が正である場合、その差し引いた値を、同一グループ内の他のキューの送出可能バイト数として設定する手段と、前記１回の送信権で送出可能なバイト数を超過することなく、同一グループ内のキューの全パケットデータを読み出し終えたグループに対して、該グループ単位の超過バイト数の値をゼロにリセットする手段と、前記残余のバイト数から前記各グループ単位に保持した超過バイト数を差し引いた値がゼロ以下である場合、該グループ単位に保持した超過バイト数から、該残余のバイト数を差し引いた値を、次回のグループ単位の超過バイト数として保持する手段と、を備えたものである。
【００２３】
【発明の実施の形態】
図１に本発明の第１の実施形態の構成を示す。入力ポートから到着する各パケットデータは、キュー振り分け部１−１においてバーチャルＬＡＮ識別情報（ＶＩＤ）が認識され、該バーチャルＬＡＮ識別情報（ＶＩＤ）はキュー制御部１−２へ通知される。
【００２４】
キュー制御部１−２は、キュー振り分け部１−１から通知されるバーチャルＬＡＮ識別情報（ＶＩＤ）に対応するキューへ、入力ポートからのパケットデータを書き込む。キュー制御部１−２はこれと同時に、キュー単位のパケット情報管理テーブル１−３を所定の条件に応じて更新する。
【００２５】
パケットデータの書き込み時に、パケット情報管理テーブル１−３を更新する条件は、そのバーチャルＬＡＮ識別情報（ＶＩＤ）のキューがこれまで空状態であって、到着パケットデータが該キューの先頭となる場合である。その場合、パケット情報管理テーブル１−３の該当するキューのＶＩＤ番号の“パケット有無”の欄に、パケットデータが到着する前は  “無し”を表す“０”が格納され、パケットデータが到着すると“パケット有無”の欄に  “有り”を表す“１”を書き込み、また、“先頭パケットバイト数”の欄に、到着パケットデータのバイト数を書き込む。
【００２６】
キュー制御部１−２の読み出し制御としては、一定時間間隔（重み付けラウンドロビンによって与える各キューへの１回の送信権によって送出可能なバイト数の送出時間）毎に、重み付け読み出しテーブル１３−１をアドレス順に読み出し、読み出したバーチャルＬＡＮ識別情報（ＶＩＤ）をセレクタ１−５に与え、セレクタ１−５は、該バーチャルＬＡＮ識別情報（ＶＩＤ）のキューからパケットデータを読み出し、出力ポートへデータを送出する。
【００２７】
このとき、読み出すキューに１個のパケットデータしか存在しなかった場合、パケット情報管理テーブル１−３の“パケット有無”の欄に“０”を書き込む。また、２個以上のパケットデータが存在した場合には、１個のパケットデータを読み出し後に、次に先頭となるパケットデータのバイト数を、パケット情報管理テーブル１−３の“先頭パケットバイト数”の欄に書き込み、パケット情報管理テーブル１−３を更新する。
【００２８】
ここで、重み付け読み出しテーブル１３−１に従って、ＶＩＤ＝ｎのキューを読み出す場合について説明する。キュー制御部１−２は、パケット情報管理テーブル１−３におけるＶＩＤ＝ｎの欄のキュー管理情報を読み出し、その“パケット有無”の欄が“１”であることから、パケットデータが存在することを認識し、Ｘｎバイトのパケットデータを読み出す。このとき、各キューへ与えられる１回の送信権の読み出し可能バイト数をＡバイトとし、Ａ−Ｘｎ＝Ｚであったとする。
【００２９】
また、ＶＩＤ＝ｎのキューから先頭のパケットデータを読み出した後、
（１）このキューの次のパケットデータのデータ長がＺバイトを超える場合、
又は、
（２）次のパケットデータがこのキューに存在しない場合（“パケット有無”＝“０”となった場合）に、
パケット有無検索部１−４は、パケット情報管理テーブル１−３から、パケットデータが存在する（即ち、“パケット有無”＝“１”の）キューのバーチャルＬＡＮ識別情報（ＶＩＤ）を検索する。
【００３０】
そして、ＶＩＤ＝ｍ（ｍ≠ｎ）の“パケット有無”の欄が“１”で、かつ、その先頭パケットバイト数ＸｍがＺバイト以下（Ｘｍ≦Ｚ）であることを検出した場合に、このバーチャルＬＡＮ識別情報（ＶＩＤ）＝ｍのキューからパケットデータを読み出す。
【００３１】
その結果、図２に示すように、１回の送信権で読み出し可能なバイト数Ａの送信期間内に、バーチャルＬＡＮ識別情報（ＶＩＤ）＝ｎ及びバーチャルＬＡＮ識別情報（ＶＩＤ）＝ｍの各パケットデータが出力ポートへ送出されるため、従来のパケット間ギャップ（即ち、未使用帯域）Ｚを、Ｚ−Ｘｍまでに減少させることができる。
【００３２】
更に、Ｚ−Ｘｍ＝Ｚ２  とし、再度、パケット有無検索部１−４により、Ｚ２  バイト以下のパケットデータが存在するかどうかを検索し、存在する場合は同様の処理を繰り返すことにより、更に一層、未使用帯域を減少させ、パケットデータを効率的に送出することができる。
【００３３】
このように、本発明の第１の実施形態は、重み付けラウンドロビン（ＷＲＲ）読み出し制御により、或るキューのパケットデータ読み出し時に、読み出し可能バイト数Ａで与えられたバイト数まで、該キューのパケットデータを読み出し、該キューに溜まっていたパケットデータを全て読み出し終えても、まだ読み出し可能バイト数が残っている場合に、他のキューを検索し、残余バイト数以下のパケットデータが溜まっているキューが有る場合、そのパケットデータを読み出して送出することにより、帯域の有効利用が可能になる。
【００３４】
なお、本発明の第１の実施形態は、１つのキューに与えられた送信権の残余の帯域を有効利用するもので、他のキューからパケットデータを読み出す際に、その読み出すパケットデータが残余のバイト数を超過する場合には、他のキューからの読み出しを行わないため、元々のキューに与えられた送信権の帯域を超過して送信することはなく、また、重み付けラウンドロビン（ＷＲＲ）による読み出しにおいて、他のキューの読み出し帯域に影響を与えることなく、帯域の有効利用を図ることができる。
【００３５】
次に本発明の第２の実施形態を図３を参照して説明する。この第２の実施形態は、前述の第１の実施形態において、残余の帯域を譲り受ける他のコネクションを、ラウンドロビン（ＲＲ）方式によって選定するようにしたものである。図３に示すように、第２の実施形態のパケット有無検索部１−４は、内部にテーブル検索用カウンタ２−１を備える。
【００３６】
該テーブル検索用カウンタ２−１は、キュー単位のパケット情報管理テーブル１−３の、最小アドレスから最大アドレス（即ち、エントリーされているバーチャルＬＡＮ識別情報（ＶＩＤ）の最小のアドレスから最大のアドレス）までのカウント値を順番に巡回生成するカウンタである。
【００３７】
今、ＶＩＤ＝ｎのキューの読み出しで残余帯域が発生した場合、パケット有無検索部１−４は、そのときのテーブル検索用カウンタ２−１のカウント値が示すアドレスから順次カウントアップしがなら、キュー単位のパケット情報管理テーブル１−３の検索を開始する。
【００３８】
そして、最初に検出したパケット有りのＶＩＤ番号の先頭パケットバイト数を読み出し、その先頭パケットバイト数が残余バイト数以下であるか判定し、残余バイト数以下であれば、そのＶＩＤ番号のキューから先頭パケットデータを読み出し、テーブル検索用カウンタ２−１のカウント値を１カウントアップしてカウント動作を停止させる。
【００３９】
次の読み出し機会に、重み付け読み出しテーブル１３−１に従って、重み付けラウンドロビン（ＷＲＲ）により、次のキューのパケットデータの読み出しが開始されたとき、そこで残余帯域が発生すると、テーブル検索用カウンタ２−１は、前回停止したカウンタ値のアドレスから、パケット情報管理テーブル１−３の検索を開始する。この動作によって、残余帯域が割り振られるキューは順番に巡回することになるので、残余帯域を公平に割り振ることが可能となる。
【００４０】
次に本発明の第３の実施形態について説明する。第３の実施形態の機能ブロックは、図１に示した機能ブロックと同様であるので図示を省略する。第３の実施形態におけるキュー制御部１−２の処理のフローを図４に示す。図４に示すように、重み付け読み出しテーブル１３−１に従って、ＶＩＤ＝ｎのキューの読み出し順番になると（ステップ４−１）、キュー制御部１−２は、パケット情報管理テーブル１−３からＶＩＤ＝ｎのキュー管理情報を読み出す（ステップ４−２）。
【００４１】
そして、ＶＩＤ＝ｎのキューにパケットデータが存在しない場合、このＶＩＤ＝ｎのキューのパケットデータ読み出し処理を終了する（ステップ４−８）。ＶＩＤ＝ｎのキューにパケットデータが存在する場合、その先頭パケットバイト数（＝Ｘｎバイト）が、今回の送信権で送出可能なバイト数（＝Ａバイト）未満かどうかを判定し（ステップ４−４）、送出可能なバイト数（＝Ａバイト）未満の場合には、その先頭パケットデータを読み出す（ステップ４−５）。
【００４２】
パケット情報管理テーブル１−３のＶＩＤ＝ｎのエントリーの先頭パケットバイト数、及び“パケット有無”の情報は、キューの書き込み及び読み出し動作に応じて更新し、Ｘｎバイトのパケットデータを読み出した後は、元々の送信可能なＡバイトからＸｎバイトを差し引いた残余分（Ａ−Ｘｎ）を新規の送出可能バイト数Ａとして更新する（ステップ４−６）。
【００４３】
このように、ＶＩＤ＝ｎのキューから先頭パケットデータを読み出した後、再度、パケット情報管理テーブル１−３からＶＩＤ＝ｎのキュー管理情報を読み出すステップ４−２から同様の処理を繰り返す。そして、このＶＩＤ＝ｎのキューに後続のパケットデータが存在し、かつ、その先頭パケットデータのバイト数（Ｘｎ）が、送出可能バイト数Ａ以上となった場合に、その先頭パケットデータ（データ長Ｘｎ）を読み出し、ＶＩＤ＝ｎのキュー単位のパケット情報管理テーブルを更新した後（ステップ４−７）、ＶＩＤ＝ｎのキューのパケットデータ読み出し処理を終了する（ステップ４−８）。
【００４４】
このとき、Ｘｎ＝Ａ（更新後のＡ）であれば、ＶＩＤ＝ｎのキューから読み出されるパケットデータの合計バイト数は、１回の送出権利として与えられる送出可能バイト数に一致するが、Ｘｎ＞Ａの場合には、ＶＩＤ＝ｎのキューから読み出されたパケットデータの合計バイト数は、１回の送出権利の送出可能バイト数を超えることになる。その場合の出力ポートからの読み出し状態を図５に示す。
【００４５】
図５に示すように、本発明の第３の実施形態では、ＶＩＤ＝ｎのキューから、１回の送出権利として与えられる送出可能バイト数Ａを越えるまで、パケットデータを読み出して出力ポートに送出する。図示の例では、Ｘｎ１バイトのパケットデータと、Ｘｎ２バイトのパケットデータと、Ｘｎ３バイトのパケットデータとを送出する。そのため、Ｘｎ１＋Ｘｎ２＋Ｘｎ３−Ａ＝Ｌｎのバイト数が超過バイトとして送出される。しかし、本発明の第３の実施形態では、図１５に示したような未使用帯域の発生を防ぎ、帯域の有効利用が可能となる。
【００４６】
次に本発明の第４の実施形態について説明する。本発明の第４の実施形態は、前述の第３の実施形態において発生した超過バイトのバイト数Ｌｎを記憶しておき、次回に当該キューの読み出しの順番が回って来たときに、元々の送信権に与えられた送出可能バイト数Ａから、前回の送出時に記憶しておいた超過バイト数Ｌｎを差し引き、その差し引いたバイト数を今回の送出可能バイト数としてパケットデータを読み出すようにしたもので、瞬間的には重み付けラウンドロビン（ＷＲＲ）によって与えられた帯域を超えるが、平均的には重み付けラウンドロビン（ＷＲＲ）によって与えられた帯域となり、帯域を有効利用しながら、公平性を保つことができる。
【００４７】
第４の実施形態の構成例を図６に示す。同図に示すように、キュー単位のパケット情報管理テーブル６−１に超過バイト数を記憶する領域を備える。この超過バイトの領域には、実際に読み出したパケットデータの合計バイト数が、１回の送出権の送出可能バイト数を超過したバイト数Ｌｎを書き込む。
【００４８】
そして、重み付け読み出しテーブル１３−１に従って、このキューの次回の読み出しの順番が回って来たときに、元々の１回の送出権に与えられた送出可能バイト数Ａから、この超過バイト数Ｌｎを差し引いたバイト数を、新規の１回の送出権の送出可能バイト数として、当該キューのパケットデータの読み出し条件に使用する。
【００４９】
この処理により、第３の実施形態において超過バイトを許容してパケットデータの読み出しを行っても、重み付けラウンドロビン（ＷＲＲ）によるキューの巡回読み出しを行った場合に、連続して超過バイト数を累算することなく、各回毎の超過バイト数Ｌｎを１回の送出権の送出可能バイト数Ａから差し引いたバイト数を、新規の１回の送出権の送出可能バイト数とすることにより、平均的に元々の１回の送出権の送出可能バイト数のパケットデータが読み出されることになり、各キューからのパケットデータの読み出しを公平に行うことが可能となる。
【００５０】
次に、本発明の第５の実施形態について説明する。本発明の第５の実施形態は、前述の第１又は第２の実施形態と第４の実施形態とを組み合わせたパケットデータの読み出しを行い、かつ、第４の実施形態の超過バイト数Ｌｎをリセットする機能を備えたものである。
【００５１】
第５の実施形態のキュー制御部の処理フローを図７に示す。同図に示すように、重み付け読み出しテーブル１３−１からＶＩＤ＝ｎを読み出し（ステップ７−１）、ＶＩＤ＝ｎのキューの読み出し順番になると、キュー制御部１−２は、パケット情報管理テーブル６−１からＶＩＤ＝ｎのキュー管理情報を読み出す（ステップ７−２）。
【００５２】
そして、ＶＩＤ＝ｎのキューにパケットデータが有るか否かを判定し（ステップ７−３）、パケットデータが無ければ、第１の実施形態と同様に、他コネクション（キュー）のパケットデータを読み出し（ステップ７−４）、パケット情報管理テーブル６−１に記憶されているＶＩＤ＝ｎの超過バイト数Ｌｎを“０”にリセットし（ステップ７−５）、ＶＩＤ＝ｎのキューのパケットデータの読み出し処理を終了する（ステップ７−１１）。
【００５３】
前述の判定７−３において、ＶＩＤ＝ｎのキューにパケットデータが有る場合には、ＶＩＤ＝ｎのキューの先頭のパケットデータのバイト数Ｘｎが、１回の送信権で読み出し可能なバイト数Ａ未満であるか否かを判定する（ステップ７−６）。なお、１回の送信権で読み出し可能なバイト数Ａは、第４の実施形態で説明したように、元々の１回の送信権で送出可能なバイト数から、前回の超過バイト数Ｌｎを差し引いたものを、今回の読み出し可能なバイト数Ａとして更新する。
【００５４】
ＶＩＤ＝ｎのキューの先頭のパケットデータのバイト数Ｘｎが、該読み出し可能なバイト数Ａ未満であれば、ＶＩＤ＝ｎのキューの先頭パケットデータを読み出し（ステップ７−７）、その読み出したバイト数Ｘｎを、読み出し可能なバイト数Ａから減算して、次回の読み出し可能なバイト数Ａを更新し（ステップ７−８）、ステップ７−２に戻って同様の処理を繰り返す。
【００５５】
そして、ＶＩＤ＝ｎのキューの先頭のパケットデータのバイト数Ｘｎが、読み出し可能なバイト数Ａに等しいか又はそれを越える場合には、パケット情報管理テーブル６−１に記憶するＶＩＤ＝ｎの超過バイト数ＬｎとしてＸｎ−Ａを書き込み（ステップ７−９）、その先頭パケットデータを読み出し、ＶＩＤ＝ｎのパケット情報管理テーブルを更新し（ステップ７−１０）、ＶＩＤ＝ｎのキューのパケットデータの読み出し処理を終了する（ステップ７−１１）。
【００５６】
次に、本発明の第６の実施形態について説明する。本発明の第６の実施形態は、複数のコネクション（キュー）をグループ化し、そのグループに割り当てた帯域に対して、第１の実施形態等と同様に、或るコネクション（キュー）の１回の送信権の残余バイトを、同一グループ内の他のコネクション（キュー）のパケットデータの読み出しに割り当て、同一グループ内の他のコネクション（キュー）のパケットデータの読み出しバイト数が、その残余バイト数に等しくなるか又はその残余バイト数を超過するかのいずれかの条件を満たすまで、同一グループ内の他のコネクション（キュー）のパケットデータを送出するようにしたものである。
【００５７】
本発明の第６の実施形態のキュー制御部の処理フローは、図７の「他のコネクションのデータ読み出し（ステップ７−４）」の内部処理になり、そのフロー図を図８に示す。或るグループに属する或るＶＩＤ＝ｎのキューに送信権が与えられたときに、該ＶＩＤ＝ｎのキューのパケットデータを全て送出し終わっても、まだ１回の送信権の送出可能バイト数に残余バイトが存在する場合、該残余バイトによりパケットデータを読み出す同一グループ内の他のキューを、第２の実施形態のテーブル検索用カウンタ２−１などによって決定する（ステップ８−１）。
【００５８】
上記ステップ８−１で決定したキュー（ＶＩＤ＝ｍ）のキュー管理情報を、パケット情報管理テーブル１−３から読み出し（ステップ８−２）、該ＶＩＤ＝ｍのキューにパケットデータが有るか否かを判定する（ステップ８−３）。該キューにパケットデータが無ければ、パケットデータの読み出し処理を終了する（ステップ８−８）。
【００５９】
ＶＩＤ＝ｍのキューにパケットデータが有る場合、その先頭パケットデータのバイト数Ｘｍが、今回の残余バイト数Ａｎ未満であるかを判定し（ステップ８−４）、残余バイト数Ａ未満の場合には、その先頭パケットデータを読み出す（ステップ８−５）。
【００６０】
パケット情報管理テーブル１−３の■ＩＤ＝ｍのエントリーの先頭パケットバイト数及びパケット有無の情報は、Ｘｍバイトのパケットデータを読み出したことにより、元々の残余バイト数Ａから、実際に送出したＸｍバイトを引き算した結果を新規の残余バイト数Ａｎとする（ステップ８−６）。
【００６１】
先頭パケットデータを読み出した後、再度、パケット情報管理テーブル１−３からＶＩＤ＝ｍのパケット情報を読み出すステップ８−２に戻り、同様の処理を繰り返す。そして、該ＶＩＤ＝ｍのキューにパケットデータが存在し、かつ、その先頭パケットのバイト数Ｘｍが、残余バイト数Ａｎと等しいか又はそれを越える場合には、その先頭パケットデータを読み出した後に（ステップ８−７）、該ＶＩＤ＝ｍのキューのパケットデータ読み出し処理を終了する（ステップ８−８）。
【００６２】
このとき、Ｘｍ＝Ａｎ（更新後のＡｎ）であれば、送出権を与えられたＶＩＤ＝ｎのキューのその回に読み出されるパケットデータの合計バイト数（ＶＩＤ＝ｎとＶＩＤ＝ｍの合計）は、元々の１回の送信権として与えられるバイト数Ａに一致するが、Ｘｍ＞Ａｎの場合には、ＶＩＤ＝ｎのキューのその回に読み出されるパケットデータの合計バイト数は、元々の１回の送信権として与えられるバイト数Ａを超えることになる。その場合の出力ポートからの読み出し状態を図９に示す。
【００６３】
図９に示すように、本発明の第６の実施形態では、同一グループ内のＶＩＤ＝ｎのキューとＶＩＤ＝ｍとから、１回の送出権利として与えられる送出可能バイト数Ａを越えるまで、パケットデータを読み出して出力ポートに送出する。図示の例では、ＶＩＤ＝ｎのキューからＸｎバイトのパケットデータと、ＶＩＤ＝ｍのキューからＸｍ１バイト及びＸｍ２バイトのパケットデータとを送出する。そのため、Ｘｎ＋Ｘｍ１＋Ｘｍ２−Ａのバイト数が超過バイトとして送出される。しかし、図１５に示したような未使用帯域の発生を防ぐことができ、効率的にパケットデータを送出することができる。
【００６４】
次に、本発明の第７の実施形態について説明する。図１０に本発明の第７の実施形態のキュー制御部の処理フローを示す。同図に示すように、第６の実施形態と同様に、残余バイトによりパケットデータを読み出す同一グループ内の他のキューを決定する（ステップ１０−１）。
【００６５】
決定したキュー（ＶＩＤ＝ｍ）のグループ単位で記憶している、残余バイトで読み出して発生した超過バイト数ＬＸを読み出す（ステップ１０−２）。そして、今回の読み出しで残っている残余バイト数Ａｎとグループ単位の超過バイト数ＬＸとから、（Ａｎ−ＬＸ）バイトを計算し（ステップ１０−３）、その結果がゼロ以下であった場合は、即ち、残余バイト数Ａをグループ単位の超過バイト数ＬＸが越えている場合、超過バイト数ＬＸから残余バイト数Ａｎを差し引いた値を、新規のグループ単位の超過バイト数ＬＸバイトとして記憶し（ステップ１０−４）、このグループのキューからパケットデータを読み出すことなく、読み出し処理を終了する（ステップ１０−１３）。
【００６６】
（Ａｎ−ＬＸ）の計算結果が正であった場合は、（Ａｎ−ＬＸ）の計算結果を新規の残余バイト数Ａｎとして設定し（ステップ１０−５）、その後は、第６の実施形態と同様の処理を行う（ステップ１０−６〜ステップ１０−１０）。そして、ＶＩＤ＝ｍのキューの先頭パケットデータのバイト数Ｘｍが、残余バイト数Ａｎに等しいか又はそれを超えた場合に、そのデータ長Ｘｍから残余バイト数Ａｎを差し引いた値を、そのグループの新規の超過バイト数ＬＸとして記憶し（ステップ１０−１１）、そのパケットデータまでを読み出し（ステップ１０−１２）、ＶＩＤ＝ｍのキューのパケットデータ読み出し処理を終了する（ステップ１０−１３）。
【００６７】
次に、本発明の第８の実施形態について説明する。この第８の実施形態は、前述の第７の実施形態に、グループ単位の超過バイト数をリセットする機能を付加したものである。第８の実施形態の処理フローを図１１に示す。第８の実施形態の処理フローにおいて、第７の実施形態と同様の処理ステップには同一の符号を付し、重複した説明は省略する。
【００６８】
第８の実施形態の処理フローで新たに付加したステップは、キュー単位のパケット情報テーブル１−３からＶＩＤ＝ｍのキュー管理情報を読み出した後の、ステップ１０−７によるパケット有りか否か判定において、パケット無しと判定された場合に、グループ単位の超過バイト数ＬＸをゼロにリセットし（ステップ１１−１）、ＶＩＤ＝ｍのキューのパケットデータ読み出し処理を終了する（ステップ１０−１３）ようにしたものである。
【００６９】
（付記１）  複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、前記重み付けラウンドロビンにより送信権を与えられたキューから、１回の送信権で送出可能なバイト数未満のパケットデータを送出した場合に、１回の送信権で送出可能なバイト数から実際に送出したパケットデータのバイト数を差し引いた残余のバイトを使用して、他のキューのパケットデータを読み出し送出する手段と、前記残余のバイトを使用してパケットデータを読み出す他のキューを、所定の順番で順次選択する手段と、を備えたことを特徴とする可変長パケットの帯域制御装置。
（付記２）  前記残余のバイトを使用してパケットデータを読み出す他のキューを、ラウンドロビンによって公平に選択する手段を備えたことを特徴とする付記１に記載の可変長パケットの帯域制御装置。
（付記３）  複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、前記重み付けラウンドロビンにより送信権を与えられたキューから、１回の送信権で送出可能なバイト数に等しくなるか又はそのバイト数を超過するかの何れかの条件を満たすまで、当該キューの後続のパケットデータを読み出し送出する手段を備えたことを特徴とする可変長パケットの帯域制御装置。
（付記４）  前記１回の送信権で送出可能なバイト数を超過するまで、パケットデータを読み出し送出した場合に、該超過して読み出し送出した超過バイト数を各キュー対応に保持する手段と、前記各キュー対応に保持した超過バイト数を、元々の１回の送信権で送出可能なバイト数から差し引いたバイト数を、次回に与える各キューへの送信権による送出可能バイト数として設定する手段と、１回の送信権で送出可能なバイト数を超過することなく、全パケットデータを読み出し終えたキューに対して、前記超過バイト数の値をゼロにリセットする手段と、を備えたことを特徴とする付記３に記載の可変長パケットの帯域制御装置。
（付記５）  グループ化された複数のキューに格納された可変長の各パケットデータを、重み付けラウンドロビンにより各キューに送信権を与えて、各キューから順次読み出し、送出する可変長パケットの帯域制御装置において、送信権を与えられたキューからパケットデータを送出し、該キューの１回の送信権で送出可能なバイト数に残余がある場合に、該送信権を与えられたキューと同一グループ内の他のキューから、１回の送信権で送出可能なバイト数に等しくなるか又はそのバイト数を超過するかの何れかの条件を満たすまで、当該キューの同一グループ内の他のキューのパケットデータを読み出し送出する手段を備えたことを特徴とする可変長パケットの帯域制御装置。
（付記６）  前記同一グループの他のキューから、１回の送信権で送出可能なバイト数を超過するまでパケットデータを読み出し送出した場合に、該超過して読み出した超過バイト数を各グループ単位に保持する手段と、送信権を与えられたキューからパケットデータを送出し、該キューの１回の送信権で送出可能なバイト数に残余がある場合に、該残余のバイト数から、前記各グループ単位に保持した超過バイト数を差し引いた値が正である場合、その差し引いた値を、同一グループ内の他のキューの送出可能バイト数として設定する手段と、前記１回の送信権で送出可能なバイト数を超過することなく、同一グループ内のキューの全パケットデータを読み出し終えたグループに対して、該グループ単位の超過バイト数の値をゼロにリセットする手段と、前記残余のバイト数から前記各グループ単位に保持した超過バイト数を差し引いた値がゼロ以下である場合、該グループ単位に保持した超過バイト数から、該残余のバイト数を差し引いた値を、次回のグループ単位の超過バイト数として保持する手段と、を備えたことを特徴とする付記５に記載の可変長パケットの帯域制御装置。
【００７０】
【発明の効果】
以上説明したように、本発明によれば、重み付けラウンドロビン（ＷＲＲ）による読み出し制御において、或るキューの読み出し時に、該キューからパケットデータを読み出しても、まだ読み出し可能バイト数が残っている場合に、他のキューからパケットデータを読み出すことにより、未使用帯域を減少させ、帯域の有効利用を図ることができる。
【００７１】
また、送信権を与えられたキュー以外の他のキューからパケットデータを読み出す場合に、該送信権を与えられたキューの１回の読み出し可能バイト数を超過しない範囲で読み出すことにより、重み付けラウンドロビン（ＷＲＲ）による読み出しの公平性を保つことが可能となる。また、残余帯域の割り当てにおいて、該残余帯域により読み出すキューをラウンドロビンにより選択することにより、各キューの残余帯域の利用の公平化を図ることが可能となる。
【００７２】
また、重み付けラウンドロビン（ＷＲＲ）による読み出し時に、後続の１パケットデータを読み出すと、与えられた送出権による送出可能バイト数を超えてしまう場合であっても、そのパケットデータまで読み出して送出することにより、空き帯域の発生を防ぎ、帯域の有効利用が可能になる。
【００７３】
また、与えられた送出権による送出可能バイト数を超過してパケットデータを送出した場合、超過バイト数分だけ公平性が崩れることになるが、次回のキューの読み出し時に、前回の超過バイト数を元々の１回の送出権による送出可能バイト数から差し引いた値を、新規の１回の送出権による送出可能バイト数とすることにより、瞬間的には重み付けラウンドロビン（ＷＲＲ）によって与えられた帯域を超えても、平均的には、重み付けラウンドロビン（ＷＲＲ）によって与えられた帯域を超えないため、帯域を有効利用しながら、公平性を保つことが可能となる。
【００７４】
また、複数のキューをグループ化し、送信権を与えられたキューに送出可能な残余帯域が有る場合、該残余帯域を使用して同一グループ内の他のキューのパケットデータを読み出し、各グループに割り当てた帯域を超えてしまう場合であっても、そのパケットデータまで読み出すことにより、空き帯域の発生を防ぎ、帯域の有効利用が可能になる。
【００７５】
また、各グループに割り当てた帯域を超過してパケットデータを送出した場合、超過バイト数分だけグループ間の公平性が崩れることになるが、次回のキューの読み出し時に残余帯域がある場合、前回の超過バイト数を該残余帯域から差し引いた値を、同一グループの他のキューへの割り当て帯域とすることにより、平均的にはグループ間の公平性を保ちながら、グループ内の各キューでの帯域の有効利用を図ることが可能となる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態の構成を示す図である。
【図２】本発明の第１の実施形態のパケット出力の例を示す図である。
【図３】本発明の第２の実施形態の構成を示す図である。
【図４】本発明の第３の実施形態の処理フローを示す図である。
【図５】本発明の第３の実施形態のパケット出力の例を示す図である。
【図６】本発明の第４の実施形態の構成を示す図である。
【図７】本発明の第５の実施形態の処理フローを示す図である。
【図８】本発明の第６の実施形態の処理フローを示す図である。
【図９】本発明の第６の実施形態のパケット出力の例を示す図である。
【図１０】本発明の第７の実施形態の処理フローを示す図である。
【図１１】本発明の第８の実施形態の処理フローを示す図である。
【図１２】イーサネット技術をベースにした通信サービスネットワークの全体構成を示す図である。
【図１３】従来の重み付けラウンドロビン（ＷＲＲ）による読み出し制御部のモデルを示す図である。
【図１４】従来の重み付けラウンドロビン（ＷＲＲ）による読み出し制御の例を示す図である。
【図１５】従来の重み付けラウンドロビン（ＷＲＲ）による未使用帯域の発生例を示す図である。
【符号の説明】
１−１  キュー振り分け部
１−２  キュー制御部
１−３  キュー単位のパケット情報管理テーブル
１−４  パケット有無検索部
１−５  セレクタ
１３−１  重み付け読み出しテーブル
【図１】
2004153482.tif 000003
【図２】
2004153482.tif 000004
【図３】
2004153482.tif 000005
【図４】
2004153482.tif 000006
【図５】
2004153482.tif 000007
【図６】
2004153482.tif 000008
【図７】
2004153482.tif 000009
【図８】
2004153482.tif 000010
【図９】
2004153482.tif 000011
【図１０】
2004153482.tif 000012
【図１１】
2004153482.tif 000013
【図１２】
2004153482.tif 000014
【図１３】
2004153482.tif 000015
【図１４】
2004153482.tif 000016
【図１５】
2004153482.tif 000017