(57)【特許請求の範囲】
【請求項１】
受け取ったＩＰパケットについてのルーティングを実行するルーティング処理装置において、
次に参照される先行テーブルの存在に関する情報を格納する第１の領域、前記先行テーブルのエントリ数を特定する情報を格納する第２の領域および前記先行テーブルについてのアドレス情報を格納する第３の領域を備える第１のポインタと、
前記第１のポインタに続いて参照の対象となり、かつ、さらに次に参照される後続テーブルの存在に関する情報を格納する第４の領域、前記後続テーブルのエントリ数を特定する情報を格納する第５の領域および前記後続テーブルについてのアドレス情報を格納する第６の領域を備える第２のポインタを前記第１のポインタの前記第２の領域に格納された前記エントリ数を特定する情報の分だけ有する前記先行テーブルと、を備えた情報記憶部と、
前記第１のポインタの前記第１ないし第３の領域に格納された情報に基づいて、前記ＩＰパケットに含まれるＩＰアドレスの所定のビット列が示す値に対応する前記第２のポインタを参照することを指示する参照指示部と、
を備え、
前記所定のビット列におけるビット数は、前記第１のポインタの前記第２の領域に格納された前記エントリ数を特定する情報に基づいて定められ、
前記所定のビット列が示す最大値は、前記テーブルのエントリ数と一致することを特徴とするルーティング処理装置。
【請求項２】
前記先行テーブルにおいて、
前記第４の領域に格納される前記後続テーブルの存在に関する情報は、前記後続テーブルの存在する前記情報記憶部内のアドレスが前記第６の領域に格納されているか否かを特定する情報であることを特徴とする請求項１に記載のルーティング処理装置。
【請求項３】
前記先行テーブルにおいて、
前記第４の領域は、前記後続テーブルの存在に関する情報に替えて、前記ＩＰパケットの転送先の存在を示す情報が格納され、その場合において、前記ＩＰパケットの転送先に関する情報が前記第６の領域に格納されることを特徴とする請求項１に記載のルーティング処理装置。
【請求項４】
受け取ったＩＰパケットの転送先を特定するルーティング処理装置であって、
前記ＩＰパケットの転送先を格納するルーティング・テーブルと、
前記ルーティング・テーブルを参照して前記転送先を特定するルーティング処理部と、を備え、
前記ルーティング・テーブルは、１または２以上のポインタからなるテーブルが階層化されており、かつ前記ポインタは、自身より下位に位置する下層テーブルを特定する情報と、前記下層テーブルを構成するポインタの数を格納し、
前記ルーティング処理部は、
前記ポインタの数に基づいて前記ＩＰパケットに含まれるＩＰアドレスを構成するビット列の中の所定の複数ビットを特定し、前記下層テーブルを特定する情報および前記特定された複数ビットの値に基づいて当該下層テーブルの中の該当するポインタを参照することにより、当該ＩＰパケットの転送先を特定することを特徴とするルーティング処理装置。
【請求項５】
前記ルーティング処理部は、
複数の前記テーブルを参照する際に、先行して参照された先行テーブルについて特定された前記ＩＰアドレスの中の第１の所定の複数ビットと、続いて参照された後続テーブルについて特定された前記ＩＰアドレスの中の第２の所定の複数ビットとして、前記第１の所定の複数ビットに連続し、かつ前記第１の複数ビットよりも下位に位置する複数のビットとを順次に用いることを特徴とする請求項４に記載のルーティング処理装置。
【請求項６】
階層化された複数のルーティング・テーブルを順次参照することにより受け取ったＩＰパケットの転送先を特定するルーティング方法であって、
先行して参照されるルーティング・テーブル（ａ）およびその次に参照されるルーティング・テーブル（ｂ）は、参照先情報の格納領域を単数または複数備え、
前記ルーティング・テーブル（ａ）の前記参照情報により次に参照されるルーティング・テーブル（ｂ）を特定する参照テーブル特定ステップと、
前記ＩＰパケットに含まれるＩＰアドレスに基づいて、前記ルーティング・テーブル（ｂ）の中で参照される前記格納領域を特定する参照領域特定ステップと、
を備え、
前記参照領域特定ステップは、
前記ＩＰアドレスを構成するビット情報の中で、前記ルーティング・テーブル（ａ）により特定された所定の複数のビット情報に基づいて前記ルーティング・テーブル（ｂ）の中で参照される前記格納領域を特定し、
前記所定の複数のビット情報は、前記ルーティング・テーブル（ａ）に格納された前記ルーティング・テーブル（ｂ）における前記格納領域の数を示すことを特徴とするルーティング方法。
【請求項７】
前記ＩＰパケットの中で、前記ＩＰパケットに含まれＩＰアドレスと予め設定された比較ＩＰアドレスとを、相互に対応する所定のビット列の一致または不一致を判定し、
前記比較ＩＰアドレスと一致した前記ＩＰアドレスを含む前記ＩＰパケットをルーティングの対象とすることを特徴とする請求項６に記載のルーティング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インターネット等のネットワークに適用する、データ転送の転送経路を制御するルーティングに関するものである。
【０００２】
【従来の技術】
インターネット等のネットワークにおける最も典型的なプロトコルは、ＴＣＰ（Transmission Control Protocol）／ＩＰ（Internet Protocol）である。このＴＣＰ／ＩＰにおいて、ネットワークに接続される機器には、３２ビット（ｂｉｔ）のアドレス、つまりＩＰアドレスが割り当てられる。ネットワークを流れるデータ・ストリーム（ＩＰパケット）は、ＩＰパケットを送り届ける先（以下、宛先）のＩＰアドレスを含んでいる。ＩＰパケットを所定の宛先に送り届ける過程の経路制御（ルーティング）を行なうルータが、ネットワーク上に配置される。ルータは、ＩＰパケットに含まれるＩＰアドレスを参照することによって、ＩＰパケットの宛先までのルーティングを行なう。通常、送り主と宛先との間には、複数のルータが介在しており、ＩＰパケットは、複数のルータを経由して宛先に届く。
【０００３】
ＩＰアドレスは、３２ビットの大きさを有しており、かつネットワーク・アドレスとホスト・アドレスから構成される。なお、この３２ビットという定義は、現行のＩＰｖ４によるものである。ネットワーク・アドレスは、宛先が属するネットワークを識別する番号であり、インターネットに接続される全ての他のネットワークにおけるネットワーク・アドレスと重ならないように設定される。ホスト・アドレスは当該ネットワーク上で宛先（ホストあるいはノード）を識別する番号であり、同一のネットワークにおいて他のホストと重ならないように設定される。ルーティングは、ＩＰアドレスのうちのネットワーク・アドレスを参照することにより行なわれる。
ルータはルーティングを行なうためのルーティング・テーブルを所持する。このルーティング・テーブルには、ＩＰパケットを次にどのルータへ転送すればよいかが格納されている。例えば、ルータＡに対して２つのルータＢおよびルータＣが接続される一方、ルータＢにはネットワークＢが、またルータＣにはネットワークＣが接続されているとする。ルータＡのルーティング・テーブルには、ネットワークＢに転送されるべきＩＰパケットはルータＢに転送すべきことが、ネットワークＣに転送されるべきＩＰパケットはルータＣに転送されるべきことが格納されているのである。
【０００４】
ＩＰアドレスは、クラスＡ〜Ｅという５種類のアドレス・クラスに分類される。このうち、クラスＤおよびクラスＥは、特殊用途に用いられており、ここでの説明は省略する。
クラスＡは、ＩＰアドレスの先頭ビットが“０”で始まる。そして、クラスＡは、ネットワーク・アドレスがこの先頭の１ビットを含めて８ビット（実質７ビット）と定義され、残りの２４ビットがホスト・アドレスになる。したがって、１つのネットワーク、換言すれば１つのネットワーク・アドレスに対して割り当てることのできるホスト・アドレスは、２24個となる。ただし、このうちで全て“０”および全て“１”のものはリザーブ（Reserved）となっているため、現実に割り当てられるホスト・アドレスは、２24−２個となる。
クラスＢは、ＩＰアドレスの先頭ビットが“１０”で始まる。そして、クラスＢは、ネットワーク・アドレスがこの先頭の２ビットを含めて１６ビット（実質１４ビット）までと定義され、残りの１６ビットがホスト・アドレスになる。したがって、１つのネットワーク、換言すれば１つのネットワーク・アドレスに対して割り当てることのできるホスト・アドレスは、２16個となる。このうちで全て“０”および全て“１”のものがリザーブ（Reserved）となっているのは、クラスＡと同様である。
クラスＣは、ＩＰアドレスの先頭ビットが“１１０”で始まる。そして、クラスＣは、ネットワーク・アドレスがこの先頭の３ビットを含めて２４ビット（実質２１ビット）までと定義され、残りの８ビットがホスト・アドレスになる。したがって、１つのネットワーク、換言すれば１つのネットワーク・アドレスに対して割り当てることのできるホスト・アドレスは、２8個となる。このうちで全て“０”および全て“１”のものがリザーブ（Reserved）となっているのは、クラスＡ，Ｂと同様である。
最近では、上位ビットから指定されたビット数がネットワーク・アドレス、残りがホスト・アドレスとして使用するＣＩＤＲ（Classless Inter Domain Routing）が主流になってきている。
【０００５】
【発明が解決しようとする課題】
さて、ルータは、転送されたＩＰアドレスについて、上位から１ビットずつ順にルーティング・テーブル内に存在するか否か判断する。この手順を図８および図９に基づいて説明する。
ルーティング・テーブルは、メモリ上に展開されており、メモリにおけるアドレス（メモリ・アドレス）ごとに情報が格納された構造を有している。図８は、１つのメモリ・アドレスを構成するメモリの内容（メモリ・ユニットと呼ぶことにする）を示している。ルーティング・テーブルは、図８に示すメモリ・ユニットの集合体ということができる。
【０００６】
メモリ・ユニットは、図８に示すように、２つに区分される。１つはネットワーク・アドレスのビット値が０の場合に参照される情報を格納し、他の１つはネットワーク・アドレスのビット値が１の場合に参照される情報を格納している。図８の例では、ビット値が０の場合に参照される情報を上段に格納し、ビット値が１の場合に参照される情報を下段に格納している。また、メモリ・ユニットは、参照すべき情報が格納されているか否かを示すヘッダ領域と、参照すべき情報が格納されている情報格納領域とから構成される。なお、ヘッダ領域および情報格納領域は、本明細書中で用いる名称であって、一般に用いられている名称ではない。ヘッダ領域には、１または０の値が入力されている。ヘッダ領域の値が１の場合には、対応する情報格納領域に参照すべき情報が格納されていることを示す。また、ヘッダ領域の値が０の場合には、対応する情報格納領域に参照すべき情報が格納されていないことを示す。
【０００７】
情報格納領域には、次に参照すべきメモリ・ユニットのメモリ・アドレスが格納されている。このように、メモリ・ユニットは、次に参照すべきメモリ・ユニットを指し示すポインタということができる。また、情報格納領域には、ＩＰパケットが転送されるべきポートの番号（図中、ポートＮｏ．）が格納される。ここでポートとは、ルータがＩＰパケットを転送する出力端を意味し、通常ルータは複数のポートを有しており、各ポートには他のルータあるいはネットワークが接続されている。図８の例では、ビット値が０の場合には、次にメモリ・アドレス＊１のメモリ・ユニットを参照する。また、ビット値が１の場合には、当該ＩＰパケットは、メモリ・ユニットに格納されているＮｏ．のポートから外部に対して転送される。転送されるＩＰパケットは、当該ポートに接続された他のルータまたはネットワーク・アドレスが所属するネットワークに届くことになる。
【０００８】
さて、図９に示すように、あるルータに対して、ネットワーク・アドレスが「００１１０００１」であるＩＰパケットが転送されてきたものとする。なお、このネットワーク・アドレスは、先頭ビットが０であるから、クラスＡのＩＰアドレスに該当する。
ルータは、転送されたネットワーク・アドレスの先頭ビット値について、ルーティング・テーブルの、例えば先頭に位置するメモリ・ユニットを参照する。図９の例では、ネットワーク・アドレスの先頭ビット値は０である。一方、先頭のメモリ・ユニットの情報格納領域は、ビット値が０（ビット＝０）の場合にはメモリ上のアドレスＡのメモリ・ユニットを参照すべきことを、またビット値が１（ビット＝１）の場合にはメモリ上のアドレスＢのメモリ・ユニットを参照すべきことの情報を格納している。このとき、ヘッダ領域には、１が入力されている。したがって、図９に示す例では、ビット＝０に対応する側の情報格納領域の参照情報であるアドレスＢを次に参照することになる。
【０００９】
アドレスＢに存在するメモリ・ユニットを参照すると、ビット＝０に対応する情報格納領域はアドレスＣを示し、ビット＝１に対応する情報格納領域はアドレスＧを示している。ネットワーク・アドレスの２番目のビット値は０である。したがって、アドレスＢのメモリ・ユニットを参照することにより、次にアドレスＣに存在するメモリ・ユニットを参照すべきことが指示される。
次いで、アドレスＣに存在するメモリ・ユニットを参照すると、ビット＝０に対応する情報格納領域はアドレスＦを示し、ビット＝１に対応する情報格納領域はアドレスＤを示している。ネットワーク・アドレスの３番目のビット値は１である。したがって、アドレスＣのメモリ・ユニットを参照することにより、次にアドレスＤに存在するメモリ・ユニットを参照すべきことが指示される。
【００１０】
図９に示す例では、ＩＰアドレスがクラスＡに属しているため、以上のような参照手順が、ネットワーク・アドレスの先頭ビットから最後の８番目のビットまで順次繰り返される。例えば、７番目のビットまで以上の参照を繰り返した結果、アドレスＯに辿り着いたとする。そして、ネットワーク・アドレスの８番目のビット値は１であり、一方、アドレスＯのビット＝１に対応する情報格納領域には、ポート＃１が格納されている。したがって、当該ＩＰパケットは、当該ルータのポート＃１から外部に向けて転送されることを示している。前述のように、＃１のポートには、他のルータまたはネットワークが接続されており、当該ＩＰパケットは、前記他のルータまたは前記ネットワークに転送されることになる。
【００１１】
以上のように、ルータにおいて、ＩＰパケットの転送先が決定される過程で、ネットワーク・アドレスがルーティング・テーブルに対して複数回の参照作業が繰り返される。図９の例では、ＩＰパケットがクラスＡに属しているため最大８回の参照作業が繰り返されるに過ぎないが、クラスＢでは最大１６回、クラスＣでは最大２４回繰り返されることになる。これは、１台のルータにおけるＩＰパケットのルーティングに相当の時間を要することを示唆している。前述したように、ＩＰパケットは、通常、複数台のルータを経由して宛先に届けられてから、ルーティングのために費やされる時間によって、ＩＰパケットがホストに届くまでに不必要な遅延を招くおそれがある。
そこで本発明は、ルーティングに要する時間を短縮することのできる効率的なルーティング手法の提案を課題とする。
【００１２】
【課題を解決するための手段】
従来のルーティング・テーブルを用いたルーティングは、ネットワーク・アドレスの上位から１ビットづつ参照、判定が繰り返されていた。そこで本発明は、複数ビットをまとめて参照することにより、ルーティングの時間を短縮することを検討した。その結果、ルーティング・テーブルの構成を変更することにより、複数ビットをまとめて参照可能であることを知見した。より具体的には、従来のルーティング・テーブルにおけるメモリ・ユニットがヘッダ領域と情報格納領域という２つの領域に区分されていたのに対して、図１に示すように、３つの領域に区分した。
３つの領域のうちの１つ目の領域は、従来のメモリ・ユニットのヘッダ領域に類似する情報を格納する領域であって、以後、コントロール領域と呼ぶことにする。また、２つ目の領域は、次に参照すべきルーティング・テーブルを構成するメモリ・ユニットの数（テーブル・サイズ）を表示する。このメモリ・ユニットの数は、１度に比較されるネットワーク・アドレス中のビットの数をも示している。本明細書中では、この領域をサイズ格納領域と呼ぶことにする。さらに、３つ目の領域は、従来のメモリ・ユニットの情報格納領域に極めて類似した性格を有する。
【００１３】
コントロール領域には、転送先情報が存在しないこと、転送先情報が存在することまたはさらに参照すべきメモリ・ユニットが存在することのいずれかの情報が格納される。
サイズ格納領域には、次に参照すべきルーティング・テーブルのメモリ・ユニットの数に関する情報が格納される。また、サイズ格納領域に格納される情報は、ネットワーク・アドレスの中で参照されるビットの数をも示している。例えば、ここの記述（２進数）が“１０”の場合には、次に参照されるルーティング・テーブルのメモリ・ユニットの数は２2＝４である。また、ネットワーク・アドレスの中で参照されるビットの数は２つ（２桁）である。ここで、参照されるビットの数が２つであるから、２進数では００，０１，１０および１１の４つのケースが考えられる。メモリ・ユニットの数は、この４つのケースに対応している。つまり、ルーティング・テーブルは、００，０１，１０および１１に対応して４つのメモリ・ユニットを保持することになる。なお、このメモリ・ユニットの数を、以下、ルーティング・テーブルのエントリ数ということがある。そして、参照されるビットの値自体も、００，０１，１０および１１のいずれかであるから、００，０１，１０および１１のいずれかに対応するメモリ・ユニットを次に参照することにすればよい。
本発明において、このサイズ格納領域を設け、かつこのサイズ格納領域に格納された値に対応する数のエントリ数を有するルーティング・テーブルを下層に設けることにより、ネットワーク・アドレス中の複数のビットを一度に参照することを可能にする。しかも、参照する複数のビット列が示す値に対応するメモリ・ユニットのみを参照すれば足りるため、参照に費やされる時間は、従来のルーティング・テーブルに比べて相当低減される。
情報格納領域には、次に参照すべきルーティング・テーブル上のアドレスあるいは当該ＩＰパケットが転送されるポートＮｏ．が格納されている。あるいは、参照すべきルーティング・テーブル上のアドレスあるいは当該ＩＰパケットが転送されるポートＮｏ．のいずれも格納されていない場合もある。これは、転送先がないことを示している。以上の構成からなるメモリ・ユニット（以下、ポインタ）からなるテーブルを階層化してルーティングを実行する。
本発明は、以上の事項に基づいてなされたものであり、以下の構成を有している。
【００１４】
本発明は、受け取ったＩＰパケットについてのルーティングを実行するルーティング処理装置において、次に参照される先行テーブルの存在に関する情報を格納する第１の領域、先行テーブルのエントリ数を特定する情報を格納する第２の領域および先行テーブルについてのアドレス情報を格納する第３の領域を備える第１のポインタを有する。そして、この第１のポインタに続いて参照の対象となり、かつ、さらに次に参照される後続テーブルの存在に関する情報を格納する第４の領域、後続テーブルのエントリ数を特定する情報を格納する第５の領域および後続テーブルについてのアドレス情報を格納する第６の領域を備える第２のポインタを第１のポインタの第２の領域に格納されたエントリ数を特定する情報の分だけ有する先行テーブルとを備えた情報記憶部と、さらに、ＩＰパケットに含まれるＩＰアドレスの所定のビット列が示す値に対応する第２のポインタを参照することを指示する参照指示部を備える。
【００１５】
本発明のルーティング処理装置において、所定のビット列におけるビット数は、第１のポインタの第２の領域に格納されたエントリ数を特定する情報に基づいて定める。そして、所定のビット列が示す最大値が、テーブルのエントリ数と一致することにより、所定のビット列で表される値によって、参照すべきエントリを特定することができる。
【００１６】
本発明のルーティング処理装置の先行テーブルにおいて、第４の領域に格納される後続テーブルの存在に関する情報は、後続テーブルの存在する情報記憶部内のアドレスが第６の領域に格納されているか否かを特定する情報とすることができる。また、この先行テーブルにおいて、第４の領域は、後続テーブルの存在に関する情報に替えて、ＩＰパケットの転送先の存在を示す情報が格納されることもある。
そして、先行テーブルにおいて、第４の領域にＩＰパケットの転送先の存在を示す情報が格納されている場合には、第６の領域にＩＰパケットの転送先に関する情報が格納される。
【００１７】
また本発明は、受け取ったＩＰパケットの転送先を特定するルーティング処理装置であって、ＩＰパケットの転送先を格納するルーティング・テーブルと、ルーティング・テーブルを参照して転送先を特定するルーティング処理部と、を備え、ルーティング・テーブルは、１または２以上のポインタからなるテーブルが階層化されており、かつポインタは、自身より下位に位置する下層テーブルを特定する情報と、下層テーブルを構成するポインタの数を格納するルーティング処理装置を提供する。
【００１８】
このルーティング処理装置において、ルーティング処理部は、ポインタの数に基づいてＩＰパケットに含まれるＩＰアドレスを構成するビット列の中の所定の複数ビットを特定し、下層テーブルを特定する情報および特定された複数ビットの値に基づいて、下層テーブルの中の該当するポインタを参照することにより、当該ＩＰパケットの転送先を特定することができる。
【００１９】
また、ルーティング処理部は、複数のテーブルを参照する際に、先行して参照された先行テーブルについて特定されたＩＰアドレスの中の第１の所定の複数ビットと、続いて参照された後続テーブルについて特定されたＩＰアドレスの中の第２の所定の複数ビットとして、第１の所定の複数ビットに連続し、かつ第１の所定の複数ビットよりも下位に位置する複数のビットとを順次に用いる。このようにして、ＩＰアドレスを複数ビット毎に参照していくのが、本発明の１つの特徴である。
【００２０】
本発明は以上のルーティング処理装置に適用することのできる、以下のルーティング方法を提供する。すなわち本発明のルーティング方法は、階層化された複数のルーティング・テーブルを順次参照することにより受け取ったＩＰパケットの転送先を特定するルーティング方法であって、先行して参照されるルーティング・テーブル（ａ）およびその次に参照されるルーティング・テーブル（ｂ）は、参照先情報の格納領域を単数または複数備え、ルーティング・テーブル（ａ）の前記参照先情報に基づいて次に参照されるルーティング・テーブル（ｂ）を特定する参照テーブル特定ステップと、ＩＰパケットに含まれるＩＰアドレスに基づいて、ルーティング・テーブル（ｂ）の中で参照される前記格納領域を特定する参照領域特定ステップと、を備えることを特徴としている。
【００２１】
本発明のルーティング方法において、参照領域特定ステップは、ＩＰアドレスを構成するビット情報の中で、ルーティング・テーブル（ａ）により特定された所定の複数のビット情報に基づいてルーティング・テーブル（ｂ）の中で参照される格納領域を特定する。ここで、所定の複数のビット情報は、ルーティング・テーブル（ａ）に格納されたルーティング・テーブル（ｂ）における格納領域の数を示すことができる。
さらに、本発明において、ＩＰパケットの中で、ＩＰパケットに含まれＩＰアドレスと予め設定された比較ＩＰアドレスとを、相互に対応する所定のビット列の一致または不一致を判定し、比較ＩＰアドレスと一致したＩＰアドレスを含むＩＰパケットをルーティングの対象とすることができる。つまり、ルーティング対象の絞込みを行なう。
【００２３】
【発明の実施の形態】
以下本発明を実施の形態に基づいて説明する。なお、本実施の形態では、ＩＰｖ４を例にして説明するが、ＩＰｖ６について適用することもできることは言うまでもない。
図２は、本実施の形態によるルーティング処理装置１の主要構成を示すブロック図である。
ルーティング処理装置１は、ＴＣＰ／ＩＰに基づくルーティング処理を実行する装置であり、ルータあるいはスイッチに適用することができる。
ルーティング処理装置１は、デコード回路２と、デコード回路２に接続されたルーティング回路３〜５とを備えている。ルーティング回路３は、ブランチＡポインタ３１、処理部Ａ３２およびルーティング・テーブルＡ３３とを備えている。また、ルーティング回路４は、ブランチＢポインタ４１、処理部Ｂ４２およびルーティング・テーブルＢ４３とを備えている。さらに、ルーティング回路５は、ブランチＣポインタ５１、処理部Ｂ５２およびルーティング・テーブルＣ５３とを備えている。処理部Ａ３２〜Ｃ５２は、ブランチＡポインタ３１〜ブランチＣポインタ５１およびルーティング・テーブルＡ３３〜Ｃ５３の参照、ネットワーク・アドレスの参照等を実行する。
【００２４】
デコード回路２は、ＩＰパケットから得られたＩＰアドレスの転送を受けて、アドレス・クラスを判断し、ネットワーク・アドレスを分類する。前述のように、アドレス・クラスはクラスＡ〜Ｃの３つのクラスに分類される。この分類は、ネットワーク・アドレスの先頭１ビットが０の場合にクラスＡ、先頭２ビットが１０の場合にクラスＢまた先頭３ビットが１１０の場合にクラスＣに分類される。この分類がクラスＡの場合にはルーティング回路３が、クラスＢの場合にはルーティング回路４が、さらにクラスＣの場合にはルーティング回路５が選択され、各ルーティング回路３〜５において以後のルーティング処理が実行される。
この例では、クラスＡ〜Ｃの３つのクラスに分ける例について説明するが、前述したＣＩＤＲ（Classless Inter Domain Routing）について本発明を適用することもできる。
【００２５】
ブランチＡポインタ３１〜ブランチＣポインタ５１の基本的な構成は一致しており、図１に示す通りである。
図１に示すように、ブランチＡポインタ３１〜ブランチＣポインタ５１は、各々、コントロール領域、サイズ格納領域および情報格納領域の３つの領域から構成される。
コントロール領域には、２ビットからなるコントロール情報が格納される。図１に示すように、コントロール領域には、“０１”、“１０”および“１１”の３種類の情報が格納される。この中で、“０１”は、選択されたルーティング回路には転送先に関する情報が含まれていないことを示す。また、“１０”は、対応する情報格納領域に当該ＩＰパケットを転送するポートＮｏ．換言すれば転送先が格納されていることを示している。さらに、“１１”は、次に参照すべきルーティング・テーブル（以下、次段のルーティング・テーブル）のメモリ上のアドレスが格納されていることを示している。ここで、ブランチＡポインタ３１〜ブランチＣポインタ５１も、ルーティング・テーブルを構成する。そして、次段のルーティング・テーブルに対して上位の階層に位置することになる。つまり、本実施の形態によるルーティング・テーブルは、階層構造をなしている。この階層構造は、後述するより具体的な説明によって、明確になろう。
【００２６】
サイズ格納領域には、５ビットからなるサイズ情報が格納されている。ただし、このビット数は５ビットに限るわけではなく、任意である。ここで、サイズとは、ルーティング・テーブルを構成するブランチ・ポインタの数、換言すればエントリの数をいう。例えば、図１に示すように、サイズ格納領域に“０００１０”が格納されている場合には、次段のルーティング・テーブルのサイズ（ブランチ・ポインタの数またはエントリ数）は、２２＝４となる。そして、図１に示すように、ルーティング・テーブルには、上位のブランチ・ポインタから順に、“００”，“０１”，“１０”および“１１”の順位が割り当てられる。サイズ格納領域に“０００１１”が格納されていれば、次のルーティング・テーブルのサイズ（ブランチ・ポインタの数またはエントリ数）は、２３＝８となる。
【００２７】
また、サイズ格納領域に格納される値は、次段のルーティング・テーブルの中で参照すべきブランチ・ポインタの位置を示している。例えば、図１に示すように、ネットワーク・アドレスが“１１０１０１０１”だとする。そして、サイズ格納領域に“０００１０”が格納され、かつ次段のルーティング・テーブルが２段目のルーティング・テーブルの場合、先頭から２番目のビットと、これに続く３番目のビットが２段目のルーティング・テーブルの中で参照すべきブランチ・ポインタを示している。図１に示す例の場合、２番目のビット値が１、３番目のビット値が０である。したがって、２段目のルーティング・テーブルのなかで、“１０”番目のブランチ・ポインタを参照することになる。この“１０”番目のブランチ・ポインタの、情報格納領域には、メモリ・アドレスＸが格納されている。これは、さらに次に参照すべきルーティング・テーブルのメモリ上のアドレスを示している。
【００２８】
本実施の形態は、以上のようなブランチ・ポインタおよびブランチ・ポインタの集合としてのルーティング・テーブルを備えている。このルーティング・テーブルを用いることにより、ネットワーク・アドレスの中の複数のビットを一度に参照の対象とすることを可能にし、加えて、複数のエントリから構成されるルーティング・テーブルであっても、１つのブランチ・ポインタを参照すれば足りる。したがって、従来のルーティング・テーブルを用いる場合に比べて、効率的なルーティングを実現できる。
【００２９】
以下では、本実施の形態によるルーティング・テーブルを用いたより具体的なルーティングの手順を、図３および図４に基づいて説明する。
図３は、図２におけるデコード回路２が、１００１０１０１．１１００１１０１．１１１０１１１１．０００００００１からなるＩＰアドレスを受け取った例を示している。
受け取ったＩＰアドレスは、先頭２ビットが“１０”であるから、クラスＢに分類され、ルーティング回路４においてルーティングが実行される。
ルーティング回路４におけるルーティングは以下のように実行される。はじめに、ブランチＢポインタ４１が参照される。このブランチＢポインタ４１は、１段目のブランチ・ポインタ（またはルーティング・テーブル）に該当する。
【００３０】
ブランチＢポインタ４１は、コントロール領域に“１１”、サイズ格納領域に“０００１０”および情報格納領域に“メモリ・アドレスＡ”が格納されている。
コントロール領域の“１１”は、次のルーティング・テーブルが存在することを示している。なお、ルータの機能上、１段目のブランチ・ポインタ（ブランチＡポインタ３１〜ブランチＣポインタ５１）におけるコントロール領域は“１１”に設定される。
サイズ格納領域の“０００１０”は、次段である２段目のルーティング・テーブルにおけるブランチ・ポインタの数が２2＝４であることを示している。図３に示すように、２段目のルーティング・テーブルは、＋００〜＋１１までの４つのブランチ・ポインタから構成されている。
また、サイズ格納領域の“０００１０”は、受け取ったネットワーク・アドレスの中で参照すべきビットの数が２つであることを示している。２段目のルーティング・テーブルにおいては、ネットワーク・アドレスの上位から２番目および３番目のビットを参照する。図３に示すように、上位から２番目および３番目のビットの値は、“００”であり、この値が参照される。そして、この“００”は、２段目のルーティング・テーブルにおいて参照すべきブランチ・ポインタを示している。
情報格納領域の“メモリ・アドレスＡ”は、アドレスＡに展開されているルーティング・テーブルを次に参照することを示している。
【００３１】
以上の通りであり、ブランチＢポインタ４１は、次段（２段目）のルーティング・テーブルが、メモリ上のアドレスＡに展開されていること、この２段目のルーティング・テーブルは、４つのブランチ・ポインタから構成されることを示している。そして、受け取ったＩＰアドレスを考慮することにより、２段目のルーティング・テーブルの中で参照すべきブランチ・ポインタを特定することができる。
【００３２】
次に、２段目のルーティング・テーブルについて説明する。
前述のように、２段目のルーティング・テーブルは、メモリ上のアドレスＡに展開されていおり、４つのブランチ・ポインタから構成される。そして、図３にも示すように、上位のブランチ・ポインタから、＋００，＋０１，＋１０および＋１１の順位が特定される。そして、ブランチＢポインタ４１およびネットワーク・アドレスから、２段目のルーティング・テーブルでは、＋００のブランチ・ポインタを参照する。
参照するブランチ・ポインタは、コントロール領域に“１１”、サイズ格納領域に“０００１１”および情報格納領域に“メモリ・アドレスＢ”が格納されている。
【００３３】
コントロール領域の“１１”は、前述のように、次のルーティング・テーブルが存在することを示している。
サイズ格納領域の“０００１１”は、次段である３段目のルーティング・テーブルにおけるブランチ・ポインタの数が２3＝８であることを示している。図３に示すように、３段目のルーティング・テーブルは、＋０００〜＋１１１までの８つのブランチ・ポインタから構成されている。
また、サイズ格納領域が“０００１１”であるから、受け取ったネットワーク・アドレスの中で参照すべきビットの数は３つである。２段目のルーティング・テーブルを参照する過程で、既に上位から３番目までのビットが参照されており、今回は、上位から４番目、５番目および６番目の３つのビットが参照される。４番目、５番目および６番目のビットの値は、“１０１”であり、この値が、３段目のルーティング・テーブルにおいて参照すべきブランチ・ポインタを示している。
情報格納領域の“メモリ・アドレスＢ”は、メモリ上のアドレスＢに展開されているルーティング・テーブルを次に参照することを示している。
【００３４】
そこで、３段目のルーティング・テーブルについて説明する。
前述のように、３段目のルーティング・テーブルは、メモリ上のアドレスＢに展開されており、８つのブランチ・ポインタから構成される。そして、図３にも示すように、上位のブランチ・ポインタから、＋０００〜＋１１１の順位が付けられる。２段目のルーティング・テーブルおよびネットワーク・アドレスから、３段目のルーティング・テーブルでは、＋１０１のブランチ・ポインタを参照することになる。
参照するブランチ・ポインタは、コントロール領域に“０１”が格納されている。コントロール領域の“０１”は、転送先に関する情報が含まれていないことを示す。したがって、ここまでの検索によって、受け取ったＩＰパケットは破棄されることになる。
【００３５】
以上では、３段目までのルーティング・テーブルの検索後に当該ＩＰパケットが破棄された例を示したが、次に、当該ＩＰパケットが所定の転送先に転送される例を次に説明する。
この例では、図４に示すように、１１１０１０１１．１１００１１０１．１１１０１１１１．０００００００１からなるＩＰアドレスをデコード回路２が受け取ったことを前提としている。
受け取ったＩＰアドレスは、先頭３ビットが“１１１”であるから、クラスＣに分類され、ルーティング回路５においてルーティングが実行される。
ルーティング回路５におけるルーティングは以下のように実行される。はじめに、ブランチＣポインタ５１が参照される。
【００３６】
ブランチＣポインタ５１は、コントロール領域に“１１”、サイズ格納領域に“０００１０”および情報格納領域に“メモリ・アドレスＣ”が格納されている。
したがって、２段目のルーティング・テーブルを参照することになる。この２段目のルーティング・テーブルは、図４に示すように、＋００〜＋１１までの４つのブランチ・ポインタから構成される。サイズ格納領域の“０００１０”および受け取ったネットワーク・アドレスの上位から２番目および３番目のビット値“１１”より、２段目のルーティング・テーブルの＋１１の位置にあるブランチ・ポインタを参照する。
【００３７】
２段目のルーティング・テーブルにおいて、＋１１で特定されるブランチ・ポインタには、コントロール領域に“１１”、サイズ格納領域に“０００１１”および情報格納領域に“メモリ・アドレスＤ”が格納されている。
以上の情報に基づいて、３段目のルーティング・テーブルを参照する。
３段目のルーティング・テーブルは、メモリ上のアドレスＤに展開されている。このルーティング・テーブルは、２段目のルーティング・テーブルにおけるコントロール領域の“１１”が示すように、８つのブランチ・ポインタから構成されている。各々のブランチ・ポインタには、＋０００〜＋１１１までの順位が特定される。図４の例の場合、コントロール領域の“１１”にしたがって、ネットワーク・アドレスの上位から４番目、５番目および６番目の３つのビットが参照される。４番目、５番目および６番目のビットの値は、“０１０”であるから、３段目のルーティング・テーブルにおいて＋０１０で特定されるブランチ・ポインタを参照することを指示している。
【００３８】
３段目のルーティング・テーブルにおいて、＋０１０で特定されるブランチ・ポインタは、コントロール領域に“１０”が格納されている。つまり、このブランチ・ポインタに転送先の情報が含まれていることを示している。そして、情報格納領域には、“ポート＃３”が格納されている。したがって、当該ＩＰパケットは、ルータの＃３のポートから外部に転送される。外部とは、次のルータあるいはネットワークを含む。
【００３９】
以上説明したように、本実施の形態によれば、ＩＰアドレスに基づくルーティングにおいて、ネットワーク・アドレス中の複数のビットを一度に参照することを可能にする。しかも、参照する複数のビット値に対応するブランチ・ポインタのみを参照すれば足りるため、参照に費やされる時間は、従来のルーティング・テーブルに比べて相当低減される。
【００４０】
次に、以上説明した本実施の形態によるルーティングをより効率的に行なうために望ましい形態について説明する。この形態は、以上説明した本実施の形態によるルーティングの実行対象を、自身が転送先情報を持つＩＰパケットに絞込むことを趣旨とする。
【００４１】
例えば、“０１０１．１１００．”、“０１０１．１１０１．”、“０１０１．１１１０．”および“０１０１．１１１１．” の４つのネットワーク・アドレスについて、ルータが転送先を有するものとする。そうすると、ネットワーク・アドレスの上位６ビットまでを参照することにより、転送先情報を有するか否かまで判断することができる。つまり、ネットワーク・アドレスの上位６ビットが、“０１０１．１１＊＊”であることがわかれば、転送先情報が存在していると判断することができる。そして、このような判断を、複数種組み合わせることにより、受け取ったＩＰアドレスについて、自身が転送先情報を有しているか否かについて絞込みが可能となる。
【００４２】
図５は、上記絞込みのための機能を示すブロック図である。
図５に示すように、ｎ台の比較器１〜ｎを備えている。なお、比較器１〜ｎにおける比較の具体的内容は後述する。比較器１〜ｎは、受け取ったネットワーク・アドレスに基づいて、当該ルータ換言すればルーティング・テーブルが転送先情報を持つか否かを判断する。比較器１〜ｎは、ルーティング・テーブルが転送先情報を持つと判断した場合には、Ｈｉｇｈの情報を出力する。図５は、比較器１〜ｎのうちのいずれか一つがＨｉｇｈを出力した場合に、本実施の形態によるルーティング・テーブルを参照したルーティングを実行することを示している。
【００４３】
図６は、比較器ｎの具体的処理例を示している。比較器ｎは、受け取ったＩＰアドレスと比較ＩＰアドレスとを所定のビット分だけその値を比較し、所定のビット分の値が一致している場合には、自身のルーティング・テーブルに転送先情報が含まれていると判断する。したがって、比較ＩＰアドレスは、転送先の公約数としての性格を有している。また、所定のビットよりも下位のビットについては、前述したルーティング・テーブルを用いたルーティングを実行することになる。図６において、比較器ｎは、マスク・レジスタを備える。マスク・レジスタは、所定のビットを指定する。つまり、受け取ったＩＰアドレスのうち、比較ＩＰアドレスと比較するビットを指定する。図６の例では、マスク・レジスタ“０１０００”が格納されており、受け取ったＩＰアドレスのうち、上位９ビットが比較対象となる。一方、それ以降の２３ビットは、比較対象外となる。また、マスク・レジスタの値に基づいて、マスク・データが作成される。図６の例では、３２ビット中、上位９ビットが１として格納される。
【００４４】
受け取ったＩＰアドレスとマスク・データの論理和を取ることにより、比較対象となるビット列を抽出する。このビット列は、図６に示すように、“１１００１１０１１”である。
抽出されたビット列について、比較ＩＰアドレスとの間で排他的論理和を取り比較する。ここで、受け取ったＩＰアドレスのうち、比較対象とならないビットについては、次の論理回路において比較される。
３２ビット全てについて論理和を取ったものが、この比較器ｎに対する結果ｎとなる。この結果ｎは、比較対象ビット列が比較ＩＰアドレスの所定ビットと一致したか否かである。図６の例では、比較対象となるビット列“０１０００”は、比較ＩＰアドレスの対応ビット列“０１０００”と一致している。したがって、受け取ったＩＰアドレスは、先に説明したブランチ・ポインタおよび階層化されたルーティング・テーブルを用いたルーティングに供される。
その例を図７に示しておくが、“１１００１１０１１”以降のビット列が参照の対象となって、ルーティングが実行される。なお、図７の構成は、図３および図４と同様のため、ここでの詳細な説明は割愛する。
【００４５】
本実施の形態では、図５に示すように、以上のような比較器ｎを複数台設ける。したがって、受け取ったＩＰアドレスについて、設けられた台数分同時に比較することができる。このことは、受け取ったＩＰアドレスについて転送先情報を有するか否かを極めて短時間に判断できることを示唆している。前述したように、転送先情報を有すると判断されたＩＰアドレスについては、先に説明したブランチ・ポインタおよび階層化されたルーティング・テーブルを用いたルーティングに供される。一方、転送先情報を有しないと判断されたＩＰアドレスについては、当該ＩＰパケットを破棄するか、転送されてきた上位のルータに返すことになる。なお、比較器１〜ｎの台数は、専ら、ルータの有するポートの数、換言すれば転送先の数に応じて定められる。転送先の多いルータでは比較器１〜ｎの台数は多くなる。そして、比較器１〜ｎは、転送先を多く抱えたルータに適用することが効果的である。なお、比較器ｎにより、直接転送先を求めることもできる。
【００４６】
【発明の効果】
以上説明したように、本発明によるルーティング方法は、ネットワーク・アドレス中の複数のビットを一度に参照の対象とすることを可能にし、加えて、複数のエントリから構成されるルーティング・テーブルであっても、１つのブランチ・ポインタを参照すれば足りる。したがって、従来のルーティング・テーブルを用いる場合に比べて、効率的なルーティングを実現できる。しかも、比較器１〜ｎを用いてルーティング対象の絞込みを実行することにより、より効率的なルーティングを可能とする。
【図面の簡単な説明】
【図１】  本実施の形態によるブランチ・ポインタの構成を説明する図である。
【図２】  本実施の形態によるルーティング処理装置の構成を示す図である。
【図３】  本実施の形態によるルーティング方法を説明するための図である。
【図４】  本実施の形態によるルーティング方法を説明するための図である。
【図５】  本実施の形態によるルーティング処理装置に付加される構成であって、ルーティングの対象となるＩＰパケットを絞込むための機能を示す図である。
【図６】  図５における比較器の構成を示す図である。
【図７】  絞込まれたＩＰパケットついて、本実施の形態によるルーティングを実行する様子を示す図である。
【図８】  従来のルーティング方法を説明するための図である。
【図９】  従来のルーティング方法を説明するための図である。
【符号の説明】
１…ルーティング処理装置、２…デコード回路、３，４，５…ルーティング回路、３１…ブランチＡポインタ、４１…ブランチＢポインタ、５１…ブランチＣポインタ
【図１】
0003639553.tif 000002
【図２】
0003639553.tif 000003
【図３】
0003639553.tif 000004
【図４】
0003639553.tif 000005
【図５】
0003639553.tif 000006
【図６】
0003639553.tif 000007
【図７】
0003639553.tif 000008
【図８】
0003639553.tif 000009
【図９】
0003639553.tif 000010