(57)【要約】【課題】余剰帯域共有の際において、各フローが公平に帯域を利用できるようにしながら、限られた通信容量を無駄なく活用すること。【解決手段】本発明は、複数のフローのデータを格納するバッファのフロー毎の使用量を管理し、新たなデータが到着した際にバッファに新たなデータが格納できる空き容量がある場合には新たなデータを格納し、バッファに前記新たなデータを格納する空き容量がない場合には使用量に基づいて選択したフローのデータをバッファから削除するようにした。【選択図】      図２
2004266561.tif 000002
【特許請求の範囲】
【請求項１】
複数のフローのデータを格納するバッファと、前記フロー毎の前記バッファの使用量を管理するバッファ使用量管理手段と、新たなデータが到着した際に前記バッファに前記新たなデータが格納できる空き容量がある場合には前記新たなデータを格納し、前記バッファに前記新たなデータを格納する空き容量がない場合には前記使用量に基づいて選択した前記フローの前記データを前記バッファから削除する入れ替え制御手段と、を具備したことを特徴とするトラヒック量制御装置。
【請求項２】
前記入れ替え制御手段は、前記使用量が多い順に複数の前記フローの中から一つの前記フローを選択し、選択した前記フローの前記データを削除することを特徴とする請求項１記載のトラヒック量制御装置。
【請求項３】
前記入れ替え制御手段は、全ての前記フローの前記使用量における平均値を求め、前記使用量が前記平均値より多い複数の前記フローの中から一つの前記フローを選択し、選択した前記フローの前記データを削除することを特徴とする請求項１記載のトラヒック量制御装置。
【請求項４】
前記入れ替え制御手段は、前記データを削除する際に同じ前記フローを連続して選択しないようにすることを特徴とする請求項１から請求項３のいずれかに記載のトラヒック量制御装置。
【請求項５】
前記入れ替え制御手段は、前記フローから削除する前記データをランダムに選ぶことを特徴とする請求項１から請求項４のいずれかに記載のトラヒック量制御装置。
【請求項６】
前記入れ替え制御手段は、前記フローから到着時間の古い前記データから順に削除することを特徴とする請求項１から請求項４のいずれかに記載のトラヒック量制御装置。
【請求項７】
請求項１から請求項６のいずれかに記載のトラヒック量制御装置と、受信したデータを前記トラヒック量制御装置に振り分ける振り分け手段と、前記バッファが格納した前記データを受信端末に転送する転送手段と、を具備したことを特徴とする中継装置。
【請求項８】
複数のフローのデータをバッファに格納するステップと、前記バッファの前記フロー毎の使用量を管理するステップと、新たなデータが到着した際に前記バッファに前記新たなデータが格納できる空き容量がある場合には前記新たなデータを格納するステップと、前記バッファに前記新たなデータを格納する空き容量がない場合には前記使用量に基づいて選択した前記フローの前記データを前記バッファから削除するステップと、を具備したトラヒック量制御方法。
【請求項９】
コンピュータに、複数のフローのデータをバッファに格納するステップと、前記バッファの前記フロー毎の使用量を管理するステップと、新たなデータが到着した際に前記バッファに前記新たなデータが格納できる空き容量がある場合には前記新たなデータを格納するステップと、前記バッファに前記新たなデータを格納する空き容量がない場合には前記使用量に基づいて選択した前記フローの前記データを前記バッファから削除するステップと、を行わせることを特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムを格納したことを特徴とするコンピュータ読取可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の中継装置からなる中継ネットワークと、情報を送受信する端末より構成される通信ネットワークにおいて、余剰帯域を活用しネットワーク効率を向上させるトラヒック量制御装置およびその方法に関する。
【０００２】
【従来の技術】
近年、インターネットサービスプロバイダのサービス多様化につれて、ユーザに最低帯域を保証するサービスが求められ始めている。
【０００３】
最低帯域を保証するサービスとしてＧＦＲ（Ｇｕａｒａｎｔｅｅｄ  Ｆｒａｍｅ  Ｒａｔｅ）サービスがある。このサービスでは、非輻輳時には各ユーザは互いに利用可能帯域（余剰帯域）を共有して利用することができる。余剰帯域の共有手法としては、ベストエフォートで利用されることが多い。
【０００４】
また、無線ＬＡＮの普及や、携帯電話の通信速度の向上により、無線通信におけるベストエフォートサービスの要望も増えてきている。
【０００５】
無線通信におけるベストエフォートサービスを考える場合、限られた通信容量をいかに無駄なく有効に使うかということが重要になってくる。
【０００６】
また、ベストエフォートサービスを行う場合、複数のフローが公平に帯域を利用できなければならない。つまり、公平性の確保が重要となる。
【０００７】
余剰帯域を共有する方式として、特許文献１に記載された方法がある。この方法は、各フローの保証レートとバッファのキュー長とから許可レートを計算し、入力レートが許可レートを下回っていた場合はパケットをバッファに格納する。そして、入力レートが許可レートを超えていた場合は許可レートを超えた分のパケットを廃棄する。
【０００８】
【特許文献１】
特開２００２−１８５４５９号公報
【０００９】
【発明が解決しようとする課題】
しかしながら、特許文献１の方法は、バッファに空きがあった場合も、入力レートが許可レートを超えていた場合はパケットを廃棄する。
【００１０】
このため、各フローの保証レートに偏りがあった場合で輻輳が発生していなかった場合、保証レートの低いフローは、まだバッファに十分な空き領域があるのにパケットが廃棄される。このように、特許文献１の方法は、通信容量を無駄なく利用することが難しい場合がある。したがって、ネットワーク資源を最大限に活用することはできないという問題がある。
【００１１】
本発明は、かかる点に鑑みてなされたものであり、余剰帯域共有の際において、限られた通信容量を無駄なく活用することを目的とする。
【００１２】
【課題を解決するための手段】
本発明は、複数のフローのデータを格納するバッファのフロー毎の使用量を管理し、新たなデータが到着した際にバッファに新たなデータが格納できる空き容量がある場合には新たなデータを格納し、バッファに新たなデータを格納する空き容量がない場合には使用量に基づいて選択したフローのデータをバッファから削除するようにした。
【００１３】
これにより、余剰帯域共有の際において、バッファの容量を最大限に使用できるので、限られた通信容量を無駄なく活用することができる。
【００１４】
【発明の実施の形態】
本発明の第１の態様にかかるトラヒック量制御装置は、複数のフローのデータを格納するバッファと、前記フロー毎の前記バッファの使用量を管理するバッファ使用量管理手段と、新たなデータが到着した際に前記バッファに前記新たなデータが格納できる空き容量がある場合には前記新たなデータを格納し、前記バッファに前記新たなデータを格納する空き容量がない場合には前記使用量に基づいて選択した前記フローの前記データを前記バッファから削除する入れ替え制御部と、を具備した構成を採る。
【００１５】
これにより、余剰帯域共有の際において、バッファの容量を最大限に使用できるので、限られた通信容量を無駄なく活用できるように帯域制御が行える。
【００１６】
本発明の第２の態様は、第１の態様にかかるトラヒック量制御装置において、前記入れ替え制御手段は、前記使用量が多い順に複数の前記フローの中から一つの前記フローを選択し、選択した前記フローの前記データを削除する。
【００１７】
これにより、バッファの使用量の最も多いフローのデータを削除でき、その他のフローがバッファを使用できるようになるので、全てのフローが公平にバッファを使用できるようになる。この結果、全てのフローが通信帯域を使えるようになる。つまり、複数のフローが公平に帯域を利用するベストエフォートサービスを提供できる。
【００１８】
本発明の第３の態様は、第１の態様にかかるトラヒック量制御装置において、前記入れ替え制御手段は、全ての前記フローの前記使用量における平均値を求め、前記使用量が前記平均値より多い複数の前記フローの中から一つの前記フローを選択し、選択した前記フローの前記データを削除する。
【００１９】
これにより、バッファの使用量が平均値より多いフローのデータを削除でき、全てのフローが公平にバッファを使用できるようになる。この結果、全てのフローが公平に通信帯域を使えるようになる。
【００２０】
本発明の第４の態様は、第１の態様から第３の態様のいずれかにかかるトラヒック量制御装置において、前記入れ替え制御手段は、前記データを削除する際に同じ前記フローを連続して選択しないようにする。
【００２１】
これにより、同じフローからデータを連続して削除しないようにできる。この結果、同じフローから連続したデータを連続して削除しないようにできる。よって、フローがＴＣＰフローである場合でも、ＴＣＰフローにおけるスループットの極端な低下を抑えることができるように、帯域制御を行うことができる。
【００２２】
本発明の第５の態様は、第１の態様から第４の態様のいずれかにかかるトラヒック量制御装置において、前記入れ替え制御手段は、前記フローから削除する前記データをランダムに選ぶ。
【００２３】
これにより、同じフローから連続したデータが連続して削除されることを抑えることができる。この結果、フローがＴＣＰフローである場合でも、ＴＣＰフローにおけるスループットの極端な低下を抑えることができるように、帯域制御を行うことができる。
【００２４】
本発明の第６の態様は、第１の態様から第４の態様のいずれかにかかるトラヒック量制御装置において、前記入れ替え制御手段は、前記フローから到着時間の古い前記データから順に削除する。
【００２５】
前記フローがＴＣＰフローであった場合、前記データがあまり長く前記バッファ内に存在していると、受信端末に前記データが届くのが遅れ、送信端末にＡＣＫが帰るのが遅くなる。このような場合、受信端末は前記データを受け取っているのにも関わらず、送信端末側で再度前記データを送ってしまう場合がある、したがって、あまり長く前記バッファ内に存在している前記データは廃棄してしまって、その分別の前記データを送った方がよいことになる。したがって、上述したように、到着時間の古い前記データを廃棄することにより、ＴＣＰフローのスループットの低下を抑えることができる。
【００２６】
本発明の第７の態様にかかる中継装置は、第１の態様から第６の態様のいずれかにかかるトラヒック量制御装置と、受信したデータを前記トラヒック量制御装置に振り分ける振り分け手段と、前記バッファが格納した前記データを受信端末に転送する転送手段と、を具備した構成を採る。
【００２７】
これにより、本発明のトラヒック量制御装置を用いた中継装置が実現できる。
【００２８】
本発明の第８の態様は、複数のフローのデータをバッファに格納するステップと、前記バッファの前記フロー毎の使用量を管理するステップと、新たなデータが到着した際に前記バッファに前記新たなデータが格納できる空き容量がある場合には前記新たなデータを格納するステップと、前記バッファに前記新たなデータを格納する空き容量がない場合には前記使用量に基づいて選択した前記フローの前記データを前記バッファから削除するステップと、を具備したトラヒック量制御方法である。
【００２９】
本発明の第９の態様は、コンピュータに、複数のフローのデータをバッファに格納するステップと、前記バッファの前記フロー毎の使用量を管理するステップと、新たなデータが到着した際に前記バッファに前記新たなデータが格納できる空き容量がある場合には前記新たなデータを格納するステップと、前記バッファに前記新たなデータを格納する空き容量がない場合には前記使用量に基づいて選択した前記フローの前記データを前記バッファから削除するステップと、を行わせることを特徴とするプログラムである。
【００３０】
本発明の第１０の態様は、第９の態様にかかるプログラムを格納したことを特徴とするコンピュータ読取可能な記憶媒体である。
【００３１】
以下、本発明の一実施の形態にかかるトラヒック量制御を適用した中継装置について添付図面を参照して説明する。図１は、上記実施の形態にかかる中継装置の構成図である。
【００３２】
本発明の中継装置１０２は、送信端末１０１から送られてきたデータを複数の受信端末１０３ａ〜１０３ｎに中継する。送信端末１０１および受信端末１０３ａ〜１０３ｎは、具体的にはサーバ、ＰＣなどのユーザ端末である。
【００３３】
中継装置１０２には、送信端末１０１から到着したＩＰパケットのＩＰヘッダの「あて先アドレス」などの情報をもとにＩＰパケットをＩＰパケット蓄積管理部１０５ａ〜１０５ｎに振り分けるＩＰパケット振り分け部１０４と、ＩＰパケットの蓄積、及び、ＩＰパケットの送出を行うＩＰパケット蓄積管理部１０５ａ〜１０５ｎが設けられている。なお、本文中の廃棄とは、ＩＰパケット廃棄を意味する。
【００３４】
また、中継装置１０２は、具体的にはルータやゲートウェイである。本実施の形態で仮定するネットワークは、インターネットプロトコル（ＩＰ）を前提とし、伝送路は有線（例えばＦＴＴＨ，ＡＤＳＬ）／無線（例えば無線ＬＡＮ）のいずれであってもよい。
【００３５】
次に、ＩＰパケット蓄積管理部１０５ａ〜１０５ｎの構成について図２を用いて説明する。図２は、上記実施の形態にかかるＩＰパケット蓄積管理部１０５ａ〜１０５ｎの構成図である。
【００３６】
ＩＰパケット蓄積管理部１０５ａ〜１０５ｎには、トラヒック量制御部２００が設けられている。
【００３７】
トラヒック量制御部２００は、ＩＰパケット振り分け部１０４からの到着パケットのフローのトラヒック量を制御する。トラヒック量制御部２００は、フロー検出部２０１、バッファ使用量管理部２０２、パケット入れ替え制御部２０３、およびＩＰパケット蓄積部２０４から構成されている。
【００３８】
フロー検出部２０１は、ＩＰパケット振り分け部１０４からの到着ＩＰパケットがどのフローのＩＰパケットかということを識別する。フロー検出部２０１は、到着したＩＰパケットのフロー番号、および、データ量をバッファ使用量管理部２０２に送る。
【００３９】
ＩＰパケット蓄積部２０４は、転送待ちのＩＰパケットを格納しておくバッファである。また、本実施例ではＩＰパケット蓄積部２０４は、一つのキューで構成されている。
【００４０】
バッファ使用量管理部２０２は、ＩＰパケット蓄積部２０４内に格納されている各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量（以下、単にバッファ使用量ともいう）、および、ＩＰパケット蓄積部２０４の総バッファ使用量（以下、単に総バッファ使用量ともいう）を保持しておく。バッファ使用量管理部２０２は、必要に応じて各フローのバッファ使用量、および、総バッファ使用量をパケット入れ替え制御部２０３に送る。
【００４１】
パケット入れ替え制御部２０３は、バッファ使用量管理部２０２から送られて各フローのバッファ使用量、および、総バッファ使用量のデータをもとに到着ＩＰパケットをＩＰパケット蓄積部２０４に格納するのか、または、ＩＰパケット蓄積部２０４内に格納されている他のＩＰパケットと入れ替えるのか、または、廃棄するのかを決定する。
【００４２】
また、ＩＰパケット蓄積管理部１０５ａ〜１０５ｎには、トラヒック量制御部２００から出力されたＩＰパケットを受信端末１０３に転送するＩＰパケット転送部２０５が設けられている。
【００４３】
ＩＰパケット転送部２０５は、ＩＰパケットを受信端末１０３に転送した際、転送したＩＰパケットのフロー番号、及び、ＩＰパケットのデータ量をバッファ使用量管理部２０２に送る。
【００４４】
次に、中継装置１０２のＩＰパケット受信時の動作について図３を用いて説明する。図３は、上記実施の形態にかかるトラヒック量制御部２００のＩＰパケット受信時における動作の流れを示す図である。
【００４５】
まず、中継装置１０２に到着したＩＰパケットは、まずＩＰパケット振り分け部１０４に入る。そして、ＩＰパケット振り分け部１０４が、このＩＰパケットをＩＰパケットの「あて先アドレス」などに応じて、ＩＰパケット蓄積管理部１０５に振り分ける（ステップ３０１）。
【００４６】
次に、ＩＰパケット蓄積管理部１０５においてフロー検出部２０１が、到着したＩＰパケットのフロー番号を検出する（ステップ３０２）。
【００４７】
次に、バッファ使用量管理部２０２が、フロー検出部２０１から得た到着ＩＰパケットのフロー番号、および、到着ＩＰパケットのデータ量をもとに到着ＩＰパケットのフローのバッファ使用量、及び、総バッファ使用量を到着ＩＰパケットのデータ量分増やす（ステップ３０３）。
【００４８】
次に、パケット入れ替え制御部２０３が、ＩＰパケット蓄積部２０４に十分な空き容量あるのかを確認する（ステップ３０４）。
【００４９】
次に、ＩＰパケット蓄積部２０４に十分な空き容量があった場合は（ステップ３０５）、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に送り格納する（ステップ３０６）。
【００５０】
一方、ＩＰパケット蓄積部２０４に十分な空き容量がなかった場合は（ステップ３０５）、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４内のＩＰパケット、または、到着ＩＰパケットを廃棄する（ステップ３０７）。
【００５１】
次に、パケット入れ替え制御部２０３は、ＩＰパケット廃棄後、再度ＩＰパケット蓄積部２０４の容量とＩＰパケット蓄積部２０４の使用量を比較し（ステップ３０４）、十分な空き容量があれば（ステップ３０５）、ＩＰパケットを格納し（ステップ３０６）、まだ空き容量が十分でなければ（ステップ３０５）、ＩＰパケットの廃棄を行う（ステップ３０７）。
【００５２】
そして、パケット入れ替え制御部２０３は、ステップ３０４、ステップ３０５、および、ステップ３０７の動作をＩＰパケット蓄積部２０４の総バッファ使用量がＩＰパケット蓄積部２０４のバッファの容量より小さくなるまで繰り返す。
【００５３】
以上のように、中継装置１０２は、ＩＰパケットを受信した際、ＩＰパケット蓄積部２０４がいっぱいになるまで、ＩＰパケットを蓄積するように動作する。これにより、余剰帯域共有の際において、各フローが限られた通信容量を無駄なく活用できる。
【００５４】
次に、図３におけるステップ３０１の動作について図４を用いて詳細に説明する。図４は、上記実施の形態にかかるＩＰパケット振り分け部１０４の動作を示す図である。
【００５５】
ステップ３０１において、まず、ＩＰパケット振り分け部１０４は、到着したＩＰパケットのＩＰヘッダ情報から、「あて先アドレス」の情報を読み込み（ステップ４０１）、読み込んだ「あて先アドレス」をもとに到着したＩＰパケットをＩＰパケット蓄積管理部１０５に振り分ける（ステップ４０２）。
【００５６】
このようにして、ＩＰパケット振り分け部１０４は、到着ＩＰパケットを振り分ける。
【００５７】
なお、本実施の形態では、ＩＰパケット振り分け部１０４は、「あて先アドレス」に基づいて、到着したＩＰパケットを振り分けたが、到着したＩＰパケットの「送信元アドレス」、「ポート番号」、「ＶＬＡＮタグ」、「ＭＰＬＳタグ」、「Ｅｔｈｅｒアドレス」、「コンテンツの内容」などの情報を読み込み、これらの情報やこれらの情報の組み合わせをもとに、到着したＩＰパケットをＩＰパケット蓄積管理部１０５に振り分けるようにしても良い。
【００５８】
次に、図３におけるステップ３０２の動作について図５を用いて詳細に説明する。図５は、上記実施の形態にかかるフロー検出部２０１の動作を示す図である。
【００５９】
まず、フロー検出部２０１が、到着したＩＰパケットのＩＰヘッダのフローＩＤフィールドからフロー番号を読み込み、読み込んだ値をバッファ使用量管理部２０２に送る（ステップ５０１）。
【００６０】
次に、フロー検出部２０１は、到着したＩＰパケットのＩＰヘッダから到着ＩＰパケットのデータ量を読み込み、バッファ使用量管理部２０２に送る（ステップ５０２）。
【００６１】
最後に、フロー検出部２０１は、到着ＩＰパケットをパケット入れ替え制御部２０３に送る（ステップ５０３）。
【００６２】
なお、本実施の形態では、フロー検出部２０１は、ＩＰヘッダのフローＩＤフィールドからフロー番号を読み込む形態を採ったが、到着したＩＰパケットの「あて先アドレス」、「送信元アドレス」、「ポート番号」、「ＶＬＡＮタグ」、「ＭＰＬＳタグ」、「Ｅｔｈｅｒアドレス」、「コンテンツの内容」などの情報を読み込み、これらの情報やこれらの情報の組み合わせをもとに、ＩＰパケットのフロー番号を検出・確認し、検出結果であるフロー番号をバッファ使用量管理部２０２に送る形態であっても良い。
【００６３】
次に、図３におけるステップ３０３の動作について図６を用いて詳細に説明する。図６は、上記実施の形態にかかるバッファ使用量管理部２０２の動作を示した図である。
【００６４】
バッファ使用量管理部２０２は、フロー検出部２０１から到着ＩＰパケットのフロー番号、および、到着ＩＰパケットのデータ量を取得する（ステップ６０１）。
【００６５】
次に、フロー検出部２０１から得た到着ＩＰパケットのフロー番号をもとに到着ＩＰパケットのフローのＩＰパケット蓄積部２０４におけるバッファ使用量を到着ＩＰパケットのデータ量分増やす（ステップ６０２）。
【００６６】
次に、バッファ使用量管理部２０２は、ＩＰパケット蓄積部２０４の総バッファ使用量（総データ量）を到着ＩＰパケットのデータ量分増やす（ステップ６０３）。
【００６７】
最後に、バッファ使用量管理部２０２は、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量、および、ＩＰパケット蓄積部２０４の総バッファ使用量をパケット入れ替え制御部２０３に送る（ステップ６０４）。
【００６８】
本実施の形態では、データ量をＩＰパケット蓄積部２０４のバッファ容量の単位として考えているが、ＩＰパケット蓄積部２０４のバッファ容量の単位としては、ＩＰパケット数や、フレーム数、セル数などを用いても構わない。
【００６９】
次に、図３におけるステップ３０４、ステップ３０５、ステップ３０６、および、ステップ３０７の動作について詳細に説明する。
【００７０】
本実施の形態では、ＩＰパケット蓄積部２０４のバッファに余裕のある限り、到着ＩＰパケットを廃棄せずに格納する。こうすることにより、ネットワーク資源をより無駄なく有効に利用することができる。
【００７１】
しかし、到着ＩＰパケットを格納し続けていると、ＩＰパケット蓄積部２０４のバッファがいっぱいになってしまうことがある。そこで、ＩＰパケットが到着した際に、ＩＰパケット蓄積部２０４のバッファに十分な空き容量がない場合は、ＩＰパケット蓄積部２０４内に格納されているＩＰパケット、または、到着ＩＰパケットを廃棄することにより必要な空き容量を確保する。
【００７２】
しかし、同一フローから連続したＩＰパケットを連続して廃棄してしまうとそのフローがＴＣＰフローだった場合、送信側に受信側からＩＰパケットが受信されたというＡＣＫが連続して帰ってこなくなる。この場合は、送信側は、ネットワークの輻輳が激しいために、受信側がＩＰパケットの受信ができず、ＡＣＫが帰ってこないと判断する。そして、送信側は、輻輳がそれほど激しくなくても、受信側に対して一度に送るＩＰパケット数を減らす処理をする。このようにして、実際には激しい輻輳が発生しているわけではないのに、スループットの極端な低下を招いてしまう恐れがある。
【００７３】
このため、ＴＣＰフローのスループットの極端な低下を防ぐために、同一フローから連続したＩＰパケットが連続して廃棄されてしまわないようにすることが望ましい。そこで、本実施の形態では、一つのフローからＩＰパケットを連続して廃棄するのではなく、複数の異なるフローから交互にＩＰパケットを廃棄する手法をとっている。
【００７４】
こうすることにより、一つのフローから連続的にＩＰパケットが廃棄されることを防ぎ、ＴＣＰフローのスループットの極端な低下を抑えることができる。
【００７５】
さらに、本実施の形態では、複数のフローが余剰帯域を公平に使えるように、帯域の使用量が多いフローのＩＰパケットを削除するように工夫をしている。
【００７６】
詳細には、ＩＰパケットを廃棄するフローを決定する際には、閾値を計算し、ＩＰパケット蓄積部２０４におけるバッファ使用量がその閾値を超えているフローの中で順番にＩＰパケットを廃棄するようにする。
【００７７】
こうすることで、ＩＰパケット蓄積部２０４のバッファを多く利用しているフローのＩＰパケットが廃棄されやすいようにできる。
【００７８】
さらに、本実施の形態では、閾値を超えている複数のフローから交互にＩＰパケットを廃棄するようにしている。これにより、１つのフローからの連続したＩＰパケット廃棄を防ぎ、また、フロー間の公平性を高めることが可能である。また、上記のようにＩＰパケットのＩＰパケット蓄積部２０４のバッファへの格納を制御することで、ＴＣＰのスループットの極端な低下を抑えながら、余剰帯域を余すことなく利用することが可能で、公平性を保持することもできる。
【００７９】
次に、図７を用いて、実施の形態にかかるパケット入れ替え制御部２０３の動作について詳しく説明する。
【００８０】
まず、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、パケット入れ替え制御部２０３で保持しているＩＰパケット蓄積部２０４のバッファ容量とバッファ使用量管理部２０２から得た現在のＩＰパケット蓄積部２０４の総バッファ使用量を比較する（ステップ７０１）。
【００８１】
ここで、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があれば（（バッファ容量）≧（総バッファ使用量）ならば）（ステップ７０２）、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【００８２】
一方、ＩＰパケット蓄積部２０４のバッファに十分な空き容量がなければ（（バッファ容量）＜（総バッファ使用量）ならば）（ステップ７０２）、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量をＩＰパケット蓄積部２０４のバッファ容量以内に納めるためにいくつかのＩＰパケットを廃棄する。
【００８３】
ＩＰパケットを廃棄するためには、ＩＰパケットを廃棄するフローを決定する必要がある。また、複数のフローが公平に余剰帯域を使用するために、各フローの使用している帯域の目安として、ＩＰパケット蓄積部２０４のバッファを多く使用しているフローのＩＰパケットを廃棄し、その他のフローがバッファを使用できるようにする必要がある。
【００８４】
このため、まず、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量を、現在、ＩＰパケット蓄積部２０４のバッファを使用しているフローの数で割って各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の平均値を計算する。そして、パケット入れ替え制御部２０３は、この計算した平均値を、ＩＰパケットを廃棄するフローを決定するための閾値とする（ステップ７０３）。
【００８５】
なお、本実施の形態では、ＩＰパケットを廃棄するフローを決定するための閾値として、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の平均値にしたが、これ以外であっても良い。この閾値は、ＩＰパケット蓄積部２０４におけるバッファ使用量の高いフローが選び出せるような値であれば構わない。
【００８６】
次に、パケット入れ替え制御部２０３は、閾値を超えているフローについてＩＰパケット蓄積部２０４におけるバッファ使用量の多い順にソートする（ステップ７０４）。
【００８７】
なお、本実施の形態では、ＩＰパケットを廃棄するフローの候補として、閾値をもとに選択したが、閾値を用いずに、ＩＰパケット蓄積部２０４におけるバッファ使用量の多い順に複数フローを選択するなどの方法でも構わない。
【００８８】
次に、パケット入れ替え制御部２０３は、同じフローのＩＰパケットを連続して廃棄しないようにするために、閾値を超えたフローの内、過去α回（αはパラメータ）の廃棄についてＩＰパケットを廃棄されたフローの番号の履歴（パケット入れ替え制御部２０３が保持している）の中に番号のないフローを選択する。
【００８９】
そして、次に、パケット入れ替え制御部２０３は、このように選択したフローの中で、ＩＰパケット蓄積部２０４におけるバッファ使用量の最も多いフローを選択する。つまり、パケット入れ替え制御部２０３は、閾値を超えたフローの内、過去α回の処理中にＩＰパケットが廃棄されていなく、かつ最もバッファ使用量の多いフローを選択する。
【００９０】
そして、パケット入れ替え制御部２０３は、このように選択したフローのＩＰパケットの中からランダムに一つＩＰパケットを選んできて廃棄する。
【００９１】
もし、上記条件を満たすフローが存在しなかった場合は、パケット入れ替え制御部２０３は、閾値を超えたフローのうち最も昔に廃棄されたフローのＩＰパケットの中からランダムに一つＩＰパケットを選んできて廃棄する（ステップ７０５）。
【００９２】
このようにフローのＩＰパケットの中からランダムに一つＩＰパケットを選んできて廃棄することにより、同じフローから連続したＩＰパケットを連続して廃棄することが抑えられる。
【００９３】
なお、廃棄するＩＰパケットの決め方は、ランダムでなくても、最も滞在時間の長い、つまり到着時間の最も古いデータＩＰパケットや、到着時間の最も新しいＩＰパケットなどにしてもよい。
【００９４】
フローがＴＣＰフローであった場合、ＩＰパケットがあまり長くバッファ内に存在していると、受信端末にＩＰパケットが届くのが遅れ、送信端末にＡＣＫが帰るのが遅くなる。このような場合、受信端末はＩＰパケットを受け取っているのにも関わらず、送信端末側で同じＩＰパケットを送ってしまう場合がある、したがって、あまり長くバッファ内に存在しているＩＰパケットは廃棄してしまって、その分別のＩＰパケットを送った方がよいことになる。したがって、上述したように、最も滞在時間の長いＩＰパケットを廃棄することにより、ＴＣＰフローのスループットの低下を抑えられる。
【００９５】
次に、パケット入れ替え制御部２０３は、過去α回のＩＰパケット廃棄の履歴９０７を更新する（ステップ７０６）。
【００９６】
次に、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファ使用状況を更新するため、ＩＰパケットを廃棄したフローにおけるＩＰパケット蓄積部２０４のバッファ使用量を廃棄したＩＰパケットのデータ量分減らす（ステップ７０７）。さらに、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量を廃棄したＩＰパケットのデータ量分減らす（ステップ７０８）。
【００９７】
そして、パケット入れ替え制御部２０３は、ステップ７０１からステップ７０８までの動作をＩＰパケット蓄積部２０４のバッファに十分な空き容量ができるまで繰り返す。
【００９８】
ＩＰパケット蓄積部２０４のバッファに十分な空き容量ができれば、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。次に、ＩＰパケット蓄積部２０４は、バッファ使用量管理部２０２に計算した各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量とＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ７１０）。
【００９９】
このようにして、余剰帯域共有の際において、ＴＣＰフローのスループットの低下を抑えつつ、各フローが公平に帯域を利用できるようにしながら、限られた通信容量を無駄なく活用することができる。
【０１００】
また、今後ＵＤＰフローは、帯域保証型サービスで利用され、ベストエフォートサービスにおいてはＴＣＰフローが流れる可能性が高いと考えられるので、本発明は、将来において大きな効果を持つと考えられる。
【０１０１】
次に、図８を用いてＩＰパケット転送時の動作を説明する。
【０１０２】
出力リンクが空いたとき、ＩＰパケット転送部２０５は、ＩＰパケットを受信端末１０３に転送する（ステップ８０１）。
【０１０３】
ＩＰパケットの転送順序は、対象となる全てのフローが一つのＦＩＦＯキューに集約されている場合は、最も昔に格納されたＩＰパケットから順に転送すればよい。
【０１０４】
このように、対象となる全てのフローを一つのＦＩＦＯキューに集約することにより、フロー毎にキューを用意する必要がなくなり、必要とするバッファ容量を抑えることができる。したがって、回線が高速化され、収容フロー数が多いようなモデルに適用するのに適している。
【０１０５】
なお、回線が比較的低速で、収容フロー数があまり多くないモデルであれば、ＩＰパケットの転送順序を、スケジューリングアルゴリズムにより管理しても良い。スケジューリングアルゴリズムとは、最低帯域を保証しつつ、余剰帯域を共有することができる方式で従来から使われているものである。スケジューリングアルゴリズム中でもよく使われるものとしてＣＢＱ（Ｃｌａｓｓ  Ｂａｓｅｄ  Ｑｕｅｕｅ）がある。ＣＢＱは各フローに所定のレートを割り当てるようにレートコントロールするスケジューリングアルゴリズムである。
【０１０６】
次に、バッファ使用量管理部２０２に、転送したＩＰパケットのフロー番号、および、転送したＩＰパケットのデータ量を送る（ステップ８０２）。
【０１０７】
こうすることにより、ＩＰパケット蓄積部２０４のバッファの使用状況を正確なものにする。最後に、バッファ使用量管理部２０２が、ＩＰパケット転送部２０５から得た、転送されたＩＰパケットのフロー番号、および、転送されたＩＰパケットのデータ量をもとに、フロー番号のフローにおけるＩＰパケット蓄積部２０４のバッファ使用量、および、ＩＰパケット蓄積部２０４の総バッファ使用量を再計算する（ステップ８０３）。
【０１０８】
次に、図９〜図１８を用いて、ＩＰパケット蓄積管理部１０５内での動作について具体例を用いて説明する。
【０１０９】
本実施の形態では、フローはＦｌｏｗ１からＦｌｏｗ６までの６本のフローが流れているとする。また、簡単のため、全てのＩＰパケットのデータ量は１５００（ｂｙｔｅ）とし、ＩＰパケット蓄積部２０４のバッファ容量は３００００（ｂｙｔｅ）とする。また、全てのフローは、一つのＦＩＦＯキューに格納されるものとし、全てのフローでＩＰパケット蓄積部２０４のバッファ容量３００００（ｂｙｔｅ）を共有する。
【０１１０】
図９は各フローのＩＰパケット蓄積部２０４のバッファ使用状況を表しており、９０１〜９０６に示すものは、各フローのＩＰパケットがいくつＩＰパケット蓄積部２０４のバッファ内にあるかということを表した仮想的なキューである。キュー９０１〜９０６は、いくつかのＩＰパケットから構成されている。
【０１１１】
実際には、一つのＦＩＦＯキュー９０１〜９０６に全てのフローのＩＰパケットが順不同に格納されている。また、廃棄の履歴９０７としては、実施例では扱うフロー数が少ないので前回廃棄したフローの番号一つのみを用いるものとする。
【０１１２】
図９の状態では、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量は、Ｆｌｏｗ１が１０５００（ｂｙｔｅ）、Ｆｌｏｗ２が１０５００（ｂｙｔｅ）、Ｆｌｏｗ３が３０００（ｂｙｔｅ）、Ｆｌｏｗ４が１５００（ｂｙｔｅ）、Ｆｌｏｗ５が１５００（ｂｙｔｅ）、Ｆｌｏｗ６が１５００（ｂｙｔｅ）である。
【０１１３】
また、ＩＰパケット蓄積部２０４の総バッファ使用量は２８５００（ｂｙｔｅ）である。
【０１１４】
ここで、ＩＰパケット蓄積管理部１０５にＦｌｏｗ３のＩＰパケットが到着したとする。
【０１１５】
まず、フロー検出部２０１が到着ＩＰパケットのＩＰヘッダのフローＩＤフィールドからフロー番号「３」を読み取り、検出結果であるフロー番号「３」という情報をバッファ使用量管理部２０２に送る（ステップ５０１）。
【０１１６】
次に、フロー検出部２０１は、到着ＩＰパケットのデータ量「１５００ｂｙｔｅ」という情報をバッファ使用量管理部２０２に送る（ステップ５０２）。
【０１１７】
これに対して、バッファ使用量管理部２０２は、フロー検出部から得た（ステップ６０１）フロー番号「３」、ＩＰパケットデータ量「１５００（ｂｙｔｅ）」という情報をもとにＦｌｏｗ３におけるＩＰパケット蓄積部２０４のバッファ使用量を１５００（ｂｙｔｅ）増やして４５００（ｂｙｔｅ）にする（ステップ６０２）。また、バッファ使用量管理部２０２は、ＩＰパケット蓄積部２０４の総バッファ使用量も１５００（ｂｙｔｅ）増やして３００００（ｂｙｔｅ）にする（ステップ６０３）。
【０１１８】
次に、バッファ使用量管理部２０２は、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量、および、ＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））をパケット入れ替え制御部２０３に送る（ステップ６０４）。
【０１１９】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））と、バッファ使用量管理部２０２から得たＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））を比較する（ステップ７０１）。
【０１２０】
この場合、ＩＰパケット蓄積部２０４のバッファ容量（３００００）＝ＩＰパケット蓄積部２０４の総バッファ使用量（３００００）であり（ステップ７０２）、到着ＩＰパケットを格納するだけの空き容量があるので、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【０１２１】
次に、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２に各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量とＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ７１０）。
【０１２２】
この時点で、各フローのＩＰパケット蓄積部２０４のバッファ使用状況は図１０のようになっている。
【０１２３】
次に、図１０の状態でＦｌｏｗ５のＩＰパケットが到着したとする。
【０１２４】
この場合、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２から、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量として、Ｆｌｏｗ１が１０５００（ｂｙｔｅ）、Ｆｌｏｗ２が１０５００（ｂｙｔｅ）、Ｆｌｏｗ３が４５００（ｂｙｔｅ）、Ｆｌｏｗ４が１５００（ｂｙｔｅ）、Ｆｌｏｗ５が３０００（ｂｙｔｅ）、Ｆｌｏｗ６が１５００（ｂｙｔｅ）という情報を得る。また、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量として、３１５００（ｂｙｔｅ）という情報を得る（ステップ６０４）。
【０１２５】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））と、バッファ使用量管理部２０２から得たＩＰパケット蓄積部２０４の総バッファ使用量（３１５００（ｂｙｔｅ））を比較する（ステップ７０１）。
【０１２６】
この場合、バッファ容量（３００００）＜総バッファ使用量（３１５００）なので（ステップ７０２）、このままでは到着ＩＰパケットを格納することができない。そこで、パケット入れ替え制御部２０３は、いくつかのＩＰパケットを廃棄する。
【０１２７】
まず、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄するための閾値を計算する（ステップ７０３）。本実施の形態では、この閾値を各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の平均値とする。
【０１２８】
そこで、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量３１５００（ｂｙｔｅ）をフロー数６で割り、閾値として５２５０（ｂｙｔｅ）という値を得る。
【０１２９】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄するフローの候補として、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフローを調べて、ＩＰパケット蓄積部２０４におけるバッファ使用量の多い順にソートする（ステップ７０４）。
【０１３０】
この場合、Ｆｌｏｗ１とＦｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量が閾値を超えている。また、Ｆｌｏｗ１とＦｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量は同じである（１０５００（ｂｙｔｅ））。
【０１３１】
本実施の形態では、複数のフローにおけるＩＰパケット蓄積部２０４におけるバッファ使用量が同じ場合には、フロー番号順にソートすることにする。
【０１３２】
したがって、この例では、Ｆｌｏｗ１、Ｆｌｏｗ２の順になる。
【０１３３】
なお、本実施の形態では、バッファ使用量の同じフローが複数ある場合にはフロー番号順にソートすることにしたが、最終ＩＰパケットの到着タイム順にしても、確率的に決定する等でも構わない。
【０１３４】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄する（ステップ７０５）。
【０１３５】
パケット入れ替え制御部２０３は、ＩＰパケットを廃棄するフローの決定を、閾値を超えたフローの番号と廃棄の履歴９０７とを用いて決定する。
【０１３６】
廃棄の履歴９０７の値は「１」であり、これは前回廃棄されたフローの番号が「１」であったということを示している。
【０１３７】
本実施の形態では、廃棄の履歴９０７の中にないフロー番号のフローから廃棄を行うようにすることで、同じフローからＩＰパケットを連続して廃棄してスループットの極端な低下を招くことを防いでいる。
【０１３８】
この場合、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフローであるＦｌｏｗ１およびＦｌｏｗ２のうち、廃棄の履歴９０７の中にフロー番号が出てこないＦｌｏｗ２のＩＰパケットを廃棄する。
【０１３９】
ここでは、Ｆｌｏｗ２のＩＰパケット１から７のうち、ランダムに選んだ６番のＩＰパケットが廃棄されたとする。
【０１４０】
次に、パケット入れ替え制御部２０３は、廃棄の履歴９０７を更新する（ステップ７０６）。
【０１４１】
本実施の形態では、廃棄の履歴９０７の長さは１にしてあるので、パケット入れ替え制御部２０３は、廃棄の履歴９０７の値「１」を、今ＩＰパケットを廃棄したフローの番号「２」で置き換える。
【０１４２】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄したフローであるＦｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量を、廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし、９０００（ｂｙｔｅ）とする（ステップ７０７）。
【０１４３】
次に、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量を廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし、３００００（ｂｙｔｅ）とする（ステップ７０８）。
【０１４４】
ここで、パケット入れ替え制御部２０３は、再度ＩＰパケット蓄積部２０４のバッファ容量とＩＰパケット蓄積部２０４の総バッファ使用量を比較する（ステップ７０１）。
【０１４５】
ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））＝ＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））なので（ステップ７０２）、これ以上ＩＰパケットを廃棄する必要はない。よって、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【０１４６】
次に、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２に計算した各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量と、ＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ７１０）。
【０１４７】
この時点で、各フローのＩＰパケット蓄積部２０４のバッファ使用状況は図１１のようになっている。
【０１４８】
次に、図１１の状態でＦｌｏｗ５のＩＰパケットが到着したとする。
【０１４９】
この場合、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２から、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量として、Ｆｌｏｗ１が１０５００（ｂｙｔｅ）、Ｆｌｏｗ２が９０００（ｂｙｔｅ）、Ｆｌｏｗ３が４５００（ｂｙｔｅ）、Ｆｌｏｗ４が１５００（ｂｙｔｅ）、Ｆｌｏｗ５が４５００（ｂｙｔｅ）、Ｆｌｏｗ６が１５００（ｂｙｔｅ）という情報を得る。また、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量として、３１５００（ｂｙｔｅ）という情報を得る（ステップ６０４）。
【０１５０】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））と、バッファ使用量管理部２０２から得たＩＰパケット蓄積部２０４の総バッファ使用量（３１５００（ｂｙｔｅ））を比較する（ステップ７０１）。
【０１５１】
この場合、ＩＰパケット蓄積部２０４のバッファ容量（３００００）＜ＩＰパケット蓄積部２０４の総バッファ使用量（３１５００）なので（ステップ７０２）、このままでは到着ＩＰパケットを格納することができない。そこで、パケット入れ替え制御部２０３は、いくつかのＩＰパケットを廃棄する。
【０１５２】
まず、パケット入れ替え制御部２０３は、閾値を計算する（ステップ７０３）。本実施の形態では閾値を各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の平均値としているので、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量３１５００（ｂｙｔｅ）をフロー数６で割り、閾値として５２５０（ｂｙｔｅ）という値を得る。
【０１５３】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄するフローの候補として、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフローを調べて、ＩＰパケット蓄積部２０４におけるバッファ使用量の多い順にソートする（ステップ７０４）。
【０１５４】
この場合、Ｆｌｏｗ１とＦｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量が閾値を超えており、二つのフローにおけるＩＰパケット蓄積部２０４のバッファ使用量は、それぞれ、１０５００（ｂｙｔｅ）と９０００（ｂｙｔｅ）である。したがって、ソート結果は、Ｆｌｏｗ１、Ｆｌｏｗ２の順になる。
【０１５５】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄する（ステップ７０５）。
【０１５６】
廃棄の履歴９０７の値は「２」であり、これは前回廃棄されたフローの番号が「２」であったということを示している。
【０１５７】
この場合、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフロー、Ｆｌｏｗ１，Ｆｌｏｗ２のうち、廃棄の履歴９０７の中にフロー番号が出てこないＦｌｏｗ１のＩＰパケットを廃棄する。
【０１５８】
ここでは、パケット入れ替え制御部２０３は、Ｆｌｏｗ１のＩＰパケット１から７のうち、ランダムに選んだ４番のＩＰパケットを廃棄するとする。
【０１５９】
次にパケット入れ替え制御部２０３は、廃棄の履歴９０７を更新する（ステップ７０６）。
【０１６０】
本実施の形態では、廃棄の履歴９０７の長さは１にしてあるので、パケット入れ替え制御部２０３は、廃棄の履歴９０７の値「２」を、今ＩＰパケットを廃棄したフローの番号「１」で置き換える。
【０１６１】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄したフローであるＦｌｏｗ１におけるＩＰパケット蓄積部２０４のバッファ使用量を、廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし９０００（ｂｙｔｅ）とする（ステップ７０７）。
【０１６２】
次に、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量を、廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし３００００（ｂｙｔｅ）とする（ステップ７０８）。
【０１６３】
ここで、パケット入れ替え制御部２０３は、再度、ＩＰパケット蓄積部２０４のバッファ容量とＩＰパケット蓄積部２０４の総バッファ使用量を比較する（ステップ７０１）。
【０１６４】
ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））＝ＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））なので（ステップ７０２）、これ以上ＩＰパケットを廃棄する必要は無い。よって、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【０１６５】
次に、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２に計算した各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量と、ＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ７１０）。
【０１６６】
この時点で、各フローのＩＰパケット蓄積部２０４のバッファ使用状況は図１２のようになっている。
【０１６７】
次に、図１２の状態でＦｌｏｗ４のＩＰパケットが到着したとする。
【０１６８】
この場合、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２から、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量として、Ｆｌｏｗ１が９０００（ｂｙｔｅ）、Ｆｌｏｗ２が９０００（ｂｙｔｅ）、Ｆｌｏｗ３が４５００（ｂｙｔｅ）、Ｆｌｏｗ４が３０００（ｂｙｔｅ）、Ｆｌｏｗ５が４５００（ｂｙｔｅ）、Ｆｌｏｗ６が１５００（ｂｙｔｅ）という情報を得る。また、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量として、３１５００（ｂｙｔｅ）という情報を得る（ステップ６０４）。
【０１６９】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））と、バッファ使用量管理部２０２から得たＩＰパケット蓄積部２０４の総バッファ使用量（３１５００（ｂｙｔｅ））を比較する（ステップ７０１）。
【０１７０】
この場合、ＩＰパケット蓄積部２０４のバッファ容量（３００００）＜ＩＰパケット蓄積部２０４の総バッファ使用量（３１５００）なので（ステップ７０２）、このままでは到着ＩＰパケットを格納することができない。そこで、パケット入れ替え制御部２０３は、いくつかのＩＰパケットを廃棄する。
【０１７１】
まず、パケット入れ替え制御部２０３は、閾値を計算する（ステップ７０３）。本実施の形態では閾値を各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の平均値としているので、ＩＰパケット蓄積部２０４の総バッファ使用量３１５００（ｂｙｔｅ）をフロー数６で割り、閾値として５２５０（ｂｙｔｅ）という値を得る。
【０１７２】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄するフローの候補として、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフローを調べて、ＩＰパケット蓄積部２０４におけるバッファ使用量の多い順にソートする（ステップ７０４）。
【０１７３】
この場合、Ｆｌｏｗ１とＦｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量が閾値を超えており、二つのフローにおけるＩＰパケット蓄積部２０４のバッファ使用量は同じである（９０００（ｂｙｔｅ））。
【０１７４】
本実施の形態では、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４におけるバッファ使用量が同じ場合にはフロー番号順にソートすることにしているので、ソート結果はＦｌｏｗ１、Ｆｌｏｗ２の順になる。
【０１７５】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄する（ステップ７０５）。廃棄の履歴９０７の値は「１」であり、これは前回廃棄されたフローの番号が「１」であったということを示している。
【０１７６】
この場合は、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフロー、Ｆｌｏｗ１，Ｆｌｏｗ２のうち、廃棄の履歴９０７の中にフロー番号が出てこないＦｌｏｗ２のＩＰパケットを廃棄する。
【０１７７】
ここでは、パケット入れ替え制御部２０３は、Ｆｌｏｗ２のＩＰパケットのうち、ランダムに選んだ２番のＩＰパケットが廃棄されたとする。
【０１７８】
次に、パケット入れ替え制御部２０３は、廃棄の履歴９０７を更新する（ステップ７０６）。
【０１７９】
本実施の形態では、廃棄の履歴９０７の長さは１にしてあるので、パケット入れ替え制御部２０３は、廃棄の履歴９０７の値「１」を、今ＩＰパケットを廃棄したフローの番号「２」で置き換える。
【０１８０】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄したフローであるＦｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量を、廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし７５００（ｂｙｔｅ）とする（ステップ７０７）。
【０１８１】
次に、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量を廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし３００００（ｂｙｔｅ）とする（ステップ７０８）。
【０１８２】
ここで、パケット入れ替え制御部２０３は、再度、ＩＰパケット蓄積部２０４のバッファ容量とＩＰパケット蓄積部２０４の総バッファ使用量を比較する（ステップ７０１）。
【０１８３】
ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））＝ＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））なので（ステップ７０２）、これ以上ＩＰパケットを廃棄する必要は無い。よって、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【０１８４】
次に、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２に計算した各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量と、ＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ７１０）。
【０１８５】
この時点で、各フローのＩＰパケット蓄積部２０４のバッファ使用状況は図１３のようになっている。
【０１８６】
次に、図１３の状態でＦｌｏｗ４のＩＰパケットが到着したとする。
【０１８７】
この場合、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２から、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量として、Ｆｌｏｗ１が９０００（ｂｙｔｅ）、Ｆｌｏｗ２が７５００（ｂｙｔｅ）、Ｆｌｏｗ３が４５００（ｂｙｔｅ）、Ｆｌｏｗ４が４５００（ｂｙｔｅ）、Ｆｌｏｗ５が４５００（ｂｙｔｅ）、Ｆｌｏｗ６が１５００（ｂｙｔｅ）という情報を得る。
【０１８８】
また、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量として、３１５００（ｂｙｔｅ）という情報を得る（ステップ６０４）。
【０１８９】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））と、バッファ使用量管理部２０２から得たＩＰパケット蓄積部２０４の総バッファ使用量（３１５００（ｂｙｔｅ））を比較する（ステップ７０１）。
【０１９０】
この場合、ＩＰパケット蓄積部２０４のバッファ容量（３００００）＜ＩＰパケット蓄積部２０４の総バッファ使用量（３１５００）なので（ステップ７０２）、このままでは到着ＩＰパケットを格納することができない。そこで、パケット入れ替え制御部２０３は、いくつかのＩＰパケットを廃棄する。
【０１９１】
まず、パケット入れ替え制御部２０３は、閾値を計算する（ステップ７０３）。
【０１９２】
本実施の形態では、パケット入れ替え制御部２０３は、閾値を各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の平均値としているので、ＩＰパケット蓄積部２０４の総バッファ使用量３１５００（ｂｙｔｅ）をフロー数６で割り、閾値として５２５０（ｂｙｔｅ）という値を得る。
【０１９３】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄するフローの候補として、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフローを調べて、ＩＰパケット蓄積部２０４におけるバッファ使用量の多い順にソートする（ステップ７０４）。
【０１９４】
この場合、Ｆｌｏｗ１とＦｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量が閾値を超えており、二つのフローにおけるＩＰパケット蓄積部２０４のバッファ使用量は、それぞれ、９０００（ｂｙｔｅ）と７５００（ｂｙｔｅ）である。したがって、ソート結果は、Ｆｌｏｗ１、Ｆｌｏｗ２の順になる。
【０１９５】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄する（ステップ７０５）。
【０１９６】
廃棄の履歴９０７の値は「２」であり、これは前回廃棄されたフローの番号が「２」であったということを示している。
【０１９７】
この場合は、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフロー、Ｆｌｏｗ１，Ｆｌｏｗ２のうち、廃棄の履歴９０７の中にフロー番号が出てこないＦｌｏｗ１のＩＰパケットを廃棄する。
【０１９８】
ここでは、パケット入れ替え制御部２０３は、Ｆｌｏｗ１のＩＰパケットのうち、ランダムに選んだ６番のＩＰパケットが廃棄されたとする。
【０１９９】
次に、パケット入れ替え制御部２０３は、廃棄の履歴９０７を更新する（ステップ７０６）。
【０２００】
本実施の形態では、パケット入れ替え制御部２０３は、廃棄の履歴９０７の長さは１にしてあるので、廃棄の履歴９０７の値「２」を、今ＩＰパケットを廃棄したフローの番号「１」で置き換える。
【０２０１】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄したフローであるＦｌｏｗ１におけるＩＰパケット蓄積部２０４のバッファ使用量を、廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし７５００（ｂｙｔｅ）とする（ステップ７０７）。
【０２０２】
次に、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量を廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし３００００（ｂｙｔｅ）とする（ステップ７０８）。
【０２０３】
ここで、パケット入れ替え制御部２０３は、再度、ＩＰパケット蓄積部２０４のバッファ容量とＩＰパケット蓄積部２０４の総バッファ使用量を比較する（ステップ７０１）。
【０２０４】
ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））＝ＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））なので（ステップ７０２）、これ以上ＩＰパケットを廃棄する必要はない。よって、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【０２０５】
次に、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２に計算した各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量と、ＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ７１０）。
【０２０６】
この時点で、各フローのＩＰパケット蓄積部２０４のバッファ使用状況は図１４のようになっている。
【０２０７】
次に、図１４の状態でＦｌｏｗ２のＩＰパケットが受信端末１０３に向けて転送されたとする。
【０２０８】
この場合、ＩＰパケット転送部２０５が、Ｆｌｏｗ２の１番のＩＰパケットを受信端末１０３に転送する（ステップ８０１）。
【０２０９】
次に、ＩＰパケット転送部２０５は、バッファ使用量管理部２０２に、転送されたＩＰパケットのフロー番号として「２」という情報と、ＩＰパケットのデータ量として「１５００（ｂｙｔｅ）」という情報を送る（ステップ８０２）。
【０２１０】
次に、バッファ使用量管理部２０２は、ＩＰパケット転送部２０５から得た、フロー番号「２」という情報と、ＩＰパケットのデータ量「１５００（ｂｙｔｅ）」という情報をもとに、Ｆｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量を１５００（ｂｙｔｅ）減らして６０００（ｂｙｔｅ）とし、ＩＰパケット蓄積部２０４の総バッファ使用量を１５００（ｂｙｔｅ）減らして２８５００（ｂｙｔｅ）とする（ステップ８０３）。
【０２１１】
この時点でＩＰパケット蓄積部２０４のバッファの使用状況は図１５のようになっている。
【０２１２】
次に、図１５の状態でＦｌｏｗ４のＩＰパケットが到着したとする。
【０２１３】
この場合、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２から、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量として、Ｆｌｏｗ１が７５００（ｂｙｔｅ）、Ｆｌｏｗ２が６０００（ｂｙｔｅ）、Ｆｌｏｗ３が４５００（ｂｙｔｅ）、Ｆｌｏｗ４が６０００（ｂｙｔｅ）、Ｆｌｏｗ５が４５００（ｂｙｔｅ）、Ｆｌｏｗ６が１５００（ｂｙｔｅ）という情報を得る。また、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量として、３００００（ｂｙｔｅ）という情報を得る（ステップ６０４）。
【０２１４】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））と、バッファ使用量管理部２０２から得たＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））を比較する（ステップ７０１）。
【０２１５】
この場合、ＩＰパケット蓄積部２０４のバッファ容量（３００００）＝ＩＰパケット蓄積部２０４の総バッファ使用量（３００００）であり（ステップ７０２）、到着ＩＰパケットを格納するだけの空き容量がある。よって、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【０２１６】
次に、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２に各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量とＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ７１０）。
【０２１７】
この時点で、各フローのＩＰパケット蓄積部２０４のバッファ使用状況は図１６のようになっている。
【０２１８】
次に、図１６の状態でＦｌｏｗ６のＩＰパケットが到着したとする。
【０２１９】
この場合、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２から、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量として、Ｆｌｏｗ１が７５００（ｂｙｔｅ）、Ｆｌｏｗ２が６０００（ｂｙｔｅ）、Ｆｌｏｗ３が４５００（ｂｙｔｅ）、Ｆｌｏｗ４が６０００（ｂｙｔｅ）、Ｆｌｏｗ５が４５００（ｂｙｔｅ）、Ｆｌｏｗ６が３０００（ｂｙｔｅ）という情報を得る。また、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量として、３１５００（ｂｙｔｅ）という情報を得る（ステップ６０４）。
【０２２０】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））と、バッファ使用量管理部２０２から得たＩＰパケット蓄積部２０４の総バッファ使用量（３１５００（ｂｙｔｅ））を比較する（ステップ７０１）。
【０２２１】
この場合、ＩＰパケット蓄積部２０４のバッファ容量（３００００）＜ＩＰパケット蓄積部２０４の総バッファ使用量（３１５００）なので（ステップ７０２）、このままでは到着ＩＰパケットを格納することができない。そこで、パケット入れ替え制御部２０３は、いくつかのＩＰパケットを廃棄する。
【０２２２】
まず、パケット入れ替え制御部２０３は閾値を計算する（ステップ７０３）。本実施の形態では閾値を各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の平均値としているので、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量３１５００（ｂｙｔｅ）をフロー数６で割り、閾値として５２５０（ｂｙｔｅ）という値を得る。
【０２２３】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄するフローの候補として、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフローを調べて、ＩＰパケット蓄積部２０４におけるバッファ使用量の多い順にソートする（ステップ７０４）。この場合、Ｆｌｏｗ１とＦｌｏｗ２、及び、Ｆｌｏｗ４におけるＩＰパケット蓄積部２０４のバッファ使用量が閾値を超えており、三つのフローにおけるＩＰパケット蓄積部２０４のバッファ使用量は、それぞれ、７５００（ｂｙｔｅ）、６０００（ｂｙｔｅ）、６０００（ｂｙｔｅ）である。
【０２２４】
本実施の形態では、ＩＰパケット蓄積部２０４におけるバッファ使用量が同じ場合にはフロー番号順にソートすることにしているので、ソート結果は、Ｆｌｏｗ１、Ｆｌｏｗ２、Ｆｌｏｗ４の順になる。
【０２２５】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄する（ステップ７０５）。
【０２２６】
廃棄の履歴９０７の値は「１」であり、これは前回廃棄されたフローの番号が「１」であったということを示している。
【０２２７】
この場合は、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフロー、Ｆｌｏｗ１，Ｆｌｏｗ２、Ｆｌｏｗ４のうち、廃棄の履歴９０７の中にフロー番号が出てこないＦｌｏｗ２、Ｆｌｏｗ４のどちらかのフローのＩＰパケットを廃棄する。
【０２２８】
この場合は、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４におけるバッファ使用量の多い順にＩＰパケットを廃棄するので、Ｆｌｏｗ２のＩＰパケットを廃棄する。
【０２２９】
ここでは、パケット入れ替え制御部２０３は、Ｆｌｏｗ２のＩＰパケットのうち、ランダムに選んだ４番のＩＰパケットが廃棄されたとする。
【０２３０】
次にパケット入れ替え制御部２０３は、廃棄の履歴９０７を更新する（ステップ７０６）。
【０２３１】
本実施の形態では、パケット入れ替え制御部２０３は、廃棄の履歴９０７の長さは１にしてあるので、廃棄の履歴９０７の値「１」を、今ＩＰパケットを廃棄したフロー番号「２」で置き換える。
【０２３２】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄したフローであるＦｌｏｗ２におけるＩＰパケット蓄積部２０４のバッファ使用量を、廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし４５００（ｂｙｔｅ）とする（ステップ７０７）。次に、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量を廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし３００００（ｂｙｔｅ）とする（ステップ７０８）。
【０２３３】
ここで、パケット入れ替え制御部２０３は、再度、ＩＰパケット蓄積部２０４のバッファ容量とＩＰパケット蓄積部２０４の総バッファ使用量を比較する（ステップ７０１）。
【０２３４】
ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））＝ＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））なので（ステップ７０２）、これ以上ＩＰパケットを廃棄する必要はない。よって、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【０２３５】
次に、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２に計算した各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量と、ＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ７１０）。この時点で、パケット入れ替え制御部２０３は、各フローのＩＰパケット蓄積部２０４のバッファ使用状況は図１７のようになっている。
【０２３６】
次に、図１７の状態でＦｌｏｗ６のＩＰパケットが到着したとする。
【０２３７】
この場合、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２から、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量として、Ｆｌｏｗ１が７５００（ｂｙｔｅ）、Ｆｌｏｗ２が４５００（ｂｙｔｅ）、Ｆｌｏｗ３が４５００（ｂｙｔｅ）、Ｆｌｏｗ４が６０００（ｂｙｔｅ）、Ｆｌｏｗ５が４５００（ｂｙｔｅ）、Ｆｌｏｗ６が４５００（ｂｙｔｅ）という情報を得る。また、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量として、３１５００（ｂｙｔｅ）という情報を得る（ステップ６０４）。
【０２３８】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４のバッファに十分な空き容量があるかどうか確認するため、ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））と、バッファ使用量管理部２０２から得たＩＰパケット蓄積部２０４の総バッファ使用量（３１５００（ｂｙｔｅ））を比較する（ステップ７０１）。この場合、ＩＰパケット蓄積部２０４のバッファ容量（３００００）＜ＩＰパケット蓄積部２０４の総バッファ使用量（３１５００）なので、このままでは到着ＩＰパケットを格納することができない。そこで、パケット入れ替え制御部２０３は、いくつかのＩＰパケットを廃棄する。
【０２３９】
まず、パケット入れ替え制御部２０３は閾値を計算する（ステップ７０３）。本実施の形態では、閾値を各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の平均値としているので、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量３１５００（ｂｙｔｅ）をフロー数６で割り、閾値として５２５０（ｂｙｔｅ）という値を得る。
【０２４０】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄するフローの候補として、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフローを調べて、ＩＰパケット蓄積部２０４におけるバッファ使用量の多い順にソートする（ステップ７０４）。
【０２４１】
この場合、Ｆｌｏｗ１とＦｌｏｗ４におけるＩＰパケット蓄積部２０４のバッファ使用量が閾値を超えており、二つのフローにおけるＩＰパケット蓄積部２０４のバッファ使用量は、それぞれ、７５００（ｂｙｔｅ）と６０００（ｂｙｔｅ）である。したがって、ソート結果は、Ｆｌｏｗ１、Ｆｌｏｗ４の順になる。
【０２４２】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄する（ステップ７０５）。
【０２４３】
廃棄の履歴９０７の値は「２」であり、これは前回廃棄されたフローの番号が「２」であったということを示している。
【０２４４】
パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４におけるバッファ使用量が閾値を超えているフロー、Ｆｌｏｗ１，Ｆｌｏｗ４はどちらも廃棄の履歴９０７の中にないので、二つのフローのうち、ＩＰパケット蓄積部２０４におけるバッファ使用量の多いＦｌｏｗ１のＩＰパケットを廃棄する。
【０２４５】
ここでは、パケット入れ替え制御部２０３は、Ｆｌｏｗ１のＩＰパケットのうち、ランダムに選んだ３番のＩＰパケットが廃棄されたとする。
【０２４６】
次に、パケット入れ替え制御部２０３は、廃棄の履歴９０７を更新する（ステップ７０６）。
【０２４７】
本実施の形態では、廃棄の履歴９０７の長さは１にしてあるので、パケット入れ替え制御部２０３は、廃棄の履歴９０７の値「２」を、今ＩＰパケットを廃棄したフロー番号「１」で置き換える。
【０２４８】
次に、パケット入れ替え制御部２０３は、ＩＰパケットを廃棄したフローであるＦｌｏｗ１におけるＩＰパケット蓄積部２０４のバッファ使用量を、廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし６０００（ｂｙｔｅ）とする（ステップ７０７）。
【０２４９】
次に、パケット入れ替え制御部２０３は、ＩＰパケット蓄積部２０４の総バッファ使用量を廃棄したＩＰパケットのデータ量分（１５００（ｂｙｔｅ））減らし３００００（ｂｙｔｅ）とする（ステップ７０８）。
【０２５０】
ここで、パケット入れ替え制御部２０３は、再度、ＩＰパケット蓄積部２０４のバッファ容量とＩＰパケット蓄積部２０４の総バッファ使用量を比較する（ステップ７０１）。
【０２５１】
ＩＰパケット蓄積部２０４のバッファ容量（３００００（ｂｙｔｅ））＝ＩＰパケット蓄積部２０４の総バッファ使用量（３００００（ｂｙｔｅ））なので（ステップ７０２）、これ以上ＩＰパケットを廃棄する必要はない。よって、パケット入れ替え制御部２０３は、到着ＩＰパケットをＩＰパケット蓄積部２０４に格納する（ステップ７０９）。
【０２５２】
次に、パケット入れ替え制御部２０３は、バッファ使用量管理部２０２に計算した各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量と、ＩＰパケット蓄積部２０４の総バッファ使用量を送る（ステップ９１０）。
【０２５３】
この時点で、各フローのＩＰパケット蓄積部２０４のバッファ使用状況は図１８のようになっている。
【０２５４】
以上説明したように、上記実施の形態によれば、ＩＰパケット蓄積部２０４のバッファ容量を可能な限り使いきることができる。そのため、ネットワーク資源を有効に利用することができる。
【０２５５】
また、上記実施の形態によれば、ＩＰパケット蓄積部２０４のバッファ容量に空き容量がない場合には、バッファの使用量の多いフローのデータを削除するようにできる。これにより、バッファ使用量の少ないフローがバッファを使用できるようになるので、各フローにおけるＩＰパケット蓄積部２０４のバッファ使用量の公平性を高めることができる。この結果、複数のフローが公平に帯域を利用するベストエフォートサービスを提供できる。
【０２５６】
また、上記実施の形態によれば、同一のフローの連続したデータを連続して削除することを抑えることができる。これにより、フローがＴＣＰフローであっても、ＴＣＰフローのスループットの極端な低下も抑えることができるので、結果として各フローのスループットの公平性を向上させることができる。
【０２５７】
さらに、上記実施の形態によれば、複数のクラスに対して、一つのＩＰパケット蓄積部２０４のキュー（バッファ）でも対応することが可能であり、収容するフローの数が多くなった場合でもキューの数を増やすことなく処理することが可能である。
【０２５８】
なお、上述した中継装置１０２が備える各処理部の処理を専用のハードウェアで実現しても、各処理部の処理をプログラムにし記憶媒体に格納し、汎用のコンピュータに記憶媒体に格納したプログラムを読み込ませ実行させる形態であっても良い。
【０２５９】
【発明の効果】
以上説明したように、本発明によれば、到着ＩＰパケットを可能な限り格納し、必要に応じて複数のフローからＩＰパケットを離散的に廃棄することによって、ネットワーク資源を可能な限り有効利用しつつ、ＴＣＰフローのスループットの極端な低下を防ぎつつ、各フローのスループットを公平にすることができる。
【図面の簡単な説明】
【図１】本発明の一実施の形態における中継装置の実施例の構成図
【図２】上記実施の形態におけるＩＰパケット蓄積管理部の構成図
【図３】上記実施の形態におけるトラヒック量制御部のＩＰパケット受信時の動作を説明するためのフローチャート
【図４】上記実施の形態におけるＩＰパケット振り分け部の動作を説明するためのフローチャート
【図５】上記実施の形態におけるフロー検出部の動作を説明するためのフローチャート
【図６】上記実施の形態におけるバッファ使用量管理部の動作を説明するためのフローチャート
【図７】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのフローチャート
【図８】上記実施の形態におけるＩＰパケット転送部のＩＰパケット転送時の動作を説明するためのフローチャート
【図９】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第１の図
【図１０】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第２の図
【図１１】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第３の図
【図１２】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第４の図
【図１３】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第５の図
【図１４】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第６の図
【図１５】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第７の図
【図１６】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第８の図
【図１７】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第９の図
【図１８】上記実施の形態におけるパケット入れ替え制御部の動作を説明するためのＩＰパケット蓄積部の状態を示す第１０の図
【符号の説明】
１０１  送信端末
１０２  中継装置
１０３  受信端末
１０４  ＩＰパケット振り分け部
１０５  ＩＰパケット蓄積管理部
２００  トラヒック量制御部
２０１  フロー検出部
２０２  バッファ使用量管理部
２０３  パケット入れ替え制御部
２０４  ＩＰパケット蓄積部
２０５  ＩＰパケット転送部
【図１】
2004266561.tif 000003
【図２】
2004266561.tif 000004
【図３】
2004266561.tif 000005
【図４】
2004266561.tif 000006
【図５】
2004266561.tif 000007
【図６】
2004266561.tif 000008
【図７】
2004266561.tif 000009
【図８】
2004266561.tif 000010
【図９】
2004266561.tif 000011
【図１０】
2004266561.tif 000012
【図１１】
2004266561.tif 000013
【図１２】
2004266561.tif 000014
【図１３】
2004266561.tif 000015
【図１４】
2004266561.tif 000016
【図１５】
2004266561.tif 000017
【図１６】
2004266561.tif 000018
【図１７】
2004266561.tif 000019
【図１８】
2004266561.tif 000020