(57)【要約】  本発明の種々の実施形態は、資源プールから割り当て、様々な期間使用し、かつ最終的に資源プールに返すことのできる計算資源のプールを管理するための効率的かつ柔軟な方法およびシステムに向けられる。本発明の特定の実施形態は、短期間の通信接続に使用されるエフェメラルポートを効率的に管理するための方法およびシステムに向けられる。本発明の一実施形態では、エフェメラルプロトコルポートの大空間を格納しかつ管理するために、ポートテーブルの配列を使用する。各ポートテーブルは循環バッファであり、その各エントリは通信ポートを一意に識別するポート番号、ポートを即時に再割当てすることを可能にするシーケンス番号、およびポートに関連付けることのできる任意の他の追加的プロトコル特定的情報を含む。
2009532807.tif 000002
【特許請求の範囲】
【請求項１】
各計算資源が資源のプールから割当て可能であり、割当ての後ある期間使用され、割当ておよび使用の後で割当て解除されてプールに返される、計算資源のプールを管理するための方法であって、
資源テーブルのエントリに資源記述および資源再割当て許可情報を格納するステップと、
資源割当て要求を受け取ると、
前記資源テーブルの利用可能なエントリに含まれる資源識別子および資源再割当て許可情報を返すステップと、
前記資源テーブルの前記利用可能なエントリを解放するステップと、
資源の割当て解除要求を受け取ると、
資源の識別子および資源再割当て許可情報を前記資源テーブルの次の空きエントリ内に格納するステップと、
を含む方法。
【請求項２】
前記資源テーブルが、
エントリの配列と、
資源識別子および資源再割当て許可情報を格納することのできる、前記資源テーブルの空きエントリを指す空きポインタと、
資源識別子および資源再割当て許可情報を含む前記資源テーブル内の利用可能なエントリを指す利用可能ポインタと、
を含む循環バッファである、請求項１に記載の方法。
【請求項３】
前記資源テーブルの利用可能なエントリ内に格納された資源識別子および資源再割当て許可情報を返す前記ステップが、
前記利用可能ポインタによって指定された前記資源テーブル内のエントリにアクセスするステップと、
前記アクセスされたエントリが有効な資源識別子を含む場合、
前記エントリ内に格納された資源識別子および資源再割当て許可情報を返すステップと、
前記エントリ内の資源識別子に無効値を設定するステップと、
前記資源テーブル内の次のエントリを指すように、前記利用可能ポインタを前進させるステップと、
前記アクセスされたエントリが有効な資源識別子を含まない場合、
失敗の指標を返すステップと、
をさらに含む、請求項２に記載の方法。
【請求項４】
前記資源テーブルの次の空きエントリ内に資源の識別子および資源再割当て許可情報を格納する前記ステップが、
前記空きポインタによって指定されたエントリ内に資源識別子および資源−再割当て許可情報を格納するステップと、
前記資源テーブルの次のエントリを指すように、前記空きポインタを前進させるステップと、
をさらに含む、請求項２に記載の方法。
【請求項５】
現在第１の資源テーブルエントリを指定しているポインタが、ポインタの値を変更することによって、前記資源テーブルエントリの配列内で前記第１の資源テーブルエントリより後に来る資源テーブルエントリを指定するように前進し、第１のエントリの資源テーブルエントリ配列インデックスより、エントリ１つ分大きい資源テーブルエントリ配列インデックスを持つ第２のエントリが、前記第１のエントリの後に続き、かつ資源テーブルエントリの配列内の最初のエントリが資源テーブルエントリの配列の最後のエントリの後に続く、請求項２に記載の方法。
【請求項６】
資源は、一意にアドレス指定可能なエンティティと関連付けられるように割り当てられ、
前記一意にアドレス指定可能なエンティティは、エンティティグループのスパン集合に分割され、
別々の資源テーブルに、各エンティティグループのための割当て可能な資源が格納される、
請求項２に記載の方法。
【請求項７】
エンティティに関連付けられる資源テーブルは、エンティティのアドレスをハッシュして、資源テーブル識別子を生成することによって決定される、請求項６に記載の方法。
【請求項８】
請求項１に記載の方法を実現する、コンピュータ可読メモリに格納されたコンピュータ命令。
【請求項９】
前記計算資源が通信ポートであり、
資源再割当て許可情報がメッセージシーケンス番号である、
請求項１に記載の方法。
【請求項１０】
各通信ポートが通信ポートのプールから割当て可能であり、割当ての後ある期間使用され、割当ておよび使用の後で割当て解除されてプールに返される、通信ポートのプールを管理するための方法であって、
シーケンス番号と対を成す通信ポート記述を通信ポートテーブルのエントリに格納するステップと、
通信ポート割当要求を受け取ると、
前記通信ポートテーブルの利用可能なエントリ内に格納された通信ポート識別子およびシーケンス番号を返すステップと、
前記ポートテーブルの前記利用可能なエントリを解放するステップと、
通信ポートの割当て解除要求を受け取ると、
通信ポート識別子およびシーケンス番号を前記ポートテーブルの次の空きエントリ内に格納するステップと、
を含む方法。
【請求項１１】
前記ポートテーブルが、
エントリの配列と、
通信ポート識別子およびシーケンス番号を格納することのできる空きエントリを指す空きポインタと、
通信ポート識別子およびシーケンス番号を含む、前記ポートテーブル内の利用可能なエントリを指す利用可能ポインタと
を備える循環バッファである、請求項１０に記載の方法。
【請求項１２】
前記通信ポートテーブルの利用可能なエントリ内に格納された通信ポート識別子およびシーケンス番号を返す前記ステップが、
前記利用可能ポインタによって指定された前記ポートテーブル内のエントリにアクセスするステップと、
前記アクセスされたエントリが有効な通信ポート識別子を含む場合、
前記エントリ内に格納された通信ポート識別子およびシーケンス番号を返すステップと、
前記エントリの通信ポート識別子を無効値に設定するステップと、
前記ポートテーブル内の次のエントリを指すように、前記利用可能ポインタを前進させるステップと、
前記アクセスされたエントリが有効な通信ポート識別子を含まない場合、
失敗の指標を返すステップと、
をさらに備える、請求項１１に記載の方法。
【請求項１３】
前記ポートテーブルの次の空きエントリに通信ポート識別子およびシーケンス番号を格納する前記ステップが、
前記空きポインタによって指定されたエントリに通信ポート識別子およびシーケンス番号を格納するステップと、
前記資源テーブルの次のエントリを指すように、前記空きポインタを前進させるステップと、
をさらに備える、請求項１１に記載の方法。
【請求項１４】
現在第１のポートテーブルエントリを指定しているポインタが、ポインタの値を変更することによって、前記ポートテーブルエントリの配列内で前記第１のポートテーブルエントリより後に来るポートテーブルエントリを指定するように前進し、第１のエントリのポートテーブルエントリ配列インデックスより、エントリ１つ分大きいポートテーブルエントリ配列インデックスを持つ第２のエントリが、前記第１のエントリの後に続き、かつポートテーブルエントリの配列内の最初のエントリがポートテーブルエントリの配列の最後のエントリの後に続く、請求項１１に記載の方法。
【請求項１５】
通信ポートは、接続アドレスを有する通信接続と関連付けられるように割り当てられ、
前記通信接続は接続グループのスパン集合に分割され、
別々のポートテーブルに、各接続グループのための割当て可能なポートが格納される、
請求項１１に記載の方法。
【請求項１６】
接続に関連付けられるポートテーブルは、前記接続のアドレスの非ローカルポートアドレス部分をハッシュして、ポートテーブル識別子を生成することによって決定される、請求項１５に記載の方法。
【請求項１７】
請求項１に記載の方法を実現する、コンピュータ可読メモリに格納されたコンピュータ命令。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータアルゴリズムおよび資源の管理に関し、特に、プールから割り当てられ、かつ種々の使用期間後に割当てを解除され、再割当てのためにプールに返されるコンピュータシステム内の計算資源を、低い計算オーバヘッドおよび最小限の遅延で管理するための方法およびシステムに関する。
【背景技術】
【０００２】
本発明は一般的に、コンピュータシステムの多種多様なタイプの計算資源のいずれかの管理に向けられ、かつそれに適用可能である。本発明を以下で、特定のクラスの通信資源管理の問題に関連して説明するが、そのクラスの問題は、単に本発明を説明するのに便利な文脈であるにすぎない。
【０００３】
コンピュータシステム間でデータを交換するために、多種多様なタイプの通信プロトコルが開発されてきた。例示的通信プロトコルとして、低レベルインターネットプロトコル（「ＩＰ」）で信頼できるシーケンス番号付き順序メッセージ交換を達成し、かつＩＰと共にインターネットのための主要通信基盤をもたらす、中レベルプロトコルである伝送制御プロトコル（「ＴＣＰ」）がある。種々のネットワークプラットフォームで、イーサネットベースのローカルエリアネットワークのためのプロトコル、および大容量記憶装置構成要素を相互接続しかつホストコンピュータを大容量記憶装置と相互接続するためにしばしば使用されるファイバチャネル通信のためのプロトコルを含め、多くの追加のタイプのコンピュータプロトコルが現在使用されている。以下の説明は特定のＴＣＰのような実施例に基づくが、本発明はＴＣＰ関連の通信資源への適用に限定されず、多種多様なタイプのハードウェアおよびソフトウェア上で種々の通信プロトコルをサポートする任意の数の様々なタイプのコンピュータシステム内の通信資源を管理するための一般的用途を見出す。
【０００４】
現在の説明では、用語「通信ポート」とは一般的に、２つのコンピュータシステム間の通信接続を確立するために使用される資源を指す。一般的にこれは、プロトコルアドレスに関連付けられる所与のプロトコルの通信エンドポイントを識別する、プロトコルポートと呼ばれる論理資源である。通信ポートは、コンピュータシステムを通信媒体にインタフェースする物理的接続、内部データバスと通信媒体コントローラもしくは多くの他の物理的オペレーティングシステムとの間の内部インタフェース、またはコンピュータシステムの内部処理構成要素と通信媒体との間のデータおよびコマンドの交換に関係するプロトコルインタフェースとすることもできる。本発明を説明することを目的として、用語「通信ポート」とは、コンピュータシステムとリモートコンピュータシステムとの間の通信接続を確立することに関係するコンピュータシステムによって直接的または間接的に計算資源として取り扱われるインタフェースを指し、任意の所与のシステムの通信ポートの厳密な性質は、システムのハードウェアおよびソフトウェア構成要素によって異なる。
【０００５】
図１Ａ〜Ｉは、現在利用可能な通信資源管理戦略に見られる通信ポート、通信接続、および複数の問題を示す。図１Ａ〜Ｉは全て、図１Ａに関連して下述するのと同様の図解上の慣例を使用する。
【０００６】
図１Ａは、クライアントコンピュータとサーバコンピュータとの間の通信の単純な抽象的コンピュータ環境を示す。図１Ａに示す通り、クライアントコンピュータ１０２およびサーバコンピュータ１０４は両方とも一定数の通信ポートを使用し、リモートコンピュータとの通信トランザクションまたは接続を確立しかつ実行するために、クライアントコンピュータ１０２によって使用されるポート１０６のような、各ポートは小さい正方形によって表わされる。図１Ａ〜Ｉの実施例では、クライアントコンピュータ１０２は、クライアントコンピュータに関連付けられるカラム１０８に配列された一定数のポートを使用し、サーバコンピュータ１０４は、サーバコンピュータに関連付けられるポートのカラム１１０に配列された一定数のポートを使用する。ポートは、特定のタイプのプロトコルスタックおよびネットワークシステムに関するコンピュータシステム内の相互接続資源を表わす論理エンティティであり、各々がコンピュータシステム内でポート番号によって一意に識別される。コンピュータシステムは、プロトコルを使用してリモートコンピュータとの接続を、存在するポートの個数と同じ数だけ同時に実行することができる。一般的に、ポートは種々のポートクラスに分割される。図１Ａで破線の長方形１１２によって示される１つのクラスは、比較的短期間の接続に使用される１組のエフェメラルポートを備える。エフェメラルポート１１２のクラス内のポート１１３〜１１７は、エフェメラルポートのプールを構成し、比較的高い頻度でそこからポートが割り当てられ、かつ割当て解除されたポートがそこに返される。残りのポート１０６および１２０〜１２７は一般的に、特殊な用途、接続、およびタスクのために予約される。
【０００７】
コンピュータシステムで利用可能なポートの総数は、極めて大きくなることがある。しかし、本発明を説明する目的のために、コンピュータシステム内で利用可能なポートの個数は一般的に無関係である。代わりに、関連するものは、ポートの個数が固定しており、かつシステムの動作中に高い頻度で確立されかつ終了される短期間の接続に必要なエフェメラルポートの個数は一般的に、ポートの総数よりかなり小さい固定数であるということである。図１Ａで破線の長方形１１２内のポート１１３〜１１７によって表わされるエフェメラルポートは、潜在的障害を意味する。エフェメラルポートは、エフェメラルポートの割当ておよび他のエフェメラルポート管理操作における随伴する計算オーバヘッドおよび遅延を最小限に止めて、短期間の接続のスループットをできるだけ高く維持するために、コンピュータシステムによって注意深く管理する必要のある計算資源のプールを表わす。
【０００８】
図１Ｂ〜Ｆは、例示的クライアント／サーバ通信（プロトコル）接続を示す。図１Ｂで、クライアントコンピュータはエフェメラルポート１１２のプールからポート１１４を選択し、それを通して、専用サーバポート１３０を介してのサーバコンピュータ１０４への接続を確立する。接続確立プロトコルの一環として、クライアントコンピュータから選択されたポート１１４を介して、サーバコンピュータの専用ポート１３０にメッセージ１３２が送信される。図１Ｂおよび後続の図において、接続のために割当て済みのポートは、そのポートが現在割当てに利用できないことを示すために、陰影を付けて示されることに留意されたい。
【０００９】
次に、図１Ｃに示すように、サーバは初期メッセージに対し、選択されたクライアントポート１１４に向けられたサーバコンピュータによる返信メッセージ１３４で応答する。図１Ｂおよび１Ｃに示す例示的接続確立プロトコルでは、接続を確立するためにクライアントとサーバとの間で２つのメッセージが交換されるだけである。しかし、ＴＣＰプロトコルのような一般的に使用されるプロトコルでは、接続を確立するために、３つ以上のメッセージの交換が必要であるかもしれない。図１Ｂ〜Ｃに示す例示的な２メッセージ接続プロトコルは、簡潔を期すと共に図を分かり易くするために使用するものである。
【００１０】
次に、図１Ｄに示すように、通信トランザクションを完結するために、クライアントとサーバコンピュータとの間で両方向に追加メッセージ１３６〜１４０が交換される。例えばファイルが転送され、データベースがアクセスされ、データが返送され、ウェブページに基づく対話が実行され、または多くの他のそのような活動が、通信接続を介するデータの交換を通して実行され得る。メッセージの順序付けを容易にするために、各メッセージにシーケンス番号が関連付けられる。図１Ｂ〜１Ｆの実施例では、クライアントとサーバコンピュータとの間で交換される３番目ないしｎ番目のメッセージ１３６〜１４０が、接続を通して行なわれる高レベルのトランザクションに関連するデータを搬送する。最後に、図１Ｅに示すように、高レベルトランザクションが完了するときに、接続が終了することを示すために、サーバは最後の（ｎ＋ｌ）番目のメッセージ１４２をクライアントコンピュータに送信することができる。現在使用されている多くのプロトコルで、接続の終了は複数のメッセージの交換を含み、クライアントまたはサーバコンピュータのどちらかでも開始することができる。図１Ｅに示す単純な単一メッセージ終了は、図を分かり易く簡潔にするのに便利である。
【００１１】
終了メッセージを受け取ると、図１Ｆに示すように、クライアントコンピュータは、サーバコンピュータへの接続が終了されるとみなす。しかし、接続がそれらを通して行なわれたクライアントポート１１４およびサーバポート１３０は、しばらくの間、クライアントコンピュータをサーバコンピュータに再接続するために利用不能に維持される。クライアントポートおよびサーバポートの識別子は、部分的に、クライアント／サーバ接続を識別するのに役立つ。接続が終了すると、とりわけ遅延したメッセージまたは反復メッセージの正しい処理を可能にするために、ある期間が経過し終わるまで、新しい同一識別接続を再確立することができない。同一エフェメラルクライアントポートを通してサーバへの接続を直ちに再確立する試みがクライアントによってなされた場合、下述する例外を除いて、サーバは一般的に接続要求を拒絶する。
【００１２】
本質的に、ポートが再割当てのために利用できないある固定長期間または待ち時間を示すために、各ポートにタイマ１４４が関連付けられると考えることができる。終了した接続のポートに関連付けられる上記待ち時間のため、接続要求が潜在的に失敗に終わることなく、ポートが即座に再利用可能または再割当て可能になるための方法が幾つか存在する。図１Ｇは、第１の再割当て許可イベントを示す。図１Ｇに示すように、タイマ１４４が満了すると、その時点でポート１１４は利用可能なエフェメラルポートのプールに再加入することができる。図１Ｈは、ポート１１４を再割当てに利用可能にする第２の再割当て許可イベントを示す。図１Ｈに示すように、エフェメラルポートを通して行なわれた前回の接続の最終メッセージのシーケンス番号１４７より大きいシーケンス番号１４８を持つ次の接続要求１４６が、そのエフェメラルポートを通して伝送された場合には、前回そのエフェメラルポートを介してクライアントコンピュータに接続された同じサーバおよびサーバポートに送信されたときでも、接続要求は拒絶されない。このシーケンス番号に基づく例外は、最直近に終了した接続を通して伝送された遅延メッセージによるシーケンス番号付けの曖昧さを防止するように、コンピュータシステム間の同一識別接続の迅速な再確立を可能にする。第３の再割当て許可イベントは、エフェメラルポートが異なるサーバに、または同一サーバの異なるポートに接続要求を送信するために使用され、したがって結果的に得られる接続が、最直近に終了した接続のアイデンティティを共有しない場合である。
【００１３】
特定の第１のシーケンス番号が第２のシーケンス番号より大きいか否かは、シーケンス番号が使用される特定の通信プロトコルに依存する。例えば特定の事例では、シーケンス番号は、固定サイズの符号無し整数によって表わされる。順序付けられたシーケンス番号の集合は、最大値の符号無し整数から０に戻る。シーケンス番号に８ビットの符号無し整数が使用される場合、整数０は整数２５５のすぐ後に続き、整数３は整数２５５から４つのシーケンス番号だけ後に続く。一方、整数２５５は整数３から２５２個のシーケンス番号だけ後に続く。したがって、「より大きい」に対するさらなる定義が無ければ、任意の値の第１のシーケンス番号が第２のシーケンス番号の後に来ることができ、またはより大きいものとすることができる。潜在的曖昧さを解消する１つの方法は、１つのシーケンス番号から別の番号までの最大距離を定義することである。現在説明する実施例で、最大距離を１０に設定した場合、３は２５５の後に来るが、２５５は３の後に来ない。そのような曖昧さを解消するための多くの他の技術を使用することもできる。
【００１４】
一定の限定された個数のエフェメラルポートが短期間の接続に利用可能であるので、エフェメラルポートのプールは全体で、潜在的に制限される計算資源を表わす。図１Ｉは、コンピュータシステム内の全てのエフェメラル通信ポートの割当てによって生じ得る障害を示す。図１Ｉに示すように、エフェメラルポート１１３〜１１７が全てリモートサーバへの接続に割り当てられ、現在そのために使用されているということが起こるかもしれない。この場合、エフェメラルポートを割り当てようとするその後の試みは失敗する。換言すると、コンピュータシステムのための同時接続帯域幅は、それ以上拡大することができない。接続を形成する追加の試みは失敗し、結果的に通信の遅延を生じ、かつ高レベルのトランザクションの失敗さえも生じ、それは次にさらなる計算オーバヘッド、通信遅延、および大規模なシステム障害さえも引き起こすおそれがある。たとえ接続が終了しても、エフェメラルポート資源プールは、かなりの期間、完全に使用し尽くされた状態を維持するかもしれない。図１Ｊは、図１Ｉに示されたシステムの通信接続の１つが終了した後の状態を示す。この場合、終了した接続が行なわれたポート１１４は、図１Ｆ〜Ｇに関連して上述した通り、終了した接続の同じサーバの同じポートに再接続するためにポートがすぐにかつ偶発的に再使用された場合に発生する接続要求拒絶を防止するために、一定の期間、利用不能な状態を維持し続ける。
【００１５】
多くの現在利用可能な通信およびネットワークの実現では、エフェメラルポートのプールは複雑な多層リスト構造を通して管理され、利用可能なポートは空きリストに維持され、かつ割り当てられたポートは、現在使用されているポートを表わす種々の割当てポートリストに維持される。そのような構造は管理のための計算コストが高くつき、必要とされる処理オーバヘッドおよびメモリ空間オーバヘッドの両方とも、エフェメラルポート資源が最大資源割当てに近づくにつれて急速に増大する傾向があり、多数の同時通信接続による高いメッセージトラフィックに関連付けられる高い計算オーバヘッドから生じる計算上の障害を潜在的に悪化させる。他の現在利用可能な通信およびネットワークの実現では、ポートは、同様の計算オーバヘッドを伴うビットマップを通して管理される。通信プロトコルおよびネットワークの設計者、コンピュータ製造供給者、オペレーティングシステムの設計者および製造供給者、コンピュータシステム製造者、ならびにコンピュータ利用者は皆、任意の特定のハードウェアおよびソフトウェアプラットフォーム上で達成することのできる、通信スループットおよび通信接続帯域幅の継続的な進展および改善の必要性を認識してきた。さらに、上記の通信ポート管理の問題が属している一般的資源管理の問題は、即座の再使用を促進するために資源再割当て許可情報が資源に関連付けられた場合にだけ、前回の使用から割当て解除された後すぐに再使用することのできる、コンピュータシステム内の多くの他のタイプの資源を含み、そのような資源の管理効率を高めるための一般的方法が、コンピュータシステムの研究者、開発者、製造者、および利用者によって継続的に模索されている。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
したがって、計算資源を管理するための手法が必要とされる。
【課題を解決するための手段】
【００１７】
本発明の種々の実施形態は、資源プールから割り当て、様々な期間使用し、割当て解除し、資源の即座の再割当ておよび使用を促進する資源再割当て許可情報と共に資源プールに返すことのできる計算資源のプールを管理するための効率的かつ柔軟な方法およびシステムに向けられる。本発明の特定の実施形態は、短期間の通信接続に使用されるエフェメラルポートを効率的に管理するための方法およびシステムに向けられる。通信ポートはプールから割り当てられ、様々な期間使用され、かつ割当て解除される。割当て解除された通信ポートは、ポートに関連付けられた資源−再割当て許可情報の使用によって即時再割当てが促進される場合にだけ、即座に再割当てを行なうことができる。資源−再割当て許可情報は、これらの実施形態では、その通信ポートを通しての前回の接続で使用された最終メッセージシーケンス番号、または即座の通信ポートの再使用による接続要求の拒絶を回避するために、そのポートを通してその後に送信される接続要求で使用することのできる次のシーケンス番号のいずれかとすることができる。本発明の一実施形態では、利用可能な通信ポートは、ポートテーブルの配列内のポートテーブルに格納される。各ポートテーブルは循環バッファであり、その各エントリは通信ポートを一意に識別するポート番号、ポートを即座に再使用することを可能にする次のシーケンス番号、およびポート番号によって一意に識別されるポートに関連付ける必要のある任意の他の追加情報を含む。接続アドレス、または接続アドレスの一部分の数値識別子はハッシュされて、ポートテーブルの配列またはリスト内の特定のポートテーブルに対する数値リファレンスを生成し、接続アドレスのためのエフェメラルポートが数値で識別されたポートテーブルから割り当てられ、かつ割当て解除されて、そこに返される。代替的実施形態では、単一のポートテーブルだけが使用される。
【発明を実施するための最良の形態】
【００１８】
本発明の方法およびシステムの実施形態は、計算資源のプールの効率的な管理に向けられる。記載する実施形態は、通信ポートの管理に向けられる。上述の通り、通信ポートのプールはコンピュータシステムの制限される資源を表わし、通信ポートは現在、次善の策として、多くのコンピュータシステムの複雑なデータ構造および待ち時間を使用して管理される。本発明の方法は、通信ポートのプールの効率的な管理をもたらす。本発明の代替的実施形態は、プールから割り当てられ、ある期間使用され、割当て解除され、かつ資源の即座の再割当ておよび使用を促進する資源再割当て許可情報と共にプールに返される、任意の数の様々なタイプのコンピュータ資源を管理するために使用することができる。通信プロトコル例は、本発明の特定の実施形態を説明するための文脈として使用するものであり、本発明は、下述する単純なクライアント／サーバ通信プロトコル、および上述したずっと広範囲の様々な計算資源管理問題に加えて、多種多様な電子通信システムに適用可能である。
【００１９】
通信接続は一般的に、通信接続に資する論理および／または物理構成要素の数値識別子の数値組合せによって指定され得る。例えば、通信エンドポイントは、プロトコルアドレス、プロトコルタイプ、およびプロトコルポートの組合せによって指定することができる。以下の説明に使用する別の実施例として、通信接続は、特定の通信プロトコルおよびネットワークの実現で、４つのフィールドを備える単一の番号によって一意に指定することができる。図２は、図１Ｂ〜Ｈに関連して上述した通信接続のような通信接続の数値指定子またはアドレスの構成要素を示す。特定のシステムでは、ポートは１６ビットの符号無し整数によって指定され、コンピュータのＩＰアドレスは３２ビットの符号無し整数によって指定される。図２に示すように、クライアントコンピュータ２０２とサーバコンピュータ２０４との間の特定の通信接続は、クライアントコンピュータポート２０８の１６ビットのアドレス２０６、クライアントコンピュータの３２ビットのＩＰアドレス２１０、サーバコンピュータの３２ビットのアドレス２１２、およびサーバコンピュータ２０４のポート２１６の１６ビットのアドレス２１４の連結によって一意に指定することができる。したがって、例示的通信ネットワーク内の特定の通信接続は、９６ビットの符号無し整数として一意に指定することができる。
【００２０】
クライアントコンピュータの観点から、クライアントのエフェメラルポートの各々は、ローカルエフェメラルポート識別子を含まない異なる８０ビットの部分接続アドレスと組み合わせて、各エフェメラルポートアドレスに対し２８０個の異なる接続アドレスを生成することができる。換言すると、接続アドレスが図２に示す通りとみなされる場合、クライアントコンピュータは、エフェメラルポートの総数またはエフェメラルポート空間を、２１６個未満のある一定数のエフェメラルポートから、２８０倍に拡大することができる。さらに、通信ポート資源を可能な接続アドレスの間で公平に分配するために、エフェメラル通信ポートの総数を、可能なローカルＩＰアドレス／リモートＩＰアドレス／リモートポートアドレスの一部分、つまり８０ビットの数値にそれぞれ関連付けられるサブパーティションに分割することが好都合であるかもしれない。本発明の様々な実施形態では、利用可能なエフェメラル通信ポート番号を含むポートテーブルは、接続アドレスの８０ビットの非ローカルポートアドレス部分の可能な値のスパングループの集合内の各グループに関連付けられる。これにより、総エフェメラルポート空間をポートテーブルの個数に等しい乗数だけ拡大することが可能になる。また、これにより、接続アドレス空間の８０ビットの非ローカルポートアドレス部分の可能な値のグループの各々に資源を公平に分配することも可能になる。図３は、本発明の特定の実施形態で使用される、接続アドレスの８０ビットの非ローカルポートアドレス部分と、コンピュータシステム内の利用可能なエフェメラル通信ポートのサブパーティションを表わす特定のポートテーブルとのマッピングを示す。コンピュータシステム内に格納されたポートテーブル３０２の配列、リスト、または集合の中からポートテーブルを見出すために、接続アドレス３０４の８０ビットの非ローカルポートアドレス部分が、種々の異なるハッシュ関数３０６のいずれかによってハッシュされて、より短いハッシュ値３０８を生成する。次いで、ハッシュ値の特定のビットが選択され、一緒に連結されてポートテーブルインデックス３１０を生成し、それは、利用可能なエフェメラル通信ポートを格納するポートテーブル３０２の配列または集合内の特定のポートテーブル３１２を識別する。接続アドレスの８０ビットの非ローカルポートアドレス部分とポートテーブルとの間の多くの他のマッピングが可能である。
【００２１】
各ポートテーブルは、ポートテーブル内のポートテーブルエントリを各々が指定する空きポインタおよび利用可能ポインタと共に、ポートテーブルエントリの配列またはリストを備える。各ポートテーブルエントリは、エフェメラル通信ポートを一意に識別するポート番号、および資源−再割当て許可情報を含む。特定の実施形態では、資源再割当て許可情報は、そのポートを通して受信または送信されたメッセージの最後のシーケンス番号に、ランダムまたは擬似ランダムに生成された整数を加算することによって生成される、次のシーケンス番号である。第２のシーケンス番号が、最大可能なシーケンス番号のモジュロである固定距離内にあるときに、第２のシーケンス番号は第１のシーケンス番号の後に来る。例えばシーケンス番号が０から９の範囲であるときに、固定距離が２であるならば、０および１は両方とも９の後になり、１および２は両方とも０より後になる。次のシーケンス番号は、そのポートを通しての次回の接続の第１のメッセージの初期シーケンス番号と考えることができる。以下の説明で、次のシーケンス番号を「ＩＳＮ」または初期シーケンス番号と呼ぶ。このシーケンス番号は、図１Ｈに関連して上述した通り、例えばそのポートを通してそのシーケンス番号で次の接続要求を発行することによって、そのポートを即座に再割当てするために使用することができる。これら次のシーケンス番号をポートテーブルエントリに格納することによって、そのポートを通して発行された接続要求をリモートコンピュータシステムが拒絶しないことを確実にするために一定期間待つことなく、割当て解除されたポートを即座に再割当てすることができる。代替的実施形態では、最後のシーケンス番号が格納され、ポートが再割当てされ、使用されるときに、そこから次のシーケンス番号が計算される。様々なタイプの資源を管理するための様々なタイプのシステムで、多くの他のタイプの再割当て許可情報が可能である。以下の説明では、上述したＩＳＮを例示的再割当て許可情報として使用する。加えて、新しい通信接続のたびにメッセージのシーケンス番号付けをランダムまたは擬似ランダムに初期化することによって、通信システムに対する多くのタイプの悪意ある攻撃を阻止することができる。
【００２２】
図４Ａ〜Ｅは、ポートテーブルに対し実行された種々の操作の結果生じる、本発明の一実施形態を表わすポートテーブルの様々な状態を示す。図４Ａは、例示的な２６エントリのポートテーブルの初期状態を示す。ポートテーブル４０２は、図４Ａ〜Ｅに単一の大文字で表わされたポート番号および次のシーケンス番号が各々に格納された、ポートテーブルエントリ４０４のようなポートテーブルエントリを含む。図４Ａ〜Ｅの実施例では、次のシーケンス番号は１から１００までの間の値を持つ符号無し整数である。図４Ａに示す初期状態では、空きポインタ４０６および利用可能ポインタ４０８は両方とも、ポートテーブルの最初のエントリ４０４を指している。ポートテーブルは２６個の有効なエントリを含み、各々に範囲Ａ〜Ｚ内の異なるポート番号が格納されている。ポインタは、プログラミング言語ポインタ、数値配列インデックス、または多数のエントリの１つを識別するために使用することができる任意の他のそのような値とすることができる。
【００２３】
ポートテーブル内に格納されたポートの割当ては一般的に、利用可能ポインタによって指定されたポートテーブルエントリの内容を返し、エントリを消去し、利用可能ポインタをポートテーブルエントリ１つ分前進させることによって行なわれる。ポートテーブルは循環バッファと考えられるので、空きまたは利用可能ポインタのいずれかがポートテーブルの最後のエントリ４１０を指すと、ポートテーブルの最初のポートテーブルエントリ４０４を指定するようにポインタを設定することによって、ポインタは前進する。図４Ａ〜Ｅの例示的ポートテーブルから最初のポートＡを割り当てる結果、最初のポートテーブルエントリ４０４の内容は消去され、利用可能ポインタは前進して、図４Ｂに示すように、２番目のポートテーブルエントリ４１２を指す。図４Ｃに示すように、ポート番号Ｂ〜Ｅを返す４回の追加割当ての結果、ポートテーブル４０４および４１２〜４１５の最初の５つのエントリが消去され、利用可能ポインタ４０８は６番目のポートテーブルエントリ４１６を指定する。
【００２４】
割当て解除は、空きポインタによって指定されたポートテーブルエントリにポート番号および次のシーケンス番号を格納し、かつ空きポインタを次のポートテーブルエントリに前進させることによって実行される。図４Ｄは、以前に割り当てられたポートＤの割当て解除のみならず、ポートＦ〜Ｈのその後の割当ても行なわれた後の例示的ポートテーブルの状態を示す。ポートＤおよび次のシーケンス番号は今や、最初のポートテーブルエントリ４０４に格納され、空きポインタは前進して２番目のポートテーブルエントリ４１２を指している。ポートテーブルから３つの追加ポート割当てで、ポートＦ〜Ｈが割り当てられた結果、利用可能ポインタ４０８は９番目のポートテーブルエントリ４１８を指定している。ポートテーブルから全てのポートが割り当てられると、ポートテーブルの全てのポートテーブルエントリが消去され、利用可能ポインタおよび空きポインタは両方とも同じポートテーブルエントリを指す。図４Ｅは、利用可能な通信ポートが全て割り当てられた例示的ポートテーブルを示す。空のポートテーブルから追加ポートを割り当てようと試みると、結果的にヌルポインタ、誤り状態、ブール偽値、または割当てが失敗したことを示す何らかの他の指標が返される。
【００２５】
したがって、エフェメラル通信ポートを多層リスト構造に格納し、通信接続の終了後に待ち時間を経験するというのではなく、本発明の方法およびシステムは、利用可能なポートを格納するために計算効率の高い、循環バッファに基づくポートテーブルを提供し、かつそのポートを通した前回の接続の終了前にそのポートを通して送信された最後のメッセージのシーケンス番号の後に来る次のシーケンス番号を格納することによって、終了した接続に関連付けられるポートの即時再割当てを達成する。こうして、本発明の方法およびシステムは再割当て遅延のみならず、複雑なリスト構造に関連付けられる処理およびメモリオーバヘッドをも改善する。
【００２６】
次に、本発明の一実施形態を例証するために、エフェメラル通信ポート管理方法およびシステムの簡潔なＣ＋＋様擬似コード実現を以下に提供する。最初に、幾つかの定数、ルーチン、および構造が宣言される。
【表１】
2009532807.tif 000003
【００２７】
上で１行目に宣言された定数ＭＡＸ＿ＳＥＱは、メッセージの最大シーケンス番号であり、上で２行目に宣言された定数ＭＡＸ＿ＦＯＬＬＯＷは、シーケンス番号の後に来る第２のシーケンス番号を生成するために該シーケンス番号に加算することのできる最大値、モジュロＭＡＸ＿ＳＥＱである。上で３行目に宣言されたルーチン「ｉｎｉｔｉａｌｉｚｅＲＮＧ」は、乱数発生器を初期化した。上で４行目に宣言されたルーチン「ＲＮＧ」は、呼び出されるたびに、数字のある範囲内の異なる乱数を返す乱数発生器である。上で５〜１０行目に宣言されたタイプＣＯＮＮＥＣＴＩＯＮのタイプ定義は、図３に関連して上述した通り、接続アドレスの非ローカルポートアドレス部分を定義する。上で１１行目に宣言されたルーチン「ｈａｓｈＣｏｎｎｅｃｔｉｏｎ」は、供給された接続アドレスｃからポートテーブルインデックス、および最大可能なポートテーブルインデックスｍａｘの指標を返す。ルーチン「ｉｎｉｔｉａｌｉｚｅＲＮＧ」、「ＲＮＧ」、および「ｈａｓｈＣｏｎｎｅｃｔｉｏｎ」の実現については、明瞭かつ簡潔を期すために提示しない。乱数発生器およびハッシュ関数は、コンピュータプログラミングおよびコンピュータサイエンスの当業者には周知である。さらに、そのようなルーチンは、所望の計算特性および実現上の制約に応じて多種多様な方法で実現することができる。
【００２８】
次に、ポートテーブルエントリ、ポートテーブル、およびポート空間に対し、クラス宣言が行なわれる。ポート空間はポートテーブルの配列または集合を表わし、そこからポートを割り当てることができ、かつそこにポートを割当て解除することができる。
【表２】
2009532807.tif 000004
【００２９】
上で１２〜２３行目に宣言されたクラス「ポートテーブルエントリ」は、図４Ａ〜Ｅに関連して上述した通り、ポートテーブル内の単一のエントリを表わす。各ポートテーブルエントリはポート番号、つまり上で１５行目に宣言された「ｐｏｒｔＮｏ」、および上で１６行目に宣言された次のシーケンス番号「ＩＳＮ」を含む。クラス「ｐｏｒｔＴａｂｌｅＥｎｔｒｙ」は、ポート番号および次のシーケンス番号をポートテーブルエントリから検索することを可能にし、かつポート番号および次のシーケンス番号をポートテーブルエントリに入力することを可能にする関数メンバを含む。
【００３０】
次に、クラス「ｐｏｒｔＴａｂｌｅ」が２４〜３８行目で宣言される。クラス「ｐｏｒｔＴａｂｌｅ」は、（１）上で２７行目に宣言された、ポートテーブルエントリのテーブルまたは配列「ｔａｂｌｅ」、（２）上で２８行目に宣言された、ポートテーブルエントリに、ポートテーブルエントリの配列のサイズ「ｔａｂｌｅＳｉｚｅ」を指定する符号無し整数、（３）上で２９行目に宣言された空きポインタ「ｆｒｅｅ」、（４）上で３０行目に宣言された利用可能ポインタ「ａｖａｉｌ」、および（５）上で３１行目に宣言された、ポートテーブル内の最後のポートテーブルエントリを指す、最後のポインタ「ｌａｓｔ」を含む。クラス「ｐｏｒｔＴａｂｌｅ」は、（１）ポートテーブルエントリが有効なポート番号を含む場合には、利用可能ポインタによって指されるポートテーブルエントリへの指定を返し、そうでない場合にはヌルを返す、上で３４行目に宣言された関数メンバ「ｇｅｔＮｅｘｔＰｏｒｔ」、（２）空きポインタによって指定されたポートテーブルエントリにポート番号および次のシーケンス番号を格納する関数メンバ「ｓｔｏｒｅＰｏｒｔ」、および（３）上で３６行目に宣言された、ポートテーブルを初期化する初期化関数メンバ「ｉｎｉｔ」を含む。
【００３１】
上で３９〜５１行目に宣言されたクラス「ｐｏｒｔＳｐａｃｅ」は、そこからポートを割り当てることができ、かつそこにポートを割当て解除することができるエフェメラル通信ポート管理オブジェクトを定義する。クラス「ｐｏｒｔＳｐａｃｅ」は、（１）上で４２行目に宣言されたポートテーブルの配列「ｐｏｒｔＴａｂｌｅＡｒｒａｙ」、および（２）上で４３行目に宣言された、ポートテーブルの配列「ｐｏｒｔＴａｂｌｅＡｒｒａｙ」内のポートテーブルの個数を指定する符号無し整数「ｎｕｍＴａｂｌｅｓ」を含む。クラス「ｐｏｒｔＳｐａｃｅ」は、（１）特定の接続アドレスｃにポート空間から次のポートを割り当て、ポートが割当てに成功した場合にはＴＲＵＥを返し、ポートが得られない場合にはＦＡＬＳＥを返す、上で４５行目に宣言された関数メンバ「ａｌｌｏｃａｔｅＰｏｒｔ」、（２）接続アドレスｃに関連付けられたポート番号および次のシーケンス番号を返す、上で４７行目に宣言された関数メンバ「ｄｅａｌｌｏｃａｔｅＰｏｒｔ」、および（３）上で４９行目に宣言された、ポート空間を初期化するコンストラクタ「ｐｏｒｔＳｐａｃｅ」を含む。
【００３２】
次に、ポートテーブル関数メンバの実現が提供される。
【表３】
2009532807.tif 000005
【００３３】
クラスポートテーブルエントリのコンストラクタが最初に提供される。次に、上記のポートテーブルエントリ関数メンバｇｅｔＮｅｘｔＰｏｒｔの実現が提供される。５行目でｇｅｔＮｅｘｔＰｏｒｔは、利用可能ポインタが有効なポート番号を含むポートテーブルエントリを指しているか否かを決定する。そうである場合、利用可能ポインタは８および９行目で前進し、前進する前に利用可能ポインタが指していたポートテーブルエントリへのリファレンスが返される。次に、ｐｏｒｔＴａｂｌｅ関数メンバｓｔｏｒｅＰｏｒｔの実現が提供される。３行目でｓｔｏｒｅＰｏｒｔは、空きポインタが現在指しているポートテーブルエントリが空であることを確認するために検査する。任意の特定のポートテーブルから以前に割り当てられていないポートが割当て解除されることはないので、この検査は厳密には必要でない。現在説明する実現は、誤り検査をほとんど省いていることに留意されたい。商業用または研究用の実現は一般的に、誤り状態が生じていないかどうかを決定するため、および重大な誤り状態の発生を様々な方法で回避するための精巧な手段を含む。４行目で次のシーケンス番号が、空きポインタによって指定されたポートテーブルエントリに入力される。供給され最直近に観察されたシーケンス番号が引数「ＩＳＮ」として提供され、そのシーケンス番号に乱数が加算されて次のシーケンス番号が生成される。次のシーケンス番号が、供給され最直近に観察されたシーケンス番号の後に来るように、乱数はある範囲内に制限される。５行目で供給されたポート番号が、空きポインタによって指定されたポートテーブルエントリ内に入力され、６〜７行目で、空きポインタは前進する。最後に、ポートテーブル関数メンバｉｎｉの実現が提供される。関数メンバｉｎｉｔは、４行目でポートテーブルエントリの配列を割り当て、８〜１２行目のｆｏｒループでポートテーブルエントリの内容を初期化し、最後に、１３行目で、図４Ａに関連して記載したように、ポートテーブルの最初のポートテーブルエントリを指定するように利用可能ポインタおよび空きポインタをセットする。
【００３４】
最後に、ｐｏｒｔＳｐａｃｅ関数メンバの実現が提供される。
【表４】
2009532807.tif 000006
【００３５】
ポート空間関数メンバａｌｌｏｃａｔｅＰｏｒｔは、７〜８行目で供給された接続アドレスｃに関連付けられるポートテーブルのインデックスを計算し、インデックスポートテーブル内に利用可能なポート番号がある場合には、次いで９〜１６行目で、次の利用可能なポート番号および次のシーケンス番号をポートテーブルから検索する。利用可能なポート番号が無かった場合、関数メンバａｌｌｏｃａｔｅＰｏｒｔは、１７行目にＦＡＬＳＥを返す。同様に、ｐｏｒｔＳｐａｃｅ関数メンバｄｅａｌｌｏｃａｔｅＰｏｒｔは、６〜７行目で供給された接続アドレスｃに関連付けられるポートテーブルのインデックスを計算し、８行目で、ポートテーブル関数メンバｓｔｏｒｅＰｏｒｔの呼出しを介して、供給されたポート番号および最直近に使用されたシーケンス番号をポートテーブルに格納する。最後に、ｐｏｒｔＳｐａｃｅコンストラクタは、６行目で乱数発生器を初期化し、７行目でポートテーブルの配列を割り当て、１０〜１４行目のｆｏｒループでポートテーブルを初期化する。
【００３６】
本発明を特定の実施形態に関して説明したが、本発明をこれらの実施形態に限定することを意図するものではない。本発明の精神の範囲内の変形は、当業者には明らかである。例えば、異なるプログラム言語、異なる制御構造、異なるデータ構造、異なるモジュール式編成、および種々の他のそのような実現パラメータを使用して、通信ポート管理方法およびシステムの本質的に無数の代替的実現が可能である。本発明は、完全にソフトウェアで、ファームウェアで、論理回路で、またはソフトウェアおよびハードウェアの何らかの組合せにより、実現することができる。上述の通り、本発明の方法およびシステムの実施形態は、通信ポートに加え、種々のタイプの計算資源の管理に適用することができる。代替的実施形態では、ポートテーブルエントリにポート番号を格納するのではなく、むしろ、ポートテーブルをポート番号によってインデクシングし、次のシーケンス番号および任意の他の必要なデータだけを、ポートテーブルエントリに格納することができる。代替的実施形態では、ポートテーブルは可変サイズを有することができ、システムの割当ての必要性の均衡を動的に保つために、ポートテーブルの間でポートが移動するので、ポートテーブルのサイズを動的に拡大することができる。代替的実施形態では、ポートテーブルの配列を使用するのではなく、むしろ、システム内の全てのエフェメラル通信ポートを管理するには、単一のポートテーブルで充分であり得る。
【００３７】
説明を目的とする上記の記載は、本発明の完全な理解をもたらすために特定の専門用語を使用した。しかし、本発明を実施するために特定の詳細は必須ではないことが、当業者には明らかである。本発明の特定の実施形態の上記の記載は、例証および説明のために提示したものである。それらは全てを網羅するものではなく、本発明を開示した厳密な形に制限するものでもない。上記の教示に照らして、多くの変更および変形が可能であることは明らかである。実施形態は、本発明の原理およびその実際の適用を最もよく説明し、それによって他の当業者が考えられる特定の使用に適するように種々の変形を施して、本発明および種々の実施形態を最大限に活用することを可能にするために、提示しかつ説明したものである。本発明の範囲は、添付する特許請求の範囲およびそれらの均等物によって定義されるものとする。
【図面の簡単な説明】
【００３８】
【図１Ａ】クライアントコンピュータとサーバコンピュータとの間の通信のための単純な抽象的計算環境を示す。
【図１Ｂ】例示的クライアント／サーバ通信接続を示す。
【図１Ｃ】例示的クライアント／サーバ通信接続を示す。
【図１Ｄ】例示的クライアント／サーバ通信接続を示す。
【図１Ｅ】例示的クライアント／サーバ通信接続を示す。
【図１Ｆ】例示的クライアント／サーバ通信接続を示す。
【図１Ｇ】第１の再割当て許可イベントを示す。
【図１Ｈ】ポート１１４が再割当てに再び利用可能状態になることを可能にする、第２の再割当て許可イベントを示す。
【図１Ｉ】コンピュータシステム内の全てのエフェメラル通信ポートの割当てによって生じるかもしれない障害を示す。
【図１Ｊ】図１Ｉに示したシステムの通信接続の１つが終了した後の状態を示す。
【図２】図１Ｂ〜Ｈに関連して上述した通信接続のような通信接続の数値指定子またはアドレスの構成要素を示す。
【図３】本発明の特定の実施形態で使用される、接続アドレスの８０ビットの非ローカルポートアドレス部分と、コンピュータシステム内の利用可能なエフェメラル通信ポートのサブパーティションを表わす特定のポートテーブルとのマッピングを示す。
【図４Ａ】本発明の一実施形態を表わす、ポートテーブルに実行された種々の操作の結果生じるポートテーブルの種々の状態を示す。
【図４Ｂ】本発明の一実施形態を表わす、ポートテーブルに実行された種々の操作の結果生じるポートテーブルの種々の状態を示す。
【図４Ｃ】本発明の一実施形態を表わす、ポートテーブルに実行された種々の操作の結果生じるポートテーブルの種々の状態を示す。
【図４Ｄ】本発明の一実施形態を表わす、ポートテーブルに実行された種々の操作の結果生じるポートテーブルの種々の状態を示す。
【図４Ｅ】本発明の一実施形態を表わす、ポートテーブルに実行された種々の操作の結果生じるポートテーブルの種々の状態を示す。
【図１Ａ】
2009532807.tif 000007
【図１Ｂ】
2009532807.tif 000008
【図１Ｃ】
2009532807.tif 000009
【図１Ｄ】
2009532807.tif 000010
【図１Ｅ】
2009532807.tif 000011
【図１Ｆ】
2009532807.tif 000012
【図１Ｇ】
2009532807.tif 000013
【図１Ｈ】
2009532807.tif 000014
【図１Ｉ】
2009532807.tif 000015
【図１Ｊ】
2009532807.tif 000016
【図２】
2009532807.tif 000017
【図３】
2009532807.tif 000018
【図４Ａ】
2009532807.tif 000019
【図４Ｂ】
2009532807.tif 000020
【図４Ｃ】
2009532807.tif 000021
【図４Ｄ】
2009532807.tif 000022
【図４Ｅ】
2009532807.tif 000023
【国際調査報告】
2009532807.tif 000024