(57)【要約】ネットワーク上でパケットを送信する方法は、粗く時間間隔があいた第1の時間位置の間に第1の複数の試験パケットを送信する段階；第1の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；細かく時間間隔があいた第2の複数の時間位置の間にネットワーク上で第2の複数の試験パケットを送信する段階であって、第2の複数の時間位置が、好適なネットワーク・トラフィック条件に基づいて選択される段階；第2の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；および細かく間隔があいた試験パケットによって決定された1つまたは複数の好適な時間位置を使用してネットワーク上でデータ・パケットを送信する段階を含む。この方法を使用して、試験パケット間のパケット待ち時間の差を検出することによって、輻輳ネットワーク期間に「的を絞る」ことができる。
2008518552.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上でパケットを送信する方法であって、
（1）粗く時間間隔があいた第1の複数の時間位置の間にネットワーク上で第1の複数の試験パケットを送信する段階；
（2）段階（1）に基づいて、第1の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；
（3）細かく時間間隔があいた第2の複数の時間位置の間にネットワーク上で第2の複数の試験パケットを送信する段階であって、第2の複数の時間位置が、段階（2）で決定された好適なネットワーク・トラフィック条件に基づいて選択される段階；および
（4）段階（3）に基づいて、第2の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階
を含む方法。
【請求項２】
（5）段階（4）で決定された1つまたは複数の好適な時間位置の間にネットワーク上でデータ・パケットを送信する段階をさらに含む、請求項1記載の方法。
【請求項３】
段階（1）および（3）は、段階（5）でデータ・パケットを送信するのに使用される優先順位レベルよりも低い優先順位レベルを使用して試験パケットを送信する段階を含む、請求項2記載の方法。
【請求項４】
段階（2）は、第1の複数の試験パケットに関連するパケット待ち時間を評価する段階を含む、請求項1記載の方法。
【請求項５】
段階（2）は、第1の複数の試験パケットに関連するパケット破棄率を評価する段階を含む、請求項1記載の方法。
【請求項６】
段階（3）は、必要な接続帯域幅に相当するデータレートで試験パケットを送信する段階を含む、請求項1記載の方法。
【請求項７】
段階（2）は、送信ノードが、第1の複数の時間位置に関連するパケット待ち時間およびパケット破棄率のうちの一方を評価する段階を含む、請求項1記載の方法。
【請求項８】
段階（2）は、受信ノードが、第1の複数の時間位置に関連するパケット待ち時間およびパケット破棄率のうちの一方を評価する段階を含む、請求項1記載の方法。
【請求項９】
試験パケットおよびデータ・パケットは、パケット交換ネットワーク上で送信されるインターネット・プロトコル（IP）パケットを含む、請求項2記載の方法。
【請求項１０】
IPパケットは、クロックに同期したフレーム内の時間位置の間に送信されるようにスケジューリングされる、請求項9記載の方法。
【請求項１１】
試験パケットは、段階（5）のデータ・パケットよりも低いが、ネットワーク上で送信される他のデータを含む他のデータ・パケットよりも高い優先順位レベルで送信される、請求項2記載の方法。
【請求項１２】
データ・パケットは音声データを含む、請求項2記載の方法。
【請求項１３】
ネットワーク内の2つのノード間の2方向接続の各側に対して、段階（1）から（5）を繰り返す段階をさらに含む、請求項2記載の方法。
【請求項１４】
ネットワークは、パケット・キューを維持するパケット・スイッチを含むパケット交換ネットワークである、請求項1記載の方法。
【請求項１５】
第1の複数の試験パケットは、第2の複数の試験パケットのパケット・サイズとは異なるパケット・サイズを有する、請求項1記載の方法。
【請求項１６】
段階（5）の前に、以下の段階をさらに含む、請求項2記載の方法：
（a）段階（3）よりも細かく時間間隔があいた第3の複数の時間位置の間に第3の複数の試験パケットを送信する段階であって、第3の複数の時間位置が、段階（4）で決定された好適なネットワーク・トラフィック条件に基づいて選択される段階；
（b）段階（a）に基づいて、第3の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；および
（c）段階（b）で決定された時間位置を段階（5）でデータ・パケットを送信するための基礎として使用する段階。
【請求項１７】
試験パケット間の待ち時間の差を検出し、検出された差を使用して輻輳に相当する時間間隔を識別する段階をさらに含む、請求項1記載の方法。
【請求項１８】
複数のパケット・スイッチを含むインターネット・プロトコル（IP）ネットワークにおいて、データ・パケットを送信する方法であって、以下の段階を含む方法：
（1）IPネットワークを介してIPパケットが送信される複数の時間位置を含む、時刻基準フレームを確立する段階；
（2）複数の時間位置のうちのどの時間位置が、意図された受信側ノードに対するパケット輻輳率の低下に関連するかを経験的に決定する段階；および
（3）段階（2）でパケット輻輳率の低下に関連すると経験的に決定された1つまたは複数の時間位置の間に、送信ノードから意図された受信側ノードに複数のデータ・パケットを送信する段階であって、
ここで段階（2）は、粗く時間間隔があいた第1の複数の試験パケットを送信し、次いで細かく時間間隔があいた第2の複数の試験パケットを送信することによって実施され、第2の複数の試験パケットは、第1の複数の試験パケットによって決定された相対的なネットワーク非輻輳の期間に相当するように選択された時間位置の間に送信される段階。
【請求項１９】
段階（2）は、段階（3）で複数のデータ・パケットを送信するのに使用されるパケット優先順位レベルよりも低いパケット優先順位レベルを使用して試験パケットを送信する段階を含む、請求項18記載の方法。
【請求項２０】
段階（2）は、段階（3）で所望の帯域幅をサポートするのに十分なデータレートで試験パケットを送信する段階を含む、請求項18記載の方法。
【請求項２１】
実行されたときに、
（1）粗く時間間隔があいた第1の複数の時間位置の間にネットワーク上で第1の複数の試験パケットを送信する段階；
（2）段階（1）に基づいて、第1の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；
（3）細かく時間間隔があいた第2の複数の時間位置の間にネットワーク上で第2の複数の試験パケットを送信する段階であって、第2の複数の時間位置が、段階（2）で決定された好適なネットワーク・トラフィック条件に基づいて選択される段階；
（4）段階（3）に基づいて、第2の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；および
（5）段階（4）で決定された1つまたは複数の好適な時間位置を使用してネットワーク上でデータ・パケットを送信する段階
を実施する、コンピュータ実行可能命令をプログラムされたコンピュータ。
【請求項２２】
コンピュータ実行可能命令は、ネットワークに接続された第2のコンピュータを用いてパケット待ち時間を評価する段階をさらに実施する、請求項21記載のコンピュータ。
【請求項２３】
コンピュータ実行可能命令は、段階（5）でデータ・パケットを送信するのに使用される優先順位レベルよりも低い優先順位レベルを使用して段階（1）および（3）を実施する、請求項21記載のコンピュータ。
【請求項２４】
コンピュータ実行可能命令は、第1の複数の試験パケットに関連するパケット待ち時間を評価することによって段階（2）を実施する、請求項21記載のコンピュータ。
【請求項２５】
コンピュータ実行可能命令は、第1の複数の試験パケットに関連するパケット破棄率を評価することによって段階（2）を実施する、請求項21記載のコンピュータ。
【請求項２６】
コンピュータ実行可能命令は、必要な接続帯域幅に相当するデータレートで試験パケットを送信することによって段階（3）を実施する、請求項21記載のコンピュータ。
【請求項２７】
コンピュータ実行可能命令は、試験パケット間の待ち時間の差を検出し、検出された差を使用して輻輳に相当する期間を識別する段階を実施する、請求項21記載のコンピュータ。
【請求項２８】
コンピュータ実行可能命令は、クロックに同期したフレーム内の時間位置の間に送信されるようにパケットをスケジューリングする、請求項21記載のコンピュータ。
【請求項２９】
コンピュータ実行可能命令は、段階（5）で送信されるデータ・パケットよりも低いが、ネットワーク上で送信される他のデータを含む他のデータ・パケットよりも高い優先順位レベルで試験パケットを送信する、請求項21記載のコンピュータ。
【請求項３０】
コンピュータ実行可能命令は、音声データを含むデータ・パケットを送信する、請求項21記載のコンピュータ。
【請求項３１】
コンピュータ実行可能命令は、第2の複数の試験パケットのパケット・サイズとは異なるパケット・サイズを使用して第1の複数の試験パケットを送信する、請求項21記載のコンピュータ。
【請求項３２】
コンピュータ実行可能命令は、段階（5）の前に、
（a）段階（3）よりも細かく時間間隔があいた第3の複数の時間位置の間に第3の複数の試験パケットを送信する段階であって、第3の複数の時間位置が、段階（4）で決定された好適なネットワーク・トラフィック条件に基づいて選択される段階；
（b）段階（a）に基づいて、第3の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；および
（c）段階（b）で決定された時間位置を段階（5）でデータ・パケットを送信するための基礎として使用する段階
を実施する、請求項21記載のコンピュータ。
【請求項３３】
コンピュータ実行可能命令は、複数の時間位置にわたる第1の時間セグメントの間に試験パケットを送信することによって段階（1）を実施し、
コンピュータ実行可能命令は、第1の時間セグメントのサブセットの間に試験パケットを送信することによって段階（3）を実施する、
請求項21記載のコンピュータ。
【請求項３４】
コンピュータによって実行されたときに、
（1）粗く時間間隔があいた第1の複数の時間位置の間にネットワーク上で第1の複数の試験パケットを送信する段階；
（2）段階（1）に基づいて、第1の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；
（3）細かく時間間隔があいた第2の複数の時間位置の間にネットワーク上で第2の複数の試験パケットを送信する段階であって、第2の複数の時間位置が、段階（2）で決定された好適なネットワーク・トラフィック条件に基づいて選択される段階；
（4）段階（3）に基づいて、第2の複数の時間位置のうちのどの時間位置が好適なネットワーク・トラフィック条件に相当するかを決定する段階；および
（5）段階（4）で決定された1つまたは複数の好適な時間位置を使用して、ネットワーク上でデータ・パケットを送信する段階
を実施するコンピュータ命令を含む、コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、2003年9月17日に出願され、本出願によって優先権が主張される、出願済みの米国特許出願第10/663,378号の一部継続出願である。
【背景技術】
【０００２】
発明の背景
本発明は、概して、ネットワーク（たとえば、IPネットワークやイーサネット・ネットワーク）に接続された装置が、他のそのような装置と協働して、ネットワークに影響を与えずにデータ・パケットの送受信を行うのを可能にするシステムに関する。
【０００３】
一般に知られているように、イーサネットおよびインターネット・プロトコル（IP）は、通信ネットワーク上の様々な地点の間でパケットを伝送するシステムである。このような切換えシステムは、「競合ベースの」システムと呼ばれている。すなわち、すべての送信側がネットワーク・リソースを求めて競合する。すべての送信側は同時に送信を行うことができる。すべての送信側が同時に送信を行った場合、ネットワーク・リソースは予約過多になる可能性がある。そうすると、データが遅延したり失われたりしてネットワークが影響を受ける恐れがある。
【０００４】
図1に示されているように、4つのパケット・ストリームがパケット・スイッチ112に入力され、パケット・スイッチ112は、各パケットを、それに含まれているアドレス指定情報に基づいて1つまたは複数の出力に経路指定する。パケットは予測不能な時間にスイッチに到着し、取り扱わなければならない入力のバーストが起こる恐れがある。スイッチは典型的に、少数のパケットを格納することのできる、1つまたは複数のパケット・キュー114を維持する（例えば、各出力ポートに1つのキュー）。キューは、パケット優先順位レベルによって配置された複数のキューを含んでよく、したがって、たとえば優先順位3のパケットは優先順位1のパケットよりも優先される。入力が過度のバースト状態である場合、キューは満杯になり、いくつかのパケットは廃棄されることがある。より高い優先順位のキューは通常、より低い優先順位のキューよりも前に空にされ、したがって、より低い優先順位のキューの方が先にデータを失う可能性が高い。
【０００５】
IPシステムは、パケット喪失やジッターなどの障害を被る。これは、任意の所与の瞬間にルーターにこのようなパケットがいくつ到着するかが調節されないためである。同じポートを宛先とする2つのパケットが同時にルーターに到着した場合、一方を遅延させる必要がある。両方を同時に送信することはできない。一方のパケットは、第1のパケットが完全に送信されるまでキューに保存される。
【０００６】
図2は、エンドポイント100、101、102、および103を含むコンピュータ・ネットワークを示している。ネットワークはルーター104〜107を含んでいる。図を見ると分かるように、エンドポイント100および101がエンドポイント102および103と同時に通信する場合、ルーター105とルーター106との間にボトルネックが起こる可能性がある。これは、ルーター間で同時に送信されるパケットが多すぎ、ルーターがオーバーフロー・パケットを廃棄する恐れがあるためである。このことは、平均的なネットワーク利用でも起こる可能性がある。
【０００７】
イーサネット・ネットワークおよびIPネットワーク上のデータ喪失を解消する様々な方法が開発されている。主な手法は、追加的なプロトコルを使用して失われたデータを置き換えることであった。これは、事後（after-the-fact）解決策である。一例として公知の伝送制御プロトコル（TCP）が挙げられる。TCPは、データ喪失を検出することが可能であり、完全なデータ・ファイルの完全なコピーが受信側装置に配信されるまでデータを再送させる。
【０００８】
多くの装置では、TCPなどの再送方法が低速すぎて使用不可能な場合がある。リアルタイム・アプリケーションでは、データを1回で正確に配信する必要がある。このようなアプリケーションをうまく動作させようとすると、光速でも望ましくない遅延が起こる。再送による遅延を付加することは不可能であり、また望ましくない。
【０００９】
1つの問題は、競合ベースのネットワーク上でデータを1回で確実に配信するにはどうすればよいかを決定することである。様々な手法が試みられている。最も広く提案されているシステムはネットワークにおけるデータの優先順位付けに依存している。この手法では、リアルタイム制約を有するデータが、優先順位符号によって識別され、したがって、他のデータよりも先に送信することができる。
【００１０】
優先順位付けは適切な解決策に思える。しかしながら、優先順位付けでは、反射時に同じ問題が起こる。優先順位付けは、より低い優先順位のデータを配信する際に有利であるに過ぎない。優先順位付けは、他の優先順位のデータには有利ではない。分析および試験によって、この手法はある状況では作用するが、優先順位データの量が少ないときに限られることが分かっている。音声のような単純なアプリケーションの場合、データの合計に対する割合は8%以下である必要がある。他のアプリケーションは総ネットワーク・リソースに締める割合はこれよりもずっと小さくなければならない。図1に示されているように、高い優先順位のパケットでも、短い時間間隔の間に送信される高い優先順位のパケットが多すぎる場合は廃棄されることがある。多くのネットワークでは、このため優先順位付けは実際的ではない。
【００１１】
他の手法はデータを多重化することである。この方法では、1つのデータ・フローに伴うデータのブロックが別のブロックから分離される。多重化では通常、ある種の時分割システムを使用して（時分割多重化（TDM）と呼ばれる）フローが分離される。多重化に伴う主要な問題は、ネットワークの主な利点が無くなり、すなわち、すべてに利用可能な平均帯域幅が狭くなることである。言い換えれば、ネットワーク上の潜在的な各送信側には、ネットワーク上の時間枠が、その時間が頻繁には使用されない場合でも確保される。このため、リソースの使用が非効率的になる。
【００１２】
非同期転送モード（ATM）は、データ・ネットワークを多重化して競合を減らすもう1つの方法である。ATMは、すべてのデータ・フローを等しい長さのデータ・セルに分割する。さらにATMは、任意のフローまたはアプリケーションが利用できるデータ・セルの数を制限することができる。いつ何時でも最大数のセルに対して十分な帯域幅が常に存在するように、セルを過剰供給することにより、結果として仮想TDMシステムが得られる。
【００１３】
TDMとATMは、どちらも競合を減らすが、複雑さ、コスト、構成要素をかなり増大させ、帯域幅性能を失わせる。他の手法は、パケット配信をスケジューリングするための専用ハードウェアに依存し、ハードウェア・コストを増大させる。
【発明の開示】
【００１４】
発明の概要
本発明の態様は、ネットワーク上の2つのエンドポイント間で配信されるパケットについての、経験的に求められた配信スケジュールを提供する。（たとえば、音声電話の呼び出しをサポートするために）既知のデータレートに従ってパケットを送信する必要のある送信ノードは、異なるパケット送信時間を使用して、ネットワーク上で、意図された受信側に一連の試験パケットを送信する。試験パケットは評価され、待ち時間、ジッター、および／またはパケット喪失が最も少なかった送信時間はどれかが決定され、これらの送信時間を使用して各パケットが送信持続時間に対してスケジューリングされる。他のエンドポイントも同様の方法を使用し、したがって、各エンドポイントは、どの配信スケジュールが、考えられるパケット喪失および待ち時間を最小限に抑えてパケットを送信するのに最も適しているかを評価することが可能である。ネットワークにおいてデータ、試験パケット、およびその他のデータを送信するのに異なる優先順位レベルが使用される。本システムは、ネットワーク上の2つのエンドポイント間でデータ・パケットを送信するための望ましい時間スケジュールを経験的に決定する。
【００１５】
本発明の一つの変形によれば、エンドポイントはまず、広く（粗く）時間間隔があいた試験パケットを送信し、確実な配信を行うことができる時間セグメントを広範囲に調べる。確実な配信サービスを可能にすると考えられるこのような粗い間隔（たとえば、待ち時間が短くおよび／またはパケット破棄率が低い時間間隔）は、好適であると考えられる粗い間隔の間に細かく間隔があいた追加の試験パケットを送信することによってさらに調べられる。最後に（かつ任意に）、特に微細なパケット間隔があいた更なる試験パケットを送信することによって、微細な時間間隔をさらに調べることができる。
【００１６】
詳細な説明
本発明の1つの態様によれば、リアルタイム配信または近リアルタイム配信（たとえば、電話の呼び出しや、ビデオ・フレームや、IPパケットに変換されたTDMデータ・パケット）を目的とするパケットの配信にネットワークにおける最高の優先順位が割り当てられるように、ネットワークにおけるデータ・パケットに優先順位レベルを割り当てる優先順位方式が使用される。2番目に高い優先順位レベルは、試験のために使用されるデータ・パケット（いわゆる試験パケット）に割り当てられる。3番目に高い優先順位は、ウェブ・ブラウザによって使用されるTCPデータのような、システム内の残りのデータ・パケットに割り当てられる。
【００１７】
図3はこの方式を示している。これらの優先順位レベルは、すでに多数のパケットルーターで利用できるパケット優先順位方式を使用可能にすることによって割り当てることができる。この3つのレベルよりも上および下の他の優先順位レベルにも対処することができる。たとえば、リアルタイム・レベルよりも上の優先順位レベルは、緊急目的のために割り当てるか、またはネットワーク・レベル・メッセージ（たとえば、ルーターまたはその他の装置にそれぞれの異なる機能を実行するよう指示するメッセージ）用に割り当てることができる。
【００１８】
図4は、1秒の任意の配信期間（マスタ・フレーム）を、各々の持続時間が100ミリ秒のサブフレームに分解するにはどうすればよいか、および各サブフレームをさらに各々の持続時間が10ミリ秒の二次サブフレームに分解するにはどうすればよいかを示している。各二次サブフレームは、持続時間が1ミリ秒の時間配信位置に分割される。本発明の1つの変形によれば、送信の各期間の配信スケジュールは、図4に示されているような方式を使用して分解され、各パケットは、試験パケットを送信し、かつデータを配信するためのこのスケジュールに従って、1つまたは複数の時間位置に割り当てられる。この意味では、この方式は従来のTDMシステムに類似しうる。しかしながら、TDMシステムとは異なり、どのエンドポイントにも特定の時間枠を持つことを保証できない。その代わり、ネットワーク上の各ノードは、2つのエンドポイントの間での試験パケットの事前送信に基づいて、経験的に好適であると決定される時間位置を使用して送信を行う（注意：「間隔位置」または「時間間隔位置」または「時間位置」という用語は、TDMシステムを区別するために「時間枠」の代わりに使用される）。図4に示されている期間が例示のためのみのものであり、もちろん、本発明の原則から逸脱せずに他の期間、間隔、および分解を使用できることを理解されたい。各時間位置は、様々な方式（たとえば、通し番号；マスタ・フレーム、サブフレーム、および二次サブフレームに対する番号付けなど）のうちのいずれかを使用して番号付けまたは識別することができる。
【００１９】
図5は、本発明の様々な原則を実施するのに使用できる方法の各段階を示している。まず段階501で、ネットワーク（たとえば、イーサネット・ネットワークやIPネットワーク）上の2つのエンドポイントが通信を望んでいると決定される。この決定は、電話の受信機が取り上げられ、2つのノードがボイス・オーバーIP接続を開始する必要があることを示す電話番号がダイアルされた結果であってよい。あるいは、ビデオ・データを送信しているノードと受信ノードとの間に一方向接続を確立することが必要になる場合がある。これらの接続タイプはそれぞれ、ネットワークにある量のデータ・パケット・トラフィックを課すと考えられる。たとえば、ボイス・オーバーIP接続は、10ミリ秒毎に送られるパケットに対して、80バイト・パケット・ペイロード（パケット・ヘッドを含まない）を使用する毎秒64キロビットの転送速度を必要とすることがある。ビデオストリームは典型的に、これよりも高い帯域幅要件をネットワークに課す。
【００２０】
二方向通信では、2つの別々の接続、ノードAがノードBに送信を行うための接続とノードBがノードAに送信を行うための別の接続が、通常は確立されうることに注意すべきである。本発明の原則について一方向送信に関して説明するが、二方向接続が望まれている他のエンドポイントで同じ段階が繰り返されることを理解されたい。
【００２１】
段階502で、図4に示されているような方式に従って配信スケジュールが時間間隔位置に分割される（この段階は、事前に実行することができ、2つのエンドポイント間に接続が確立されるたびに繰り返す必要はない）。配信スケジュールは、汎地球測位システム（GPS）から提供されるようなクロックから得ることができる。一例として、1秒の任意の期間をマスタ・フレーム用に確立することができ、マスタ・フレームを連続的にサブフレームおよび二次サブフレームに分解することができる。各サブフレームは、各々の持続時間が10ミリ秒の10個の時間間隔から構成され、各二次サブフレームは、各々の持続時間が1ミリ秒の10個の時間間隔から構成される。したがって、1秒の期間は、各々の持続時間が1ミリ秒の1000個の時間位置を含みうる。もちろん、他の期間を使用することができ、本発明はいかなる時間方式または分解手法にも限定されない。
【００２２】
段階503で、2つのエンドポイント間の必要な帯域幅が求められる。たとえば、単一のボイス・オーバーIP接続の場合、毎秒64キロビットの帯域幅が必要になることがある。パケット・サイズが80バイトまたは640ビットであると仮定すると（その瞬間のパケット・オーバーヘッドは無視する）、これは、毎秒100個のパケットを送信しなければならないことを意味し、すなわち、（平均で）10ミリ秒ごとに1パケットという計算になる。図4に示されている例に戻ると、このことは、図の下部の二次サブフレーム内の少なくとも1つの時間位置の間に1つのパケットを送信することによって達成されうる（各時間位置が1ミリ秒に相当する）。
【００２３】
段階504で、複数の試験パケットが、異なる時間位置の間に所望の帯域幅をサポートするのに必要な速度で送信される。各試験パケットは、通常のデータ・パケット（たとえば、TCPパケット）に応じた優先順位よりも高いが、リアルタイム・データ・トラフィック（後述）に割り当てられる優先順位よりも低い「発見」レベル優先順位（図3参照）を使用して送信される。たとえば、簡潔に図6を参照し、スケジュールが1ミリ秒時間位置に分割されていると仮定する。示すように、試験パケットは時間位置1、3、5、7、9、11、および12の間に送信することができる。各試験パケットは好ましくは、「発見」レベル優先順位と、パケットがいつ送信されたかを示すタイムスタンプと、パケットが送信された後でパケットを識別するための固有の通し番号と、パケットを送信するのにどんな時間位置を使用したかを識別する何らかの手段とを含んでいる（時間位置は、通し番号から推定することができる）。受信側エンドポイントは、試験パケットを受信すると、パケットを送信側に返送してもよく、これによって送信側は、（a）送信されたパケットのうちのどれだけが実際に受信されたかを確認し、（b）各パケットの待ち時間を求めることができる。もちろん、待ち時間を求める他の手法を使用してよい。この評価は、送信側によって行っても、受信側によって行っても、両者の組合せによって行ってもよい。例えば、受信側は各パケットについての受信時間および/または他の統計を示すレポートを返送することができる。1つまたは複数の統計メッセージを送ることにより、一連の試験パケットに対する統計を提供することができる。
【００２４】
段階505で、送信側は、試験パケットを評価し、接続を実施するうえでどの時間位置が最も好適かを決定する。たとえば、時間位置#1を使用して送信されるパケットが他の時間位置よりも、平均的なパケット破棄率が低い場合、その位置は好ましい。同様に、パケット待ち時間が最も短かった（送信側からの往復）時間位置は、待ち時間がより長い他の時間位置よりも好ましい。この理論では、ストレスがかかり始めているパケット・スイッチは、満杯になりそうなキューを有し、待ち時間、ジッター、および破棄パケットの増大を引き起こす。したがって、本発明の様々な原則によれば、他の時間位置を使用して、これらのスイッチにおけるキューを長くする可能性の高い期間にパケットを送信するのを避けることができる。1つの変形では、時間位置に「過度のストレスをかけて」システムを1ビット伸長させることができる。たとえば、実際に必要なのが80バイト・パケットに過ぎない場合、試験フェーズ中に160バイト・パケットを送信して試験過負荷状態を表すことができる。この過負荷状態は、通常の80バイト・パケットでは示すことのできないボトルネックを示すことができる。
【００２５】
受信側は、タイムスタンプを有するパケットを送り返す代わりに、収集された試験パケットに統計を行い、各時間位置に関連する待ち時間およびパケット破棄率を識別するレポートを送り返す。
【００２６】
上述のように、パケット・ヘッダ・オーバーヘッドは無視されているが、通常、評価プロセスに含まれる（すなわち、80バイト・パケットはパケット・ヘッダのサイズの分だけ大きくなる）。試験パケットに対する時間位置選択は無作為にに行うことも（すなわち、試験パケットに対する時間位置の無作為選択）、すでに使用されている時間間隔位置に基づいて行うこともできる。たとえば、送信ノードは、すでに時間間隔3で送信を行っている場合、そのような時間間隔が第2の接続に対して望ましい選択肢ではないことを事前に知ることになる。他の例として、送信ノードがすでに時間位置3で送信を行っている場合、パケットをできるだけ分散させるように試験パケットを時間位置3から最も遠い時間位置で送信することができる。
【００２７】
段階506で、2つのエンドポイント間に接続が確立され、パケットは、より高い「リアルタイム」優先順位レベルを使用し、かつ送信に最も好適であると決定された1つまたは複数の時間位置を使用して送信される。より高い優先順位レベルが使用されるため、接続は、ネットワークにおいて送信され、かつより低い優先順位レベルにある試験パケットの影響を受けない。1つの変形では、IPパケット・ヘッダ内のIP優先順位フィールドを使用してそれぞれの異なる優先順位レベルを確立することができる。
【００２８】
図6は、本発明の様々な原則を使用したシステムを示している。図6に示されているように、2つのエンドポイントはそれぞれ（たとえば、タイムスタンプを使用し待ち時間を求めるために）、正確なタイム・クロック同期が得られるようにGPS受信機に依存している。IPネットワークは、パケット（たとえば、IPパケットやイーサネット・パケット）を最終的に一方のエンドポイントから他方のエンドポイントに経路指定することが可能である複数のルーターおよび／または他のネットワーク装置で構成することができる。ネットワークを構成する組織は、他のノードが発見優先順位レベルおよびリアルタイム優先順位レベルを使うのを防止するように、ネットワーク上で使用される優先順位レベルを調節する能力を持つと仮定する。1つまたは複数の装置を各エンドポイントとネットワーク要素の間に介在させてもよい（例えば、ルーター、プロキシ装置、または以下に記載するような他の装置）。そのような装置は本発明の原理を実施して、各エンドポイントが直接そのような操作を実施する代わりに接続を確立することができる。
【００２９】
各試験パケットを異なる時間位置の間に同時に送信するのではなく、単一の位置を試験し、次いで別の位置を試験し、送信に適切な時間位置が見つかるまで、同様に試験していくことができることを理解されたい。この場合、接続を確立するのに必要な時間が長くなる。さらに、上述のように、二方向接続の場合、両方のエンドポイントが各段階を実行して接続を確立する。
【００３０】
すべてのフレームのフェーズが互いに独立しており、各フレームを共通のクロックから得るだけでよいことも理解されたい。それぞれの異なるエンドポイントは、フレーム同士を互いに同期させる必要はない。もちろん、他の手法を使用することができる。
【００３１】
本発明は、ルーター・キューにおける「早期廃棄」設定でも機能する。これは、この経験的な方法が、廃棄条件が迫っていることを検出するからである。
【００３２】
1つの態様では、パケット待ち時間およびパケット破棄率を、エンドポイント同士が接続されている間、いずれかのパラメータの低下傾向の検出に基づいて監視することができ、追加の試験パケットを送信して、接続を移動させるのにより適する時間位置を見つけることができる。
【００３３】
図7は、第1のエンドポイント701が複数のパケット・スイッチ703から705を通して第2のエンドポイント706と通信するシステムを示している。各パケット・スイッチは、複数のパケット・キュー（例えば1ポートにつき1つ）を維持している。図示の都合上、4つの異なる優先順位レベルが示されており、4は最高レベルであり、レベル1は最低レベルである。エンドポイント701がネットワークを通じたエンドポイント706との接続の開始を試みていると仮定する。エンドポイント701は、優先順位レベル2を使用して複数の「試験」パケットを送信する。図を見ると分かるように、パケット・スイッチ703は、負荷が低く、キューはトラフィックに容易に対処することができる。
【００３４】
しかしながら、パケット・スイッチ704には高い負荷がかけられている。このスイッチでは、優先順位レベル1トラフィック用のキューが満杯であり、破棄パケット、ジッター、およびパケット待ち時間の延長をもたらす。同様に、エンドポイント701によって優先順位レベル2で送信されている試験パケットは、そのキューをオーバーフローさせ、破棄パケット、ジッター、および待ち時間の延長を生じる。しかしながら、優先順位レベル3のキュー（既存のリアルタイム・トラフィック）はまだ満杯になっておらず、したがって、これらのパケットは、影響を受けていないネットワークを通じてある時期に送信される。本発明の1つの態様によれば、エンドポイント701は、ある時間位置の間に送信される試験パケットが破棄され、かつ／または待ち時間が長くなっていることを検出すると、破棄率が最も少なく、および／または待ち時間が最も短い時間位置を選択し、これらの時間位置を使用してパケットをスケジューリングする（これらのパケットは次に優先順位レベル3を使用して送信される）。
【００３５】
図7の各エンドポイントは、上述の機能のうちの1つまたは複数を実施するコンピュータ実行可能命令を含むノード（すなわち、ネットワーク・インタフェースを有するコンピュータ）を含むと仮定する。
【００３６】
すべてのフレームのフェーズが、互いに独立していてよく、共通のクロックから導かれるかまたは共通のクロックに整合されるだけでよいことも理解されたい。異なるエンドポイントが、互いにフェーズが同期したフレームを有する必要はない。言い換えれば、異なるエンドポイント間では、両方のエンドポイントが同じ相対期間を参照できるかぎり、各時間間隔を一意に識別する必要はない。この原則は、2つのエンドポイントが、異なるフェーズを有するが共通のクロックを参照するフレームに関して指定された時間間隔をどのように参照することができるかを示す図11に示されている。
【００３７】
図11に示されているように、エンドポイントA（図11の下部）が、パケット遅延を導入するWANを通してエンドポイントB（図11の上部）と通信する必要があると仮定する。各エンドポイントは、WANとの接続に対処する関連ネットワーク接続装置（NCD）を有している。（1つの考えられるそのような装置は、「Network Connection Device」という名称で、2004年10月13日に出願された本発明者の同時係属中の米国特許出願第10/962,521号に記載されている）。さらに、図11の上部を横切るタイムラインおよび図11の下部を横切るタイムラインが「絶対」時間を表し、すなわち、絶対時間において、図11の上部の時間間隔1が、図11の下部の時間間隔と同じ瞬間に現れると仮定する。さらに、NCD Aが、間隔1の間にネットワークを介して第1の試験パケットXを送信し、時間間隔3の間にネットワークを介して第2の試験パケットYを送信すると仮定する。WANによって導入されるパケット遅延のために、試験パケットXは、エンドポイントBが時間間隔4と認識するものに至るまでエンドポイントBに到達しない。同様に、試験パケットYは、エンドポイントBが時間間隔6と認識するものに至るまでエンドポイントBに到達しない。しかし、エンドポイントAおよびBは（それぞれのネットワーク接続装置NCD AおよびNCD Bを通して）、将来のパケットをその時間間隔で送信するかに関して合意する必要がある。
【００３８】
簡単に言えば、NCD Bは、試験パケットXが最小限の遅延で受信されたと決定すると、「パケットX」として識別された試験パケットが将来の送信に経験的に好適であったことをNCD Aに通知する。したがって、NCD Aは、適切な時間間隔を間隔1と識別し、一方、NCD Bは、適切な時間間隔を間隔4と識別する。同様に、NCD Aは、パケットYの適切な時間間隔を間隔3と識別し、一方、NCD Bは、パケットYの適切な時間間隔を間隔6と識別する。図11の上部のタイムラインおよび図11の下部のタイムラインが相対的に移動しないかぎり、システムはパケット遅延に対処することができ、エンドポイント（またはそのプロキシ）は、パケットを送信するのにどの時間間隔位置を使用すべきかに合意することができる。もちろん、他の手法を使用してもよい。
【００３９】
図8は、本発明の他の態様による、試験パケットを使用して微細な発見プロセスを実施する様々な段階を示す。この方法によれば、送信側エンドポイントはまず、広く時間間隔があいた試験パケットを送信して、どの時間セグメント（サブフレームまたは二次サブフレームなど）がさらなる検査の候補となるかを決定することができる。その後、エンドポイントは、さらなる検査の適切な候補と決定された1つまたは複数のセグメントの間に細かく時間間隔があいた試験パケットを送信する。この2段階試験プロセスの結果を使用して将来のパケットの配信をスケジューリングすることができる。第3のレベルの微細試験も可能である。
【００４０】
まず段階801で、ネットワーク内のエンドポイントが他のエンドポイントとの接続を開始する。前述のように、ネットワークは、イーサネットなどのローカル・エリア・ネットワーク（LAN）を含んでよく、またはインターネットなどのワイド・エリア・ネットワーク（WAN）を含んでよい。もちろん、他のネットワーク・タイプを使用することができ、本発明はこの点では制限されない。
【００４１】
段階802で、エンドポイント（またはエンドポイントの代わりに働く他の装置）は、粗く時間間隔があいた試験パケットを送信する。たとえば、図9に示されているように、エンドポイントAがエンドポイントFにパケットを送信し、パスがパケットをルータB、C、D、およびEに通すと仮定する。さらに、ルータCは、時間セグメント903の間、より具体的には時間位置11、12、13、および16〜17の間にパケット（図9でPで示されているパケット）を送信すると仮定する。エンドポイントGは、パケットをルータCおよびDに通す、エンドポイントHとの仮想接続を確立する必要があると仮定する。ルータCは、すでに間隔11、12、13、および16〜17の間にパケットを送信しているので、本発明の一局面では、パケットを送信すべき好適な時間位置を識別するために試験が実施される。しかし、一態様によれば、多数の異なる時間間隔位置を広範囲に調べるのではなく、パケットがまず、粗く間隔があいた時間セグメントの間に送信され、この粗い試験の結果が、微細試験を実施する前に評価される。
【００４２】
たとえば、図9に示されているように、まず（各々が10個の個々の時間位置で構成される複数のより小さなセグメント902および903を含む）時間セグメント901が、時間セグメント901の間に1つまたは複数のパケットを送信することによって調べられる。同様に、試験パケットが他の「粗い」時間セグメント（図9には示されていない）の間にも送信され、これらの粗い時間間隔についての結果（パケット喪失率および／または待ち時間）が評価される。粗いセグメント901の間に送信された試験パケットの方が他の粗いセグメント（図9には示されていない）の間に送信された試験パケットよりも好適であると決定されたと仮定する。図8の段階803によれば、エンドポイントG（またはその代わりに働くプロキシ装置）は、粗い時間セグメント901が好ましかったが、パケットを送信するセグメント901内の時間位置を絞り込むためにさらなる検査が必要であったと決定する。
【００４３】
段階804で、エンドポイントGは、1つまたは複数の候補セグメントの間（たとえば、セグメント901および／またはより具体的には任意のセグメント902および903）の間により細かく間隔があいた追加の試験パケットを送信し、送信に好適な時間間隔を識別する。本発明の一態様では、粗い時間セグメント901内の異なる時間間隔位置の間に追加の試験パケットが送信される。本発明の他の態様では、粗いセグメント901の間に試験パケットを送信した後、「細かな」時間セグメント902および903の間に追加の試験パケットが送信され、（たとえば）時間セグメント902は、すでにトラフィックをサポートしている時間セグメント903よりもパケット送信に好適であると決定される。段階805で、微細試験パケットに基づく好適な時間位置が識別され、段階806で、それらの時間位置の間に実際のデータ・パケットが送信される。
【００４４】
パケットのこの連続的な微細検査は任意の所望の程度に実施することができる。図8の各段階は、2レベル試験プロセスを示しているが、3レベル（または他の多重レベル）も本発明の範囲内である。
【００４５】
図10Aは、本発明の様々な原則による、粗い試験パケット、細かい試験パケット、および特に細かい試験パケットの送信を示している。図10Aの上部は、複数の「粗い」時間セグメントの各々の間の1つの試験パケットの送信を示している。それぞれの粗い時間セグメントは、たとえば図4に示されているフレームまたはサブフレームに相当するものであってよいが、本発明はこの点では制限されない。例示のために、粗い時間セグメント1001が100ミリ秒持続時間のサブフレームに相当し、したがって、複数の粗いセグメント1001は1秒の送信時間に等しいと仮定する。さらに、粗い時間セグメント1001をさらにより小さなセグメント（たとえば、それぞれが10ミリ秒持続時間の二次サブフレーム）に分解することができると仮定する。
【００４６】
図10Aに示されているようにそれぞれの粗い時間セグメントの間に1つの試験パケットを送信した後、粗いセグメント1001が好適なパケット送信特性（たとえば、待ち時間が短く、かつ／またはパケット破棄率が最も低い）を示したと決定されたと仮定する。その後、本発明の一態様によれば、この粗いセグメントの間により多くの試験パケットが送信され、時間セグメント1001のどの部分がパケット送信に最も好適であるかが決定される。図10Aに示されているように、粗い時間セグメント1001内に複数の追加の微細試験パケットが送信され、結果（たとえば、待ち時間および／またはパケット破棄率）が評価される。さらなる段階として、セグメント1001の、最適なパケット送信特性を示した部分を、図10Aの下部に示されているように特に微細な試験パケットを使用してさらに調べることができる。好適な時間の位置が識別された後、それらの位置を使用して（より高いデータ・パケット送信優先順位を使用して）データ・パケットを送信することができる。
【００４７】
図10Aの下部の試験パケットは持続時間がより短い（より小さい）パケットとして示されている。ただし、本発明はこの点では制限されない。たとえば、粗い時間セグメントの間に送信される試験パケットは1000バイト・パケットを含んでよく、一方、細かい時間セグメントおよび特に細かい時間セグメントの間に送信される試験パケットは、それぞれより小さな（たとえば、500バイトおよび100バイト）サイズを含んでよい。または、すべての試験期間中に同じパケット・サイズを使用してもよい。さらに、粗い期間1001の間に単一の試験パケットが送信されるように示されているが、その代わりに、それぞれの粗い期間の間に複数の試験パケットを送信してもよい。しかし、本発明の一態様によれば、微細試験期間中により多くのパケットが送信され、パケット送信に好適な時間位置に的が絞られる。まばらに間隔があいた多数の試験パケットを細かく間隔があいたより多数の試験パケットに「縮小する」ことによって、エンドポイントはデータ・パケット送信に好適な時間位置を迅速に識別することができる。「粗い」、「細かい」、および「特に細かい」という用語は、相対的な語であり、任意の数値に限定されるものではない。しかし、「粗い」パケットは「細かい」パケットよりも広い間隔を置いて送信され、「細かい」パケットは「特に細かい」パケットよりも広い間隔で送信される。
【００４８】
試験パケットの数およびそのサイズを所望の接続の帯域幅要件に基づいて変更できることも理解されたい。たとえば、ボイス・オーバーIP接続をサポートするのに毎秒64キロビットの帯域幅が必要である場合、80バイト（パケット・ヘッダを除く）のパケット・サイズを使用することができ、10ミリ秒ごとに1パケットの平均パケット送信速度が必要になることがある。各粗試験期間中に1回送信される80バイト・パケット・サイズを使用した粗いパケット試験の後で、複数の細かな時間セグメントの間に10ミリ秒おきに1回送信される80バイトの微細試験パケットを送信することができる。もちろん、他の変形も可能である。
【００４９】
図10Bは、試験パケットの送信、および既存のパケット・トラフィックのためにいくつかの試験パケットが遅延したときに起こるパケット待ち時間を示している。図10Bを見ると分かるように、「微細」試験パケット1001は各時間間隔中に送信される。各パケットが試験パケット通し番号（1、2、3、4、および5）を付けて送信され、各パケットが試験パケット同士の間の間隔を示す（たとえば、3ミリ秒）と仮定する。図10Bに示されているように、既存のネットワーク・トラフィックは各時間間隔中に送信される大きなパケット1002を含むと仮定する。第1の試験パケットは、ほとんどまたは全く遅延無しに受信されるが、残りの4つの試験パケット1003はネットワーク・トラフィックのために遅延してひとまとめにされる。ネットワーク・トラフィックは、ネットワーク内の1つまたは複数のキューを渋滞させ、したがって、ネットワーク内の試験パケットを遅延させることがある。
【００５０】
本発明の一態様によれば、受信ノード（または統計パケットが送信側に返される場合には、送信ノード）は、いくつかの試験パケットが遅延したと決定し、ネットワーク・トラフィックの存在および相対時間位置を推定することができる。受信ノードはその後、各間隔中の輻輳期間を回避するようにデータ・パケットをスケジューリングすることができる。この技術は、パケット・スケジューリングのために使用するのとは別に、ネットワーク診断および試験に使用することができる。たとえば、この技術を使用してネットワーク・トラフィック輻輳マップを作成することができる。
【００５１】
たとえば、各試験パケットが3ミリ秒の間隔を有し、第1の試験パケットが遅延無しに受信されたが、第2の試験パケットが12ミリ秒遅延したと仮定する。したがって、第2の試験パケットは、予定通りに第1の試験パケットから3ミリ秒後に到着するのではなく、3 + 12 = 15ミリ秒後に到着する。この状況から、第1の試験パケットを受信してから第2の試験パケットを受信するまでの期間中にネットワーク・トラフィックが存在しており、この12ミリ秒の期間は輻輳期間であると推定することができる。第2の試験パケットから第5の試験パケットがまとめて受信された（すなわち、これらの試験パケットは3ミリ秒もあいておらず、1ミリ秒未満の間隔で到着する）ため、輻輳期間の直後の期間には輻輳が起こらなかったことも推定することができる。この情報を使用してネットワークにおけるデータ・パケットをスケジューリングすることができる。
【００５２】
上記に明確に示されていないが、ネットワークは、電話番号のデータベースを維持すると共にIPアドレスにマップする1つまたは複数のソフト・フォン・スイッチ（本質的にネットワークに結合された小型コンピュータ）を含んでよい。意図された受信側に電話呼出しをかける場合、電話スイッチに繋がれ、受信側の電話番号に対応するIPアドレスが決定される。ネットワークを介してビデオ・グレード・データを送信するビデオ端末；コンピュータ・データを送信するコンピュータ端末；または他の任意の種類のデータと一緒に本発明のシステムおよび方法を使用することができる。
【００５３】
本明細書で説明した方法段階はいずれも、コンピュータ・ソフトウェアで実現し、汎用または専用コンピュータまたは装置（PLD、PGSなどを含む）で実行できるようにコンピュータ可読媒体上に記憶することができ、このようなコンピュータ可読媒体は、対象となる発明の範囲内である。専用または汎用コンピュータは、本発明の様々な原則を実施するようにネットワーク上で通信するネットワーク・インタフェースを含んでよい。特許請求の範囲内の処理段階に関連する番号付けは、都合のためのみのものであり、特定の順序またはシーケンスを必要とするものと解釈すべきではない。
【図面の簡単な説明】
【００５４】
【図１】パケット喪失が起こるオーバーフロー条件をパケット・スイッチで生じさせるバースト状態のパケットの問題を示す図である。
【図２】2組のエンドポイントがバースト条件の下で共通のネットワーク・リソースを共用するボトルネックが、ネットワークの輻輳によってどのように生じるかを示す図である。
【図３】スケジューリングされたデータ（リアルタイム・レベル）、試験パケット（発見レベル）、および他のネットワーク・トラフィック（データ・レベル）に異なるレベルを割り当てる1つの手法を示す図である。
【図４】配信スケジュールをマスタ・フレーム、サブフレーム、および二次サブフレームに分割することのできるフレーム構造を示す図である。
【図５】1つの態様に従って、本発明の様々な原則を実施する各段階を有するフローチャートを示す図である。
【図６】第1のエンドポイントから第2のエンドポイントへの試験パケット用の配信スケジュールを使用したシステムを示す図である。
【図７】リアルタイム・トラフィック（優先順位3）用のキューが1つのパケット・スイッチでほぼ満杯であり、しかも依然としてトラフィックがネットワークに通っているシステムを示す図である。
【図８】本発明の1つの方法により、粗く間隔があいた試験パケットを送信し、その後細かく間隔があいた試験パケットを送信する1組の可能な段階を示す図である。
【図９】本発明の一態様により、一連の試験パケットが送信されるネットワークを示す図である。
【図１０Ａ】本発明の一態様による、粗い試験パケット、細かい試験パケット、および特に細かい試験パケットの送信を示す図である。
【図１０Ｂ】既存のパケット・トラフィックの位置および長さに関して推論を導くのを可能にする細かい試験パケットの送信を示す図である。
【図１１】2つのエンドポイントが、異なるフェーズを有するが共通のクロックを参照するフレームに関して指定された時間間隔をどのように参照することができるかを示す図である。
【図１】
2008518552.tif 000003
【図２】
2008518552.tif 000004
【図３】
2008518552.tif 000005
【図４】
2008518552.tif 000006
【図５】
2008518552.tif 000007
【図６】
2008518552.tif 000008
【図７】
2008518552.tif 000009
【図８】
2008518552.tif 000010
【図９】
2008518552.tif 000011
【図１０Ａ】
2008518552.tif 000012
【図１０Ｂ】
2008518552.tif 000013
【図１１】
2008518552.tif 000014
【国際調査報告】
2008518552.tif 000015
2008518552.tif 000016