(57)【要約】【課題】多段構成のキューを利用したパケット中継装置において、従来とは異なるパケットの廃棄制御を実現することのできる技術を提供する。【解決手段】多段に構成されたキューを利用してパケットを中継するパケット中継装置は、受信したパケットをキューに格納せずに廃棄するか否かを判定する判定部を備える。判定部は、パケットが属する前段以前のキューの状態を示す前段キュー情報と、パケットが属する後段のキューの状態を示す後段キュー情報とに基づいて、当後段のキューにおいてパケットを廃棄するか否かを判定する。【選択図】図１
2011151601.tif 000002
【特許請求の範囲】
【請求項１】
多段に構成されたキューを利用してパケットを中継するパケット中継装置であって、
受信したパケットを前記キューに格納せずに廃棄するか否かを判定する判定部を備え、
前記判定部は、前記パケットが属する前段以前のキューの状態を示す前段キュー情報と、前記パケットが属する後段のキューの状態を示す後段キュー情報とに基づいて、当該後段のキューにおいて前記パケットを廃棄するか否かを判定する、パケット中継装置。
【請求項２】
請求項１に記載のパケット中継装置であって、
前記判定部は、前記前段キュー情報に基づいてパケットの廃棄確率と前記後段キュー情報との関係を設定し、当該後段キュー情報に対応して求められる廃棄確率に基づいてパケットを廃棄するか否かを判定する、パケット中継装置。
【請求項３】
請求項２に記載のパケット中継装置であって、
前記廃棄確率を求めるために用いられる計算式に含まれる定数は、ユーザからの指示によって設定される、パケット中継装置。
【請求項４】
請求項２または請求項３に記載のパケット中継装置であって、
前記廃棄確率を求めるために用いられる計算式は、ユーザからの指示によって設定される、パケット中継装置。
【請求項５】
請求項１に記載のパケット中継装置であって、
前記判定部は、前記前段キュー情報に基づいて前記受信したパケットをクラス分けし、前記クラス毎に設定された閾値と前記後段キュー情報とに基づいて、当該パケットを廃棄するか否かを判定する、パケット中継装置。
【請求項６】
請求項１ないし請求項５のいずれか一項に記載のパケット中継装置であって、
前記前段キュー情報は、前段以前のキューのキュー長を含む、パケット中継装置。
【請求項７】
請求項１ないし請求項６のいずれか一項に記載のパケット中継装置であって、
前記前段キュー情報は、前段以前のキューの通信量を含む、パケット中継装置。
【請求項８】
多段に構成されたキューを利用してパケットを中継する方法であって、
受信したパケットを前記キューに格納せずに廃棄するか否かを判定する廃棄判定工程を備え、
前記廃棄判定工程は、前記パケットが属する前段以前のキューの状態を示す前段キュー情報と、前記パケットが属する後段のキューの状態を示す後段キュー情報とに基づいて、当該後段のキューにおいて前記パケットを廃棄するか否かを判定する工程を含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットを中継するパケット中継装置及びパケットを中継する方法に関するものである。
【背景技術】
【０００２】
通信の中継を行う装置に対して許容能力を大きく超える通信や要求があると、通信が滞ることがある。これは一般に通信の輻輳と呼ばれ、その発生はインターネット通信においても例外ではない。
【０００３】
インターネットの通信においては、通常、パケットと呼ばれる単位で送受信が行われ、データのやり取りが行なわれる。このパケットの中継を行うパケット中継装置としては、例えば、スイッチやルータといったものが知られている。パケット中継装置は、多くの場合、パケットを一時格納するためのキューを備えている。キューは、パケット中継装置の通信において、複数のフロー間での送信パケットの到着順序の重なりによって生じるバースト的なトラフィックによってパケットの廃棄が発生してしまうことを抑制する役割や、QoS(Quality of Service)のためにパケットの優先制御や通信の帯域制御を実施する役割などを担っている。
【０００４】
パケット中継装置に対してその許容範囲を超えるトラフィックが流れようとした場合、輻輳が発生する可能性がある。インターネットを構成するネットワークは、基本的にベストエフォート型ネットワーク通信である。インターネットで使用される代表的なプロトコルであるTCP/IP(Transmission Control Protocol/Internet Protocol)では、品質が保証されていないネットワーク上を伝播させても通信の完全性を保つために、パケットの送受信を行う端末間でパケットを再送する仕組みが実装されている。このことから、インターネット上で使用されるパケット中継装置は、パケットを廃棄する制御が許容されており、ローコストで高速な通信を実現することが可能となっている。一方で、この廃棄制御の重要性は極めて高くなっている。
【０００５】
パケットの廃棄制御の代表例としては、例えば、Tail DropやRED(Random Early Detection)が挙げられる。Tail Dropは、キューごとにパケットを格納可能な最大閾値を持つ方式で、キュー長が最大閾値を超えた場合に、あふれたパケットを廃棄する方式である。この制御方式は、実装が容易である一方、一斉廃棄によってパケットの再送がスロースタートになり、TCP/IPによる通信の下では、得られるべきスループットが得られないといった問題がある。
【０００６】
もう1つの代表例であるREDは、キューごとに最小閾値、最大閾値及び最大パケット廃棄率をパラメータとして持つ方式であり、キュー長が最小閾値を超えると、キュー長に応じたパケット廃棄確率を用いてパケットを廃棄する。そして、キュー長が最大閾値に達するまではキュー長に応じた確率で徐々にパケットが廃棄されるが、キュー長が最大閾値を超えるとキューからパケットがあふれるため、あふれた全てのパケットが廃棄される。REDは実装がTail Dropより複雑な一方、キュー長に応じた割合でパケットが徐々に廃棄されるため、TCP/IPによる通信の下において、一斉に再送処理が発生する現象を抑制することができ、本来の回線性能が発揮されやすくなる。
【０００７】
上述した２つの廃棄制御技術には、WTD(Weighted Tail Drop)と呼ばれる改良技術と、WRED(Weighted Random Early Detection)と呼ばれる改良技術が提案されている。この２つの改良技術は、どちらもパケットが属するアプリケーション種別ごとに異なるポリシーによって制御する方式であり、それぞれのアプリケーションごとに異なる廃棄閾値を持つことにより、廃棄優先制御を実現することができる。WTDの場合では、キュー長の最大閾値をパケットのアプリケーション種別ごとに変更することができる。WREDの場合では、最小閾値、最大閾値及び最大パケット廃棄率を、パケットが属するアプリケーション種別ごとに変更することができる。いずれの制御方式もパケットのアプリケーション種別ごとに廃棄優先度制御を可能としているため高機能であるが、アプリケーション種別ごとの情報管理が必要となる。
【０００８】
ところで、パケット中継装置の中には、キューが多段的な構造になっているものがある。そして、多段キューの構成を採用するパケット中継装置では、統計多重効果の考え方に基づいて各キューの最大長が設計されることがある。この場合における統計多重効果とは、全てのキューが同時に設定した最大値までキュー長を使うことはないと考え、全てのキューの最大値の合計よりも少ないキュー長で全てのキューをまかなうというものである。統計多重効果を適用しない場合には全てのキューの最大値の総和分のメモリが必要になるのに対し、この考えに基づいて設計した場合、メモリ量が少なく済むため省資源になり、コスト削減や消費電力の低減が可能となる。
【０００９】
なお、統計多重効果の考えに基づいて設計されたパケット中継装置の多段キューでは、前段の全てのキューの最大長の総和よりも全体のバッファメモリ量を監視するキューの最大長の方が短くなる。このような内部構成のとき、キューが輻輳する場合には、全体のバッファメモリ量を監視するキューが先に逼迫するケースがある。例えば、全体のメモリに余剰があればパケットがキューに格納（キューイング）されるような単純な仕組みの場合、特定のキューのパケットにより後段のキューが逼迫するに至ることがある。このようになると、他のキューがバッファメモリを使用できず、そのキューの通信が阻害されるといった問題が発生する。これが特定キューによるバッファの占有である。
【００１０】
このような問題を解決するための技術としては、例えば、以下の特許文献１に開示された技術が挙げられる。この技術では、全体のバッファメモリ量を監視するキュー長が一定の割合を超えたとき、状態を遷移させ、全てのキュー長の最大閾値を一定割合に短くする制御を行う。これにより、各キューの閾値が一定割合に短くなる。この時、短くなった閾値よりもキュー長の長いキューに接続している送信元には、輻輳の知らせが送信される。そして、輻輳の知らせを受け取った送信元が通信速度を落とすことにより、当該キューのパケットがバッファメモリから減っていく。この結果、バッファの占有が解消され、他のユーザが通信可能となる。
【００１１】
しかし特許文献１に開示された技術は、今日のようなインターネット通信を前提にした技術ではなく、インターネットにおけるパケット通信に適用した場合には次のような動作になる。各キューの閾値が一定割合に短くなった際、短くなった閾値よりも多くのパケットを格納しているキューは、閾値を超えた状態で届くパケット全ての一斉廃棄を行う。この結果、通信帯域のバッファメモリを占有されることによって通信をすることができなかった他のユーザが通信できるようになる。
【００１２】
しかしその一方で、キュー長が閾値を超えていたキューに接続していたユーザは、全てスロースタートからの一斉再送になる。このため、ネットワーク全体でのスループットが大きく落ちるといった弊害がある。また、特許文献１に開示された技術では、全体のバッファメモリ量を監視するキューの輻輳を検知してからの処理となっているため、その影響が全てのキューに同時に及び、一斉に廃棄が発生してしまう可能性が高かった。そして、優先度の高いユーザや低いユーザに対して柔軟な廃棄制御が実現できないという問題があった。
【００１３】
なおこのような問題は、統計多重効果の考えに基づいて設計されたパケット中継装置に限らず、一般に、多段構成のキューを利用したパケット中継装置全般に共通する問題であった。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開平１０−１７３６６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
本発明は、上述した従来の課題を解決するためになされたものであり、多段構成のキューを利用したパケット中継装置において、従来とは異なるパケットの廃棄制御を実現することのできる技術を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明は、上述の課題の少なくとも一部を解決するために、以下の形態または適用例を取ることが可能である。
【００１７】
[適用例１]
多段に構成されたキューを利用してパケットを中継するパケット中継装置であって、
受信したパケットを前記キューに格納せずに廃棄するか否かを判定する判定部を備え、
前記判定部は、前記パケットが属する前段以前のキューの状態を示す前段キュー情報と、前記パケットが属する後段のキューの状態を示す後段キュー情報とに基づいて、当該後段のキューにおいて前記パケットを廃棄するか否かを判定する、パケット中継装置。
【００１８】
適用例１のパケット中継装置によれば、前段キュー情報と後段キュー情報とに基づいてパケットを廃棄するか否かを判定するので、前段以前のキューの状態を反映した廃棄制御を実現することができる。
【００１９】
[適用例２]
適用例１に記載のパケット中継装置であって、
前記判定部は、前記前段キュー情報に基づいてパケットの廃棄確率と前記後段キュー情報との関係を設定し、当該後段キュー情報に対応して求められる廃棄確率に基づいてパケットを廃棄するか否かを判定する、パケット中継装置。
【００２０】
適用例２のパケット中継装置によれば、前段キュー情報に基づいてパケットの廃棄確率と後段キュー情報との関係を設定するので、前段以前のキューの状態を反映した廃棄制御を実現することができる。
【００２１】
[適用例３]
適用例２に記載のパケット中継装置であって、
前記廃棄確率を求めるために用いられる計算式に含まれる定数は、ユーザからの指示によって設定される、パケット中継装置。
【００２２】
適用例３のパケット中継装置によれば、ユーザによる指示を反映した廃棄制御を実現することができる。
【００２３】
[適用例４]
適用例２または適用例３に記載のパケット中継装置であって、
前記廃棄確率を求めるために用いられる計算式は、ユーザからの指示によって設定される、パケット中継装置。
【００２４】
適用例４のパケット中継装置によれば、ユーザによる指示を反映した廃棄制御を実現することができる。
【００２５】
[適用例５]
適用例１に記載のパケット中継装置であって、
前記判定部は、前記前段キュー情報に基づいて前記受信したパケットをクラス分けし、前記クラス毎に設定された閾値と前記後段キュー情報とに基づいて、当該パケットを廃棄するか否かを判定する、パケット中継装置。
【００２６】
適用例５のパケット中継装置によれば、前段キュー情報に基づいて受信したパケットをクラス分けするので、前段以前のキューの状態を反映した廃棄制御を実現することができる。
【００２７】
[適用例６]
適用例１ないし適用例５のいずれか一項に記載のパケット中継装置であって、
前記前段キュー情報は、前段以前のキューのキュー長を含む、パケット中継装置。
【００２８】
適用例６のパケット中継装置によれば、前段以前のキューのキュー長に応じた廃棄制御を実現することができる。
【００２９】
[適用例７]
適用例１ないし適用例６のいずれか一項に記載のパケット中継装置であって、
前記前段キュー情報は、前段以前のキューの通信量を含む、パケット中継装置。
【００３０】
適用例７のパケット中継装置によれば、前段以前のキューの通信量に応じた廃棄制御を実現することができる。
【００３１】
なお、本発明は、種々の態様で実現することが可能である。例えば、パケットを中継する方法およびパケット中継システム、それらの方法または装置の機能を実現するための集積回路、コンピュータプログラム、そのコンピュータプログラムを記録した記録媒体等の形態で実現することができる。
【図面の簡単な説明】
【００３２】
【図１】本発明の一実施例としてのパケット中継装置１００の構成をキューイングを実行する部位を中心として示す説明図である。
【図２】多段キュー構造についての概念を示す説明図である。
【図３】パケット中継装置１００のキューイング制御処理を示すフローチャートである。
【図４】（Ｎ）段制御用メモリＴ２に格納されている制御情報を示す説明図である。
【図５】（Ｎ＋１）段制御用メモリＴ３に格納されている制御情報を示す説明図である。
【図６】（Ｎ＋１）段目のキューにおける廃棄判定の流れを示すフローチャートである。
【図７】平均キュー長QAVEと廃棄確率DPとの関係式をグラフ形式として示すと共に、（Ｎ＋１）段目のキューにおける廃棄判定で用いられる条件式を示す説明図である。
【図８】比較例のREDによるパケットの廃棄判定をグラフ形式として示す説明図である。
【図９】第２実施例における多段キュー構造についての概念を示す説明図である。
【図１０】第２実施例における（Ｎ＋１）段制御用メモリＴ３に格納された制御情報を示す説明図である。
【図１１】第４実施例における（Ｎ）段目制御用メモリＴ２に格納された制御情報を示す説明図である。
【図１２】キューごとに個別のバッファメモリを備えた態様を示す説明図である。
【発明を実施するための形態】
【００３３】
次に、本発明の実施の形態を実施例に基づいて以下の順序で説明する。
Ａ．第１実施例：
Ｂ．第２実施例：
Ｃ．第３実施例：
Ｄ．第４実施例：
Ｅ．変形例：
【００３４】
Ａ．第１実施例：
Ａ１．装置構成：
図１は、本発明の一実施例としてのパケット中継装置１００の構成を、キューイングを実行する部位を中心として示す説明図である。パケット中継装置１００は、パケット通信用のキューを内部に２段有している。本実施例では、パケット中継装置１００における前段を（Ｎ）段、後段を（Ｎ＋１）段として説明する。
【００３５】
パケット中継装置１００は、各キューの制御情報に基づいてパケットのキューイング制御を行なうキューイング制御部１０１と、制御情報やパケットを格納するメモリ群１０２と、インターフェース部１０４とを備えている。キューイング制御部１０１は、図示しないＣＰＵや、ＲＯＭ、ＲＡＭ等を備えており、ＲＡＭに展開されたプログラムをＣＰＵが読み込んで実行することにより、キューイング制御を行なう。メモリ群１０２は、パケットのデータそのものを格納するためのバッファメモリＴ１と、（Ｎ）段目のキューイング制御を行うための制御情報を格納する（Ｎ）段制御用メモリＴ２と、（Ｎ＋１）段目のキューイング制御を行うための制御情報を格納する（Ｎ＋１）段制御用メモリＴ３とを含んでいる。インターフェース部１０４には、ディスプレイ等の表示装置や、キーボード、マウス等の入力装置が接続可能であり、パケット中継装置１００を管理するユーザ（以下、「管理ユーザ」ともいう）は、インターフェース部１０４を介してキューイング制御部１０１及びメモリ群１０２の各種設定を行なうことができる。
【００３６】
本実施例におけるパケット中継装置１００は、共有バッファ方式の多段キュー構造を採用している。共有バッファ方式とは、統計多重効果に基づき、全てのキューの最大値の総和よりも少ないバッファメモリを、全てのキューで共有する方式である。すなわち、共有バッファ方式では、全てのキューの最大値の総和分のバッファメモリを用意しなくてもよいため、バッファメモリの容量を小さくすることができる。このため、共有バッファ方式によれば、省資源によるコストの削減や消費電力の低減を実現することが可能となる。本実施例では、バッファメモリＴ１が共有バッファとなる。
【００３７】
図２は、多段キュー構造についての概念を示す説明図である。この図２に示した例では、（Ｎ）段目には複数のキューが存在しており、（Ｎ）段目のキューのそれぞれは、送信元1つ1つに対応した個別のキューとして利用される。具体的には、例えば、ユーザ１からの通信は（Ｎ）段目のキュー＃１に入る、といった態様となっている。そして、統計多重効果を利用した共有バッファ方式の場合では、複数の（Ｎ）段目のキューのそれぞれに格納されるパケット数の合計を（Ｎ＋１）段目のキューが管理している。すなわち、共有バッファ方式では、（Ｎ＋１）段目のキューのキュー長QLEN(N+1)は、（Ｎ）段目の複数のキューのキュー長QLEN(N)の合計値となっている。なお、この図２には、（Ｎ）段目のキューの最大閾値MAX_TH(N)と、（Ｎ＋１）段目のキューの最大閾値MAX_TH(N+1)と、（Ｎ＋１）段目のキューの最小閾値MIN_TH(N)とが示されている。これらについては、後述する。
【００３８】
図３は、パケット中継装置１００のキューイング制御処理を示すフローチャートである。ステップＳ１００では、パケット中継装置１００（図１）は、パケットを受信する。ステップＳ２００では、キューイング制御部１０１（図１）は、当該パケットが、（Ｎ）段目の複数のキューのうちどのキューに属するかを判定する。ステップＳ３００では、キューイング制御部１０１は、当該パケットに対するキューイング制御を行うために、メモリ群１０２の内部にある（Ｎ）段制御用メモリＴ２に格納されたデータを読み出し、読み出したデータに基づいて（Ｎ）段目のキューにおける廃棄判定を行う。（Ｎ）段目のキューにおける廃棄判定の詳細については後述する。
【００３９】
キューイング制御部１０１は、（Ｎ）段目のキューにおける廃棄判定において、廃棄と判定した場合（ステップＳ４００：Ｙｅｓ）には、当該パケットを廃棄する（ステップＳ８００）。一方、（Ｎ）段目のキューにおける廃棄判定において、廃棄と判定しなかった場合（ステップＳ４００：Ｎｏ）には、キューイング制御部１０１は、（Ｎ＋１）段目のキューにおける廃棄判定を行なう（ステップＳ５００）。具体的には、キューイング制御部１０１は、（Ｎ）段制御用メモリＴ２に格納されたデータ及び（Ｎ＋１）段制御用メモリＴ３に格納されたデータに基づいて、（Ｎ＋１）段目のキューにおける廃棄判定を行う。（Ｎ＋１）段目のキューにおける廃棄判定の詳細については後述する。
【００４０】
キューイング制御部１０１は、（Ｎ＋１）段目のキューにおける廃棄判定において、廃棄と判定した場合（ステップＳ６００：Ｙｅｓ）には、当該パケットを廃棄する（ステップＳ８００）。一方、（Ｎ＋１）段目のキューにおける廃棄判定において、廃棄と判定しなかった場合（ステップＳ６００：Ｎｏ）には、キューイング制御部１０１は、当該パケットをバッファメモリＴ１に格納（キューイング）する（ステップＳ７００）。
【００４１】
Ａ２．（Ｎ）段目のキューにおける廃棄判定：
図４は、（Ｎ）段制御用メモリＴ２に格納されている制御情報を示す説明図である。（Ｎ）段制御用メモリＴ２は、（Ｎ）段目のキューにおけるパケットの廃棄判定を行うための制御情報として、（Ｎ）段目の複数のキュー毎に設定されたキュー長の閾値である最大閾値MAX_TH(N)と、当該キューに格納されているパケット数であるキュー長QLEN(N)とが格納されている。
【００４２】
キューイング制御部１０１（図１）は、受信したパケットが属するキュー番号に対応したキュー長QLEN(N)が最大閾値MAX_TH(N)未満の場合には、廃棄判定において、当該パケットを廃棄と判定しない。一方、受信したパケットが属するキュー番号に対応したキュー長QLEN(N)が最大閾値MAX_TH(N)と同じ値の場合には、キューイング制御部１０１は、廃棄判定において、当該パケットを廃棄と判定する。廃棄判定の結果、（Ｎ）段目のキューにおいて廃棄されないことが確定すると、キューイング制御部１０１は、後述する（Ｎ＋１）段目のキューにおける廃棄判定を実行する。
【００４３】
具体的には、図４に示した例であれば、キュー番号＃４では、キュー長QLEN(N)が最大閾値MAX_TH(N)と一致しているため、キューイング制御部１０１は、当該キューに受信したパケットを廃棄と判定する。一方、他の（Ｎ）段目のキューでは、キュー長QLEN(N)が最大閾値MAX_TH(N)と一致するまでには余裕があるため、キューイング制御部１０１は、他のキューに受信したパケットを（Ｎ）段目の廃棄判定では廃棄と判定しない。
【００４４】
なお、（Ｎ）段制御用メモリＴ２の更新動作は次のようになる。キューイング制御部１０１に受信されたパケットが（Ｎ）段目のキューにおいて廃棄と判定されず、（Ｎ＋１）段目のキューにおいても廃棄と判定されなかった場合（後述）には、当該パケットはバッファメモリＴ１に格納され、（Ｎ）段制御用メモリＴ２の当該キューのキュー長QLEN(N)が１増加する。そして、後にバッファメモリＴ１からパケットが送信された場合には、（Ｎ）段制御用メモリＴ２の当該キューのキュー長QLEN(N)が１減少する。
【００４５】
Ａ３．（Ｎ＋１）段目のキューにおける廃棄判定：
キューイング制御部１０１は、受信したパケットが属する（Ｎ）段目のキューのキュー長QLEN(N)及び（Ｎ＋１）段制御用メモリＴ３の制御情報を用いて、（Ｎ＋１）段目のキューにおける当該パケットの廃棄判定を行う。具体的には、キューイング制御部１０１は、パケットの属する（Ｎ）段目のキューのキュー長QLEN(N)が長いほど、（Ｎ＋１）段目のキューにおける廃棄判定で、当該パケットが廃棄と判定される確率を大きく設定する。以下、詳細について説明する。
【００４６】
図５は、（Ｎ＋１）段制御用メモリＴ３に格納されている制御情報を示す説明図である。（Ｎ＋１）段制御用メモリＴ３は、廃棄判定を実行するために用いられる制御情報として、格納可能なキュー長の閾値である最大閾値MAX_TH(N+1)と、廃棄を開始するキュー長の閾値である最小閾値MIN_TH(N+1)と、キュー長が最大閾値MAX_TH(N+1)に達したときのパケットの廃棄確率である最大廃棄確率MAX_DPと、（Ｎ）段目の複数のキューに格納されているパケットの合計を示すキュー長QLEN(N+1)と、時系列的に変化するキュー長QLEN(N+1)の平均をとった平均キュー長QAVEとを格納している。この図５に示した例においては、最大閾値MAX_TH(N+1)が１０００、最小閾値MIN_TH(N+1)が５００、最大廃棄確率MAX_DPが５０％、キュー長QLEN(N+1)が７００、平均キュー長QAVEが７００となる。
【００４７】
（Ｎ＋１）段制御用メモリＴ３の更新動作は次のようになる。（Ｎ）段目のキューにおける廃棄判定で廃棄と判定されず、かつ、（Ｎ＋１）段目のキューにおける廃棄判定で廃棄と判定されなかったパケットは、キューイング制御部１０１からメモリ群１０２に送られ、バッファメモリＴ１に書き加えられる。この時、（Ｎ＋１）段制御用メモリＴ２のキュー長QLEN(N+1)が１増加し、平均キュー長QAVEも更新される。パケット送信の際には、パケットはバッファメモリＴ１から順に読み出され、キューイング制御部１０１を通って送信される。この時、（Ｎ＋１）段制御用メモリＴ２のキュー長QLEN(N+1)が１減少し、平均キュー長QAVEも更新される。
【００４８】
図６は、（Ｎ＋１）段目のキューにおける廃棄判定の流れを示すフローチャートである。ステップＳ５１０では、キューイング制御部１０１は、キュー長QLEN(N+1)が更新されると、平均キュー長QAVEを更新する。更新後の新たな平均キュー長QAVEnewは、更新後のキュー長QLEN(N+1)と更新前の平均キュー長QAVEoldとを用いた以下の式（１）によって求められる。
QAVEnew = {QLEN(N+1) * 1/2^S} + {QAVEold * (1-1/2^S)}  …式（１）
ここで、Sは重み係数である。上記式から理解できるように、重み係数Sが大きいほど、更新後の平均キュー長QAVEnewに対するキュー長QLEN(N+1)の影響が小さくなる。すなわち、重み係数Sを大きくすれば、キュー長QLEN(N+1)が短期間のうちに大きく変動したとしても、平均キュー長QAVEの変動を小さくすることができる。
【００４９】
ステップＳ５２０では、キューイング制御部１０１は、（Ｎ）段制御用メモリＴ２から、廃棄判定の対象となっているパケットが属する（Ｎ）段目のキューの制御情報（キュー長QLEN(N)及び最大閾値MAX_TH(N)）を取得する。
【００５０】
ステップＳ５３０では、キューイング制御部１０１は、取得した（Ｎ）段目のキューのキュー長QLEN(N)及び最大閾値MAX_TH(N)を用いて、平均キュー長QAVEと廃棄確率DPとの関係式を求める。すなわち、平均キュー長QAVEと廃棄確率DPとの関係式は、（Ｎ）段目のキュー毎に異なったものとなる。詳細については後述する。ステップＳ５４０では、キューイング制御部１０１は、平均キュー長QAVEに対応した廃棄確率DPに基づいて、（Ｎ＋１）段目のキューにおける廃棄判定を行なう。
【００５１】
キューイング制御部１０１は、平均キュー長QAVEに対応した廃棄確率DPに基づいて廃棄判定を行い、廃棄と判定した場合にはパケットを廃棄し（図３のステップＳ８００）、廃棄と判定しなかった場合にはパケットをバッファメモリＴ１に格納（キューイング）する（図３のステップＳ７００）。
【００５２】
図７（Ａ）は、平均キュー長QAVEと廃棄確率DPとの関係式をグラフ形式として示す説明図である。キューイング制御部１０１は、上述したように、平均キュー長QAVEに対応した廃棄確率DPを求め、求めた廃棄確率DPに基づいて（Ｎ＋１）段目におけるパケットの廃棄判定を行なう。平均キュー長QAVEと廃棄確率DPとの関係は、次のとおりである。
QAVE≧MAX_TH(N+1)のとき
DP=100%
QAVE≦MIN_TH(N+1)-βのとき
DP=0%
MIN_TH(N+1)-β＜QAVE＜MAX_TH(N+1)のとき
DP=(MAX_DP+α)(QAVE-MIN_TH(N+1)+β)/(MAX_TH(N+1)-MIN_TH(N+1)+β)
ここで、αは廃棄確率重み、βは廃棄閾値重みである。
【００５３】
図７（Ａ）に示すように、廃棄確率重みαが正の値であり、かつ、その絶対値が大きくなるほど、平均キュー長QAVEが最大閾値MAX_TH(N+1)と一致した場合における廃棄確率DPが、最大廃棄確率MAX_DPより大きくなる。一方、廃棄確率重みαが負の値であり、かつ、その絶対値が大きくなるほど、平均キュー長QAVEが最大閾値MAX_TH(N+1)と一致した場合における廃棄確率DPが、最大廃棄確率MAX_DPより小さくなる。
【００５４】
また、廃棄閾値重みβが正の値であり、かつ、その絶対値が大きくなるほど、パケットの廃棄が開始される閾値が、最小閾値MIN_TH(N+1)よりも小さくなる。一方、廃棄閾値重みβが負の値であり、かつ、その絶対値が大きくなるほど、パケットの廃棄が開始される閾値が、最小閾値MIN_TH(N+1)よりも大きくなる。すなわち、廃棄確率重みα及び廃棄閾値重みβに応じて、パケットが廃棄と判定される廃棄確率DPと平均キュー長QAVEとの関係が変動する。
【００５５】
廃棄確率重みα及び廃棄閾値重みβは、廃棄判定の対象となっているパケットが属する（Ｎ）段目のキューのキュー長QLEN(N)及び最大閾値MAX_TH(N)をパラメータとした以下の式（２）、式（３）によって求められる。
α = αMAX * {QLEN(N)/MAX_TH(N) * 2-1}  …式（２）
β = βMAX * {QLEN(N)/MAX_TH(N) * 2-1}  …式（３）
ここで、αMAX及びβMAXは、所定の定数である。
【００５６】
廃棄確率DPと平均キュー長QAVEとの関係は、廃棄判定の対象となっているパケットの属する（Ｎ）段目のキューの状態に応じて変更される。具体的には、パケットが属する（Ｎ）段目のキューの最大閾値MAX_TH(N)に占めるキュー長QLEN(N)の割合が大きいほど、廃棄確率重みα及び廃棄閾値重みβが大きくなり、（Ｎ＋１）段目のキューにおける当該パケットの廃棄確率DPが大きくなる。
【００５７】
なお、αMAX及びβMAXの値は、インターフェース部１０４に入力装置を接続し、入力装置からの指示によって設定可能とすることができる。こうすれば、廃棄確率重みα及び廃棄閾値重みβの変動する範囲を、管理ユーザが自由に設定・変更することが可能となる。例えば、管理ユーザは、パケット中継装置１００に接続されたユーザ数や通信量等に合わせて、廃棄確率重みα及び廃棄閾値重みβの変動する範囲を適宜調整することができる。また、αMAX及びβMAXの値は、予め調整された複数の値の中から、管理ユーザが選択可能としてもよい。
【００５８】
廃棄確率DPの算出方法の具体例について説明する。例えば、（Ｎ＋１）段制御用メモリＴ３に格納された制御情報が図５に示された状態の場合、すなわち、最大閾値MAX_TH(N+1)が1000、最小閾値MIN_TH(N+1)が500、最大廃棄確率MAX_DPが50%、平均キュー長QAVEが700であり、定数αMAXが40%、定数βMAXが400である場合について説明する。
【００５９】
パケットが属する（Ｎ）段目のキューのキュー長QLEN(N)が最大閾値MAX_TH(N)の3/4の場合には、廃棄確率重みαは20%、廃棄閾値重みβは200となる。（Ｎ＋１）段目のキューの平均キュー長QAVEは700であることから、当該パケットの（Ｎ＋１）段目における廃棄確率DPは40%となる。そして、当該パケットは、40%の確率で廃棄と判定されて廃棄されることになる。一方、廃棄と判定されなかった場合には、当該パケットはキューイング制御部１０１からメモリ群１０２に送られ、バッファメモリＴ１に格納される。なお、廃棄確率DPに基づく廃棄判定には、乱数が用いられる。
【００６０】
同様に、パケットが属する（Ｎ）段目のキューのキュー長QLEN(N)が最大閾値MAX_TH(N)の1/4の場合には、廃棄確率重みαは-20%、廃棄閾値重みβは-200となる。（Ｎ＋１）段目のキューの平均キュー長QAVEが700であることから、当該パケットの（Ｎ＋１）段目における廃棄確率DPは0%となる。この場合には、当該パケットは廃棄と判定されず、キューイング制御部１０１からメモリ群１０２に送られ、バッファメモリＴ１に格納される。
【００６１】
図７（Ｂ）は、（Ｎ＋１）段目のキューにおける廃棄判定で用いられる条件式を示す説明図である。キューイング制御部１０１は、更新した平均キュー長QAVEと最大閾値MAX_TH(N+1)とを比較し、平均キュー長QAVEが最大閾値MAX_TH(N+1)以上であった場合にはパケットを廃棄する。キューイング制御部１０１は、平均キュー長QAVEが最大閾値MAX_TH(N+1)未満であった場合には、平均キュー長QAVEと補正最小閾値MIN_TH2(N+1)(=MIN_TH(N+1)-β)とを比較し、平均キュー長QAVEが補正最小閾値MIN_TH2(N+1)以下である場合には、パケットをバッファメモリＴ１に格納（キューイング）する。平均キュー長QAVEが最大閾値MAX_TH(N+1)未満であり、かつ補正最小閾値MIN_TH'(N+1)より大きい場合には、キューイング制御部１０１は、平均キュー長QAVEに応じて算出された廃棄確率DPに基づいて、廃棄判定を行なう。
【００６２】
以上より、本実施例によれば、バッファメモリＴ１を占有するような（Ｎ）段目のキューのパケットの廃棄確率DPを大きくし、当該パケットを選択的に廃棄することが可能となる。この点を比較例との対比を通して説明する。
【００６３】
図８は、比較例のREDによるパケットの廃棄判定をグラフ形式として示す説明図である。比較例のREDにおける平均キュー長QAVEと廃棄確率DPとの関係は、次のとおりである。
QAVE＞MAX_TH(N+1)のとき
DP=100%
QAVE＜MIN_TH(N+1)のとき
DP=0%
MIN_TH(N+1)≦QAVE≦MAX_TH(N+1)のとき
DP=(MAX_P)(QAVE-MIN_TH(N+1))/(MAX_TH(N+1)-MIN_TH(N+1))
上述した実施例との違いは、廃棄確率重みα及び廃棄閾値重みβが含まれていない点である。
【００６４】
（Ｎ＋１）段制御用メモリＴ３に格納された制御情報が図５に示された状態の場合について説明する。図５に示した例であれば、平均キュー長QAVEが700であるため、廃棄確率DPは20%となる。したがって、当該パケットは、20%の確率で廃棄と判定され、80%の確率で廃棄と判定されない。
【００６５】
このように、REDでは、（Ｎ＋１）段目のキューの平均キュー長QAVEに応じた廃棄確率DPに基づいてパケットを廃棄することで、キューあふれに起因するパケットの一斉廃棄を抑制することができる。このため、（Ｎ＋１）段目のキューにREDを適用した場合、（Ｎ＋１）段目のキューがキューあふれを起こすことによるパケットの一斉廃棄の発生確率を下げることが可能である。しかし、この比較例におけるＲＥＤでは、廃棄判定の対象となっているパケットが前段のどのキューのパケットであるかを問わないため、特定のキューによるバッファメモリＴ１の占有を抑制することは困難である。
【００６６】
これに対して、上記実施例によれば、上述したように、バッファメモリＴ１を占有するような（Ｎ）段目のキューのパケットの廃棄確率DPを大きくし、当該パケットを選択的に廃棄することが可能である。
【００６７】
すなわち、上記実施例によれば、複数の（Ｎ）段目のキューのうち、バッファメモリＴ１に格納されているパケット数が多いキューのパケットの廃棄確率DPが大きくなる一方で、バッファメモリＴ１に格納されているパケット数が少ないキューのパケットの廃棄確率DPが小さくなるので、バッファメモリＴ１を占有しているあるいはそれに近いキューのバッファメモリＴ１の使用率を下げることができる。
【００６８】
また、（Ｎ）段目のキュー長QLEN(N)が長いほど廃棄確率DPが大きくなっていくために、（Ｎ）段目のキュー全てにＲＥＤを実装した場合と同等の効果が得られる一方で、全てのキューにＲＥＤを実装するよりもはるかに小さな実装面積で済むため、低コスト・低消費電力を実現することができる。以上より、本実施例によれば、特定のキューによるバッファメモリの占有を抑制し、他のキューがバッファメモリを使用することができずに通信が阻害されることを抑制することができる。
【００６９】
Ｂ．第２実施例：
図９は、第２実施例における多段キュー構造についての概念を示す説明図である。上述した第１実施例との違いは、（Ｎ＋１）段目のキューにおける廃棄判定において廃棄クラスを用いるという点だけであり、（Ｎ）段目のキューにおける廃棄判定の処理及び構成は第１実施例と同じである。廃棄クラスとは、パケットを廃棄優先度毎に区分けするものであり、廃棄クラス毎にパケットの廃棄されやすさが異なる。
【００７０】
本実施例では、キューイング制御部１０１は、パケットが属する（Ｎ）段目のキューの状態に基づいて、当該パケットを４つの廃棄クラスのいずれかに区分けする。そして、キューイング制御部１０１は、廃棄優先度の高い廃棄クラスに区分けされたパケットを、廃棄優先度の低い廃棄クラスに区分けされたパケットに比べて廃棄されにくくする制御を行なう。具体的には、キューイング制御部１０１は、パケットが属する（Ｎ）段目のキューのキュー長QLEN(N)に基づいて、当該パケットの廃棄クラスを決定する。なお、本明細書において、「廃棄優先度が高い」とは、当該パケットが廃棄されにくいことを意味し、一方、「廃棄優先度が低い」とは、当該パケットが廃棄されやすいことを意味する。
【００７１】
例えば、図９の場合では、（Ｎ）段目のキュー#1000はキュー長QLEN(N)が短いため、キューイング制御部１０１は、（Ｎ）段目のキュー#1000に属するパケットを廃棄優先度の高い廃棄クラス#4に割り当てる。一方、（Ｎ）段目のキュー#1はキュー長QLEN(N)が長いため、キューイング制御部１０１は、（Ｎ）段目のキュー#1に属するパケットを、廃棄優先度の低い廃棄クラス#2に割り当てる。すなわち、（Ｎ）段目のキューのキュー長QLEN(N)の長いキューのパケットが廃棄優先度の低い廃棄クラスに割り当てられ、（Ｎ＋１）段目のキューにおける廃棄判定において廃棄と判定される可能性が高くなる。これにより、キュー長QLEN(N)の長い特定のキューによるバッファメモリＴ１の占有を抑制することができる。
【００７２】
本実施例では、パケットに割り当てられた廃棄クラスごとに異なる廃棄閾値が設定されており、図９には、廃棄クラス毎に設定された４つの廃棄閾値TH#1〜TH#4が示されている。４つの廃棄閾値TH#1〜TH#4は、廃棄優先度が高い廃棄クラスほど、小さな値に設定されている。
【００７３】
図１０は、第２実施例における（Ｎ＋１）段制御用メモリＴ３に格納された制御情報を示す説明図である。第２実施例における（Ｎ＋１）段制御用メモリＴ３は、廃棄判定を実行するために用いられる制御情報として、格納可能なキュー長の閾値である最大閾値MAX_TH(N+1)と、（Ｎ）段目の複数のキューに格納されているパケットの合計を示すキュー長QLEN(N+1)と、各廃棄クラスに設定された４つの廃棄閾値TH#1〜TH#4とを格納している。
【００７４】
キューイング制御部１０１は、（Ｎ＋１）段目のキューにおける廃棄判定において、キュー長QLEN(N+1)と、廃棄判定の対象となっているパケットの廃棄クラスに設定された廃棄閾値とを比較する。そして、キューイング制御部１０１は、キュー長QLEN(N+1)が当該廃棄閾値以上の場合にはパケットを廃棄と判定し、廃棄閾値未満の場合にはパケットを廃棄と判定しない。
【００７５】
このように、第２実施例では、パケットが属する（Ｎ）段目のキューのキュー長QLEN(N)によって廃棄クラスを決定し、当該廃棄クラス毎に設定された廃棄閾値に基づいて廃棄判定を行なうので、キュー長QLEN(N)の長い特定のキューによるバッファメモリＴ１の占有を抑制することができる。この結果、他のキューに通信の阻害が発生するのを抑制することができる。
【００７６】
なお、上記廃棄閾値TH#1〜TH#4の値や、廃棄クラスの割り当て方法、廃棄クラスの数は、管理ユーザによって変更可能とすることが好ましい。こうすれば、パケット中継装置１００に接続されたユーザ数や通信量等に合わせて、きめ細かい廃棄制御を実現することが可能となる。
【００７７】
Ｃ．第３実施例：
図１１は、第４実施例における（Ｎ）段制御用メモリＴ２に格納された制御情報を示す説明図である。上記第１ないし第３実施例では、キューイング制御部１０１は、（Ｎ）段目のキューのキュー長QLEN(N)を用いて廃棄確率DPを算出したり、廃棄クラスを決定しているが、この代わりに、キューイング制御部１０１は、（Ｎ）段目のキューの通信量TRAF(N)を計測し、（Ｎ＋１）段目のキューにおける廃棄判定の制御情報として用いることもできる。具体的には、例えば、キューイング制御部１０１は、通信量TRAFが多いキューに属するパケットが（Ｎ＋１）段目のキューにおける廃棄判定において廃棄と判定されやすくなるように、廃棄確率DPを算出したり、廃棄クラスを決定することができる。このようにしても、（Ｎ）段目のキューの状態を反映して、（Ｎ＋１）段目における廃棄判定を実現することができる。なお、キューイング制御部１０１は、（Ｎ）段目のキューの通信量TRAFとキュー長QLEN(N)とを含んだ制御情報に基づいて、廃棄確率DPを算出したり、廃棄クラスを決定してもよい。
【００７８】
Ｄ．第４実施例：
図１２は、キューごとに個別のバッファメモリを備えた態様を示す説明図である。本実施例では、物理的にバッファが分かれた構成（個別バッファ方式）となっており、（Ｎ）段目のキューにおけるメモリ群１０２Ａ，１０２Ｂは、それぞれ、バッファメモリＴ１と、（Ｎ）段制御用メモリＴ２とを備えている。（Ｎ＋１）段目のキューにおけるメモリ群１０２Ｃは、バッファメモリＴ１と（Ｎ＋１）段制御用メモリＴ３とを備えている。本実施例では、（Ｎ＋１）段目のキューにおける廃棄制御の際には、（Ｎ）段目のキューイング制御部１０１Ａ，１０１Ｂが（Ｎ）段制御用メモリＴ２に格納された（Ｎ）段目のキューの制御情報をキューイング制御部１０１Ｃに送信することで、上記の共有バッファ方式と同様の処理が可能となる。
【００７９】
以下、物理的にバッファが分かれている場合の動作について説明する。パケット中継装置がパケットを受け取ると、当該パケットがどのキューに属するかが決定される。当該パケットが属する（Ｎ）段目のキューでは、キューイング制御部１０１がそれぞれのメモリ群１０２の（Ｎ）段制御用メモリＴ２から、キュー長の最大閾値MAX_TH(N)と現在のバッファメモリＴ１に格納されたパケット数であるキュー長QLEN(N)を読み出し、当該パケットの廃棄判定を行う。廃棄と判定された場合には当該パケットは廃棄され、廃棄と判定されなかった場合には当該パケットはメモリ群１０２内のバッファメモリＴ１に書き込まれ、（Ｎ）段制御用メモリＴ２のキュー長QLEN(N)が１増加する。
【００８０】
その後、調停装置１０３によって（Ｎ）段目のキューに格納されているパケットが送出される順番になった時、（Ｎ）段目のバッファメモリＴ１からパケットのデータが読み出され、パケットのデータと同時に（Ｎ）段目のキューの制御情報であるキュー長QLEN(N)が（Ｎ＋１）段目のキューに送られる。これと同時に（Ｎ）段制御用メモリＴ２のキュー長QLEN(N)が１減少する。パケットを受け取った（Ｎ＋１）段目のキューでは、キューイング制御部１０１Ｃが、（Ｎ＋１）段目のメモリ群１０２Ｃの（Ｎ＋１）段制御用メモリＴ３から読み出した制御情報と、（Ｎ）段目のキューから受信した（Ｎ）段目のキューのキュー長QLEN(N)とを利用して、（Ｎ＋１)段目における廃棄判定を行う。このように、物理的にバッファが分かれた構成としても、（Ｎ）段目のキューの状態を反映して、（Ｎ＋１）段目における廃棄判定を実現することができる。
【００８１】
なお、上記第２ないし第４実施例において示した（Ｎ＋１）段目における廃棄判定の手法は、当然、本実施例において示したバッファが物理的に分かれた構成に対しても適用することができる。
【００８２】
Ｅ．変形例：
なお、この発明は上記の実施例や実施形態に限られるものではなく、その要旨を逸脱しない範囲において種々の態様において実施することが可能であり、例えば次のような変形も可能である。
【００８３】
変形例１：
上記実施例では、２段のキューを有する構成について説明したが、本発明は、３段以上のキューを有する構成に対しても同様に適用することができる。具体的には、各段におけるキューのパケットの廃棄判定において、キューイング制御部１０１は、前段以前のキューの制御情報とその段のキューの制御情報とに基づいて、廃棄判定が行われることになる。
【００８４】
変形例２：
上記第１実施例では、パケット中継装置１００が受信したパケットが（Ｎ）段目の複数のキューのうちどのキューに属するのかの判定は、キューイング制御部１０１が行なっているが、この代わりに、パケット中継装置１００とは別の他の装置がこの判定を行なうこととしてもよい。
【００８５】
変形例３：
上記第１実施例において示された廃棄確率DPを求めるための式や、廃棄確率重みα、廃棄閾値重みβを求めるための式は、一例であり、パラメータとして（Ｎ）段目のキューにおける制御情報を含んでいれば、他の式であってもよい。また、廃棄確率DPを求めるための式や、廃棄確率重みα、廃棄閾値重みβを求めるための式、これらの式に含まれる定数、廃棄クラス毎に設定される廃棄閾値TH（第２実施例）は、インターフェース部１０４を介した管理ユーザからの指示によって変更可能としてもよく、また、予め調整された複数の選択肢の中から選択可能としてもよい。こうすれば、ユーザ数や通信量の変化に応じて、パケットの廃棄判定の方式を適宜調整することが可能となる。
【００８６】
変形例４：
上記第２実施例では、廃棄クラスを４段階として説明したが、廃棄クラスは４段階以上または３段階以下とすることも可能である。
【００８７】
変形例５：
上記第２実施例では、キューイング制御部１０１は、パケットが属する（Ｎ）段目のキューのキュー長QLEN(N)が長いほど、廃棄優先度の低い廃棄クラスに割り当てていたが、これとは逆に、パケットが属する（Ｎ）段目のキューのキュー長QLEN(N)が長いほど、廃棄優先度の高い廃棄クラスに割り当てることとしてもよい。こうすれば、例えば（Ｎ）段目のキューでパケットがたまりキューあふれを起こしそうだが、（Ｎ＋１）段目のキューのバッファには余裕があるような場合に、キューあふれを起こしそうな（Ｎ）段目のキューのパケットの廃棄優先度を高く（廃棄されにくく）することで、（Ｎ）段目のキューのキューあふれを抑制することが可能となる。
【００８８】
変形例６：
上記実施例では、インターフェース部１０４に対してディスプレイ等の表示装置や、キーボード等の入力装置を接続可能としたが、この代わりに、パケット中継装置１００の本体に表示部や入力部を設けてもよい。また、インターフェース部１０４に代えて、ネットワーク経由でのリクエストを受け付ける簡易サーバの機能を設け、ネットワークに接続された他のコンピュータから上記廃棄確率DPを求めるための式やαMAX及びβMAX等の定数を設定するものとしてもよい。
【００８９】
変形例７：
上記実施例においてソフトウェアで実現されている機能の一部をハードウェアで実現してもよく、あるいは、ハードウェアで実現されている機能の一部をソフトウェアで実現してもよい。
【符号の説明】
【００９０】
１００…パケット中継装置
１０１…キューイング制御部
１０１Ａ…キューイング制御部
１０１Ｂ…キューイング制御部
１０１Ｃ…キューイング制御部
１０２…メモリ群
１０２Ａ…メモリ群
１０２Ｂ…メモリ群
１０２Ｃ…メモリ群
１０３…調停装置
１０４…インターフェース部
Ｔ１…バッファメモリ
Ｔ２…段制御用メモリ
Ｔ３…段制御用メモリ
【図１】
2011151601.tif 000003
【図２】
2011151601.tif 000004
【図３】
2011151601.tif 000005
【図４】
2011151601.tif 000006
【図５】
2011151601.tif 000007
【図６】
2011151601.tif 000008
【図７】
2011151601.tif 000009
【図８】
2011151601.tif 000010
【図９】
2011151601.tif 000011
【図１０】
2011151601.tif 000012
【図１１】
2011151601.tif 000013
【図１２】
2011151601.tif 000014