(57)【要約】輻輳管理及び遅延予測の手段が記載される。種々の実施形態において、当該手段は、一連の短い送信遅延を合計し、短い各送信遅延は失敗した送信試行の確率に、失敗した送信試行に要したコストを乗算して得られる値として測定され、そして合計値を供給する。【特許請求の範囲】
【請求項１】
リンクの遅延をブロードキャストネットワークにおいて予測する方法であって、
前記短い各送信遅延は失敗した送信試行の確率に失敗した送信試行に要したコストを乗算して得られる値として測定される、一連の短い送信遅延を合計すること、
前記合計値を供給すること
を備える方法。
【発明の詳細な説明】
【背景技術】
【０００１】
関連出願の相互参照
本出願は、２００６年２月１日出願の「ＣＳＭＡ方式伝送媒体における輻輳管理及び遅延予測」と題する米国仮特許出願第６０／７６４，０１３号の利益を主張し、そして２００６年２月１日出願の「プロトコル回線レイヤ」と題する米国仮特許出願第６０／７６３，９７７号、及び２００６年２月１日出願の「プロトコルリンクレイヤ」と題する米国仮特許出願第６０／７６３，９５９号に関連する。
【０００２】
コンピュータをネットワーク化することによりデータをコンピュータ間で数十年間に亘って授受してきている。一つの重要なネットワークであるインターネットは、通信チャネルで相互接続される非常に多くのコンピュータ及びコンピュータネットワークを含む。インターネットは、電子商取引、電子メールのような情報交換、情報の抽出及び調査の実施などを含む種々の理由により使用される。多くの規格が、情報をインターネット経由で授受するために設定され、規格として、電子メール、ゴーファー（Ｇｏｐｈｅｒ），及びワールドワイドウェブ（ＷＷＷ）を挙げることができる。ＷＷＷサービスによって、サーバコンピュータシステム（すなわち、ウェブサーバまたはウェブサイト）は情報をグラフィカルなウェブページの形でリモートクライアントコンピュータシステムに送信することができる。従って、リモートクライアントコンピュータシステムはウェブページを表示することができる。ＷＷＷの各リソース（例えば、コンピュータまたはウェブページ）は、ユニフォームリソースロケータ（ＵＲＬ）によって一意に特定することができる。特定のウェブページを閲覧するために、クライアントコンピュータシステムは、当該ウェブページに対応するＵＲＬをリクエスト（例えば、ハイパーテキスト転送プロトコル（ＨＴＴＰ）リクエスト）として指定する。リクエストは、ウェブページをサポートするウェブサーバに転送される。当該ウェブサーバがリクエストを受信すると、サーバはリクエストされたウェブページをクライアントコンピュータシステムに送信する。クライアントコンピュータシステムが当該ウェブページを受信すると、クライアントコンピュータシステムは通常、ブラウザを使用してウェブページを表示する。ブラウザは通常、ウェブページをリクエストし、そして表示する特定用途向けプログラムである。
【０００３】
現在、ウェブページは多くの場合、ハイパーテキストマークアップ言語（ＨＴＭＬ）を使用して記述される。ＨＴＭＬには一連の標準のタグが使用され、これらのタグは、ウェブページを表示する方法について記述する。ユーザがリクエストをブラウザに対して行なってウェブページを表示させる場合、ブラウザはリクエストをサーバコンピュータシステムに送信し、サーバコンピュータシステムに、ウェブページを記述するＨＴＭＬドキュメントをクライアントコンピュータシステムに転送させる。リクエストされたＨＴＭＬドキュメントをクライアントコンピュータシステムが受信すると、ブラウザは、ＨＴＭＬドキュメントに記述されたウェブページを表示する。ＨＴＭＬドキュメントは種々のタグを含み、これらのタグで、テキスト、グラフィックス、コントロール、及び他の機能の表示を制御する。ＨＴＭＬドキュメントには、当該サーバコンピュータシステムで、または他のサーバコンピュータシステムで利用することができる他のウェブページのＵＲＬが含まれる。
【０００４】
拡張可能マークアップ言語（ＸＭＬ）及びワイヤレスアクセスプロトコル（ＷＡＰ）のような新規のプロトコルが存在する。ＸＭＬはＨＴＭＬよりも高いフレキシビリティを持つ。ＷＡＰは種々の機能の中でもとりわけ、ウェブページを、携帯電話機及び携帯型コンピュータ（例えばＰＤＡ）のような携帯型無線機器で閲覧する機能を実現する。これらのプロトコルの全てが、情報を人々に種々のデータ処理装置を介して提供する手段を容易にするように機能する。データをデータ処理装置の間で授受する多くの他のプロトコル及び手段が継続的に開発されることにより、情報の授受が更に容易になる。
【０００５】
無線通信では、確認応答の受信をポイントツーポイントメッセージの限定再送信に使用することにより、媒体衝突の問題を解決することが通常行なわれている。通信ネットワークの密度の変更を可能にし、かつ輻輳を改善するために、指数関数的に増加する係数を有する遅延を使用することも通常行なわれている。しかしながら、ブロードキャストメッセージには、確認応答の受信を有効に使用することができない。なぜならば、受信側の数は信頼できないからである。
【０００６】
この方法の一つの望ましくない特徴は、輻輳が最も激しく、かつ最も信頼度の低い通信リンクに最も長いメッセージ配信遅延が生じ易いことである。当該遅延によってまた、別のメッセージが、前のメッセージ配信の完了前にキューで待機する確率が高くなり易い。これらの要素が重なると、初期の輻輳が悪化し易くなって、ネットワークがネットワーク自体で復元する確率が低くなる。この一連の問題を回避するために、ルーティングを輻輳ポイントから遠く離れて避けるように決定する必要がある。このような必要が生じると今度は、輻輳領域に含まれるノード群に、メッセージ遅延に関するこれらのノードの傾向をレポートさせる方法が必要になる。
【０００７】
メッセージ遅延を測定する単純な方法では、タイミングデータを一つだけメッセージごとに収集するので、現在の再送信遅延の合理的な近似値を生成するために非常に多くのメッセージが必要になる。これらの推定には時間的な食い違いが生じ易く、そして当該食い違いが、アクティビティの同じバーストに対応しなくなり易く、これによって初期の輻輳を管理することができなくなる。
【発明を実施するための最良の形態】
【０００８】
ピアブロードキャストの信頼性の推定
本方法における測定の基本単位はブロードキャストメッセージである。各参加ノードは、短いブロードキャストメッセージを固定の時間区間で送信する。メッセージのフォーマットは、送信ごとに１だけ増加する整数カウンタを表わす簡単なビットフィールドである。各受信側は、いずれかの２つのメッセージの間の時間を測定し、そして当該期間を、メッセージカウンタの差で除算して、送信側の送信周期を求める。経過するこのような周期のたびに、受信側は単一ビットを、当該送信側の送信が受信された（１）か、または受信されなかった（０）かに関して記録する。これらのビットの履歴が、測定値「ピアブロードキャストの信頼性」の基本を構成する。
【０００９】
受信及び失敗の履歴を表わす、順番に並んだ或る系列のビットを使用して、いずれか一つのブロードキャストを所定のピアから受信する尤度を、１の個数を計数し、そして系列のビットの数で除算することにより推定することができる。情報は時間の経過とともに重要度が低くなるので、最も古いデータを時々削除することが望ましい。簡単かつ静的な系列長を使用すると、２つの問題の内の一つの問題が生じ易くなる。系列が短くなり過ぎて、アルゴリズムが瞬時イベントに対して極めて迅速に応答してしまう、または系列が長くなり過ぎて、アルゴリズムの応答が極めて緩慢になるので初期の輻輳を回避することができない。
【００１０】
これらの問題を回避するために、系列を半分に分割し、２つのサブ系列の各サブ系列に含まれる１の比率の差が統計的に重要ではないという、帰無仮説を設定し、各要素を系列に記録した後、帰無仮説を評価する。帰無仮説が誤りであることが判明する場合、系列の最も古い半分を廃棄する。このようにして、履歴が非常に安定した通信が行なわれている期間の間に蓄積され、そして履歴によって、ピアブロードキャストの信頼性について安定した推定を行なうことができる。バースト性の輻輳が生じると、ブロードキャストを受信する確率が急激に低くなり、そして履歴の新しい方の半分が、最も古い半分よりも遥かに悪くなる。この状況では、ピアブロードキャストの信頼性の推定は、伝送媒体の変化する状態に迅速に応答するためには非常に不安定になっている。
【００１１】
ユニキャスト送信遅延の予測
ピアブロードキャストの信頼性の非常に正確な推定をユニキャスト送信遅延の予測に拡張するために、ブロードキャスト損失の理由をユニキャスト再送信のアルゴリズムに拡張する必要がある。都合の良いことに、最新のバックオフアルゴリズムでは、送信の失敗ごとに２倍になる簡単な整数係数を使用する。従って、ユニキャスト遅延は一連の短い送信遅延の合計と見なすことができ、これらの送信遅延の各々は、失敗した送信試行の確率に、当該送信試行に要したコストを乗算して得られる値として定義される。送信方式に２ｎ指数バックオフアルゴリズムを使用する場合、予測遅延は、ｐをピアブロードキャストの信頼性とし、そしてｒを再試行遅延とする場合に２（ｒ／ｐ）に比例する。
【００１２】
関連するセマンティックのコンセプト
・送信遅延
・メッセージ遅延
・予測アルゴリズム
・メッセージ遅延
・ＣＳＭＡ方式伝送媒体
・媒体衝突
・再送信方法
・バックオフアルゴリズム
・指数バックオフ
・ネットワーク輻輳
・輻輳ポイント
図１は、輻輳管理及び遅延予測をＣＳＭＡ方式伝送媒体において行なうルーチンを示すフロー図である。ブロック１０２では、ルーチンが始まる。ブロック１０４では、ルーチンは、２つのネットワークデバイスの間で授受される一連の定期的な受信メッセージ及び廃棄メッセージを測定し、そしてこれらのメッセージのログを採る。ブロック１０６では、ルーチンはログを最近のアクティビティを含む第１分割ログ及び古いアクティビティを含む第２分割ログに等分する。ブロック１０８では、ルーチンは２つの分割ログの完全性（及び、可能であれば他の特性）を比較する。古い方の分割ログの完全性が第１分割ログの完全性と少なくとも同じである場合、ルーチンはブロック１１２に進む。それ以外の場合、ルーチンはブロック１１４に進む。ブロック１１２では、ルーチンは両方の分割ログの記録を行なう。ブロック１１４では、最近のアクティビティを含む分割ログの記録を行なう。ブロック１１６では、ルーチンは戻る。
【００１３】
上記説明した技術によって、少なくとも、リンクの遅延をブロードキャストネットワークにおいて予測する方法、及び輻輳をブロードキャストネットワークにおいて管理する方法が実現される。
【００１４】
これまでの記載から、本発明の特定の実施形態について本明細書において説明して例示を行なってきたが、種々の変更を本発明の技術思想及び技術範囲から逸脱しない限り加え得ることを理解できるであろう。従って、本発明は、添付の請求項によって規定される以外には制限されない。
【図面の簡単な説明】
【００１５】
【図１】ＣＳＭＡ方式伝送媒体における輻輳管理及び遅延予測の方法を示すフロー図である。
【図１】
2009525707.tif 000002
【国際調査報告】
2009525707.tif 000003
2009525707.tif 000004