(57)【要約】ネットワーク接続装置（505）は、交渉によるパケット配信スケジューリング方式を使用する第1のネットワーク（504）および経験的に判定されるパケット配信スケジューリング方式を使用する第2のネットワーク（503）を相互接続する。ネットワーク接続装置（505）は、第1のネットワーク（504）上で通信するための要求を第2のネットワーク（503）上で通信するための要求に変換し、したがって、2つのネットワークを相互接続する。交渉によるパケット配信スケジューリング方式は、エンドポイント（501、502）がパケットのスケジューリングされた配信時間を交渉するのを可能にし、一方、経験的に判定されるパケット配信方式は、ネットワークにおける様々な時間間隔位置を試験し、送信に好ましい時間間隔位置を判定する。2つのプロトコルは、2つのネットワークにおける時間間隔位置の間の互いに適合する重なり合いを見つけることによって相互接続される。これによって、パケット間のジッタの少ない、エラーの無い配信の提供が可能になる。
2008516552.tif 000002
【特許請求の範囲】
【請求項１】
第1のネットワークを介してデータ・パケットを送信する方法であって、以下の段階を含む方法：
（1）第1のネットワークを介してデータ・パケットを配信するために交渉によるパケット配信方式に従って接続を確立するための要求を第1のネットワーク上の発信側ノードから受信する段階；
（2）データ・パケットが、経験的にスケジューリングされるパケット配信機構を使用する第2のネットワークを介して宛先ノードに宛てたデータ・パケットであると判定する段階；および
（3）段階（2）に応じて、経験的にスケジューリングされるパケット配信機構を使用する第2のネットワーク上で接続を開始する段階。
【請求項２】
（4）経験的にスケジューリングされるパケット配信機構に適合する交渉によるパケット配信スケジュールを生成する段階；および
（5）交渉によるパケット配信スケジュールに従って発信側ノードからデータ・パケットを送信する段階
をさらに含む、請求項1記載の方法。
【請求項３】
第1のネットワークはローカル・エリア・ネットワークを含み、第2のネットワークはワイド・エリア・ネットワークを含む、請求項2記載の方法。
【請求項４】
段階（3）が、
（a）複数の試験パケットを第2のネットワーク上で様々な時間間隔位置で送信する段階；
（b）試験パケットに関連するパケット待ち時間率または損失率を評価する段階；および
（c）好ましいパケット待ち時間率または損失率を有する1つまたは複数の時間間隔位置を選択する段階
を含む、請求項1記載の方法。
【請求項５】
段階（1）が、第1のネットワークにおけるパケットの配信に関する提案された送信スケジュールを受信する段階を含む、請求項1記載の方法。
【請求項６】
段階（1）が、第1のネットワークにおけるパケットの配信に関する帯域幅要求を受信する段階を含む、請求項1記載の方法。
【請求項７】
段階（3）が、第1のネットワークの外部の装置で実行される、請求項1記載の方法。
【請求項８】
第2のネットワークに結合された第3のネットワーク上の第2の発信側ノードについて段階（1）〜（3）を繰り返す段階をさらに含む、請求項1記載の方法。
【請求項９】
第1および第2のネットワーク上で送信されるパケットの時間位相同期を確立する段階をさらに含む、請求項1記載の方法。
【請求項１０】
時間同期を確立する段階は、全地球測位システム（GPS）受信機を使用する段階を含む、請求項9記載の方法。
【請求項１１】
プロセッサによって実行された場合に、以下の段階：
（1）第1のネットワークを介して交渉によるパケット配信方式に従ってデータ・パケットを配信するための接続を求める要求を、第1のネットワーク上の発信側ノードから受信する段階；
（2）データ・パケットが、経験的にスケジューリングされるパケット配信機構を使用する第2のネットワークを介して配置された宛先ノードを対象とするパケットであると判定する段階；および
（3）段階（2）に応じて、経験的にスケジューリングされるパケット配信機構を使用する第2のネットワーク上で接続を開始する段階
を実行するコンピュータ命令を含むコンピュータ可読媒体。
【請求項１２】
コンピュータ命令が、さらなる段階：
（4）経験的にスケジューリングされるパケット配信機構に適合する交渉によるパケット配信スケジュールを生成する段階；および
（5）交渉によるパケット配信スケジュールに従って発信側ノードからデータ・パケットを送信する段階
を実行する、請求項11記載のコンピュータ可読媒体。
【請求項１３】
コンピュータ命令が、さらなる段階：
（a）複数の試験パケットを第2のネットワーク上で様々な時間間隔位置で送信する段階；
（b）それぞれの異なる時間間隔位置に関連するパケット待ち時間率または損失率を評価する段階；および
（c）好ましいパケット待ち時間率または損失率を有する1つまたは複数の時間間隔位置を選択する段階
を実行する、請求項12記載のコンピュータ可読媒体。
【請求項１４】
段階（1）が、第1のネットワークにおけるパケットの配信に関する提案された送信スケジュールを受信する段階を含む、請求項11記載のコンピュータ可読媒体。
【請求項１５】
段階（1）が、第1のネットワークにおけるパケットの配信に関する帯域幅要求を受信する段階を含む、請求項11記載のコンピュータ可読媒体。
【請求項１６】
コンピュータ命令が、第2のネットワークに結合された第3のネットワーク上の第2の発信側ノードについて段階（1）〜（3）を繰り返すさらなる段階を実行する、請求項11記載のコンピュータ可読媒体。
【請求項１７】
コンピュータ命令が、第2のネットワーク上に配置された装置との時間位相同期を確立するさらなる段階を実行し、そのため、第2のネットワーク上で送信されるデータ・パケットをネットワーク上で相対的に時間に間に合うように同期させることができる、請求項11記載のコンピュータ可読媒体。
【請求項１８】
（1）互いに交渉してパケットが送信される時間間隔位置を確立することによって接続を形成するノードを有する第1のネットワークにおける発信側ノードから、パケットが送信される時間間隔位置を経験的に判定することによって接続を形成するノードを有する第2のネットワークを介して配置された宛先ノードとの接続を確立するための要求を受信する段階；
（2）段階（1）に応じて、第2のネットワークを介して複数のパケットを送信し、データ・パケットを送信するのに望ましい第2のネットワーク上の1つまたは複数の時間間隔位置をパケットから経験的に判定する段階；および
（3）宛先ノードとの接続を確立するために発信側ノードに応答を送信する段階
を実行するようにプログラムされたメモリおよびプロセッサを含む装置。
【請求項１９】
プロセッサが、複数の時間間隔位置候補上で複数のパケットを同時に送信することによって段階（2）を実行する、請求項18記載の装置。
【請求項２０】
プロセッサが、複数の時間間隔位置候補上で複数のパケットを順次送信することによって段階（2）を実行する、請求項18記載の装置。
【請求項２１】
第2のネットワークに結合された第2の装置と時間間隔位置とを同期させるための手段をさらに含む、請求項18記載の装置。
【請求項２２】
同期させるための手段は全地球測位システム（GPS）受信機を含む、請求項21記載の装置。
【請求項２３】
プロセッサおよびメモリが、ネットワークにおいてデータ・パケットをルーティングするように設定可能なルータ内に配置される、請求項18記載の装置。
【請求項２４】
プロセッサおよびメモリが、複数のネットワーク要素からのデータを統合するために設定可能なネットワーク統合装置内に配置される、請求項18記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の背景
本発明は、概して、それぞれが異なるパケット配信方式を使用する2つの異なる種類のネットワーク間の仮想接続を容易にする装置および方法に関する。
【背景技術】
【０００２】
一般に知られているように、イーサネットおよびインタネット・プロトコル（IP）は、通信網上のそれぞれの異なるポイント間でパケットを送信するシステムである。これらのスイッチング・システムは、「競合ベースの」システムと呼ばれている。すなわち、すべての送信側がネットワーク・リソースを求めて競合する。すべての送信側が同時に送信を行うことができる。すべての送信側が同時に送信を行った場合、ネットワーク・リソースは需要が過多になる可能性がある。そうすると、データが遅延するかまたは失われ、ネットワークが影響を受ける。
【０００３】
図1に示されているように、パケットの4つの流れがパケットスイッチ112に入力され、パケットスイッチ112は、各パケットに含まれるアドレス指定情報に基づいてパケットを1つまたは複数の出力に送る。パケットが予測できない時間にスイッチに到着し、それによって、対処しなければならない入力のバーストが起こる可能性がある。スイッチは通常、少数のパケットを記憶することのできるパケット・キュー114を維持する。（いくつかの装置では、各出力ポートごとに1つのキューが設けられ、したがって、8つのポートがある場合、8つのキューを設けることができる。）各キューは、たとえば、優先順位3のパケットが優先順位1のパケットに優先するように、パケット優先順位レベルによって配置された複数のキューを含むことができる。入力が過度のバースト状態である場合、キューは満杯になり、いくつかのパケットを破棄することができる。最高優先順位のキューは通常、より低い優先順位のキューの前に空にされ、したがって、より低い優先順位のキューが最初にデータを失いやすい。
【０００４】
IPシステムには、パケット喪失やジッタなどの不具合が生じる。これが起こるのは、任意の所定の瞬間にそのようなパケットがいくつルータに到着するかが制御されないからである。2つのパケットが同じポートを目標として同時にルータに到着した場合、一方を遅延させる必要がある。両方のパケットを同時に送信することはできない。一方のパケットは、第1のパケットが完全に送信されるまでキューに保存される。
【０００５】
図2は、エンドポイント100、101、102、および103を含むコンピュータ・ネットワークを示している。ネットワークは、ルータ104〜107を含んでいる。図示のように、エンドポイント100および101がエンドポイント102および103と同時に通信する場合、ルータ105および106間にボトルネックが生じる恐れがある。これが起こるのは、ルータ間で同時に送信されるパケットが多すぎ、ルータがオーバフロー・パケットを破棄するからである。これは、平均ネットワーク利用度が低いときでも起こる可能性がある。
【０００６】
イーサネットおよびIPネットワーク上のデータ喪失を解消する様々な方法が開発されている。主要な手法は、追加的なプロトコルを使用して、失われたデータを置き換えることである。これは、事後的解決策である。一例として公知の伝送制御プロトコル（TCP）が挙げられる。TCPは、データ喪失を検出することができ、完全なデータ・ファイルの完全なコピーが受信側装置に配信されるまでデータを再送させる。
【０００７】
確実な最初の配信を提供するための1つの手法は、まず様々な期間中に試験パケットを送信し、その後、各期間ごとに待ち時間および／またはパケット欠損率を評価し、好ましい送信特性を有する1つまたは複数の期間を選択することによって、ネットワーク内のパケットの最適なスケジューリングを経験的に決定する手法である。過負荷のルータ・キューによって欠損するかまたは遅延したパケットは、好ましくないスケジューリング状態を示し、送信側ノードは、将来のパケットを送信するのにより好ましいスケジュールを選択して、パケット喪失の可能性を最小限に抑えることができる。この手法は、本発明の原則に関連して以下に詳しく説明する（以下の「ネットワーク・パケットの経験的スケジューリング」という見出しを参照されたい）、出願済みの米国特許出願第10/663,378号（2003年8月17日出願）に記載されている。この手法を使用すると、ルータを含むWANなどのネットワーク内の2つのノード間に仮想接続を確立することができる。
【０００８】
LANスイッチを含むローカル・エリア・ネットワーク（LAN）で別の種類のパケット輻輳問題が起こることがある。図3に示されているように、たとえば、従来のネットワークは、イーサネットLANに接続されたコンピュータのような複数のローカル・エリア・ネットワーク（LAN）エンドポイントを含む。エンドポイントは1つまたは複数のLANスイッチ302に結合され、LANスイッチ302は、ネットワークの別の部分を通して1つまたは複数の他のLANエンドポイント303に接続されている。エンドポイント301がエンドポイント303にパケットを送信すると、パケットは、他のLANエンドポイントからのパケットにも対処するLANスイッチ302を通して送信される。他のエンドポイント303によって同時に送信されるパケットが多すぎる場合、LANスイッチ302はキュー・オーバフローを起こし、パケットが失われることがある。（語「パケット」は、LANまたはワイド・エリア・ネットワーク（WAN）環境におけるデータグラムを指すのに使用される。LAN環境では、パケットを「フレーム」と呼ぶことがある。パケット切換えWAN環境では、パケット切換え装置を通常「ルータ」と呼ぶ。）。
【０００９】
図4は、LAN環境でもWAN環境でも起こりえる、図3のネットワークにおけるパケット欠損の問題の性質を示している。複数のエンドポイントがネットワーク上でパケットを同時に送信する期間には、LANスイッチ302が過負荷になり、したがって、いくつかのパケットが破棄されることがある。これは通常、LANスイッチ内の内部キューが満杯になり、したがって、発信パケットがキューから取り除かれるまで新しいパケットを受け入れられなくなることによって起こる。この場合、送信側エンドポイントのパケットが到着することが保証されず、伝送制御プロトコル（TCP）などの保証された配信プロトコルを使用することのような他の解決策が必要になる。このような解決策は、パケットの再送を待つことのできないストリーミング・ビデオまたはその他のリアルタイムアプリケーションには不適切である。
【００１０】
図3に示されている種類のネットワークにおいて最初の配信を確実に行う他の手法は、ネットワークにおける送信側ノードと受信側ノードを、両方のノードに適合する送信スケジュールについて合意させる手法である。たとえば、送信側ノードがネットワーク内の他のノードとの仮想接続を確立する必要があるとき、送信側ノードは、将来のパケットの送信を提案する時間間隔位置を示す提案スケジュールを受信側ノードに送信することができる。受信側ノードは、この提案された「送信マップ」を他のスケジューリングされた配信と比較し、提案された送信スケジュールを受け入れるかまたはネットワーク内のパケット輻輳を最小限に抑える異なる送信スケジュールを提案する。この手法は、2003年10月31日に出願され、以下に本発明の原則に関連して説明する（「交渉によるパケット配信」という見出しを参照されたい）米国特許出願第10/697,103号に記載されている。この手法を使用すると、LANスイッチを含むLANなどのネットワーク内の2つのノード間に仮想接続を確立することができる。
【００１１】
互いに適合しないパケット・スケジューリング・アルゴリズムを有する様々な種類のネットワーク間に仮想接続を確立することが必要になることがある。たとえば、図5に示されているように、第1のエンドポイント501を、上述の交渉パケット・スケジューリング技術（すなわち、LAN 504内のエンドポイントが「送信マップ」について交渉し、ネットワーク504上の輻輳を回避する）を使用するLAN 504に関連付けることができる。第2のエンドポイント502は、上述の経験的パケット・スケジューリング技術（すなわち、WAN 503上のエンドポイントが互いに試験パケットを送信し、送信側パケットに最も有利な期間を経験的に判定する）を使用するWAN 503を通してアクセスしなければならない他のLAN 508上に配置することができる。エンドポイント501がエンドポイント502にパケットを送信する必要がある場合、ネットワーク上でパケットを送信するのに互いに適合しないプロトコルが使用されているために問題が生じる恐れがある。
【発明の開示】
【００１２】
発明の概要
本発明の一局面によれば、互いに適合しないネットワーク上のエンドポイント（たとえば、経験的にスケジューリングされるネットワークおよび交渉によってスケジューリングされるネットワーク）が互いに通信できるようにする装置および方法が提供される。一変化形では、ネットワーク接続装置（NCD）は、ネットワーク間に仮想接続を確立するプロキシ装置として働く。この装置は、ネットワーク間の接続を確立しかつ切断するハンドシェーキング機能を実行することができ、任意にファイアウォール機能およびネットワーク・アドレス変換（NAT）機能を含むことができる。
【００１３】
詳細な説明  
本発明の様々な原則を説明する前に、以下に、ネットワークにおいて経験的に決定されるスケジューリング技術または交渉によるスケジューリング技術によってパケットを送信するにはどうすればよいかについて説明する。あらゆる種類のネットワーク上でどちらの技術でも使用できることが明らかであろう。
【００１４】
A. ネットワーク・パケットの経験的スケジューリング
経験的手法を使用してパケットをスケジューリングするネットワークでは、リアルタイムまたは近リアルタイム配信（たとえば、IPパケットに変換される電話呼出し、ビデオ・フレーム、またはTDMデータ・パケット）を対象とするパケットの配信にネットワークにおける最高優先順位が割り当てられるように、優先順位方式を使用してネットワーク内のデータ・パケットに優先順位レベルを割り当てることができる。2番目に高い優先順位レベルは、試験のために使用されるパケット（すなわち、いわゆる試験パケット）に割り当てられる。3番目に高い優先順位レベルは、ウェブ・ブラウザによって使用されるTCPデータのような、システム内の残りのデータ・パケットに割り当てられる。図6はこの方式を示している。これらの優先順位レベルは、すでに多数のルータで利用可能なパケット優先順位方式を有効化することによって割り当てることができる。
【００１５】
この3つのレベルよりも高い他の優先順位レベルおよびそれよりも低い他の優先順位レベルにも対処することができる。たとえば、リアルタイム・レベルよりも高い優先順位レベルは緊急またはネットワーク・レベル・メッセージ（たとえば、ルータまたは他の装置にそれぞれの異なる機能を実行するよう指示するメッセージ）のために割り当てることができる。
【００１６】
図7は、1秒の任意の配信期間（マスタ・フレーム）をそれぞれ持続時間が100ミリ秒のサブフレームに分解するにはどうすればよいか、および各サブフレームをそれぞれ持続時間が10ミリ秒の二次サブフレームにさらに分解するにはどうすればよいかを示している。各二次サブフレームは、持続時間が1ミリ秒の時間間隔に分割され、この分割を任意の所望の粒度レベルまで継続することができる。一変化形によれば、送信帯域幅の毎秒の配信期間は、図7に示されているような方式を使用して分解され、パケットは、試験パケットを送信するため、および本発明の原則を使用してデータを配信するためにこのスケジュールに従って1つまたは複数の時間間隔位置に割り当てられる。この点では、この方式は、従来のTDMシステムに類似している。しかし、TDMシステムとは異なり、エンドが特定のタイム・スロットを有することは保証されない。その代わり、ネットワーク上の各ノードは、2つのエンドポイント間ですでに行われた試験パケットの送信に基づいて経験的に好ましいと判定される間隔位置を使用して送信を行う。（注意：TDMシステムを区別するために、「タイム・スロット」ではなく語「間隔位置」または「時間間隔位置」が使用される）。
【００１７】
図8は、経験的に判定されるパケット配信システムを使用するWANなどのネットワークにおけるパケットをスケジューリングするのに使用できる方法段階を示している。まず段階801で、ネットワーク（たとえば、イーサネット・ネットワークまたはIPネットワーク）上の2つのエンドポイントが通信することを望んでいるという判定が下される。この判定は、電話の受信器が取り上げられ、電話番号がダイアルされ、2つのノードがボイス・オーバーIP接続を開始する必要があることが示された結果であってよい。あるいは、ビデオ・データを送信するノードと受信側ノードとの間に一方向接続を確立する必要がある場合がある。これらの接続タイプはそれぞれ、ネットワーク上にある一定量のデータ・パケット・トラフィックを課すことが予想される。たとえば、ボイス・オーバーIP接続は、パケットが10ミリ秒ごとに送信される（パケット・ヘッダを含まない）80バイト・パケット・ペイロードを使用した場合、毎秒64キロビットの転送速度を必要とすることがある。ビデオ・ストリームは通常、ネットワークに高帯域幅要件を課す。
【００１８】
2方向通信の場合、ノードAからノードBへの送信用の1つの接続およびノードBからノードAへの送信用の別の接続の、2つの別々の接続を確立しなければならない。本発明の原則について1方向送信に関して説明するが、2方向接続が必要とされる他のエンドポイントでも同じ段階が繰り返されることを理解されたい。
【００１９】
段階802では、配信スケジュールが、図7に示されているような方式によって間隔位置に区分される。（この段階は、事前に行うことができ、2つのエンドポイント間に接続を確立するたびに繰り返す必要はない）。配信スケジュールは、全地球測位システム（GPS）から得られるようなクロックから得ることができる。一例として、マスタ・フレームに1秒の任意の期間を確立することができ、マスタ・フレームは、サブフレームおよび二次サブフレームに連続的に分解することができる。各サブフレームは、それぞれ継続時間が10ミリ秒の10個の間隔で構成され、各二次サブフレームは、それぞれ持続時間が1ミリ秒の10個の間隔で構成される。したがって、1秒の期間は、持続時間が1ミリ秒の1000個の間隔を含む。もちろん、他の時間間隔を使用することができ、本発明は、任意の特定のタイミング方式に限定されることを意図するものではない。
【００２０】
段階803では、2つのエンドポイント間の必要な帯域幅が求められる。たとえば、シングル・ボイス・オーバーIP接続では、毎秒64キロビットの帯域幅が必要になる場合がある。80バイトまたは640ビットのパケット・サイズを仮定すると（その瞬間のパケット・オーバヘッドは無視する）、これは、10ミリ秒おきに1つのパケットに相当する毎秒100個のパケットを送信しなければならないことを意味する。図7の例に戻ると、これは、図の1番下の二次サブフレーム内の少なくとも1つの時間間隔の間にパケットを送信することを意味する。（各間隔は1ミリ秒に相当する）。
【００２１】
段階804で、それぞれの異なる時間間隔に、所望の帯域幅をサポートするのに必要な速度で複数の試験パケットが送信される。各試験は、通常のデータ・パケット（たとえば、TCPパケット）に与えられる優先順位よりも高く、リアルタイム・データ・トラフィック（後述）に割り当てられる優先順位よりも低い「発見」レベル優先順位（図6参照）を使用して送信される。たとえば、しばらくの間図9を参照して、スケジュールが1ミリ秒の時間間隔に区分されていると仮定する。試験パケットは、図示のように時間間隔1、3、5、7、9、11、および12の間に送信することができる。各試験パケットは好ましくは、「発見」レベル優先順位；パケットがいつ送信されたかを示すタイム・スタンプ；およびパケットを送信するのにどの時間間隔が使用されたかを識別するある手段を含む。（この時間間隔は通し番号から推定することができる）。受信側エンドポイントは、試験パケットを受信すると、そのパケットを送信側に返送することができ、それによって送信側は、（a）送信されたパケットのうちで実際に受信されたパケットはいくつかを確認し、（b）各パケットの待ち時間を判定することができる。受信側エンドポイントは、パケットを返送する代わりに、試験パケットに関する統計を概略的に示す要約パケットを送信することができる。もちろん、待ち時間を判定する他の手法を使用することができる。評価は、送信側によって行うことも、受信側によって行うことも、あるいはこの2つの組合せによって行うこともできる。
【００２２】
段階806では、送信側が、試験パケットを評価し、接続を実施するのにどの時間間隔が最も好ましいかを判定する。たとえば、時間間隔#1を使用して送信されたパケットが他の間隔よりもパケット欠損率が低いと判定された場合、その間隔が好ましい。同様に、パケット待ち時間が最も短くなった時間間隔（送信側からの往復）は、より長い待ち時間を有する他の時間間隔と比べて好ましい。この理論は、パケット・スイッチにストレスがかかるようになると、キューが満杯に近くなり、待ち時間、ジッタ、およびパケット欠損が増えるという理論である。したがって、本発明の原則によれば、他の時間間隔を使用して、これらのスイッチにおけるキューの長さを延ばす可能性のある期間の間パケットの送信を回避することができる。一変化形では、時間間隔に「過度のストレスがかかり」、システムが少し無理を強いられる可能性がある。たとえば、実際に必要とされるパケットが80バイトに過ぎない場合、過負荷状態を表す160バイト・パケットを試験フェーズ中に送信することができる。過負荷状態は、通常の80バイト・パケットが示さないボトルネックを示すことがある。
【００２３】
受信側は、タイム・スタンプの付いたパケットを送り返す代わりに、収集された試験パケットに対する統計を実行し、各時間間隔に関連する待ち時間およびパケット欠損率を識別するレポートを送り返す。
【００２４】
上述のように、パケット・ヘッダ・オーバヘッドは無視されているが、通常評価プロセスに含まれる（すなわち、80バイト・パケットがパケット・ヘッダのサイズの分だけ大きくなる）。試験パケットに関する間隔選択は、無作為に判定する（すなわち、試験パケットについて時間間隔の無作為な選択を選択することができる）か、またはすでに使用された時間間隔に基づいて判定することができる。たとえば、送信側ノードがすでに時間間隔3の間に送信を行っている場合、送信側ノードは、このような時間間隔が第2の接続に望ましい選択ではないことを事前に知ることになる。他の例として、送信側ノードがすでに間隔3の間に送信を行っている場合、間隔位置3から最も遠く離れた時間間隔位置で試験パケットを送信し、パケットをできるだけ分散させることができる。
【００２５】
段階806で、2つのエンドポイント間に接続が確立され、より高い「リアルタイム」優先順位レベルを使用し、送信により好ましいと判定された間隔を使用してパケットが送信される。より高い優先順位レベルが使用されるため、接続は、ネットワークを介して送信され、より低い優先順位レベルを有する試験パケットの影響を受けない。一変化形では、IPパケット・ヘッド内のIP優先順位フィールドを使用して様々な優先順位レベルを確立することができる。
【００２６】
図9は、本発明の様々な原則を使用するシステムを示している。図9に示されているように、2つのエンドポイントはそれぞれ、GPS受信機を使用して（たとえば、タイム・スタンプを付加し待ち時間を判定するために）正確な時間クロック同期を行う。IPネットワークは、パケット（たとえば、IPまたはイーサネット・パケット）を最終的に一方のエンドポイントから他方のエンドポイントにルーティングすることのできる複数のルータおよび／またはその他のネットワーク装置で構成することができる。ネットワークを構成する組織が、ネットワーク上で使用される優先順位レベルを制御し、他のノードが発見優先順位レベルおよびリアルタイム優先順位レベルを使用するのを妨げる能力を有すると仮定する。
【００２７】
それぞれの異なる時間間隔位置の間に同時に試験パケットを送信するのではなく、送信に適切な間隔位置が見つかるまで時間間隔位置を1つずつ試験していくことができることを理解されたい。この場合、接続を確立するのに必要な時間が長くなる。さらに、上述のように、2方向接続では、両方のエンドポイントが接続を確立する段階を実施する。
【００２８】
この方式は、ルータ・キューにおける「早期破棄」設定にもうまく働く。というのは、この経験的な方法は、破棄条件が迫っていることを検出するからである。言い換えれば、その時点でさらにトラフィックを付加すべきである場合に起こる恐れのあるような、破棄が行われる可能性がある状況を検出することができる。
【００２９】
他の変化形では、エンドポイント同士が接続されている間、パケット待ち時間、ジッタ、およびパケット欠損率を監視することができ、いずれかのパラメータの下降傾向の検出に基づいて、追加的な試験パケットを送信し、接続を移動させるのにより適した時間位置を見つけることができる。
【００３０】
図10は、第1のエンドポイント1001が複数のパケット・スイッチ1003〜1005を通して第2のエンドポイント1006と通信するシステムを示している。各パケット・スイッチは、複数のパケット・キューを維持する。（上記に指摘したように、いくつかの装置では、各出力ポートごとに別個のキューを維持することができる）。例示のために、4つの異なる優先順位レベルが示されており、この場合、4が最高レベルであり、レベル1が最低レベルである。エンドポイント1001がネットワークを通したエンドポイント106との接続の開始を試みると仮定する。エンドポイント1001は、優先順位レベル2を使用して複数の「試験」パケットを送信する。図を見ると分かるように、パケット・スイッチ1003は負荷が軽く、キューがトラフィックに問題なく対処することができる。
【００３１】
しかし、パケット・スイッチ1004の負荷は重い。このスイッチでは、優先順位レベル1トラフィック用のキューは満杯であり、パケットが欠損し、待ち時間が生じている。同様に、エンドポイント1001によって優先順位レベル2で送信される試験パケットは、このキューをオーバフローさせ、パケットが欠損し、待ち時間が長くなっている。しかし、優先順位レベル3キュー（既存のリアルタイム・トラフィック）はまだ満杯ではなく、したがって、これらのパケットは所定の瞬間に影響を受けずにネットワーク内を転送される。本発明の一変化形によれば、ある時間間隔位置の間に送信された試験パケットが欠損し、および／または待ち時間が長いことを検出すると、エンドポイント1001は最低欠損率および／または最短待ち時間を有する時間位置を選択し、これらの位置を使用してパケットをスケジューリングする（パケットは次に、レベル3優先順位を使用して送信される）。
【００３２】
図10の各エンドポイントが、上述の機能のうちの1つまたは複数を実施するコンピュータ実行可能な命令を含むノード（すなわち、ネットワーク・インタフェースを有するコンピュータ）を含むと仮定する。
【００３３】
B.  交渉によるパケット配信
交渉によるパケット配信を使用してパケットを送信するネットワークでは、送信側ノードは、対象となる受信側ノードにクエリーを送信する。受信側ノードは、他の送信側ノードによってすでにどの送信時間間隔位置が割り当てられているか（あるいはどの送信時間間隔が利用可能であるか）を示す受信マップで応答する。送信側ノードは次に、すでに割り当てられている任意の時間位置を考慮して、受信側ノードに送信マップを提案する。受信側ノードは、提案された送信マップを受け入れるか、または他の送信マップを提案する。ノード同士が合意すると、送信側ノードは、提案された送信マップに従って送信を開始し、受信側ノードは、提案された送信マップをその割当てテーブルに組み込む。提案された配信スケジュールが2つのエンドポイント間で合意されているので、他の場合にはエンドポイントの近くのネットワーク・スイッチをオーバフローさせる恐れのある調和の取れていない競合が回避される。（いくつかの装置では、各ポートがそれ自体のキューを有するため、それぞれの異なるキュー上のトラフィックは衝突しない）。スケジュールが2つのエンドポイントによって決定されるので、ネットワーク・リソース間の調和を図るネットワーク調停者は必要とされない。一態様では、交渉は単一のLANスイッチ間でのみ行われる。
【００３４】
一態様では、送信側ノードは、提案された送信（たとえば、ビデオ・パケットのストリーミング）をサポートするのに送信側ノードが必要とする帯域幅を示す帯域幅要件を、対象となる受信側ノードに送信する。対象となる受信側ノードは、他の送信側にすでに割り当てられている時間間隔位置を評価した後、送信側に必要な帯域幅を維持しつつ、すでにスケジューリングされているパケットとの競合を回避するために送信側がパケットを送信すべきである時間位置を示している提案配信スケジュールで応答する。送信側はその後、提案された配信スケジュールに従ってパケットを送信する。
【００３５】
他の変化形では、送信側ノードは、送信側ノードがパケットを送信する時間として提案する時間に対応する時間間隔位置を示している提案配信スケジュールを、対象となる受信側に送信する。対象となる受信側は、提案された配信スケジュールに合意するか、または送信側の帯域幅要件を考慮した他の配信スケジュールを提案する。ノード同士が合意すると、合意された配信スケジュールに従って送信が行われる。このスケジュールは、送信の終了時に解放することができる。
【００３６】
一時的に図7を参照すると、送信間隔は、データ・パケットを送信することのできる時間の単位および（任意に）部分単位に区分することができる。図7の例では、任意の1秒の送信間隔（マスタ・フレーム）をそれぞれ持続時間が100ミリ秒のサブフレームに分解することができ、各サブフレームをそれぞれ持続時間が10ミリ秒の二次サブフレームにさらに分解することができる。各二次サブフレームは、持続時間が1ミリ秒の時間間隔位置に分割される。（前述のように、時間分解は任意の所望の粒度まで行うことができ、この説明はこの点に関して限定することを意図するものではない。）
【００３７】
一変化形によれば、スケジュール配信方式は、ネットワークにおける優先順位付けされるパケットに適用され、優先順位付けされない他のパケットはこの方式に含まれない。したがって、優先トラフィックおよび非優先トラフィックのみをサポートするシステムでは、スケジュール配信方式がすべての優先トラフィックに適用され、アドホック・ネットワーク・トラフィックは引き続き非優先的に配信される。言い換えれば、すべての優先トラフィックは、あらゆる非優先順トラフィックが配信される前に配信される。
【００３８】
図11を参照すると、段階1101で、送信側ノードは、ネットワーク内の対象となる受信側ノードに、受信マップに関するクエリーを送信する。受信マップ（図14参照）は、すでに他の送信側に割り当てられている時間間隔位置（またはまだ割り当てられていない時間位置、または送信の候補である時間位置）を示し、受信側ノードによって受信されるデータ構造である。より一般的には、受信マップは、対象となる受信側ノードへの送信が他の送信側と衝突しない時間間隔位置を何らかの形態で示すデータ構造である。このようなマップを表す多数の方法があるが、1つの手法は、各ビットが1つの時間間隔位置に相当し、"1"が、その時間位置が送信側ノードに割り当てられていることを示し、"0"が、その時間位置がまだ割り当てられていないことを示すビット・マップを使用する手法である。したがって、図11は、配信スケジュールの25個の時間位置を表し、ある時間間隔位置（図14では"x"で示されている）はすでに他の送信側に割り当てられている。
【００３９】
段階1102で、対象となる受信側ノードは、すでに他の送信側に割り当てられている時間位置はどれかを示す、図14に示されているような受信マップで応答する。これが、この受信側ノードに最初に送信を行う送信側である場合、受信マップは空である。同じ送信側に時間位置を事前に割り当てておき、より早い送信をサポートすることも可能である（すなわち、同じ送信側が同じ受信側との第2の接続を確立する必要がある）。
【００４０】
段階1103で、送信側は、対象となる受信側ノードに提案送信マップを送信する。提案送信マップは好ましくは、対象となる受信側ノードから受信された割り当てられた時間位置を考慮に入れるので、したがって、すでに割り当てられている時間位置が回避される。送信側は、すでに割り当てられている時間間隔位置を回避しつつ送信に必要な帯域幅をサポートするのに十分な時間位置を割り当てる。
【００４１】
電話音声接続をサポートするためにネットワーク上の2つのノード間に仮想接続を確立すると仮定する。ボイス・オーバーIP接続は、10ミリ秒おきに80バイト・パケット・ペイロードを使用する場合（パケット・ヘッダは含まない）、毎秒64キロビットの転送速度を必要とすることがある。ビデオ・ストリームは通常、ネットワークに高帯域幅要件を課す。イーサネットLAN上では、各パケットは最大で1,500バイトを含む。
【００４２】
段階1104で、対象となる受信側は、提案された送信マップを見直してそれに合意するか、または他のの送信マップを提案する。たとえば、送信側が帯域幅に関する交渉を行っている間に、対象となる受信側が、提案された時間位置のいくつかを他の送信側に割り当てた場合、新たに提案された配信スケジュールには衝突が存在する。この状況では、対象となる受信側は、送信側の帯域幅要件を維持する他のマップを提案することができる。
【００４３】
段階1105で、送信側は、合意された配信スケジュールに従って対象となる受信側に繰返し送信を行う。ボイス・オーバーIP接続をサポートするために、たとえば、送信側は、10ミリ秒おきに80バイト・パケットを送信することができる。ビデオ接続の場合、送信側はより頻繁に送信を行うことができる。最後に、段階1106で、送信側がもはや送信を続行しなくなると、受信側のマップは割当て解除される。それよりむしろ、トラフィックがもはや送信されていないことを気付くことによって、割当て解除が暗黙的に行われ得る。
【００４４】
2方向通信では、ノードAからノードBへの送信用の1つの接続およびノードBからノードAへの送信用の別の接続の、2つの別々の接続を確立しなければならない。本発明の原則について1方向送信に関して説明するが、2方向接続が必要とされる他のエンドポイントでも同じ段階が繰り返されることを理解されたい。
【００４５】
図12は、パケット配信時間について交渉する他の方法を示している。まず段階1201で、送信側は、対象となる受信側に帯域幅要件を送信する。たとえば、送信側は、パケット・サイズおよび／または帯域幅を示すことができ、対象となる受信側は、その帯域幅をサポートするのにどの時間位置を割り当てるべきかを判定することができる。段階1202で、対象となる受信側は、すでに割り当てられた時間位置を考慮した提案送信マップで応答する。
【００４６】
段階1203で、送信側は、提案された送信マップに合意し、それによって、対象となる受信側は、合意された時間位置に「ロックイン」し（この段階は省略することができる）、段階1204で、送信側は、合意されたスケジュールに従ってパケットを送信する。最後に、段階1205で、送信マップは、接続の終了時に割当てを解除される。
【００４７】
図13は、交渉によるパケット配信の他の変化形を示している。段階1301で、送信側ノードは、対象となる受信側に提案送信マップを送信する。段階1302で、対象となる受信側は、提案された送信マップに合意する（送信マップが、すでに割り当てられているマップに適合する場合）か、または提案された送信マップから推定することのできる送信側の帯域幅要件を満たす他のマップを提案する。たとえば、送信側が時間位置1、11、21、31、41などでの送信を提案した場合、送信側が10時間間隔おきに送信する必要があることは明白である。要求された位置が利用可能でない場合、対象となる受信側は代わりに時間位置2、12、22、32などを提案する。
【００４８】
段階1303で、送信側は、合意された配信スケジュールに従ってパケットを送信し、段階1304で、送信の終了時に送信マップが割当て解除される。
【００４９】
他の変化形では、送信側は帯域幅（たとえば、10ミリ秒おきに1つの1000バイト・パケット）を要求することができ、受信側は配置メッセージで応答する（たとえば、75番目の時間位置から始める）。受信側は、複数の代替案で応答することもできる（たとえば、75番目、111番目、または376番目の時間位置から始める）。送信側は、送信側が使用する予定である時間間隔位置（たとえば、111番目の時間間隔位置）で応答し、送信を開始する。この変化形は、本明細書で使用される語である「送信マップ」および「受信マップ」の送信の範囲内であることを意図する。
【００５０】
送信側および受信側のそれぞれに配信スケジュールに合意させるには、ノード間にある時間同期を生じさせ維持することが望ましい。図15は、ネットワーク内のノード間で配信スケジュールを同期させる1つの可能な手法を示している。
【００５１】
図15に示されているように、ネットワークは、スイッチ1502を通して接続された様々なエンドポイントを含んでいる。本発明の一変化形によれば、クロック源1504（たとえば、GPSによるクロック）が、スケジュール配信方式に参加する各ネットワーク・ノードに電線1505を通して結合されている。クロック源は、各ノードに送信され配信スケジュールを得るための基礎として使用されるパルスを発生させる。各ノードは、タイマ・カード、またはタイミング信号を使用して共通の基準系を確立することのできるその他の機構（たとえば、割込み駆動オペレーティング・システム）を含んでよい。したがって、この同期手段は、同期信号を各ノードに送信するための（ネットワークから分離されかつ離れた）物理的なワイヤを含んでよい。同期手段はさらに、同期信号を検出し複合するハードウェアおよび／またはソフトウェアを各ノードに含んでよい。
【００５２】
クロック・パルスは、パルスの開始時間に同期させられる時間位置を生成するために各ノードによって使用される合意された間隔（たとえば、1秒）に応じたパルスを含んでよい。あるいは、クロック源は、後で各ノードによって時間位置に分割される高周波数信号を生成することができる。他の手法ももちろん可能である。他の手法として、各ノードは、米国政府によって送信される無線信号のような共通の基準信号に（GPSまたはその他の手段を介して）同期させられる独自のクロック源を含んでよい。ワイヤ1505は、同軸ケーブル、またはクロック源を各ノードに接続するその他の手段を含んでよい。一変化形では、接続は、送信効果および遅延が回避されるように十分に短い距離（数百フィート）である。これらの同期手段はどれも他の同期手段とは独立に使用することができる。
【００５３】
時間位置および配信スケジュールをノード間で同期させる他の方法および手段は、あるノードに、そのノード上の同期パケットをネットワーク上で定期的に（たとえば、マルチキャストを介して）送信させることである。各ノードは、このパケットを受信し、それを使用して内部クロックを同期させて基準を得る。マルチキャスト手法の代わりとして、各参加ネットワーク・ノードに同期パケットを個別に送信し、その際にこのような送信に伴うスタガ遅延(stagger delay)を考慮するように、1つのネットワーク・ノードを構成することができる。たとえば、同期ノードは、ネットワーク上の第1のノードに同期パケットを送信し、次に、同じパケットをネットワーク上の第2のノードに送信し、このパケットは後で第2のノードによって受信される。この時間差を定量化し、それを使用して共通の基準点に戻すことができる。もちろん、他の手法も可能である。
【００５４】
図16は、交渉によるパケット配信方式では、送信側と受信側との間でデータ・パケットをより効率的にスケジューリングすることによって、輻輳をどのように低減させることができるかを示している。図16に示されているように、各送信側ノードは、他のノードによって送信されるパケットと衝突しない時間の間に配信されるようにパケットをスケジューリングするため、パケットが失われることはない。
【００５５】
C. ネットワーク接続装置
経験的にスケジューリングされるパケット配信方式を使用するネットワーク、および交渉によるパケット配信方式を使用するネットワークの原則を検討したが、2つのエンドポイント501および502が様々な種類のネットワーク上で通信しなければならない問題を示す図5を再び参照する。本発明の一変化形によれば、様々なネットワークにわたるエンドポイント間の仮想接続を容易にするネットワーク接続装置（NCD）が設けられている。
【００５６】
図17は、本発明の一変化形に従う1つまたは複数のネットワーク接続装置（NCD）1707、1708、および1710を含むシステムを示している。ネットワーク接続装置1708は、第1のネットワーク1704（この場合は、交渉によるパケット・スケジューリング技術を使用してパケットを他のノードに送信するLAN）および第2のネットワーク1703（この場合は、経験的なスケジューリング技術を使用するWAN）を相互接続する。これに関しては、NCD 1708は、ネットワーク1704とネットワーク1703とのプロキシとして働き、パケット配信プロトコルを変換して様々なパケット・スケジューリング技術間の通信を可能にする。NCD 1710はまた、ルータ1701および1706を通してLAN 1704をWAN 1703に接続する。同様に、NCD 1707はLAN 1709およびWAN 1703を相互接続する。
【００５７】
各NCDは別個の装置として示されているが、後述の各NCDの機能は、ルータまたはその他の要素のような、既存のネットワーク装置に付加されるソフトウェアおよび／またはハードウェア（たとえば、PLD、PALなど）を使用して実施することができる。NCD機能は、複数のDSL線をより大きなネットワーク構造に統合する装置であるDSLAM（DSLアクセス・マルチプレクサ）などのアクセス統合装置で実施することもできる。したがって、語「ネットワーク接続装置」またはNCDは、NCD状機能を、それらの機能が実施される特定のハードウェア、ソフトウェア、またはネットワーク要素とは無関係に実行する装置を暗示する語と理解すべきである。
【００５８】
エンドポイント1701は、エンドポイント1702と通信する必要があるとき、エンドポイント1702と交渉によるパケット配信スケジュールを開始する。LAN 1704における配信プロトコルは、要求されたエンドポイント1702のIPアドレスに基づいて、エンドポイント1702がLAN 1704内に存在しないと判定することができ、したがって、エンドポイント1702にアクセスするには、要求をNCD 1708を通してルーティングしなければならないと判定する。したがって、プロトコルは、要求をNCD 1708にルーティングし、NCD 1708は、エンドポイント1702にアクセスするには、経験的にスケジューリングされるWAN 1703上に存在するNCD 1707を通さなければならないと判定する。したがって、NCD 1708は、WAN 1703上でNCD 1707と経験的に判定されるプロトコル（上記の節Aを参照されたい）を開始する。言い換えれば、NCD 1708は、NCD 1707に試験パケットを送信し、NCD 1707に至るパスにおけるルータの過負荷を回避するにはどの時間位置が最も有利かを経験的に判定する。NCD 1708は次に、これらの経験的に判定された時間位置を交渉によるパケット配信プロトコル（上記の節Bを参照されたい）に応じた他の送信マップとしてエンドポイント1701に返す。同様に、NCD 1707は、エンドポイント1702と交渉による時間位置配信スケジュールを確立してLAN 1709上のパスを完成する。
【００５９】
一態様では、エンドポイントは、経験的に判定された時間間隔位置に従わなければならない。というのは、WANに経験的に望ましくない時間間隔を受け入れさせるのは困難である場合があるからである。しかし、すべてのシステムでこの制限に従う必要があるわけではない。
【００６０】
各NCDは、ネットワーク間のプロキシとして働くことに加え、（1）ネットワークに不適切に導入された、許可されていないより高い優先順位のトラフィックからの各ネットワークの保護；（2）パケットの暗号化／解読；（3）ネットワーク・アドレス変換（NAT）；（4）プロキシIPアドレス指定；（5）ファイアウォール保護；および（6）ネットワーク・チョーク・ポイントの過負荷を防止するための、帯域幅、種類などによるフロー全体および個々のフローの制御のような他の任意の機能を実行することができる。いくつかの態様では、NCD 1708のどちらの側にでもルータを配置するか、またはその代わりにNCD機能をルータに組み込むことができる。以下に詳しく説明するこれらの機能のいくつかまたはすべては、汎用コンピュータ上で実行されるソフトウェアで実施することができる。
【００６１】
図18は、交渉によるパケット配信ネットワーク内のエンドポイントとWAN 1703のような経験的にスケジューリングされるパケット網を横断しなければならない他のネットワークとの接続を開始する方法の各段階を示している。
【００６２】
段階1801で、交渉による配信エンドポイント（たとえば、LAN 1704におけるエンドポイント1701）は、経験的にスケジューリングされるネットワークを介してのみアクセスできるネットワーク内に存在するエンドポイント（たとえば、WAN 1703を介したエンドポイント1702）との仮想接続（たとえば、ボイス・オーバーIP回線）を要求する。LAN 1704におけるネットワーク・プロトコルは、要求されたエンドポイントのIPアドレスに基づいて、そのエンドポイントがLAN 1704内に位置しておらず、そのためNCD 1708を通してアクセスしなければならないと判定することができる。したがって、ネットワーク・プロトコルは要求を（たとえば、図17には示されていないルータを通して）NCD 1708に送信する。
【００６３】
段階1802で、NCD 1708は、上記の節Bに記載されているように、提案された送信マップを含んでよい要求、または対象となる受信側から与えられる関連する送信マップについての帯域幅要求を受信する。その後、NCD 1708は、上記に節Aで説明した経験的にスケジューリングされる配信方式を使用してNCD 1707との接続を開始する。言い換えれば、NCD 1708は、様々な時間位置でパケットをNCD 1707に送信し、どの時間位置が送信に有利であるかを経験的に判定する。さらに、NCD 1707は、NCD 1707とNCD 1708との間の経験的に判定された時間位置に整合する、エンドポイント1702との交渉による配信スケジュールを開始する。
【００６４】
段階1803で、NCD 1708は、経験的データを得て、交渉による送信マップ（たとえば、図14を参照されたい）に変換してエンドポイント1701に返す。エンドポイント1701が、好ましい経験的データに一致するある送信マップを提案した場合、NCDは、提案された送信マップが受け入れられることを示すことができる。経験的に判定された有利な時間位置に整合しないある送信マップをエンドポイント1701が提案した場合、NCD 1708は、経験的データに整合する他の送信マップを返す。これに対して、エンドポイント1701が帯域幅を要求した場合、NCDは、この帯域幅要件を満たし、経験的なスケジューリング判定に整合する送信マップを提案する。
【００６５】
その後、段階1804で、交渉によるエンドポイントは、NCD 1708から受信された送信マップに従ってエンドポイント1702に送信を行う。
【００６６】
段階1805で、接続は、いずれかのエンドポイントが回線の終了を要求したときにNCD 1708によって切断される。
【００６７】
2方向接続の場合、経験的にスケジューリングされるネットワークにおけるエンドポイントは、交渉による配信ネットワークにおけるエンドポイントとの接続を確立することが必要になる場合がある。その後、図18に示されている各段階が逆方向に（エンドポイント1702からエンドポイント1701に）繰り返され、ボイス・オーバーIP接続に必要とされる場合がある2方向接続が確立される。
【００６８】
図19は、NCDの1つの考えられる構成を示している。ユニット1901は、メモリ、CPU、および入出力回路を含んでよい。CPUは、上記に説明し図18に示した機能を実行するようにソフトウェアによってプログラムされている。入出力回路は、上記に概略的に説明した原則を使用して、2方向接続を確立するのに使用できるIP電話のような様々な装置に結合されたスイッチ1903に結合させてもよい。装置1901は、GPSまたはセルラCDMA源のような、アップリンクおよび／または外部クロック源からタイミングを受信してもよい。
【００６９】
すべてのフレームの位相が、互いに独立したものであってよく、共通のクロックから得るかまたは共通のクロックに合わせるだけでよいことを理解されたい。様々なエンドポイントが各フレームの位相を互いに同期させる必要はない。言い換えれば、各時間間隔が相対的に同期しているかぎり、各時間間隔を様々なエンドポイント間で固有に識別する必要はない。この原則は、異なる位相を有するが共通のクロックを参照するフレームに関連して指定された時間間隔を、2つのエンドポイントがどのように参照できるかを示す図20に示されている。（各エンドポイントを実際に共通のクロックに同期させる必要はないが、図20は、各エンドポイントについて理解するために同期状態を示している）。
【００７０】
図20に示されているように、エンドポイントA（図20の下部）が、パケット遅延を招くWANを通してエンドポイントB（図20の上部）と通信する必要があると仮定する。各エンドポイントは、WANとの接続に対処する関連するNCDを有している。図20の上部を横切るタイムラインおよび図20の下部を横切るタイムラインが「絶対」時間を表し、すなわち、図20の上部の時間間隔1が、絶対時間において図20の下部の時間間隔1と同じ瞬間に現れると仮定する。さらに、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として識別する。図20の上部のタイムラインおよび図20の下部のタイムラインが互いに対して移動しないかぎり、システムは、パケット遅延に対処することができ、かつどの時間間隔位置を使用してパケットを送信すべきであるかについて合意することができる。もちろん、他の手法を使用してよい。
【００７２】
上記に明示的に示されていないが、ネットワークは、電話番号のデータベースを維持しその電話番号をIPアドレスにマップする1つまたは複数のソフト・フォン・スイッチ（本質的に、ネットワークに結合された小形コンピュータ）を含んでよい。対象となる受信側に電話呼出しを行う場合、フォン・スイッチと連絡が取られ、受信側の電話番号に対応するIPアドレスが判定される。本発明のシステムおよび方法は、ビデオ・グレードのデータをネットワークを介して送信するビデオ端末；コンピュータ・データを送信するコンピュータ端末；または他の任意の種類のデータと一緒に使用することもできる。
【００７３】
本明細書で説明した方法段階はどれも、コンピュータ・ソフトウェアで実現し、汎用または専用ハードウェアまたはプロセッサ（PLD、PGA、ルータ、スイッチなど）またはコンピュータで実行されるコンピュータ可読媒体上に記憶することができ、このようなコンピュータ可読媒体は、対象となる発明の範囲内に含まれる。本明細書で使用される語「プロセッサ」は、これらの様々な種類の装置のいずれかを含むものと理解すべきである。特許請求の範囲内の方法またはプロセス段階に関連する番号付けは、便宜上のものに過ぎず、特定の順序またはシーケンスを必要とするものと解釈すべきではない。
【図面の簡単な説明】
【００７４】
【図１】バースト状態のパケットがパケット・スイッチでオーバフロー状態を生じさせ、パケット喪失に至る問題を示す。
【図２】ネットワーク輻輳が、2組のエンドポイントがバースト状態の下で共通のネットワーク・リソースを共用するボトルネックを、どのように生じさせるかを示す。
【図３】4つのLANエンドポイントが、LANスイッチを通して他のLANエンドポイントと通信し、場合によってはスイッチにおいて輻輳を生じさせることを示す。
【図４】図3のLANスイッチでの輻輳によってパケット（フレーム）が失われる問題を示す。
【図５】経験的にスケジューリングされるパケット・スケジューリング技術を使用するWAN 503、および交渉によるパケット・スケジューリング技術を使用するLAN 504を含む、2つの相互接続されたネットワークを示す。
【図６】スケジューリングされたデータ（リアルタイム・レベル）；試験パケット（発見レベル）；およびその他のネットワーク・トラフィック（データ・レベル）にそれぞれの異なる優先順位レベルを割り当てる1つの手法を示す。
【図７】発見スケジュールを、マスタ・フレーム；サブフレーム；および二次サブフレームに分解することのできるフレーム構造を示す。
【図８】WANなどのネットワーク上で経験的なスケジューリングを実行する段階を有するフローチャートを示す。
【図９】第1のエンドポイントから第2のエンドポイントへの試験パケットの配信スケジュールを使用するシステムを示す。
【図１０】リアルタイム・トラフィック（優先順位3）用のキューが、あるパケット・スイッチではほぼ満杯であるが、それでもトラフィックがネットワークを通過することができるシステムを示す。
【図１１】LANなどのネットワーク上の送信側ノードと対象となる受信側ノードとの間の送信に関する、交渉による配信スケジュールの調和を図る1つの方法を示す。
【図１２】送信側ノードと対象となる受信側ノードとの間の送信に関する配信スケジュールの調和を図る第2の方法を示す。
【図１３】送信側ノードと対象となる受信側ノードとの間の送信に関する配信スケジュールの調和を図る第3の方法を示す。
【図１４】所定の送信間隔に関する1つの考えられる受信マップを示す。
【図１５】ネットワーク・ノード間で配信スケジュールを同期させる方式を示す。
【図１６】本発明の原則を使用することによってネットワーク輻輳を回避し、ネットワークにおいてパケットをより効率的にスケジューリングするにはどうするかを示す。
【図１７】本発明の一変化形によるネットワーク接続装置（NCD）を含むシステムを示す。
【図１８】交渉によるパケット配信ネットワーク内のエンドポイントと、経験的にスケジューリングされるパケット配信ネットワーク内のエンドポイントとの間の接続を開始する方法の各段階を示す。
【図１９】ネットワーク接続装置（NCD）の1つの考えられる構成を示す。
【図２０】異なる位相を有するが共通のクロックを参照するフレームに関連して指定された時間間隔を、2つのエンドポイントがどのように参照できるかを示す。
【図１】
2008516552.tif 000003
【図２】
2008516552.tif 000004
【図３】
2008516552.tif 000005
【図４】
2008516552.tif 000006
【図５】
2008516552.tif 000007
【図６】
2008516552.tif 000008
【図７】
2008516552.tif 000009
【図８】
2008516552.tif 000010
【図９】
2008516552.tif 000011
【図１０】
2008516552.tif 000012
【図１１】
2008516552.tif 000013
【図１２】
2008516552.tif 000014
【図１３】
2008516552.tif 000015
【図１４】
2008516552.tif 000016
【図１５】
2008516552.tif 000017
【図１６】
2008516552.tif 000018
【図１７】
2008516552.tif 000019
【図１８】
2008516552.tif 000020
【図１９】
2008516552.tif 000021
【図２０】
2008516552.tif 000022
【手続補正書】
【提出日】平成19年7月13日(2007.7.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プロセッサにプログラムを実行させることによって、第1のネットワーク上の発信側ノードから第2のネットワーク上の宛先ノードへ第1のネットワークと第2のネットワークを介してデータ・パケットを送信する方法であって、以下の段階を含む方法：
（1）第1のネットワークを介してデータ・パケットを配信するために交渉によるパケット配信方式に従って接続を確立するための要求を第1のネットワーク上の発信側ノードから受信する段階；
（2）データ・パケットが、経験的にスケジューリングされるパケット配信機構を使用する第2のネットワークを介して宛先ノードに宛てたデータ・パケットであると判定する段階；および
（3）段階（2）に応じて、経験的にスケジューリングされるパケット配信機構を使用する第2のネットワーク上で接続を開始する段階。
【請求項２】
（4）経験的にスケジューリングされるパケット配信機構に適合する交渉によるパケット配信スケジュールを生成する段階；および
（5）交渉によるパケット配信スケジュールに従って発信側ノードからデータ・パケットを送信する段階
をさらに含む、請求項1記載の方法。
【請求項３】
第1のネットワークはローカル・エリア・ネットワークを含み、第2のネットワークはワイド・エリア・ネットワークを含む、請求項2記載の方法。
【請求項４】
段階（3）が、
（a）複数の試験パケットを第2のネットワーク上で様々な時間間隔位置で送信する段階；
（b）試験パケットに関連するパケット待ち時間率または損失率を評価する段階；および
（c）好ましいパケット待ち時間率または損失率を有する1つまたは複数の時間間隔位置を選択する段階
を含む、請求項1記載の方法。
【請求項５】
段階（1）が、第1のネットワークにおけるパケットの配信に関する提案された送信スケジュールを受信する段階を含む、請求項1記載の方法。
【請求項６】
段階（1）が、第1のネットワークにおけるパケットの配信に関する帯域幅要求を受信する段階を含む、請求項1記載の方法。
【請求項７】
段階（3）が、第1のネットワークの外部の装置で実行される、請求項1記載の方法。
【請求項８】
第2のネットワークに結合された第3のネットワーク上の第2の発信側ノードについて段階（1）〜（3）を繰り返す段階をさらに含む、請求項1記載の方法。
【請求項９】
第1および第2のネットワーク上で送信されるパケットの時間位相同期を確立する段階をさらに含む、請求項1記載の方法。
【請求項１０】
時間同期を確立する段階は、全地球測位システム（GPS）受信機を使用する段階を含む、請求項9記載の方法。
【請求項１１】
プロセッサによって実行された場合に、以下の段階：
（1）第1のネットワークを介して交渉によるパケット配信方式に従ってデータ・パケットを配信するための接続を求める要求を、第1のネットワーク上の発信側ノードから受信する段階；
（2）データ・パケットが、経験的にスケジューリングされるパケット配信機構を使用する第2のネットワークを介して配置された宛先ノードを対象とするパケットであると判定する段階；および
（3）段階（2）に応じて、経験的にスケジューリングされるパケット配信機構を使用する第2のネットワーク上で接続を開始する段階
を実行するコンピュータ命令を含むコンピュータ可読媒体。
【請求項１２】
コンピュータ命令が、さらなる段階：
（4）経験的にスケジューリングされるパケット配信機構に適合する交渉によるパケット配信スケジュールを生成する段階；および
（5）交渉によるパケット配信スケジュールに従って発信側ノードからデータ・パケットを送信する段階
を実行する、請求項11記載のコンピュータ可読媒体。
【請求項１３】
コンピュータ命令が、さらなる段階：
（a）複数の試験パケットを第2のネットワーク上で様々な時間間隔位置で送信する段階；
（b）それぞれの異なる時間間隔位置に関連するパケット待ち時間率または損失率を評価する段階；および
（c）好ましいパケット待ち時間率または損失率を有する1つまたは複数の時間間隔位置を選択する段階
を実行する、請求項12記載のコンピュータ可読媒体。
【請求項１４】
段階（1）が、第1のネットワークにおけるパケットの配信に関する提案された送信スケジュールを受信する段階を含む、請求項11記載のコンピュータ可読媒体。
【請求項１５】
段階（1）が、第1のネットワークにおけるパケットの配信に関する帯域幅要求を受信する段階を含む、請求項11記載のコンピュータ可読媒体。
【請求項１６】
コンピュータ命令が、第2のネットワークに結合された第3のネットワーク上の第2の発信側ノードについて段階（1）〜（3）を繰り返すさらなる段階を実行する、請求項11記載のコンピュータ可読媒体。
【請求項１７】
コンピュータ命令が、第2のネットワーク上に配置された装置との時間位相同期を確立するさらなる段階を実行し、そのため、第2のネットワーク上で送信されるデータ・パケットをネットワーク上で相対的に時間に間に合うように同期させることができる、請求項11記載のコンピュータ可読媒体。
【請求項１８】
メモリ；
互いに交渉してパケットが送信される時間間隔位置を確立することによって接続を形成するノードを有する第1のネットワークにおける発信側ノードから、パケットが送信される時間間隔位置を経験的に判定することによって接続を形成するノードを有する第2のネットワークを介して配置された宛先ノードとの接続を確立するための要求を受信する手段(1)；
要求に応答して、第2のネットワークを介して複数のパケットを送信し、データ・パケットを送信するのに望ましい第2のネットワーク上の1つまたは複数の時間間隔位置をパケットから経験的に判定する手段(2)；および
宛先ノードとの接続を確立するために発信側ノードに応答を送信する手段(3)
を含む、第1のネットワーク上の発信側ノードから第2のネットワーク上の宛先ノードへ第1のネットワークと第2のネットワークを介してデータ・パケットを送信する装置。
【請求項１９】
前記手段(2)が、複数の時間間隔位置候補上で複数のパケットを同時に送信することを含むものである、請求項18記載の装置。
【請求項２０】
前記手段(2)が、複数の時間間隔位置候補上で複数のパケットを順次送信することを含むものである、請求項18記載の装置。
【請求項２１】
第2のネットワークに結合された第2の装置と時間間隔位置とを同期させるための手段をさらに含む、請求項18記載の装置。
【請求項２２】
同期させるための手段は全地球測位システム（GPS）受信機を含む、請求項21記載の装置。
【請求項２３】
前記手段(1)〜(3)およびメモリが、ネットワークにおいてデータ・パケットをルーティングするように設定可能なルータ内に配置される、請求項18記載の装置。
【請求項２４】
前記手段(1)〜(3)およびメモリが、複数のネットワーク要素からのデータを統合するために設定可能なネットワーク統合装置内に配置される、請求項18記載の装置。
【国際調査報告】
2008516552.tif 000023