(57)【要約】【課題】ＤＲＲを用いたネットワークおいても、ＥＣＮをサポートしているフローがＥＣＮのメリット（低いパケットロス率）を享受することが可能なルータの選択的パケット廃棄およびマーキング法を提供する。【解決手段】パケットが到着した時、全体のキュー長に到着したパケットのサイズを加算したものが予め定めたしきい値以上、かつ、バッファサイズ以下のときに、キュー長が最大のフローを調べ、そのフロー用のバッファに格納されているパケットを１つ選択し、当該選択したパケットのＥＣＴビットがセットされているか否かを調べ、ＥＣＴビットがセットされていれば、当該選択したパケットのＣＥビットがセットされているか否かを調べ、ＣＥビットがセットされていれば、確率ＰでＣＥビットをセットし、ＣＥビットがセットされていなければ、確率Ｐでそのパケットを廃棄する。【選択図】        図３
2004357177.tif 000002
【特許請求の範囲】
【請求項１】
フロー毎にバッファが用意されているフロー毎キューイング法を実行するルータの輻輳制御方法であって、
パケットが到着した時、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断するステップ１と、
前記ステップ１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下の場合に、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きいか否かを判断するステップ２と、
前記ステップ２において、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きい場合に、キュー長が最大のフローを検索するステップ３と、
前記ステップ３で検索したフロー用のバッファに格納されているパケットを１つ選択するステップ４と、
前記ステップ４で選択したパケットのＥＣＴビットがセットされているか否かを検索するステップ５と、
前記ステップ５において、前記選択したパケットのＥＣＴビットがセットされている場合に、前記選択したパケットのＣＥビットがセットされているか否かを検索するステップ６と、
前記ステップ６において、前記選択したパケットのＣＥビットがセットされていない場合に、確率Ｐで前記選択したパケットにＣＥビットをセットするステップ７と、
前記ステップ５において、前記選択したパケットのＥＣＴビットがセットされていない場合に、確率Ｐで前記選択したパケットを廃棄するステップ８と、
前記ステップ２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記ステップ６において前記選択したパケットのＣＥビットがセットされている場合、または、前記ステップ７で確率Ｐで前記選択したパケットにＣＥビットをセットした後、あるいは、前記ステップ８で確率Ｐで前記選択したパケットを廃棄した後に、前記到着したパケットを送信したフロー用のバッファに入力するステップ９とを備えることを特徴とするルータの輻輳制御方法。
【請求項２】
前記ステップ１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きい場合に、キュー長が最大のフローを検索するステップ１１と、
前記ステップ１１で検索したフロー用のバッファに格納されているパケットを１つ選択し、当該選択したパケットを廃棄するステップ１２と、
全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断するステップ１３と、
前記ステップ１３において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きい場合に、前記ステップ１１ないしステップ１３の処理を繰り返すステップ１４と、
前記ステップ１４において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下の場合に、前記到着したパケットを送信したフロー用のバッファに入力するステップ１５とを備えることを特徴とする請求項１に記載のルータの輻輳制御方法。
【請求項３】
前記ステップ８が省略され、
前記ステップ９は、前記ステップ２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記ステップ５において前記選択したパケットのＥＣＴビットがセットされていない場合、または、前記ステップ６において、前記選択したパケットのＣＥビットがセットされている場合、あるいは、前記ステップ７で確率Ｐで前記選択したパケットにＣＥビットをセットした後に、前記到着したパケットを送信したフロー用のバッファに入力するステップであることを特徴とする請求項１または請求項２に記載のルータの輻輳制御方法。
【請求項４】
フロー毎にバッファが用意されているフロー毎キューイング法を実行するルータの輻輳制御方法であって、
パケットが到着した時、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断するステップ１と、
前記ステップ１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下の場合に、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きいか否かを判断するステップ２と、
前記ステップ２において、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きい場合に、キュー長からフロー毎に用意されている変数ＭＢを減算したものが最大のフローを検索するステップ３と、
前記ステップ３で検索されたフロー用のバッファに格納されているパケットを１つ選択するステップ４と、
前記ステップ４で選択したパケットのＥＣＴビットがセットされているか否かを検索するステップ５と、
前記ステップ５において、前記選択したパケットのＥＣＴビットがセットされている場合に、前記選択したパケットのＣＥビットがセットされているか否かを検索するステップ６と、
前記ステップ６において、前記選択したパケットのＣＥビットがセットされていない場合に、確率Ｐで前記選択したパケットにＣＥビットをセットし、前記ＣＥビットをセットしたパケットを有するフローの変数ＭＢに前記ＣＥビットをセットしたパケットのサイズを加算するステップ７と、
前記ステップ５において、前記選択したパケットのＥＣＴビットがセットされていない場合に、確率Ｐで前記選択したパケットを廃棄するステップ８と、
前記ステップ２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記ステップ６において前記選択したパケットのＣＥビットがセットされている場合、または、前記ステップ７で確率Ｐで前記選択したパケットにＣＥビットをセットした後、あるいは、前記ステップ８で確率Ｐで前記選択したパケットを廃棄した後に、前記到着したパケットを送信したフロー用のバッファに入力するステップ９と、
パケットが出力されたとき、出力されたパケットのＣＥビットがセットされている場合に、前記出力されたパケットを有するフローの変数ＭＢから前記出力されたパケットのサイズを減算するステップ１０とを備えることを特徴とするルータの輻輳制御方法。
【請求項５】
前記ステップ１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きい場合に、キュー長からフロー毎に用意されている変数ＭＢを減算したものが最大のフローを検索するステップ１１と、
前記ステップ１１で検索したフロー用のバッファに格納されているパケットを１つ選択し、当該選択したパケットを廃棄するステップ１２と、
前記ステップ１２で廃棄したパケットのＥＣＴビットがセットされているか否かを検索するステップ１３と、
前記ステップ１３において、前記廃棄されたパケットのＥＣＴビットがセットされている場合に、前記廃棄したパケットのＣＥビットがセットされているか否かを検索するステップ１４と、
前記ステップ１４において、前記廃棄したパケットのＣＥビットがセットされている場合に、廃棄したパケットを有するフローの変数ＭＢから前記廃棄したパケットのサイズを減算するステップ１５と、
前記ステップ１３において前記廃棄したパケットのＥＣＴビットがセットされていない場合、または、前記ステップ１４において前記廃棄したパケットのＣＥビットがセットされていない場合、あるいは、前記ステップ１５で前記廃棄したパケットを有するフローの変数ＭＢから前記廃棄したパケットのサイズを減算した後に、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断するステップ１６と、
前記ステップ１６において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きい場合に、前記ステップ１１ないしステップ１６の処理を繰り返すステップ１７と、
前記ステップ１６において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下の場合に、前記到着したパケットを送信したフロー用のバッファに入力するステップ１８とを備えることを特徴とする請求項４に記載のルータの輻輳制御方法。
【請求項６】
前記ステップ８が省略され、
前記ステップ９は、前記ステップ２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記ステップ５において選択したパケットのＥＣＴビットがセットされていない場合、または、前記ステップ６において選択したパケットのＣＥビットがセットされている場合、あるいは、前記ステップ７で確率Ｐで前記選択したパケットにＣＥビットをセットした後に、前記到着したパケットを送信したフロー用のバッファに入力するステップであることを特徴とする請求項４または請求項５に記載のルータの輻輳制御方法。
【請求項７】
到着したパケットのサイズ情報を読み取るパケットサイズ読み取り部と、
各フロー毎のバッファを有し、パケットを格納するバッファ部と、
全体のキュー長、および、フロー毎のキュー長を測定するキュー長測定部と、
前記パケットサイズ読み取り部、および、前記キュー長測定部から情報を受け取り、どのパケットを選択的廃棄およびマーキングするかを決定する判定部とを備え、フロー毎にバッファが用意されているフロー毎キューイング法を実行するルータであって、
前記判定部は、パケットが到着した時、前記パケットサイズ読み取り部、および、前記キュー長測定部から情報に基づき、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断する手段１と、
前記手段１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下の場合に、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きいか否かを判断する手段２と、
前記手段２において、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きい場合に、キュー長が最大のフローを検索する手段３と、
前記手段３で検索したフロー用のバッファに格納されているパケットを１つ選択する手段４と、
前記手段４で選択したパケットのＥＣＴビットがセットされているか否かを検索する手段５と、
前記手段５において、前記選択したパケットのＥＣＴビットがセットされている場合に、前記選択したパケットのＣＥビットがセットされているか否かを検索する手段６と、
前記手段６において、前記選択したパケットのＣＥビットがセットされていない場合に、確率Ｐで前記選択したパケットにＣＥビットをセットする手段７と、
前記手段５において、前記選択したパケットのＥＣＴビットがセットされていない場合に、確率Ｐで前記選択したパケットを廃棄する手段８と、
前記手段２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記手段６において前記選択したパケットのＣＥビットがセットされている場合、または、前記手段７で確率Ｐで前記選択したパケットにＣＥビットをセットした後、あるいは、前記手段８で確率Ｐで前記選択したパケットを廃棄した後に、前記到着したパケットを送信したフロー用のバッファに入力する手段９とを有することを特徴とするルータ。
【請求項８】
前記判定部は、前記手段１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きい場合に、キュー長が最大のフローを検索する処理１と、前記処理１で検索したフロー用のバッファに格納されているパケットを１つ選択し、当該選択したパケットを廃棄する処理２と、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断する処理３とを、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下になるまで繰り返す手段１１と、
前記手段１１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下になった場合に、前記到着したパケットを送信したフロー用のバッファに入力する手段１２とを有することを特徴とする請求項７に記載のルータ。
【請求項９】
前記判定部の前記手段８が省略され、
前記前記判定部の手段９は、前記手段２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記手段５において前記選択したパケットのＥＣＴビットがセットされていない場合、または、前記手段６において前記選択したパケットのＣＥビットがセットされている場合、あるいは、前記手段７で確率Ｐで前記選択したパケットにＣＥビットをセットした後に、前記到着したパケットを送信したフロー用のバッファに入力する手段であることを特徴とする請求項７または請求項８に記載のルータ。
【請求項１０】
到着したパケットのサイズ情報を読み取るパケットサイズ読み取り部と、
各フロー毎のバッファを有し、パケットを格納するバッファ部と、
全体のキュー長、および、フロー毎のキュー長を測定するキュー長測定部と、
前記パケットサイズ読み取り部、および前記キュー長測定部から情報を受け取り、どのパケットを選択的廃棄およびマーキングするかを決定する判定部と、
前記バッファ部からパケットが出力されたとき、出力されたパケットのＣＥビットがセットされている場合に、前記出力されたパケットを有するフローのフロー識別子と前記出力されたパケットのサイズを前記判定部に通知する送信監視部とを備え、フロー毎にバッファが用意されているフロー毎キューイング法を実行するルータであって、
前記判定部は、パケットが到着した時、前記パケットサイズ読み取り部、および前記キュー長測定部から情報に基づき、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断する手段１と、
前記手段１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下の場合に、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きいか否かを判断する手段２と、
前記手段２において、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きい場合に、キュー長からフロー毎に用意されている変数ＭＢを減算したものが最大のフローを検索する手段３と、
前記手段５で検索したフロー用のバッファに格納されているパケットを１つ選択する手段４と、
前記手段４で選択したパケットのＥＣＴビットがセットされているか否かを検索する手段５と、
前記手段５において、前記選択したパケットのＥＣＴビットがセットされている場合に、前記選択したパケットのＣＥビットがセットされているか否かを検索する手段６と、
前記手段６において、前記選択したパケットのＣＥビットがセットされていない場合に、確率Ｐで前記選択したパケットにＣＥビットをセットし、前記ＣＥビットをセットしたパケットを有するフローの変数ＭＢに前記ＣＥビットをセットしたパケットのサイズを加算する手段７と、
前記手段７において、前記選択したパケットのＥＣＴビットがセットされていない場合に、確率Ｐで前記選択したパケットを廃棄する手段８と、
前記手段２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記手段６において前記選択したパケットのＣＥビットがセットされている場合、または、前記手段７で確率Ｐで前記選択したパケットにＣＥビットをセットした後、あるいは、前記手段８で確率Ｐで前記選択したパケットを廃棄した後に、前記到着したパケットを送信したフロー用のバッファに入力する手段９と、
前記送信監視部からの通知に基づき、通知されたフロー識別子に対応するフローの変数ＭＢから前記通知されたパケットのサイズを減算する手段１０とを有することを特徴とするルータ。
【請求項１１】
前記判定部は、前記手段１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きい場合に、キュー長からフロー毎に用意されている変数ＭＢを減算したものが最大のフローを検索する処理１と、前記処理１で検索したフロー用のバッファに格納されているパケットを１つ選択し、当該選択したパケットを廃棄する処理２と、前記処理２で廃棄したパケットのＥＣＴビットがセットされているか否かを検索する処理３と、前記処理３において前記廃棄したパケットのＥＣＴビットがセットされている場合に、前記廃棄したパケットのＣＥビットがセットされているか否かを検索する処理４と、前記処理４において前記廃棄したパケットのＣＥビットがセットされている場合に、前記廃棄したパケットを有するフロー変数ＭＢから前記廃棄したパケットのサイズを減算する処理５と、前記処理３において前記廃棄したパケットのＥＣＴビットがセットされていない場合、または、前記処理４において前記廃棄したパケットのＣＥビットがセットされていない場合、あるいは、前記処理５で前記廃棄したパケットを有するフロー変数ＭＢから前記廃棄したパケットのサイズを減算した後に、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断する処理６とを、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下になるまで繰り返す手段１１と、
前記手段１１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下になった場合に、前記到着したパケットを送信したフロー用のバッファに入力する手段１２とを有することを特徴とする請求項１０に記載のルータ。
【請求項１２】
到着したパケットのサイズ情報を読み取るパケットサイズ読み取り部と、
各フロー毎のバッファを有し、パケットを格納するバッファ部と、
全体のキュー長、および、フロー毎のキュー長を測定するキュー長測定部と、
フロー毎に変数ＭＢを管理する情報管理部と、
前記バッファ部からパケットが出力されたとき、出力されたパケットのＣＥビットがセットされている場合に、前記出力されたパケットを有するフローのフロー識別子と前記出力されたパケットのサイズを前記情報管理部に通知する送信監視部と、
前記パケットサイズ読み取り部、前記キュー長測定部、および前記情報管理部から情報を受け取り、どのパケットを選択的廃棄およびマーキングするかを決定する判定部とを備え、フロー毎にバッファが用意されているフロー毎キューイング法を実行するルータであって、
前記判定部は、パケットが到着した時、前記パケットサイズ読み取り部、前記キュー長測定部、および前記情報管理部から情報に基づき、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断する手段１と、
前記手段１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下の場合に、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きいか否かを判断する手段２と、
前記手段２において、全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値より大きい場合に、キュー長からフロー毎に用意されている変数ＭＢを減算したものが最大のフローを検索する手段３と、
前記手段３で検索したフロー用のバッファに格納されているパケットを１つ選択する手段４と、
前記手段４で選択したパケットのＥＣＴビットがセットされているか否かを検索する手段５と、
前記手段５において、前記選択したパケットのＥＣＴビットがセットされている場合に、前記選択したパケットのＣＥビットがセットされているか否かを検索する手段６と、
前記手段６において、前記選択したパケットのＣＥビットがセットされていない場合に、確率Ｐで前記選択したパケットにＣＥビットをセットし、前記ＣＥビットをセットしたパケットを有するフローのフロー識別子と前記ＣＥビットをセットしたパケットのサイズを前記情報管理部に通知する手段７と、
前記手段５において、前記選択したパケットのＥＣＴビットがセットされていない場合に、確率Ｐで前記選択したパケットを廃棄する手段８と、
前記手段２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記手段６において前記選択したパケットのＣＥビットがセットされている場合、または、前記手段７で確率Ｐで前記選択したパケットにＣＥビットをセットした後、あるいは、前記手段８で確率Ｐで前記選択したパケットを廃棄した後に、前記到着したパケットを送信したフロー用のバッファに入力する手段９とを有し、
前記情報管理部は、前記送信監視部からの通知に基づき、通知されたフロー識別子に対応するフローの変数ＭＢから前記通知されたパケットのサイズを減算する減算手段と、
前記判定部における前記手段７からの通知に基づき、通知されたフロー識別子に対応するフローの変数ＭＢに前記通知されたパケットのサイズを加算する加算手段とを有することを特徴とする記載のルータ。
【請求項１３】
前記判定部は、前記手段１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きい場合に、キュー長からフロー毎に用意されている変数ＭＢを減算したものが最大のフローを検索する処理１と、前記処理１で検索したフロー用のバッファに格納されているパケットを１つ選択し、当該選択したパケットを廃棄する処理２と、前記処理２で廃棄したパケットのＥＣＴビットがセットされているか否かを検索する処理３と、前記処理３において前記廃棄したパケットのＥＣＴビットがセットされている場合に、前記廃棄したパケットのＣＥビットがセットされているか否かを検索する処理４と、前記処理４において前記廃棄したパケットのＣＥビットがセットされている場合に、前記廃棄したパケットを有するフローのフロー識別子と前記廃棄したパケットのサイズを前記情報管理部に通知する処理５と、前記処理３において前記廃棄したパケットのＥＣＴビットがセットされていない場合、または、前記処理４において前記廃棄したパケットのＣＥビットがセットされていない場合、あるいは、前記処理５で前記情報管理部に通知した後に、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズより大きいか否かを判断する処理６とを、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下になるまで繰り返す手段１１と、
前記手段１１において、全体のキュー長に前記到着したパケットのサイズを加算したものがバッファサイズ以下になった場合に、前記到着したパケットを送信したフロー用のバッファに入力する手段１２とを有し、
前記情報管理部の減算手段は、前記判定部における前記手段１１からの通知に基づき、通知されたフロー識別子に対応するフローの変数ＭＢから前記通知されたパケットのサイズを減算することを特徴とする請求項１２に記載のルータ。
【請求項１４】
前記判定部の手段８が省略され、
前記判定部の手段９は、前記手段２において全体のキュー長に前記到着したパケットのサイズを加算したものが予め定めたしきい値以下の場合、または、前記手段５において選択したパケットのＥＣＴビットがセットされていない場合、または、前記手段６において前記選択したパケットのＣＥビットがセットされている場合、あるいは、前記手段７で確率Ｐで前記選択したパケットにＣＥビットをセットした後に、前記到着したパケットを送信したフロー用のバッファに入力する手段であることを特徴とする請求項１０ないし請求項１３のいずれか１項に記載のルータ。
【請求項１５】
前記請求項１ないし請求項６のいずれか１項に記載の輻輳制御方法を、コンピュータに実行させるためのプログラム。
【請求項１６】
前記請求項１５に記載のプログラムが記録された記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ルータ、ルータの輻輳制御方法、プログラムおよび記録媒体に係り、特に、フロー毎キューイングを実装するルータにおいて、輻輳が発生したときにパケットを選択的に廃棄およびマーキングする技術に関する。また、ＥＣＮをサポートしたフローのパケットをどのように選択的に廃棄およびマーキングするかに関する。また、ホームネットワークで用いられるホームゲートウェイにおける輻輳制御技術に関する。
【０００２】
【従来の技術】
ＩＰ技術を用いた網では、電話網とは異なり、ベストエフォートサービスが主流である。ベストエフオートサービスでは、通信を行っているフロー間で、利用可能な帯域を公平に分配することが必要不可欠である。
帯域を公平に分配する技術として、フロー毎にバッファを用意するフロー毎キューイング法（ｐｅｒ−ｆｌｏｗ  ｑｕｅｕｉｎｇ）がある。特に、ホームネットワークでは、商用のＩＰネットワークに比べて扱うフロー数が少ないので、フロー毎キューイング法の適用先として有望である。
現在、多くのルータは、フロー毎キューイング法として、ＤＲＲ（Ｄｅｆｉｃｉｔ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）を実装している（下記、非特許文献１参照）。
図１６は、ＤＲＲ（Ｄｅｆｉｃｉｔ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）における選択的パケット廃棄法を説明するためのフローチャートである。
以下、図１６を用いて、ＤＲＲにおける選択的パケット廃棄法を説明する。
ＤＲＲでは、パケットが到着した時（ステップ１９０）、到着したパケットのヘッダからそのパケットを送出したフローの識別子を調べ、次に、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファ部のバッファサイズ（以下、単に、バッファサイズという）より大きいかを調べる（ステップ１９１）。
【０００３】
ステップ１９１でＮｏ（全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズ以下）ならば、到着したパケットを送信したフロー用のバッファに到着したパケットを入力する（ステップ１９５）。
ステップ１９１でＹｅｓ（全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズより大きい）ならば、キュー長が最大のフローを調べ（ステップ１９２）、そのフロー用のバッファに格納されているパケットを１つ選択し、選択したパケットを廃棄する（ステップ１９３）。
次に、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズより大きいかを調べ（ステップ１９４）、ステップ１９４でＹｅｓの場合は、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズ以下になるまで、前述のステップ１９２、１９３を繰り返す。
また、ステップ１９４でＮｏの場合はステップ１９５に進み、到着したパケットを送信したフロー用のバッファに到着したパケットを入力する。
【０００４】
図１６を用いて説明したＤＲＲにおける選択的パケット廃棄法を、図１７を用いて具体的に説明する。
図１７では、全てのパケットのサイズが１０００バイト、バッファサイズが６０００バイト、フロー１用のバッファ３ａにはパケットが１つ、フロー２用のバッファ３ｂにはパケットが１つ、フロー３用のバッファ３ｃにはパケットが３つあるものする。また、今後、フロー１のパケットが２つ到着するものとする。
まず、１つ目のパケットが到着すると、まず、全体のキュー長に到着したパケットのサイズを加算したものが、バッファ部３のバッファサイズより大きいかを調べる。
図１７では、全体のキュー長が５０００（＝１０００＋１０００＋３０００）バイト、到着したパケットのサイズが１０００バイト、バッファサイズが６０００バイトなので、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズ以下である。
よって、フロー１用のバッファ３ａに到着したパケットを入力する。この時点で、フロー１用のバッファ３ａにはパケットが２つ存在することになる。
【０００５】
次に、２つ目のパケットが到着すると、全体のキュー長が６０００（＝２０００＋１０００＋３０００）バイト、到着したパケットのサイズが１０００バイト、バッファサイズが６０００バイトなので、全体のキュー長に到着したパケットのサイズを加算したものが、バッファサイズより大きい。よって、キュー長が最大のフローを調べることになる。
フロー１のキュー長は２０００バイト、フロー２のキュー長は１０００バイト、フロー３のキュー長は３０００バイトの為、キュー長が最大のフローは、フロー３である。よって、フロー３用のバッファ３ｃからパケットを１つ廃棄する。
これにより、フロー３用のバッファ３ｃに存在するパケットは２つ、全体のキュー長は５０００（＝２０００＋１０００＋２０００）バイトとなる。
これにより、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズ以下になったので、フロー１用のバッファ３ａに到着したパケットを入力する。
この結果、フロー１用のバッファ３ａにはパケットが３つ、フロー２用のバッファ３ｂにはパケットが１つ、フロー３用のバッファ３ｃにはパケットが２つ存在することになる。
【０００６】
また、現在ＴＣＰの性能を向上させる方法として、ＥＣＮ（Ｅｘｐｌｉｃｉｔ  Ｃｏｎｇｅｓｔｉｏｎ  Ｎｏｔｉｆｉｃａｔｉｏｎ）が検討されている（下記、非特許文献２参照）。
ＥＣＮをサポートしているＴＣＰフローは、ＩＰヘッダのＥＣＴ（ＥＣＮ−Ｃａｐａｂｌｅ  Ｔｒａｎｓｐｏｒｔ）ビットをセットしたパケットを送信することにより、自身がＥＣＮをサポートしていることをルータに知らせる。
ルータは、輻輳時、パケットが到着すると、到着したパケットのＥＣＴビットがセットされているか否かを調べる。
ＥＣＴビットがセットされているならば、ＩＰヘッダのＣＥ（Ｃｏｎｇｅｓｔｉｏｎ  Ｅｘｐｅｒｉｅｎｃｅ）ビットをセットし、到着したパケットをバッファに入力する。ＥＣＴビットがセットされていなければ、到着したパケットを廃棄する。
ＣＥビットがセットされたパケットをＴＣＰフローが受信すると、ＴＣＰヘッダのＥＣＥ（ＥＣＮ−Ｅｃｈｏ）ビットをセットしたＡＣＫパケットを送信側に送る。
ＥＣＥビットがセットされたＡＣＫパケットをＴＣＰフローが受信すると、ウインドウサイズを小さくすることにより、送信レートを減少させ、ＴＣＰヘッダのＣＷＲ（Ｃｏｎｇｅｓｔｉｏｎ  Ｗｉｎｄｏｗ  Ｒｅｄｕｃｅｄ）ビットをセットしたパケットを送信する。
これらの制御により、ＥＣＮをサポートしたフローは、輻輳時にもパケットが廃棄されない通信を行うことができる。
【０００７】
なお、本願発明に関連する先行技術文献としては以下のものがある。
【非特許文献１】
Ｍ．Ｓｈｒｅｅｄｈａｒ  ｅｔ  ａ１．，”Ｅｆｆｉｃｉｅｎｔ  ｆａｉｒ  ｑｕｅｕｉｎｇ  ｕｓｉｎｇ  ｄｅｆｉｃｉｔ  ｒｏｕｎｄ        ｒｏｂｉｎ，”ＩＥＥＥ／ＡＣＭ  ｔｒａｎｓ．ｎｅｔｗｏｒｋｉｎｇ，Ｊｕｎｅ  １９９６．
【非特許文献２】
Ｋ．  Ｒａｍａｋｒｉｓｈｎａｎ，Ｓ．  Ｆｌｏｙｄ，  ａｎｄ  Ｄ．Ｂｌａｃｋ，”Ｔｈｅ  Ａｄｄｉｔｉｏｎ  ｏｆ  Ｅｘｐｌｉｃｉｔ          Ｃｏｎｇｅｓｔｉｏｎ  Ｎｏｔｉｆｉｃａｔｉｏｎ（ＥＣＮ）  ｔｏ  ＩＰ，”ＲＦＣ  ３１６８，  Ｓｅｐｔｅｍｂｅｒ  ２００１
【０００８】
【発明が解決しようとする課題】
現在のＤＲＲでは、選択的パケット廃棄を行う場合、キュー長が最大のフローのパケットを必ず廃棄しなければならない。
つまり、キュー長が最大のフローを調べ、そのフロー用のバッファに格納されているパケットを１つ選択し、選択したパケットを廃棄する代わりに、選択したパケットのＣＥビットをセットするという制御ができない。
これは、現在の選択的パケット廃棄法では、ＥＣＮをサポートしているフローのパケットも必ず廃棄しなければならない為、ＥＣＮをサポートしているフローがＥＣＮのメリットを享受できないということを意味している。
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、ＤＲＲを用いたネットワーク（特に、ホームネットワーク）においても、ＥＣＮをサポートしているフローがＥＣＮのメリット（低いパケットロス率）を享受することが可能なルータ、およびルータの輻輳制御方法を提供することにある。
また、本発明の他の目的は、前述のルータの輻輳制御方法をコンピュータに実行させるためのプログラムを提供することにある。
また、本発明の他の目的は、前述のプログラムが記録された記録媒体を提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【０００９】
【課題を解決するための手段】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
本発明は、新たにしきい値を設定し、全体のキュー長に到着したパケットのサイズを加算したものが、そのしきい値以上で、かつ、バッファ部のバッファサイズ以下ならば、ＥＣＮをサポートしているフローのパケットのＣＥビットをある確率でセットすることにより、ＥＣＮをサポートしているフローに対して、パケットを廃棄することなく、輻輳を伝えることを特徴とする。
従来の技術との差異は以下の通りである。
（１）従来方式ではしきい値を設定していない。しかし、本発明ではしきい値を設定する。
（２）従来方式では必ずパケットを廃棄しなければならず、ＣＥビットをセットするという制御は実現できなかった。しかし本発明では、廃棄する代わりにＣＥビットをセットするという制御が可能である。
【００１０】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
なお、実施の形態を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
［実施の形態１］
図１は、本発明の実施の形態１のルータの概略構成を示すブロック図である。
同図に示すように、本実施の形態のルータは、フロー識別部１と、パケットサイズ読み取り部２と、各フロー毎のバッファ（３ａ，３ｂ，３ｃ）を有し、パケットを格納するバッファ部３と、キュー長測定部４と、判定部５とを備える。
フロー識別部１は、到着したパケットのヘッダから、そのパケットを送出したフローの識別子を調べ、パケットサイズ読み取り部２は、到着したパケットのヘッダに書かれているサイズ情報を読み取る。
キュー長測定部４は、全体のキュー長、及びフロー毎のキュー長を測定する。判定部５は、パケットサイズ読み取り部２、および、キュー長測定部４から情報を受け取り、図２、図３に示すフローチャートに従って、どのパケットを選択的に廃棄およびマーキングするかを決定する。
【００１１】
以下、図２、図３を用いて、本実施の形態のルータの選択的パケット廃棄およびマーキング法を説明する。
パケットが到着した時（ステップ１０１）、判定部５は、パケットサイズ読み取り部２、および、キュー長測定部４から情報を受け取り、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファ部３のバッファサイズ（以下、単に、バッファサイズという）より大きいかを調べる（ステップ１０２）。
ステップ１０２でＹｅｓ（全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズより大きい）ならば、キュー長が最大のフローを調べ（ステップ１０３）、そのフロー用のバッファに格納されているパケットを１つ選択し、選択したパケットを廃棄する（ステップ１０４）。
次に、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズより大きいかを調べ（ステップ１０５）、ステップ１０５でＹｅｓの場合は、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズ以下になるまで、前述のステップ１０３、１０４を繰り返す。
また、ステップ１０５でＮｏの場合は、到着したパケットを送信したフロー用のバッファに到着したパケットを入力する（ステップ１０６）。
ステップ１０２でＮｏ（全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズ以下）ならば、全体のキュー長に、到着したパケットのサイズを加算したものが、しきい値よりも大きいかを調べる（ステップ１０７）。
【００１２】
ステップ１０７でＮｏ（全体のキュー長に、到着したパケットのサイズを加算したものが、しきい値以下）ならば、到着したパケットを送信したフロー用のバッファに到着したパケットを入力する（ステップ１１４）。
ステップ１０７でＹｅｓ（到着したパケットのサイズを加算したものが、しきい値より大きい）ならば、キュー長が最大のフローを調べ（ステップ１０８）、そのフロー用のバッファに格納されているパケットを１つ選択する（ステップ１０９）。
次に、選択したパケットのＥＣＴビットがセットされているかを調べ（ステップ１１０）、ステップ１１０でＮｏ（選択したパケットのＥＣＴビットがセットされていない）の場合は、ある確率Ｐで、選択したパケットを廃棄し（ステップ１１３）、ステップ１１４に進む。
ステップ１１０でＹｅｓ（選択したパケットのＥＣＴビットがセットされている）の場合は、選択したパケットのＣＥビットがセットされているかを調べ（ステップ１１１）、ステップ１１１でＹｅｓ（選択したパケットのＣＥビットがセットされている）の場合は、ステップ１１４に進む。
ステップ１１１でＮｏ（選択したパケットのＣＥビットがセットされていない）の場合は、ある確率Ｐで、選択したパケットのＣＥビットをセットし（ステップ１１２）、ステップ１１４に進む。
【００１３】
以下、図４に示す例を用いて、本実施の形態のルータの動作を具体的に説明する。
図４に示す例では、全てのパケットのサイズが１０００バイト、バッファサイズが６０００バイト、しきい値が３０００バイト、フロー１用のバッファ３ａにはパケットが１つ、フロー２用のバッファ３ｂにはパケットが１つ、フロー３用のバッファ３ｃにはパケットが２つあるものとする。
また、フロー１のみが、ＥＣＮをサポートしているとし、フロー１用のバッファ３ａに存在するフロー１のパケットのＣＥビットはセットされていないものとする。
さらに、図４（ａ）に示すように、今後、フロー１、フロー１、フロー３のパケットが順次到着するとし、パケットはバッファ部３から出力されないとする。
１つ目のパケットが到着すると、フロー識別部１により、フロー１のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長４０００バイトと、フロー毎のキュー長とを受け取り、判定部５は、全体のキュー長（４０００）に到着したパケットのサイズ（１０００）を加算したもの（５０００＝４０００＋１０００）が、バッファサイズ（６０００）より大きくはないが、しきい値（３０００）より大きいと判断する。
今、フロー１、２、３のキュー長は、それぞれ１０００、１０００、２０００バイトなので、キュー長が最大のフローはフロー３である。よって、フロー３用のバッファ３ｃからパケットを１つ選択する。
この場合には、フロー３は、ＥＣＮをサポートしていない為、ＥＣＴビットがセットされていないので、確率Ｐでパケットを廃棄する。ここではパケットを廃棄しなかったとする。
到着したフロー１のパケットは、図４（ｂ）に示すように、フロー１用のバッファ３ａに入力される。
【００１４】
２つ目のパケットが到着すると、フロー識別部１により、フロー１のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長５０００バイトとフロー毎のキュー長を受け取り、全体のキュー長（５０００）に到着したパケットのサイズ（１０００）を加算したもの（６０００＝５０００＋１０００）がバッファサイズ（６０００）より大きくはないが、しきい値（３０００）より大きいと判断する。
今、フロー１、２、３のキュー長は、それぞれ２０００、１０００、２０００バイトなので、キュー長が最大のフローはフロー１である（フロー１とフロー３のキュー長は同じであるが、ここではフロー１を最大のキュー長として選択したと仮定する）。
よって、フロー１用のバッファ３ａからパケットを１つ選択し（ここでは、先頭のパケットを選択したとする）、選択パケットのＥＣＴビットがセットされており、ＣＥビットがセットされていないので、確率Ｐで先頭パケットのＣＥビットをセットする（ここでは、セットしたとする）。
到着したフロー１のパケットは、図４（ａ）に示すように、フロー１用のバッファ３ａに入力される。
【００１５】
３つ目のパケットが到着すると、フロー識別部１により、フロー３のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長６０００バイトとフロー毎のキュー長とを受け取り、判定部５は、全体のキュー長（６０００）に到着したパケットのサイズ（１０００）を加算したもの（７０００＝６０００＋１０００）が、バッファサイズ（６０００）より大きいと判断する。
今、フロー１、２、３のキュー長は、それぞれ３０００、１０００、２０００バイトなので、キュー長が最大のフローはフロー１である。
よって、フロー１用のバッファ３ａからパケットを１つ選択し（ここでは、先頭から２番目のパケットを選択したとする）、そのパケットを廃棄する。
全体のキュー長（５０００）に、到着したパケットのサイズ（１０００）を加算したもの（６０００＝５０００＋１０００）が、バッファサイズ（６０００）以下なので、これ以上パケットを廃棄することを中止する。
到着したフロー３のパケットは、フロー３用のバッファ３ｃに入力される。
【００１６】
［実施の形態２］
本発明の実施の形態２のルータの概略構成は、図１と同じであるので再度の説明は省略する。
本実施の形態でも、判定部５は、パケットサイズ読み取り部２、および、キュー長測定部４から情報を受け取り、そして、図５、図６に示すフローチャートに従って、どのパケットを選択的に廃棄およびマーキングするかを決定する。
図５、図６に示すフローチャートは、図２、図３に示すフローチャートにおいて、ステップ１１３が省略されたものと同じであるので、再度の説明は省略する。
即ち、本実施の形態のルータは、図６に示すステップ１３０でＮｏ（選択したパケットのＥＣＴビットがセットされていない）の場合に、ステップ１４４に進み、到着したパケットを送信したフロー用のバッファに到着したパケットを入力する。
以下、図７に示す例を用いて、本実施の形態のルータの動作を具体的に説明する。
図７に示す例では、全てのパケットのサイズが１０００バイト、バッファサイズが６０００バイト、しきい値が３０００バイト、フロー１用のバッファ３ａにはパケットが１つ、フロー２用のバッファ３ｂにはパケットが１つ、フロー３用のバッファ３ｃにはパケットが２つあるものとする。
また、フロー１のみがＥＣＮをサポートしているとし、バッファに存在するフロー１のパケットのＣＥビットはセットされていないものとする。
さらに、図７（ａ）に示すように、今後、フロー１、フロー１、フロー３のパケットが順次到着するとし、パケットはバッファ部３から出力されないものとする。
【００１７】
１つ目のパケットが到着すると、フロー識別部１により、フロー１のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長４０００バイトとフロー毎のキュー長とを受け取り、判定部５は、全体のキュー長（４０００）に到着したパケットのサイズ（１０００）を加算したもの（５０００＝４０００＋１０００）がバッファサイズ（６０００）より大きくはないが、しきい値（３０００）より大きいと判断する。
今、フロー１、２、３のキュー長は、それぞれ１０００、１０００、２０００バイトなので、キュー長が最大のフローはフロー３である。
よって、フロー３用のバッファ３ｃからパケットを１つ選択するが、フロー３はＥＣＮをサポートしていない為、ＥＣＴビットがセットされていないので選択したパケットに対して何ら制御を行わない。
到着したフロー１のパケットは、図７（ｂ）に示すように、フロー１用のバッファ３ａに入力される。
【００１８】
２つ目のパケットが到着すると、フロー識別部１により、フロー１のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長５０００バイトとフロー毎のキュー長とを受け取り、判定部５は、全体のキュー長（５０００）に到着したパケットのサイズ（１０００）を加算したもの（６０００＝５０００＋１０００）がバッファサイズ（６０００）より大きくはないが、しきい値（３０００）より大きいと判別する。
今、フロー１、２、３のキュー長は、それぞれ２０００、１０００、２０００バイトなので、キュー長が最大のフローはフロー１である（フロー１とフロー３のキュー長は同じであるが、ここでは、フロー１を最大のキュー長として選択したと仮定する）。
よって、フロー１用のバッファ３ａからパケットを１つ選択し（ここでは、先頭のパケットを選択したとする）、選択したパケットのＥＣＴビットがセットされており、ＣＥビットがセットされていないので、確率Ｐで先頭パケットのＣＥビットをセットする（ここでは、セットしたとする）。
到着したフロー１のパケットは、図７（ｃ）に示すように、フロー１用のバッファ３ａに入力される。
【００１９】
３つ目のパケットが到着すると、フロー識別部１により、フロー３のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長６０００バイトとフロー毎のキュー長とを受け取り、判定部５は、全体のキュー長（６０００）に、到着したパケットのサイズ（１０００）を加算したもの（７０００＝６０００＋１０００）が、バッファサイズ（６０００）より大きいことを判別する。
今、フロー１、２、３のキュー長は、それぞれ３０００、１０００、２０００バイトなので、キュー長が最大のフローはフロー１である。
よって、フロー１用のバッファ３ａからパケットを１つ選択し（ここでは、先頭から２番目のパケットを選択したとする）、そのパケットを廃棄する。
全体のキュー長（５０００）に、到着したパケットのサイズ（１０００）を加算したもの（６０００＝５０００＋１０００）が、バッファサイズ（６０００）以下なので、これ以上パケットを廃棄することを中止する。
到着したフロー３のパケットは、フロー３用のバッファ３ｃに入力される。
【００２０】
［実施の形態３］
図８は、本発明の実施の形態３のルータの概略構成を示すブロック図である。
本実施の形態のルータは、フロー識別部１と、パケットサイズ読み取り部２と、パケットを格納するバッファ部３と、キュー長測定部４と、判定部５とに加えて、フロー毎に変数ＭＢを管理する情報管理部６と、送信監視部７とを備える点で、前述の各実施の形態のルータと相異する。
フロー識別部１は、到着したパケットのヘッダからそのパケットを送出したフローの識別子を調べ、また、パケットサイズ読み取り部２は、到着したパケットのヘッダに書かれているサイズ情報を読み取る。
キュー長測定部４は、全体のキュー長、及びフロー毎のキュー長を測定する。
判定部５は、パケットサイズ読み取り部２、キュー長測定部４、情報管理部６から情報を受け取る。
そして、図９、図１０に示すフローチャートに従って、どのパケットを選択的に廃棄およびマーキングするかを決定する。
【００２１】
以下、図９、図１０を用いて、本実施の形態のルータの選択的パケット廃棄およびマーキング法を説明する。
パケットが到着した時（ステップ１４１）、判定部５は、パケットサイズ読み取り部２、キュー長測定部４、および情報管理部６から情報を受け取り、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファ部３のバッファサイズ（以下、単に、バッファサイズという）より大きいかを調べる（ステップ１４２）。
ステップ１４２でＹｅｓ（全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズより大きい）ならば、キュー長から変数ＭＢを減算したものが最大のフローを調べ（ステップ１４３）、そのフロー用のバッファに格納されているパケットを１つ選択し、選択したパケットを廃棄する（ステップ１４４）。
次に、廃棄したパケットのＥＣＴビットがセットされているかを調べ（ステップ１４５）、ステップ１４５でＮｏ（廃棄したパケットのＥＣＴビットがセットされていない）の場合は、ステップ１４８に進む。
【００２２】
ステップ１４５でＹｅｓ（廃棄したパケットのＥＣＴビットがセットされている）の場合、廃棄したパケットのＣＥビットがセットされているかを調べ（ステップ１４６）、ステップ１４６でＮｏ（廃棄したパケットのＣＥビットがセットされていない）の場合は、ステップ１４８に進む。
ステップ１４６でＹｅｓ（廃棄したパケットのＣＥビットがセットされている）の場合、廃棄したパケットを有するフローのフロー識別子と廃棄したパケットのサイズを情報管理部６に通知し、情報管理部６で廃棄したパケットを有するフローの変数ＭＢから廃棄したパケットのサイズを減算し（ステップ１４８）、ステップ１４８に進む。
ステップ１４８では、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズより大きいかを調べ、ステップ１４８でＹｅｓの場合は、全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズ以下になるまで、前述のステップ１４３ないしステップ１４７を繰り返す。
また、ステップ１４８でＮｏの場合は、到着したパケットを送信したフロー用のバッファに到着したパケットを入力する（ステップ１４９）。
【００２３】
ステップ１４２でＮｏ（全体のキュー長に、到着したパケットのサイズを加算したものが、バッファサイズ以下）ならば、全体のキュー長に、到着したパケットのサイズを加算したものが、しきい値よりも大きいかを調べる（ステップ１５０）。
ステップ１５０でＮｏ（全体のキュー長に、到着したパケットのサイズを加算したものが、しきい値以下）ならば、到着したパケットを送信したフロー用のバッファに到着したパケットを入力する（ステップ１５７）。
ステップ１５０でＹｅｓ（到着したパケットのサイズを加算したものが、しきい値より大きい）ならば、キュー長から変数ＭＢを減算したものが最大のフローを調べ（ステップ１５１）、そのフロー用のバッファに格納されているパケットを１つ選択する（ステップ１５２）。
次に、選択したパケットのＥＣＴビットがセットされているかを調べ（ステップ１５３）、ステップ１５３でＮｏ（選択したパケットのＥＣＴビットがセットされていない）の場合は、ある確率Ｐで、選択したパケットを廃棄し（ステップ１５６）、ステップ１５７に進む。
【００２４】
ステップ１５３でＹｅｓ（選択したパケットのＥＣＴビットがセットされている）の場合は、選択したパケットのＣＥビットがセットされているかを調べ（ステップ１５４）、ステップ１５４でＹｅｓ（選択したパケットのＣＥビットがセットされている）の場合は、ステップ１５７に進む。
ステップ１５４でＮｏ（選択したパケットのＣＥビットがセットされていない）の場合は、ある確率Ｐで、選択したパケットのＣＥビットをセットし、ＣＥビットをセットしたパケットを有するフローのフロー識別子とＣＥビットをセットしたパケットのサイズを情報管理部６に通知し、情報管理部６でＣＥビットをセットしたパケットを有するフローの変数ＭＢにＣＥビットをセットしたパケットのサイズを加算し（ステップ１５５）、ステップ１５７に進む。
このように、判定部５が、パケットを選択的廃棄あるいはマーキングした場合は、そのパケットを送出したフローの識別子とパケットサイズを情報管理部６に通知する。
【００２５】
図１１は、本実施の形態のルータのパケット出力時の動作を説明するためのフローチャートである。
以下、図１１を用いて、本実施の形態のルータのパケット出力時の動作を説明する。
送信監視部７は、バッファ部３から出力されるパケットを監視しており、バッファ部３からパケットが出力されると（ステップ１６１）、送信監視部７は、出力されたパケットのＥＣＴビットがセットされているかを調べ（ステップ１６２）、ステップ１６２でＮｏの場合には、なにもしない（ステップ１６５）。
ステップ１６２でＹｅｓの場合には、出力されたパケットのＣＥビットがセットされているかを調べ（ステップ１６３）、ステップ１６３でＮｏの場合には、ステップ１６５に進む。
ステップ１６３でＹｅｓの場合には、即ち、出力されたパケットが、マーキングされたパケットならば、そのパケットを送出したフローの識別子とパケットサイズを情報管理部６に通知する。
情報管理部６は、出力したパケットを有するフローの変数ＭＢから出力したパケットのサイズを減算する（ステップ１６４）。
【００２６】
以下、図１２に示す例を用いて、本実施の形態のルータの動作を具体的に説明する。
図１２に示す例では、全てのパケットのサイズが１０００バイト、バッファサイズが６０００バイト、しきい値が３０００バイト、フロー１用のバッファ３ａにはパケットが１つ、フロー２用のバッファ３ｂにはパケットが１つ、フロー３用のバッファ３ｃにはパケットが２つあるものとする。
また、フロー１のみがＥＣＮをサポートしているとし、フロー１用のバッファ３ａに存在するフロー１のパケットのＣＥビットはセットされていないものとする。
さらに、図１２（ａ）に示すように、今後、フロー１、フロー１、フロー３のパケットが順次到着し、全てのパケットが到着した後、フロー１用のバッファ３ａから先頭のパケットが出力されるとする。
１つ目のパケットが到着すると、フロー識別部１により、フロー１のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
【００２７】
判定部５は、キュー長測定部４から全体のキュー長４０００バイトとフロー毎のキュー長を受け取り、判定部５は、全体のキュー長（４０００）に到着したパケットのサイズ（１０００）を加算したもの（５０００＝４０００＋１０００）が、バッファサイズ（６０００）より大きくはないが、しきい値（３０００）より大きいと判別する。
今、フロー１、２、３のキュー長は、それぞれ１０００、１０００、２０００バイト、変数ＭＢはすべて０バイトなので、キュー長から変数ＭＢを減算したものが最大のフローはフロー３である。
よって、フロー３用のバッファ３ｃからパケットを１つ選択するが、フロー３はＥＣＮをサポートしていない為、ＥＣＴビットがセットされていないので確率Ｐでパケットを廃棄する。ここでは、パケットは廃棄されなかったとする。
到着したフロー１のパケットは、図１２（ｂ）に示すように、フロー１用のバッファ３ａに入力される。
【００２８】
２つ目のパケットが到着すると、フロー識別部１により、フロー１のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長５０００バイトとフロー毎のキュー長を受け取り、判定部５は、全体のキュー長（５０００）に到着したパケットのサイズ（１０００）を加算したもの（６０００＝５０００＋１０００）がバッファサイズ（６０００）より大きくはないが、しきい値（３０００）より大きいと判別する。
今、フロー１、２、３のキュー長は、それぞれ２０００、１０００、２０００バイト、変数ＭＢはすべて０バイトなので、キュー長から変数ＭＢを減算したものが最大のフローはフロー１である（フロー１とフロー３の値は同じであるが、ここでは、フロー１を選択したと仮定する）。
よって、フロー１用のバッファ３ａからパケットを１つ選択するが（ここでは、先頭のパケットを選択したとする）、選択したパケットはＥＣＴビットがセットされており、ＣＥビットがセットされていないので、確率Ｐで先頭パケットのＣＥビットをセットする（ここでは、セットしたとする）。
そして、情報管理部６で管理しているフロー１の変数ＭＢに１０００バイトを加算し、到着したフロー１のパケットは、図１２（ｃ）に示すように、フロー１用のバッファ３ａに入力される。
【００２９】
３つ目のパケットが到着すると、フロー識別部１により、フロー３のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長６０００バイトとフロー毎のキュー長を受け取り、判定部５は、全体のキュー長（６０００）に到着したパケットのサイズ（１０００）を加算したもの（７０００＝６０００＋１０００）が、バッファサイズ（６０００）より大きいことを判別する。
今、フロー１、２、３のキュー長は、それぞれ３０００、１０００、２０００バイト、変数ＭＢは１０００、０、０バイトなので、キュー長から変数ＭＢを減算したものが最大のフローはフロー３である（フロー１とフロー３の値は同じであるが、ここでは、フロー３を選択したと仮定する）。
よって、フロー３用のバッファ３ｃからパケットを１つ選択し（ここでは、先頭から２番目のパケットを選択したとする）、そのパケットを廃棄する。
全体のキュー長（５０００）に、到着したパケットのサイズ（１０００）を加算したもの（６０００＝５０００＋１０００）が、バッファサイズ（６０００）以下なので、これ以上パケットを廃棄することを中止し、到着したフロー３のパケットはフロー３用のバッファ３ｃに入力される。
フロー１用のバッファ３ａから先頭のパケットが出力されると、出力されたパケットのＣＥビットはセットされているので、送信監視部７はフロー識別子１とパケットサイズ１０００バイトを情報管理部６に通知する。
情報管理部６は、フロー１の変数ＭＢから１０００バイトを減算する。その結果、フロー１の変数ＭＢの値は０になる。
【００３０】
［実施の形態４］
本発明の実施の形態４のルータの概略構成は、図８と同じであるので再度の説明は省略する。
本実施の形態でも、判定部５は、パケットサイズ読み取り部２、キュー長測定部４、情報管理部６から情報を受け取る。
そして、図１３、図１４に示すフローチャートに従って、どのパケットを選択的に廃棄およびマーキングするかを決定する。
図１３、図１４に示すフローチャートは、図９、図１０に示すフローチャートにおいて、ステップ１５６が省略されたものと同じであるので、再度の説明は省略する。
即ち、本実施の形態のルータは、図１４に示すステップ１８３でＮｏ（選択したパケットのＥＣＴビットがセットされていない）の場合に、ステップ１８６に進み、到着したパケットを送信したフロー用のバッファに到着したパケットを入力する。
判定部５は、パケットをマーキングした場合は、そのパケットを送出したフローの識別子とパケットサイズを情報管理部６に通知する。
パケットの出力時に、情報管理部６、および、送信監視部７は、前述の図１１に示すフローチャートに従って動作する。
送信監視部７は、バッファから出力されるパケットを監視し、出力されたパケットがマーキングされたパケットならば、そのパケットを送出したフローの識別子とパケットサイズを情報管理部６に通知する。情報管理部６は、変数ＭＢの値を更新する。
【００３１】
以下、図１５に示す例を用いて、本実施の形態のルータの動作を具体的に説明する。
図１５に示す例では、全てのパケットのサイズが１０００バイト、バッファサイズが６０００バイト、しきい値が３０００バイト、フロー１用のバッファ３ａにはパケットが１つ、フロー２用のバッファ３ｂにはパケットが１つ、フロー３用のバッファ３ｃにはパケットが２つあるものとする。
また、フロー１のみがＥＣＮをサポートしているとし、フロー１用のバッファ３ａに存在するフロー１のパケットのＣＥビットはセットされていないものとする。
さらに、図１５（ａ）に示すように、今後、フロー１、フロー１、フロー３のパケットが順次到着し、全てのパケットが到着した後、フロー１用のバッファ３ａから先頭のパケットが出力されるとする。
１つ目のパケットが到着すると、フロー識別部１により、フロー１のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
【００３２】
判定部５は、キュー長測定部４から全体のキュー長４０００バイトとフロー毎のキュー長を受け取り、判定部５は、全体のキュー長（４０００）に到着したパケットのサイズ（１０００）を加算したもの（５０００＝４０００＋１０００）がバッファサイズ（６０００）より大きくはないが、しきい値（３０００）より大きいと判別する。
今、フロー１、２、３のキュー長はそれぞれ１０００、１０００、２０００バイト、変数ＭＢはすべて０バイトなので、キュー長から変数ＭＢを減算したものが最大のフローはフロー３である。
よって、フロー３用のバッファ３ｃからパケットを１つ選択するが、フロー３はＥＣＮをサポートしていない為、ＥＣＴビットがセットされていないので選択したパケットに対して何ら制御を行わない。
到着したフロー１のパケットは、図１５（ｂ）に示すように、フロー１用のバッファ３ａに入力される。
【００３３】
２つ目のパケットが到着すると、フロー識別部１により、フロー１のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長５０００バイトとフロー毎のキュー長を受け取り、判定部５は、全体のキュー長（５０００）に到着したパケットのサイズ（１０００）を加算したもの（６０００＝５０００＋１０００）がバッファサイズ（６０００）より大きくはないが、しきい値（３０００）より大きいと判別する。
今、フロー１、２、３のキュー長はそれぞれ２０００、１０００、２０００バイト、変数ＭＢはすべて０バイトなので、キュー長から変数ＭＢを減算したものが最大のフローはフロー１である（フロー１とフロー３の値は同じであるが、ここでは、フロー１を選択したと仮定する）。
よって、フロー１用のバッファ３ａからパケットを１つ選択するが（ここでは、先頭のパケットを選択したとする）、選択したパケットはＥＣＴビットがセットされているが、ＣＥビットがセットされていないので、確率Ｐで先頭パケットのＣＥビットをセットする（ここでは、セットしたとする）。
そして、情報管理部６で管理しているフロー１の変数ＭＢに１０００バイトを加算し、到着したフロー１のパケットは、図１５（ｃ）に示すように、フロー１用のバッファ３ａに入力される。
【００３４】
３つ目のパケットが到着すると、フロー識別部１により、フロー３のパケットであると判断される。そして、パケットサイズ読み取り部２により、パケットサイズ１０００バイトが読み取られる。
判定部５は、キュー長測定部４から全体のキュー長６０００バイトとフロー毎のキュー長を受け取り、判定部５は、全体のキュー長（６０００）に到着したパケットのサイズ（１０００）を加算したもの（７０００＝６０００＋１０００）がバッファサイズ（６０００）より大きいことを判別する。
今、フロー１、２、３のキュー長は、それぞれ３０００、１０００、２０００バイト、変数ＭＢは１０００、０、０バイトなので、キュー長から変数ＭＢを減算したものが最大のフローはフロー３である（フロー１とフロー３の値は同じであるが、ここでは、フロー３を選択したと仮定する）。
よって、フロー３用のバッファ３ｃからパケットを１つ選択し（ここでは、先頭から２番目のパケットを選択したとする）、そのパケットを廃棄する。
【００３５】
全体のキュー長（５０００）に、到着したパケットのサイズ（１０００）を加算したもの（６０００＝５０００＋１０００）がバッファサイズ（６０００）以下なので、これ以上パケットを廃棄することを中止し、到着したフロー３のパケットをフロー３用のバッファ３ｃに入力する。
フロー１用のバッファ３ａから先頭のパケットが出力されると、出力されたパケットのＣＥビットはセットされているので、送信監視部７は、フロー識別子１とパケットサイズ１０００バイトを情報管理部６に通知する。
情報管理部６は、フロー１の変数ＭＢから１０００バイトを減算する。その結果、フロー１の変数ＭＢの値は０になる。
なお、本実施の形態３、４において、情報管理部６を省略し、判定部５でフロー毎の変数ＭＢを管理するようにしてもよい。
また、前述の説明において、ルータは、コンピュータに実行させることも可能であり、その場合に、ルータの輻輳制御方法は、コンピュータ内のハードディスクなどに格納されるプログラムを、コンピュータが実行することにより行われる。このプログラムは、ＣＤ−ＲＯＭ、あるいは、ネットワークを介したダウンロードにより供給される。
以上、本発明者によってなされた発明を、前記実施の形態に基づき具体的に説明したが、本発明は、前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００３６】
【発明の効果】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、ＤＲＲ（Ｄｅｆｉｃｉｔ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）においてもＥＣＮ（Ｅｘｐｌｉｃｉｔ  Ｃｏｎｇｅｓｔｉｏｎ  Ｎｏｔｉｆｉｃａｔｉｏｎ）をサポートすることができ、その結果、ＥＣＮをサポートしたフローはネットワーク（特に、ホームネットワーク）内にＤＲＲを実装したルータが存在しても、ＥＣＮのメリット（少ないパケットロス等）を享受することが可能となる。
【図面の簡単な説明】
【図１】本発明の実施の形態１のルータの概略構成を示すブロック図である。
【図２】本発明の実施の形態１のルータの選択的パケット廃棄およびマーキング法を説明するためのフローチャートである。
【図３】本発明の実施の形態１のルータの選択的パケット廃棄およびマーキング法を説明するためのフローチャートである。
【図４】本発明の実施の形態１のルータの選択的パケット廃棄およびマーキング法を具体的に説明するための図である。
【図５】本発明の実施の形態２のルータの選択的パケット廃棄およびマーキング法を説明するためのフローチャートである。
【図６】本発明の実施の形態２のルータの選択的パケット廃棄およびマーキング法を説明するためのフローチャートである。
【図７】本発明の実施の形態２のルータの選択的パケット廃棄およびマーキング法を具体的に説明するための図である。
【図８】本発明の実施の形態３のルータの概略構成を示すブロック図である。
【図９】本発明の実施の形態３のルータの選択的パケット廃棄およびマーキング法を説明するためのフローチャートである。
【図１０】本発明の実施の形態３のルータの選択的パケット廃棄およびマーキング法を具体的に説明するためのフローチャートである。
【図１１】本発明の実施の形態３のルータの、パケット出力時の処理手順を示すフローチャートである。
【図１２】本発明の実施の形態３のルータの選択的パケット廃棄およびマーキング法を具体的に説明するための図である。
【図１３】本発明の実施の形態４のルータの選択的パケット廃棄およびマーキング法を説明するためのフローチャートである。
【図１４】本発明の実施の形態４のルータの選択的パケット廃棄およびマーキング法を説明するためのフローチャートである。
【図１５】本発明の実施の形態４のルータの選択的パケット廃棄およびマーキング法を具体的に説明するための図である。
【図１６】ＤＲＲ（Ｄｅｆｉｃｉｔ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）における選択的パケット廃棄法を説明するためのフローチャートである。
【図１７】ＤＲＲ（Ｄｅｆｉｃｉｔ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）における選択的パケット廃棄法を具体的に説明するため図である。
【符号の説明】
１…フロー識別部、２…パケットサイズ読み取り部、３…バッファ部、３ａ，３ｂ，３ｃ…バッファ、４…キュー長測定部、５…判定部、６…情報管理部、７…送信監視部。
【図１】
2004357177.tif 000003
【図２】
2004357177.tif 000004
【図３】
2004357177.tif 000005
【図４】
2004357177.tif 000006
【図５】
2004357177.tif 000007
【図６】
2004357177.tif 000008
【図７】
2004357177.tif 000009
【図８】
2004357177.tif 000010
【図９】
2004357177.tif 000011
【図１０】
2004357177.tif 000012
【図１１】
2004357177.tif 000013
【図１２】
2004357177.tif 000014
【図１３】
2004357177.tif 000015
【図１４】
2004357177.tif 000016
【図１５】
2004357177.tif 000017
【図１６】
2004357177.tif 000018
【図１７】
2004357177.tif 000019