(57)【特許請求の範囲】
【請求項１】
通信コネクションが登録されるエントリの複数個を持つコネクション・テーブルにおいて、目的の通信コネクションに対応するエントリを見つけ出すコンピュータ通信における通信コネクション識別方法であって、
目的の通信コネクションを規定する送信側ネットワーク・アドレス，送信側ポート番号，受信側ネットワーク・アドレスおよび受信側ポート番号の全部または一部でビット列を構成し、当該ビット列を暗号化し、
暗号化の結果得られる暗号文の全部または一部の値をハッシュ値として、コネクション・テーブルの探索を行う
ことを特徴とするコンピュータ通信における通信コネクション識別方法。
【請求項２】
通信コネクションが登録されるエントリの複数個を持つコネクション・テーブルにおいて、目的の通信コネクションに対応するエントリを見つけ出すコンピュータ通信における通信コネクション識別方法であって、
目的の通信コネクションを規定する要素である送信側ネットワーク・アドレス，送信側ポート番号，受信側ネットワーク・アドレスおよび受信側ポート番号のうち、送信側ポート番号および受信側ポート番号のみをハッシュ関数計算モジュールに入力し、
ハッシュ関数計算モジュールから出力されたハッシュ値を用いてコネクション・テーブルの探索を行う
ことを特徴とするコンピュータ通信における通信コネクション識別方法。
【請求項３】
通信コネクションが登録されるエントリの複数個を持つコネクション・テーブルにおいて、目的の通信コネクションに対応するエントリを見つけ出すコンピュータ通信における通信コネクション識別方法であって、
目的の通信コネクションを規定する送信側ネットワーク・アドレス，送信側ポート番号，受信側ネットワーク・アドレスおよび受信側ポート番号の全部または一部をそれぞれビット・シャッフルし、
ビット・シャッフルの結果をハッシュ関数計算モジュールに入力し、
ハッシュ関数計算モジュールから出力されたハッシュ値を用いてコネクション・テーブルの探索を行う
ことを特徴とするコンピュータ通信における通信コネクション識別方法。
【請求項４】
通信コネクションが登録されるエントリの複数個を持つコネクション・テーブルにおいて、目的の通信コネクションに対応するエントリを見つけ出すコンピュータ通信における通信コネクション識別方法であって、
目的の通信コネクションを規定する送信側ネットワーク・アドレス，送信側ポート番号，受信側ネットワーク・アドレスおよび受信側ポート番号をハッシュ関数計算モジュールに入力し、
ハッシュ関数計算モジュールからの出力をビット・シャッフルし、
ビット・シャッフルの結果得られた値を用いてコネクション・テーブルの探索を行う
ことを特徴とするコンピュータ通信における通信コネクション識別方法。
【請求項５】
通信コネクションが登録されるエントリの複数個を持つコネクション・テーブルにおいて、目的の通信コネクションに対応するエントリを見つけ出すコンピュータ通信における通信コネクション識別方法であって、
目的の通信コネクションを規定する送信側ネットワーク・アドレス，送信側ポート番号，受信側ネットワーク・アドレスおよび受信側ポート番号のうち、送信側ネットワーク・アドレスの下位ビット，送信側ポート番号，受信側ネットワーク・アドレスの下位ビットおよび受信側ポート番号をハッシュ関数計算モジュールに入力し、
ハッシュ関数計算モジュールから出力されたハッシュ値を用いてコネクション・テーブルの探索を行う
ことを特徴とするコンピュータ通信における通信コネクション識別方法。
【請求項６】
通信コネクションが登録されるエントリの複数個を持つコネクション・テーブルにおいて、目的の通信コネクションに対応するエントリを見つけ出すコンピュータ通信における通信コネクション識別方法であって、
目的の通信コネクションを規定する要素である送信側ネットワーク・アドレスと受信側ネットワーク・アドレスの差分をハッシュ関数計算モジュールに入力するとともに、目的の通信コネクションを規定する要素である送信側ポート番号と受信側ポート番号またはそれらの差分を上記ハッシュ関数計算モジュールに入力し、
ハッシュ関数計算モジュールから出力されたハッシュ値を用いてコネクション・テーブルの探索を行う
ことを特徴とするコンピュータ通信における通信コネクション識別方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、少なくとも２台以上のコンピュータが通信を行っているときに、複数の通信コネクションが登録されるコネクション・テーブルの中から、目的の通信コネクションに対応するエントリを見つけ出すコンピュータ通信における通信コネクションの識別方法に関するものである。
近年ネットワークの普及に伴い、コンピュータはスタンドアローンとしてではなく他のコンピュータと通信して使用されることが当然になり、１組のコンピュータ間に複数の通信コネクションが張られることも珍しくない。このため、コンピュータは、自分が送受信するデータがどの通信コネクションに属しているかを、多数のコネクションの中から識別する必要がある。
【０００２】
【従来の技術】
従来、コンピュータがコネクションを識別する際には、自分に対して張られたコネクションＩＤ（識別子）をコネクション・テーブルに保持しておき、線形探索で、コネクション・テーブルに登録されたコネクションを一つ一つ送受信データから取り出されたコネクションＩＤと比較照合していた。この遣り方では１回コネクションを識別するのに平均でコネクション・テーブルのテーブル・エントリ数の半分のコネクションと比較する必要がある。
【０００３】
図１０は従来の技術によるコネクション識別方式を説明する図である。同図において、Ｔはコネクション・テーブル、αはコネクションＩＤの値を示す。
通信コネクションとは、二つのコンピュータ（ホスト）の間に張られた論理的な通信路である。コネクションを識別するためのコネクションＩＤは、データを送信するコンピュータのネットワーク・アドレス，データを送信するコンピュータのポートの番号，データを受信するコンピュータのネットワーク・アドレス及びデータを受信するコンピュータのポートの番号で定義される。なお、データを送信するコンピュータのネットワーク・アドレスを送信側アドレス、データを送信するコンピュータのポートの番号を送信側ポート番号、データを受信するコンピュータのネットワーク・アドレスを受信側アドレス、データを受信するコンピュータのポートの番号を受信側ポート番号と呼ぶこととする。
【０００４】
コネクション・テーブルＴは複数のエントリを有しており、各エントリはコネクションＩＤフィールド，コネクション関連情報フィールドを有している。コネクション関連情報とは、例えば通信コネクション上で何処までデータを送信（又は受信）済みかといった情報がある。このような従来の技術では、コネクションＩＤをキーとして、コネクション・テーブルＴを先頭から１エントリずつ照合していく必要があり、図示の例ではｄ回の照合が必要になっている。
【０００５】
【発明が解決しようとする課題】
従来の技術においては、１台のコンピュータに対して張られているコネクションの数が増えると、それに比例してコネクション・テーブルの探索にかかる時間が大きくなると言う欠点を生じていた。コネクションＩＤは送信側と受信側のネットワーク・アドレス・ペアを含み、今後，次世代プロトコルにおいてネットワーク・アドレス長が増えると、さらにコネクション照合にかかる時間が増加するという問題もある。
本発明は、この点に鑑みて創作されたものであって、コネクション識別に特化したハッシュ関数を使用して、コネクションの数が多いときでも短時間にコネクション識別を完了させることを目的としている。
【０００６】
【課題を解決するための手段】
図１は本発明の原理説明図である。最初にコンピュータがデータを受信したとき、それがコネクション・テーブル上の何れのコネクションに属するかを識別する場合について説明する。先ず受信データからコネクションＩＤを抽出する。コネクションは送信側と受信側のネットワーク・アドレス・ペアおよびポート番号ペアから定義され、従って抽出されたコネクションＩＤも送信側アドレス，送信側ポート番号，受信側アドレス，受信側ポート番号の４要素を含んでいる。このような４要素の全部または一部をハッシュ関数計算モジュールに入力して、ハッシュ関数モジュールにハッシュ値を計算させ、その結果としてハッシュ関数計算モジュールからハッシュ値ｄが出力される。
【０００７】
次に、コネクション・テーブルのｄ番目のエントリのコネクションＩＤと，受信データから抽出したコネクションＩＤが一致しているか否かを確認する。それが一致した場合には、それが目的のコネクションとなる。もし一致しない場合、つまりハッシュ値の衝突が起きている場合には，周知の線形走査法あるいは二重ハッシュ法を用いて、目的のコネクションを発見する。ハッシュ値衝突時に線形走査法を用いる場合には、異なるハッシュ値を持つコネクション同士まで衝突しあってしまうクラスター化現象による効率低下が問題になるが、それへの耐性を持つハッシュ関数を採用して回避する。
【０００８】
コンピュータがデータを送信する場合は、コンピュータは、データを送信する通信コネクションのコネクションＩＤを知っている。コネクションＩＤからコネクション・テーブルのエントリを探索する方法は、データ受信の場合と同じである。
【０００９】
コネクション・テーブルへのコネクションの登録について説明する。コンピュータＡがコンピュータＢにデータを送信する場合、通信コネクションを設定する必要がある。先ず、コンピュータＡは、自己のネットワーク・アドレス（Ａａとする），自己が使用するポート番号（Ｐａとする），コンピュータＢのネットワーク・アドレス（Ａｂとする）及び特定のポート番号（Ｐｃとする）を持つコネクション設定要求を送信する。コンピュータＢは、このコネクション設定要求を受け取ると、使用すべきポート番号（Ｐｂとする）を決め、使用すべきポート番号を含む応答をコンピュータＡに返す。
【００１０】
この応答を受け取ると、コンピュータＡは送信側ネットワーク・アドレスＡａ，送信側ポート番号Ｐａ，受信側ネットワーク・アドレスＡｂ，受信側ポート番号Ｐｂより成るコネクションＩＤを自己のコネクション・テーブルに登録する。コンピュータＢも同様なコネクションＩＤを自己のコネクション・テーブルに登録する。
【００１１】
コネクション設定時にコネクションＩＤを登録する方法は、受信の場合と略ぼ同じである。即ち、コネクションＩＤを構成するアドレス・ペアおよびポート番号ペアをハッシュ関数計算モジュールに入力し、出力されるハッシュ値ｄで指定されるエントリが既に他のコネクションに割り当てられているか否かを調べる。そのエントリが他のコネクションに割り当てられていなければ、そのエントリに該当するコネクションＩＤを書き込む。ハッシュ値の衝突が起きた場合には、周知の方法でそのコネクションを他のエントリに割り当てる。
【００１２】
本発明では、図１に示すように、コネクションＩＤ（又はその部分集合）を入力としてハッシュ関数計算モジュールにハッシュ値を計算させており、同一コネクションに関しては必ず同じハッシュ値が出力されることが保証される。そこで、コネクション・テーブルへの新規コネクション登録時にハッシュ値をコネクション・テーブルの先頭からのオフセットとなるようにすると、２つ以上のコネクションが同じハッシュ値を持つ衝突現象が起きない限り、テーブル探索時もハッシュ値さえ判っていればテーブルを先頭から一つずつ調べることなく、直接的に目的とするテーブル・エントリを参照することが可能になる。即ち、一回コネクションを比較照合するだけで目的のコネクションに到達できる。なお、衝突が起きた場合は、周知の衝突対策法である線形走査法または二重ハッシュ法などを用いて引き続き探索を実行する。
【００１３】
一般にコネクションがテーブル上にランダムに分布すると仮定した場合、テーブルに登録されたエントリ数がテーブル・サイズの５０％であれば、衝突を考慮しても、平均照合回数が２回以下になることが知られている(L.I.Kronsjo.Algotrithms，John Wiley & Sons 参照) 。したがって、テーブルの占拠率を常に５０％以下であるようにテーブル・サイズを広く取ってやれば、コネクション識別に特化したハッシュ関数を使用して出来るだけコネクションを一様に分布させることで、コネクション・テーブル探索時のコネクション照合回数が略ぼ２回以下になり、容易にコネクションを識別することが可能になる。
【００１４】
【発明の実施の形態】
図２は本発明の全体構成を説明する図である。
同図において、Ａは送信側ノード、Ｂは受信側ノード、Ｆはハッシュ関数計算モジュール、Ｔはコネクション・テーブルをそれぞれ示している。
送信側ノードＡも受信側ノードＢもコンピュータであり、送信側ノードＡと受信側ノードＢの間には通信コネクションが張られている。コネクションＩＤを構成する送信側アドレス，送信側ポート番号，受信側アドレス，受信側ポート番号を通信データから取り出す処理は、ハッシュ関数計算モジュールＦの中で行っても、ハッシュ関数モジュールＦの外で行っても良い。また、ハッシュ関数計算モジュールＦについては、異なる通信プロトコル毎に別の関数を使用しても構わない。更に、コネクションの両端のコンピュータは直接つながっている必要がなく、間に中継ノードが存在しても構わない。
【００１５】
図３は本発明の第１実施例を説明する図である。
第１実施例では、コネクションを定義する要素である送信側アドレス，受信側アドレス，送信側ポート番号，受信側ポート番号の和を計算して、その値をハッシュ値としている。ネットワーク・アドレス・ペアとポート番号ペアのビット長がＴＣＰ／ＩＰのように大きく違っている場合には、ネットワーク・アドレスをそれぞれ上位ビットと下位ビットに分割してから合計６要素の和を計算しても良い。なお、ＴＣＰ／ＩＰプロトコルでは、ＩＰアドレスは３２ビットであり、ポート番号は１６ビットである。また、ＩＰアドレスのように、ネットワーク・アドレスが幾つかのフィールドから構成されている場合には、フィールド単位で和を計算しても良い。ＩＰアドレスは、例えば１３３．１２．１２．１のように表現され、点で区切られている各整数は８ビットで表現されている。フィールドとは、このような８ビットの範囲を意味している。
【００１６】
図４は本発明の第２実施例を説明する図である。
第２実施例においては、ハッシュ関数計算モジュールＦは暗号化アルゴリズムを使用している。ハッシュ関数計算モジュールＦへの入力は、コネクションを定義する送信側アドレス，受信側アドレス，送信側ポート番号，受信側ポート番号である。これらは、連続して例えばメモリ・バッファ上に並べられる。ハッシュ関数計算モジュールＦは、これらを一つのビット列と見做して暗号化アルゴリズムを起動し、その結果として出力される暗号文をハッシュ値とする。暗号化によってコネクション・テーブル上にコネクションを略ぼランダムに割り振ることができ、ハッシュによる探索の効率を向上できる。コネクション定義要素をビット列に並べるときの順番は任意で良く、定義要素の一部のみでビット列を構成しても良い。暗号化アルゴリズムは、ＤＥＳ，ＭＤ５など何れでも良い。一般に暗号アルゴリズムは数十ビット以上の暗号文を出力するが、その内の何ビットをハッシュ値として使用するか，また何れのビットを使用するかについては制限はない。
【００１７】
図５は本発明の第３実施例を説明する図である。
ハッシュ関数計算モジュールＦへの入力はポート番号ペアのみであり、特に受信データからネットワーク・アドレス・ペアを切り出す必要がない。ポート番号しか使用しないことで、簡単でそれなりに効率の良いハッシュ関数が実現できる。例えば、単に送信側ポート番号と受信側ポート番号の和を取って、それをハッシュ値とする関数もハッシュ関数モジュールＦの一例である。
【００１８】
図６は本発明の第４実施例を説明する図である。同図において、ＳないしＳ３はビット・シャッフル手段を示している。
ビット・シャッフル手段は、入力されたデータのビット位置を変換する機能を有している。送信側アドレスはビット・シャッフル手段Ｓに入力され、送信側ポート番号はビット・シャッフル手段Ｓ１に入力され、受信側アドレスはビット・シャッフル手段Ｓ２に入力され、受信側ポート番号はビット・シャッフル手段Ｓ３に入力されている。ビット・シャッフル手段Ｓ，Ｓ１，Ｓ２，Ｓ３の出力は、ハッシュ関数計算モジュールＦに入力される。ハッシュ関数計算モジュールＦの出力がハッシュ値ｄになる。
【００１９】
ビット・シャッフル手段Ｓ，Ｓ１，Ｓ２，Ｓ３をソフトウェアで実現しても、ハードウェアで実現しても良い。また、各入力要素毎に異なる方法でビット・シャッフルしても構わない。さらに、一部の入力要素に対してだけビット・シャッフルしても良い。ビット・シャッフルによってポート番号の違いを増幅できるため、ハッシュ値衝突時のクラスター化現象による探索効率の低下を避けられる。ビット・シャッフルの方式例として、ビット・ローテーションによるビット位置入れ替えもある。
【００２０】
図７は本発明の第５実施例を説明する図である。第５実施例においては、第４実施例の場合と異なり、ハッシュ関数計算モジュールＦへの入力をビット・シャッフルする代わりに、ハッシュ関数計算モジュールＦの出力をビット・シャッフルし、ビット・シャッフルの結果をハッシュ値とする。各入力要素をビット・シャッフルする場合に比べ、ビット・シャッフル手段の起動回数を１回に減らせるという利点がある。
【００２１】
図８は本発明の第６実施例を説明する図である。送信側アドレスの上位ビットを０マスクし、受信側アドレスの上位ビットも０マスクする。そして、送信側アドレスの下位ビット，受信側アドレスの下位ビット，送信ポート番号，受信ポート番号をハッシュ関数計算モジュールＦに入力する。
【００２２】
ローカルなコネクション同士ではネットワーク・アドレスの上位ビットは全て一緒になってしまい、コネクションを識別するための情報として役に立たないので、送信側アドレスおよび受信側アドレスの下位ビットのみの抽出により、うまくコネクション識別情報をハッシュ値に畳み込める。これはコネクション・テーブルのサイズを小さくするため、ハッシュ値のサイズを押さえる必要があるときに効果が大きい。また、ＩＰアドレスのように、ネットワーク・アドレスが幾つかのフィールドから構成されている場合には、それぞれのフィールドに対して上位ビットをマスクすることで、下位ビットのみを取り出しても良い。その際、例えば上位フィールドより下位フィールドの方で、多くのビット数を取り出すようにしても良い。
【００２３】
図９は本発明の第７実施例を説明する図である。同図において、Ｇはハッシュ関数計算モジュールのサブルーチン、Ｈもハッシュ関数計算モジュールのサブルーチンをそれぞれ示す。
送信側アドレス及び受信側アドレスから成るネットワーク・アドレス・ペアに関しては、差分を取ってからハッシュ関数計算モジュールＦに入力する。送信側ポート番号と受信側ポート番号をそのままハッシュ関数計算モジュールＦに入力しても良いし、送信側ポート番号と受信側ポート番号の差分を取って入力しても良い。ＩＰアドレスのように、ネットワーク・アドレスが幾つかのフィールドから構成されている場合には、フィールド毎に差分を計算しても良い。
【００２４】
このようにすることにより、通信コネクションの両端のコンピュータが同一ネットワークに属しているか否かがネットワーク・アドレス・ペアの差の上位ビットが０か否かで判定できる。この情報を利用して、コネクションの両端が同一ネットワークに属しているか否かで、ハッシュ算出方法を図９のように相違させても良い。例えば差分の上位ビットが０の場合にはサブルーチンＧを使用し、０でない場合にはサブルーチンＨを使用する。サブルーチンＧは、ネットワーク・アドレスの上位ビットを使わないハッシュ関数を使用するものであり、例えば本発明の第６実施例（図８を参照）のようなものである。サブルーチンＨは、ネットワーク・アドレスの上位ビットを使うハッシュ関数を使用するものであり、例えば本発明の第１実施例（図３を参照）のようなものである。
【００２５】
【発明の効果】
以上の説明から明らかなように、本発明によれば、コネクションが多い場合でも、コネクション識別用に特化されたハッシュ関数を用いるため、従来に比べて短時間でコネクション・テーブルからコネクションを探索することができ、コンピュータ通信におけるコネクション識別の効率向上に寄与する所が大きい。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】本発明の全体構成を説明する図である。
【図３】本発明の第１実施例を説明する図である。
【図４】本発明の第２実施例を説明する図である。
【図５】本発明の第３実施例を説明する図である。
【図６】本発明の第４実施例を説明する図である。
【図７】本発明の第５実施例を説明する図である。
【図８】本発明の第６実施例を説明する図である。
【図９】本発明の第７実施例を説明する図である。
【図１０】従来の通信コネクションの識別方法を説明する図である。
【符号の説明】
Ｔ  コネクション・テーブル
Ｆ  ハッシュ関数計算モジュール
Ｓ  ビット・シャッフル手段
Ａ  送信側ノード
Ｂ  受信側ノード
【図１】
0003846963.tif 000002
【図２】
0003846963.tif 000003
【図３】
0003846963.tif 000004
【図４】
0003846963.tif 000005
【図５】
0003846963.tif 000006
【図６】
0003846963.tif 000007
【図７】
0003846963.tif 000008
【図８】
0003846963.tif 000009
【図９】
0003846963.tif 000010
【図１０】
0003846963.tif 000011