ネットワークシステム、ノード、パケット転送方法およびそのプログラム
【課題】オーバーレイツリートポロジにおいて確保すべきアドレス数を低減し、新規ノードが論理ネットワークに参加する際の制限を緩和する。
【解決手段】サービスごとの論理ネットワークをツリートポロジで構成し、その論理ネットワークを１以上のサブツリーからなるエリアに分割する。そして、そのエリア内のノードへのアドレッシングは、エリア内ごとに設定された最大階層数Ｌｍと、そのエリアの階層ｄごとに設定された最大子ノード数Ｒｍｄとを用いて行う。また、そのエリア同士もツリー構造で構成し、各エリアのエリア番号は、最大エリア階層数Ａａｒｅａ＿Ｌｍと、エリア階層Ａａｒｅａ＿ｄごとに設定された最大子エリア数Ａａｒｅａ＿Ｒｍｄを用いてアドレッシングを行う。
【解決手段】サービスごとの論理ネットワークをツリートポロジで構成し、その論理ネットワークを１以上のサブツリーからなるエリアに分割する。そして、そのエリア内のノードへのアドレッシングは、エリア内ごとに設定された最大階層数Ｌｍと、そのエリアの階層ｄごとに設定された最大子ノード数Ｒｍｄとを用いて行う。また、そのエリア同士もツリー構造で構成し、各エリアのエリア番号は、最大エリア階層数Ａａｒｅａ＿Ｌｍと、エリア階層Ａａｒｅａ＿ｄごとに設定された最大子エリア数Ａａｒｅａ＿Ｒｍｄを用いてアドレッシングを行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークアーキテクチャに関する技術である。
【背景技術】
【０００２】
従来、ネットワークにより提供されるサービス単位でトポロジを構成するネットワーク構成方法がある（非特許文献１参照）。この方法では、トポロジをツリー構造で構築し、予め定められたツリーの階層数と、そのツリーにおける親ノード１つあたりの子ノード数をもとに、このトポロジ内の各ノードにアドレス番号を付与する。この方法によれば、各ノード（例えば、ルータ）は、受信したパケットのアドレス番号の大小をもとに、そのパケットを親ノード側に転送すればよいか、子ノード側に転送すればよいかを判断し、また子ノード側に転送する場合、どの子ノードに転送すればよいをかを判断できる。つまり、各ノードの宛先のエントリ数をできるだけ少なくできるので、ノードの持つべきルーチングテーブルの情報量を削減し、ルーチング処理の負荷を軽減できる。なお、このように、サービス単位で別個のネットワークトポロジをツリー構造で構築したものをオーバーレイツリートポロジと呼ぶ。
【０００３】
ここで、図１２を用いて、前記した方法による、オーバーレイツリートポロジの詳細を説明する。オーバーレイツリーポロジは、例えば、大きく２種類のパラメータでツリーの形状を決定する。１つは、ツリーの最大ツリー階層数Ｌｍであり、もう１つは、ｄ階層の１ルータ（１ノード）当たりの子ノード数Ｒｍｄである。これらの値から、ｄ＋１階層のルータ（ノード）以下の総ルータ数Ｃｓｋｉｐ（ｄ）を算出し、各ノードのアドレッシング（アドレス番号の付与）を行う。なお、Ｃｓｋｉｐ（ｄ）の値は、図１２の吹き出し部分に示される式により計算される。
【０００４】
このオーバーレイツリーポロジ上に配置される各ノードは、図１２に示すようなルーチングテーブルを保持する。このルーチングテーブルには、自身のアドレス（My addr)や自身の階層数(My Depth)等の所属情報、ツリーのルートノードのアドレス（root addr)や、ツリーの階層数（Ｌｍ）、階層毎の子ノード数Ｒｍｄ等の構成情報、自身のノードの親ノード（Parent addr)や子ノード（Child addr)等の隣接ノードの情報を示す隣接エントリ情報を含む。そして、ノードは、このルーチングテーブルと、Ｃｓｋｉｐ（ｄ）の値とから、パケットの宛先アドレスが自身の親ノード側に存在するか、子ノード側に存在するかを判断し、ネクストホップ（次にパケットを転送すべきノード）を決定することが可能となる。つまり、ノードは、宛先アドレスに対するエントリ数を保持せずとも、宛先アドレスでネクストホップを決定できる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】磯貝彰則、小島久史、 井上一郎、塩本公平、” 多数サービスをスケーラブルに収容するネットワーク仮想化技術に関する検討”2008年 ソサイエティ大会
【発明の概要】
【発明が解決しようとする課題】
【０００６】
このようなオーバーレイツリートポロジにおいて、特定のサブツリー以下に多数のノードが存在する場合、事前に確保が必要なアドレス数が増大する。つまり、非特許文献１に記載の技術において、各ノードのアドレスは、そのツリーの最も深い階層までの階層数と、１つのノードの子ノード数の最大値を見越して決める必要がある。よって、例えば、図１３に示すように、サブツリーごとに階層の深さの偏りがある場合でも、ツリーのアドレスは階層数と子ノード数を基準に決定する必要がある。つまり、ノードの存在の有無に関わらず、アドレスの確保は必要なので、実際には使用されないアドレス空間（未使用のアドレス空間）が大量に発生する。図１３に示した例でいうと、６〜１００１、１００４〜２００１、２００５〜３００１等のアドレスが未使用アドレスとなる。
【０００７】
このような未使用アドレスが大量に発生するという現象は、同じ階層におけるノード間での子ノード数の数に偏りがある場合にも、発生しうる。このようにネットワークのノードに対し、未使用アドレスが大量に発生するようなアドレッシングを行うと、極めて大きな値（大きな桁数）のアドレスを持つノードが現れる可能性が高くなる。よって、各ノードは、ルーチング処理時に、このように極めて大きな値（大きな桁数）のアドレスを処理する可能性も高くなり、ルーチング処理の負荷が高くなるという問題がある。
【０００８】
さらに、前記したサービスにおけるノードの追加や削除、トラヒック量の増減が発生すると、オーバーレイツリートポロジへの新たなノードの参加および既存のノードの離脱等も必要となる。ここで、オーバーレイツリートポロジへの新たなノードを接続する場合、ノードの数が集中しているサブツリー周辺では最大ツリー階層数Ｌｍや最大子ノード数Ｒｍｄによる制限があるため、所望する位置に接続できないという問題がある。
【０００９】
例えば、図１４に示すように、オーバーレイツリートポロジにおいて、最大ツリー階層数Ｌｍ＝５、最大子ノード数Ｒｍ５＝３という制限がある場合を考える。つまり、子ノード数は３台までという制限がある場合を考える。この場合、新規参加ノードは、この階層Ｌｍ＝５のノードＡ，Ｂのいずれかのノードの子ノードとして接続したくても、これらのノードには、既に３台の子ノードが接続されているので、ノードＡ，Ｂの子ノードとして接続できない。従って、この場合、新規参加ノードは、別の階層のノードの子ノードとして接続しなければならない等、必ずしも最適な位置（または、ネットワークの管理者が所望する位置）に接続できないことがある。
【００１０】
本発明は、前記課題を解決し、オーバーレイツリートポロジにおいて確保すべきアドレス数を低減し、新規ノードが論理ネットワークに参加する場合の制限を緩和することを目的とする。
【課題を解決するための手段】
【００１１】
前記した課題を解決するため、本発明は、１以上のサービスのパケットを転送するネットワークシステムを、当該サービスのパケットを転送する１以上の論理ネットワークに分け、その論理ネットワークをツリー型トポロジとして構成し、当該論理ネットワークを１以上のサブツリーからなるエリアに分割する場合において、そのエリアにおけるツリーの最大ツリー階層数Ｌｍと、そのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数Ｒｍｄとをもとに、そのエリア内のツリーにおける第ｄ＋１階層におけるｎ番目に参加する子ノードの当該エリア内におけるアドレスＡｎが、以下の式（１）により定義されるノードを備えるネットワークシステムであって、
Ａｎ＝Ａｐａｒｅｎｔ＋Ｃｓｋｉｐ（ｄ）×（ｎ−１）＋１…式（１）
但し、
ｄ＝Ｌｍの場合
Ｃｓｋｉｐ（ｄ）＝０
０≦ｄ≦Ｌｍ−１の場合
Ｃｓｋｉｐ（ｄ）＝（Ｃｓｋｉｐ（ｄ＋１）×Ｒｍｄ＋１）＋１
Ａｐａｒｅｎｔ：当該エリアのツリーにおける自身のノードの親ノードのアドレス
Ｃｓｋｉｐ（ｄ）：当該エリアのツリーの第ｄ＋１階層の１つのノード以下に存在するノード数
ｄ：当該エリアのツリーにおける自身のノードの属する階層
Ｌｍ：当該エリアのツリーの最大ツリー階層数
Ｒｍｄ：当該エリアのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数
当該論理ネットワークにおいて、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍと、その論理ネットワークの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄとをもとに、その論理ネットワークにおける第Ａａｒｅａ＿ｄ＋１階層におけるｍ番目に参加するエリアのエリア番号Ａａｒｅａが、以下の式（２）により定義されることを特徴とするネットワークシステムとした。
Ａａｒｅａ＝Ａａｒｅａ＿ｐａｒｅｎｔ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）×（ｍ−１）＋１…式（２）
但し、
Ａａｒｅａ＿ｄ＝Ａａｒｅａ＿Ｌｍの場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝０
Ａａｒｅａ＿ｄ≦Ａａｒｅａ＿Ｌｍ−１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ＋１）×Ａａｒｅａ＿Ｒｍｄ＋１）＋１
Ａａｒｅａ＿ｐａｒｅｎｔ：当該論理ネットワークにおける当該エリアの親エリアのアドレス
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）：当該論理ネットワークの第Ａａｒｅａ＿ｄ＋１階層の１つのエリア以下に存在する子エリア数
Ａａｒｅａ＿ｄ：当該論理ネットワークにおける自エリアの属する階層
Ａａｒｅａ＿Ｌｍ：当該論理ネットワークの最大エリア階層数
Ａａｒｅａ＿Ｒｍｄ：当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数
【００１２】
また、このネットワークシステムにおけるノードは、（１）論理ネットワークそれぞれに割り当てられたアドレス空間を示した論理ネットワーク情報と、（２）論理ネットワークにおいて自身のノードの属するエリアのエリア番号Ａａｒｅａと、当該論理ネットワークにおいて当該エリアの属する階層Ａａｒｅａ＿ｄと、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍおよび１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄと、当該エリアの親エリアＡａｒｅａ＿ｐａｒｅｎｔおよび子エリアＡａｒｅａ＿ｃｈｉｌｄとを示したエリア構造テーブルと、（３）当該エリアに隣接する隣接エリアごとに、その隣接エリアへ接続するエリア境界ノードを示したエリア境界ノード情報テーブルと、（４）当該エリアにおける自身のノードのアドレスＡ、自身のノードの属する階層ｄ、最大ツリー階層数Ｌｍおよび最大子ノード数Ｒｍｄ、自身のノードの親ノードのアドレスＡｐａｒｅｎｔおよび子ノードのＡｃｈｉｌｄとを示したエリア内テーブルとを記憶する記憶部と、当該パケットの宛先ノードの属するエリア番号を含むアドレスが付されたパケットの入出力を司るネットワークインタフェース部と、論理ネットワーク情報と、ネットワークインタフェース部経由で入力されたパケットの宛先アドレスに含まれる宛先ノードの属するエリアのエリア番号を参照して、宛先ノードが自身のノードの属するエリアのノードか否かを判断するエリア判定部と、（Ａ）宛先ノードが、自身のノードの属するエリアのノードであったとき、エリア内テーブルと自身のノードのアドレスＡと、アドレスに含まれるエリア内でのアドレスＤとを参照して、その宛先ノードに転送する際のネクストホップノードのアドレスＮｅｘｔｈｏｐ ａｄｄｒを、以下の式（３）または式（４）により決定するネクストホップ決定部と、
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）の場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａ＋１＋Ｆｌｏｏｒ［（Ｄ−（Ａ＋１））／Ｃｓｋｉｐ（ｄ）］×Ｃｓｋｉｐ（ｄ）…式（３）
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）ではない場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａｐａｒｅｎｔ…式（４）
決定されたアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ入力されたパケットをネットワークインタフェース部経由で転送するパケット転送部と、
（Ｂ）宛先ノードが、自身のノードの属するエリアのノードではなかったとき、その宛先ノードに転送する際のネクストエリアを、エリア構造テーブルを参照して、以下の式（５）または式（６）により決定するネクストエリア決定部と、
Ａａｒｅａ＜宛先エリアのエリア番号＜Ａａｒｅａ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の場合、ネクストエリア＝Ａａｒｅａ＋１＋Ｆｌｏｏｒ［（エリア番号−（Ａａｒｅａ＋１））／Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）］×Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）…式（５）
Ａａｒｅａ＿ｄ＜宛先エリアのエリア番号＜Ａａｒｅａ＿ｄ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）ではない場合、ネクストホップエリア＝Ａａｒｅａ＿ｐａｒｅｎｔ…式（６）
エリア構造テーブルを参照して、決定したネクストエリアへ接続するエリア境界ノードのアドレスを特定するエリア境界ノード特定部とを備え、ネクストホップ決定部は、特定したエリア境界ノードのアドレスを宛先アドレスとしたときのネクストホップへのアドレスＮｅｘｔｈｏｐ ａｄｄｒを決定し、パケット転送部は、決定したアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ、入力されたパケットを転送することを特徴とする。
【００１３】
このようにすることで、ネットワークの各ノードは、サービスごとに用意された論理ネットワークに基づきパケットを転送する。また、この論理ネットワークにおいて、従来、論理ネットワーク全体を１つのツリートポロジとしていたが、その論理ネットワークを１以上のサブツリーからなる複数のエリアに分割する。つまり、論理ネットワークを分割したエリア同士の接続関係がツリー構造になり、かつ、エリア内のノード間の接続関係もツリー構造になる。これにより、ツリーの最大ツリー階層数Ｌｍおよびツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数Ｒｍｄを、エリアごとに設定可能になる。よって、オーバーレイツリートポロジに新規ノードが参加するときの制限を緩和することができ、新規ノードを最適な位置に接続しやすくなる。また、オーバーレイツリートポロジのサブツリー間で階層数やノード数の偏りがあった場合でも、エリアごとにツリーの構造を変化させて対応できるので、事前に確保が必要なアドレス数を削減できる。
【００１４】
また、各エリア内のノードのアドレスは、ルートノードから、子ノード、孫ノードに行くに従い大きな値をとるように割り当てられる。つまり、パケットを受信したノードは、宛先アドレスと自身のノードのアドレスとを比較することで、ツリー型トポロジにおいてその宛先アドレスのノードが、自身のノードからみてルート方向（親ノードの方向）にあるのか、リーフ方向（子ノードの方向）にあるのかが分かる。従って、まず、パケットを受信したノードは、パケットの宛先アドレスと自身のアドレスとの比較により、ネクストホップノード（このパケットを転送先となるノード）は、ルート方向のノードか、リーフ方向のノードかを判断できる。ここで、ネクストホップノードがリーフの方向のノードであると判断した場合、自身のノードにリーフ方向のノード（子ノード）が複数ある場合もある。この場合、このノードの子ノードの１つは、この自身のノードのアドレスに１を足した値であり、他の子ノードのアドレスは、このアドレスにＣｓｋｉｐ（ｄ）で計算される値が加算された値が割り当てられる（例えば、あるノードのｎ番目の子ノードのアドレスは、このアドレスにＣｓｋｉｐ（ｄ）×ｎが加算された値となる）ので、ノードは、フロア関数によりＦｌｏｏｒ［（Ｄ−（Ａ＋１））／Ｃｓｋｉｐ（ｄ）］を計算して、パケットの宛先アドレスにつながるノードは、このノードの第何番目の子ノードかを特定できる。そして、ノードは、その特定した子ノードへパケット転送する。各ノードがこのような転送処理を行うことで、パケットはエリア内のツリー型トポロジのノード間を転送され、所定の宛先アドレスのノードに到達することができる。
【００１５】
なお、このような各ノードへのアドレス割り当てに用いられるＣｓｋｉｐ（ｄ）は、０≦ｄ≦Ｌｍ−１の場合、Ｃｓｋｉｐ（ｄ）＝（Ｃｓｋｉｐ（ｄ＋１）×Ｒｍｄ＋１）＋１という式に基づき計算される。これより、エリア内のツリー型トポロジの階層ごとに最大子ノード数が異なる場合、その階層ごとの最大子ノード数Ｒｍｄを考慮して、無駄のないアドレスの割り当てを実現している。つまり、エリア内のツリー型トポロジの階層ごとに最大子ノード数が異なる場合に、その階層ごとの最大子ノード数Ｒｍｄを考慮し、実際には割り当てられないことが明らかなアドレスについては、これを省いてアドレスが割り当てられている。これにより、エリア内で事前に確保が必要なアドレス数を低減できる。
【００１６】
また、この論理ネットワークにおける各エリアのエリア番号についても、前記したノードのアドレスと同様に、ルートエリアから、子エリア、孫エリアに行くに従い大きな値をとるように割り当てられる。つまり、パケットを受信したノードは、宛先エリアのエリア番号と自エリアのエリア番号とを比較することで、ツリー型トポロジにおいてその宛先エリアに到達するためのネクストエリアへは、自エリアからみてルート方向（親ノードの方向）にあるのか、リーフ方向（子ノードの方向）にあるのかが分かる。このような転送処理を各エリアのノードが行うことで、パケットはツリー型トポロジのエリア間を転送され、所定のエリアのノードに到達することができる。なお、各ノードは、自エリアに隣接するエリアごとに、そのエリアへ接続するためのエリア境界ノードのアドレスを示したエリア境界ノード情報を記憶する。これにより各ノードは、このネクストエリアにパケットを到達させるためには、自エリア内のどのノード目指してパケットを転送すればよいかが分かる。つまり、ネクストホップ決定部が、この特定したエリア境界ノードのアドレスを宛先アドレスとしたときのネクストホップを求めることで、このネクストエリアにパケットを到達させるためのネクストホップが分かる。
【００１７】
なお、このツリー型トポロジのエリアで、各階層ごとに最大子エリア数が異なる場合、その階層ごとの最大子エリア数Ａａｒｅａ＿Ｒｍｄを考慮し、実際には割り当てられないことが明らかなエリア番号については、これを省いてアドレスが割り当てられる。これにより、論理ネットワーク内で事前に確保が必要なエリア番号の数も低減できる。
【００１８】
また、本発明は、エリア内のツリーのすべての階層で当該階層の子ノード数Ｒｍが等しいとき、式（１）におけるＣｓｋｉｐ（ｄ）は、
Ｒｍ＝１の場合
Ｃｓｋｉｐ（ｄ）＝Ｌｍ−ｄ
Ｒｍ＝１ではない場合
Ｃｓｋｉｐ（ｄ）＝（１−ＲｍＬｍ−ｄ）／（１−Ｒｍ）
とする。
【００１９】
このようにすることで、オーバーレイツリートポロジにおいて、各階層の子ノード数が同じ場合、Ｃｓｋｉｐ（ｄ）の計算を簡単に行うことができる。
【００２０】
また、本発明は、論理ネットワーク内のすべてのエリアの階層で当該階層の子エリア数Ａａｒｅａ＿Ｒｍが等しいとき、
式（１）におけるＣｓｋｉｐ（Ａａｒｅａ＿ｄ）は、
Ａａｒｅａ＿Ｒｍ＝１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝Ｌｍ−ｄ
Ａａｒｅａ＿Ｒｍ＝１ではない場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（１−Ａａｒｅａ＿ｄＡａｒｅａ＿Ｌｍ−Ａａｒｅａ＿ｄ）／（１−Ａａｒｅａ＿Ｒｍ）
とする。
【００２１】
このようにすることで、オーバーレイツリートポロジの各階層の子エリア数が同じ場合、Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）の計算を簡単に行うことができる。
【００２２】
また、本発明は、請求項５に記載のパケット転送方法を、ネットワークシステム内のノードであるコンピュータに実行させるためのプログラムとした。
【００２３】
このようなプログラムによれば、一般的なコンピュータに、請求項５に記載のパケット転送方法を実行させることができる。
【発明の効果】
【００２４】
本発明によれば、オーバーレイツリートポロジにおいて確保すべきアドレス数を低減し、新規ノードがオーバーレイツリートポロジに参加する場合の制限を緩和できる。
【図面の簡単な説明】
【００２５】
【図１】本実施の形態のノードを含むシステムを例示した図である。
【図２】本実施の形態の論理ネットワークを例示した図である。
【図３】本実施の形態のノードの構成を示すブロック図である。
【図４】本実施の形態のＣｓｋｉｐ（ｄ）の計算式を示した図である。
【図５】図４に示す計算式により求められたＣｓｋｉｐ（ｄ）によりアドレッシングされたツリー型トポロジを例示した図である。
【図６】図３のルーチングテーブルを例示した図である。
【図７】図６のルーチングテーブルの示すエリア構成を例示した図である。
【図８】図３のノードのパケット転送処理手順を示したフローチャートである。
【図９】図３のネクストホップ決定処理の詳細を示したフローチャートである。
【図１０】図３のネクストエリア決定処理の詳細を示したフローチャートである。
【図１１】本実施の形態のＣｓｋｉｐ（Ａａｒｅａ＿ｄ）の計算式を示した図である。
【図１２】比較例のオーバーレイツリートポロジを示した図である。
【図１３】比較例のオーバーレイツリートポロジを示した図である。
【図１４】比較例のオーバーレイツリートポロジを示した図である。
【発明を実施するための形態】
【００２６】
以下、本発明を実施するための形態（以下、実施の形態とする）について説明する。
【００２７】
＜概要＞
以下、本発明を実施するための最良の形態（以下、実施の形態という）について説明する。まず、本実施の形態のノードを含むネットワークシステムの概要を、図１を用いて説明する。ネットワークシステムは、例えば、図１に示すように、バックボーンネットワーク１と、そのバックボーンネットワーク１により接続されるサービスネットワーク２，３を含んで構成される。
【００２８】
バックボーンネットワーク１は、複数のノード１０を含んで構成される。なお、このバックボーンネットワーク１のノード１０は、サービスネットワーク２，３との境目に設置される境界ノードと、その境界ノード間を接続する中継ノードとを含んで構成される。各ノード１０は、例えば、ルータやスイッチである。サービスネットワーク２，３にはサービスを提供するサーバ２１と、そのサーバから提供されるサービスを利用するクライアント３１とを含む。ここでは、サービスネットワーク２は、サービスＡを提供するサーバ２１Ａと、サービスＢを提供するサーバ２１Ｂとを含み、サービスネットワーク３は、サービスＡを利用する（つまり、サーバ２１Ａとデータ送受信を行う）クライアント３１Ａと、サービスＢを利用する（つまり、サーバ２１Ｂとデータ送受信を行う）クライアント３１Ｂとを含む。つまり、境界ノードであるノード１０（１０Ａ，１０Ｂ）間にはサービスＡ，Ｂ両方のトラヒックが流れることになる。
【００２９】
ここで、このバックボーンネットワーク１内において、サービスＡのルーチング経路と、サービスＢのルーチング経路とを分けるために、サービスごとに論理ネットワークを用意する。例えば、図１に示すように、サービスＡについて論理ネットワークＡという論理ネットワークを用意し、サービスＢについては論理ネットワークＢという論理ネットワークを用意する。そして、各論理ネットワークを構成するノードにアドレッシング（アドレスの割り当て）を行う。このときのアドレッシングは以下のように行う。まず、各サービスの論理ネットワークが利用するアドレス空間を、論理ネットワークごとに重複しないように割り当てる。例えば、サービスＡについて割り当てアドレス空間「０１０１〜０９０９」を割り当てたならば、サービスＢについて割り当てアドレス空間について「１００１０〜１９０９」を割り当てる。
【００３０】
この割り当てアドレス空間の大きさや、各ノードのアドレスの割り当て方法は、各論理ネットワークに含まれるノード１０の数やトポロジの構成方法による。このようにサービスごとに重複のないアドレス空間の割り当てを行うことで、当該アドレスのノード１０がどのサービスの論理ネットワークに属するかを識別することができる。ここで、サービスごとに用意される論理ネットワークは、例えば、ツリー型トポロジで構成され、各ノード１０はルーチングテーブル１３１（後記）を参照し、このツリー型トポロジを前提としたルーチングを行う。よって、ノード１０は、ルーチングテーブル１３１にパケットの宛先アドレスごとのエントリを用意する必要がなくなる。
【００３１】
次に、図２を用いて、前記した論理ネットワークの構成例を説明する。論理ネットワークＮは、図２に例示するように複数のエリア（エリア１〜７）から構成される。このエリアはそれぞれ、オーバーレイツリートポロジの一部のツリー（サブツリー）を含む。また、この論理ネットワークＮにおける、エリア自体のトポロジもツリー構造とする。つまり、エリア同士はツリー状に接続される。
【００３２】
このエリアの構造は、
Ａａｒｅａ＿Ｌｍ：当該論理ネットワークの最大エリア階層数
Ａａｒｅａ＿Ｒｍｄ：当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数
により定義される。
【００３３】
例えば、論理ネットワークＮは、エリア階層Ａａｒｅａ＿Ｌｍ＝２であり、０階層目の子エリア数Ａａｒｅａ＿Ｒｍ０＝２、１階層目の子エリア数Ａａｒｅａ＿Ｒｍ１＝２である場合、図２に示すようなエリア構造となる。このエリアの構造に関する定義情報は、ノード内のエリア構造テーブル１３３（後記）に記憶される。各エリアのエリア番号は、Ａａｒｅａ＿ＬｍおよびＡａｒｅａ＿Ｒｍｄをもとに決定される（詳細は後記）。
【００３４】
このエリア内のノード１０の構造は、
Ｌｍ：当該エリアのノードの最大ツリー階層数
Ｒｍｄ：当該エリアの第ｄ階層の１つのノードが保持可能な最大子エリア数
により定義される。
【００３５】
例えば、エリア内階層Ｌｍ＝１であり、このエリアの０階層目の子ノード数Ｒｍ０＝３である場合、図２のエリア２のような構造となる。このエリア内の構造に関する定義情報は、ノード内のエリア内テーブル１３２（後記）に記憶される。各エリア内におけるノード１０のアドレスは、このＬｍ、Ｒｍｄをもとに決定される（詳細は後記）。
【００３６】
なお、このエリア同士は、エリア境界ノードにより接続される。このエリア境界ノードには、そのエリア境界ノードの属するエリアごとに、そのエリアの構造から決定されたアドレスが付与される。そして、論理ネットワークの各ノードは、自エリアに隣接する外部エリアと、その外部エリアに接続するためのエリア境界ノードとの情報（外部エリア情報）をエリア境界ノード情報テーブル１３４（後記）に記憶する。例えば、図２のエリア６のノード「９９９」は、外部エリア情報として、隣接エリアがエリア５であり、このエリア５へ接続する自エリアのエリア境界ノードは「１」であるという情報を記憶する。
【００３７】
なお、論理ネットワークの各ノード１０のアドレスは、エリアのエリア番号と当該エリア内における自身のノードのアドレスとの組み合わせにより記述される。例えば、エリア４のノード「３」のアドレスは「エリア４，ノード３」というように記述される。ノード間のパケットの転送は、このアドレスをもとに行われる。すなわち、ノード１０はそれぞれ、パケットの宛先アドレスに含まれるエリア番号から、そのパケットが自エリア宛か否かを判断し、自エリア宛であれば、その宛先アドレスに含まれる自エリア内のアドレスを用いてルーティングを行う。一方、他エリア宛であれば、ノード１０は、エリア構造テーブル１３２およびエリア境界ノード情報テーブル１３４を参照して、どのエリアに転送すべきか、また、そのエリアに接続するエリア境界ノードはどれかを特定し、この特定したエリア境界ノードへパケットを転送する。各ノード１０が、このような処理を繰り返すことで、パケットは宛先アドレスに示されるノードに到達する。
【００３８】
なお、各エリア内のアドレスおよび各エリアのエリア番号は、ルート側から、子方向に行くに従い、大きな値をとるように割り当てられる。つまり、パケットを受信したノードは、宛先アドレスのエリア内のアドレスやエリア番号と、自身のノードのエリア内のアドレスやエリア番号とを比較することで、ツリー型トポロジにおいてその宛先が、ルート方向（親方向）にあるのか、リーフ方向（子方向）にあるのかを判断できる。よって、各ノード１０のルーチング処理負荷を軽減できる。
【００３９】
また、このように論理ネットワークを複数のエリアに分割し、そのエリアごとにＬｍ、Ｒｍｄが設定可能となるので、新規ノードが接続するとき、様々な箇所を選択可能となり、確保すべきアドレス数を低減できる。さらに、論理ネットワークのエリア階層（Ａａｒｅａ＿ｄ）ごとに子エリア最大値（Ａａｒｅａ＿Ｒｍ）を設定可能なので、エリアの構造自体も自由度が高いものとなる。
【００４０】
＜構成＞
次に、図３を用いて、このようなバックボーンネットワーク１に用いられるノード１０の構成を説明する。
【００４１】
図３に示すように、ノード１０は、他のノード１０との間でパケットの入出力を行うためのネットワークインタフェース部１１と、ネクストホップの決定等を行う処理部１２と、この処理部１２がネクストホップの決定を行うときに参照するルーチングテーブル１３１を記憶する記憶部１３とを備える。
【００４２】
なお、ネットワークインタフェース部１１は、パケット等の入出力を行うためのインタフェースから構成される。また、処理部１２は、このノード１０が備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部１３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、ノード１０をプログラム実行処理により実現する場合、記憶部１３には、このノード１０の機能を実現するためのプログラムが格納される。
【００４３】
処理部１２は、データ受信部１２０と、トンネル処理部１２１と、エリア判定部１２２と、ネクストエリア決定部１２３と、エリア境界ノード特定部１２４と、ネクストホップ決定部１２５と、パケット転送部１２６と、割り当てアドレス算出部１２７とを含んで構成される。
【００４４】
データ受信部１２０は、ネットワークインタフェース部１１経由で受信したパケットの宛先アドレスを検出し、このパケットが自分宛のものか、それとも中継すべきか否かの判断を行う。なお、この宛先アドレスは、パケットの宛先ノードの属するエリアのエリア番号＋エリア内でのアドレスの組み合わせにより記述される。そして、例えば、ノード１０間で、アドレスのエリア番号を示すカラム（例えばアドレスの前半２桁）と、エリア内でのアドレスを示すカラム（例えばアドレスの後半２桁）とを予め決めておく。そして、ノード１０がパケットの転送を行う際は、それぞれのカラムの値を参照することで、転送先のノード１０を決定する。
【００４５】
トンネル処理部１２１は、他のノード１０との間のトンネルを確立する。また、トンネル確立後、ルーチングテーブル１３１にこの確立したトンネルに関するトンネル情報を書き込む。なお、このように、自身のノードが論理ネットワーク上でネクストホップとしたいノード１０との間でトンネルを確立しておくことで、ノード１０は、物理的にリンク接続された隣接ノード１０を飛び越して、そのトンネルが確立されたノード１０をネクストホップとしてパケットを転送することができる。
【００４６】
エリア判定部１２２は、論理ネットワーク情報１３０（後記）と、受信したパケットの宛先アドレスとを参照して、宛先ノードの属する論理ネットワーク（例えば、図１の論理ネットワークＡ，Ｂ）を特定する。そして、この特定した論理ネットワークに関するエリア構造テーブル１３３と、このパケットの宛先アドレスに含まれるエリア番号とを参照して、パケットの宛先エリアが自ノードのエリアか否かを判断する。
【００４７】
ネクストエリア決定部１２３は、エリア判定部１２２により、パケットの宛先ノードが、自エリアのノードではないと判断されたとき、その宛先ノードに転送する際のネクストエリアを、エリア構造テーブル１３３（後記）を参照して、決定する。このネクストエリアの決定処理の詳細は、後記する。
【００４８】
エリア境界ノード特定部１２４は、ネクストエリア決定部１２３により決定されたネクストエリアへ接続するエリア境界ノードを、エリア境界ノード情報テーブル１３４（後記）を参照して特定する。
【００４９】
ネクストホップ決定部１２５は、受信したパケットの宛先アドレスと、ルーチングテーブル１３１とを参照して、このパケットの転送先のノード１０であるネクストホップノードの決定を行う。このときのネクストホップノードの決定処理の詳細は、具体例を用いて後記する。
【００５０】
パケット転送部１２６は、ネクストホップ決定部１２５により決定されたネクストホップノード、または、エリア境界ノード特定部１２４により特定されたエリア境界ノードへ、パケットを転送する。なお、このパケット転送部１２６は、パケットを転送するとき、ＭＰＬＳ（Multi-Protocol Label Switching）によりパケットを転送してもよい。
【００５１】
割り当てアドレス算出部１２７は、エリア内におけるノード１０のアドレスおよび各エリアのエリア番号を計算する。ノード１０のエリア内のアドレスは、Ｃｓｋｉｐ（ｄ）（第ｄ＋１階層の１つのノード以下に存在するノード数、つまり、第ｄ＋１階層のノードの子ノード同士のアドレスがどの程度離れているかを示す値）を計算することにより求められる。また、エリア番号も同様に、Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）（第ｄ＋１階層の１つのエリア以下に存在するエリア数、つまり、第ｄ＋１階層のエリアの子エリア同士のアドレスがどの程度離れているかを示す値）を計算することにより求められる。この割り当てアドレス算出部１２７により行われる計算処理の詳細は、後記する。
【００５２】
記憶部１３は、論理ネットワーク情報１３０とルーチングテーブル１３１とを記憶する。この論理ネットワーク情報１３０は、論理ネットワークそれぞれに割り当てられたアドレス空間を示す情報である（表１参照）。
【００５３】
【表１】
【００５４】
ルーチングテーブル１３１は、このノード１０が受信したパケットのルーチング（転送先の決定）を行うときに参照される情報である。このルーチングテーブル１３１は、自身のノードの属する論理ネットワークごとに用意され、エリア内テーブル１３２と、エリア構造テーブル１３３と、エリア境界ノード情報テーブル１３４とを備える。また、ここでは図示を省略しているが、ルーチングテーブル１３１は、自身のノードが、当該論理ネットワークの親ノード、子ノードとの間で確立されたトンネルについてのトンネル情報も含むものとする。このトンネル情報は、ノード１０間でトンネルを用いてパケットを転送するときに用いられる情報である。
【００５５】
ここで、図３を参照しつつ、図４および図５を用いて、割り当てアドレス算出部１２７による、各エリア内のノード１０のアドレスの計算方法を説明する。ここでのアドレスの計算方法は、例えば、近距離無線通信に用いられる規格ZigBee（登録商標）（Zigbee Specification Document 053474r17 3.6.1.6章 p370〜372）を応用したものである。
【００５６】
ここでのアドレスの計算には、２種類のパラメータが関与する。１つめのパラメータは、エリア内のトポロジをツリー型トポロジで考えたときの、最大ツリー階層数（ツリーの深さ）Ｌｍである。この最大ツリー階層数Ｌｍは、ツリーのルートの階層を「０（第０階層）」と考え、論理ネットワークごとに最大で何階層のツリー型トポロジを構成するかを定めるパラメータである。２つめのパラメータは、エリア内のツリーの１つのノード１０が持つ最大子ノード数Ｒｍである。この最大子ノード数Ｒｍは、エリア内のツリーの全階層で同じ値をとるパターンと、異なる値をとるパターンの２つのパターンが適用できる（前者の最大子ノード数を、Ｒｍ、後者の第ｄ階層の最大子ノード数を、Ｒｍｄとする）。
【００５７】
割り当てアドレス算出部１２７は、この最大ツリー階層数Ｌｍと、最大子ノード数Ｒｍ（またはＲｍｄ）を用い、図４に示した式（７）または式（８）を用いてエリア内のツリーの第ｄ＋１階層の１つのノード以下に存在するノード数を表すＣｓｋｉｐ（ｄ）を計算する。そして、このＣｓｋｉｐ（ｄ）を、以下の式（９）に代入することで、当該エリア内のツリーの第ｄ＋１階層においてｎ番目に参加するノードのアドレスＡｎを求めることができる。なお、Ａｐａｒｅｎｔは、ｎ番目に参加するノードの親ノードとなるノードのアドレスである。
【００５８】
Ａｎ＝Ａｐａｒｅｎｔ＋Ｃｓｋｉｐ（ｄ）×（ｎ−１）＋１…式（９）
【００５９】
ここで、図５（ａ）を参照して、ツリーの全階層の子ノード数が同じ場合のアドレスの割り当ての具体例を説明する。最大ツリー階層数Ｌｍ＝２、最大子ノード数Ｒｍ＝２のツリーにおいて、図４の式（７）の計算式により、Ｃｓｋｉｐ（０）を計算すると「３」が得られる。この値は、このツリーの第０階層の１つ下の階層（第１階層）の１つのノード以下に存在するノード数（自身のノードを含む）が「３」であることを示す。よって、ルートノードのアドレスを「０」とすると、まず、このルートノードの子ノードとして１番目に参加するノードのアドレスは「０＋１＝１」となる。また、このノード以下に存在するノード数は「３」なので、このルートノードの子ノードとして２番目に参加するノードのアドレスは「１＋３＝４」となる。
【００６０】
同様に、Ｃｓｋｉｐ（１）を計算すると「１」が得られる。よって、アドレス「１」のノードの子ノードとして、１番目に参加するノードのアドレスは「１＋１＝２」となる。また、このノード以下に存在するノード数は「１」（つまり自分自身のみ）なので、２番目に参加するノードのアドレスは「２＋１＝３」となる。また、同様にアドレス「４」のノードの子ノードとして１番目に参加するノードのアドレスは「４＋１＝５」となる。また、このノード以下に存在するノード数は「１」（つまり自分自身のみ）なので、子ノードとして２番目に参加するノードのアドレスは「５＋１＝６」となる。
【００６１】
次に、図５（ｂ）を用いて、ツリーの階層ごとに子ノード数が異なる場合のアドレスの割り当ての具体例を説明する。最大ツリー階層数Ｌｍ＝３、最大子ノード数Ｒｍ０＝３、Ｒｍ１＝２、Ｒｍ２＝３、Ｒｍ３＝０のツリーにおいて、図４の式（８）の計算式により、Ｃｓｋｉｐ（０）を計算すると「９」が得られる。よって、ルートノードのアドレスを「７」とすると、まず、このルートノードに１番目に参加するノードのアドレスは「７＋１＝８」となる。また、このノード以下に存在するノード数は「９」なので、このルートノードの子ノードとして２番目に参加するノードのアドレスは「８＋９＝１７」となり、３番目に参加するノードのアドレスは「１７＋９＝２６」となる。
【００６２】
同様に、Ｃｓｋｉｐ（１）を計算すると「４」が計算される。よって、アドレス「８」のノードの子ノードとして１番目に参加するノードのアドレスは「８＋１＝９」となる。また、このノード以下に存在するノード数は「４」なので、アドレス「８」のノードの子ノードとして２番目に参加するノードのアドレスは「９＋４＝１３」となる。また、同様にアドレス「１７」のノードの子ノードとして１番目に参加するノードのアドレスは「１７＋１＝１８」となる。このような計算を、このサービスＩＤ「７」のツリーの第３層まで繰り返すと、図５（ｂ）に示すようなアドレスの割り当てが行われる。
【００６３】
図３の割り当てアドレス算出部１２７は、各エリア番号の計算も、前記したＣｓｋｉｐ（ｄ）を用いた方法と同様に行う。つまり、論理ネットワークにおける第Ａａｒｅａ＿ｄ＋１階層におけるｍ番目に参加するエリアのエリア番号Ａａｒｅａは、以下の式（１０）により計算される。
【００６４】
Ａａｒｅａ＝Ａａｒｅａ＿ｐａｒｅｎｔ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）×（ｍ−１）＋１…式（１０）
但し、
Ａａｒｅａ＿ｄ＝Ａａｒｅａ＿Ｌｍの場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝０
Ａａｒｅａ＿ｄ≦Ａａｒｅａ＿Ｌｍ−１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ＋１）×Ａａｒｅａ＿Ｒｍｄ＋１）＋１
Ａａｒｅａ＿ｐａｒｅｎｔ：当該論理ネットワークにおける当該エリアの親エリアのエリア番号
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）：当該論理ネットワークの第Ａａｒｅａ＿ｄ＋１階層の１つのエリア以下に存在する子エリア数
Ａａｒｅａ＿ｄ：当該論理ネットワークにおける自エリアの属する階層
Ａａｒｅａ＿Ｌｍ：当該論理ネットワークの最大エリア階層数
Ａａｒｅａ＿Ｒｍｄ：当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数
【００６５】
つまり、割り当てアドレス算出部１２７は、前記したｄに代えて、Ａａｒｅａ＿ｄ（当該論理ネットワークにおける自エリアの属する階層）を用い、また、最大ツリー階層数Ｌｍに代えて、Ａａｒｅａ＿Ｌｍ（当該論理ネットワークの最大エリア階層数）を用い、最大子ノード数Ｒｍｄに代えて、Ａａｒｅａ＿Ｒｍｄ（当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数）を用いることで各エリア番号を計算できる。
【００６６】
次に、図６を用いて、図３のエリア内テーブル１３２、エリア構造テーブル１３３およびエリア境界ノード情報テーブル１３４を説明する。なお、これらのテーブルは、事前に手動で設定してもよいし、ノード情報を管理するサーバから取得した情報をもとに設定してもよいし、ノード間で制御情報を交換することにより設定してもよい。
【００６７】
図６に示すように、エリア内テーブル１３２は、エリア内のノード間のパケットのルーチングに用いられる情報である。このエリア内テーブル１３２は、所属情報、構成情報および隣接エントリ情報を備える。所属情報は、自身のノードの属するエリア（自エリア）における、自身のノードのアドレス（Ｍｙ ａｄｄｒ）およびそのエリアにおける自身のノードの階層（Ｍｙ Ｄｅｐｔｈ）を示した情報である。構成情報は、自エリアにおけるルートノードのアドレス（ｒｏｏｔ ａｄｄｒ）、最大ツリー階層数Ｌｍ、最大子ノード数Ｒｍ（またはＲｍｄ）を示した情報である。隣接エントリ情報は、自身のノードの親ノードのアドレス（Ｐａｒｅｎｔ ａｄｄｒ）および子ノードアドレス（Ｃｈｉｌｄ ａｄｄｒ１，２…，Ｎ)とを示した情報である。エリア内テーブル１３２は、ノードが受信したパケットの宛先アドレスに基づき、ネクストホップを決定するときに参照される。
【００６８】
エリア構造テーブル１３３は、論理ネットワークのエリアのうち、どのエリアにパケットを転送するか判断するときに参照される情報である。このエリア構造テーブル１３３は、エリア所属情報、エリア構成情報および隣接エリア情報を記憶する。エリア所属情報は、論理ネットワークにおける自エリアのアドレス（Ｍｙ Ａｒｅａ）および自エリアの階層（Ｍｙ Ａｒｅａ Ｄｅｐｔｈ）を示した情報である。エリア構成情報は、論理ネットワークにおけるルートエリアのエリア番号（ｒｏｏｔ Ａｒｅａ）、最大エリア階層数Ａａｒｅａ＿Ｌｍ、最大子エリア数Ａａｒｅａ＿Ｒｍｄを示した情報である。隣接エリア情報は、自エリアの親エリアのエリア番号（Ｐａｒｅｎｔ Ａｒｅａ）および子エリアのエリア番号（Ｃｈｉｌｄ Ａｒｅａ１，２，…，Ｎ)とを示した情報である。このエリア構造テーブル１３３は、ノード１０がエリアをまたいでパケットを転送するときに、宛先エリアの方向（ルート方向かリーフ方向か）を決定する際に参照される。
【００６９】
エリア境界ノード情報テーブル１３４は、自エリアに隣接する外部エリアごとに、その外部エリアと接続するエリア境界ノードを示した情報である。このエリア境界ノード情報テーブル１３４は、ノード１０がエリアをまたいでパケットを転送するときに、自エリア内のどのノード（エリア境界ノード）にパケットを転送すればよいかを決定するときに参照される。なお、このエリア境界ノード情報テーブル１３４は、エリア境界ノードとなるノード１０がエリア境界ノードであることを示すフラグを付したパケットを自エリア内にフラッディングしたものを、受信することにより設定してもよい。
【００７０】
図６に例示したエリア内テーブル１３２によれば、例えば、図７に示すようなエリア内の構成が分かる。つまり、エリアにおける自身のノードのアドレスは「Ａ」であり、このノードの自エリア内の階層は「１」、ルートノードのアドレスは「Ａ１」であり、最大ツリー階層数Ｌｍ＝２、最大子ノード数Ｒｍ０＝３である。自身のノードの親アドレスは「Ａ１」であり、子ノードのアドレスは「Ａ２」…「ＡＮ」であることが分かる。
【００７１】
さらに、エリア構造テーブル１３３によれば、図７に示すように、自身のノードの属するエリアは「Ａａｒｅａ」であり、エリアの階層は「Ａａｒｅａ＿ｄ」であり、ルートエリアは「Ａａｒｅａ＿ｐａｒｅｎｔ」であることが分かる。また、自身のノードの属するエリアの親エリアは「Ａａｒｅａ＿ｐａｒｅｎｔ」であり、子エリアは「Ａａｒｅａ＿ｃｈｉｌｄ １」、…、「Ａａｒｅａ＿ｃｈｉｌｄ Ｎ」であることが分かる。さらに、エリア境界ノード情報テーブル１３４から、隣接エリアは、「Ａａｒｅａ＿ｐａｒｅｎｔ」、「Ａａｒｅａ＿ｃｈｉｌｄ １」…「Ａａｒｅａ＿ｃｈｉｌｄ Ｎ」であり、それぞれのエリアに接続するエリア境界ノードは「Ａｄｄｒ Ａ１」、「Ａｄｄｒ Ａ２」、…、「Ａｄｄｒ ＡＮ」であることが分かる。
【００７２】
＜転送手順＞
次に、図８を用いて、ノード１０のパケット転送手順を説明する。なお、各ノード１０はトンネル処理部１２１により、各サービスの論理ネットワークにおいて隣接するノード１０との間でトンネルを確立し、トンネル情報をルーチングテーブル１３１に書き込んでおくものとする。また、各ノード１０は、自身のノードの属するサービスの論理ネットワーク情報１３０と、自エリア内における自身のノードのパラメータ情報（エリア内テーブル１３２）、自エリアのパラメータ情報（エリア構造テーブル１３３）および自エリアの外部エリアに関する情報（エリア境界ノード情報テーブル１３４）とを記憶部１３に記憶しているものとする。
【００７３】
まず、図３のノード１０のデータ受信部１２０は、ネットワークインタフェース部１１経由でパケットの入力を受け付けると（Ｓ１）、そのパケットの宛先アドレスを解析する（Ｓ２）。そして、エリア判定部１２２は、論理ネットワーク情報１３０と、パケットの宛先アドレスとを参照して、このパケットの宛先ノードの属するサービスとエリアとを特定する(Ｓ３)。つまり、エリア判定部１２２は、パケットの宛先アドレスから、この宛先アドレスがどの論理ネットワークのものかを特定し、さらに、この宛先アドレスが当該論理ネットワークのどのエリアに属するものかを特定する。
【００７４】
ここで、エリア判定部１２２は、Ｓ１で受信したパケットが、自エリア宛のものであると判定し（Ｓ４のＹｅｓ）、かつ、そのパケットが中継パケットでなければ（Ｓ５のＮｏ）、つまり、自身のノード宛のパケットであれば、そのパケットを自身のノードで受信し（Ｓ６）、処理を終了する。一方、そのパケットが中継パケットであれば（Ｓ５のＹｅｓ）、ネクストエリア決定部１２３は、自身のノードのエリア内でのアドレスＡと、受信したパケットのエリア内でのアドレス、エリア内テーブル１３２に示されるＬｍ（当該エリアのツリーの最大ツリー階層数）、Ｒｍｄ（当該エリアのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数）とを用いて、このパケットの次の転送先であるネクストホップを決定する（Ｓ９）。ここでのネクストホップの決定処理の詳細は後記するが、ネクストホップ決定部１２５が、このパケットのエリア内でのアドレスが自身のノードからみてルート側か、リーフ側かを判断することにより行われる。
【００７５】
そして、トンネル処理部１２１は、トンネル情報を参照して、このネクストホップのノード１０への送信Ｉ／Ｆ（InterFace）とオーバーレイリンクを決定し（Ｓ１０）、パケット転送部１２６は、この決定した送信Ｉ／Ｆとオーバーレイリンクとを用いて、パケットをネクストホップのノード１０へ送信する（Ｓ１１）。
【００７６】
一方、Ｓ４においてエリア判定部１２２が、Ｓ１で受信したパケットが、自エリア宛ではないと判定したとき（Ｓ４のＮｏ）、ネクストエリア決定部１２３は、自エリアのエリア番号Ａａｒｅａと、自エリアの属する階層Ａａｒｅａ＿ｄと、パケットの宛先アドレスに含まれるエリア番号と、エリア構造テーブル１３３に示されるＡａｒｅａ＿Ｌｍと、Ａａｒｅａ＿Ｒｍｄとから、ネクストエリアを決定する（Ｓ７）。つまり、ネクストエリア決定部１２３は、パケットの転送先となるネクストエリアを決定する。ここでのネクストエリアの決定処理の詳細は後記するが、ネクストエリア決定部１２３が、自エリアのエリア番号Ａａｒｅａと、パケットの宛先アドレスに含まれるエリア番号と、エリア構造テーブル１３３に示される、Ａａｒｅａ＿ｄと、Ａａｒｅａ＿Ｌｍと、Ａａｒｅａ＿Ｒｍｄとを参照して、自エリアからみて宛先ノードの属するエリアが、ルート側か、リーフ側かを判断することにより行われる。
【００７７】
ネクストエリア決定部１２３がネクストエリアを決定すると、エリア境界ノード特定部１２４は、エリア境界ノード情報テーブル１３４を参照して、このネクストエリア所属のエリア境界ノードを特定する（Ｓ８）。例えば、ネクストエリアが、エリア境界ノード情報テーブル１３４（図６参照）に示される外部エリアのうち「Ａａｒｅａ＿ｃｈｉｌｄ１」である場合、このエリアに所属するエリア境界ノードとして「Ａｄｄｒ Ａ２」を特定する。そして、ネクストホップ決定部１２５は、このエリア境界ノードに到達するためのネクストホップを決定するため、Ｓ９の処理を実行する。つまり、エリア境界ノード「Ａｄｄｒ Ａ２」を宛先アドレスとして考えたとき、パケットがこのエリア境界ノードに到達するためのネクストホップを決定する。このようにすることで、パケットはエリア境界ノード経由で、ネクストエリアに転送される。
【００７８】
論理ネットワーク内の各ノード１０が以上のような処理を実行することで、パケットはアドレスに設定された宛先エリアに到達し、この宛先エリア内の宛先ノードに到達する。
【００７９】
＜ネクストホップ決定処理＞
ここで、図９を用いて、図８におけるネクストホップの決定処理（Ｓ９）の詳細を説明する。まず、図３のネクストホップ決定部１２５は、割り当てアドレス算出部１２７へ、エリア内テーブル１３２に示される自身のノードの属する階層ｄと、Ｌｍ（自エリアのツリーの最大ツリー階層数）と、Ｒｍｄ（自エリアのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数）とを、割り当てアドレス算出部１２７へ出力し、Ｃｓｋｉｐ（ｄ−１）の計算依頼を行う。これを受けて、割り当てアドレス算出部１２７は、Ｃｓｋｉｐ（ｄ−１）を計算する（Ｓ９１）。このときのＣｓｋｉｐ（ｄ−１）の計算は、図４に示す式（７）または式（８）に基づき行われる。
【００８０】
次に、ネクストホップ決定部１２５は、この割り当てアドレス算出部１２７により計算されたＣｓｋｉｐ（ｄ−１）の値と、自エリアにおける自身のノードのアドレスＡとを用いて、パケットのエリア内での宛先アドレスＤが、以下の式（１１）に示す条件を満たすか否かを判断する（Ｓ９２）。つまり、ネクストホップ決定部１２５は、宛先アドレスＤのノードが、自身のノードからみてリーフ側にあるか、ルート側にあるかを判断する。
【００８１】
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）…式（１１）
【００８２】
ここで、ネクストホップ決定部１２５が、パケットの当該エリア内での宛先アドレスＤは、式（１１）に示す条件を満たすと判断したとき（Ｓ９２のＹｅｓ）、つまり、当該エリア内での宛先アドレスＤのノードが、自身のノードからみてリーフ側にあると判断したとき、図４に示す式（７）または式（８）に基づき、Ｃｓｋｉｐ（ｄ）を計算する（Ｓ９３）。そして、ネクストホップ決定部１２５は、以下の式（１２）により、このパケットの転送先であるネクストホップのノード１０のアドレスＮｅｘｔｈｏｐ ａｄｄｒを求める（Ｓ９４）。なお、Ｆｌｏｏｒ［ ］は、フロア関数であり、ここでは、(Ｄ−（Ａ＋１）)／Ｃｓｋｉｐ（ｄ）で求めた値の小数点以下を切り下げた値とする。
【００８３】
Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａ＋１＋Ｆｌｏｏｒ［(Ｄ−（Ａ＋１）)／Ｃｓｋｉｐ（ｄ）］×Ｃｓｋｉｐ（ｄ）…式（１２）
【００８４】
一方、ネクストホップ判定部１２５は、パケットのエリア内での宛先アドレスＤが、式（１１）に示す条件を満たさないとき（Ｓ９２のＮｏ）、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａｐａｒｅｎｔとする（Ｓ９５）。つまり、ネクストホップ決定部１２５は、宛先アドレスＤが式（１１）を満たさないときは、この宛先アドレスＤのノードは、自身のノードからみてルート側にあると判断できるので、自身のノードの親ノード（Ａｐａｒｅｎｔ）をネクストホップとする。
【００８５】
このようにノード１０は、エリア内における自身のノードのアドレスＡおよび階層ｄ、最大ツリー階層数Ｌｍ、最大子ノード数Ｒｍ（またはＲｍｄ）等を参照することで、パケットの転送先であるネクストホップを知ることができる。
【００８６】
なお、Ｓ９２において、ネクストホップ決定部１２５がパケットのエリア内での宛先アドレスＤは、式（１１）に示す条件を満たすと判断したとき（Ｓ９２のＹｅｓ）、つまり、エリア内での宛先アドレスＤのノードが、自身のノードからみてリーフ側にあると判断した場合であって、自身のノードの子ノード（エリア内テーブル１３２の隣接エントリ情報に示されるＣｈｉｌｄ ａｄｄｒ）が１つであるとき、Ｓ９３およびＳ９４の処理をスキップして、この子ノードをネクストホップノードとして決定するようにしてもよい。
【００８７】
＜ネクストエリア決定処理＞
次に、図１０を用いて、前記した図７におけるネクストエリアの決定処理（Ｓ７）の詳細を説明する。このネクストエリアの決定処理は、ノード１０が、パケットの宛先エリアが自エリアからみてルート側か、リーフ側かを判断することにより行われる。
【００８８】
具体的には、ノード１０が、前記したネクストホップ決定処理に用いた自身のノードのアドレスＡに代えて、Ａａｒｅａを用い、パケットのエリア内での宛先アドレスＤに代えて、このパケットの宛先エリアのエリア番号を用いる。また、自身のノードの属する階層ｄに代えて、Ａａｒｅａ＿ｄ（当該論理ネットワークにおける自エリアの属する階層）を用い、Ｌｍに代えて、Ａａｒｅａ＿Ｌｍ（当該論理ネットワークの最大エリア階層数）を用い、Ｒｍｄに代えて、Ａａｒｅａ＿Ｒｍｄ（当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数）を用いることで計算される。
【００８９】
まず、図３のネクストエリア決定部１２３は、エリア構造テーブル１３３に示されるＡａｒｅａ＿ｄと、Ａａｒｅａ＿Ｌｍと、Ａａｒｅａ＿Ｒｍｄとを、割り当てアドレス算出部１２７へ出力し、自エリアの階層をＡａｒｅａ＿ｄとしたときのＣｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の計算依頼を行う。これを受けて、割り当てアドレス算出部１２７は、エリア構造テーブル１３３に示されるＡａｒｅａ＿ＬｍおよびＡａｒｅａ＿Ｒｍｄ用いて、Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）を計算する（Ｓ９１）。このときのＣｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の計算は、図１１に示す式（１２）または式（１３）に基づき行われる。
【００９０】
なお、この式（１２）および（１３）は、前記した図４の式（７）および式（８）における、階層ｄを、Ａａｒｅａ＿ｄに置き換え、Ｌｍを、Ａａｒｅａ＿Ｌｍに置き換え、Ｒｍｄを、Ａａｒｅａ＿Ｒｍｄに置き換えたものである。
【００９１】
次に、ネクストエリア決定部１２３は、この割り当てアドレス算出部１２７により計算されたＣｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の値と、自身のノードのエリアにおけるアドレスＡａｒｅａとを用いて、宛先エリアのエリア番号が、式（１４）に示す条件を満たすか否かを判断する（Ｓ９２）。つまり、ネクストエリア決定部１２３は、宛先エリアが、自エリアからみてリーフ側か、ルート側かを判断する。
【００９２】
Ａａｒｅａ＜宛先エリアのエリア番号＜Ａａｒｅａ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）…式（１４）
【００９３】
ここで、ネクストエリア決定部１２３が、宛先エリアのエリア番号は、式（１４）に示す条件を満たすと判断したとき（Ｓ７２のＹｅｓ）、つまり、宛先エリアが、自身のノードからみてリーフ側にあると判断したとき、図１１に示す式（１２）または式（１３）に基づき、Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）を計算する（Ｓ７３）。そして、ネクストエリア決定部１２３は、以下の式（１５）により、ネクストエリアのエリア番号を求める（Ｓ７４）。
【００９４】
ネクストエリア＝Ａａｒｅａ＋１＋Ｆｌｏｏｒ［(宛先エリアのエリア番号−（Ａａｒｅａ＋１）)／Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）］×Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）…式（１５）
【００９５】
一方、ネクストエリア決定部１２３は、パケットの宛先エリアのエリア番号が、以下の式（１４）に示す条件を満たさないと判定したき（Ｓ７２のＮｏ）、ネクストエリア＝Ａａｒｅａ＿ｐａｒｅｎｔとする（Ｓ７５）。つまり、ネクストエリア決定部１２３は、宛先エリア番号が式（１４）を満たさないときは、この宛先エリアは、自エリアからみてルート側にあると判断できるので、自エリアの親エリア（エリア構造テーブル１３３に示されるＡａｒｅａ＿ｐａｒｅｎｔ）をネクストエリアとする。
【００９６】
このようにノード１０は、各エリアがツリー型トポロジで構成される場合、そのツリーにおける自エリアのエリア番号およびＡａｒｅａ＿ｄ、Ａａｒｅａ＿Ｌｍ、Ａａｒｅａ＿Ｒｍ（またはＡａｒｅａ＿Ｒｍｄ）を参照することで、入力されたパケットを次に転送すべきエリア（ネクストエリア）を知ることができる。
【００９７】
なお、Ｓ７２において、ネクストエリア決定部１２３は、宛先エリアのエリア番号が、式（１４）に示す条件を満たすと判断したとき（Ｓ７２のＹｅｓ）、つまり、宛先エリアが、自エリアからみてリーフ側にあると判断した場合であって、自エリアの子エリア（エリア構造テーブル１３３の隣接エリア情報におけるＣｈｉｌｄ Ａｒｅａ）が１つのとき、Ｓ７３およびＳ７４の処理をスキップして、この子エリアをネクストエリアとして決定するようにしてもよい。
【００９８】
以上説明したネットワークシステムによれば、論理ネットワークのツリートポロジを複数のエリアに分けて構成するので、そのエリアごとにツリーの最大階層数、子ノード数を設定可能となる。よって、論理ネットワーク内に新規ノードを接続するときの制約を緩和することができる。また、論理ネットワークのエリアごとにツリーの最大階層数、子ノード数を設定可能となるので、ネットワークにおいて確保すべきアドレス数を低減することができる。
【符号の説明】
【００９９】
１ バックボーンネットワーク
２，３ サービスネットワーク
１０ ノード
１１ ネットワークインタフェース部
１２ 処理部
１３ 記憶部
１２０ データ受信部
１２１ トンネル処理部
１２２ エリア判定部
１２３ ネクストエリア決定部
１２４ エリア境界ノード特定部
１２５ ネクストホップ決定部
１２６ パケット転送部
１２７ 割り当てアドレス算出部
１３０ 論理ネットワーク情報
１３１ ルーチングテーブル
１３２ エリア内テーブル
１３３ エリア構造テーブル
１３４ エリア境界ノード情報テーブル
【技術分野】
【０００１】
本発明は、ネットワークアーキテクチャに関する技術である。
【背景技術】
【０００２】
従来、ネットワークにより提供されるサービス単位でトポロジを構成するネットワーク構成方法がある（非特許文献１参照）。この方法では、トポロジをツリー構造で構築し、予め定められたツリーの階層数と、そのツリーにおける親ノード１つあたりの子ノード数をもとに、このトポロジ内の各ノードにアドレス番号を付与する。この方法によれば、各ノード（例えば、ルータ）は、受信したパケットのアドレス番号の大小をもとに、そのパケットを親ノード側に転送すればよいか、子ノード側に転送すればよいかを判断し、また子ノード側に転送する場合、どの子ノードに転送すればよいをかを判断できる。つまり、各ノードの宛先のエントリ数をできるだけ少なくできるので、ノードの持つべきルーチングテーブルの情報量を削減し、ルーチング処理の負荷を軽減できる。なお、このように、サービス単位で別個のネットワークトポロジをツリー構造で構築したものをオーバーレイツリートポロジと呼ぶ。
【０００３】
ここで、図１２を用いて、前記した方法による、オーバーレイツリートポロジの詳細を説明する。オーバーレイツリーポロジは、例えば、大きく２種類のパラメータでツリーの形状を決定する。１つは、ツリーの最大ツリー階層数Ｌｍであり、もう１つは、ｄ階層の１ルータ（１ノード）当たりの子ノード数Ｒｍｄである。これらの値から、ｄ＋１階層のルータ（ノード）以下の総ルータ数Ｃｓｋｉｐ（ｄ）を算出し、各ノードのアドレッシング（アドレス番号の付与）を行う。なお、Ｃｓｋｉｐ（ｄ）の値は、図１２の吹き出し部分に示される式により計算される。
【０００４】
このオーバーレイツリーポロジ上に配置される各ノードは、図１２に示すようなルーチングテーブルを保持する。このルーチングテーブルには、自身のアドレス（My addr)や自身の階層数(My Depth)等の所属情報、ツリーのルートノードのアドレス（root addr)や、ツリーの階層数（Ｌｍ）、階層毎の子ノード数Ｒｍｄ等の構成情報、自身のノードの親ノード（Parent addr)や子ノード（Child addr)等の隣接ノードの情報を示す隣接エントリ情報を含む。そして、ノードは、このルーチングテーブルと、Ｃｓｋｉｐ（ｄ）の値とから、パケットの宛先アドレスが自身の親ノード側に存在するか、子ノード側に存在するかを判断し、ネクストホップ（次にパケットを転送すべきノード）を決定することが可能となる。つまり、ノードは、宛先アドレスに対するエントリ数を保持せずとも、宛先アドレスでネクストホップを決定できる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】磯貝彰則、小島久史、 井上一郎、塩本公平、” 多数サービスをスケーラブルに収容するネットワーク仮想化技術に関する検討”2008年 ソサイエティ大会
【発明の概要】
【発明が解決しようとする課題】
【０００６】
このようなオーバーレイツリートポロジにおいて、特定のサブツリー以下に多数のノードが存在する場合、事前に確保が必要なアドレス数が増大する。つまり、非特許文献１に記載の技術において、各ノードのアドレスは、そのツリーの最も深い階層までの階層数と、１つのノードの子ノード数の最大値を見越して決める必要がある。よって、例えば、図１３に示すように、サブツリーごとに階層の深さの偏りがある場合でも、ツリーのアドレスは階層数と子ノード数を基準に決定する必要がある。つまり、ノードの存在の有無に関わらず、アドレスの確保は必要なので、実際には使用されないアドレス空間（未使用のアドレス空間）が大量に発生する。図１３に示した例でいうと、６〜１００１、１００４〜２００１、２００５〜３００１等のアドレスが未使用アドレスとなる。
【０００７】
このような未使用アドレスが大量に発生するという現象は、同じ階層におけるノード間での子ノード数の数に偏りがある場合にも、発生しうる。このようにネットワークのノードに対し、未使用アドレスが大量に発生するようなアドレッシングを行うと、極めて大きな値（大きな桁数）のアドレスを持つノードが現れる可能性が高くなる。よって、各ノードは、ルーチング処理時に、このように極めて大きな値（大きな桁数）のアドレスを処理する可能性も高くなり、ルーチング処理の負荷が高くなるという問題がある。
【０００８】
さらに、前記したサービスにおけるノードの追加や削除、トラヒック量の増減が発生すると、オーバーレイツリートポロジへの新たなノードの参加および既存のノードの離脱等も必要となる。ここで、オーバーレイツリートポロジへの新たなノードを接続する場合、ノードの数が集中しているサブツリー周辺では最大ツリー階層数Ｌｍや最大子ノード数Ｒｍｄによる制限があるため、所望する位置に接続できないという問題がある。
【０００９】
例えば、図１４に示すように、オーバーレイツリートポロジにおいて、最大ツリー階層数Ｌｍ＝５、最大子ノード数Ｒｍ５＝３という制限がある場合を考える。つまり、子ノード数は３台までという制限がある場合を考える。この場合、新規参加ノードは、この階層Ｌｍ＝５のノードＡ，Ｂのいずれかのノードの子ノードとして接続したくても、これらのノードには、既に３台の子ノードが接続されているので、ノードＡ，Ｂの子ノードとして接続できない。従って、この場合、新規参加ノードは、別の階層のノードの子ノードとして接続しなければならない等、必ずしも最適な位置（または、ネットワークの管理者が所望する位置）に接続できないことがある。
【００１０】
本発明は、前記課題を解決し、オーバーレイツリートポロジにおいて確保すべきアドレス数を低減し、新規ノードが論理ネットワークに参加する場合の制限を緩和することを目的とする。
【課題を解決するための手段】
【００１１】
前記した課題を解決するため、本発明は、１以上のサービスのパケットを転送するネットワークシステムを、当該サービスのパケットを転送する１以上の論理ネットワークに分け、その論理ネットワークをツリー型トポロジとして構成し、当該論理ネットワークを１以上のサブツリーからなるエリアに分割する場合において、そのエリアにおけるツリーの最大ツリー階層数Ｌｍと、そのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数Ｒｍｄとをもとに、そのエリア内のツリーにおける第ｄ＋１階層におけるｎ番目に参加する子ノードの当該エリア内におけるアドレスＡｎが、以下の式（１）により定義されるノードを備えるネットワークシステムであって、
Ａｎ＝Ａｐａｒｅｎｔ＋Ｃｓｋｉｐ（ｄ）×（ｎ−１）＋１…式（１）
但し、
ｄ＝Ｌｍの場合
Ｃｓｋｉｐ（ｄ）＝０
０≦ｄ≦Ｌｍ−１の場合
Ｃｓｋｉｐ（ｄ）＝（Ｃｓｋｉｐ（ｄ＋１）×Ｒｍｄ＋１）＋１
Ａｐａｒｅｎｔ：当該エリアのツリーにおける自身のノードの親ノードのアドレス
Ｃｓｋｉｐ（ｄ）：当該エリアのツリーの第ｄ＋１階層の１つのノード以下に存在するノード数
ｄ：当該エリアのツリーにおける自身のノードの属する階層
Ｌｍ：当該エリアのツリーの最大ツリー階層数
Ｒｍｄ：当該エリアのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数
当該論理ネットワークにおいて、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍと、その論理ネットワークの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄとをもとに、その論理ネットワークにおける第Ａａｒｅａ＿ｄ＋１階層におけるｍ番目に参加するエリアのエリア番号Ａａｒｅａが、以下の式（２）により定義されることを特徴とするネットワークシステムとした。
Ａａｒｅａ＝Ａａｒｅａ＿ｐａｒｅｎｔ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）×（ｍ−１）＋１…式（２）
但し、
Ａａｒｅａ＿ｄ＝Ａａｒｅａ＿Ｌｍの場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝０
Ａａｒｅａ＿ｄ≦Ａａｒｅａ＿Ｌｍ−１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ＋１）×Ａａｒｅａ＿Ｒｍｄ＋１）＋１
Ａａｒｅａ＿ｐａｒｅｎｔ：当該論理ネットワークにおける当該エリアの親エリアのアドレス
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）：当該論理ネットワークの第Ａａｒｅａ＿ｄ＋１階層の１つのエリア以下に存在する子エリア数
Ａａｒｅａ＿ｄ：当該論理ネットワークにおける自エリアの属する階層
Ａａｒｅａ＿Ｌｍ：当該論理ネットワークの最大エリア階層数
Ａａｒｅａ＿Ｒｍｄ：当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数
【００１２】
また、このネットワークシステムにおけるノードは、（１）論理ネットワークそれぞれに割り当てられたアドレス空間を示した論理ネットワーク情報と、（２）論理ネットワークにおいて自身のノードの属するエリアのエリア番号Ａａｒｅａと、当該論理ネットワークにおいて当該エリアの属する階層Ａａｒｅａ＿ｄと、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍおよび１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄと、当該エリアの親エリアＡａｒｅａ＿ｐａｒｅｎｔおよび子エリアＡａｒｅａ＿ｃｈｉｌｄとを示したエリア構造テーブルと、（３）当該エリアに隣接する隣接エリアごとに、その隣接エリアへ接続するエリア境界ノードを示したエリア境界ノード情報テーブルと、（４）当該エリアにおける自身のノードのアドレスＡ、自身のノードの属する階層ｄ、最大ツリー階層数Ｌｍおよび最大子ノード数Ｒｍｄ、自身のノードの親ノードのアドレスＡｐａｒｅｎｔおよび子ノードのＡｃｈｉｌｄとを示したエリア内テーブルとを記憶する記憶部と、当該パケットの宛先ノードの属するエリア番号を含むアドレスが付されたパケットの入出力を司るネットワークインタフェース部と、論理ネットワーク情報と、ネットワークインタフェース部経由で入力されたパケットの宛先アドレスに含まれる宛先ノードの属するエリアのエリア番号を参照して、宛先ノードが自身のノードの属するエリアのノードか否かを判断するエリア判定部と、（Ａ）宛先ノードが、自身のノードの属するエリアのノードであったとき、エリア内テーブルと自身のノードのアドレスＡと、アドレスに含まれるエリア内でのアドレスＤとを参照して、その宛先ノードに転送する際のネクストホップノードのアドレスＮｅｘｔｈｏｐ ａｄｄｒを、以下の式（３）または式（４）により決定するネクストホップ決定部と、
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）の場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａ＋１＋Ｆｌｏｏｒ［（Ｄ−（Ａ＋１））／Ｃｓｋｉｐ（ｄ）］×Ｃｓｋｉｐ（ｄ）…式（３）
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）ではない場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａｐａｒｅｎｔ…式（４）
決定されたアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ入力されたパケットをネットワークインタフェース部経由で転送するパケット転送部と、
（Ｂ）宛先ノードが、自身のノードの属するエリアのノードではなかったとき、その宛先ノードに転送する際のネクストエリアを、エリア構造テーブルを参照して、以下の式（５）または式（６）により決定するネクストエリア決定部と、
Ａａｒｅａ＜宛先エリアのエリア番号＜Ａａｒｅａ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の場合、ネクストエリア＝Ａａｒｅａ＋１＋Ｆｌｏｏｒ［（エリア番号−（Ａａｒｅａ＋１））／Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）］×Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）…式（５）
Ａａｒｅａ＿ｄ＜宛先エリアのエリア番号＜Ａａｒｅａ＿ｄ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）ではない場合、ネクストホップエリア＝Ａａｒｅａ＿ｐａｒｅｎｔ…式（６）
エリア構造テーブルを参照して、決定したネクストエリアへ接続するエリア境界ノードのアドレスを特定するエリア境界ノード特定部とを備え、ネクストホップ決定部は、特定したエリア境界ノードのアドレスを宛先アドレスとしたときのネクストホップへのアドレスＮｅｘｔｈｏｐ ａｄｄｒを決定し、パケット転送部は、決定したアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ、入力されたパケットを転送することを特徴とする。
【００１３】
このようにすることで、ネットワークの各ノードは、サービスごとに用意された論理ネットワークに基づきパケットを転送する。また、この論理ネットワークにおいて、従来、論理ネットワーク全体を１つのツリートポロジとしていたが、その論理ネットワークを１以上のサブツリーからなる複数のエリアに分割する。つまり、論理ネットワークを分割したエリア同士の接続関係がツリー構造になり、かつ、エリア内のノード間の接続関係もツリー構造になる。これにより、ツリーの最大ツリー階層数Ｌｍおよびツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数Ｒｍｄを、エリアごとに設定可能になる。よって、オーバーレイツリートポロジに新規ノードが参加するときの制限を緩和することができ、新規ノードを最適な位置に接続しやすくなる。また、オーバーレイツリートポロジのサブツリー間で階層数やノード数の偏りがあった場合でも、エリアごとにツリーの構造を変化させて対応できるので、事前に確保が必要なアドレス数を削減できる。
【００１４】
また、各エリア内のノードのアドレスは、ルートノードから、子ノード、孫ノードに行くに従い大きな値をとるように割り当てられる。つまり、パケットを受信したノードは、宛先アドレスと自身のノードのアドレスとを比較することで、ツリー型トポロジにおいてその宛先アドレスのノードが、自身のノードからみてルート方向（親ノードの方向）にあるのか、リーフ方向（子ノードの方向）にあるのかが分かる。従って、まず、パケットを受信したノードは、パケットの宛先アドレスと自身のアドレスとの比較により、ネクストホップノード（このパケットを転送先となるノード）は、ルート方向のノードか、リーフ方向のノードかを判断できる。ここで、ネクストホップノードがリーフの方向のノードであると判断した場合、自身のノードにリーフ方向のノード（子ノード）が複数ある場合もある。この場合、このノードの子ノードの１つは、この自身のノードのアドレスに１を足した値であり、他の子ノードのアドレスは、このアドレスにＣｓｋｉｐ（ｄ）で計算される値が加算された値が割り当てられる（例えば、あるノードのｎ番目の子ノードのアドレスは、このアドレスにＣｓｋｉｐ（ｄ）×ｎが加算された値となる）ので、ノードは、フロア関数によりＦｌｏｏｒ［（Ｄ−（Ａ＋１））／Ｃｓｋｉｐ（ｄ）］を計算して、パケットの宛先アドレスにつながるノードは、このノードの第何番目の子ノードかを特定できる。そして、ノードは、その特定した子ノードへパケット転送する。各ノードがこのような転送処理を行うことで、パケットはエリア内のツリー型トポロジのノード間を転送され、所定の宛先アドレスのノードに到達することができる。
【００１５】
なお、このような各ノードへのアドレス割り当てに用いられるＣｓｋｉｐ（ｄ）は、０≦ｄ≦Ｌｍ−１の場合、Ｃｓｋｉｐ（ｄ）＝（Ｃｓｋｉｐ（ｄ＋１）×Ｒｍｄ＋１）＋１という式に基づき計算される。これより、エリア内のツリー型トポロジの階層ごとに最大子ノード数が異なる場合、その階層ごとの最大子ノード数Ｒｍｄを考慮して、無駄のないアドレスの割り当てを実現している。つまり、エリア内のツリー型トポロジの階層ごとに最大子ノード数が異なる場合に、その階層ごとの最大子ノード数Ｒｍｄを考慮し、実際には割り当てられないことが明らかなアドレスについては、これを省いてアドレスが割り当てられている。これにより、エリア内で事前に確保が必要なアドレス数を低減できる。
【００１６】
また、この論理ネットワークにおける各エリアのエリア番号についても、前記したノードのアドレスと同様に、ルートエリアから、子エリア、孫エリアに行くに従い大きな値をとるように割り当てられる。つまり、パケットを受信したノードは、宛先エリアのエリア番号と自エリアのエリア番号とを比較することで、ツリー型トポロジにおいてその宛先エリアに到達するためのネクストエリアへは、自エリアからみてルート方向（親ノードの方向）にあるのか、リーフ方向（子ノードの方向）にあるのかが分かる。このような転送処理を各エリアのノードが行うことで、パケットはツリー型トポロジのエリア間を転送され、所定のエリアのノードに到達することができる。なお、各ノードは、自エリアに隣接するエリアごとに、そのエリアへ接続するためのエリア境界ノードのアドレスを示したエリア境界ノード情報を記憶する。これにより各ノードは、このネクストエリアにパケットを到達させるためには、自エリア内のどのノード目指してパケットを転送すればよいかが分かる。つまり、ネクストホップ決定部が、この特定したエリア境界ノードのアドレスを宛先アドレスとしたときのネクストホップを求めることで、このネクストエリアにパケットを到達させるためのネクストホップが分かる。
【００１７】
なお、このツリー型トポロジのエリアで、各階層ごとに最大子エリア数が異なる場合、その階層ごとの最大子エリア数Ａａｒｅａ＿Ｒｍｄを考慮し、実際には割り当てられないことが明らかなエリア番号については、これを省いてアドレスが割り当てられる。これにより、論理ネットワーク内で事前に確保が必要なエリア番号の数も低減できる。
【００１８】
また、本発明は、エリア内のツリーのすべての階層で当該階層の子ノード数Ｒｍが等しいとき、式（１）におけるＣｓｋｉｐ（ｄ）は、
Ｒｍ＝１の場合
Ｃｓｋｉｐ（ｄ）＝Ｌｍ−ｄ
Ｒｍ＝１ではない場合
Ｃｓｋｉｐ（ｄ）＝（１−ＲｍＬｍ−ｄ）／（１−Ｒｍ）
とする。
【００１９】
このようにすることで、オーバーレイツリートポロジにおいて、各階層の子ノード数が同じ場合、Ｃｓｋｉｐ（ｄ）の計算を簡単に行うことができる。
【００２０】
また、本発明は、論理ネットワーク内のすべてのエリアの階層で当該階層の子エリア数Ａａｒｅａ＿Ｒｍが等しいとき、
式（１）におけるＣｓｋｉｐ（Ａａｒｅａ＿ｄ）は、
Ａａｒｅａ＿Ｒｍ＝１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝Ｌｍ−ｄ
Ａａｒｅａ＿Ｒｍ＝１ではない場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（１−Ａａｒｅａ＿ｄＡａｒｅａ＿Ｌｍ−Ａａｒｅａ＿ｄ）／（１−Ａａｒｅａ＿Ｒｍ）
とする。
【００２１】
このようにすることで、オーバーレイツリートポロジの各階層の子エリア数が同じ場合、Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）の計算を簡単に行うことができる。
【００２２】
また、本発明は、請求項５に記載のパケット転送方法を、ネットワークシステム内のノードであるコンピュータに実行させるためのプログラムとした。
【００２３】
このようなプログラムによれば、一般的なコンピュータに、請求項５に記載のパケット転送方法を実行させることができる。
【発明の効果】
【００２４】
本発明によれば、オーバーレイツリートポロジにおいて確保すべきアドレス数を低減し、新規ノードがオーバーレイツリートポロジに参加する場合の制限を緩和できる。
【図面の簡単な説明】
【００２５】
【図１】本実施の形態のノードを含むシステムを例示した図である。
【図２】本実施の形態の論理ネットワークを例示した図である。
【図３】本実施の形態のノードの構成を示すブロック図である。
【図４】本実施の形態のＣｓｋｉｐ（ｄ）の計算式を示した図である。
【図５】図４に示す計算式により求められたＣｓｋｉｐ（ｄ）によりアドレッシングされたツリー型トポロジを例示した図である。
【図６】図３のルーチングテーブルを例示した図である。
【図７】図６のルーチングテーブルの示すエリア構成を例示した図である。
【図８】図３のノードのパケット転送処理手順を示したフローチャートである。
【図９】図３のネクストホップ決定処理の詳細を示したフローチャートである。
【図１０】図３のネクストエリア決定処理の詳細を示したフローチャートである。
【図１１】本実施の形態のＣｓｋｉｐ（Ａａｒｅａ＿ｄ）の計算式を示した図である。
【図１２】比較例のオーバーレイツリートポロジを示した図である。
【図１３】比較例のオーバーレイツリートポロジを示した図である。
【図１４】比較例のオーバーレイツリートポロジを示した図である。
【発明を実施するための形態】
【００２６】
以下、本発明を実施するための形態（以下、実施の形態とする）について説明する。
【００２７】
＜概要＞
以下、本発明を実施するための最良の形態（以下、実施の形態という）について説明する。まず、本実施の形態のノードを含むネットワークシステムの概要を、図１を用いて説明する。ネットワークシステムは、例えば、図１に示すように、バックボーンネットワーク１と、そのバックボーンネットワーク１により接続されるサービスネットワーク２，３を含んで構成される。
【００２８】
バックボーンネットワーク１は、複数のノード１０を含んで構成される。なお、このバックボーンネットワーク１のノード１０は、サービスネットワーク２，３との境目に設置される境界ノードと、その境界ノード間を接続する中継ノードとを含んで構成される。各ノード１０は、例えば、ルータやスイッチである。サービスネットワーク２，３にはサービスを提供するサーバ２１と、そのサーバから提供されるサービスを利用するクライアント３１とを含む。ここでは、サービスネットワーク２は、サービスＡを提供するサーバ２１Ａと、サービスＢを提供するサーバ２１Ｂとを含み、サービスネットワーク３は、サービスＡを利用する（つまり、サーバ２１Ａとデータ送受信を行う）クライアント３１Ａと、サービスＢを利用する（つまり、サーバ２１Ｂとデータ送受信を行う）クライアント３１Ｂとを含む。つまり、境界ノードであるノード１０（１０Ａ，１０Ｂ）間にはサービスＡ，Ｂ両方のトラヒックが流れることになる。
【００２９】
ここで、このバックボーンネットワーク１内において、サービスＡのルーチング経路と、サービスＢのルーチング経路とを分けるために、サービスごとに論理ネットワークを用意する。例えば、図１に示すように、サービスＡについて論理ネットワークＡという論理ネットワークを用意し、サービスＢについては論理ネットワークＢという論理ネットワークを用意する。そして、各論理ネットワークを構成するノードにアドレッシング（アドレスの割り当て）を行う。このときのアドレッシングは以下のように行う。まず、各サービスの論理ネットワークが利用するアドレス空間を、論理ネットワークごとに重複しないように割り当てる。例えば、サービスＡについて割り当てアドレス空間「０１０１〜０９０９」を割り当てたならば、サービスＢについて割り当てアドレス空間について「１００１０〜１９０９」を割り当てる。
【００３０】
この割り当てアドレス空間の大きさや、各ノードのアドレスの割り当て方法は、各論理ネットワークに含まれるノード１０の数やトポロジの構成方法による。このようにサービスごとに重複のないアドレス空間の割り当てを行うことで、当該アドレスのノード１０がどのサービスの論理ネットワークに属するかを識別することができる。ここで、サービスごとに用意される論理ネットワークは、例えば、ツリー型トポロジで構成され、各ノード１０はルーチングテーブル１３１（後記）を参照し、このツリー型トポロジを前提としたルーチングを行う。よって、ノード１０は、ルーチングテーブル１３１にパケットの宛先アドレスごとのエントリを用意する必要がなくなる。
【００３１】
次に、図２を用いて、前記した論理ネットワークの構成例を説明する。論理ネットワークＮは、図２に例示するように複数のエリア（エリア１〜７）から構成される。このエリアはそれぞれ、オーバーレイツリートポロジの一部のツリー（サブツリー）を含む。また、この論理ネットワークＮにおける、エリア自体のトポロジもツリー構造とする。つまり、エリア同士はツリー状に接続される。
【００３２】
このエリアの構造は、
Ａａｒｅａ＿Ｌｍ：当該論理ネットワークの最大エリア階層数
Ａａｒｅａ＿Ｒｍｄ：当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数
により定義される。
【００３３】
例えば、論理ネットワークＮは、エリア階層Ａａｒｅａ＿Ｌｍ＝２であり、０階層目の子エリア数Ａａｒｅａ＿Ｒｍ０＝２、１階層目の子エリア数Ａａｒｅａ＿Ｒｍ１＝２である場合、図２に示すようなエリア構造となる。このエリアの構造に関する定義情報は、ノード内のエリア構造テーブル１３３（後記）に記憶される。各エリアのエリア番号は、Ａａｒｅａ＿ＬｍおよびＡａｒｅａ＿Ｒｍｄをもとに決定される（詳細は後記）。
【００３４】
このエリア内のノード１０の構造は、
Ｌｍ：当該エリアのノードの最大ツリー階層数
Ｒｍｄ：当該エリアの第ｄ階層の１つのノードが保持可能な最大子エリア数
により定義される。
【００３５】
例えば、エリア内階層Ｌｍ＝１であり、このエリアの０階層目の子ノード数Ｒｍ０＝３である場合、図２のエリア２のような構造となる。このエリア内の構造に関する定義情報は、ノード内のエリア内テーブル１３２（後記）に記憶される。各エリア内におけるノード１０のアドレスは、このＬｍ、Ｒｍｄをもとに決定される（詳細は後記）。
【００３６】
なお、このエリア同士は、エリア境界ノードにより接続される。このエリア境界ノードには、そのエリア境界ノードの属するエリアごとに、そのエリアの構造から決定されたアドレスが付与される。そして、論理ネットワークの各ノードは、自エリアに隣接する外部エリアと、その外部エリアに接続するためのエリア境界ノードとの情報（外部エリア情報）をエリア境界ノード情報テーブル１３４（後記）に記憶する。例えば、図２のエリア６のノード「９９９」は、外部エリア情報として、隣接エリアがエリア５であり、このエリア５へ接続する自エリアのエリア境界ノードは「１」であるという情報を記憶する。
【００３７】
なお、論理ネットワークの各ノード１０のアドレスは、エリアのエリア番号と当該エリア内における自身のノードのアドレスとの組み合わせにより記述される。例えば、エリア４のノード「３」のアドレスは「エリア４，ノード３」というように記述される。ノード間のパケットの転送は、このアドレスをもとに行われる。すなわち、ノード１０はそれぞれ、パケットの宛先アドレスに含まれるエリア番号から、そのパケットが自エリア宛か否かを判断し、自エリア宛であれば、その宛先アドレスに含まれる自エリア内のアドレスを用いてルーティングを行う。一方、他エリア宛であれば、ノード１０は、エリア構造テーブル１３２およびエリア境界ノード情報テーブル１３４を参照して、どのエリアに転送すべきか、また、そのエリアに接続するエリア境界ノードはどれかを特定し、この特定したエリア境界ノードへパケットを転送する。各ノード１０が、このような処理を繰り返すことで、パケットは宛先アドレスに示されるノードに到達する。
【００３８】
なお、各エリア内のアドレスおよび各エリアのエリア番号は、ルート側から、子方向に行くに従い、大きな値をとるように割り当てられる。つまり、パケットを受信したノードは、宛先アドレスのエリア内のアドレスやエリア番号と、自身のノードのエリア内のアドレスやエリア番号とを比較することで、ツリー型トポロジにおいてその宛先が、ルート方向（親方向）にあるのか、リーフ方向（子方向）にあるのかを判断できる。よって、各ノード１０のルーチング処理負荷を軽減できる。
【００３９】
また、このように論理ネットワークを複数のエリアに分割し、そのエリアごとにＬｍ、Ｒｍｄが設定可能となるので、新規ノードが接続するとき、様々な箇所を選択可能となり、確保すべきアドレス数を低減できる。さらに、論理ネットワークのエリア階層（Ａａｒｅａ＿ｄ）ごとに子エリア最大値（Ａａｒｅａ＿Ｒｍ）を設定可能なので、エリアの構造自体も自由度が高いものとなる。
【００４０】
＜構成＞
次に、図３を用いて、このようなバックボーンネットワーク１に用いられるノード１０の構成を説明する。
【００４１】
図３に示すように、ノード１０は、他のノード１０との間でパケットの入出力を行うためのネットワークインタフェース部１１と、ネクストホップの決定等を行う処理部１２と、この処理部１２がネクストホップの決定を行うときに参照するルーチングテーブル１３１を記憶する記憶部１３とを備える。
【００４２】
なお、ネットワークインタフェース部１１は、パケット等の入出力を行うためのインタフェースから構成される。また、処理部１２は、このノード１０が備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部１３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、ノード１０をプログラム実行処理により実現する場合、記憶部１３には、このノード１０の機能を実現するためのプログラムが格納される。
【００４３】
処理部１２は、データ受信部１２０と、トンネル処理部１２１と、エリア判定部１２２と、ネクストエリア決定部１２３と、エリア境界ノード特定部１２４と、ネクストホップ決定部１２５と、パケット転送部１２６と、割り当てアドレス算出部１２７とを含んで構成される。
【００４４】
データ受信部１２０は、ネットワークインタフェース部１１経由で受信したパケットの宛先アドレスを検出し、このパケットが自分宛のものか、それとも中継すべきか否かの判断を行う。なお、この宛先アドレスは、パケットの宛先ノードの属するエリアのエリア番号＋エリア内でのアドレスの組み合わせにより記述される。そして、例えば、ノード１０間で、アドレスのエリア番号を示すカラム（例えばアドレスの前半２桁）と、エリア内でのアドレスを示すカラム（例えばアドレスの後半２桁）とを予め決めておく。そして、ノード１０がパケットの転送を行う際は、それぞれのカラムの値を参照することで、転送先のノード１０を決定する。
【００４５】
トンネル処理部１２１は、他のノード１０との間のトンネルを確立する。また、トンネル確立後、ルーチングテーブル１３１にこの確立したトンネルに関するトンネル情報を書き込む。なお、このように、自身のノードが論理ネットワーク上でネクストホップとしたいノード１０との間でトンネルを確立しておくことで、ノード１０は、物理的にリンク接続された隣接ノード１０を飛び越して、そのトンネルが確立されたノード１０をネクストホップとしてパケットを転送することができる。
【００４６】
エリア判定部１２２は、論理ネットワーク情報１３０（後記）と、受信したパケットの宛先アドレスとを参照して、宛先ノードの属する論理ネットワーク（例えば、図１の論理ネットワークＡ，Ｂ）を特定する。そして、この特定した論理ネットワークに関するエリア構造テーブル１３３と、このパケットの宛先アドレスに含まれるエリア番号とを参照して、パケットの宛先エリアが自ノードのエリアか否かを判断する。
【００４７】
ネクストエリア決定部１２３は、エリア判定部１２２により、パケットの宛先ノードが、自エリアのノードではないと判断されたとき、その宛先ノードに転送する際のネクストエリアを、エリア構造テーブル１３３（後記）を参照して、決定する。このネクストエリアの決定処理の詳細は、後記する。
【００４８】
エリア境界ノード特定部１２４は、ネクストエリア決定部１２３により決定されたネクストエリアへ接続するエリア境界ノードを、エリア境界ノード情報テーブル１３４（後記）を参照して特定する。
【００４９】
ネクストホップ決定部１２５は、受信したパケットの宛先アドレスと、ルーチングテーブル１３１とを参照して、このパケットの転送先のノード１０であるネクストホップノードの決定を行う。このときのネクストホップノードの決定処理の詳細は、具体例を用いて後記する。
【００５０】
パケット転送部１２６は、ネクストホップ決定部１２５により決定されたネクストホップノード、または、エリア境界ノード特定部１２４により特定されたエリア境界ノードへ、パケットを転送する。なお、このパケット転送部１２６は、パケットを転送するとき、ＭＰＬＳ（Multi-Protocol Label Switching）によりパケットを転送してもよい。
【００５１】
割り当てアドレス算出部１２７は、エリア内におけるノード１０のアドレスおよび各エリアのエリア番号を計算する。ノード１０のエリア内のアドレスは、Ｃｓｋｉｐ（ｄ）（第ｄ＋１階層の１つのノード以下に存在するノード数、つまり、第ｄ＋１階層のノードの子ノード同士のアドレスがどの程度離れているかを示す値）を計算することにより求められる。また、エリア番号も同様に、Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）（第ｄ＋１階層の１つのエリア以下に存在するエリア数、つまり、第ｄ＋１階層のエリアの子エリア同士のアドレスがどの程度離れているかを示す値）を計算することにより求められる。この割り当てアドレス算出部１２７により行われる計算処理の詳細は、後記する。
【００５２】
記憶部１３は、論理ネットワーク情報１３０とルーチングテーブル１３１とを記憶する。この論理ネットワーク情報１３０は、論理ネットワークそれぞれに割り当てられたアドレス空間を示す情報である（表１参照）。
【００５３】
【表１】
【００５４】
ルーチングテーブル１３１は、このノード１０が受信したパケットのルーチング（転送先の決定）を行うときに参照される情報である。このルーチングテーブル１３１は、自身のノードの属する論理ネットワークごとに用意され、エリア内テーブル１３２と、エリア構造テーブル１３３と、エリア境界ノード情報テーブル１３４とを備える。また、ここでは図示を省略しているが、ルーチングテーブル１３１は、自身のノードが、当該論理ネットワークの親ノード、子ノードとの間で確立されたトンネルについてのトンネル情報も含むものとする。このトンネル情報は、ノード１０間でトンネルを用いてパケットを転送するときに用いられる情報である。
【００５５】
ここで、図３を参照しつつ、図４および図５を用いて、割り当てアドレス算出部１２７による、各エリア内のノード１０のアドレスの計算方法を説明する。ここでのアドレスの計算方法は、例えば、近距離無線通信に用いられる規格ZigBee（登録商標）（Zigbee Specification Document 053474r17 3.6.1.6章 p370〜372）を応用したものである。
【００５６】
ここでのアドレスの計算には、２種類のパラメータが関与する。１つめのパラメータは、エリア内のトポロジをツリー型トポロジで考えたときの、最大ツリー階層数（ツリーの深さ）Ｌｍである。この最大ツリー階層数Ｌｍは、ツリーのルートの階層を「０（第０階層）」と考え、論理ネットワークごとに最大で何階層のツリー型トポロジを構成するかを定めるパラメータである。２つめのパラメータは、エリア内のツリーの１つのノード１０が持つ最大子ノード数Ｒｍである。この最大子ノード数Ｒｍは、エリア内のツリーの全階層で同じ値をとるパターンと、異なる値をとるパターンの２つのパターンが適用できる（前者の最大子ノード数を、Ｒｍ、後者の第ｄ階層の最大子ノード数を、Ｒｍｄとする）。
【００５７】
割り当てアドレス算出部１２７は、この最大ツリー階層数Ｌｍと、最大子ノード数Ｒｍ（またはＲｍｄ）を用い、図４に示した式（７）または式（８）を用いてエリア内のツリーの第ｄ＋１階層の１つのノード以下に存在するノード数を表すＣｓｋｉｐ（ｄ）を計算する。そして、このＣｓｋｉｐ（ｄ）を、以下の式（９）に代入することで、当該エリア内のツリーの第ｄ＋１階層においてｎ番目に参加するノードのアドレスＡｎを求めることができる。なお、Ａｐａｒｅｎｔは、ｎ番目に参加するノードの親ノードとなるノードのアドレスである。
【００５８】
Ａｎ＝Ａｐａｒｅｎｔ＋Ｃｓｋｉｐ（ｄ）×（ｎ−１）＋１…式（９）
【００５９】
ここで、図５（ａ）を参照して、ツリーの全階層の子ノード数が同じ場合のアドレスの割り当ての具体例を説明する。最大ツリー階層数Ｌｍ＝２、最大子ノード数Ｒｍ＝２のツリーにおいて、図４の式（７）の計算式により、Ｃｓｋｉｐ（０）を計算すると「３」が得られる。この値は、このツリーの第０階層の１つ下の階層（第１階層）の１つのノード以下に存在するノード数（自身のノードを含む）が「３」であることを示す。よって、ルートノードのアドレスを「０」とすると、まず、このルートノードの子ノードとして１番目に参加するノードのアドレスは「０＋１＝１」となる。また、このノード以下に存在するノード数は「３」なので、このルートノードの子ノードとして２番目に参加するノードのアドレスは「１＋３＝４」となる。
【００６０】
同様に、Ｃｓｋｉｐ（１）を計算すると「１」が得られる。よって、アドレス「１」のノードの子ノードとして、１番目に参加するノードのアドレスは「１＋１＝２」となる。また、このノード以下に存在するノード数は「１」（つまり自分自身のみ）なので、２番目に参加するノードのアドレスは「２＋１＝３」となる。また、同様にアドレス「４」のノードの子ノードとして１番目に参加するノードのアドレスは「４＋１＝５」となる。また、このノード以下に存在するノード数は「１」（つまり自分自身のみ）なので、子ノードとして２番目に参加するノードのアドレスは「５＋１＝６」となる。
【００６１】
次に、図５（ｂ）を用いて、ツリーの階層ごとに子ノード数が異なる場合のアドレスの割り当ての具体例を説明する。最大ツリー階層数Ｌｍ＝３、最大子ノード数Ｒｍ０＝３、Ｒｍ１＝２、Ｒｍ２＝３、Ｒｍ３＝０のツリーにおいて、図４の式（８）の計算式により、Ｃｓｋｉｐ（０）を計算すると「９」が得られる。よって、ルートノードのアドレスを「７」とすると、まず、このルートノードに１番目に参加するノードのアドレスは「７＋１＝８」となる。また、このノード以下に存在するノード数は「９」なので、このルートノードの子ノードとして２番目に参加するノードのアドレスは「８＋９＝１７」となり、３番目に参加するノードのアドレスは「１７＋９＝２６」となる。
【００６２】
同様に、Ｃｓｋｉｐ（１）を計算すると「４」が計算される。よって、アドレス「８」のノードの子ノードとして１番目に参加するノードのアドレスは「８＋１＝９」となる。また、このノード以下に存在するノード数は「４」なので、アドレス「８」のノードの子ノードとして２番目に参加するノードのアドレスは「９＋４＝１３」となる。また、同様にアドレス「１７」のノードの子ノードとして１番目に参加するノードのアドレスは「１７＋１＝１８」となる。このような計算を、このサービスＩＤ「７」のツリーの第３層まで繰り返すと、図５（ｂ）に示すようなアドレスの割り当てが行われる。
【００６３】
図３の割り当てアドレス算出部１２７は、各エリア番号の計算も、前記したＣｓｋｉｐ（ｄ）を用いた方法と同様に行う。つまり、論理ネットワークにおける第Ａａｒｅａ＿ｄ＋１階層におけるｍ番目に参加するエリアのエリア番号Ａａｒｅａは、以下の式（１０）により計算される。
【００６４】
Ａａｒｅａ＝Ａａｒｅａ＿ｐａｒｅｎｔ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）×（ｍ−１）＋１…式（１０）
但し、
Ａａｒｅａ＿ｄ＝Ａａｒｅａ＿Ｌｍの場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝０
Ａａｒｅａ＿ｄ≦Ａａｒｅａ＿Ｌｍ−１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ＋１）×Ａａｒｅａ＿Ｒｍｄ＋１）＋１
Ａａｒｅａ＿ｐａｒｅｎｔ：当該論理ネットワークにおける当該エリアの親エリアのエリア番号
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）：当該論理ネットワークの第Ａａｒｅａ＿ｄ＋１階層の１つのエリア以下に存在する子エリア数
Ａａｒｅａ＿ｄ：当該論理ネットワークにおける自エリアの属する階層
Ａａｒｅａ＿Ｌｍ：当該論理ネットワークの最大エリア階層数
Ａａｒｅａ＿Ｒｍｄ：当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数
【００６５】
つまり、割り当てアドレス算出部１２７は、前記したｄに代えて、Ａａｒｅａ＿ｄ（当該論理ネットワークにおける自エリアの属する階層）を用い、また、最大ツリー階層数Ｌｍに代えて、Ａａｒｅａ＿Ｌｍ（当該論理ネットワークの最大エリア階層数）を用い、最大子ノード数Ｒｍｄに代えて、Ａａｒｅａ＿Ｒｍｄ（当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数）を用いることで各エリア番号を計算できる。
【００６６】
次に、図６を用いて、図３のエリア内テーブル１３２、エリア構造テーブル１３３およびエリア境界ノード情報テーブル１３４を説明する。なお、これらのテーブルは、事前に手動で設定してもよいし、ノード情報を管理するサーバから取得した情報をもとに設定してもよいし、ノード間で制御情報を交換することにより設定してもよい。
【００６７】
図６に示すように、エリア内テーブル１３２は、エリア内のノード間のパケットのルーチングに用いられる情報である。このエリア内テーブル１３２は、所属情報、構成情報および隣接エントリ情報を備える。所属情報は、自身のノードの属するエリア（自エリア）における、自身のノードのアドレス（Ｍｙ ａｄｄｒ）およびそのエリアにおける自身のノードの階層（Ｍｙ Ｄｅｐｔｈ）を示した情報である。構成情報は、自エリアにおけるルートノードのアドレス（ｒｏｏｔ ａｄｄｒ）、最大ツリー階層数Ｌｍ、最大子ノード数Ｒｍ（またはＲｍｄ）を示した情報である。隣接エントリ情報は、自身のノードの親ノードのアドレス（Ｐａｒｅｎｔ ａｄｄｒ）および子ノードアドレス（Ｃｈｉｌｄ ａｄｄｒ１，２…，Ｎ)とを示した情報である。エリア内テーブル１３２は、ノードが受信したパケットの宛先アドレスに基づき、ネクストホップを決定するときに参照される。
【００６８】
エリア構造テーブル１３３は、論理ネットワークのエリアのうち、どのエリアにパケットを転送するか判断するときに参照される情報である。このエリア構造テーブル１３３は、エリア所属情報、エリア構成情報および隣接エリア情報を記憶する。エリア所属情報は、論理ネットワークにおける自エリアのアドレス（Ｍｙ Ａｒｅａ）および自エリアの階層（Ｍｙ Ａｒｅａ Ｄｅｐｔｈ）を示した情報である。エリア構成情報は、論理ネットワークにおけるルートエリアのエリア番号（ｒｏｏｔ Ａｒｅａ）、最大エリア階層数Ａａｒｅａ＿Ｌｍ、最大子エリア数Ａａｒｅａ＿Ｒｍｄを示した情報である。隣接エリア情報は、自エリアの親エリアのエリア番号（Ｐａｒｅｎｔ Ａｒｅａ）および子エリアのエリア番号（Ｃｈｉｌｄ Ａｒｅａ１，２，…，Ｎ)とを示した情報である。このエリア構造テーブル１３３は、ノード１０がエリアをまたいでパケットを転送するときに、宛先エリアの方向（ルート方向かリーフ方向か）を決定する際に参照される。
【００６９】
エリア境界ノード情報テーブル１３４は、自エリアに隣接する外部エリアごとに、その外部エリアと接続するエリア境界ノードを示した情報である。このエリア境界ノード情報テーブル１３４は、ノード１０がエリアをまたいでパケットを転送するときに、自エリア内のどのノード（エリア境界ノード）にパケットを転送すればよいかを決定するときに参照される。なお、このエリア境界ノード情報テーブル１３４は、エリア境界ノードとなるノード１０がエリア境界ノードであることを示すフラグを付したパケットを自エリア内にフラッディングしたものを、受信することにより設定してもよい。
【００７０】
図６に例示したエリア内テーブル１３２によれば、例えば、図７に示すようなエリア内の構成が分かる。つまり、エリアにおける自身のノードのアドレスは「Ａ」であり、このノードの自エリア内の階層は「１」、ルートノードのアドレスは「Ａ１」であり、最大ツリー階層数Ｌｍ＝２、最大子ノード数Ｒｍ０＝３である。自身のノードの親アドレスは「Ａ１」であり、子ノードのアドレスは「Ａ２」…「ＡＮ」であることが分かる。
【００７１】
さらに、エリア構造テーブル１３３によれば、図７に示すように、自身のノードの属するエリアは「Ａａｒｅａ」であり、エリアの階層は「Ａａｒｅａ＿ｄ」であり、ルートエリアは「Ａａｒｅａ＿ｐａｒｅｎｔ」であることが分かる。また、自身のノードの属するエリアの親エリアは「Ａａｒｅａ＿ｐａｒｅｎｔ」であり、子エリアは「Ａａｒｅａ＿ｃｈｉｌｄ １」、…、「Ａａｒｅａ＿ｃｈｉｌｄ Ｎ」であることが分かる。さらに、エリア境界ノード情報テーブル１３４から、隣接エリアは、「Ａａｒｅａ＿ｐａｒｅｎｔ」、「Ａａｒｅａ＿ｃｈｉｌｄ １」…「Ａａｒｅａ＿ｃｈｉｌｄ Ｎ」であり、それぞれのエリアに接続するエリア境界ノードは「Ａｄｄｒ Ａ１」、「Ａｄｄｒ Ａ２」、…、「Ａｄｄｒ ＡＮ」であることが分かる。
【００７２】
＜転送手順＞
次に、図８を用いて、ノード１０のパケット転送手順を説明する。なお、各ノード１０はトンネル処理部１２１により、各サービスの論理ネットワークにおいて隣接するノード１０との間でトンネルを確立し、トンネル情報をルーチングテーブル１３１に書き込んでおくものとする。また、各ノード１０は、自身のノードの属するサービスの論理ネットワーク情報１３０と、自エリア内における自身のノードのパラメータ情報（エリア内テーブル１３２）、自エリアのパラメータ情報（エリア構造テーブル１３３）および自エリアの外部エリアに関する情報（エリア境界ノード情報テーブル１３４）とを記憶部１３に記憶しているものとする。
【００７３】
まず、図３のノード１０のデータ受信部１２０は、ネットワークインタフェース部１１経由でパケットの入力を受け付けると（Ｓ１）、そのパケットの宛先アドレスを解析する（Ｓ２）。そして、エリア判定部１２２は、論理ネットワーク情報１３０と、パケットの宛先アドレスとを参照して、このパケットの宛先ノードの属するサービスとエリアとを特定する(Ｓ３)。つまり、エリア判定部１２２は、パケットの宛先アドレスから、この宛先アドレスがどの論理ネットワークのものかを特定し、さらに、この宛先アドレスが当該論理ネットワークのどのエリアに属するものかを特定する。
【００７４】
ここで、エリア判定部１２２は、Ｓ１で受信したパケットが、自エリア宛のものであると判定し（Ｓ４のＹｅｓ）、かつ、そのパケットが中継パケットでなければ（Ｓ５のＮｏ）、つまり、自身のノード宛のパケットであれば、そのパケットを自身のノードで受信し（Ｓ６）、処理を終了する。一方、そのパケットが中継パケットであれば（Ｓ５のＹｅｓ）、ネクストエリア決定部１２３は、自身のノードのエリア内でのアドレスＡと、受信したパケットのエリア内でのアドレス、エリア内テーブル１３２に示されるＬｍ（当該エリアのツリーの最大ツリー階層数）、Ｒｍｄ（当該エリアのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数）とを用いて、このパケットの次の転送先であるネクストホップを決定する（Ｓ９）。ここでのネクストホップの決定処理の詳細は後記するが、ネクストホップ決定部１２５が、このパケットのエリア内でのアドレスが自身のノードからみてルート側か、リーフ側かを判断することにより行われる。
【００７５】
そして、トンネル処理部１２１は、トンネル情報を参照して、このネクストホップのノード１０への送信Ｉ／Ｆ（InterFace）とオーバーレイリンクを決定し（Ｓ１０）、パケット転送部１２６は、この決定した送信Ｉ／Ｆとオーバーレイリンクとを用いて、パケットをネクストホップのノード１０へ送信する（Ｓ１１）。
【００７６】
一方、Ｓ４においてエリア判定部１２２が、Ｓ１で受信したパケットが、自エリア宛ではないと判定したとき（Ｓ４のＮｏ）、ネクストエリア決定部１２３は、自エリアのエリア番号Ａａｒｅａと、自エリアの属する階層Ａａｒｅａ＿ｄと、パケットの宛先アドレスに含まれるエリア番号と、エリア構造テーブル１３３に示されるＡａｒｅａ＿Ｌｍと、Ａａｒｅａ＿Ｒｍｄとから、ネクストエリアを決定する（Ｓ７）。つまり、ネクストエリア決定部１２３は、パケットの転送先となるネクストエリアを決定する。ここでのネクストエリアの決定処理の詳細は後記するが、ネクストエリア決定部１２３が、自エリアのエリア番号Ａａｒｅａと、パケットの宛先アドレスに含まれるエリア番号と、エリア構造テーブル１３３に示される、Ａａｒｅａ＿ｄと、Ａａｒｅａ＿Ｌｍと、Ａａｒｅａ＿Ｒｍｄとを参照して、自エリアからみて宛先ノードの属するエリアが、ルート側か、リーフ側かを判断することにより行われる。
【００７７】
ネクストエリア決定部１２３がネクストエリアを決定すると、エリア境界ノード特定部１２４は、エリア境界ノード情報テーブル１３４を参照して、このネクストエリア所属のエリア境界ノードを特定する（Ｓ８）。例えば、ネクストエリアが、エリア境界ノード情報テーブル１３４（図６参照）に示される外部エリアのうち「Ａａｒｅａ＿ｃｈｉｌｄ１」である場合、このエリアに所属するエリア境界ノードとして「Ａｄｄｒ Ａ２」を特定する。そして、ネクストホップ決定部１２５は、このエリア境界ノードに到達するためのネクストホップを決定するため、Ｓ９の処理を実行する。つまり、エリア境界ノード「Ａｄｄｒ Ａ２」を宛先アドレスとして考えたとき、パケットがこのエリア境界ノードに到達するためのネクストホップを決定する。このようにすることで、パケットはエリア境界ノード経由で、ネクストエリアに転送される。
【００７８】
論理ネットワーク内の各ノード１０が以上のような処理を実行することで、パケットはアドレスに設定された宛先エリアに到達し、この宛先エリア内の宛先ノードに到達する。
【００７９】
＜ネクストホップ決定処理＞
ここで、図９を用いて、図８におけるネクストホップの決定処理（Ｓ９）の詳細を説明する。まず、図３のネクストホップ決定部１２５は、割り当てアドレス算出部１２７へ、エリア内テーブル１３２に示される自身のノードの属する階層ｄと、Ｌｍ（自エリアのツリーの最大ツリー階層数）と、Ｒｍｄ（自エリアのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数）とを、割り当てアドレス算出部１２７へ出力し、Ｃｓｋｉｐ（ｄ−１）の計算依頼を行う。これを受けて、割り当てアドレス算出部１２７は、Ｃｓｋｉｐ（ｄ−１）を計算する（Ｓ９１）。このときのＣｓｋｉｐ（ｄ−１）の計算は、図４に示す式（７）または式（８）に基づき行われる。
【００８０】
次に、ネクストホップ決定部１２５は、この割り当てアドレス算出部１２７により計算されたＣｓｋｉｐ（ｄ−１）の値と、自エリアにおける自身のノードのアドレスＡとを用いて、パケットのエリア内での宛先アドレスＤが、以下の式（１１）に示す条件を満たすか否かを判断する（Ｓ９２）。つまり、ネクストホップ決定部１２５は、宛先アドレスＤのノードが、自身のノードからみてリーフ側にあるか、ルート側にあるかを判断する。
【００８１】
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）…式（１１）
【００８２】
ここで、ネクストホップ決定部１２５が、パケットの当該エリア内での宛先アドレスＤは、式（１１）に示す条件を満たすと判断したとき（Ｓ９２のＹｅｓ）、つまり、当該エリア内での宛先アドレスＤのノードが、自身のノードからみてリーフ側にあると判断したとき、図４に示す式（７）または式（８）に基づき、Ｃｓｋｉｐ（ｄ）を計算する（Ｓ９３）。そして、ネクストホップ決定部１２５は、以下の式（１２）により、このパケットの転送先であるネクストホップのノード１０のアドレスＮｅｘｔｈｏｐ ａｄｄｒを求める（Ｓ９４）。なお、Ｆｌｏｏｒ［ ］は、フロア関数であり、ここでは、(Ｄ−（Ａ＋１）)／Ｃｓｋｉｐ（ｄ）で求めた値の小数点以下を切り下げた値とする。
【００８３】
Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａ＋１＋Ｆｌｏｏｒ［(Ｄ−（Ａ＋１）)／Ｃｓｋｉｐ（ｄ）］×Ｃｓｋｉｐ（ｄ）…式（１２）
【００８４】
一方、ネクストホップ判定部１２５は、パケットのエリア内での宛先アドレスＤが、式（１１）に示す条件を満たさないとき（Ｓ９２のＮｏ）、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａｐａｒｅｎｔとする（Ｓ９５）。つまり、ネクストホップ決定部１２５は、宛先アドレスＤが式（１１）を満たさないときは、この宛先アドレスＤのノードは、自身のノードからみてルート側にあると判断できるので、自身のノードの親ノード（Ａｐａｒｅｎｔ）をネクストホップとする。
【００８５】
このようにノード１０は、エリア内における自身のノードのアドレスＡおよび階層ｄ、最大ツリー階層数Ｌｍ、最大子ノード数Ｒｍ（またはＲｍｄ）等を参照することで、パケットの転送先であるネクストホップを知ることができる。
【００８６】
なお、Ｓ９２において、ネクストホップ決定部１２５がパケットのエリア内での宛先アドレスＤは、式（１１）に示す条件を満たすと判断したとき（Ｓ９２のＹｅｓ）、つまり、エリア内での宛先アドレスＤのノードが、自身のノードからみてリーフ側にあると判断した場合であって、自身のノードの子ノード（エリア内テーブル１３２の隣接エントリ情報に示されるＣｈｉｌｄ ａｄｄｒ）が１つであるとき、Ｓ９３およびＳ９４の処理をスキップして、この子ノードをネクストホップノードとして決定するようにしてもよい。
【００８７】
＜ネクストエリア決定処理＞
次に、図１０を用いて、前記した図７におけるネクストエリアの決定処理（Ｓ７）の詳細を説明する。このネクストエリアの決定処理は、ノード１０が、パケットの宛先エリアが自エリアからみてルート側か、リーフ側かを判断することにより行われる。
【００８８】
具体的には、ノード１０が、前記したネクストホップ決定処理に用いた自身のノードのアドレスＡに代えて、Ａａｒｅａを用い、パケットのエリア内での宛先アドレスＤに代えて、このパケットの宛先エリアのエリア番号を用いる。また、自身のノードの属する階層ｄに代えて、Ａａｒｅａ＿ｄ（当該論理ネットワークにおける自エリアの属する階層）を用い、Ｌｍに代えて、Ａａｒｅａ＿Ｌｍ（当該論理ネットワークの最大エリア階層数）を用い、Ｒｍｄに代えて、Ａａｒｅａ＿Ｒｍｄ（当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数）を用いることで計算される。
【００８９】
まず、図３のネクストエリア決定部１２３は、エリア構造テーブル１３３に示されるＡａｒｅａ＿ｄと、Ａａｒｅａ＿Ｌｍと、Ａａｒｅａ＿Ｒｍｄとを、割り当てアドレス算出部１２７へ出力し、自エリアの階層をＡａｒｅａ＿ｄとしたときのＣｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の計算依頼を行う。これを受けて、割り当てアドレス算出部１２７は、エリア構造テーブル１３３に示されるＡａｒｅａ＿ＬｍおよびＡａｒｅａ＿Ｒｍｄ用いて、Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）を計算する（Ｓ９１）。このときのＣｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の計算は、図１１に示す式（１２）または式（１３）に基づき行われる。
【００９０】
なお、この式（１２）および（１３）は、前記した図４の式（７）および式（８）における、階層ｄを、Ａａｒｅａ＿ｄに置き換え、Ｌｍを、Ａａｒｅａ＿Ｌｍに置き換え、Ｒｍｄを、Ａａｒｅａ＿Ｒｍｄに置き換えたものである。
【００９１】
次に、ネクストエリア決定部１２３は、この割り当てアドレス算出部１２７により計算されたＣｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の値と、自身のノードのエリアにおけるアドレスＡａｒｅａとを用いて、宛先エリアのエリア番号が、式（１４）に示す条件を満たすか否かを判断する（Ｓ９２）。つまり、ネクストエリア決定部１２３は、宛先エリアが、自エリアからみてリーフ側か、ルート側かを判断する。
【００９２】
Ａａｒｅａ＜宛先エリアのエリア番号＜Ａａｒｅａ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）…式（１４）
【００９３】
ここで、ネクストエリア決定部１２３が、宛先エリアのエリア番号は、式（１４）に示す条件を満たすと判断したとき（Ｓ７２のＹｅｓ）、つまり、宛先エリアが、自身のノードからみてリーフ側にあると判断したとき、図１１に示す式（１２）または式（１３）に基づき、Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）を計算する（Ｓ７３）。そして、ネクストエリア決定部１２３は、以下の式（１５）により、ネクストエリアのエリア番号を求める（Ｓ７４）。
【００９４】
ネクストエリア＝Ａａｒｅａ＋１＋Ｆｌｏｏｒ［(宛先エリアのエリア番号−（Ａａｒｅａ＋１）)／Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）］×Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）…式（１５）
【００９５】
一方、ネクストエリア決定部１２３は、パケットの宛先エリアのエリア番号が、以下の式（１４）に示す条件を満たさないと判定したき（Ｓ７２のＮｏ）、ネクストエリア＝Ａａｒｅａ＿ｐａｒｅｎｔとする（Ｓ７５）。つまり、ネクストエリア決定部１２３は、宛先エリア番号が式（１４）を満たさないときは、この宛先エリアは、自エリアからみてルート側にあると判断できるので、自エリアの親エリア（エリア構造テーブル１３３に示されるＡａｒｅａ＿ｐａｒｅｎｔ）をネクストエリアとする。
【００９６】
このようにノード１０は、各エリアがツリー型トポロジで構成される場合、そのツリーにおける自エリアのエリア番号およびＡａｒｅａ＿ｄ、Ａａｒｅａ＿Ｌｍ、Ａａｒｅａ＿Ｒｍ（またはＡａｒｅａ＿Ｒｍｄ）を参照することで、入力されたパケットを次に転送すべきエリア（ネクストエリア）を知ることができる。
【００９７】
なお、Ｓ７２において、ネクストエリア決定部１２３は、宛先エリアのエリア番号が、式（１４）に示す条件を満たすと判断したとき（Ｓ７２のＹｅｓ）、つまり、宛先エリアが、自エリアからみてリーフ側にあると判断した場合であって、自エリアの子エリア（エリア構造テーブル１３３の隣接エリア情報におけるＣｈｉｌｄ Ａｒｅａ）が１つのとき、Ｓ７３およびＳ７４の処理をスキップして、この子エリアをネクストエリアとして決定するようにしてもよい。
【００９８】
以上説明したネットワークシステムによれば、論理ネットワークのツリートポロジを複数のエリアに分けて構成するので、そのエリアごとにツリーの最大階層数、子ノード数を設定可能となる。よって、論理ネットワーク内に新規ノードを接続するときの制約を緩和することができる。また、論理ネットワークのエリアごとにツリーの最大階層数、子ノード数を設定可能となるので、ネットワークにおいて確保すべきアドレス数を低減することができる。
【符号の説明】
【００９９】
１ バックボーンネットワーク
２，３ サービスネットワーク
１０ ノード
１１ ネットワークインタフェース部
１２ 処理部
１３ 記憶部
１２０ データ受信部
１２１ トンネル処理部
１２２ エリア判定部
１２３ ネクストエリア決定部
１２４ エリア境界ノード特定部
１２５ ネクストホップ決定部
１２６ パケット転送部
１２７ 割り当てアドレス算出部
１３０ 論理ネットワーク情報
１３１ ルーチングテーブル
１３２ エリア内テーブル
１３３ エリア構造テーブル
１３４ エリア境界ノード情報テーブル
【特許請求の範囲】
【請求項１】
１以上のサービスのパケットを転送するネットワークシステムを、当該サービスのパケットを転送する１以上の論理ネットワークに分け、その論理ネットワークをツリー型トポロジとして構成し、当該論理ネットワークを１以上のサブツリーからなるエリアに分割する場合において、そのエリアにおけるツリーの最大ツリー階層数Ｌｍと、そのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数Ｒｍｄとをもとに、そのエリア内のツリーにおける第ｄ＋１階層におけるｎ番目に参加する子ノードの当該エリア内におけるアドレスＡｎが、以下の式（１）により定義されるノードを備えるネットワークシステムであって、
Ａｎ＝Ａｐａｒｅｎｔ＋Ｃｓｋｉｐ（ｄ）×（ｎ−１）＋１…式（１）
但し、
ｄ＝Ｌｍの場合
Ｃｓｋｉｐ（ｄ）＝０
０≦ｄ≦Ｌｍ−１の場合
Ｃｓｋｉｐ（ｄ）＝（Ｃｓｋｉｐ（ｄ＋１）×Ｒｍｄ＋１）＋１
Ａｐａｒｅｎｔ：当該エリアのツリーにおける自身のノードの親ノードのアドレス
Ｃｓｋｉｐ（ｄ）：当該エリアのツリーの第ｄ＋１階層の１つのノード以下に存在するノード数
ｄ：当該エリアのツリーにおける自身のノードの属する階層
Ｌｍ：当該エリアのツリーの最大ツリー階層数
Ｒｍｄ：当該エリアのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数
当該論理ネットワークにおいて、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍと、その論理ネットワークの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄとをもとに、その論理ネットワークにおける第Ａａｒｅａ＿ｄ＋１階層におけるｍ番目に参加するエリアのエリア番号Ａａｒｅａが、以下の式（２）により定義されることを特徴とするネットワークシステム。
Ａａｒｅａ＝Ａａｒｅａ＿ｐａｒｅｎｔ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）×（ｍ−１）＋１…式（２）
但し、
Ａａｒｅａ＿ｄ＝Ａａｒｅａ＿Ｌｍの場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝０
Ａａｒｅａ＿ｄ≦Ａａｒｅａ＿Ｌｍ−１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ＋１）×Ａａｒｅａ＿Ｒｍｄ＋１）＋１
Ａａｒｅａ＿ｐａｒｅｎｔ：当該論理ネットワークにおける当該エリアの親エリアのアドレス
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）：当該論理ネットワークの第Ａａｒｅａ＿ｄ＋１階層の１つのエリア以下に存在する子エリア数
Ａａｒｅａ＿ｄ：当該論理ネットワークにおける自エリアの属する階層
Ａａｒｅａ＿Ｌｍ：当該論理ネットワークの最大エリア階層数
Ａａｒｅａ＿Ｒｍｄ：当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数
【請求項２】
請求項１に記載のネットワークシステムにおける前記ノードであって、
（１）前記論理ネットワークそれぞれに割り当てられたアドレス空間を示した論理ネットワーク情報と、（２）論理ネットワークにおいて前記自身のノードの属するエリアのエリア番号Ａａｒｅａと、当該論理ネットワークにおいて当該エリアの属する階層Ａａｒｅａ＿ｄと、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍおよび１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄと、当該エリアの親エリアＡａｒｅａ＿ｐａｒｅｎｔおよび子エリアＡａｒｅａ＿ｃｈｉｌｄとを示したエリア構造テーブルと、（３）当該エリアに隣接する隣接エリアごとに、その隣接エリアへ接続するエリア境界ノードを示したエリア境界ノード情報テーブルと、（４）当該エリアにおける自身のノードのアドレスＡ、前記自身のノードの属する階層ｄ、最大ツリー階層数Ｌｍおよび最大子ノード数Ｒｍｄ、前記自身のノードの親ノードのアドレスＡｐａｒｅｎｔおよび子ノードのＡｃｈｉｌｄとを示したエリア内テーブルとを記憶する記憶部と、
当該パケットの宛先ノードの属するエリア番号を含むアドレスが付されたパケットの入出力を司るネットワークインタフェース部と、
前記論理ネットワーク情報と、前記ネットワークインタフェース部経由で入力された前記パケットの宛先アドレスに含まれる宛先ノードの属するエリアのエリア番号を参照して、前記宛先ノードが自身のノードの属するエリアのノードか否かを判断するエリア判定部と、
（Ａ）前記宛先ノードが、前記自身のノードの属するエリアのノードであったとき、前記エリア内テーブルと前記自身のノードのアドレスＡと、前記アドレスに含まれるエリア内でのアドレスＤとを参照して、その宛先ノードに転送する際のネクストホップノードのアドレスＮｅｘｔｈｏｐ ａｄｄｒを、以下の式（３）または式（４）により決定するネクストホップ決定部と、
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）の場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａ＋１＋Ｆｌｏｏｒ［（Ｄ−（Ａ＋１））／Ｃｓｋｉｐ（ｄ）］×Ｃｓｋｉｐ（ｄ）…式（３）
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）ではない場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａｐａｒｅｎｔ…式（４）
前記決定されたアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ前記入力されたパケットを前記ネットワークインタフェース部経由で転送するパケット転送部と、
（Ｂ）前記宛先ノードが、前記自身のノードの属するエリアのノードではなかったとき、その宛先ノードに転送する際のネクストエリアを、前記エリア構造テーブルを参照して、以下の式（５）または式（６）により決定するネクストエリア決定部と、
Ａａｒｅａ＜宛先エリアのエリア番号＜Ａａｒｅａ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の場合、ネクストエリア＝Ａａｒｅａ＋１＋Ｆｌｏｏｒ［（エリア番号−（Ａａｒｅａ＋１））／Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）］×Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）…式（５）
Ａａｒｅａ＿ｄ＜宛先エリアのエリア番号＜Ａａｒｅａ＿ｄ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）ではない場合、ネクストホップエリア＝Ａａｒｅａ＿ｐａｒｅｎｔ…式（６）
前記エリア構造テーブルを参照して、前記決定したネクストエリアへ接続するエリア境界ノードのアドレスを特定するエリア境界ノード特定部とを備え、
前記ネクストホップ決定部は、前記特定したエリア境界ノードのアドレスを宛先アドレスとしたときのネクストホップへのアドレスＮｅｘｔｈｏｐ ａｄｄｒを決定し、
前記パケット転送部は、前記決定したアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ、前記入力されたパケットを転送することを特徴とするノード。
【請求項３】
前記エリア内のツリーのすべての階層で当該階層の子ノード数Ｒｍが等しいとき、
前記式（１）におけるＣｓｋｉｐ（ｄ）は、
Ｒｍ＝１の場合
Ｃｓｋｉｐ（ｄ）＝Ｌｍ−ｄ
Ｒｍ＝１ではない場合
Ｃｓｋｉｐ（ｄ）＝（１−ＲｍＬｍ−ｄ）／（１−Ｒｍ）
とすることを特徴とする請求項２に記載のノード。
【請求項４】
前記論理ネットワーク内のすべてのエリアの階層で当該階層の子エリア数Ａａｒｅａ＿Ｒｍが等しいとき、
前記式（１）におけるＣｓｋｉｐ（Ａａｒｅａ＿ｄ）は、
Ａａｒｅａ＿Ｒｍ＝１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝Ｌｍ−ｄ
Ａａｒｅａ＿Ｒｍ＝１ではない場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（１−Ａａｒｅａ＿ｄＡａｒｅａ＿Ｌｍ−Ａａｒｅａ＿ｄ）／（１−Ａａｒｅａ＿Ｒｍ）
とすることを特徴とする請求項２または請求項３に記載のノード。
【請求項５】
請求項１に記載のネットワークシステムにおける前記ノードによるパケット転送方法であって、
（１）前記論理ネットワークそれぞれに割り当てられたアドレス空間を示した論理ネットワーク情報と、（２）論理ネットワークにおいて前記自身のノードの属するエリアのエリア番号Ａａｒｅａと、当該論理ネットワークにおいて当該エリアの属する階層Ａａｒｅａ＿ｄと、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍおよび１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄと、当該エリアの親エリアＡａｒｅａ＿ｐａｒｅｎｔおよび子エリアＡａｒｅａ＿ｃｈｉｌｄとを示したエリア構造テーブルと、（３）当該エリアに隣接する隣接エリアごとに、その隣接エリアへ接続するエリア境界ノードを示したエリア境界ノード情報テーブルと、（４）当該エリアにおける自身のノードのアドレスＡ、前記自身のノードの属する階層ｄ、最大ツリー階層数Ｌｍおよび最大子ノード数Ｒｍｄ、前記自身のノードの親ノードのアドレスＡｐａｒｅｎｔおよび子ノードのＡｃｈｉｌｄとを示したエリア内テーブルとを記憶する記憶部を備える前記ノードが、
他のノードからのパケットの入力を受け付けるステップと、
前記論理ネットワーク情報と、前記パケットの宛先アドレスに含まれる宛先ノードの属するエリアのエリア番号を参照して、前記宛先ノードが自身のノードの属するエリアのノードか否かを判断する自エリア判定ステップと、
（Ａ）前記自エリア判定ステップにおいて、前記宛先ノードが、前記自身のノードの属するエリアのノードであったとき、前記エリア内テーブルと前記自身のノードのアドレスＡと、前記アドレスに含まれるエリア内でのアドレスＤとを参照して、その宛先ノードに転送する際のネクストホップノードのアドレスＮｅｘｔｈｏｐ ａｄｄｒを、以下の式（３）または式（４）により決定するステップと、
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）の場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａ＋１＋Ｆｌｏｏｒ［（Ｄ−（Ａ＋１））／Ｃｓｋｉｐ（ｄ）］×Ｃｓｋｉｐ（ｄ）…式（３）
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）ではない場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａｐａｒｅｎｔ…式（４）
前記決定されたアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ前記入力されたパケットを転送するステップとを実行し、
（Ｂ）前記自エリア判定ステップにおいて、前記宛先ノードが、前記自身のノードの属するエリアのノードではなかったとき、その宛先ノードに転送する際のネクストエリアを、前記エリア構造テーブルを参照して、以下の式（５）または式（６）により決定するステップと、
Ａａｒｅａ＜宛先エリアのエリア番号＜Ａａｒｅａ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の場合、ネクストエリア＝Ａａｒｅａ＋１＋Ｆｌｏｏｒ［（エリア番号−（Ａａｒｅａ＋１））／Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）］×Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）…式（５）
Ａａｒｅａ＿ｄ＜宛先エリアのエリア番号＜Ａａｒｅａ＿ｄ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）ではない場合、ネクストホップエリア＝Ａａｒｅａ＿ｐａｒｅｎｔ…式（６）
前記エリア構造テーブルを参照して、前記決定したネクストエリアへ接続するエリア境界ノードを特定するステップと、
前記特定したエリア境界ノードのアドレスを宛先アドレスとしたときのネクストホップへのアドレスＮｅｘｔｈｏｐ ａｄｄｒを決定するステップと、
前記決定したアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ前記入力されたパケットを転送するステップとを実行することを特徴とするパケット転送方法。
【請求項６】
請求項５に記載のパケット転送方法を、前記ノードであるコンピュータに実行させるためのプログラム。
【請求項１】
１以上のサービスのパケットを転送するネットワークシステムを、当該サービスのパケットを転送する１以上の論理ネットワークに分け、その論理ネットワークをツリー型トポロジとして構成し、当該論理ネットワークを１以上のサブツリーからなるエリアに分割する場合において、そのエリアにおけるツリーの最大ツリー階層数Ｌｍと、そのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数Ｒｍｄとをもとに、そのエリア内のツリーにおける第ｄ＋１階層におけるｎ番目に参加する子ノードの当該エリア内におけるアドレスＡｎが、以下の式（１）により定義されるノードを備えるネットワークシステムであって、
Ａｎ＝Ａｐａｒｅｎｔ＋Ｃｓｋｉｐ（ｄ）×（ｎ−１）＋１…式（１）
但し、
ｄ＝Ｌｍの場合
Ｃｓｋｉｐ（ｄ）＝０
０≦ｄ≦Ｌｍ−１の場合
Ｃｓｋｉｐ（ｄ）＝（Ｃｓｋｉｐ（ｄ＋１）×Ｒｍｄ＋１）＋１
Ａｐａｒｅｎｔ：当該エリアのツリーにおける自身のノードの親ノードのアドレス
Ｃｓｋｉｐ（ｄ）：当該エリアのツリーの第ｄ＋１階層の１つのノード以下に存在するノード数
ｄ：当該エリアのツリーにおける自身のノードの属する階層
Ｌｍ：当該エリアのツリーの最大ツリー階層数
Ｒｍｄ：当該エリアのツリーの第ｄ階層の１つのノードが保持可能な最大子ノード数
当該論理ネットワークにおいて、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍと、その論理ネットワークの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄとをもとに、その論理ネットワークにおける第Ａａｒｅａ＿ｄ＋１階層におけるｍ番目に参加するエリアのエリア番号Ａａｒｅａが、以下の式（２）により定義されることを特徴とするネットワークシステム。
Ａａｒｅａ＝Ａａｒｅａ＿ｐａｒｅｎｔ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）×（ｍ−１）＋１…式（２）
但し、
Ａａｒｅａ＿ｄ＝Ａａｒｅａ＿Ｌｍの場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝０
Ａａｒｅａ＿ｄ≦Ａａｒｅａ＿Ｌｍ−１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ＋１）×Ａａｒｅａ＿Ｒｍｄ＋１）＋１
Ａａｒｅａ＿ｐａｒｅｎｔ：当該論理ネットワークにおける当該エリアの親エリアのアドレス
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）：当該論理ネットワークの第Ａａｒｅａ＿ｄ＋１階層の１つのエリア以下に存在する子エリア数
Ａａｒｅａ＿ｄ：当該論理ネットワークにおける自エリアの属する階層
Ａａｒｅａ＿Ｌｍ：当該論理ネットワークの最大エリア階層数
Ａａｒｅａ＿Ｒｍｄ：当該論理ネットワークのエリアの第Ａａｒｅａ＿ｄ階層の１つのエリアが保持可能な最大子エリア数
【請求項２】
請求項１に記載のネットワークシステムにおける前記ノードであって、
（１）前記論理ネットワークそれぞれに割り当てられたアドレス空間を示した論理ネットワーク情報と、（２）論理ネットワークにおいて前記自身のノードの属するエリアのエリア番号Ａａｒｅａと、当該論理ネットワークにおいて当該エリアの属する階層Ａａｒｅａ＿ｄと、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍおよび１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄと、当該エリアの親エリアＡａｒｅａ＿ｐａｒｅｎｔおよび子エリアＡａｒｅａ＿ｃｈｉｌｄとを示したエリア構造テーブルと、（３）当該エリアに隣接する隣接エリアごとに、その隣接エリアへ接続するエリア境界ノードを示したエリア境界ノード情報テーブルと、（４）当該エリアにおける自身のノードのアドレスＡ、前記自身のノードの属する階層ｄ、最大ツリー階層数Ｌｍおよび最大子ノード数Ｒｍｄ、前記自身のノードの親ノードのアドレスＡｐａｒｅｎｔおよび子ノードのＡｃｈｉｌｄとを示したエリア内テーブルとを記憶する記憶部と、
当該パケットの宛先ノードの属するエリア番号を含むアドレスが付されたパケットの入出力を司るネットワークインタフェース部と、
前記論理ネットワーク情報と、前記ネットワークインタフェース部経由で入力された前記パケットの宛先アドレスに含まれる宛先ノードの属するエリアのエリア番号を参照して、前記宛先ノードが自身のノードの属するエリアのノードか否かを判断するエリア判定部と、
（Ａ）前記宛先ノードが、前記自身のノードの属するエリアのノードであったとき、前記エリア内テーブルと前記自身のノードのアドレスＡと、前記アドレスに含まれるエリア内でのアドレスＤとを参照して、その宛先ノードに転送する際のネクストホップノードのアドレスＮｅｘｔｈｏｐ ａｄｄｒを、以下の式（３）または式（４）により決定するネクストホップ決定部と、
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）の場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａ＋１＋Ｆｌｏｏｒ［（Ｄ−（Ａ＋１））／Ｃｓｋｉｐ（ｄ）］×Ｃｓｋｉｐ（ｄ）…式（３）
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）ではない場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａｐａｒｅｎｔ…式（４）
前記決定されたアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ前記入力されたパケットを前記ネットワークインタフェース部経由で転送するパケット転送部と、
（Ｂ）前記宛先ノードが、前記自身のノードの属するエリアのノードではなかったとき、その宛先ノードに転送する際のネクストエリアを、前記エリア構造テーブルを参照して、以下の式（５）または式（６）により決定するネクストエリア決定部と、
Ａａｒｅａ＜宛先エリアのエリア番号＜Ａａｒｅａ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の場合、ネクストエリア＝Ａａｒｅａ＋１＋Ｆｌｏｏｒ［（エリア番号−（Ａａｒｅａ＋１））／Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）］×Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）…式（５）
Ａａｒｅａ＿ｄ＜宛先エリアのエリア番号＜Ａａｒｅａ＿ｄ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）ではない場合、ネクストホップエリア＝Ａａｒｅａ＿ｐａｒｅｎｔ…式（６）
前記エリア構造テーブルを参照して、前記決定したネクストエリアへ接続するエリア境界ノードのアドレスを特定するエリア境界ノード特定部とを備え、
前記ネクストホップ決定部は、前記特定したエリア境界ノードのアドレスを宛先アドレスとしたときのネクストホップへのアドレスＮｅｘｔｈｏｐ ａｄｄｒを決定し、
前記パケット転送部は、前記決定したアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ、前記入力されたパケットを転送することを特徴とするノード。
【請求項３】
前記エリア内のツリーのすべての階層で当該階層の子ノード数Ｒｍが等しいとき、
前記式（１）におけるＣｓｋｉｐ（ｄ）は、
Ｒｍ＝１の場合
Ｃｓｋｉｐ（ｄ）＝Ｌｍ−ｄ
Ｒｍ＝１ではない場合
Ｃｓｋｉｐ（ｄ）＝（１−ＲｍＬｍ−ｄ）／（１−Ｒｍ）
とすることを特徴とする請求項２に記載のノード。
【請求項４】
前記論理ネットワーク内のすべてのエリアの階層で当該階層の子エリア数Ａａｒｅａ＿Ｒｍが等しいとき、
前記式（１）におけるＣｓｋｉｐ（Ａａｒｅａ＿ｄ）は、
Ａａｒｅａ＿Ｒｍ＝１の場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝Ｌｍ−ｄ
Ａａｒｅａ＿Ｒｍ＝１ではない場合
Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）＝（１−Ａａｒｅａ＿ｄＡａｒｅａ＿Ｌｍ−Ａａｒｅａ＿ｄ）／（１−Ａａｒｅａ＿Ｒｍ）
とすることを特徴とする請求項２または請求項３に記載のノード。
【請求項５】
請求項１に記載のネットワークシステムにおける前記ノードによるパケット転送方法であって、
（１）前記論理ネットワークそれぞれに割り当てられたアドレス空間を示した論理ネットワーク情報と、（２）論理ネットワークにおいて前記自身のノードの属するエリアのエリア番号Ａａｒｅａと、当該論理ネットワークにおいて当該エリアの属する階層Ａａｒｅａ＿ｄと、当該論理ネットワークにおける最大エリア階層数Ａｒｅａ＿Ｌｍおよび１つのエリアが保持可能な最大子エリア数Ａａｒｅａ＿Ｒｍｄと、当該エリアの親エリアＡａｒｅａ＿ｐａｒｅｎｔおよび子エリアＡａｒｅａ＿ｃｈｉｌｄとを示したエリア構造テーブルと、（３）当該エリアに隣接する隣接エリアごとに、その隣接エリアへ接続するエリア境界ノードを示したエリア境界ノード情報テーブルと、（４）当該エリアにおける自身のノードのアドレスＡ、前記自身のノードの属する階層ｄ、最大ツリー階層数Ｌｍおよび最大子ノード数Ｒｍｄ、前記自身のノードの親ノードのアドレスＡｐａｒｅｎｔおよび子ノードのＡｃｈｉｌｄとを示したエリア内テーブルとを記憶する記憶部を備える前記ノードが、
他のノードからのパケットの入力を受け付けるステップと、
前記論理ネットワーク情報と、前記パケットの宛先アドレスに含まれる宛先ノードの属するエリアのエリア番号を参照して、前記宛先ノードが自身のノードの属するエリアのノードか否かを判断する自エリア判定ステップと、
（Ａ）前記自エリア判定ステップにおいて、前記宛先ノードが、前記自身のノードの属するエリアのノードであったとき、前記エリア内テーブルと前記自身のノードのアドレスＡと、前記アドレスに含まれるエリア内でのアドレスＤとを参照して、その宛先ノードに転送する際のネクストホップノードのアドレスＮｅｘｔｈｏｐ ａｄｄｒを、以下の式（３）または式（４）により決定するステップと、
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）の場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａ＋１＋Ｆｌｏｏｒ［（Ｄ−（Ａ＋１））／Ｃｓｋｉｐ（ｄ）］×Ｃｓｋｉｐ（ｄ）…式（３）
Ａ＜Ｄ＜Ａ＋Ｃｓｋｉｐ（ｄ−１）ではない場合、Ｎｅｘｔｈｏｐ ａｄｄｒ＝Ａｐａｒｅｎｔ…式（４）
前記決定されたアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ前記入力されたパケットを転送するステップとを実行し、
（Ｂ）前記自エリア判定ステップにおいて、前記宛先ノードが、前記自身のノードの属するエリアのノードではなかったとき、その宛先ノードに転送する際のネクストエリアを、前記エリア構造テーブルを参照して、以下の式（５）または式（６）により決定するステップと、
Ａａｒｅａ＜宛先エリアのエリア番号＜Ａａｒｅａ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）の場合、ネクストエリア＝Ａａｒｅａ＋１＋Ｆｌｏｏｒ［（エリア番号−（Ａａｒｅａ＋１））／Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）］×Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ）…式（５）
Ａａｒｅａ＿ｄ＜宛先エリアのエリア番号＜Ａａｒｅａ＿ｄ＋Ｃｓｋｉｐ（Ａａｒｅａ＿ｄ−１）ではない場合、ネクストホップエリア＝Ａａｒｅａ＿ｐａｒｅｎｔ…式（６）
前記エリア構造テーブルを参照して、前記決定したネクストエリアへ接続するエリア境界ノードを特定するステップと、
前記特定したエリア境界ノードのアドレスを宛先アドレスとしたときのネクストホップへのアドレスＮｅｘｔｈｏｐ ａｄｄｒを決定するステップと、
前記決定したアドレスＮｅｘｔｈｏｐ ａｄｄｒを持つノードへ前記入力されたパケットを転送するステップとを実行することを特徴とするパケット転送方法。
【請求項６】
請求項５に記載のパケット転送方法を、前記ノードであるコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１１−４３６０（Ｐ２０１１−４３６０Ａ）
【公開日】平成２３年１月６日（２０１１．１．６）
【国際特許分類】
【出願番号】特願２００９−１４８０２４（Ｐ２００９−１４８０２４）
【出願日】平成２１年６月２２日（２００９．６．２２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年１月６日（２０１１．１．６）
【国際特許分類】
【出願日】平成２１年６月２２日（２００９．６．２２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]