(57)【特許請求の範囲】
【請求項１】
上位ビットから任意のビット長で任意に区切ることにより階層化されたＩＰアドレスを共有する網が上位の該階層化されたＩＰアドレスの階層化網により相互接続可能となるようにルータ間で交換した経路情報に基づき経路検索を行う網の経路制御方法において、
各ルータが、該ルータを境界としている階層化網の内の最上位の階層化網の階層情報を該経路情報に含めて交換するとともに、送信元ホストがパケットの送信先ホストのＩＰアドレスに該階層情報を付与して送信し、中継するルータが該階層情報に基づいて該経路検索を行うことを特徴とした方法。
【請求項２】
請求項１において、
各ルータが、該パケットに付与された階層情報が示す階層化されたＩＰアドレスと自ルータ中の該階層情報における同階層のＩＰアドレスとが同一の場合には該パケットに付与された階層情報が示す階層より下位の階層に対して経路検索を行い、それ以外の場合には該パケットに付与された階層情報が示す階層のＩＰアドレスのみを用いて経路検索を行うことを特徴とした方法。
【請求項３】
請求項１又は２において、
各ルータは、該パケットに該階層情報が付与されていないときには、該階層情報が有る網への経路と異なる経路検索を行うことを特徴とした方法。
【請求項４】
請求項１乃至３のいずれかにおいて、
該ホストとして、該ルータを用いることを特徴とした方法。
【請求項５】
上位ビットから任意のビット長で任意に区切ることにより階層化されたＩＰアドレスを共有する網が上位の該階層化されたＩＰアドレスの階層化網により相互接続可能となるようにルータ間で交換した経路情報に基づき経路テーブルにより検索を行う網の経路制御装置において、
各ルータが、該ルータを境界としている階層化網の内の最上位の階層化網の階層情報を該経路情報に含めて交換し経路テーブルとして保持するとともに、送信元となるホストがパケットの送信先となるホストのＩＰアドレスに該階層情報を付与して送信し、中継するルータが該階層情報に基づいて該経路テーブルによる検索を行うことを特徴とした装置。
【請求項６】
請求項５において、
各ルータは、該パケットに該階層情報が付与されていないときに、該階層情報が有る網への経路と異なる経路検索を行うための別の経路テーブルを備えていることを特徴とした装置。
【請求項７】
請求項５又は６において、
各ルータが、該パケットを送受信するためのパケット送受信手段と、該経路情報を経路テーブルとして保持する経路テーブル保持手段と、上位層からの要求により該送信元ホストとなるときにパケットを作成／送信するパケット作成手段と、隣接ルータから受信した該経路情報に基づいて該経路テーブルを作成又は更新する経路情報受信手段と、該経路情報を隣接ルータや該送信先ホストに送信する経路情報送信手段と、該パケット送受信手段から受信したパケットに対して中継処理を行う中継パケット処理手段と、で構成されており、該中継パケット処理手段が、該パケットに付与された階層情報が示す階層化されたＩＰアドレスと自ルータ中の該階層情報における同階層のＩＰアドレスとが同一の場合には該パケットに付与された階層情報が示す階層より下位の階層に対して該経路テーブルによる検索を行い、それ以外の場合には該パケットに付与された階層情報が示す階層のＩＰアドレスのみを用いて該経路テーブルによる検索を行うことを特徴とした装置。
【請求項８】
請求項７において、
該パケット送受信手段が、伝送路から受信したパケットが該経路情報なら該経路情報受信手段へ、それ以外なら中継パケット処理手段に渡すパケット受信部と、該経路情報送信手段又は該中継パケット処理手段から渡されたパケットに対し伝送路への送信処理を行うパケット送信部と、で構成されていることを特徴とした装置。
【請求項９】
請求項７において、
該経路テーブル保持手段が、階層化されていない網への該経路情報を保持する非階層化網用テーブル部と、階層化網への該経路情報を保持する階層化網用テーブル部と、で構成されていることを特徴とした装置。
【請求項１０】
請求項７において、
該パケット作成手段が、該ホストが送信するパケットを作成するパケット作成部と、該パケット作成部から指示された送信先アドレスに対して該経路テーブル保持手段に基づき経路検索を行う経路検索部と、で構成されていることを特徴とした装置。
【請求項１１】
請求項９において、
該経路情報受信手段が、該パケット送受信手段から渡された経路情報内の各々のエントリに対し、階層化拡張子の有無に基づいて階層化網のエントリか、非階層化網のエントリかの分類を行う階層化網用経路情報抽出部と、該階層化網用経路情報抽出部により抽出された非階層化網宛の経路情報のエントリを該経路テーブル保持手段の該非階層化網用テーブル部に書き込む非階層化網用テーブル構築部と、で構成されていることを特徴とした装置。
【請求項１２】
請求項９において、
該経路情報送信手段が、該経路情報の送信を一定時間毎に該送信経路情報作成部に該経路情報の送付先を指示するタイマ部と、該経路情報を送信する隣接網の階層を送信経路情報作成部に通知する階層指示部と、で構成され、該送信経路情報作成部が、該非階層化網用テーブル部及び該階層化網用テーブル部から該経路情報を作成し該パケット送受信手段経由で隣接ルータ又は該ホストに送信することを特徴とした装置。
【請求項１３】
請求項９において、
該中継パケット処理手段が、階層化対応網宛パケット選択部、非階層化網宛パケット用経路制御部、非階層化網宛経路テーブル検索部、階層化網宛パケット用経路制御部、特定階層用経路テーブル検索部、不特定階層用経路テーブル検索部、及び同一網内パケット転送部から成り、該階層化対応網宛パケット選択部が、該パケット送受信手段から渡されたパケットの階層化拡張子の有無に基づいて送信先が階層化網か否かを判断し、該階層化網であれば該階層化網宛パケット用経路制御部に、非階層化網であれば該非階層化網宛パケット用経路制御部にそれぞれ該パケットを渡し、該送信先アドレスに該階層化拡張子が付与されており、かつ該階層化拡張子が示す階層の送信先ＩＰアドレスが中継処理をしているルータの同階層のアドレスと同値の場合、該送信先ＩＰアドレスのネットワーク部における階層化拡張子より下位のビットとルータ自身が所属する網自身のＩＰアドレスが合致した場合、該送信先ホストがルータの所属網内にあると判断し、該同一網内パケット転送部を介して該送信先ホスト自身にパケットを配送し、該非階層化網宛パケット用経路制御部が、該パケットの送信先アドレスのネットワーク部への経路テーブルの検索を該非階層化網宛経路テーブル検索部に指示し、検索結果から分かる次に中継処理を行うルータへ該パケット送受信手段を通して該パケットを送信し、該非階層化網宛経路テーブル検索部が、該パケットの送信先アドレスのネットワーク部全体から次に送信すべきルータを該経路テーブル保持手段の非階層化網用テーブル部から検索し、その検索結果を該非階層化網宛パケット用経路制御部に通知し、該階層化網宛パケット用経路制御部が、送信先アドレスに階層化拡張子が付与されており、かつ該階層化拡張子が示す階層の送信先アドレスが中継処理をするルータの同階層のアドレスと異なる場合、該階層化拡張子が示す階層の網に該パケットは未だ到達していないと判断して経路検索を該特定階層パケット用経路テーブル検索部に指示し、検索結果に基づき送信処理を行い、これ以外の場合には、該パケットが階層化拡張子が示す階層の網に到達したと判断し、該送信先ＩＰアドレスのネットワーク部における該階層化拡張子より下位のビットを対象に経路検索するよう該不特定階層経路テーブル検索部に指示し、その結果、該不特定階層経路テーブル検索部から通知された階層情報を新たな階層拡張子として書き換えた後に送信処理を行い、該特定階層経路テーブル検索部が、該階層化網宛パケット用経路制御部の指示に基づいて該経路テーブル保持手段の該階層化網用テーブル部に対して該送信先ＩＰアドレスの内、該階層化拡張子で示された範囲のみを対象に経路テーブルの検索を行い、検索結果を該階層化網宛パケット用経路制御部に通知し、該不特定階層経路テーブル検索部が、該階層化網宛パケット用経路制御部の指示に基づいて該経路テーブル保持手段の該階層化網用テーブル部に対して該送信先ＩＰアドレスのネットワーク部における階層化拡張子より下位のビットを対象に経路テーブルの検索を行い、検索結果を該階層化網宛パケット用経路制御部に通知し、そして、該同一網内パケット転送部が、ルータと同一網内にいる該ホストにパケットを転送することを特徴とした装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は網（ネットワーク）の経路制御方法及び装置に関し、特に階層化された網の経路制御方法及び装置に関するものである。
オフィスやキャンパスにおけるインターネット／イントラネットはその急速な普及に伴い、従来のように実験的な網から業務の中核を担う網へと変貌している。これに伴い、網の構成をシンプルにすることで、網の管理を簡素にする階層化網が着目されて来ている。
【０００２】
【従来の技術】
１．ＩＰアドレスとその表記法
現在、一般的に使用されているＩＰ(Internet Protocol)アドレスであるＩＰv4（ＩＰversion4) アドレスは図１０に示すように３２ビットのアドレス長を持っており、任意の、例えば８ビット毎に'.' で区切って表記（階層化）する。アドレスは個々のノード毎に割り振られ、当該ノードが所属する網ＮＷを示すネットワーク部と個々のノード（ホスト）ＨＳＴを示すホスト部の２部から成り、このＩＰアドレスの後ろに'/' を付けて対象とするネットワーク部のビット数を表記するのが一般的である。
【０００３】
例えば図示のアドレス「133.160.115.5/24」は「133.160.115.5」の先頭２４ビット(133.160.115) がネットワーク部で、「5」がホスト部であることを示す。またホスト部が「0」のＩＰアドレスは網自身を指す。すなわち、アドレス「133.160.115」の網は「133.160.115.0/24」と表記される。
【０００４】
２．現在のＩＰ網の構成
現在のＩＰ網では例えば図１１に示すように網ＮＷ１とＮＷ２とがルータＲAで接続され、網ＮＷ２とＮＷ３とがルータＲBで接続され、網ＮＷ２とＮＷ４とがルータＲCで接続されているような場合、アドレス「133.160.115.0/24」の網ＮＷ１と、アドレス「133.160.116.0/24」の網ＮＷ３とが隣接しておらず、網ＮＷ２が介在している。
【０００５】
このように、上記の表示によるアドレスを有するＩＰ網では、任意の網が介在する可能性があり、アドレスに基づいた階層化が行われていない。
【０００６】
３．ＩＰv4の経路選択方法
パケットは各網の境界に設置されたルータにより経路選択が行われ、またこれに必要な経路情報はルータ間で定期的に交換されている。
従来の経路情報の交換例が図１２に示されている。アドレス「133.160.115.0/24」の経路情報がルータＲAからルータＲBに交換されており、これによりルータＲBはアドレス「150.123.212.0/24」の先にアドレス「133.160.115.0/24」の網ＮＷ１が存在することが分かる。
【０００７】
同様にルータＲAはルータＲBからの経路情報によりアドレス「150.123.212.0/24」の網ＮＷ２の先にアドレス「133.160.116.0/24」の網ＮＷ３が存在することを知る。ルータＲCとルータＲA, ＲBとの経路情報交換も同様である。各ルータはこの経路情報をテーブル化して次回の経路交換時に更新する。
【０００８】
図１２で経路交換された網におけるパケット中継の例が図１３に示されており、以下に順を追って説明する。
(1) ホストＨaからホストＨbに宛てに送信された送信先アドレス(Dst)「133.160.116.1」を有するＩＰパケットP1は「133.160.115.0/24」の網ＮＷ１のルータであるルータＲAに与えられる。
【０００９】
(2) ルータＲAは自身の送信先アドレスのネットワーク部(133.160.116.)全体を対象に経路情報テーブル（ルーティングテーブル）を検索する。この例では、ルータＲBに関するアドレス「133.160.116.0/24」の網ＮＷ３とルータＲCに関するアドレス「133.160.117.0/24」の網ＮＷ４とがテーブルに格納されている。
【００１０】
(3) テーブル検索結果からルータＲAはルータＲBが次の送信先であることを把握し、ルータＲBにパケットP1を転送する。
(4) パケットP1を受信したルータＲBはパケットP1のネットワーク部(133.160.116)から自身の配下の網ＮＷ３宛のパケットであることを知り、次いでパケットP1のホスト部(0/24)を見てホストＨbへパケットP1を転送する。
【００１１】
ここで重要な点は上記(2)項と(4)項において、経路検索をネットワーク部全てを対象に行っていることである。これは網がＩＰアドレスに基づいて階層化されていないため、例えばルータＲAはネットワーク部の一部(133.160)だけを対象にした検索ではルータＲBとルータＲCのどちらに送信してよいか判断できないからである。
【００１２】
【発明が解決しようとする課題】
昨今のインター／イントラネットの大規模化に伴い、網構成をシンプルにし、集中管理を行い易くするニーズが高まっている。このため階層的なＩＰ網の構築が着目されている。
【００１３】
しかしながら、階層化ＩＰ網を実現するためには上記のように、
▲１▼網構成そのものがＩＰアドレスに基づいた階層構造となっていない、
▲２▼経路制御が階層化に対応した仕組みになっていない、
という問題点がある。
【００１４】
このうち前者▲１▼についてはアドレスの階層化を推し進めることで網構成をも階層化しようとする新しいバージョンのＩＰ＝ＩＰv6(version6)が標準化団体で検討されるなど、解決が進みつつあるが、後者▲２▼の問題点はまだ解決されていない。
従って本発明は、上位ビットから任意のビット長で任意に区切ることにより階層化されたＩＰアドレスを共有する網が上位の該階層化されたＩＰアドレスの階層化網により相互接続可能となるようにルータ間で交換した経路情報に基づき経路検索を行う網の経路制御方法及び装置において、経路検索時に参照すべき送信先アドレスの領域を限定して階層情報の交換を簡素化し高速な経路検索を実現することを課題とする。
【００１５】
【課題を解決するための手段】
１．基本概念
階層化が進んだ網での経路制御はＩＰアドレスのネットワーク部全てを対象に行う必要はなく、階層毎に行えばよい。例えば図１に示す網はＩＰアドレスの構造に基づいて階層化した網である。
【００１６】
この網において、アドレス「α.A.a.0/24」の網ＮＷ111上のホストＨAがアドレス「β.B.a.0/24」の網ＮＷ221上のホストＨBへパケットＰを送信する場合、アドレス「α.0.0.0/8」配下の網ＮＷ10ではホストＨBのアドレス中「β」についてのみ着目して経路選択を行えばよく、ホストＨBで経路選択を行うのはアドレス「β.0.0.0/8」配下の網ＮＷ20に入ってからでよい。つまり常に全ネットワーク部を対象に経路検索を行う必要がない。
【００１７】
このため本発明では、
▲１▼上述した従来の経路情報交換の内容に加えて階層情報も交換する、
▲２▼パケットの送信先ＩＰアドレスに階層情報を付与する、
という手法により、各ルータでの経路検索時に送信先アドレスの一部、すなわちネットワーク部内の適切な階層位置のみを対象に経路選択を行うことを可能とする。
【００１８】
２．解決手段
図１に示す階層化網は以下のルールで構築された網である。
▲１▼上位階層は下位階層を包含してなくてはならない（図１の例においてアドレス「α.A.a.0/24」の網ＮＷ111と「α.A.b.0/24」の網ＮＷ112との間に「α.B.b.0/24」の網を置くことはできない) 。
▲２▼同一上位階層に接続する同階層の網は接続可能である( 図１の例においてアドレス「α.A.a.0/24」の網ＮＷ111と「α.A.b.0/24」の網ＮＷ112とは接続可) 。
【００１９】
図１に示される階層化網対応ルータＲ２〜Ｒ６は階層化網用に経路制御を行い、それに基づいてパケット中継処理を行うルータであり、特にルータＲ４について図示したように、図２に示すパケット送受信手段１、図３に示す経路テーブル保持手段２、図４に示すパケット作成手段３、図５に示す経路情報受信手段４、図６に示す経路情報送信手段５、及び図７に示す中継パケット処理手段６を有する。以降、単にルータと称する時には階層化網対応ルータを指すものとする。
【００２０】
なお上記のルータ構成要素中のパケット送受信手段１、経路テーブル保持手段２、パケット作成手段３、経路情報受信手段４を用いることで階層化網上のホストＨAを実現できるが、これらの各手段１〜４は以下に述べる階層化網対応ルータに包含される機能なため、以下では特に区別はしない。
【００２１】
各ルータが保持する各手段１〜６はアドレスの階層を示すＩＰアドレスに付与した独自の拡張子である階層情報としての階層化拡張子を扱えるものとする。これらは、自ルータを境界としている階層化網の内の最上位の階層化網の階層化拡張子を経路情報に含めて交換することにより行われる。
【００２２】
この場合、受信した経路情報中の階層化拡張子は全てルータに保持される。
【００２３】
階層化拡張子を用いたアドレス表記は、例えば「133.160.115.0/17/24」となり、この例では「133.160.115.0」の17ビット目から24ビット目にかけての階層、すなわち「115」の階層を示す。また、拡張子「115/16/24」は17ビット目から24ビット目にかけての階層が「115」であることを示す。
【００２４】
以下、各ルータ内の各手段１〜６について説明する。
2.1 パケット送受信手段１（図２参照）：
ＩＰパケットを送受信するための手段であり、パケット受信部１１と、パケット送信部１２から成る。
【００２５】
パケット受信部１１：いわゆるＩＰパケットの受信部であり、伝送路から受信したパケットが経路情報なら経路情報受信手段４へ、それ以外なら中継パケット処理手段６に渡す。
パケット送信部１２：いわゆるＩＰパケットの送信部であり、経路情報送信手段５または中継パケット処理手段６から渡されたパケットに対し伝送路への送信処理を行う。
【００２６】
2.2 経路テーブル保持手段２（図３参照）：
経路情報をテーブルとして保持する手段であり、非階層化網用テーブル部２１と、階層化網用テーブル部２２から成る。
非階層化網用テーブル部２１：階層化されていない網への経路情報を保持する従来のテーブル部である。
階層化網用テーブル部２２：階層化網への経路情報を保持するテーブルである。
【００２７】
2.3 パケット作成手段３（図４参照）：
上位層からの要求により自ルータ／ホストが送信元となり、パケットを作成／送信する手段であり、パケット作成部３１と経路検索部３２から成る。
パケット作成部３１：自ノードが送信するパケットを作成する部であり、次の機能を有する。
【００２８】
▲１▼上位層からの指示によりＩＰパケットを作成する。
▲２▼該パケットの送信先アドレスに対する経路検索を経路検索部３２に指示し、送信先が階層化網の場合には検索結果に基づく階層化拡張子の付与を行う。
▲３▼該パケットの送信をパケット送受信手段１に依頼する。
【００２９】
経路検索部３２：パケット作成部３１から指示された送信先アドレスに対して、経路テーブル保持手段２を用いて経路検索を行う機能を有する。なお検索結果が階層化網用テーブル部２２内にあった場合には、検索結果と併せて階層化拡張子もパケット作成部３１に渡す。
【００３０】
2.4 経路情報受信手段４（図５参照）：
隣接ルータから受信した経路情報に基づいて、経路テーブルを作成する手段であり、階層化網用経路情報抽出部４１と非階層化網用テーブル構築部４２と階層化網用テーブル構築部４３から成る。
【００３１】
階層化網用経路情報抽出部４１：パケット送受信手段１より渡された経路情報パケット内の各々のエントリに対し、階層化拡張子の有無に基づいて階層化網のエントリか、非階層化網のエントリかの分類を行う。
非階層化網用テーブル構築部４２：階層化網用経路情報抽出部４１により抽出された非階層化網宛の経路情報のエントリを経路テーブル保持手段２の非階層化網用テーブル部２１に書き込む、従来の経路テーブル構築部である。
【００３２】
階層化網用テーブル構築部４３：階層化網用経路情報抽出部４１により抽出された階層化網宛の経路情報のエントリから、自ルータ/ ホストにおいて検索対象となる階層のみを抽出して経路テーブル保持手段２の階層化網用テーブル部２２を書き込む。
【００３３】
2.5 経路情報送信手段５（図６参照）：
経路情報を隣接ルータやホストに送信する手段であり、タイマ部５１と階層指示部５２と送信経路情報作成部５３から成る。
タイマ部５１：経路情報の送信を一定時間毎に送信経路情報作成部５３に経路情報の送付先を指示する機能を有する従来のタイマ部である。
【００３４】
階層指示部５２：経路情報を送信する隣接網の階層を送信経路情報作成部５３に通知する機能を有する。なお階層指示部５２は隣接網の階層をユーザからの指定もしくはここに記載しない何らかの手段により予め知っているものとする。
送信経路情報作成部５３：非階層化網用テーブル部２１と階層化網用テーブル部２２から経路情報を作成し、パケット送受信手段経由で隣接ルータやホストに送信する手段である。
【００３５】
非階層化網用テーブル部２１からの経路情報の作成は従来と同様であり、階層化網用テーブル部２２からは階層指示部５２から指示に基づいて階層化に対応した経路情報を作成する。
【００３６】
2.6 中継パケット処理手段６（図７参照）：
パケット送受信手段１より受信したパケットに対し、中継処理を行う手段であり、階層化対応網宛パケット選択部６１、非階層化網宛パケット用経路制御部６２、非階層化網宛経路テーブル検索部６３、階層化網宛パケット用経路制御部６４、特定階層経路テーブル検索部６５、不特定階層用経路テーブル検索部６６、及び同一網内パケット転送部６７から成る。
【００３７】
階層化対応網宛パケット選択部６１：パケット送受信手段１から渡されたパケットの階層化拡張子の有無に基づいて送信先が階層化網か否かを判断し、階層化網であれば階層化網宛パケット用経路制御部６４に、非階層化網であれば非階層化網宛パケット用経路制御部６２に中継パケットを渡す機能を有する。
【００３８】
また、送信先ＩＰアドレスのネットワーク部における階層化拡張子より下位のビットとルータ自身が所属する網自身のＩＰアドレスが合致した場合、送信先となっているホストは当該ルータが所属する網内にあると判断し、同一網内パケット転送部６７に中継パケットを転送し送信先ホスト自身にパケットを配送する。
【００３９】
非階層化網宛パケット用経路制御部６２：パケットの送信先アドレスのネットワーク部への経路テーブルの検索を非階層化網宛経路テーブル検索部６３に指示し、検索結果から分かる次に中継処理を行うルータへパケット送受信手段１を通して、パケットを送信する機能を有する従来の経路制御部である。
【００４０】
非階層化網宛経路テーブル検索部６３：パケットの送信先アドレスのネットワーク部全体から次に送信すべきルータを経路テーブル保持手段２の非階層化網用テーブル部２１から検索し、その検索結果を非階層化網宛パケット用経路制御部６２に通知する機能を有する従来の経路テーブル検索部である。
【００４１】
階層化網宛パケット用経路制御部６４：階層化網宛てのパケットに対する経路制御部であり、以下の機能を有する。
▲１▼送信先アドレスに階層化拡張子が付与されており、かつ階層化拡張子が示す階層の送信先アドレスが中継処理をするルータの同階層のアドレスと異なる場合、本制御部は階層化拡張子が示す階層の網にパケットはまだ到達していないと判断する。この場合、経路検索を特定階層パケット用経路テーブル検索部に指示し、検索結果に基づき送信処理を行う。
【００４２】
▲２▼上記以外、すなわち送信先アドレスに階層化拡張子が付与されており、かつ階層化拡張子が示す階層の送信先ＩＰアドレスが中継処理をしているルータの同階層のアドレスと同値の場合、以下の処理が行われる。
【００４３】
パケットが階層化拡張子が示す階層の網に到達したと判断し、送信先ＩＰアドレスのネットワーク部における階層化拡張子より下位のビットを対象に経路検索するよう不特定階層経路テーブル検索部６５に指示し、その結果、不特定階層経路テーブル検索部６６から通知された階層情報を新たな階層拡張子として書き換えた後に送信処理を行う。
【００４４】
特定階層経路テーブル検索部６５：階層化網宛パケット用経路制御部６４の指示に基づいて、経路テーブル保持手段２の階層化網用テーブル部２２に対して、送信先ＩＰアドレスの内、階層化拡張子で示された範囲のみを対象に経路テーブルの検索を行い、検索結果を階層化網宛パケット用経路制御部６４に通知する機能を有する。
【００４５】
不特定階層経路テーブル検索部６６：階層化網宛パケット用経路制御部６４の指示に基づいて、経路テーブル保持手段２の階層化網用テーブル部２２に対して、送信先ＩＰアドレスのネットワーク部における階層化拡張子より下位のビットを対象に経路テーブルの検索を行い、検索結果を階層化網宛パケット用経路制御部６４に通知する機能を有する。
【００４６】
同一網内パケット転送部６７：ルータと同一網内にいるホストにパケットを転送する部であり、パケットの送信先ＩＰアドレスから階層化拡張子を除去し、さらにARP(Address Resolution Protocol)等の既存の同一網内送信手段を用いてパケットを送信先となっているホスト自身に転送する機能を有する。
【００４７】
３．通信手順
3.1経路情報受信
(1)経路情報交換用パケットを受信したパケット送受信手段１のパケット受信部１１は経路情報のパケットであると判断して、経路情報受信手段４へ該パケットを渡す。
【００４８】
(2)経路情報受信手段４の階層化網用経路情報抽出部４１において、経路情報の各エントリが階層化網を対象にしているかを各エントリにおける階層化拡張子の有無により仕分けし、階層化拡張子を有するエントリは階層化網用テーブル構築部４３に、階層化拡張子を有さないエントリは非階層化網用テーブル構築部４２に渡す。
【００４９】
(3)階層化網用テーブル構築部４３では階層化拡張子が示す階層のアドレス情報を対象として経路テーブルを作成し、階層化網用テーブル部２２に書き込む。
(4)非階層化網用テーブル構築部４２では従来技術を用いて階層化に対応しない経路テーブルを作成し、非階層化網用テーブル部２１に書き込む。
【００５０】
以上により階層化網への経路情報と非階層化網への経路情報の両方に対して、経路検索用テーブルが作成できる。
3.2経路情報送信
(1)経路情報送信手段５内のタイマ部５１が送信経路情報作成部５３に経路情報を送信する隣接網を通知する。
【００５１】
(2)送信経路情報作成部５３が非階層化網用テーブル部２１と階層化網用テーブル部２２から経路情報を以下の手順で作成する。
▲１▼経路情報を送信する隣接網の階層以上を対象とし、階層化網用テーブル部２２から経路情報のエントリを作成する。このとき各エントリに対象とする階層を明示するために階層化拡張子を付与する。なお隣接網の階層は階層指示部５２から予め通知されている。
【００５２】
▲２▼従来技術を用いて非階層化網用テーブル部２１から経路情報のエントリを作成する。
(3)送信経路情報作成部５３は項で作成したエントリを含む経路交換用パケットを作成し、パケット送受信手段１を経由して▲１▼項においてタイマ部５１から指示された隣接網へ送信する。
【００５３】
3.3パケット中継処理
(1)経路情報交換用パケット以外を受信したパケット送受信手段１のパケット受信部１１が中継すべきパケットであると判断して、中継パケット処理手段６へ渡す。
【００５４】
(2)中継パケット処理手段６の階層化対応網宛パケット選択部６１において、パケットの送信先が階層化網を対象にしているかをパケットの送信先ＩＰアドレスに階層化拡張子が付与されているか否かによって判断し、階層化拡張子を有するパケットは階層化網宛パケット用経路制御部６４に、有さないパケットは非階層網宛パケット用経路制御部６２に渡される。以降の処理は次の3 つに分かれる。
【００５５】
(a)非階層化網宛パケットの中継処理
i. 非階層化網宛パケット用経路制御部６２は非階層化網宛経路テーブル検索部６３にパケットの送信先アドレスへの経路検索を依頼する。
ii. 非階層化網宛経路テーブル検索部６３は非階層化網用テーブル部２１から次に送信すべきルータを検索し、検索結果を非階層化網宛パケット用経路制御部６２に指示する。
iii. 非階層化網宛パケット用経路制御部６２は検索結果であるルータにパケット送受信手段１経由でパケットを送信する。
【００５６】
(b)階層化網宛パケットの中継処理（同一もしくは上位階層宛処理）
i. 階層化網宛パケット用経路制御部６４はパケットに付与された階層化拡張子からで示される階層の送信先アドレスと中継処理を行っているルータ自身の同階層のアドレスを比較する。これらが異なる場合には特定階層経路テーブル検索部６５に階層化拡張子と送信先アドレスのうち階層化拡張子が示すアドレスだけを渡す。
【００５７】
ii. 特定階層経路テーブル検索部６５は階層化拡張子で示された階層のアドレスのみを対象に階層化網用テーブル部２２から、次に送信すべきルータを検索し、結果を階層化網宛パケット用経路制御部６４に通知する。
iii. 階層化網宛パケット用経路制御部６４は検索結果であるルータにパケット送受信手段１経由で本パケットを送信する。
iv. なお本処理ではパケットに付与されている階層化拡張子は変更されない。
【００５８】
(c)階層化網宛パケットの中継処理（下位階層宛処理)
i. 階層化網宛パケット用経路制御部６４はパケットに付与された階層化拡張子からで示される階層の送信先アドレスと中継処理を行っているルータ自身の同階層のアドレスを比較する。
【００５９】
これが同一値でかつ送信先ＩＰアドレスのネットワーク部における階層化拡張子より下位のビットとルータ自身が所属する網自身のＩＰアドレスが合致しなかった場合、パケットは自身の階層化拡張子が示す階層では送信先アドレスと同一の階層に到達したが、まだ送信先ホストが所属する網には到達していないことを意味する。このため、本制御部は送信先ＩＰアドレスのネットワーク部における階層化拡張子より下位のビットを対象に経路検索するよう不特定階層経路テーブル検索部６６に指示する。
【００６０】
ii. 不特定階層経路テーブル検索部６６は階層化網宛パケット用経路制御部６４から渡されたアドレスを対象に階層化網用テーブル部２２から、次に送信すべきルータを検索し、検索結果を階層化網宛パケット用経路制御部６４に通知する。
なお、このとき階層化網用テーブル部２２のエントリに記載されている階層化拡張子も併せて通知する。
【００６１】
iii. 階層化網宛パケット用経路制御部６４はパケットに付与されていた階層化拡張子を不特定階層経路テーブル検索部６６から通知された階層化拡張子に書き換え、さらに検索結果であるルータにパケット送受信手段１経由で本パケットを送信する。
【００６２】
(d)階層化網宛パケットの中継処理（同一網内ホスト宛転送処理)
i. 階層化網宛パケット用経路制御部６４はパケットに付与された階層化拡張子で示される階層の送信先アドレスと中継処理を行っているルータ自身の同階層のアドレスとを比較する。
【００６３】
これが同一値でかつ送信先ＩＰアドレスのネットワーク部における階層化拡張子より下位のビットとルータ自身が所属する網自身のＩＰアドレスが合致した場合、パケットは送信先ホストが属する網のルータに到達したことを意味する。このため本制御部はパケットを同一網内パケット転送部６７に渡す。
【００６４】
ii. 同一網内パケット転送部６７はパケットに付与されていた階層化拡張子を除去し、さらにARP(Address Resolution Protocol)等の既存の同一網内送信手段を用いてパケットを送信先となっているホスト自身に転送する。
【００６５】
3.4パケット送信処理
(1)上位層からの要求により本ルータ自身が送信元となり、パケットを送信する処理を以下に示す。上位層からの指示に基づいてパケット作成手段３のパケット作成部３１はＩＰパケットを作成し、上位層から指示された送信先アドレスに対して経路検索を行うよう経路検索部３２に指示する。
【００６６】
(2)経路検索部３２は送信先パケット作成部３１から指示された送信先アドレスに対して、経路テーブル保持手段２を用いて経路検索を行う。検索結果が階層化網用テーブル部２２内のエントリであった場合には検索結果である次に送るべきルータのアドレスとエントリが持つ階層化拡張子をパケット作成部３１に渡す。
【００６７】
(3)パケット作成部３１は経路検索部３２からの応答に基づき、送信先が階層化網の場合、検索結果に基づきＩＰパケットの送信先アドレス部に階層化拡張子を付与し、パケット送受信手段１を経由してパケットを検索結果のルータに送信する。 (4)送信先が非階層化網の場合には従来通り、階層化拡張子を付与せずにパケット送受信手段１を経由して検索結果のルータにパケットを送信する。
【００６８】
以上の動作から、本発明では階層化アドレスに基づいて階層的に構築されたＩＰ網において、経路交換時及びパケット中継時に階層化拡張子を導入することで送信先アドレスの一部のみを対象とした階層化経路制御を実現することができる。
【００６９】
【発明の実施の形態】
以下に本発明に係る網の経路制御方法及び装置の一実施例を述べる。この実施例は経路情報の交換の例と、交換された経路情報に基づくパケット中継の例と、に分けて示す。なお本実施例で用いる網は以下のような構成となっている。
【００７０】
▲１▼ＩＰアドレスの上位８ビット毎に３階層化されている。すなわち/1/8の階層、/9/16 の階層、/17/24の階層であり、上述した拡張子のルールに則って階層化されている。
▲２▼例えばアドレス「202.33.10.0/24」と「202.33.95.0/24」は階層化されていない網であり、それぞれ階層化網と接続されている。階層化網内のルータでは非階層化網のアドレスが既知であるとする。
【００７１】
１．経路情報の交換
図８に本発明による経路情報の交換例を示す。本図下部の矢印はルータ間で交換される経路情報である。例えばルータＲ2はルータＲ3からアドレス「145.0.0.0/1/8」及び「133.30.0.0/9/16」という網接続されたアドレス階層の内、最上位階層に属する二つの階層化対応の経路情報と、アドレス「202.33.95.0/24」という一つの階層化未対応の経路情報を受信しており、ルータＲ2からR3へはアドレス「133.160.10.0/17/24」という一つの階層化対応の経路情報と、アドレス「202.33.10.0/24」という一つの階層化未対応の経路情報を送信している。
【００７２】
以下、ルータＲ2,R3,R4までの経路情報の交換例について説明する。
(1) ルータＲ2における経路情報の受信
(a)ルータＲ2はルータＲ1から経路情報パケット（図示せず）を受信し、経路情報受信手段４内の階層化網用経路情報抽出部４１が該パケットから「202.33.10.0/24」のエントリを検出し、さらにこのエントリに階層化拡張子が付いていないことから非階層網への経路情報であると判断し、非階層
化網用テーブル構築部４２に経路テーブル保持手段２内の非階層化網用テーブル部に本エントリを書き込むよう指示する。
【００７３】
(b)ルータＲ2はルータＲ3から経路情報パケットを受信し、経路情報受信手段４内の階層化網用経路情報抽出部４１が該パケットから「202.33.95.0/24」のエントリに階層化拡張子がついていないことから非階層化網への経路情報であると判断し、非階層化網用テーブル構築部４２経由で非階層化網用テーブル部２１に該エントリを書き込む。
【００７４】
一方、階層化網用経路情報抽出部４１は該パケットの「145.0.0.0/1/8」, 「133.30.0.0/9/16」の二つのエントリには階層化拡張子が付与されていることから階層化網への経路情報であると判断し、経路テーブル保持手段２内の階層化網用テーブル構築部４３に階層化網用テーブル部２２への書き込みを指示する。階層化網用テーブル構築部４３は階層化拡張子が示す部分のみ、すなわち「145/1/8」と「30/9/16」を階層化網用テーブル部２２に書き込む。
【００７５】
(c)以上でルータＲ2の経路テーブルが完成する。本テーブルはルータＲ1, R2, R3からの次回の経路交換により更新される。
(2) ルータＲ2における経路情報の送信
(a)ルータＲ2の経路情報送信手段５のタイマ部５１がルータＲ3への経路情報の送信を送信経路情報作成部５３に指示する。
【００７６】
(b)ルータＲ2の経路テーブルのうちルータＲ3以外からの経路情報で作成されたエントリとルータＲ2とルータＲ3が共有しない網ＮＷ111(133.160.10.0)について経路情報を作成し、送信する。すなわち「133.160.10.0/17/24」と「202.33.10.0/24」の二つのエントリを含む経路情報パケットがルータＲ3に送信される。 (c)同様な手段でルータＲ2はルータＲ1へ経路情報を定期的に送信する。
【００７７】
(3) ルータＲ3における経路情報の受信
ルータＲ2における手順と同様にルータＲ2とルータＲ4から経路情報を受信し、経路テーブルの作成を行う。
(4) ルータＲ3における経路情報の送信
(a)ルータＲ3の経路情報送信手段５のタイマ部５１がルータＲ4への経路情報の送信を送信経路情報作成部５３に指示する。
【００７８】
(b)ルータＲ3の経路テーブルのうちルータＲ4以外からの経路情報で作成されたエントリとルータＲ2とルータＲ3が共有しない網ＮＷ112(133.160.55.0)、すなわち「133.160.10.0/17/24」,「133.160.55.0/17/24」,「202.33.10.0/24」の三つのエントリがルータＲ4に送信される経路情報の対象となる。
【００７９】
しかしながら、送信経路情報作成部５３は階層指示部５２からの通知で予めルータＲ3は自身が「133.160.0.0/9/16」と「133.30.0.0/9/16」の境界ルータ、すなわち「/9/16」階層の境界ルータであることを知っているため、「133.160.10.0/17/24」及び「133.160.55.0/17/24」は「133.160.0.0/9/16」にまとめられる。
【００８０】
すなわち、経路情報における階層化の変更が送信経路情報作成部５３で行われ、「133.160.0.0/9/16」と「202.33.10.0/24」の2 エントリを含む経路情報がルータＲ4に送信される。
(c)ルータＲ3からルータＲ2への経路情報の送信も前項と同様であり、「133.30.22.0/17/24」を「133.30.0.0/9/16」として、ルータＲ4経由のエントリ(145.0.0.0/1/8と202.33.95.0/24) と併せて送信する。
【００８１】
(5) ルータＲ4における経路情報の受信
ルータＲ2における手順と同様にルータＲ3とルータＲ5から経路情報を受信し、経路テーブルの作成を行う。
【００８２】
(6) ルータＲ4における経路情報の送信
(a)ルータＲ3と同様の手順で経路情報を送信する。なおルータＲ4は「/1/8」階層の境界ルータであるため、非階層化網へのエントリに加えて、「145.0.0.0/1/8」をルータＲ3に、「133.0.0.0/1/8」をルータＲ5に経路情報として送信する。
【００８３】
２．パケットの中継動作
2.1階層化網へのパケット中継
図８のように経路情報の交換が行われた交換網において、階層化網へのパケット送信の例、すなわちルータＲ1からホストH1(145.66.89.5) へパケットP1が送信/ 中継される様子を図９に示す。なお、以下の説明ではルータＲ１からホストＨ１への送信を例示しているが、送信は任意のホスト又はルータから可能であり、同様に受信も任意のホスト又はルータで可能である。
【００８４】
(1) ルータＲ1のパケット送信
(a)上位層からの指示によりルータＲ1のパケット作成手段３のパケット作成部３１がH1宛のパケットP1を作成し、経路検索部３２に「145.66.89.5」を対象とした経路検索を行うよう指示する。
【００８５】
(b)経路検索部３２はまず階層化網用テーブル部２２を検索し、「145/1/8」に合致したことから次の中継ルータがルータＲ2であること、階層が「/1/8」であることをパケット作成部３１に通知する。
(c)パケット作成部３１は経路検索部３２からの応答に基づいて、パケットP1の送信先アドレスに階層化拡張子「/1/8」を付与し、パケットP1をルータＲ2に送信する。
【００８６】
(2) ルータＲ2の中継
(a)ルータＲ2の中継ルータＲ2の中継パケット処理手段６はパケット送受信手段１経由でパケットP1を受信し、パケットP1に階層化拡張子が付与されていることから、階層化網宛パケット選択部６１は階層化網宛のパケットであると判断し、パケットP1は階層化網宛パケット用経路制御部６４に渡される。
【００８７】
(b)階層化網宛パケット用経路制御部６４は階層化拡張子が示す階層の送信先アドレスの値「145」がルータＲ2自身の同階層のアドレスの値「133 」と異なるため、特定階層経路テーブル検索部６５に「145/1/8」の経路検索を指示する。
【００８８】
(c)特定階層経路テーブル検索部６５は経路テーブル保持手段２の階層網用テーブル部２２に対して、「145/1/8」を対象に経路検索を行い、次の中継ルータがルータＲ3であることを階層化網宛パケット用経路制御部６４に通知する。
(d)階層化網宛パケット用経路制御部６４はパケット送受信手段１経由でルータＲ3にパケットP1を送信する。
【００８９】
(3) ルータＲ3の中継
ルータＲ2での中継処理と同様の処理によりパケットP1はルータＲ4に送信される。
(4) ルータＲ4の中継
(a)ルータＲ4の中継パケット処理手段６はパケット送受信手段１経由でパケットP1を受信し、パケットP1に階層化拡張子が付与されていることから、階層化網宛パケット選択部６１は階層化網宛パケットであると判断し、パケットP1は階層化網宛パケット用経路制御部６４に渡される。
【００９０】
(b)階層化網宛パケット用経路制御部６４は階層化拡張子が示す階層の送信先アドレスの値「145」がルータＲ2自身の同階層のアドレスの値「145」が同一のため、不特定階層経路テーブル検索部６６に「145」以下の全てのアドレス「66.89.5/9/32」を対象にした経路検索を指示する。
【００９１】
(c)不特定階層経路テーブル検索部６６は経路テーブル保持手段２の階層化網用テーブル部２２に対して、「66.89.5/9/32」を対象に経路検索を行い、「66/9/16」のエントリにヒットしたことから次の中継ルータがルータＲ5であること、階層が「/9/16」であることを階層化網宛パケット用経路制御部６４に通知する。
【００９２】
(d)階層化網宛パケット用経路制御部６４はパケットP1に付与されていた階層化拡張子を「/9/16」に付け換え、ルータＲ5にパケット送受信手段１経由でパケットP1を送信する。
(5) ルータＲ5の中継
ルータＲ2での中継処理と同様の処理によりパケットP1はルータＲ6に送信される。
(6) ルータＲ6の中継
(a)ルータＲ6の中継パケット処理手段６はパケット送受信手段１経由でパケットP1を受信し、パケットP1に階層化拡張子が付与されていることから、階層化網宛パケット選択部６１は階層化網宛パケットであると判断し、パケットP1は階層化網宛パケット用経路制御部６４に渡される。
【００９３】
(b)階層化網宛パケット用経路制御部６４は階層化拡張子が示す階層の送信先アドレスの値「66」がルータＲ6自身の同階層のアドレスの値「66」と同一であり、さらに「66」より下位ビットのネットワーク部もルータＲ6自身が所属する網ＮＷ221(145.66.89.0/17/24) と合致するため、送信先ホストは同一網内にあると判断し、同一網内パケット転送部６７に渡される。
【００９４】
(c)同一網内パケット転送部６７はARP(Address Resolution Protocol)等の既存の同一網内送信手段を用いてパケットP1をホストH1に配送する。
【００９５】
2.2非階層化網へのパケット中継
図８に示すように経路情報の交換が行われた網において、非階層化網へのパケット送信の例をやはり図９に示す。本例ではルータＲ1からホストH2(202.33.95.4) へパケットP2が送信、中継されている。非階層化網宛のパケットには、全中継処理を通じて階層化拡張子は付与されず、各ルータは中継パケット処理手段６内の非階層化網宛経路テーブル検索部６３により従来手法を用いた経路検索を行う。
なおここではルータからホストへの送信を例示しているが、送信は任意のホスト、ルータから可能であり、同様に受信も任意のホスト、ルータで可能である。
【００９６】
【発明の効果】
以上、述べたように本発明に係る網の経路制御方法及び装置によれば、各ルータが、該ルータを境界としている階層化網の内の最上位の階層化網の階層情報を階層化拡張子として経路情報に含めて交換するとともに、送信元ホストがパケットの送信先ホストのＩＰアドレスに該階層情報を付与して送信し、中継するルータが該階層情報に基づいて該経路検索を行うように構成したので、ＩＰ網において下記の効果が得られる。
【００９７】
▲１▼各ルータが経路検索に用いる階層情報を階層化拡張子としてパケットに付与し、各ルータにおいて階層を絞った経路検索を可能とする。
▲２▼階層化拡張子による経路情報の交換をルータ間で行うことで階層を特定した経路検索用テーブルの作成を可能とする。
【図面の簡単な説明】
【図１】本発明に係る網の経路制御方法及び装置の基本原理を示すブロック図である。
【図２】本発明に係る網の経路制御方法及び装置に使用されるルータを構成するパケット送受信手段の構成例を示すブロック図である。
【図３】本発明に係る網の経路制御方法及び装置に使用されるルータを構成する経路テーブル保持手段の構成例を示すブロック図である。
【図４】本発明に係る網の経路制御方法及び装置に使用されるルータを構成するパケット作成手段の構成例を示すブロック図である。
【図５】本発明に係る網の経路制御方法及び装置に使用されるルータを構成する経路情報受信手段の構成例を示すブロック図である。
【図６】本発明に係る網の経路制御方法及び装置に使用されるルータを構成する経路情報送信手段の構成例を示すブロック図である。
【図７】本発明に係る網の経路制御方法及び装置に使用されるルータを構成する中継パケット処理手段の構成例を示すブロック図である。
【図８】本発明に係る網の経路制御方法及び装置を使用した経路情報交換の実施例を示した図である。
【図９】本発明に係る網の経路制御方法及び装置を使用したパケット中継の実施例を示した図である。
【図１０】従来より知られたＩＰv4のアドレス構造を示した図である。
【図１１】従来より知られた非階層的なＩＰ網構成例を示した概念図である。
【図１２】従来より知られた経路交換例を示した概念図である。
【図１３】従来より知られたパケット転送例を示した概念図である。
【符号の説明】
ＮＷ10〜12，111,112,121,20〜22,211,212,213  網（ネットワーク）
Ｒ1〜Ｒ7  ルータ
ＨA,ＨB ホスト
１  パケット送受信手段
２  経路テーブル保持手段
３  パケット作成手段
４  経路情報受信手段
５  経路情報送信手段
６  中継パケット処理手段
図中、同一符号は同一又は相当部分を示す。
【図１】
0003973298.tif 000002
【図２】
0003973298.tif 000003
【図３】
0003973298.tif 000004
【図４】
0003973298.tif 000005
【図５】
0003973298.tif 000006
【図６】
0003973298.tif 000007
【図７】
0003973298.tif 000008
【図８】
0003973298.tif 000009
【図９】
0003973298.tif 000010
【図１０】
0003973298.tif 000011
【図１１】
0003973298.tif 000012
【図１２】
0003973298.tif 000013
【図１３】
0003973298.tif 000014