(57)【要約】インターネット・ストリーミングにおけるパケット損失検出を管理するために、循環バッファ（すなわち、環を形成するバッファ・チェーン）を提供する。検出レイテンシーはバッファ・チェーンのサイズで決まる。これを、ネットワーク条件およびアプリケーション要件に動的に適応させることができる。本発明は、十分な検出精度を達成できる。
2006510255.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを経由して所与の送信側から受信側に送信された複数のストリーミング・パケット（ｓｔｒｅａｍｅｄ  ｐａｃｋｅｔ）の前記受信側がストリーミング・パケット損失の適応検出を行うためのシステムであって、
各エントリが、受信されていない、失われた可能性のあるストリーミング・パケットのシーケンス番号を多くとも１つ有する、サイズがｍ＞１エントリである循環バッファと、
前記循環バッファを用いて、受信されていない、失われた可能性のあるシーケンス番号を検出して前記循環バッファに格納することと、失われたパケットのシーケンス番号を前記循環バッファ内で検出して前記循環バッファから除去し、前記パケットが失われたことを宣言することと、前記所与の送信側から受信された、失われた可能性のあるパケットのシーケンス番号を前記循環バッファから除去することとを行うパケット損失検出モジュールと、
ネットワーク条件に前記システムを適応させる適応モジュールとを含み、
損失検出レイテンシーが前記循環バッファのサイズｍで決まり、前記損失宣言が誤りである可能性があるシステム。
【請求項２】
ｍの初期設定値が４である、請求項１に記載のシステム。
【請求項３】
初期値が１であり、前記ネットワークを経由して前記所与の送信側から送信され前記受信側によって受信されたストリーミング・パケットの最大シーケンス番号を格納するように適応された変数ｓと、
循環チェーン内のあらかじめ定められた位置を指す初期位置を有し、順序において前記変数ｓに対応するエントリの次である、前記循環バッファ内のエントリから始めて、前記循環バッファのｍ個のエントリを順に循環するように適応されたポインタＰとをさらに含み、
前記所与の送信側から受信されたストリーミング・パケットに対し、前記パケット損失検出モジュールが、前記受信されたパケットのシーケンス番号を前記変数ｓと照合し、
ａ．受信されたパケットのシーケンスにおいて、前記ポインタＰによって指されている位置から始まる欠落が見つかった場合は、前記欠落にある、前記循環バッファの各エントリが、失われた可能性のあるパケットのシーケンス番号について検査され、対応するパケットが失われたと宣言され、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされ、前記欠落にある各シーケンス番号が、前記ポインタＰによって指されている位置から始まるシーケンシャル・エントリに昇順に格納され、Ｐが、欠落の次にある、前記循環バッファ内のエントリを指すように更新され、ｓが、前記受信されたパケット（ｐｋｔ）のシーケンス番号と同じに設定されること、
ｂ．受信されたパケットのシーケンスにおいて欠落が見られない場合は、前記ポインタＰによって指されているエントリが、失われた可能性のあるパケットのシーケンス番号について検査され、対応するパケットが失われたと宣言され、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされ、前記エントリがクリアされ、Ｐが、前記循環バッファ内の次のエントリを指すように更新され、ｓが、前記受信されたパケットのシーケンス番号と同じに設定されること、
ｃ．パケットの順序の乱れが見つかった場合は、前記受信されたパケットのシーケンス番号と同じシーケンス番号を含むエントリを見つけるために前記循環バッファのエントリが検索され、見つかった場合は、前記エントリがクリアされ、見つからない場合は、宣言の誤り率ｆａｌｓｅ＿ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされることのいずれかを実施する、請求項１に記載のシステム。
【請求項４】
前記ネットワーク条件が送信成功率（ｓｕｃｃｅｓｓ＿ｒａｔｅ）と宣言の誤り率（ｆａｌｓｅ＿ｒａｔｅ）のうちの少なくとも１つであり、前記成功率は、あらかじめ定められた期待率（ＥＸＰＥＣＴ＿ＲＡＴＥ）に初期設定され、
前記適応モジュールが、前記ネットワーク条件に応じて前記循環バッファのサイズｍを調整し、
ａ．ｆａｌｓｅ＿ｒａｔｅ＞ＴＯＬＥＲＡＢＬＥ＿ＲＡＴＥの場合（ＴＯＬＥＲＡＢＬＥ＿ＲＡＴＥはあらかじめ定められたしきい値）は、ｍを増やし、前記循環バッファにエントリを追加し、
ｂ．
【数１】
2006510255.tif 000004
の場合は、ｍを減らし、前記循環バッファからエントリを除去する、請求項３に記載のシステム。
【請求項５】
前記循環バッファが複数の（ｍ＞１個の）バッファの循環バッファ・チェーンＢｉ（ｉ＝１，．．．，ｍ）であり、その結果、前記複数のバッファのそれぞれが、前記チェーン内の次のバッファへのポインタと、未受信バッファのシーケンス番号を格納する値とを含むエントリであり、前記ポインタＰが前記チェーン内のバッファを指す、請求項４に記載のシステム。
【請求項６】
ネットワークを経由して所与の送信側から受信側に送信された複数のストリーミング・パケットの前記受信側がストリーミング・パケット損失の適応検出を行うためのシステムであって、
各エントリが、受信されていない、失われた可能性のあるストリーミング・パケットのシーケンス番号を多くとも１つ有する、サイズがｍ＞１エントリである循環バッファと、
前記循環バッファを用いて、受信されていない、失われた可能性のあるシーケンス番号を検出して前記循環バッファに格納すること、失われたパケットのシーケンス番号を前記循環バッファ内で検出して前記循環バッファから除去し、前記パケットが失われたことを宣言すること、および、前記所与の送信側から受信された、失われた可能性のあるパケットのシーケンス番号を前記循環バッファから除去することを行うパケット損失検出モジュールと、
前記システムをネットワーク条件に適応させる手段とを含み、
損失検出レイテンシーが前記循環バッファのサイズｍで決まり、前記損失宣言が誤りである可能性があるシステム。
【請求項７】
初期値が１であり、前記ネットワークを経由して前記所与の送信側から送信され前記受信側によって受信されたストリーミング・パケットの最大シーケンス番号を格納するように適応された変数ｓと、
循環チェーン内のあらかじめ定められた位置を指す初期位置を有し、順序において前記変数ｓに対応するエントリの次である、前記循環バッファ内のエントリから始めて、前記循環バッファのｍ個のエントリを順に循環するように適応されたポインタＰとをさらに含み、
前記所与の送信側から受信されたストリーミング・パケットに対し、前記パケット損失検出モジュールが、前記受信されたパケットのシーケンス番号を前記変数ｓと照合し、
ａ．受信されたパケットのシーケンスにおいて、前記ポインタＰによって指されている位置から始まる欠落が見つかった場合は、前記欠落にある、前記循環バッファの各エントリが、失われた可能性のあるパケットのシーケンス番号について検査され、対応するパケットが失われたと宣言され、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされ、前記欠落にある各シーケンス番号が、前記ポインタＰによって指されている位置から始まるシーケンシャル・エントリに昇順に格納され、Ｐが、欠落の次にある、前記循環バッファ内のエントリを指すように更新され、ｓが、前記受信されたパケット（ｐｋｔ）のシーケンス番号と同じに設定されることと、
ｂ．受信されたパケットのシーケンスにおいて欠落が見られない場合は、前記ポインタＰによって指されているエントリが、失われた可能性のあるパケットのシーケンス番号について検査され、対応するパケットが失われたと宣言され、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされ、前記エントリがクリアされ、Ｐが、前記循環バッファ内の次のエントリを指すように更新され、ｓが、前記受信されたパケットのシーケンス番号と同じに設定されることと、
ｃ．パケットの順序の乱れが見つかった場合は、前記受信されたパケットのシーケンス番号と同じシーケンス番号を含むエントリを見つけるために前記循環バッファのエントリが検索され、見つかった場合は、前記エントリがクリアされ、見つからない場合は、宣言の誤り率ｆａｌｓｅ＿ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされることとのいずれかを実施する、請求項６に記載のシステム。
【請求項８】
ネットワークを経由して所与の送信側から受信側に送信された複数のストリーミング・パケットの前記受信側によりストリーミング・パケット損失の適応検出を行う方法であって、
各エントリが、受信されていない、失われた可能性のあるストリーミング・パケットのシーケンス番号を多くとも１つ有する、サイズがｍ＞１エントリである循環バッファを提供するステップと、
前記所与の送信側から、シーケンス番号を有するストリーミング・パケットを受信するステップと、
前記循環バッファと、前記受信されたパケットのシーケンス番号とを用いて、
ａ．受信されていない、失われた可能性があるパケットのシーケンス番号を検出して前記循環バッファ内に格納するステップと、
ｂ．失われたパケットのシーケンス番号を前記循環バッファ内で検出して前記循環バッファから除去し、前記パケットが失われたと宣言し、その結果、前記損失宣言が誤りの可能性があるものとするステップと、
ｃ．前記受信されたパケットのシーケンス番号と対応する、失われた可能性のあるパケットのシーケンス番号を前記循環バッファから除去するステップとのいずれか１つを実行するステップと、のいずれか一つと、
損失検出レイテンシーが前記循環バッファのサイズｍで決まるネットワーク条件に前記方法を適応させるステップと、を含む方法。
【請求項９】
初期値が１である変数ｓを提供するステップと、
前記提供された変数ｓを、前記受信されたストリーミング・パケットのうちシーケンス番号の大きいｓに設定するステップと、
前記循環バッファ内のあらかじめ定められた位置を指す初期位置を有し、順序において前記変数ｓに対応するエントリの次である、前記循環バッファ内のエントリから始めて、前記提供された循環バッファのｍ個のエントリを順に循環するように適応されたポインタＰを提供するステップと、
前記所与の送信側から受信されたストリーミング・パケットに対し、前記受信されたパケットのシーケンス番号を前記変数ｓと照合し、
ａ．受信されたパケットのシーケンスにおいて、前記ポインタＰによって指されている位置から始まる欠落が見つかった場合は、
ａ．１  前記欠落にある、前記循環バッファの各エントリを、失われた可能性のあるパケットのシーケンス番号について検査し、対応するパケットが失われたと宣言し、
ａ．２  パケットが失われたと宣言された場合は、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓを１増やし、
ａ．３  前記欠落にある各シーケンス番号を、前記ポインタＰによって指されている位置から始まるシーケンシャル・エントリに昇順に格納し、
ａ．４  前記ポインタＰを、欠落の次にある、前記循環バッファ内のエントリを指すように更新し、
ａ．５  ｓを、前記受信されたパケットのシーケンス番号と同じに設定するステップと、
ｂ．受信されたパケットのシーケンスにおいて欠落が見られない場合は、
ｂ．１  前記ポインタＰによって指されているエントリを、失われた可能性のあるパケットのシーケンス番号について検査し、対応するパケットが失われたと宣言し、
ｂ．２  パケットが失われたと宣言された場合は、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓを１増やし、
ｂ．３  Ｐによって指されているエントリをクリアし、
ｂ．４  Ｐを、前記循環バッファ内の次のエントリを指すように更新し、
ｂ．５  ｓを、前記受信されたパケットのシーケンス番号と同じに設定するステップと、
ｃ．パケットの順序の乱れが見つかった場合は、
ｃ．１  前記受信されたパケットのシーケンス番号と同じシーケンス番号を含むエントリを見つけるために前記循環バッファのエントリを検索し、
ｃ．２  見つかった場合は、前記エントリをクリアし、
ｃ．３  見つからない場合は、宣言の誤り率ｆａｌｓｅｌｙ＿ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓを１増やすステップとのいずれか１つを実行するステップとをさらに含む、請求項８に記載の方法。
【請求項１０】
前記ネットワーク条件が送信成功率（ｓｕｃｃｅｓｓ＿ｒａｔｅ）と宣言の誤り率（ｆａｌｓｅ＿ｒａｔｅ）のうちの少なくとも１つであり、前記成功率は、あらかじめ定められた期待率（ＥＸＰＥＣＴ＿ＲＡＴＥ）に初期設定され、
前記適応ステップが、
ｄ．ｆａｌｓｅ＿ｒａｔｅ＞ＴＯＬＥＲＡＢＬＥ＿ＲＡＴＥの場合（ＴＯＬＥＲＡＢＬＥ＿ＲＡＴＥはあらかじめ定められたしきい値）には、
ｄ．１  ｍを１増やし、
ｄ．２  前記循環バッファにエントリを追加するステップを実行し、
ｅ．ｓｕｃｃｅｓｓ＿ｒａｔｅ＞ＥＸＰＥＣＴ＿ＲＡＴＥの場合には、
ｅ．１  ｍを１減らし、
ｅ．２  前記循環バッファからエントリを除去するステップのいずれか１つを実行することによって、ネットワーク条件に応じて前記循環バッファのサイズｍを調整する、請求項９に記載の方法。
【請求項１１】
ｍの初期設定値が４である、請求項９に記載の方法。
【請求項１２】
ネットワークを経由して所与の送信側から受信側に送信された複数のストリーミング・パケットの前記受信側によるストリーミング・パケット損失の検出を適応させるためにプロセッサと共に用いるコンピュータ・プログラムであって、コンピュータ可読記憶媒体と、前記コンピュータ可読記憶媒体に埋め込まれたコンピュータ・プログラム機構とを含み、前記コンピュータ・プログラム機構が、
各エントリが、受信されていない、失われた可能性のあるストリーミング・パケットのシーケンス番号を多くとも１つ有する、サイズがｍ＞１エントリである循環バッファと、
前記循環バッファを用いて、受信されていない、失われた可能性のあるシーケンス番号を検出して前記循環バッファに格納し、失われたパケットのシーケンス番号を前記循環バッファ内で検出して前記循環バッファから除去し、前記パケットが失われたことを宣言し、前記所与の送信側から受信された、失われた可能性のあるパケットのシーケンス番号を前記循環バッファから除去するための命令を含むパケット損失検出ルーチンと、
前記システムをネットワーク条件に適応させる命令を含む適応ルーチンとを含み、
損失検出レイテンシーが前記循環バッファのサイズｍで決まり、前記損失宣言が誤りである可能性があるコンピュータ・プログラム。
【請求項１３】
初期値が１であり、前記ネットワークを経由して前記所与の送信側から送信され前記受信側によって受信されたストリーミング・パケットの最大シーケンス番号を格納するように適応された変数ｓと、
循環チェーン内のあらかじめ定められた位置を指す初期位置を有し、順序において前記変数ｓに対応するエントリの次である、前記循環バッファ内のエントリから始めて、前記循環バッファのｍ個のエントリを順に循環するように適応されたポインタＰとをさらに含み、
前記所与の送信側から受信されたストリーミング・パケットに対し、前記パケット損失検出ルーチンの命令により、前記受信されたパケットのシーケンス番号を前記変数ｓと照合し、
ａ．受信されたパケットのシーケンスにおいて、前記ポインタＰによって指されている位置から始まる欠落が見つかった場合は、前記欠落にある、前記循環バッファの各エントリが、失われた可能性のあるパケットのシーケンス番号について検査され、対応するパケットが失われたと宣言され、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされ、前記欠落にある各シーケンス番号が、前記ポインタＰによって指されている位置から始まるシーケンシャル・エントリに昇順に格納され、Ｐが、欠落の次にある、前記循環バッファ内のエントリを指すように更新され、ｓが、前記受信されたパケット（ｐｋｔ）のシーケンス番号と同じに設定されること、
ｂ．受信されたパケットのシーケンスにおいて欠落が見られない場合は、前記ポインタＰによって指されているエントリが、失われた可能性のあるパケットのシーケンス番号について検査され、対応するパケットが失われたと宣言され、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされ、前記エントリがクリアされ、Ｐが、前記循環バッファ内の次のエントリを指すように更新され、ｓが、前記受信されたパケットのシーケンス番号と同じに設定されること、
ｃ．パケットの順序の乱れが見つかった場合は、前記受信されたパケットのシーケンス番号と同じシーケンス番号を含むエントリを見つけるために前記循環バッファのエントリが検索され、見つかった場合は、前記エントリがクリアされ、見つからない場合は、宣言の誤り率ｆａｌｓｅｌｙ＿ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１増やされ、宣言された損失の総数ｄｅｃｌａｒｅｄ＿ｌｏｓｓｅｓが１減らされることのいずれかを実行する、請求項１２に記載のコンピュータ・プログラム。
【請求項１４】
前記ネットワーク条件が送信成功率（ｓｕｃｃｅｓｓ＿ｒａｔｅ）と宣言の誤り率（ｆａｌｓｅ＿ｒａｔｅ）のうちの少なくとも１つであり、前記成功率は、あらかじめ定められた期待率（ＥＸＰＥＣＴ＿ＲＡＴＥ）に初期設定され、
前記適応ルーチンが、以下の前記ネットワーク条件に応じて前記循環バッファのサイズｍを調整する、すなわち、
ａ．ｆａｌｓｅ＿ｒａｔｅ＞ＴＯＬＥＲＡＢＬＥ＿ＲＡＴＥの場合（ＴＯＬＥＲＡＢＬＥ＿ＲＡＴＥはあらかじめ定められたしきい値）は、ｍが増やされ、前記循環バッファにエントリが追加され、
ｂ．
【数２】
2006510255.tif 000005
の場合は、ｍが減らされ、前記循環バッファからエントリが除去される、請求項１３に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット・ストリーミングにおけるパケット損失の検出に関する。詳細には、本発明は、インターネット・ストリーミングにおけるパケット損失検出のために、循環を形成するバッファ・チェーンによって実装される、循環バッファを用いたシステムおよび方法に関する。より詳細には、本発明は、チェーンのサイズで決まるパケット損失検出レイテンシーを、ネットワーク条件およびアプリケーション要件に動的に適応させて、十分な検出精度を達成し、かつ、実装が容易なシステムおよび方法に関する。
【背景技術】
【０００２】
インターネット・ストリーミング・アプリケーションでは、ビデオのＩフレームやスケーラブル符号化のベース・レイヤに属するパケットのような重要なパケットが失われると、受信側は送信側に対し、その失われたパケットを再送信するよう要求することができる。受信側は、再送信要求を即座に送信するためには、パケット損失を適時に検出する手段を持つ必要がある。現在、パケット損失検出は、タイマかタイミング・ウィンドウを用いて行われる。
【０００３】
転送制御（ＴＣＰ）プロトコルでは、損失検出にタイマを用いる。パケットが送信されるときに、そのパケットの送信側で、あるタイムアウト値を有するタイマがセットされる。送信側がパケットの肯定応答（acknowledgementを受信する前にタイマが切れると、送信側は、パケットが失われたことを宣言し、そのパケットを再送信する。
【０００４】
ほとんどのストリーミング・アプリケーションでは、損失検出はタイミング・ウィンドウを用いて行われる。タイミング・ウィンドウ（より正確にはテーブル）は、固定数のバイナリ・エントリを有する。各エントリは、パケットの状態（０：失われた、１：受信された）を表す。特定の時点で、このウィンドウの第１のエントリが、シーケンス番号（例えば、実時間転送プロトコル（ＲＴＰ）パケットのシーケンス番号）で識別されるパケットに関連付けられる。後続のウィンドウ・エントリは、シーケンスの順番に、より高いシーケンス番号のパケットに関連付けられる。したがって、パケット・シーケンス番号の空間はブロックに分割され、各ブロックが特定の時点でウィンドウに関連付けられると見なすことができる。
【０００５】
現在は、パケットの連続する２つのブロックに関連付けられた、そのような２つのタイミング・ウィンドウがパケット損失検出に用いられる。最初は、すべてのエントリが「０」とマーキングされている。パケットが受信されると、対応するウィンドウ・エントリが「１」とマーキングされる。その第１のウィンドウを越えるシーケンス番号のパケットが受信されると、対応する第２のウィンドウ・エントリがマーキングされる。第２のウィンドウをも越えるシーケンス番号のパケットが送信されると、ただちに第１のウィンドウが閉じられ、そのエントリがチェックされる。「０」とマーキングされたままのエントリに関連付けられたパケットは、失われたと宣言される。第２のウィンドウのすぐ後に、連続する新しいウィンドウが開かれて、検出処理が再開される。
【０００６】
タイマによる方法は、タイマのタイムアウト値を正しくセットするためにパケットの往復時間を測定できる、ＴＣＰのようなプロトコルにのみ適用できる。ストリーミング・アプリケーションでは、ほとんどの時間、一方向のメディア・ストリームだけが生成される。そのような場合には、タイマによる方法は適用できない。その代わりに、タイミング・ウィンドウによる方法を用いる。ただし、タイミング・ウィンドウによる方法には、次のような制限がある。
【０００７】
・ウィンドウ・サイズが固定である−ネットワーク条件やアプリケーション要件（例えば、遅延）が変化する場合に望ましい、ウィンドウ・サイズ適応化の組み込み機構がない。
・異なる損失に対して損失検出レイテンシーが均一でない−損失検出レイテンシーはＴ〜２Ｔの範囲にある（Ｔはタイミング・ウィンドウの平均時間長）。損失がウィンドウの最初のエントリに関連付けられた場合、その検出レイテンシーは２Ｔであるが、損失がウィンドウの最後のエントリに関連付けられた場合はＴである。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
そこで、適応型であり、かつ均一な損失検出レイテンシーを可能にする損失検出方法が求められる。
【課題を解決するための手段】
【０００９】
本発明のシステムおよび方法は以下を含む。
【００１０】
・ネットワーク条件やアプリケーション要件に応じてチェーン・サイズを調整できる、バッファの循環チェーン。これにより、適応型の損失検出レイテンシーを実現できる。
・チェーン・サイズが固定である、バッファの循環チェーン。これにより、チェーン・サイズが固定されている場合に均一な検出レイテンシーを実現できる。
【００１１】
レイテンシーを短くすると、失われたパケットを回復させる可能性を高めることができる。レイテンシーを均一にすると、あらゆる損失の回復可能性を等しくすることができる。したがって、あらゆる損失の検出レイテンシーを等しくすることは、ほとんどのストリーミング・アプリケーションにおいて好ましいと考えられる。
【００１２】
本発明の循環バッファの実装のオーバーヘッドは低く、タイミング・ウィンドウによる方法より低くできる。
【発明を実施するための最良の形態】
【００１３】
図１ａを参照すると、１からｍまでのバッファが、ｍ個のバッファＢｉ１０（ｉ＝１，．．．，ｍ）の環状に連結された並びを形成している。各バッファの構成１２を図１ｂに示す。図１ａに示すように、ｍは、損失検出レイテンシーを決定する、循環チェーンの長さであり、ネットワーク条件およびアプリケーション要件に適応させることができる。Ｐ１１は、チェーン内を循環して、各バッファを順に指すポインタである。チェーン内の各バッファＢｉ１０は、２つのフィールドＦ１１３およびＦ２１４を含む。Ｆ１１３は、次のバッファへのポインタを格納する。Ｆ２１４は、失われた可能性のあるパケットのシーケンス番号を格納する。
【００１４】
ストリーミング・アプリケーションでは、パケットは、パケット・シーケンス番号の順に送信されると想定される。無損失かつ理想的な状況では、到着するパケットのシーケンス番号は、必ず、前に到着したパケットのシーケンス番号より大きい。パケットの到着順序が乱れた場合やパケットが失われた場合は、受信したパケットのシーケンス番号に欠落や隔たりが見られる。２つ以上の連続する番号にまたがる欠落が見られた場合、おそらくは、この欠落は、１つまたは複数のパケットが失われたことを表している可能性がある。一方、パケットの到着順序の乱れは、インターネットではよくあることである。これは、各パケットがネットワーク内の異なる経路を通る可能性があり、早い番号のパケットが遅い番号のパケットより到着に時間がかかる場合があるからである。アプリケーションは、パケットの到着シーケンスに欠落があるのを見つけても、すぐに損失を宣言することができない。アプリケーションは、この欠落が到着順序の単なる乱れではないかどうかを見きわめなければならない。順序バッファによる方法は、損失を宣言できるかどうかを判断する手立てを提供する。
【００１５】
図２ａは、本発明の方法を達成するアルゴリズムの好ましい実施形態の、Ｃプログラミング言語によるコードを示す。図２ｂは、図２ａに示したアルゴリズムのフローチャートである。ポインタＰ１２は、バッファＢｉ１１のチェーン内を循環する。この循環は、ステップ２０でパケットを受信することによって駆動される。受信したパケットのシーケンス番号が、ステップ２１の時点で受信済みのパケットの最大シーケンス番号ｓに対して検査される。受信したパケットのシーケンス番号がその最大シーケンス番号より小さい場合、受信したパケットは順序の乱れたパケットである。
【００１６】
受信したパケットが順序の乱れたパケットでない場合は、ステップ２２で、シーケンス内の欠落について検査され、欠落が見つかった場合は、以下のステップを実行する。
ａ．Ｐが指しているバッファに未受信パケットが含まれる場合（ステップ２４でＰ−＞Ｆ２がゼロでない場合）は、ステップ２５で、シーケンス番号Ｐ−＞Ｆ２のパケットが失われたと宣言する。
ｂ．次に、Ｐが未受信パケットを指していたかどうかに関わらず、ステップ２６で、現時点での最大シーケンス番号を１増やして現在のバッファに保管し、シーケンス内の次のバッファを指すようにＰが更新される（すなわち、Ｐ＝Ｐ−＞Ｆ１）。
ｃ．ステップ２７で、欠落に相当するバッファの数が１減らされ、バッファの残り数がゼロになるまでステップａ〜ｃが繰り返される。
【００１７】
したがって、欠落に相当するすべてのシーケンス番号が循環バッファ・チェーンに格納され、各番号が１つのバッファを占有する。
【００１８】
欠落が見つからない場合は、以下のステップが実行される。
ｄ．ステップ２８で、Ｐが指しているバッファが未受信パケットを含む場合（Ｐ−＞Ｆ２がゼロでない場合）は、ステップ２９で、シーケンス番号Ｐ−＞Ｆ２のパケットが失われたと宣言され、そのバッファに格納されているシーケンス番号がゼロに設定される。
ｅ．Ｐ−＞Ｆ２が未受信パケットを指しているかどうかに関わらず、ステップ３０で、シーケンス内の次のバッファを指すようにＰが更新される。
【００１９】
順序どおりのパケットに関連する処理がすべて完了したら、
ｆ．ステップ３１で、現時点での最大シーケンス番号が、受信したパケットのシーケンス番号に設定される。
【００２０】
順序の乱れたパケット（現時点で受信済みのパケットの最大シーケンス番号ｓより若いシーケンス番号のパケット）が到着したら、
ｇ．受信したパケットの番号は循環バッファに格納されている番号と比較され、ステップ３２で、バッファ内の対応する記録が消去される（すなわち、ゼロに設定する）。
【００２１】
したがって、検出レイテンシーは、バッファ・チェーンのサイズｍで決まる。これは、ポインタが、空でないバッファを再度ポインタした場合（すなわち、Ｆ２がゼロでない場合）のみ、損失の宣言が行われるからである。
【００２２】
図３に示すように、検出レイテンシーを決定するチェーン・サイズｍが適合されることができる。例えば、好ましい実施形態では、最初はｍ＝４である。観測された、宣言の誤り率が所定のしきい値より高い場合、すなわち、
ｆａｌｓｅ＿ｒａｔｅ＞ＴＯＬＥＲＡＢＬＥ＿ＲＡＴＥ
である場合は、長さが短すぎる可能性があり、新しいバッファを挿入してｍをそれ相応の３６に適応することよって長くする必要があろう。ネットワーク経路が長いほど（すなわち、トラバースするリンクの数が多いほど）、ｍを大きくする必要がある。これは、パケットがトラバースするネットワーク経路が長いほど、到着順序の乱れが発生する可能性が高くなるからである。ｍの値が大きいほど、ポインタＰがバッファ・チェーンＢｉ１１内を循環するときに、ポインタＰがバッファ内で、送達されたが順序が乱れているパケットと遭遇する可能性は低くなる。
【００２３】
ｓｕｃｃｅｓｓ＿ｒａｔｅは、当初、事前に決定されたＥＸＰＥＣＴ＿ＲＡＴＥとして宣言され、その後、次のように調整される。
【数１】
2006510255.tif 000003
ｆａｌｓｅ＿ｒａｔｅ＝１−ｓｕｃｃｅｓｓ＿ｒａｔｅ
成功率が高すぎる場合、すなわち、
ｓｕｃｃｅｓｓ＿ｒａｔｅ＞ＥＸＰＥＣＴ＿ＲＡＴＥ
である場合は、バッファ・チェーンの長さが長すぎる可能性があり、図３に示すように、バッファを削除することによって短くする必要があろう。
【００２４】
本発明は、ネットワークに接続された記憶装置にあるメディアを再生するマルチメディア・プレーヤの実装において用いることができる。あるいは、エラー回復手段として再送信を行う必要がある（したがって、パケット損失検出を実行しなければならない）任意のタイプのマルチメディア・レシーバで用いることができる。最後に、パケット損失検出を受信側で行う、転送制御プロトコルの実装でも用いることができる。
【００２５】
ここまで説明し、図で示した、本発明の方法およびシステムは、検出レイテンシーを適応型または固定にすることができる循環バッファを実現するためのものである。当業者であれば、本発明の趣旨または範囲から逸脱することなく、本発明の方法およびシステムの様々な修正や変形が可能であることは自明であろう。したがって、本発明は、添付の特許請求項ならびにその均等物の範囲内にある修正や変形を含むものとする。
【図面の簡単な説明】
【００２６】
【図１ａ】本発明の循環バッファ構成の好ましい実施形態を示す図である。
【図１ｂ】図１ａに示した循環バッファの各バッファの構成を示す図である。
【図２ａ】図１ａおよびｂに示した循環バッファ構成を実現するアルゴリズムの好ましい実施形態を示す図である。
【図２ｂ】図２ａに示したアルゴリズムのフローチャートである。
【図３】循環バッファ・チェーンの構成をネットワーク特性に基づいて適応させるアルゴリズムの好ましい実施形態を示す図である。
2006510255.tif 000006
2006510255.tif 000007
2006510255.tif 000008
【図３】
2006510255.tif 000009
【国際調査報告】
2006510255.tif 000010
2006510255.tif 000011