(57)【要約】【課題】  論理アドレス空間と物理アドレス空間との対応関係を明確化すると共に当該対応関係を簡単に変更する。【解決手段】  論理アドレス空間と物理アドレス空間とを単位となるブロックに分け、論理アドレス空間の各ブロックの先頭アドレスについて論理アドレスと物理アドレスの対応関係を示すポインタテーブルを備える。【選択図】  図１
2005117210.tif 000002
【特許請求の範囲】
【請求項１】
宛先アドレスと当該宛先アドレスに対応する次ホップ先とが記録されたエントリを記憶する手段を備え、
この記憶する手段は、第一および第二のメモリ手段に分割され、
この第一および第二のメモリ手段は、それぞれ複数のブロックに分割され、
前記第一のメモリ手段には、若番から老番の順に配列された前記宛先アドレスが当該ブロック数分分割されて当該ブロックにそれぞれ割当てられ、
前記第一のメモリ手段のブロックに対応して前記第二のメモリ手段のブロックが配置されたメモリ装置において、
前記第一のメモリ手段のブロックに対応する前記第二のメモリ手段のブロックを表示するポインタ値が格納されたポインタテーブルを備えた
ことを特徴とするメモリ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はＩＰルータなどのパケット転送装置において、パケット転送処理を行うに当たり、パケットヘッダ情報を元にパケットの転送経路を決定する際に検索するテーブルの検索方法に関する。
【背景技術】
【０００２】
ＩＰルータなどのパケット転送装置においては、パケットヘッダに搭載された宛先アドレスを元に経路表を検索し、次の方路を決定する。経路表には経路と次の方路との関係を保持している。次の方路は次ホップのルータを指し、次ホップのルータも同様の経路表をもつことで、ホップバイホップでＩＰパケットが転送されていく。
【０００３】
経路表で経路を表現する方法として、インターネットではＣＩＤＲ(Classless
Inter Domain Routing)の機構が導入されている。経路は３２ビットのＩＰアドレスとそれに対するプレフィクス長の組み合わせで表現される。すなわち、経路表の経路は“ＩＰアドレス／プレフィクス長”の形式で表される。経路のうち、プレフィクス長で指定された長さ以降のビットに関してはＤｏｎ‘ｔ  Ｃａｒｅである。例えば１２９．１３１．１７５．１２９／３２は３２ビット全てのビットがＤｏｎ’ｔ  Ｃａｒｅでない経路であり、１２９．６０．８３／２４は先頭の２４ビットが有効な経路である。パケットヘッダの宛先アドレスが１２９．６０．８３．１も１２９．６０．８３．１１１も同じ経路１２９．６０．８３／２４に一致する。
【０００４】
経路表はパケットヘッダの宛先アドレスをキーとして用いて検索する。経路表を検索する際に、ＣＩＤＲでは最長一致と呼ばれるテーブル検索規則に基づく。最長一致とはキーに用いる宛先アドレスが最も長く一致するものを正解とするものである。例えば、経路表に経路１２９．３８．１１１／２４と経路１２９．３８／１６の二つの経路がある場合に、１２９．３８．１１１．２という宛先アドレスを持つパケットが到着した場合は、経路１２９．３８．１１１／２４の方がより長い範囲で一致するので、それを正解とする。このような最長一致検索を行う方法として二分探索による方法がある。
【０００５】
二分探索を用いて最長一致検索を行う場合には、１２９．３８．１１１／２４というエントリに対しては１２９．３８．１１１．０というエントリと１２９．３８．１１１．２５５という二つのエントリを追加する。このようなエントリを小さいもの順に経路表に隙間なく並べて、二分探索を行う。
【０００６】
ルーティングテーブルから二分探索用ルーティングテーブルを作成する方法を図５を用いて説明する。二分探索ではメモリの真ん中のアドレスから探索を開始して、大きければアドレスの下半分に、小さければ上半分に対して、再度、二分探索を再帰的に行い、これ以上探索できないところまで再帰的に探索を行うものである。このため、ルーティングテーブルのエントリは小さいもの順に並べられている。また、補助エントリを追加するが、この補助エントリは、二分探索が終了した時点のエントリに答えとなる情報が記載されているようにするためである。補助エントリとは、あるエントリに対してプレフィクス長までを比べたときに次に大きなエントリを補助エントリとする。例えば、１．０．０．０／８に対しては２．０．０．０／８が対応する補助エントリとなる。また、＊．＊．＊．＊／０に対してはｆｆ．ｆｆ．ｆｆ．ｆｆ／０が対応する補助エントリとなる。
【０００７】
二分探索用ルーティングテーブルを二分探索木で作ったものを図５の右側に示す。メモリ上には二分探索用ルーティングテーブル（境界値テーブル）のエントリが隙間無く並んでいる（例えば特許文献１または２参照）。
【特許文献１】特開２０００−３３２７８６号公報
【特許文献２】特開２０００−３５８０６４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
エントリを削除する場合の問題点を図６を用いて説明する。ルーティングテーブルからエントリを削除すると、二分探索用ルーティングテーブル（境界値テーブル）の２エントリ（ここでは１．０．０．０と２．０．０．０）を削除し、２エントリ（ここでは１．２．４．０と１．２．６．０）を書き換える必要がある。さらに、２エントリを削除したものを再度、メモリ上に隙間無く並べる必要がある。このとき多量のエントリのコピーが発生する。また、エントリの追加時には、追加されたエントリ以降のエントリを１つずつずらすことになり、削除の場合と同様に多量のエントリのコピーが発生する。
【０００９】
また、上記のような二分探索を行うと経路表のエントリの数は二倍必要となる。経路表の経路数は年々増加しており、１０万経路に達するとの報告もある。このような大きなアドレス空間をパケット転送装置の内部に設置された内部メモリと外部メモリとによって実現するメモリ構成が知られている。
【００１０】
これにより、例えば、内部メモリでメモリ容量が不足したときには、外部メモリを用いて不足分を補うことができる。また、内部メモリの記憶内容を更新するときには、外部メモリに新たな記憶内容をあらかじめ用意しておき、これによって内部メモリを高速に更新することもできる。
【００１１】
図７はこのような従来のメモリ構成を示す。図７に示すように、内部メモリ１に記憶されているアドレス空間を論理アドレス空間と呼び、外部メモリ２に記憶されているアドレス空間を物理アドレス空間と呼ぶこととする。この論理アドレス空間と物理アドレス空間とは対応している。このような対応をとるため、従来ＨＡＳＨ関数などを用いた方法があるが、この方法の場合、ＨＡＳＨ関数の結果が他の論理アドレスによるＨＡＳＨ関数の結果と衝突したりすることが確率的に発生する。上記のテーブル検索処理は高速に、かつ、一定時間内に処理する必要があるため、処理時間が確率的に変化するのは好ましくない。
【００１２】
本発明は、このような背景に行われたものであって、論理アドレス空間と物理アドレス空間との対応関係を明確化すると共に当該対応関係を簡単に変更することができるメモリ装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、図１に示すように、ダミーエントリという概念を導入することにより、従来の問題点を解決することを特徴とする。図１はダミーエントリを説明するための図である。ダミーエントリとは、二分探索を行う上で、そのエントリが存在してもしなくても検索結果に影響を与えないエントリである。ダミーエントリの作り方としては、例えば、図１の網かけ部分に示すように、検索結果を両方ともａとしておけば、このエントリは存在してもしなくても検索結果に関係がない。
【００１４】
図２はダミーエントリを用いたエントリの削除を示す図であるが、このようなダミーエントリの概念を導入することにより、エントリを削除するときには、削除するエントリをダミーエントリ化することにより、ごく少ないメモリの書き換えで、これに対応することができる。すなわち、メモリの内容を１つずつずらすという工程を省くことができるため、エントリ削除に伴う処理負荷を大幅に軽減させることができる。また、エントリの追加時には、追加されるエントリをダミーエントリに上書きしてしまえば、メモリの内容を１つずつずらすという工程を省くことができるため、エントリ追加に伴う処理負荷を大幅に軽減させることができる。
【００１５】
さらに、本発明では、メモリのブロック化を行うことを特徴とする。すなわち、メモリを複数のブロックに分割して、それぞれにダミーエントリを設けておけば、ルーティングテーブルの書き換えの際には、該当するブロック内だけの書き換え処理で済む。
【００１６】
さらに、本発明は、論理アドレス空間と物理アドレス空間とを単位となるブロックに分け、論理アドレス空間の各ブロックの先頭アドレスについて論理アドレスと物理アドレスの対応関係を示すポインタテーブルを備えることを特徴とする。
【００１７】
これにより、論理アドレス空間と物理アドレス空間との対応関係を明確化すると共に当該対応関係を簡単に変更することができる。また、論理アドレス空間を記憶するメモリ手段をルータなどのパケット転送装置の内部メモリとして設け、物理アドレス空間を記憶するメモリ手段を外部メモリとして設けておけば、例えば、外部メモリの空きブロックに予め書き換える経路表の内容を用意しておき、論理アドレス空間のブロックと物理アドレス空間のブロックとの対応関係を書き換えることで、一括して経路表の内容を更新することが可能となる。
【００１８】
あるいは、論理アドレス空間の１つのブロック内にダミーエントリが不足したり溢れたりしたら、この過不足を物理アドレス空間を用いて補うことができる。
【００１９】
すなわち、本発明は、宛先アドレスと当該宛先アドレスに対応する次ホップ先とが記録されたエントリを記憶する手段を備え、この記憶する手段は、第一および第二のメモリ手段に分割され、この第一および第二のメモリ手段は、それぞれ複数のブロックに分割され、前記第一のメモリ手段には、若番から老番の順に配列された前記宛先アドレスが当該ブロック数分分割されて当該ブロックにそれぞれ割当てられ、前記第一のメモリ手段のブロックに対応して前記第二のメモリ手段のブロックが配置されたメモリ装置である。
【００２０】
ここで、本発明の特徴とするところは、前記第一のメモリ手段のブロックに対応する前記第二のメモリ手段のブロックを表示するポインタ値が格納されたポインタテーブルを備えたところにある。
【００２１】
例えば、第一のメモリ手段は上述した内部メモリであり、第二のメモリ手段は上述した外部メモリである。
【発明の効果】
【００２２】
本発明のメモリ装置は、論理アドレス空間と物理アドレス空間との対応関係を明確化すると共に当該対応関係を簡単に変更することができる。
【発明を実施するための最良の形態】
【００２３】
本実施例のメモリ構成を図３に示す。
【００２４】
本実施例は、宛先アドレスと当該宛先アドレスに対応する次ホップ先とが記録されたエントリを記憶する手段を備え、この記憶する手段は、内部メモリ１および外部メモリ２に分割され、この内部メモリ１および外部メモリ２は、それぞれ複数のブロックに分割され、内部メモリ１には、若番から老番の順に配列された前記宛先アドレスが当該ブロック数分分割されて当該ブロックにそれぞれ割当てられ、内部メモリ１のブロックに対応して外部メモリ２のブロックが配置されたメモリ装置である。
【００２５】
ここで、本実施例の特徴とするところは、内部メモリ１のブロックに対応する外部メモリ２のブロックを表示するポインタ値が格納されたポインタテーブル３を備えたところにある。
【００２６】
すなわち、内部メモリ１に記憶されている論理アドレス空間を単位となるブロックに分け、同様に外部メモリ２に記憶されている物理アドレス空間を論理アドレス空間のそれと同じ大きさのブロックに分ける。各ブロックの先頭アドレスについて論理アドレス空間と物理アドレス空間との対応関係をポインタテーブル３に保持する。
【００２７】
該当の物理アドレスにアクセスする場合には、その物理アドレスに対応する論理アドレスのブロックの番号を元に、ポインタテーブル３を検索し、物理アドレス空間の対応するブロックの先頭アドレスを求め、それに必要に応じてオフセットを加えることで物理アドレスを求め、所望の物理アドレスにアクセスすることができる。
【００２８】
このように、ブロックに分けることにより、経路表の途中からエントリを削除あるいは経路表の途中に新規エントリを追加する際には、削除または追加するエントリに関するブロックのみを対象としてメモリのリード・ライトを行うことにより、従来、多量に発生していたメモリのリード・ライトを削減することができる。
【００２９】
また、エントリの削除または追加の際に、メモリのリード・ライトが行われるのは内部メモリ１の方であり、例えば、内部メモリ１に新規エントリ追加の余地がなくなったときには、外部メモリ２に、そのブロックの最後のエントリを移すことにより、内部メモリ１に余地を作ることができる。
【００３０】
また、本実施例の内部メモリ１は主メモリであり、補助メモリとしての外部メモリ２と比較して大きなメモリ容量を有する。また、１個のブロックサイズが２５６エントリとすると、論理アドレス空間が１Ｍバイトであれば、１Ｍバイト÷２５６＝４０９６ブロックが必要になる。さらに、このときのブロック内部の使用率を５０％とすると、８１９２ブロックが必要となる。
【００３１】
本実施例の物理アドレスの書き換えを図４を参照して説明する。図４は本実施例の物理アドレスの書き換え手順を説明するための図である。図４に示すように、物理アドレスのブロック（＃２）の記憶内容を一括して書き換える際には、物理アドレスの空きブロック（＃４）に予めその内容を用意しておき、ポインタテーブル３で論理ブロックと物理ブロックの対応関係（＃２→＃４）を書き換えることで、一括して経路表の内容を書き換えることができる。その後、ブロック（＃２）の記憶内容は削除または上書きされる。
【産業上の利用可能性】
【００３２】
本発明のメモリ装置は、論理アドレス空間と物理アドレス空間との対応関係を明確化すると共に当該対応関係を簡単に変更することができる。これにより、物理アドレスの空きブロックに予め記憶内容を用意しておき、論理ブロックと物理ブロックとの対応関係を書き換えることで、一括して経路表の内容を更新することが可能となる。あるいは、論理アドレス空間にダミーエントリが不足したり、あるいは、溢れたりしたときに、物理エントリ空間によって、ダミーエントリの過不足を補うことができる。したがって、今後、経路表のエントリ数が増加し、経路表の更新処理に伴うメモリのリード・ライトの処理が増加してもこれに対応することができる。
【図面の簡単な説明】
【００３３】
【図１】本発明のダミーエントリを説明するための図。
【図２】本発明のエントリの削除を説明するための図。
【図３】本実施例のメモリ構成図。
【図４】本実施例の経路表の書き換え手順を説明するための図。
【図５】ルーティングテーブルから二分探索ルーティングテーブルを作成する手順を示す図。
【図６】従来のエントリの削除または追加の問題点を示す図。
【図７】従来のメモリ構成図。
【符号の説明】
【００３４】
１  内部メモリ
２  外部メモリ
３  ポインタテーブル
【図１】
2005117210.tif 000003
【図２】
2005117210.tif 000004
【図３】
2005117210.tif 000005
【図４】
2005117210.tif 000006
【図５】
2005117210.tif 000007
【図６】
2005117210.tif 000008
【図７】
2005117210.tif 000009