(57)【要約】【課題】  あるネットワークに接続されたネットワーク接続装置に対して適切かつ自動的にネットワーク識別情報を配布する。【解決手段】  複数のネットワークを互いに接続するネットワーク接続装置が、下流側のネットワークに接続された下流側ネットワーク接続装置からネットワーク識別情報の割当要求を受信し、前記割当要求に基づき前記下流側ネットワーク接続装置に対して前記ネットワーク識別情報を割り当て、割り当てられたネットワーク識別情報を前記下流側ネットワーク接続装置に通知し、割り当てるべきネットワーク識別情報が不足するか否かを判断し、不足する場合は、上流側のネットワークに接続された上流側ネットワーク接続装置に対してネットワーク識別情報の割当要求を送出して、前記上流側ネットワーク接続装置から前記割当要求に基づいたネットワーク識別情報を取得する。【選択図】  図１
2006020153.tif 000002
【特許請求の範囲】
【請求項１】
複数のネットワークを互いに接続するネットワーク接続装置であって、
下流側のネットワークに接続された下流側ネットワーク接続装置からネットワーク識別情報の割当要求を受信する受信部と、
前記割当要求に基づき前記下流側ネットワーク接続装置に対して前記ネットワーク識別情報を割り当てる割当部と、
前記割当部によって割り当てられたネットワーク識別情報を前記下流側ネットワーク接続装置に通知する通知部と、
割り当てるべきネットワーク識別情報が不足するか否かを判断する判断部と、
前記判断部が不足すると判断した場合は、上流側のネットワークに接続された上流側ネットワーク接続装置に対してネットワーク識別情報の割当要求を送出して、前記上流側ネットワーク接続装置から前記割当要求に基づいたネットワーク識別情報を取得する取得部と、
を備えたことを特徴とするネットワーク接続装置。
【請求項２】
前記受信部は、前記ネットワーク識別情報が割り当てられた前記下流側ネットワーク接続装置から、前記割り当てられたネットワーク識別情報に連続するネットワーク識別情報の割当てをさらに要求する拡張要求を受信し、
前記割当部は、前記受信部によって前記拡張要求が受信された場合は、前記連続するネットワーク識別情報を割り当て可能か否かを判断し、可能である場合は前記連続するネットワーク識別情報を前記下流側ネットワーク接続装置に対して割り当て、
前記通知部は、割り当てられた前記連続するネットワーク識別情報を前記下流側ネットワーク接続装置に通知する、
ことを特徴とする請求項１に記載のネットワーク接続装置。
【請求項３】
前記割当部は、前記連続するネットワーク識別情報を割り当て可能でない場合は、非連続のネットワーク識別情報を割り当て可能か否かを判断し、可能である場合は前記非連続のネットワーク識別情報を前記下流側ネットワーク接続装置に対して割り当て、
前記通知部は、割り当てられた前記非連続のネットワーク識別情報を前記下流側ネットワーク接続装置に通知する、
ことを特徴とする請求項２に記載のネットワーク接続装置。
【請求項４】
前記割当部は、前記非連続のネットワーク識別情報を割り当て可能である場合は、その旨を前記下流側ネットワーク接続装置に対して通知し、前記下流側ネットワーク接続装置から前記非連続のネットワーク識別情報の割当てを受ける旨の通知を受け取った場合は、前記下流側ネットワーク接続装置に対して前記非連続のネットワーク識別情報を割り当てることを特徴とする請求項３に記載のネットワーク接続装置。
【請求項５】
前記割当部は、２つのネットワーク識別情報のビット数が同一であり、最下位ビットがそれぞれ異なり、最下位ビット以外のビットが全て同一である場合は、これら２つのネットワーク識別情報は連続であると判断することを特徴とする請求項２乃至４のいずれかに記載のネットワーク接続装置。
【請求項６】
前記判断部は、未割当てのネットワーク識別情報の大きさが事前に設定された閾値による基準に達した場合は、前記割り当てるべきネットワーク識別情報が不足すると判断することを特徴とする請求項１乃至５のいずれかに記載のネットワーク接続装置。
【請求項７】
前記判断部は、前記割当要求に示されるネットワーク識別情報の大きさが、未割当てのネットワーク識別情報の大きさよりも大きい場合は、前記割り当てるべきネットワーク識別情報が不足すると判断することを特徴とする請求項１乃至５のいずれかに記載のネットワーク接続装置。
【請求項８】
前記取得部は、取得済みの前記ネットワーク識別情報を包含するネットワーク識別情報の割当てを要求することを特徴とする請求項１乃至７のいずれかに記載のネットワーク接続装置。
【請求項９】
複数のネットワークを互いに接続するネットワーク接続装置で実行するネットワーク識別情報配布プログラムであって、
下流側のネットワークに接続された下流側ネットワーク接続装置からネットワーク識別情報の割当要求を受信する受信ステップと、
前記割当要求に基づき前記下流側ネットワーク接続装置に対して前記ネットワーク識別情報を割り当てる割当ステップと、
前記割当ステップによって割り当てられたネットワーク識別情報を前記下流側ネットワーク接続装置に通知する通知ステップと、
割り当てるべきネットワーク識別情報が不足するか否かを判断する判断ステップと、
前記判断ステップによって不足すると判断された場合は、上流側のネットワークに接続された上流側ネットワーク接続装置に対してネットワーク識別情報の割当要求を送出して、前記上流側ネットワーク接続装置から前記割当要求に基づいたネットワーク識別情報を取得する取得ステップと、
を備えたことを特徴とするネットワーク識別情報配布プログラム。
【請求項１０】
前記ネットワーク識別情報が割り当てられた前記下流側ネットワーク接続装置から、前記割り当てられたネットワーク識別情報に連続するネットワーク識別情報の割当てをさらに要求する拡張要求を受信する受信ステップと、
前記連続するネットワーク識別情報を割り当て可能か否かを判断し、可能である場合は前記連続するネットワーク識別情報を前記下流側ネットワーク接続装置に対して割り当てる追加割当ステップと、
割り当てられた前記連続するネットワーク識別情報を前記下流側ネットワーク接続装置に通知する追加通知ステップと、
をさらに備えたことを特徴とする請求項９に記載のネットワーク識別情報配布プログラム。
【請求項１１】
前記追加割当ステップは、前記連続するネットワーク識別情報を割り当て可能でない場合は、非連続のネットワーク識別情報を割り当て可能か否かを判断し、可能である場合は前記非連続のネットワーク識別情報を前記下流側ネットワーク接続装置に対して割り当て、
前記追加通知ステップは、割り当てられた前記非連続のネットワーク識別情報を前記下流側ネットワーク接続装置に通知する、
ことを特徴とする請求項１０に記載のネットワーク識別情報配布プログラム。
【請求項１２】
前記追加割当ステップは、前記非連続のネットワーク識別情報を割り当て可能である場合は、その旨を前記下流側ネットワーク接続装置に対して通知し、前記下流側ネットワーク接続装置から前記非連続のネットワーク識別情報の割当てを受ける旨の通知を受け取った場合は、前記下流側ネットワーク接続装置に対して前記非連続のネットワーク識別情報を割り当てることを特徴とする請求項１１に記載のネットワーク識別情報配布プログラム。
【請求項１３】
前記追加割当ステップは、２つのネットワーク識別情報のビット数が同一であり、最下位ビットがそれぞれ異なり、最下位ビット以外のビットが全て同一である場合は、これら２つのネットワーク識別情報は連続であると判断することを特徴とする請求項１０乃至１２のいずれかに記載のネットワーク識別情報配布プログラム。
【請求項１４】
前記判断ステップは、未割当てのネットワーク識別情報の大きさが事前に設定された閾値による基準に達した場合は、前記割り当てるべきネットワーク識別情報が不足すると判断することを特徴とする請求項９乃至１３のいずれかに記載のネットワーク識別情報配布プログラム。
【請求項１５】
前記判断ステップは、前記割当要求に示されるネットワーク識別情報の大きさが、未割当てのネットワーク識別情報の大きさよりも大きい場合は、前記割り当てるべきネットワーク識別情報が不足すると判断することを特徴とする請求項９乃至１３のいずれかに記載のネットワーク識別情報配布プログラム。
【請求項１６】
前記取得ステップは、取得済みの前記ネットワーク識別情報を包含するネットワーク識別情報の割当てを要求することを特徴とする請求項９乃至１５のいずれかに記載のネットワーク識別情報配布プログラム。
【請求項１７】
複数のネットワークを互いに接続するネットワーク接続装置で実行するネットワーク識別情報配布方法であって、
下流側のネットワークに接続された下流側ネットワーク接続装置からネットワーク識別情報の割当要求を受信する受信ステップと、
前記割当要求に基づき前記下流側ネットワーク接続装置に対して前記ネットワーク識別情報を割り当てる割当ステップと、
前記割当ステップによって割り当てられたネットワーク識別情報を前記下流側ネットワーク接続装置に通知する通知ステップと、
割り当てるべきネットトワーク識別情報が不足するか否かを判断する判断ステップと、
前記判断ステップによって不足すると判断された場合は、上流側のネットワークに接続された上流側ネットワーク接続装置に対してネットワーク識別情報の割当要求を送出して、前記上流側ネットワーク接続装置から前記割当要求に基づいたネットワーク識別情報を取得する取得ステップと、
を備えたことを特徴とするネットワーク識別情報配布方法。
【請求項１８】
前記ネットワーク識別情報が割り当てられた前記下流側ネットワーク接続装置から、前記割り当てられたネットワーク識別情報に連続するネットワーク識別情報の割当てをさらに要求する拡張要求を受信する受信ステップと、
前記連続するネットワーク識別情報を割り当て可能か否かを判断し、可能である場合は前記連続するネットワーク識別情報を前記下流側ネットワーク接続装置に対して割り当てる追加割当ステップと、
割り当てられた前記連続するネットワーク識別情報を前記下流側ネットワーク接続装置に通知する追加通知ステップと、
をさらに備えたことを特徴とする請求項１７に記載のネットワーク識別情報配布方法。
【請求項１９】
前記取得ステップは、取得済みの前記ネットワーク識別情報を包含するネットワーク識別情報の割当てを要求することを特徴とする請求項１７又は１８に記載のネットワーク識別情報配布方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク接続装置、ネットワーク識別情報配布プログラム及びネットワーク識別情報配布方法に関する。
【背景技術】
【０００２】
複数のネットワークを接続してネットワーク間通信を実現するためには、接続する複数のネットワークにネットワーク識別情報を適切に割り当て、且つ複数のネットワークを接続するネットワーク接続装置に対して、接続情報を適切に設定する必要がある。例えばIPv6を使用するネットワークでは、ネットワーク識別情報はプレフィックス、ネットワーク接続装置はルータと呼ばれ、ルータにプレフィックスを設定し、各ルータのプレフィックス情報を他のルータに手動で設定したり、各ルータが経路制御プロトコルを利用して互いのプレフィックス情報を交換したりする必要がある。
【０００３】
ところで、IPv6ではプレフィックス・デリゲーション（Prefix Delegation）を用いるとプレフィックスを自動的に配布することができる。しかし、現在有力とされているDHCPv6を利用する方式では利用可能なネットワーク構成に制限がある。現在の方式では、１つのセグメントに接続するDHCPサーバとクライアント間でのプレフィックス配布、またはDHCPリレーエージェントを介した、異なるセグメント間でのプレフィックス配布のみ可能である。この方法ではサイト（全セグメント）を管理する１つのサーバが全情報を管理し、セグメント間には適切にリレーエージェントが設置されている必要がある。このため、互いに独立に多段接続した機器間ではプレフィックスを再帰的に配布できない。
【０００４】
この問題に対して、非特許文献１では階層プレフィックス・デリゲーションが提案されている。この方式はDHCPv6方式とは互換性が無いが、この方式を採用する事で、多段接続したノード間でプレフィックス・デリゲーションを実現する事ができる。しかしながら、この提案では使用すべきメッセージについては述べられているが、プレフィックスをどのように管理するかが述べられておらず、その方式は実装に依存する。また、この方式では、要求された個々のプレフィックスは独立して扱われるため、サイト内でプレフィックスの断片化を招き経路情報が複雑になる可能性もある。
【非特許文献１】"Hierarchical Prefix Delegation Protocol for Internet Protocol      Version 6 (IPv6)", Byung-Yeob Kim, Kyeong-Jin Lee,      Jung-Soo Park, Hyoung-Jun Kim, Feb 2004,      internet-draft, draft-bykim-ipv6-hpd-01.txt
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、あるネットワークに接続されたネットワーク接続装置に対して適切かつ自動的にネットワーク識別情報の配布できるネットワーク接続装置、ネットワーク識別情報配布方法及びネットワーク識別情報配布プログラムを提供する。
【課題を解決するための手段】
【０００６】
本発明のネットワーク接続装置は、複数のネットワークを互いに接続するネットワーク接続装置であって、下流側のネットワークに接続された下流側ネットワーク接続装置からネットワーク識別情報の割当要求を受信する受信部と、前記割当要求に基づき前記下流側ネットワーク接続装置に対して前記ネットワーク識別情報を割り当てる割当部と、前記割当部によって割り当てられたネットワーク識別情報を前記下流側ネットワーク接続装置に通知する通知部と、割り当てるべきネットワーク識別情報が不足するか否かを判断する判断部と、前記判断部が不足すると判断した場合は、上流側のネットワークに接続された上流側ネットワーク接続装置に対してネットワーク識別情報の割当要求を送出して、前記上流側ネットワーク接続装置から前記割当要求に基づいたネットワーク識別情報を取得する取得部と、を備えたことを特徴とする。
【０００７】
本発明のネットワーク識別情報配布プログラムは、複数のネットワークを互いに接続するネットワーク接続装置で実行するネットワーク識別情報配布プログラムであって、下流側のネットワークに接続された下流側ネットワーク接続装置からネットワーク識別情報の割当要求を受信する受信ステップと、前記割当要求に基づき前記下流側ネットワーク接続装置に対して前記ネットワーク識別情報を割り当てる割当ステップと、前記割当ステップによって割り当てられたネットワーク識別情報を前記下流側ネットワーク接続装置に通知する通知ステップと、割り当てるべきネットワーク識別情報が不足するか否かを判断する判断ステップと、前記判断ステップによって不足すると判断された場合は、上流側のネットワークに接続された上流側ネットワーク接続装置に対してネットワーク識別情報の割当要求を送出して、前記上流側ネットワーク接続装置から前記割当要求に基づいたネットワーク識別情報を取得する取得ステップと、を備えたことを特徴とする。
【０００８】
本発明のネットワーク識別情報配布方法は、複数のネットワークを互いに接続するネットワーク接続装置で実行するネットワーク識別情報配布方法であって、下流側のネットワークに接続された下流側ネットワーク接続装置からネットワーク識別情報の割当要求を受信する受信ステップと、前記割当要求に基づき前記下流側ネットワーク接続装置に対して前記ネットワーク識別情報を割り当てる割当ステップと、前記割当ステップによって割り当てられたネットワーク識別情報を前記下流側ネットワーク接続装置に通知する通知ステップと、割り当てるべきネットトワーク識別情報が不足するか否かを判断する判断ステップと、前記判断ステップによって不足すると判断された場合は、上流側のネットワークに接続された上流側ネットワーク接続装置に対してネットワーク識別情報の割当要求を送出して、前記上流側ネットワーク接続装置から前記割当要求に基づいたネットワーク識別情報を取得する取得ステップと、を備えたことを特徴とする。
【発明の効果】
【０００９】
本発明により、あるネットワークに接続されたネットワーク接続装置に対して適切かつ自動的にネットワーク識別情報を配布できる。
【発明を実施するための最良の形態】
【００１０】
以下に示す本発明の実施形態では、IPv6を利用して構成されるネットワークを前提とする。使用する各用語は以下に従う。
【００１１】
ネットワーク識別情報＝プレフィックス
ネットワーク接続装置＝ルータ
ネットワーク識別情報の配布＝プレフィックス・デリゲーション、プレフィックスの委譲
図１は、本発明の第１の実施形態に従ったネットワーク接続装置（ルータ）の構成図である。
【００１２】
図中１０１は、本ルータをネットワークに接続するネットワークインターフェイス部であり、図中１０２は、ネットワークに接続されている他のルータからメッセージ要求（プレフィックス取得要求、プレフィックス拡張要求など）を受信する要求受信部であり、図中１０３は、ネットワークに接続されている他のルータに対し、受信したメッセージ要求に対するメッセージ応答（プレフィックス取得応答、プレフィックス拡張応答など）を送信する応答送信部であり、図中１０４は、要求受信部１０２で受信されたメッセージ要求を処理する要求処理部であり、図中１０５は、本ルータが割り当て可能なプレフィックスを格納したネットワーク識別情報表を記憶したネットワーク識別情報表記憶部であり、図中１０６は、要求に基づいて他のルータに割り当てたプレフィックスを格納した割り当て管理表及び後述する二分木を記憶する割り当て管理表記憶部であり、図中１０７は、割り当て管理表記憶部１０６内の割り当て管理表及び二分木を更新する割り当て管理表更新部である。
【００１３】
図２は本実施形態に係わるネットワークシステムの一形態を示す図である。
【００１４】
図２において、親ルータ２０１は配下における複数のネットワークＮ１〜Ｎ５とそれらを相互に接続するためのルータ２０２〜２０５を外部のＩＳＰ（インターネットサービスプロバイダ）のルータ等に接続する。子ルータ２０２，２０３は親ルータ２０１のネットワークＮ１に接続され、ネットワークＮ２，Ｎ３を配下に置く。同様に子ルータ２０２に対して孫ルータ２０４，２０５が存在し、孫ルータ２０４，２０５はネットワークＮ４，Ｎ５を配下に置く。親ルータ２０１、子ルータ２０２，２０３及び孫ルータ２０４，２０５は、それぞれ図１に示した構成を有するものとする。図中ＩＦ１はルータの上流側のインターフェイス、ＩＦ２はルータの下流側のインターフェイスを表す。
【００１５】
以降の説明を行うにあたり、親ルータ２０１はプレフィックス・デリゲーションや手動設定など何らかの手法で配下のネットワークにて利用可能なIPv6プレフィックスをあらかじめISPから取得しているものとする。このプレフィックスは親ルータ２０１のネットワーク識別情報表に記録される。この状態を図３に示す。また、この際に図４に示すプレフィックス割り当てに関するデータ構造を生成する。これは割り当て管理表の別表現であり、割り当て管理表更新部１０７によって生成される。図４では便宜上二分木を利用しているが、プレフィックスの階層構造を適切に表現できるデータ構造であれば、その形式は問わない。このデータ構造では、各ノードが「プレフィックス／プレフィックス長」に対応し、ノードの親子関係はプレフィックスの包含関係に対応する（子ノードが持つプレフィックスは親ノードが持つプレフィックスに含まれる）。また、各ノードは２つの付随する情報を保持でき、割り当て先のルータを表す「使用中：Ｘ」あるいは割り当て先のルータが存在しない「未使用」と、該ノード以下の全てのプレフィックスに対する割り当てが完了していることを示す「ＦＵＬＬ」とがある。親ルータ２０１は自分が管理しているネットワークN1でIPv6を利用するため、委譲されたプレフィックスから１つを選択し、ネットワークN1で使用する（複数のネットワークに接続されている場合には、その数を確保する）。このプレフィックスを2001:0db8:abcd::/64とすると、図５、図６に示すように二分木及び割り当て管理表が更新される。図６に示すように、割当先アドレスは、自分自身の場合には、空白にしておく。また、図５における「使用中：Ｓ」の“Ｓ”は自ノードを表す記号である。
【００１６】
ここで二分木の構築方法について簡単に説明する。
【００１７】
図２７は、２分木の生成アルゴリズムの一例を説明するフローチャートである。図２８は、本生成アルゴリズムによって生成された二分木の一例を示す。
【００１８】
1.1. まず、入力されたプレフィックスP及びプレフィックス長lに基づきP/lを有するノード（ノードP/l）を根ノードとして生成する（ステップS1、S2）。
【００１９】
ここでは例えばP/l = 2001:0db8:abcd::/48 が入力され、2001:0db8:abcd::/48 を有するノード X1 、すなわち、ノードX1(2001:0db8:abcd::/48)が生成されるとする。
【００２０】
1.2. 生成したノードに「未使用」をマークする（ステップS3）。例えばX1(2001:0db8:abcd::/48,未使用)とする。
【００２１】
1.3. このノードP/lが末端ノードであるか否かを判断する（ステップS4）。末端ノードであるか否かは、プレフィックス長が最小割り当て単位と同じであるか否かで判断する。ここでは最小割り当て単位を51とする。すると48≠ 51であるから、このノードP/l（ノードX1）は末端ノードではない（ステップS4のNO）。
【００２２】
1.4. プレフィックス長lを１増加し本ルーチンを再帰的に呼び出す（ステップS5）。すなわち、準備ルーチン(2001:0db8:abcd:0000::, 49) 呼び出しを行う。
【００２３】
2.1 ノード X2(2001:0db8:abcd:0000::/49) 生成（ステップS1、S2）
2.2 ノード X2(2001:0db8:abcd:0000::/49,未使用)（ステップS3）
2.3 49 ≠51 であるのでノードX2は末端ノードではない（ステップS4のNO）
2.4 準備ルーチン(2001:0db8:abcd:0000::, 50) 呼び出し（ステップS5）
3.1 ノード X3(2001:0db8:abcd:0000::/50) 生成（ステップS1、S2）
3.2 ノード X3(2001:0db8:abcd:0000::/50,未使用)（ステップS3）
3.3 50 ≠51であるのでノードX3は末端ノードではない（ステップS4のNO）
3.4 準備ルーチン(2001:0db8:abcd:0000::, 51) 呼び出し（ステップS5）
4.1 ノード X4(2001:0db8:abcd:0000::/51) 生成（ステップS1、S2）
4.2 ノード X4(2001:0db8:abcd:0000::/51,未使用)（ステップS3）
4.3 51 = 51 であるのでノードX4は末端ノードである（ステップS4のYES）
4.4 結果として ノード X4 を返す（ステップS9）
4.5 準備ルーチン(2001:0db8:abcd:0000::, 51) 終了
3.5 準備ルーチン(2001:0db8:abcd:0000::, 51) の結果 ret（すなわち X4）をノード X3 の左の子とする（ステップS6）。
3.6 準備ルーチン(2001:0db8:abcd:2000::, 51) 呼び出し（ステップS7）
4.1 ノード X5(2001:0db8:abcd:2000::/51) 生成（ステップS1、S2）
4.2 ノード X5(2001:0db8:abcd:2000::/51,未使用)（ステップS3）
4.3 51 = 51 であるのでノードX5は末端ノードである（ステップS4のYES）
4.4 結果として ノード X5 を返す（ステップS9）
4.5 準備ルーチン(2001:0db8:abcd:2000::, 51) 終了
3.7 準備ルーチン(2001:0db8:abcd:2000::, 51) の結果 ret（すなわち X5）をノード X3 の右の子とする（ステップS8）
3.8 結果として ノード X3 を返す（ステップS9）
2.5 準備ルーチン(2001:0db8:abcd:0000::, 50) の結果 ret（すなわち X3）をノード X2 の左の子とする（ステップS6）
2.6 準備ルーチン(2001:0db8:abcd:4000::, 50) 呼び出し（ステップS7）
(中略)
2.7 準備ルーチン(2001:0db8:abcd:4000::, 50) の結果 ret（すなわち X6）をノード X2 の右の子とする（ステップS8）
2.8 結果として ノード X2 を返す（ステップS9）
1.5 準備ルーチン(2001:0db8:abcd:0000::, 49) の結果 ret（すなわち X2）をノード X1 の左の子とする（ステップS6）
1.6 準備ルーチン(2001:0db8:abcd:8000::, 49) 呼び出し（ステップS7）
(中略)
1.7 準備ルーチン(2001:0db8:abcd:8000::, 49) の結果 ret（すなわち X9）をノード X1 の右の子とする（ステップS8）
1.8 結果として ノード X1を返す（ステップS9）
1.9 終了
【００２４】
ここで、親ルータ２０１の二分木及び割り当て管理表が図５及び図６の状態において、図７に示すように、親ルータ２０１のネットワークN1に子ルータ２０２が接続される状況を考える。子ルータ２０２はネットワークN1上でプレフィックス・デリゲーションを実行可能なルータを探し、その結果、親ルータ２０１がプレフィックス・デリゲーションを実行可能であることを知る。子ルータ２０２は親ルータ２０２との間でプレフィックス・デリゲーションを実行し、あるプレフィックスを受け取る。子ルータ２０２はこのプレフィックスを自身が管理するネットワーク識別情報表に書き込む。この状態を図８に示す。本例では、子ルータ２０２は、2001:0db8:abcd::/61 というプレフィックスを委譲されたと仮定する。現時点における親ルータ２０１の割り当て管理表と二分木とを図示したものを、図９，図１０に示す。
【００２５】
ここで図８に示すように、ネットワーク識別情報表に書き込まれたプレフィックスには親ルータ２０１に指定された有効期間が設定されている。有効期間が切れた場合には、要求処理部１０４にプレフィックス無効通知が送られる。このプレフィックス無効通知への対応処理は本発明の範囲を外れているため、説明を省略する。一方、子ルータ２０２は、ネットワーク識別情報表に図８の情報を書き込んだ後に、自ノードが直接接続しているネットワークにおいて使用する自ノード用のプレフィックスを確保する。確保したプレフィックスは通常のIPv6ルータと同様にルータ通知メッセージを通じてネットワーク内に広告可能となる。子ルータ２０２は、自ノード用に割り当てた該プレフィックスを、図１１に示すように、割り当て管理表に自らを割り当て先として記入する。本例では、子ルータ２０２は２つのネットワークＮ１，Ｎ２に接続し、そのうちの１つのネットワークＮ２を管理しているので、割り当て管理表には該ネットワークＮ２に割り当てたプレフィックスを記入する。この時、インターフェイスの欄には該ネットワークN2に接続するインターフェイスIF2を記入し、割り当て先アドレスは親ルータ２０１の場合と同様に空白にしておく。また、親ルータ２０１と同様に、子ルータ２０２は、委譲されたプレフィックスを根ノードとする二分木を構築する。
【００２６】
この状態で、子ルータ２０２の管理するネットワークN2に孫ルータ２０４が接続されたとする（なお、以降の手順は、親ルータ２０１−子ルータ２０２間でも同様に行われているが説明を省略する）。孫ルータ２０４は、子ルータ２０２が親ルータ２０１からプレフィックスを取得した時と同様に、プレフィックス・デリゲーションが実行可能なルータを検索し、結果として子ルータ２０２が実行可能であることを知る。
【００２７】
子ルータ２０２は孫ルータ２０４からプレフィックス取得要求メッセージを受信する。つまり、孫ルータ２０４は子ルータ２０２のネットワークに接続直後であるため、子ルータ２０２はこの時点ではプレフィックス取得要求を受信する。すなわち後述する他のメッセージを受信しない（仮に他のメッセージを受信した場合には、エラーを返せば良い）。このプレフィックス取得要求は、より詳しくは、ネットワークインターフェイス部１０１を介して要求受信部１０２によって受信され、要求処理部１０４に渡される。要求処理部１０４は、ここでは、プレフィックス長64のプレフィックスに対するプレフィックス取得要求を受信していると仮定する。
【００２８】
プレフィックス取得要求を受信した要求処理部１０４は、新規にプレフィックスを割り当てる処理（新規割り当てルーチン）を実行する。
【００２９】
図２９は、新規割り当てルーチンの処理ステップを示したフローチャートである。
【００３０】
プレフィックス取得要求を受信した要求処理部１０４は、まず割り当て管理表記憶部１０６内に二分木が格納されているか否かを判断し、格納さていない場合は（ステップS11のNo）、割り当て管理表更新部１０７に二分木を生成させる（ステップS12）。
【００３１】
要求処理部１０４は、割り当て管理表記憶部１０６内に二分木が格納されている場合は（ステップS11のYes）、
a) 孫ルータ２０４から受信したプレフィックス取得要求メッセージ
b) ネットワーク識別情報表
c) 割り当て管理表
d) （オプション）管理者の設定
に含まれる情報に基づいて、プレフィックスを割り当てるかどうかを決定し、割り当てる場合には、どのようなプレフィックスを割り当てるかを決定する（ステップS13〜S19）。
【００３２】
より詳しくは、要求処理部１０４は、子ルータ２０２の二分木において、幅方向を優先して、「未使用」がマークされたノードを探索する（ステップS13,S14）。この様子を図１３の上段に示す。図１３に示す二分木は子ルータ２０２の割り当て管理表記憶部１０６に格納された二分木である。要求処理部１０４は「未使用」がマークされたノードが存在しない場合は（ステップS15のNo）、割り当てエラーを表すプレフィックス取得応答を応答送信部１０３経由で孫ルータ２０４に返す（ステップS16）。
【００３３】
割り当てエラーは
a) 割り当て可能なプレフィックスが１つも存在しない
b) 十分な長さの割り当て可能なプレフィックスが存在しない
c) 管理者により割り当てが禁止されている
などのエラー原因を詳細に含んでも良い。
【００３４】
一方、要求処理部１０４、「未使用」がマークされたノードが存在する場合は（ステップS15のYes）、そのノードを起点に、深さ方向へ探索を行い、要求されたプレフィックス長以下の長さで最も大きいプレフィックス長を有するノードを探索する（ステップS17〜S19）。ここでは、図１３の上段に示すように、プレフィックス2002:0db8:abcd:8004::/64を有するノードが探索されたとする。
【００３５】
要求処理部１０４は、探索されたプレフィックスならびにプレフィックス長、プレフィックスの有効期間を含んだプレフィックス取得応答メッセージを、応答送信部１０３経由で孫ルータ２０４に送信する（ステップS20,S21）。
【００３６】
子ルータ２０２は孫ルータ２０４にこの応答を返すと共に、割り当て管理表も更新する。この場合には、
a) 割り当てたプレフィックスとプレフィックス長
b) 割り当てた孫ルータ２０４のアドレス
c) 割り当て要求を受信したインターフェイス
d) 有効期間  
を一つのまとまりとして、割り当て管理表に登録する。現時点における子ルータ２０２の割り当て管理表を図１２に示す。登録は要求処理部１０４が割り当て管理表更新部１０７へ上記a)〜d)からなる登録メッセージを送り、割り当て管理表更新部１０７が実行する。
【００３７】
この後、子ルータ２０２は、図１３の下段に示すように、孫ルータ２０４に割り当てたノードを含むパス上に位置するノードに、「使用中：A」のマークを付する（ステップS21〜S28）。図１３においてSは子ルータ２０２を、Aは孫ルータ２０４を表す記号である。但し、割り当てられたノードが一番右の子である場合は、そのノードの親ノードには「FULL」をマークする（ステップS25）（後述する図１４参照）。図２９において、ステップS22,S27は、ステップS17で探索されたノードAと、ステップS19で探索されたノードBとが一致するまで、これらのステップS22,S27で囲まれたステップS23〜S26をループ処理することを意味する。
【００３８】
次に、子ルータ２０２が、孫ルータ２０４からプレフィックス長64のプレフィックスをもう１つ追加することを要求するプレフィックス拡張要求メッセージを受信したと仮定する。このメッセージは、プレフィックス取得要求メッセージと同様に、ネットワークインターフェイス部１０１、要求受信部１０２を経て要求処理部１０４に渡される。プレフィックス拡張要求メッセージを受信した子ルータ２０２は、割り当て拡張ルーチンを実行する。
【００３９】
図３０は、割り当て拡張ルーチンを説明するフローチャートである。
【００４０】
要求処理部１０４は、まず始めに、割り当て管理表を確認し、プレフィックス拡張要求の送信元に対して既に割り当てたプレフィックスが存在するか否かを確認する（ステップS31,S32）。もし、割り当て済のプレフィックスが存在しない場合には（ステップS32のNo）、子ルータ２０２は、エラー（拡張可能なプレフィックスが存在しない）を示すプレフィックス拡張応答メッセージを応答送信部１０３経由で返す（ステップS33）。
【００４１】
一方、子ルータ２０２は、割り当て済プレフィックスが存在する場合（ステップS32のYes）は、自己が保有する二分木において、「使用中：A」がマークされたノードを、幅方向を優先して探索する（ステップS35）。この様子を図１４の上段に示す。子ルータ２０２は、「使用中：A」がマークされたノードが存在しなければ（ステップS36のNo）、エラーを返し（ステップS37）、存在した場合は（ステップＳ36のYes）、そのノードを起点に深さ優先探索を行い、要求されたプレフィックス長以下の長さで最も大きいプレフィックス長を有するノードを探索する（ステップS38、S39）。ここでは、図１４の上段に示すように、プレフィックス2002:0db8:abcd:8005::/64を有するノードが探索されたとする（ステップS40のYes）。
【００４２】
子ルータ２０２は、孫ルータ２０４に拡張後のプレフィックスを含むプレフィックス拡張応答を返すとともに、割り当て管理表も更新する（ステップS41,S42）。この際、子ルータ２０２は、拡張前に割り当てられたプレフィックスに対する有効期間も拡張されたプレフィックスに合わせて変更する（全体が１つの有効期間の元で管理される）。図１５に、孫ルータ２０４のプレフィックスを拡張した後における子ルータ２０２の割り当て管理表を示す。そして、子ルータ２０２は、孫ルータ２０４に割り当てたノードに「使用中：A」をマークし、そのノードが右の子である場合は、その親ノードに「FULL」をマークする（S43〜S49）（図１４の下段参照）。
【００４３】
一方、ステップS39における探索の途中で「FULL」とマークされたノードが途中で見付かったために連続したプレフィックスを割り当てられない場合には（これについては後にさらに詳述する）（ステップS40のNo）、子ルータ２０２は、二分木において全てのプレフィックスを割り当て済みか否かを判断する（ステップS50）。全てのプレフィックスを割り当て済みである場合は（ステップS50のYes）、子ルータ２０２は、割り当て可能なプレフィックスが１つも存在しない旨のエラーを示すプレフィックス拡張応答を返し、プレフィックスの残りがある場合は（ステップS50のNo）、エラー（断片化警告）を示すプレフィックス拡張応答を返す（ステップS52）。このエラー（断片化警告）を示す応答メッセージは、プレフィックスの断片化を受け入れるならばプレフィックスを割り当てられる可能性があることを示すメッセージである（実際に割り当て可能かどうかは分からない）。なお、管理上の設定に基づきプレフィックスの断片化を認めない場合には、エラー（断片化警告）ではなく、上述の割り当て可能なプレフィックスが１つも存在しない旨のエラーを返しても良い。それ以外の理由を含め、子ルータ２０２は、新規割り当て時と同様のエラーメッセージを返すこともできる。
【００４４】
孫ルータ２０４がプレフィックス拡張要求の結果として、エラー（断片化警告）を含むプレフィックス拡張応答を受信した場合、断片化することを受け入れるのであれば、再度プレフィックス取得要求を子ルータ２０２に送信することが出来る。子ルータ２０２は、孫ルータ１からプレフィックス取得要求メッセージを受信した場合は、既割当て済みプレフィックスの存在を考慮することなく（この要求は新規割り当てであるため）、上述した新規割り当てルーチン（図２９参照）に従って新規にプレフィックスが割当て可能かを検討し、応答を返す。孫ルータ２０４は、プレフィックス取得要求に対する応答もエラーだった場合には、割り当てを受けることが出来ないと判断して要求を中止する。なお、一度中止した後、一定時間後に再度要求を送信してもよい。
【００４５】
続いて、子ルータ２０２のネットワークN2に孫ルータ２０５が接続された場合を考える（図２参照）。接続される直前の子ルータ２０２の割り当て管理表は、上述の図１５の状態になっているものとする。孫ルータ２０５は64ビットのプレフィックス長を持つプレフィックスを要求するプレフィックス取得要求を子ルータ２０２に向けて送信する。子ルータ２０２はプレフィックス取得要求を受信すると、その要求に基づいて上述の新規割り当てルーチン（図２９参照）を実行して、孫ルータ２０５にプレフィックスを割り当てる。この例では、子ルータ２０２は、要求されたプレフィックス長64のプレフィックスを孫ルータ２０５に割り当てたと仮定する。子ルータ２０２によるプレフィックスの決定の様子を図１６に、割り当て後の割当て管理表を図１７に示す。図１６においてＢは孫ルータ２０５を示す記号である。
【００４６】
次に子ルータ２０２が、プレフィックス長64のプレフィックスをもう１つ追加することを要求するプレフィックス拡張要求を孫ルータ２０５から受信したと仮定する。子ルータ２０２は、その要求に基づき割り当て拡張ルーチン（図３０参照）を実行する。現時点における子ルータ２０２の二分木及び割り当て管理表が図１６の下段、図１７に示す状態であるため、プレフィックスの拡張は可能である。したがって、子ルータ２０２はプレフィックスを孫ルータ２０５に割り当てる。このときの子ルータ２０２によるプレフィックスの決定の様子を図１８に、割り当て後の割り当て管理表を図１９に示す。
【００４７】
連続して子ルータ２０２が孫ルータ２０５から、プレフィックス長64のプレフィックスをもう１つ追加することを要求するプレフィックス拡張要求を受信したとする。子ルータ２０２は、その要求に基づき上述の割り当て拡張ルーチンを実行する（図３０参照）。現時点における二分木及び割り当て管理表は図１８の下段，図１９に示す状態であるため、探索は失敗する（図３０のステップS40のNo参照）。このときの探索の様子を図２０に示す。しかし、子ルータ２０２はまだ自分が保持する全てのプレフィックスを割り当てたわけではないので（図３０のステップS50のNo参照）、エラー（断片化警告）を含むプレフィックス拡張応答を孫ルータ２０５に返すことができる。本例では、子ルータ２０２は、設定上、断片化が禁止されていないものとすると、子ルータ２０２は前述のように、エラー（断片化警告）を含むプレフィックス拡張応答を孫ルータ２０５に返す（図３０のステップS52参照）。
【００４８】
この応答を受けた孫ルータ２０５は、プレフィックス取得要求を送信することができる。この例では断片化を受け付けるものと仮定すると、孫ルータ２０５はプレフィックス長64のプレフィックスを１つ要求するプレフィックス取得要求を送信する。子ルータ２０２は新規割り当てルーチン（図２９参照）を実行し、適切なプレフィックスを孫ルータ２０５に割り当てる。プレフィックスの決定の様子を図２１の上段に示す。この結果、子ルータ２０２の二分木及び割り当て管理表は図２１の下段，図２２のようになる。
【００４９】
一連のプレフィックス割り当て手順によって割り当て管理表に登録されたレコードは、有効期間を持っている。この有効期間は、割り当て管理表更新部１０７によって定期的に更新される。有効期間が切れた場合、割り当て管理表更新部１０７が割り当て管理表からエントリを削除するとともに、外部（要求処理部１０４など）に通知する。この通知への具体的な対応方法については、本発明の範囲を超えているので説明を省略する。
【００５０】
先の一連の流れが進み、図２３に示すように子ルータ２０２が親ルータ２０１から委譲されたプレフィックスを全て割り当てたと仮定する。この状況で、子ルータ２０２が取る動作としては次の２つがある。
【００５１】
1) 次の要求（取得要求、拡張要求）が来る前に親ルータ２０１に対してプレフィックス拡張要求を送信する
2) 次の要求（取得要求、拡張要求）を待ち、プレフィックスの新規割り当てが発生することが確定した段階で親ルータ２０１に対してプレフィックス拡張要求を送信する
ただし、いずれの場合も、子ルータ２０２が孫ルータから受信した要求メッセージがプレフィックス拡張要求だった場合には、子ルータ２０２は、必ずエラー（断片化警告）を返す。これは、子ルータ２０２がこれから孫ルータに割り当てるプレフィックスと、孫ルータに既割り当て済みのプレフィックスとの連続性が確保されないからである。親ルータ２０１と子ルータ２０２との間でのプレフィックスの連続性は確保できるが、孫ルータまでの連続性は確保されない。なお、この段階で子ルータ２０２が親ルータ２０１に要求するプレフィックス長の決定方法に関しては後述する第２の実施形態で示すように２通りの方法がある。
【００５２】
以下、子ルータ２０２が1)及び2)の方法を取った場合の処理についてそれぞれ説明する。
【００５３】
図３１は、子ルータ２０２が1)の方法を取った場合の処理を説明するフローチャートである。
【００５４】
子ルータ２０２は、未割り当てのプレフィックスが無くなるまで、上述した新規割り当てルーチン（図２９参照）及び割り当て拡張ルーチン（図３０参照）を実行する（ステップS61、S62のYes,S63）。未割り当てのプレフィックスが無くなったら（ステップS62のNo）、子ルータ２０２における割当て管理表更新部１０７から要求処理部１０４にその旨の通知がなされ、この通知を受けた要求処理部１０４は、ネットワーク識別情報表に記載されたプレフィックスの委譲元（親ルータ２０１）にプレフィックス拡張要求を送信する（ステップS64）。
【００５５】
子ルータ２０２は、要求が成功した場合は（ステップS65のYes）、親ルータ２０１から受信したプレフィックスを根ノードとする二分木を生成し、通常通り、新規割り当てルーチン及び割り当て拡張ルーチンを実行する（ステップS66）。但し、このように要求が成功する場合は、後述する第２の実施形態を用いた場合にのみ起こり得る。今まで説明してきた第１の実施形態ではこの要求に対してはエラー（断片化警告）あるいはエラー（割り当て可能なプレフィックスが存在しない）が返される。
【００５６】
子ルータ２０２は、要求が成功しなかった場合で（ステップS65のNo）、親ルータ２０１からエラー（割り当て可能なプレフィックスが存在しない）を受信した場合は（ステップS67のNo）、処理を終了する（ステップS68）。従って、子ルータ２０２は、この後、孫ルータから新規割り当て要求や拡張要求を受信したとしてもエラー（割り当て可能なプレフィックスが存在しない）を返す。
【００５７】
子ルータ２０２は、要求が成功しなかった場合で（ステップS65のYes）、親ルータ２０１からエラー（断片化警告）を受信した場合は（ステップS67のYes）、プレフィックスの断片化を受け入れるか否かを判断する（ステップS69）。子ルータ２０２は、プレフィックスの断片化を受け入れない場合は（ステップS69のNo）、処理を終了する（ステップS70）。従って、子ルータ２０２は、この後、孫ルータから新規割り当て要求や拡張要求を受信したとしてもエラー（割り当て可能なプレフィックスが存在しない）を返す。一方、子ルータ２０２は、プレフィックスの断片化を受け入れる場合は（ステップS69のYes）、親ルータ２０１にプレフィックス取得要求を送信する（ステップS71）。
【００５８】
要求が成功しなかった場合は（ステップS72のNo）子ルータ２０２は処理を終了する（ステップS73）。従って、子ルータ２０２は、この後、孫ルータから新規割り当て要求や拡張要求を受信したとしてもエラー（割り当て可能なプレフィックスが存在しない）を返す。
【００５９】
要求が成功した場合は（ステップS72のYes）、子ルータ２０２は、プレフィックスに余裕ができ、新規割り当てルーチン及び割り当て拡張ルーチンにより、孫ルータからの以降の要求に応えることができる（ステップS74）。子ルータ２０２がプレフィックスに余裕ができた後に孫ルータから受信したプレフィックス拡張要求に関しては、子ルータ２０２は、エラー（断片化警告）を含むプレフィックス拡張応答で答える。これに対応して子ルータ２０２が孫ルータからプレフィックス取得要求を受信した場合には、子ルータ２０２は新たに委譲されたプレフィックスから適切に選んで応答を返す。
【００６０】
次に、子ルータ２０２が2)の方法を取った場合の処理について説明する。
【００６１】
この場合、子ルータ２０２は、図２３のように、全てのプレフィックスを割り当ててしまっても、この時点では特別な処理は開始しない。子ルータ２０２における要求処理部１０４が、孫ルータから要求を受け、全てのプレフィックスが割り当て済みであることを検出した時点で処理を開始する。子ルータ２０２が行う処理は次の２通りが考えられる。
【００６２】
1)  エラー（一時的エラー）を含むプレフィックス取得応答を返す。エラー送信後、次の要求が来るまでに、親ルータ２０１から新たなプレフィックスを取得する。
【００６３】
2)  応答を保留し、親ルータ２０１から新たなプレフィックスを取得した後、孫ルータに適切な応答を返す。
【００６４】
図３２は、後者2)を詳細に説明するフローチャートである。
【００６５】
子ルータ２０２は、孫ルータから要求（取得要求、拡張要求）を受信し（ステップS81）、未割り当てのプレフィックスが存在すれば、上述した新規割り当てルーチン（図２９参照）及び割り当て拡張ルーチン（図３０参照）を実行する（ステップS81、S82のYes,S83）。子ルータ２０２は、孫ルータからの要求（取得要求、拡張要求）を受信した時点で、未割り当てのプレフィックスがもはや無いと判断した場合は（ステップS82のNo）、親ルータ２０１にプレフィックス拡張要求を送信する（ステップS84）。
【００６６】
子ルータ２０２は、要求が成功した場合は（ステップS85のYes）、親ルータ２０１から受信したプレフィックスを根ノードとする二分木を生成し、通常通り、新規割り当てルーチン及び割り当て拡張ルーチンを実行する（ステップS86）。但し、このように要求が成功する場合は、後述する第２の実施形態を用いた場合にのみ起こり得る。今まで説明してきた第１の実施形態ではこの要求に対してはエラー（断片化警告）あるいはエラー（割り当て可能なプレフィックスが存在しない）が返される。
【００６７】
子ルータ２０２は、要求が成功しなかった場合で（ステップS85のNo）、親ルータ２０１からエラー（割り当て可能なプレフィックスが存在しない）を受信した場合は（ステップS87のNo）、孫ルータにエラー（割り当て可能なプレフィックスが存在しない）を返す（ステップS88,S89）。
【００６８】
子ルータ２０２は、要求が成功しなかった場合で（ステップS85のYes）、親ルータ２０１からエラー（断片化警告）を受信した場合は（ステップS87のYes）、プレフィックスの断片化を受け入れるか否かを判断する（ステップS90）。子ルータ２０２は、プレフィックスの断片化を受け入れない場合は（ステップS90のNo）、孫ルータにエラー（割り当て可能なプレフィックスが存在しない）を返す（ステップS91,S92）。一方、子ルータ２０２は、プレフィックスの断片化を受け入れる場合は（ステップS90のYes）、親ルータ２０１にプレフィックス取得要求を送信する（ステップS93）。
【００６９】
要求が成功しなかった場合は（ステップS94のNo）子ルータ２０２は孫ルータにエラー（割り当て可能なプレフィックスが存在しない）を返す（ステップS95,S96）。
【００７０】
要求が成功した場合は（ステップS97のYes）、子ルータ２０２は、新規割り当てルーチン及び割り当て拡張ルーチンによって、孫ルータからの要求に応える（ステップS94）。
【００７１】
続いて本発明の第２の実施形態について述べる。
【００７２】
図２のネットワークシステムにおいて、親ルータ２０１は配下のネットワークＮ０〜Ｎ５に再配布可能なプレフィックスをＩＳＰから取得済みであるとし、子ルータ２０２は親ルータ２０１からプレフィックス長63のプレフィックスを委譲されているものと仮定する。この様子を図２４に示す。
【００７３】
この状態で、子ルータ２０２が、孫ルータ２０４からプレフィックス長61のプレフィックスを要求された場合を考える。子ルータ２０２は、該要求に対してネットワーク識別子情報表などを参照して、割当可能か否かを判断する。要求されたプレフィックス長61は、子ルータ２０２が委譲されているプレフィックス長63の範囲内でないことから、子ルータ２０２は親ルータ２０１に対してプレフィックス拡張要求を送信するとする。
【００７４】
この場合のプレフィックス拡張要求は以下の２通りがある。
【００７５】
1) 要求されたプレフィックス長のまま拡張要求を出す
2) （要求されたプレフィックス長−１）を持つ拡張要求（包含許可）を出す
子ルータ２０２が1)の要求を送信した場合、第１の実施形態で述べたように、その要求を受信した親ルータ２０１は割り当て拡張ルーチン（図３０参照）を実行してプレフィックスを子ルータ２０２に割り当てる。但し、仮に拡張が成功した場合であっても、初めに割り当てられていたプレフィックス長63の空間（空間Ａ）と拡張要求に対して割り当てられたプレフィックス長61の空間（空間Ｂ）との間には隔たりが生じる。この様子を図２５に示す。このような隔たりが生じても、親ルータ２０１から見た子ルータ２０２は１つのプレフィックス長60のプレフィックスの下に存在することになるため、親ルータ２０１から見た経路の断片化、プレフィックスの断片化は発生していない。しかし、子ルータ２０２から見た場合には管理すべき空間が２つになるため処理に手間がかかる。
【００７６】
このため、2)のような拡張要求を利用することができる。この拡張要求は、これまでに説明したプレフィックス拡張要求メッセージに対して、既に割り当てられているプレフィックスが拡張後のプレフィックスの一部として包含されることを許可する“包含許可”を明示的に示すフラグを追加したものである。
【００７７】
図３３は、本実施形態における子ルータ２０２の処理を説明するフローチャートである。
【００７８】
子ルータ２０２は、未割り当てのプレフィックスが存在しなくなったり、管理範囲よりも広範囲なプレフィックスの取得要求を受信したりして、プレフィックスに不足が生じた場合は（ステップS101）、プレフィックス拡張要求（包含許可）を親ルータ２０１に送信する（ステップS102）。子ルータ２０２は、要求が通ならかった場合は（ステップS103のNo）、例えば通常の拡張要求（図３０参照）を行う（ステップS104）。一方、子ルータ２０２は、要求が通った場合は（ステップS103のYes）、取得したプレフィックスに基づき二分木を再構築する（ステップS105）。再構築のアルゴリズムは上述した図２７に示すアルゴリズムに従うが、既に保持している二分木の各ノードに格納されている情報は、再構築された二分木内に保存する。子ルータ２０２は、中断している処理があれば処理を再開する（ステップS106）。例えば孫ルータからの要求に基づきプレフィックス拡張要求（包含許可）を送信した場合は、子ルータ２０２はその要求に対応する処理を実行する。
【００７９】
図３４は、子ルータ２０２からプレフィックス拡張要求（包含許可）を受信した親ルータ２０１の処理手順を示す。この処理手順は、原則として割り当てプレフィックス拡張ルーチン（図３０参照）と同じであるが、以下の点が異なる。
【００８０】
a) 図３４のステップS119に示すように、L = l(X) となるノードXが、R以外のルータに使用されていないことを確認する手順が追加される。すなわち、ノードXに「使用中:R」とだけマークされていることを確認する(Xは探索するノード、Rは拡張要求を送信したルータを表す記号)。
【００８１】
b) 図３４のステップS123に示すように、目的のノードを発見した後、該ノードより下位の全てのノードに対して「使用中」とマークする。
【００８２】
c)図３４のステップS133に示すように、全てのプレフィックスが割り当て済みの場合は（ステップS131のNo）、通常の拡張要求処理を行う。
【００８３】
原則として空きプレフィックスを見つける処理は要求されたプレフィックス長に基づいて実施するため、拡張要求を出す側（子ルータ２０２側）で適切なプレフィックス長を決定する。本例では、子ルータ２０２は親ルータ２０１に対してプレフィックス長60のプレフィックスを１つ要求するプレフィックス拡張要求（包含許可）メッセージを出すことになる。この結果、子ルータ２０２に既存のプレフィックスを包含するプレフィックスが委譲され、子ルータ２０２が管理するプレフィックスを１つにまとめることができる。この様子を図２６に示す。
【００８４】
親ルータ２０１が子ルータ２０２から受信したプレフィックス拡張要求（包含許可）に対応するエラーメッセージとして、これまでのメッセージに加え次のメッセージを定義してもよい。
【００８５】
a) 要求されたプレフィックス長では包含できない
b) 包含可能な長さのプレフィックスが存在しない
この場合、例えば図３４のステップS119で、要求されたプレフィックス長で包含できるか否か、及び包含可能な長さのプレフィックスが存在するか否かの判断をさらに行い、それぞれの判断に対して、必要に応じてa)及びb)のエラーメッセージを返せばよい。
【００８６】
以上までに説明してきた本発明の第１の実施形態及び第２の実施形態はプログラムをコンピュータに実行させることによっても実現可能である。
【図面の簡単な説明】
【００８７】
【図１】本発明の第１の実施形態に従ったルータの構成図。
【図２】第１の実施形態に係わるネットワークのトポロジ図。
【図３】第１の実施形態において親ルータがISPからプレフィックスを取得した直後のネットワーク識別情報表。
【図４】第１の実施形態において親ルータがISPから取得したプレフィックスに基づき生成した二分木。
【図５】第１の実施形態において親ルータが自分が接続しているネットワークにプレフィックスを１つ割り当てたときの二分木の状態を示す図。
【図６】第１の実施形態において自分が接続しているネットワークにプレフィックスを一つ割り当てたときの親ルータの割り当て管理表。
【図７】親ルータの下に子ルータ２０２のみが接続していることを示すネットワークトポロジ図。
【図８】第１の実施形態における子ルータ２０２が親ルータからプレフィックスを取得した直後の子ルータ２０２のネットワーク識別情報表。
【図９】第１の実施形態において子ルータ２０２にプレフィックスを譲渡した後における親ルータの二分木の状態を示す図。
【図１０】第１の実施の形態において子ルータ２０２にプレフィックスを割り当てた直後の親ルータの割り当て管理表。
【図１１】第１の実施形態において親ルータから取得したプレフィックスを自分が接続しているLANに割り当てた直後の子ルータ２０２の割り当て管理表。
【図１２】第１の実施形態において親ルータから取得したプレフィックスを、孫ルータ２０４に対して割り当てた直後の子ルータ２０２の割り当て管理表。
【図１３】第１の実施形態において子ルータ２０２が親ルータから取得したプレフィックスを、孫ルータ２０４に対して割り当てる際におけるプレフィックスの決定方法を図示したもの。
【図１４】第１の実施形態において孫ルータ２０４から受信したプレフィックス拡張要求に対する子ルータ２０２の動作を説明する図。
【図１５】第１の実施形態において孫ルータ２０４から受信したプレフィックス拡張要求を処理した直後の子ルータ２０２の割り当て管理表。
【図１６】第１の実施形態において孫ルータ２０５から受信したプレフィックス取得要求に対する子ルータ２０２の動作を説明する図。
【図１７】第１の実施形態において孫ルータ２０５から受信したプレフィックス取得要求を処理した直後の子ルータ２０２の割り当て管理表。
【図１８】第１の実施形態において孫ルータ２０５から受信したプレフィックス拡張要求（１回目）に対する子ルータ２０２の動作を説明する図。
【図１９】第１の実施形態において孫ルータ２０５から受信したプレフィックス拡張要求（１回目）を処理した直後の子ルータ２０２の割り当て管理表。
【図２０】第１の実施形態において孫ルータ２０５から受信したプレフィックス拡張要求（２回目）に対する子ルータ２０２の動作を説明する図。
【図２１】第１の実施形態において孫ルータ２０５から受信したプレフィックス取得要求（断片化承認後）に対する子ルータ２０２の動作を説明する図。
【図２２】第１の実施形態において孫ルータ２０５から受信したプレフィックス取得要求（断片化承認後）を処理した直後の子ルータ２０２の割り当て管理表。
【図２３】第１の実施形態において子ルータ２０２が親ルータから取得した全てのプレフィックスを割り当ててしまった状態を示す割り当て管理表。
【図２４】第２の実施形態において子ルータ２０２が親ルータから取得した範囲よりも大きい範囲を要求する要求メッセージを受信した場合の動作を説明するための図。
【図２５】第２の実施形態において子ルータ２０２が親ルータから取得した範囲よりも大きい範囲を要求する要求メッセージを受信した場合の動作を説明するための図。
【図２６】第２の実施形態において子ルータ２０２が親ルータから取得した範囲よりも大きい範囲を要求する要求メッセージを受信した場合の動作を説明するための図。
【図２７】二分木を生成するアルゴリズムを説明するフローチャート。
【図２８】図２７に示すアルゴリズムによって生成された二分木の一例を示す図
【図２９】新規割り当てルーチンを説明するフローチャート。
【図３０】割り当て拡張ルーチンを説明するフローチャート。
【図３１】次の要求が来る前に親ルータに対してプレフィックス拡張要求を送信する場合における子ルータ２０２の動作を説明するフローチャート。
【図３２】プレィックスの新規割り当てが発生することが確定した段階で親ルータ２０１に対してプレフィックス拡張要求を送信する場合における子ルータ２０２の動作を説明するフローチャート。
【図３３】本発明の第２の実施形態における子ルータ２０２の処理手順を説明するフローチャート。
【図３４】第２の実施形態において子ルータ２０２からプレフィックス拡張要求（包含許可）を受信した場合における親ルータの処理手順を説明するフローチャート。
【符号の説明】
【００８８】
１０１：ネットワークインターフェイス部
１０２：要求受信部
１０３：応答送信部
１０４：要求処理部
１０５：ネットワーク識別情報表記憶部
１０６：割り当て管理表記憶部
１０７：割り当て管理表更新部
２０１：親ルータ
２０２，２０３：子ルータ
２０４，２０５：孫ルータ
IF1：上流側インターフェイス
IF2：下流側インターフェイス
【図１】
2006020153.tif 000003
【図２】
2006020153.tif 000004
【図３】
2006020153.tif 000005
【図４】
2006020153.tif 000006
【図５】
2006020153.tif 000007
【図６】
2006020153.tif 000008
【図７】
2006020153.tif 000009
【図８】
2006020153.tif 000010
【図９】
2006020153.tif 000011
【図１０】
2006020153.tif 000012
【図１１】
2006020153.tif 000013
【図１２】
2006020153.tif 000014
【図１３】
2006020153.tif 000015
【図１４】
2006020153.tif 000016
【図１５】
2006020153.tif 000017
【図１６】
2006020153.tif 000018
【図１７】
2006020153.tif 000019
【図１８】
2006020153.tif 000020
【図１９】
2006020153.tif 000021
【図２０】
2006020153.tif 000022
【図２１】
2006020153.tif 000023
【図２２】
2006020153.tif 000024
【図２３】
2006020153.tif 000025
【図２４】
2006020153.tif 000026
【図２５】
2006020153.tif 000027
【図２６】
2006020153.tif 000028
【図２７】
2006020153.tif 000029
【図２８】
2006020153.tif 000030
【図２９】
2006020153.tif 000031
【図３０】
2006020153.tif 000032
【図３１】
2006020153.tif 000033
【図３２】
2006020153.tif 000034
【図３３】
2006020153.tif 000035
【図３４】
2006020153.tif 000036