(57)【特許請求の範囲】
【請求項１】
ＯＳＰＦ（Open  Shortest  Path  First）プロトコルを実装するネットワークエレメント上で実行される、異なるルートに関連付けられる異なるリンクステート広告（ＬＳＡ）が同じＬＳＩＤを共有することを防止するようにリンクステート識別子（ＬＳＩＤ）の衝突をハンドリングする方法であって、各ＬＳＡは、割当てられるＬＳＩＤにより識別され、前記方法は、
第１のルートについてのＬＳＩＤ割当て処理の間に、
前記第１のルートについての暫定ＬＳＩＤを生成するステップ、並びに、
前記暫定ＬＳＩＤの値が第２のルートについてのＬＳＡに既に割当てられていることを判定し、前記第１及び第２のルートの１つがホストルートであることをさらに判定するステップ、
を実行するステップと、
前記ホストルートは、ホストルートマスクを有するルートであることと、
前記第１及び第２のルートは異なることと、
前記ホストルートが前記第１のルートであることの判定に応じて、
前記第１及び第２のルートの間のＬＳＩＤの衝突を防止するように、前記第１のルートを抑制するステップ、
を実行するステップと、
前記抑制するステップは、ＬＳＡを前記第１のルートについて発生させないステップを含むことと、
前記ホストルートが前記第２のルートであることの判定に応じて、
前記第１及び第２のルートの間のＬＳＩＤの衝突を防止するように、前記第２のルートを抑制するステップ、並びに、
前記暫定ＬＳＩＤの前記値で前記第１のルートについてのＬＳＡを発生させるステップ、
を実行するステップと、
前記抑制するステップは、前記第２のルートについてのＬＳＡをパージするステップを含むことと、
を含み、
前記ホストルートを包含する範囲についてのネットワーク到達可能性は、前記第１及び第２のルートのうち抑制されていないものを通じて提供され、
それにより、抑制されたホストルートの存在においてさえも前記ルートの各々が到達可能でありながら、ホストルートを含む異なるルートについてのＬＳＡが同じＬＳＩＤを共有することが防止される、
方法。
【請求項２】
抑制されない他方のルートに前記ホストルートを関連付けるステップ、をさらに含み、それにより、関連付けられる当該ルートが撤回される場合には前記ホストルートが自動的に抑制解除される、請求項１に記載の方法。
【請求項３】
前記ホストルートの撤回に応じて、前記第１及び第２のルートの関連付けを解除するステップ、
をさらに含む、請求項２に記載の方法。
【請求項４】
前記第１及び第２のルートのうちホストルートではない方の撤回であって、当該ルートに関連付けられるＬＳＡをパージすることを含む撤回に応じて、前記ホストルートを抑制解除し、当該ルートについてのＬＳＡを、パージされる前記ＬＳＡに割当てられたＬＳＩＤで発生させるステップ、
をさらに含む、請求項２に記載の方法。
【請求項５】
前記第１のルートはホストルートであり、前記第２のルートは前記第１のルートに関連付けられていることと、
ホストルートマスクではないルートマスクを有する第３のルートについてのＬＳＩＤ割当て処理の間に、
前記第３のルートについての暫定ＬＳＩＤを生成するステップと、
前記第３のルートについての前記暫定ＬＳＩＤの値が前記第２のルートについての前記ＬＳＡに既に割当てられていることを判定するステップと、
前記第３のルートの前記ルートマスクは、前記第２のルートのルートマスクより短いことと、
前記判定するステップに応じて、
前記第１及び第２のルートの関連付けを解除するステップ、
前記第２のルートについての前記ＬＳＡをパージするステップ、
前記第３のルートを前記第１のルートに関連付けるステップ、並びに、
前記第２のルートについての前記ＬＳＡに以前に割当てられた前記暫定ＬＳＩＤの値を有する前記第３のルートについてのＬＳＡを発生させるステップ、
を実行するステップと、
を実行するステップと、
をさらに含む、請求項２に記載の方法。
【請求項６】
前記第２のルートについての暫定ＬＳＩＤを生成するステップと、
前記第２のルートについての前記暫定ＬＳＩＤの値が異なるルートについての既存のＬＳＡに割当てられているかどうか判定するステップと、
前記第２のルートについての前記暫定ＬＳＩＤの前記値が既存のＬＳＡに割当てられていないことの判定に応じて、前記第２のルートについて当該ＬＳＩＤを割当て、当該割当てられるＬＳＩＤで前記第２のルートについてのＬＳＡを発生させるステップと、
前記第２のルートについての前記暫定ＬＳＩＤの前記値が、ホストルートである第４のルートについての既存のＬＳＡに既に割当てられていることの判定に応じて、前記第４のルートを抑制し、それにより、前記第２及び前記第４のルートの間のＬＳＩＤの衝突を防止するステップと、
をさらに含む、請求項５に記載の方法。
【請求項７】
前記ＬＳＡをパージする前記ステップは、リンクステートデータベース（ＬＳＤＢ）から前記第２のルートについての対応するエントリを除去するステップを含み、前記発生させるステップは、前記発生させるＬＳＡを前記ＬＳＤＢに追加するステップを含む、請求項１に記載の方法。
【請求項８】
前記ネットワークエレメントのローカルＯＳＰＦルーティング情報ベース（ＲＩＢ：routing  information  base）において抑制される各ホストルートを維持するステップ、をさらに含む、請求項１に記載の方法。
【請求項９】
前記ＯＳＰＦプロトコルを介して結合された別のネットワークエレメントからの、前記ネットワークエレメント上のＯＳＰＦとは異なるルーティングプロトコルから再配布される、又は静的に構成される前記第１のルートを受け取るステップ、をさらに含む、請求項１に記載の方法。
【請求項１０】
異なるルートに関連付けられる異なるリンクステート広告（ＬＳＡ）が同じＬＳＩＤを共有することを防止するようにＯＳＰＦ（Open  Shortest  Path  First）リンクステート識別子（ＬＳＩＤ）の衝突をハンドリングするシステムであって、各ＬＳＡは、割当てられるＬＳＩＤにより識別され、前記システムは、
ＯＳＰＦプロトコルを介して第１のプロバイダエッジネットワークエレメントにＯＳＰＦルートを配布するカスタマエッジネットワークエレメントと、前記ＯＳＰＦルートのうちの少なくともいくつかはホストルートであり、ホストルートとはホストルートマスクを有するルートであることと、
ＢＧＰ（Border  Gateway  Protocol）を介して第２のプロバイダエッジネットワークエレメントに前記ＯＳＰＦルートを配布する前記第１のプロバイダエッジネットワークエレメントと、
を備え、
前記第１のプロバイダエッジネットワークエレメントは、前記ＯＳＰＦプロトコルを実装し、ＬＳＡを生成し、前記ＬＳＡにＬＳＩＤを割当てるＯＳＰＦモジュール、を備え、
前記ＯＳＰＦモジュールは、ＬＳＩＤ割当ての間に、
前記ＯＳＰＦルートのうち、通常は他のＬＳＡと衝突するＬＳＩＤを有する対応するＬＳＡを有するはずのホストルートであるものを抑制すること、
を実行し、
ここで抑制するとは、抑制される前記ホストルートに関連付けられる前記ＬＳＡの除去、及び抑制される前記ホストルートについてのＬＳＡを発生させないことを含み、
抑制される前記ホストルートの各々は、抑制される当該ホストルートと衝突するＬＳＩＤを有している前記ＬＳＡに関連付けられる前記ルートを通じて到達可能であり、
それにより、抑制されるホストルートの存在においてさえも前記ルートの各々が到達可能でありながら、ホストルートを含む異なるルートについてのＬＳＡが同じＬＳＩＤを共有することが防止される、
システム。
【請求項１１】
前記第１のプロバイダエッジネットワークエレメントの前記ＯＳＰＦモジュールは、
抑制される各ホストルートについて、当該抑制されるホストルートを、通常は当該抑制されるホストルートと衝突するＬＳＩＤを有したはずのルートに関連付けること、
をさらに実行する、
請求項１０に記載のシステム。
【請求項１２】
抑制されるホストルートについてのネットワーク到達可能性を提供するルートの各々について、前記ＯＳＰＦモジュールは、
当該ＯＳＰＦルートと同じネットワークプレフィックスを有する異なるＯＳＰＦルートがより小さいルートマスクを有することの判定に応じて、前記関連付けを、当該ＯＳＰＦルートから前記異なるＯＳＰＦルートに移行すること、
も実行し、
抑制される各ホストルートは、所与の時点で単一のＯＳＰＦルートに関連付けられている、
請求項１１に記載のシステム。
【請求項１３】
前記第１のプロバイダエッジネットワークエレメントは、
ＯＳＰＦルートを記憶するローカルＯＳＰＦルーティング情報ベース（ＲＩＢ）と、
リンクステートデータベース（ＬＳＤＢ）と、
をさらに含み、
前記ＯＳＰＦモジュールは、前記ローカルＯＳＰＦ  ＲＩＢにおいて抑制されるホストルートをさらに維持し、
前記ＯＳＰＦモジュールは、抑制されないルートについてのＬＳＡを前記ＬＳＤＢにさらに追加する、
請求項１１に記載のシステム。
【請求項１４】
前記第１のプロバイダエッジネットワークエレメントの前記ＯＳＰＦモジュールは、
ホストルートではないＯＳＰＦルートを撤回し、対応するＬＳＡをパージすること、及び、
前記撤回されるルートに関連付けられ抑制されているホストルートを抑制解除すること、
をさらに実行し、
抑制解除することは、当該抑制解除されるホストルートについてのＬＳＡを発生させることを含む、
請求項１１に記載のシステム。
【請求項１５】
異なるルートに関連付けられる異なるリンクステート広告（ＬＳＡ）が同じＬＳＩＤを共有することを防止するようにリンクステート識別子（ＬＳＩＤ）の衝突をハンドリングするネットワークエレメントであって、各ＬＳＡは、割当てられるＬＳＩＤにより識別され、
前記ネットワークエレメントは、リンクステートデータベース（ＬＳＤＢ）を維持し、ＬＳＩＤを含むＬＳＡを生成するＯＳＰＦ（Open  Shortest  Path  First）モジュール、を含み、
前記ＯＳＰＦモジュールは、ＬＳＩＤ割当ての間に、
ルートについてのＬＳＡに、当該ルートのネットワークプレフィックス及びルートマスクに基づいてＬＳＩＤを割当てること、並びに
前記ルートのうち、通常は異なるルートに関連付けられる異なるＬＳＡのＬＳＩＤと衝突するＬＳＩＤを有する対応するＬＳＡを有するはずのホストルートであるものを抑制すること、
を実行し、
ホストルートとは、ホストルートマスクを有するルートであり、
当該ホストルートの前記抑制は、抑制される前記ホストルートに関連付けられる前記ＬＳＡの除去、及び抑制される前記ホストルートについてのＬＳＡを発生させないことを含み、
抑制される前記ホストルートの各々について、当該抑制されるホストルートを包含する範囲が、通常は当該抑制されるホストルートのＬＳＡと衝突するＬＳＩＤを含んでいたはずのＬＳＡに関連付けられるルートを通じて到達可能であり、
それにより、ルートが到達不可能であること又は複数のルートが同じＬＳＡを指し示すことを防止するように、ホストルートのＬＳＩＤの衝突が回避される、
ネットワークエレメント。
【請求項１６】
前記ＯＳＰＦモジュールは、ＯＳＰＦプロトコルを介して他のネットワークエレメントから知らされ、前記ネットワークエレメント上の他のルーティングプロトコルから再配布され、又は静的に構成されるルートを受け取る、請求項１５に記載のネットワークエレメント。
【請求項１７】
抑制されないルートを異なるネットワークエレメントに配布するＢＧＰ（Border  Gateway  Protocol）モジュール、をさらに含む、請求項１５に記載のネットワークエレメント。
【請求項１８】
ＯＳＰＦルートを記憶するローカルＯＳＰＦルーティング情報ベース（ＲＩＢ）、をさらに含み、前記ＯＳＰＦモジュールは、また、抑制される前記ホストルートを前記ローカルＯＳＰＦ  ＲＩＢに記憶する、請求項１５に記載のネットワークエレメント。
【請求項１９】
前記ＯＳＰＦモジュールは、ＬＳＩＤ割当ての間に、
抑制される各ホストルートについて、当該抑制されるホストルートを、通常は当該抑制されるホストルートと衝突するＬＳＩＤを有したはずのルートに関連付けること、
をも実行する、請求項１５に記載のネットワークエレメント。
【請求項２０】
前記ＯＳＰＦモジュールは、また、同じネットワークプレフィックスを有するルート間の関連付けを、前記ルートの前記ネットワークプレフィックス及び当該ルートのルートマスクの長さに基づいて移行する、請求項１９に記載のネットワークエレメント。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、リンクステートルーティングプロトコルに関し、より具体的には、リンクステートの割当ての間のリンクステート識別子の衝突のハンドリングに関する
【背景技術】
【０００２】
（例えば、１９９８年４月付けのＲＦＣ２３２８において定義されているような）ＯＳＰＦ（Open  Shortest  Path  First）などのリンクステートルーティングプロトコルは、リンクステート広告（ＬＳＡ：Link  State  Advertisements）を識別する際にリンクステート識別子（ＬＳＩＤ：Link  State  Identifiers）をキーとして使用する。同じＬＳＩＤを共有する異なるルートについてのＬＳＡは、不正確なトポロジーのビュー、データマッピングの問題、複数のルートが同じＬＳＡを指し示すことなどを含む様々な問題を引き起こし得る。
【０００３】
大多数のルートについて、各ルートに関連付けられるＬＳＡは、当該ルートのネットワークアドレスに等しいＬＳＩＤを割当てられる。ルートについてのネットワークアドレスは、ルートプレフィックス及びルートマスクのビットごとのＡＮＤ演算を実行することにより計算される。例えば、ルート［１０．０．０．０，２５５．２５５．０．０］についてのネットワークアドレスは１０．０．０．０であるから、当該ルートについてのＬＳＡは、典型的には、１０．０．０．０というＬＳＩＤ値を割当てられる。
【０００４】
同じプレフィックスを有するルートは、そのマスクが異なれば異なるとみなされるが、それらのルートのネットワークアドレスは同じにすることができる。例えば、ルート［１０．０．０．０，２５５．２５５．０．０］及び［１０．０．０．０，２５５．２５５．２５５．０］は異なるが、にもかかわらず、１０．０．０．０という同じネットワークアドレスを共有している。よって、これらのルートに関連付けられるＬＳＡについてのＬＳＩＤは衝突するはずである。そのような場合に、ＲＦＣ２３２８は、それらのルートのＬＳＡについて異なるＬＳＩＤを割当てようと試みるアルゴリズムを記載している（このアルゴリズムは、ＲＦＣ２３２８の付録Ｅにおいて指定されている）。ＲＦＣ２３２８におけるＬＳＩＤの衝突のハンドリングアルゴリズムは、より長いマスクを有するルートを選択し、当該マスクのビットごとのＮＯＴ演算を実行し、当該結果とルートプレフィックスとのビットごとのＯＲ演算を実行し、その結果をＬＳＩＤとして割当てる。例えば、上記の２つのルートを使用すると、ルート［１０．０．０．０，２５５．２５５．２５５．０］が選択され、０．０．０．２５５に等しいマスク２５５．２５５．２５５．０のビットごとのＮＯＴ演算の結果が、ビットごとに、ルートプレフィックス１０．０．０．０とＯＲ演算され、１０．０．０．２５５という値がもたらされ、この値が次いで当該ルートのＬＳＡについてのＬＳＩＤとして割当てられる。選択されないルートは、ネットワークアドレスに等しいＬＳＩＤを割当てられる。
【０００５】
ＲＦＣ２３２８に記載されているＬＳＩＤの衝突のハンドリングアルゴリズムは、衝突するルートの１つがホストルートであるときには、ＬＳＩＤの衝突を正しくハンドリングしない。ホストルートとは、ホストマスク（２５５．２５５．２５５．２５５など）を有するルートである。例えば、同じネットワークアドレス（１０．０．０．０）を有するルート［１０．０．０．０，２５５．２５５．２５５．０］及び［１０．０．０．０，２５５．２５５．２５５．２５５］を考える。ＲＦＣ２３２８のＬＳＩＤの衝突のハンドリングアルゴリズムによれば、（ホストルートである）ルート［１０．０．０．０，２５５．２５５．２５５．２５５］が選択され、０．０．０．０に等しいマスク２５５．２５５．２５５．２５５のビットごとのＮＯＴ演算の結果が、ビットごとに、ルートプレフィックス１０．０．０．０とＯＲ演算され、１０．０．０．０という値がもたらされ、この値が次いで当該ルートのＬＳＡについてのＬＳＩＤとして割当てられる。よって、ＲＦＣ２３２８のＬＳＩＤの衝突のハンドリングアルゴリズムを使用すると、異なるルート［１０．０．０．０，２５５．２５５．２５５．０］及び［１０．０．０．０，２５５．２５５．２５５．２５５］が、１０．０．０．０という同じＬＳＩＤを共有するＬＳＡを有することになる。したがって、ＲＦＣ２３２８に記載されているＬＳＩＤの衝突のハンドリングアルゴリズムは、ホストルートに適用される際に、前述の問題をもたらし得る同じＬＳＩＤを共有する異なるルートのＬＳＡをもたらす。
【発明の概要】
【課題を解決するための手段】
【０００６】
ネットワークエレメントが異なるルートに関連付けられる異なるＬＳＡが同じＬＳＩＤを共有することを防止するようにＬＳＩＤの衝突をハンドリングする方法及び装置を説明する。本発明の一実施形態によれば、ネットワークエレメントは、ＬＳＩＤ割当て処理の間に第１のルートについての暫定ＬＳＩＤを生成する。ネットワークエレメントは、暫定ＬＳＩＤの値が第２のルートに既に割当てられていること、及び第１のルート又は第２のルートのどちらかがホストルートであることを判定し、ホストルートはホストルートマスクを有し、第１及び第２のルートは異なる。第１のルートがホストルートであることを判定したことに応じて、第１のルートは、第１及び第２のルートの間のＬＳＩＤの衝突を防止するように抑制され、これは、第１のルートについてのＬＳＡを発生させないことを含む。第２のルートがホストルートであることを判定したことに応じて、第２のルートは、第１及び第２のルートの間のＬＳＩＤの衝突を防止するように抑制され、これは、第２のルートのＬＳＡをパージすることを含み、第１のルートについてのＬＳＡは、第２のルートに割当てられたＬＳＩＤで発生される。ホストルートは抑制されるが、ホストルートを包含する範囲のネットワーク到達可能性は、ホストルートではないルートを通じて提供される。ホストルートとのＬＳＩＤの衝突を生じたはずのルートが、ホストルートより前に撤回される場合には、ホストルートは抑制解除され、ＬＳＡが、他方のルートのＬＳＡに以前に割当てられたＬＳＩＤでホストルートについて自動的に発生される。
【０００７】
本発明の別の実施形態によれば、カスタマエッジネットワークエレメントは、ＯＳＰＦプロトコルを介して第１のプロバイダエッジネットワークエレメントにＯＳＰＦルートを配布し、ＯＳＰＦルートの少なくともいくつかはホストルートであり、ホストルートとは、ホストルートマスクを有するルートである。第１のプロバイダエッジネットワークエレメントは、ＯＳＰＦルートを、ＢＧＰ（Border  Gateway  Protocol）を介して第２のプロバイダエッジネットワークエレメントに配布する。第１のプロバイダエッジネットワークエレメントは、ＯＳＰＦプロトコルを実装し、ＬＳＡを生成し、ＬＳＡにＬＳＩＤを割当てるＯＳＰＦモジュールを含む。ＬＳＩＤ割当ての間に、ＯＳＰＦモジュールは、ＯＳＰＦルートのうち、通常は他のＬＳＡと衝突するＬＳＩＤを有する対応するＬＳＡを有するはずのホストルートであるＯＳＰＦルートを抑制する。ＯＳＰＦルートを抑制することは、抑制されるホストルートに関連付けられるＬＳＡを除去すること、及び抑制されるホストルートについてのＬＳＡを発生させないことを含む。ＬＳＡは当該抑制されるホストルートについて発生されないが、ネットワーク到達可能性は、当該ホストルートと衝突するＬＳＩＤを有したＬＳＡに関連付けられるルートを通じて抑制される各ホストルートについて提供される。抑制される各ホストルートは、ホストルートと同じＬＳＩＤを有するはずのＬＳＡに関連付けられるルートが、当該抑制されるホストルートより前に撤回されるときには抑制解除され、ＬＳＡが、他方のルートのＬＳＡに以前に割当てられたＬＳＩＤで、当該抑制解除されるホストルートについて自動的に発生される。
【０００８】
本発明の別の実施形態によれば、ＬＳＩＤの衝突をハンドリングするネットワークエレメントは、リンクステートデータベース（ＬＳＤＢ）を維持し、ＬＳＩＤを含むＬＳＡを生成するＯＳＰＦモジュールを含む。ＬＳＡについてのＬＳＩＤ割当ての間に、ＯＳＰＦモジュールは、ルートについてのＬＳＡに、当該ルートのネットワークプレフィックス及びルートマスクに基づいてＬＳＩＤを割当て、ルートのうち、通常は異なるルートに関連付けられる異なるＬＳＡのＬＳＩＤと衝突するＬＳＩＤを有する対応するＬＳＡを有するはずのホストルートであるルートを抑制する。当該ルートの抑制は、抑制されるホストルートに関連付けられるＬＳＡを除去すること、及び抑制されるホストルートについてのＬＳＡを発生させないことを含む。ＬＳＡは当該抑制されるホストルートについて発生されないが、ネットワーク到達可能性は、当該ホストルートと衝突するＬＳＩＤを有しているＬＳＡに関連付けられるルートを通じて抑制される各ホストルートについて提供される。抑制される各ホストルートは、ホストルートと同じＬＳＩＤを有するはずのＬＳＡに関連付けられるルートが、当該抑制されるホストルートより前に撤回されるときには抑制解除され、ＬＳＡが、他方のルートのＬＳＡに以前に割当てられたＬＳＩＤで当該抑制解除されるホストルートについて自動的に発生される。
【０００９】
よって、ホストルートを含む異なるルートは、抑制されるホストルートの存在においてさえもルートの各々が到達可能でありながら、同じＬＳＩＤを共有するＬＳＡを発生させることを防止される。抑制されるホストルートについてのＬＳＡと衝突したはずのＬＳＩＤを有するＬＳＡに関連付けられるルートが、当該抑制されるホストルートより前に撤回されるときには、当該抑制されるホストルートは抑制解除され、ＬＳＡが、他方のルートのＬＳＡに割当てられたＬＳＩＤで当該ホストルートについて発生する。
【図面の簡単な説明】
【００１０】
本発明は、以下の説明、及び本発明の実施形態を例示するのに使用される添付図面を参照することにより適切に理解され得る。
【００１１】
【図１】本発明の一実施形態による例示的なネットワークを示すブロック図である。
【図２】本発明の一実施形態による例示的なネットワークを示すブロック図である。
【図３】本発明の一実施形態によるＬＳＩＤの衝突をハンドリングする例示的なネットワークエレメントを示すブロック図である。
【図４】本発明の一実施形態による、ＬＳＩＤの衝突をハンドリングすることを含む、ルートについてのＬＳＩＤを割当てる例示的なルート追加処理を示すデータフロー図である。
【図５】本発明の一実施形態による、ルートを抑制解除することを含む、例示的なルート撤回処理を示すデータフロー図である。
【図６】本発明の一実施形態による、ＬＳＩＤの衝突をハンドリングすることを含む、ルート追加処理の間に実行される例示的な動作を示すフロー図である。
【図７】本発明の一実施形態による、ルート撤回処理の間に実行される例示的な動作を示すフロー図である。
【図８】本発明の一実施形態による、ある順序で到着するルートのセットについてのＬＳＩＤ割当てを示すブロック図である。
【図９】本発明の一実施形態による、図８と異なる順序で到着するルートのセットについてのＬＳＩＤ割当てを示すブロック図である。
【発明を実施するための形態】
【００１２】
以下の説明では、多くの具体的詳細が示される。しかし、本発明の実施形態はこれらの具体的詳細なしでも実施され得ることが理解される。場合によっては、この説明の理解を不明確にしないように、周知の回路、構造及び技法が詳細に示されていない。当業者は、含まれる説明を読めば、必要以上の実験を行わなくても適切な機能を実装することができるであろう。
【００１３】
本明細書で「１つの実施形態」、「一実施形態」、「一例としての実施形態」などという場合、それらは、説明される実施形態が、特定の特徴、構造、又は特性を含み得るが、あらゆる実施形態が必ずしもその特定の特徴、構造、又は特性を含むとは限らないことを示すものである。さらに、そのような語句は必ずしも同じ実施形態を指し示すものであるとは限らない。さらに、特定の特徴、構造、又は特性が１つの実施形態との関連で説明されるときには、明示されようとされまいと、そのような特徴、構造、又は特性を他の実施形態との関連で実施することが当業者の知識の範囲に含まれるものであることが提示されるものである。
【００１４】
以下の説明及び特許請求の範囲では、「結合された（coupled）」及び「接続された（connected）」という用語が、その派生語と共に使用される場合がある。これらの用語は相互についての同義語を意図するものではないことを理解すべきである。「結合された」は、相互に直接物理的又は電気的に接触していてもいなくてもよい２つ以上の要素が、相互に協働し、又は相互に作用し合うことを示すのに使用される。「接続された」は、相互に結合されている２つ以上の要素の間での通信の確立を示すのに使用される。
【００１５】
図に示す技法は、１台又は複数の電子機器（例えば、端局、ネットワークエレメントなど）上で記憶され、実行されるコード及びデータを使って実装することができる。そのような電子機器は、マシン読取可能な記憶媒体（磁気ディスク、光ディスク、ランダムアクセスメモリ、読取り専用メモリ、フラッシュメモリデバイス、相変化メモリなど）や、マシン読取可能な通信媒体（電気的、光学的、音響的、又は他の形の伝搬信号、例えば、搬送波、赤外線信号、ディジタル信号など）といったマシン読取可能な媒体を使ってコード及びデータを記憶し、（内部で、及び／又はネットワーク上で他の電子機器と）通信する。加えて、そのような電子機器は、典型的には、例えば、１つ又は複数の記憶装置、ユーザ入力／出力装置（キーボード、タッチスクリーン、及び／又はディスプレイなど）、並びにネットワーク接続といった１つ又は複数の他の構成要素に結合された１つ又は複数のプロセッサのセットを含む。プロセッサのセット及び他の構成要素の結合は、典型的には、１つ又は複数のバス及びブリッジ（バスコントローラともいう）を介したものである。記憶装置及びネットワークトラフィックを搬送する信号は、それぞれ、１つ又は複数のマシン読取可能な記憶媒体及びマシン読取可能な通信媒体を表す。よって、所与の電子機器の記憶装置は、典型的には、当該電子機器の１つ又は複数のプロセッサのセット上で実行するためのコード及び／又はデータを記憶する。当然ながら、本発明の実施形態の１つ又は複数の部分は、ソフトウェア、ファームウェア、及び／又はハードウェアの異なる組み合わせを使って実装されてもよい。
【００１６】
本明細書で使用する場合、ネットワークエレメント（例えば、ルータ、スイッチ、ブリッジなど）とは、ネットワーク上の他の設備（例えば、他のネットワークエレメント、端局など）と通信可能な状態で相互接続する、ハードウェア及びソフトウェアを含むネットワーク設備である。ネットワークエレメントの中には、複数のネットワーキング機能（ルーティング、ブリッジング、スイッチング、レイヤ２アグリゲーション、セッションボーダ制御（session  border  control）、及び／又は加入者管理など）についてのサポートを提供し、及び／又は複数のアプリケーションサービス（データ、音声、ビデオなど）についてのサポートを提供する「複数サービスネットワークエレメント」がある。加入者端局（例えば、サーバ、ワークステーション、ラップトップ、パームトップ、携帯電話、スマートフォン、マルチメディアフォン、ＶＯＩＰ（Voice  Over  Internet  Protocol）フォン、携帯用メディアプレーヤ、ＧＰＳユニット、ゲームシステム、セットトップボックスなど）は、インターネット上で提供されるコンテンツ／サービス及び／又はインターネット上にオーバーレイされたＶＰＮ（virtual  private  network）上で提供されるコンテンツ／サービスにアクセスする。コンテンツ及び／又はサービスは、典型的には、サービス又はコンテンツプロバイダに属する１つ若しくは複数の端局（サーバ端局など）又はピアツーピアサービスに参加している端局によって提供され、公開ウェブページ（無料コンテンツ、店頭、検索サービスなど）、専用ウェブページ（ユーザ名／パスワードでアクセスされる電子メールサービスを提供するウェブページなど）、ＶＰＮ上の企業ネットワークなどを含み得る。典型的には、加入者端局は、（例えば（有線又は無線で）アクセスネットワークに結合されたカスタマ構内設備を介して）エッジネットワークエレメントに結合され、エッジネットワークエレメントは（例えば１つ又は複数のコアネットワークエレメントを介して）他のエッジネットワークエレメントに結合され、他のエッジネットワークエレメントは他の端局（サーバ端局など）に結合される。
【００１７】
典型的には、ネットワークエレメントは、１つ又は複数のラインカードのセット、１つ又は複数の制御カードのセット、及び、任意選択で、１つ又は複数のサービスカード（リソースカードとも呼ばれる）のセットを含む。これらのカードは、１つ又は複数の機構（例えば、ラインカードを結合する第１のフルメッシュ及びすべてのカードを結合する第２のフルメッシュなど）を介して相互に結合される。ラインカードのセットはデータプレーンを構成し、制御カードのセットは制御プレーンを提供し、ラインカードを介して外部ネットワークエレメントとパケットを交換する。サービスカードのセットは特殊化された処理（例えば、レイヤ４からレイヤ７までのサービス（ファイアウォール、ＩＰｓｅｃ、ＩＤＳ、Ｐ２Ｐ）、ＶｏＩＰセッションボーダコントローラ、モバイルワイヤレスゲートウェイ（Mobile  Wireless  Gateway）（ＧＧＳＮ、ＥＰＳ（Evolved  Packet  System）ゲートウェイ）など）を提供することができる。例として、サービスカードは、ＩＰｓｅｃトンネルを終端させ、付随的認証及び暗号化（attendant  authentication  and  encryption）のアルゴリズムを実行するのに使用され得る。
【００１８】
ＬＳＩＤの衝突をハンドリングする方法及び装置を説明する。本発明の一実施形態では、そのＬＳＡが異なるルートとのＬＳＩＤの衝突を生じるはずのホストルートは、当該ホストルートについてのＬＳＡが発生されず、及び／又はリンクステートデータベース（ＬＳＤＢ）からパージされるように抑制される。当該ホストルートを抑制することは、複数の異なるルートが、同じＬＳＩＤを共有するＬＳＡを有することを防止する。よって、異なるルートについて発生される同じＬＳＩＤを有するＬＳＡに生じ得る問題（例えば、誤ったトポロジー、データ完全性の問題、トラフィックのブラックホール化、ソフトウェアクラッシュなど）が回避される。
【００１９】
一実施形態では、抑制される各ホストルートは、そのＬＳＡが、抑制されるホストルートのＬＳＡに割当てられるはずのＬＳＩＤと衝突することになるＬＳＩＤを有するルートに関連付けられる。当該他のルートが抑制されるホストルートより前に撤回されたことに応じて、ホストルートは抑制解除され（unsuppressed）、ＬＳＡが、当該他のルートのＬＳＡに割当てられたＬＳＩＤで発生する。
【００２０】
図１は、本発明の一実施形態による例示的なネットワーク１００を示すブロック図である。図１に示すように、ネットワーク１００は、ネットワークエレメント１２０と（直接的又は間接的に）結合された加入者端局（subscriber  end  station）１１０Ａ〜１１０Ｎを含む。ネットワークエレメント１２０は、ネットワーク１００においてＡＳＢＲ（Autonomous  System  Border  Router）として働く。ネットワークエレメント１２０は、ネットワークエレメント１２０上のＯＳＰＦへのルート再配布によって加入者端局１１０Ａ〜１１０Ｎからのホストルートを知得することができ、及び／又は、ホストルートは、ネットワークエレメント１２０上で静的に構成され得る（ホストルートは、典型的には、ルート再配布によってＯＳＰＦにも提供される）。図示されていないが、ネットワークエレメント１２０は、加入者端局１１０Ａ〜１１０Ｎに割当てられるホストルート以外のルートをも知得する。
【００２１】
ネットワークエレメント１２０は、ホストルートを含む知得したルートをＯＳＰＦドメインへと（例えば、ネットワーク１００においてＡＢＳ（Area  Border  Router）として働くネットワークエレメント１３０などに）広告（advertise）する。例えば、ネットワークエレメント１２０は、加入者端局１１０Ａ〜１１０Ｎに割当てられるホストルートと、ホストルートがそこから割り振られるプールに対応するルート群とを広告することができる。一実施形態では、ネットワークエレメント１２０は、ホストルートを含むルートを、ＯＳＰＦタイプ５ＬＳＡ（外部ＬＳＡ）を使ってネットワークエレメント１３０に広告する。
【００２２】
図２は、本発明の一実施形態による例示的なネットワーク２００を示すブロック図である。図２に示すように、ネットワーク２００はＶＰＮ（レイヤ３ＶＰＮなど）である。カスタマエッジ（ＣＥ）ネットワークエレメント２１５は、ＯＳＰＦリンクであるＣＥ−ＰＥリンク２８０上でプロバイダエッジ（ＰＥ）ネットワークエレメント２２０と通信する。同様に、ＣＥネットワークエレメント２３０も、ＯＳＰＦリンクであるＣＥ−ＰＥリンク２８２上でＰＥネットワークエレメント２２５と通信する。ＰＥネットワークエレメント２２０及び２２５は、ＢＧＰリンクであるＰＥ−ＰＥリンク２８４上で通信する。
【００２３】
ＣＥネットワークエレメント２１５は、ＣＥ−ＰＥリンク２８０上でサイト２１０からＰＥネットワークエレメント２２０に、ホストルートを含むルートを広告する。ＣＥネットワークエレメント２３０は、ＣＥ−ＰＥリンク２８２上でサイト２４０からＰＥネットワークエレメント２２５に、ホストルートを含むルートを広告する。サイト２１０及び２４０は、それぞれ、複数の加入者端局を含むことができる。ＰＥネットワークエレメント２２０及び２２５は、それぞれ、ＣＥネットワークエレメント２１５及び２３０から知らされる、ホストルートを含むルートを、相互にエクスポートし合う。さらに詳細に後述するように、ＢＧＰを介してエクスポートされるルートは、ＯＳＰＦへと再配布することができる。
【００２４】
図１及び図２に示すネットワークは例示であり、本発明の実施形態は、ホストルートがリンクステートプロトコルによって広告される異なるタイプのネットワークにも適用できることを理解すべきである。
【００２５】
図３は、本発明の一実施形態による、ＬＳＩＤの衝突をハンドリングする例示的なネットワークエレメントを示すブロック図である。図３にはネットワークエレメント２２０が示されているが、図１に示すネットワークエレメント１２０及びネットワークエレメント２２５も本発明のいくつかの実施形態において同様の機能を含むことを理解すべきである。
【００２６】
ネットワークエレメント２２０は、ルーティング情報ベース（ＲＩＢ：Routing  Information  Base）モジュール３６０と結合された、ＯＳＰＦプロトコルの実装形態を実装するＯＳＰＦモジュール３２０を含み、ＲＩＢモジュール３６０は、ＢＧＰモジュール３４０の実装形態を実装するＢＧＰモジュール３４０と結合される。ＯＳＰＦモジュール３２０及びＢＧＰモジュール３４０は、あるルートメトリック（メトリックはＯＳＰＦモジュール３２０及びＢＧＰモジュール３４０について異なるものとすることができる）に基づいてメインＲＩＢ３６５にルートエントリをダウンロードする。ＲＩＢモジュール３６０はメインＲＩＢ３６５を管理し（例えば、ルート更新、ルート削除を処理するなど）、また、ルーティングプロトコル間でルートを再配布させることもできる。例えば、ＲＩＢモジュール３６０は、（ＰＥネットワークエレメント２２５によってエクスポートされるホストルートを含むことができる）ＢＧＰモジュール３４０によって知得されるルートをＯＳＰＦモジュール３２０に再配布させることができる。別の例として、ＲＩＢモジュール３６０は、（ＣＥネットワークエレメント２１５から知らされるホストルートを含むことができる）ＯＳＰＦモジュール３２０によって知得されるルートを、ＰＥネットワークエレメント２２５にエクスポートするためにＢＧＰモジュール３４０に再配布させることができる。
【００２７】
実施形態は、再配布機能がメインＲＩＢ３６５を管理するＲＩＢモジュール３６０によって提供されることを記述しているが、プロトコル間のルートの再配布は、異なるやり方で実行することもできること（例えば、ＯＳＰＦモジュール３２０及びＢＧＰモジュール３４０はルートを直接交換することができ、メインＲＩＢ３６５とは別個の遠隔の再配布モジュールが再配布を実行してもよいなど）を理解すべきである。一実施形態によれば、システムオペレータは、ＯＳＰＦルートをＢＧＰモジュール３４０へと再配布し、ＢＧＰルートをＯＳＰＦモジュール３２０へと再配布するようにネットワークエレメント２００を構成する。
【００２８】
ＯＳＰＦモジュール３２０は、ＬＳＡの形でＯＳＰＦを実装する他のネットワークエレメントから（例えばＣＥネットワークエレメント２１５から）ルートを知得することができる（ＯＳＰＦモジュール３２０もＬＳＡを発生させる）。またＯＳＰＦモジュール３２０は、他のプロトコルから再配布されるルート（ＢＧＰモジュール３４０からの再配布ルートなど）及び／又は静的に知らされる（例えば、コマンドラインインターフェース３３０を介してネットワークエレメント２２０のオペレータによって構成される）ルートも知得することができる。新しいルートを知得したことに応じて、ＯＳＰＦモジュール３２０は、ルート追加モジュール３５０によって実行されるルート追加処理を開始する。例示的なルート追加処理を、図４及び図６を参照してさらに詳細に説明する。またＯＳＰＦモジュール３２０は、ルート撤回処理を実行するルート撤回モジュール３５５も含み、これについては、図５及び図７を参照してさらに詳細に説明する。
【００２９】
またネットワークエレメント２２０は、以下のデータ構造、即ち、リンクステートデータベース（ＬＳＤＢ）３２４、ローカルＯＳＰＦ  ＲＩＢ３２６、ローカルＢＧＢ  ＲＩＢ３２８、及びメインＲＩＢ３６５も含む。しかし、本明細書で説明する本発明の実施形態では、異なる数のデータ構造（例えば、上記データ構造の２つ以上を組み合わせたデータ構造など）が使用されてもよいことを理解すべきである。
【００３０】
ＬＳＤＢ３２４は、ＯＳＰＦモジュール３２０と結合されており、ネットワーク内のルートに関連付けられるＬＳＡを記憶する。実施形態によっては、ネットワークエレメント２２０が属するエリアごとに別個のＬＳＤＢがあり、実施形態によっては、異なるＬＳＡのタイプについて異なるＬＳＤＢがある。さらに詳細に後述するように、ＯＳＰＦモジュール３２０はＬＳＤＢ３２４にＬＳＡを追加し、ＬＳＤＢ３２４からＬＳＡを除去する。
【００３１】
ローカルＯＳＰＦ  ＲＩＢ３２６は、ＯＳＰＦモジュール３２０に結合されており、メインＲＩＢ３６５にダウンロードされないもの及びＬＳＡが発生されないものを含むＯＳＰＦルートエントリを記憶する。例えば、ローカルＯＳＰＦ  ＲＩＢ３２６は抑制されるルートを記憶することができ、抑制されるルートは、（さらに詳細に後述する）ＬＳＡが発生されないルートである。一実施形態によれば、ローカルＯＳＰＦ  ＲＩＢ３２６は、抑制される各ホストルートと、通常は当該抑制されるホストルートについてのＬＳＡと衝突することになるＬＳＩＤを有するＬＳＡを有していたはずのルートとの間の関連付けを維持する。
【００３２】
メインＲＩＢ３６５は、ＯＳＰＦモジュール３２０及びＢＧＰモジュール３４０によって選択されるルートを記憶する。本発明の理解を不明確にしないように図示されていないが、（アクティブルートエントリとも呼ばれる）メインＲＩＢ３６５内のルートのサブセットは、転送トラフィックにおいて使用するためにネットワークエレメント２２０のラインカードにダウンロードされる。ローカルＢＧＰ  ＲＩＢ３２８は、ＢＧＰモジュール３４０と結合されており、メインＲＩＢ３６５にダウンロードされないものを含むＢＧＰルートエントリを記憶する。
【００３３】
図４は、本発明の一実施形態による、ＬＳＩＤの衝突をハンドリングすることを含むルートについてのＬＳＩＤを割当てる例示的なルート追加処理を示すデータフロー図である。
【００３４】
図４に示すように、ルート追加モジュール３５０は、暫定ＬＳＩＤを生成する暫定ＬＳＩＤ生成器（tentative  LSID  generator）、及びＬＳＩＤの衝突をハンドリングするＬＳＩＤ衝突ハンドリングモジュール４２０を含む。ＯＳＰＦモジュール３２０は、知得しているルートについてルート追加モジュール３５０を呼び出す。ルートは、他のＯＳＰＦピアから知らされてもよく、異なるプロトコルによって再配布されてもよく、静的に構成されてもよい。
【００３５】
暫定ＬＳＩＤ生成器４１５は、追加されるルートについて、動作４５５で暫定ＬＳＩＤを生成する。最初は、暫定ＬＳＩＤがルートのネットワークアドレスになり、これは、ルートプレフィックス及びルートマスクのビットごとのＡＮＤ演算を実行することにより計算される。暫定ＬＳＩＤはＬＳＩＤ衝突モジュール４２０に渡される。
【００３６】
ＬＳＩＤ衝突モジュール４２０は、暫定ＬＳＩＤが異なるルートの既存のＬＳＡに割当てられたＬＳＩＤと衝突するかどうか判定する。例えば、ＬＳＩＤ衝突ハンドリングモジュール４２０は、ＬＳＤＢ３２４にアクセスして、ＬＳＤＢ内のＬＳＡのいずれかが暫定ＬＳＩＤに等しいＬＳＩＤを割当てられているかどうか判定するＬＳＩＤの衝突の検査動作４６０を実行する。衝突が生じない場合には、暫定ＬＳＩＤが割当てられ、ＬＳＩＤ割当て処理が完了する。ＯＳＰＦモジュール３２０は、それに続いて、ＬＳＡ発生モジュール４３５を呼び出して、割当てられたＬＳＩＤで当該ルートについてのＬＳＡを発生させることができる。しかし、ＬＳＩＤの衝突が生じ、追加されるルート又は既存のルート（暫定ＬＳＩＤに等しいＬＳＩＤを有するＬＳＡに関連付けられているルート）のどちらかがホストルートである場合には、ホストルートの衝突のハンドリング処理４２５が呼び出される。
【００３７】
ホストルートの衝突のハンドリング処理４２５は、ホストルートであるルートを、ホストルートの抑制動作４６５を実行することにより抑制する。追加されるルートがホストルートである場合には、ホストルートの抑制動作４６５は、当該ホストルートについてのＬＳＡを発生させないことを、したがって、当該ルートについてのＬＳＡをＬＳＤＢ３２４に含めないことを含む。既存のルート（通常は追加されるルートとのＬＳＩＤの衝突を生じたはずのルート）のＬＳＡについてのＬＳＩＤは同じままに維持される。また一実施形態では、ホストルートの抑制動作４６５は、ローカルＯＳＰＦ  ＲＩＢ３２６におけるホストルートについてのルートエントリを、ホストルートが抑制されていることを表示するように（例えば、ホストルートが抑制され、ルートについてのＬＳＡが発生されるべきでないことを表示するフラグなど）変更することも含む。一実施形態によれば、ＬＳＡ発生モジュール４３５は、そのルートエントリにおいて抑制フラグが設定されているルートをスキップする。
【００３８】
既存のルートがホストルートである場合には、ホストルートの抑制動作４６５は、ＬＳＤＢ３２４から当該ホストルートに関連付けられるＬＳＡをパージするＬＳＡのパージ動作４８０を実行することを含む（例えば、ホストルートの衝突のハンドリング処理４２５は、ＬＳＤＢ３２４にアクセスし、抑制されるホストルートについてのＬＳＡを除去する）。また一実施形態では、ホストルートの抑制動作４６５は、ローカルＯＳＰＦ  ＲＩＢ３２６におけるホストルートについてのルートエントリを、ホストルートが抑制されていることを表示するように変更することも含む。よって、ホストルートが追加されるルートであるかそれとも既存のルートであるかを問わず、いくつかの実施形態では、ホストルートの抑制動作４６５は、ローカルＯＳＰＦ  ＲＩＢ３２６におけるホストルートについてのルートエントリを、ホストルートが抑制されていることを表示するように変更することを含む。追加されるルートについてのＬＳＡは、次いで、ホストルートに関連付けられるＬＳＡに以前に割当てられたＬＳＩＤを引き継ぐ。ＬＳＡ発生モジュール４３５は次いで、ルートについての当該ＬＳＩＤを有するＬＳＡを発生させるＬＳＡの発生動作４７５を実行することができる（ＬＳＩＤは次いでＬＳＤＢ３２４に記憶される）。説明のために、抑制されるホストルートを、場合によっては、「被抑制側（“suppressee”）」ルートと呼び、通常は被抑制側ルートとのＬＳＩＤ衝突が生じたはずの被抑制側ルートに関連付けられるルートを、場合によっては、「抑制側（“suppressor”）」ルートと呼ぶ。
【００３９】
通常は抑制されるホストルートとのＬＳＩＤの衝突を生じたはずのルートは、ホストマスクルートを包含する範囲についてのＩＰ到達可能性を提供することを理解すべきである。したがって、一例として、再配布されるルートは、抑制されるＩＰホストルートの存在においてさえも、自律システムにおいて到達可能である。
【００４０】
ＯＳＰＦモジュール３２０は、被抑制側ルート及び抑制側ルートを、抑制側ルートが撤回される場合に、被抑制側ルートが自動的に追加され、ＬＳＡが、抑制側ルートに割当てられたＬＳＩＤを有する当該ルートについて発生されるように関連付ける。例えば、ホストルートの衝突のハンドリング処理４２５は、被抑制側ルートを抑制側ルートに関連付ける。本発明の一実施形態では、関連付けはローカルＯＳＰＦ  ＲＩＢ３２６内で行われる。例えば、一実施形態では、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルートエントリは、ルートが別のルートによって抑制されているかどうか、及び当該ルートの識別情報、並びにルートが別のルートを抑制しているかどうか、及び当該ルートの識別情報を表示する。
【００４１】
ＬＳＩＤの衝突が生じ、追加されるルートも既存のルートもホストルートではない場合には、非ホストルートの衝突のハンドリング処理４３０が呼び出される。一実施形態によれば、非ホストルートの衝突のハンドリング処理４３０は、ＲＦＣ２３２８に記載されているＬＳＩＤの衝突のハンドリングアルゴリズムの変更バージョンである。非ホストルートの衝突のハンドリング処理４３０は、最長のマスクを有するルートを選択し、当該ルートが抑制されるルートに関連付けられているかどうか（即ち、選択されるルートがホストの被抑制側ルートの抑制側ルートであるかどうか）判定する。現在ＬＳＤＢに存在しているＬＳＡを有する選択されるルートだけが抑制側ルートになり得ること（よって、追加されるルートは抑制側ルートになり得ないこと）を理解すべきである。
【００４２】
選択されるルートが抑制側ルートである場合には、非ホストルートの衝突のハンドリング処理４３０は、（例えば、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルートエントリを変更することによって）選択されるルート（より長いルートマスクを有するルート）からより短いルートマスクを有するルートに関連付けを移行する抑制側ルートの移行動作４７０を実行する。関連付けの移行が行われるのは、選択されるルートが異なるＬＳＩＤを割当てられることになり、選択されないルート（より短いルートマスクを有するルート）が、選択されるルートに割当てられたＬＳＩＤを引き受けることになるからである。抑制されるホストルートによって使用されるはずであったＬＳＩＤは変化しない。
【００４３】
新しい暫定ＬＳＩＤが選択されるルートについて生成される（例えば、暫定ＬＳＩＤ生成器４１５は、（ＲＦＣ２３２８によって定義されているのと同様に）選択されるルートのマスクのビットごとのＮＯＴ演算を実行し、当該結果と選択されるルートのプレフィックスとのビットごとのＯＲ演算を実行する。選択されるルートについての新しい暫定ＬＳＩＤを生成した後で、この新しい暫定ＬＳＩＤは既に（ホストルートであってもなくてもよい）異なるルートについてのＬＳＡに割当てられている可能性があるのであるから、ＬＳＩＤの衝突の検査動作４６０が再度実行される。衝突が生じない場合には、当該ルートについてのＬＳＡは暫定ＬＳＩＤで発生させることができる。選択されないルートは、選択されるルートのＬＳＡに以前に割当てられたＬＳＩＤの使用を引き継ぐ。
【００４４】
選択されるルートが抑制側ルートでない場合には、非ホストルートの衝突のハンドリング処理４３０は、ＲＦＣ２３２８によって定義されているのと同様に、選択されるルートについての新しい暫定ＬＳＩＤを生成する。新しい暫定ＬＳＩＤが異なるルートについてのＬＳＡに既に割当てられているかどうか判定するために、ＬＳＩＤの衝突の検査動作４６０が再度実行される。選択されないルートは、選択されるルートのＬＳＡに以前に割当てられたＬＳＩＤの使用を引き継ぐ。
【００４５】
図５は、本発明の一実施形態による、ルートを抑制解除することを含む例示的なルート撤回処理を示すデータフロー図である。図５には、ルート撤回モジュール３５５とルート追加モジュール３５０、ローカルＯＳＰＦ  ＲＩＢ３２６、及びＬＳＤＢ３２４との間のインタラクションが示されている。
【００４６】
ルートを撤回する命令を受け取ったことに応じて、ルート撤回モジュール３５５は抑制解除モジュール５２５を呼び出す。抑制解除モジュール５２５は、撤回されるべきルートが現在、抑制されるルートに関連付けられているかどうか（即ち、ルートが抑制側ルートであるかどうか）判定する抑制側ルートの検査動作５６０を実行する。一実施形態では、抑制側ルートの検査動作５６０は、（例えば、撤回されるべきルートについて抑制側フラグが設定されているかどうか判定するために）ローカルＯＳＰＦ  ＲＩＢ３２６における撤回されるべきルートについてのルートエントリにアクセスすることを含む。抑制側フラグが設定されている場合、抑制解除モジュール５２５は、ＬＳＩＤの値が抑制側ルートによって使用されていたＬＳＩＤであるキー（ＬＳＩＤ，ＩＰホストマスク）を用いてローカルＯＳＰＦ  ＲＩＢ３２６におけるルートルックアップを実行する。ルックアップに失敗した場合（例えば、ＮＵＬＬ値を返す場合など）には、被抑制側ルートは既に撤回されている。しかし、ルックアップがルートを返す場合には、抑制解除モジュール５２５は、当該ルートを抑制解除する（例えば、抑制側ルートによって使用されたＬＳＩＤでＬＳＡを発生させる）。別の実施形態では、ローカルＯＳＰＦ  ＲＩＢ３２６における抑制側ルートについてのルートエントリは、被抑制側ルートの識別情報も表示する。一実施形態では、抑制解除モジュール５２５は、任意選択で、撤回されるルートが現在、抑制されているかどうか（即ち、ルートが被抑制側ルートであるかどうか）も判定する。
【００４７】
撤回されるルートが抑制側ルートである場合には、抑制解除モジュール５２５は、被抑制側ルートを抑制解除する被抑制側ルートの抑制解除動作５７０を実行する。一実施形態によれば、被抑制側ルートの抑制解除動作５７０は、ローカルＯＳＰＦ  ＲＩＢ３２６における被抑制側ルートについてのルートエントリにアクセスし、ホストルートが抑制されることの表示を除去するように変更すること（例えば、ホストルートが被抑制側ルートであることを表示するフラグをクリアすること）を含む。ルート撤回モジュール３５５は、次いで、抑制解除されるホストルートを追加するために、ルート追加モジュール３５０を呼び出す。一実施形態によれば、ルート追加モジュール３５０は、抑制解除されるルートの追加動作５７５を実行し、抑制側ルートに以前に割当てられていた抑制解除されるホストルートに関連付けられるＬＳＡについてのＬＳＩＤを割当てる。
【００４８】
抑制側ルートはその被抑制側ルートを包含するのであるから、被抑制側ルートは、抑制側ルートが当該被抑制側ルートより前に撤回されるときには、到達不可能になることを理解すべきである。当該ルートを抑制解除し、当該ルートについてのＬＳＡをネットワーク全体に広告することにより、抑制解除されるホストルートは再度到達可能になる。
【００４９】
また、ルート撤回モジュール３５５は、撤回されるルートに関連付けられるＬＳＡを除去するＬＳＡのパージ動作５８０も実行する（例えば、抑制解除モジュール５２５は、ＬＳＤＢ３２４にアクセスし、撤回されるルートに関連付けられるＬＳＡを削除する）。一実施形態では、ルート撤回モジュール３５５は、ローカルＯＳＰＦ  ＲＩＢ３２６から、撤回されるルートについてのルートエントリも除去する。
【００５０】
図６は、本発明の一実施形態による、ＬＳＩＤの衝突をハンドリングすることを含む、ルート追加処理の間に実行される例示的な動作を示すフロー図である。図６は、図８及び９の例示的なＬＳＩＤ割当てを参照しながら説明されるが、図６の動作は、他のＬＳＩＤ割当てを参照して実行することもできることを理解すべきである。加えて、図６の動作は、図４の例示的な実施形態をも参照しながら説明される。しかし、図６の動作は、図４を参照して論じた本発明の実施形態以外の実施形態によって実行することもでき、図４を参照して論じた実施形態は、図６を参照して論じる実施形態とは異なる動作を実行することもできることを理解すべきである。
【００５１】
ブロック６１０で、ＯＳＰＦモジュール３２０は、図８のルート１［１０．０．０．０，２５５．２５５．０．０］についてのルート追加処理を開始する。ルートは、他のＯＳＰＦルータから知らされてもよく、異なるプロトコルによって再配布されてもよく、静的に構成されてもよい。説明のために、図８に、様々な時にネットワークエレメント２２０において知得されるルートに関連付けられるＬＳＡについてのＬＳＩＤの割当てを表す。最初は（ルート１が追加されるより前には）、ＬＳＤＢにはＬＳＡがなく、したがって、割当てられたＬＳＩＤがない。
【００５２】
フローはブロック６１０からブロック６１５に進み、そこでＬＳＩＤ割当て処理が開始する。図４を参照すると、ＬＳＩＤ割当てモジュール４１０は、ルート１についてのＬＳＩＤ割当てを開始している。フローは次いでブロック６２０に進み、そこで暫定ＬＳＩＤ生成器４１５はルート１についての暫定ＬＳＩＤを生成する。一実施形態では、暫定ＬＳＩＤは、ＲＦＣ２３２８に従って生成される。例えば、ルート１についての暫定ＬＳＩＤは、ルートのネットワークアドレス（１０．０．０．０）である。
【００５３】
フローはブロック６２０からブロック６２５に進み、そこでＬＳＩＤ衝突ハンドリングモジュール４２０は、ルート１についての暫定ＬＳＩＤが既存のルートのＬＳＩＤと衝突するかどうか判定する。現在割当てられているＬＳＩＤがないのであるから、ＬＳＩＤの衝突も生じない。したがって、フローはブロック６３０に進み、そこで処理は通常のやり方で動作する（例えば、ＬＳＡがルート１について発生され、１０．０．０．０というＬＳＩＤを割当てられる）。したがって、図８に示すように、時刻Ｔ１において、ルート１はＬＳＩＤ値１０．０．０．０に関連付けられる。
【００５４】
図８のルート２［１０．０．０．０，２５５．２５５．２５５．０］は、次の追加されるべきルートである。ルート２についての暫定ＬＳＩＤは、ルートのネットワークアドレス（１０．０．０．０）である。ルート１はＬＳＩＤ１０．０．０．０に関連付けられているのであるから、ＬＳＩＤの衝突が生じる。したがって、フローはブロック６２５からブロック６３５に進む。
【００５５】
ブロック６３５で、ホストルートはルート１であるかそれともルート２であるかの判定が行われる。これらのルートのどちらもホストルートではない（これらのルートはどちらもホストマスクを有しない）のであるから、フローはブロック６４０に進む。一実施形態によれば、ブロック６４０〜６６０を参照して説明する動作は、非ホストルートの衝突のハンドリング処理４３０によって実行される。ブロック６４０で、ルート２はルート１より長いルートマスクを有するのであるから、ルート２が選択される。フローはブロック６４０からブロック６４５に進む。
【００５６】
ブロック６４５で、非ホストルートの衝突のハンドリング処理４３０は、ルート２が抑制されるルートに関連付けられているかどうか判定する。例えば、非ホストルートの衝突のハンドリング処理４３０は、（例えば、被抑制側フラグが設定されているかどうか判定するために）ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート２についてのエントリにアクセスする。ルート２は現在、抑制されるルートに関連付けられていないのであるから、フローはブロック６５５に進む。ブロック６５５で、ビットごとのＮＯＴ演算がルート２のマスク（２５５．２５５．２５５．０）に実行され、０．０．０．２５５という値がもたらされる。フローはブロック６５５からブロック６６０に進み、そこでルート２についての新しい暫定ＬＳＩＤは、ビットごとのＮＯＴ演算の結果と暫定ＬＳＩＤとのビットごとのＯＲ演算の結果である。よって、ルート２についての新しい暫定ＬＳＩＤは０．０．０．２５５｜１０．０．０．０という値であり、これは１０．０．０．２５５に等しい。
【００５７】
フローはブロック６６０からブロック６２５に戻り、そこでＬＳＩＤ衝突ハンドリングモジュール４２０は、暫定ＬＳＩＤ１０．０．０．２５５が既存のルートに関連付けられるＬＳＩＤと衝突するかどうか判定する。図８に示すように、ＬＳＩＤ１０．０．０．２５５は現在、異なるルートについてのＬＳＡに割当てられていない。よって、フローはブロック６３０に進み、そこで処理は、通常のやり方で動作し、ＬＳＡが、ルート２について発生され、１０．０．０．２５５というＬＳＩＤを割当てられる。したがって、図８に示すように、時刻Ｔ２において、ルート１はＬＳＩＤ値１０．０．０．０に関連付けられており、ルート２はＬＳＩＤ値１０．０．０．２５５に関連付けられている。
【００５８】
図８のルート３［１０．０．０．０，２５５．２５５．２５５．２５５］は、次の追加されるべきルートである。ルート３についての暫定ＬＳＩＤは、（例えば、ブロック６２０を実行した結果としての）ルートのネットワークアドレス（１０．０．０．０）である。ルート１はＬＳＩＤ１０．０．０．０に関連付けられているのであるから、ＬＳＩＤの衝突が生じる。したがって、フローはブロック６２５からブロック６３５に進む。
【００５９】
ブロック６３５で、ＬＳＩＤ衝突ハンドリングモジュール４２０は、ホストルートはルート１であるかそれともルート３であるか判定する。ルート３はホストルートである（ルート３はホストマスクを有する）から、フローはブロック６６５に進む。一実施形態によれば、ブロック６６５及び６７０を参照して説明する動作は、ホストルートの衝突のハンドリング処理４２５によって実行される。
【００６０】
ブロック６６５で、ホストルートの衝突のハンドリング処理４２５は、ルート３がホストルートであるから、ルート３を抑制する。ルート３は追加される過程にある（よって、現在、ルート３についてのＬＳＡはない）のであるから、ルート３を抑制することは、ルート３についてＬＳＡが発生されることを防止することを含む。一実施形態では、ホストルートを抑制することは、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート３についてのルートエントリを、ルート３が抑制されることを表示するように変更すること（例えば、被抑制側フラグがローカルＯＳＰＦ  ＲＩＢ３２６におけるルート３について設定される）も含む。たとえルート３が抑制されるとしても、ルート１は、ルート３を包含する範囲についてＩＰ到達可能性を提供することを理解すべきである。
【００６１】
フローはブロック６６５からブロック６７０に進み、そこでホストルートの衝突のハンドリング処理４２５は、ルート３をルート１に関連付ける（例えば、被抑制側ルートを抑制側ルートに関連付ける）。さらに詳細に後述するように、ルート３及びルート１は、ルート１がルート３より前に撤回される場合には、ルート３についてのＬＳＡをルート１に割当てられるＬＳＩＤで発生させることができるように関連付けられる。ルート３及びルート１の間の関連付けは、異なる実施形態においては異なるやり方で実行することもできる。例えば、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート１についてのルートエントリは、それが抑制側ルートであること（例えば、抑制側フラグが設定されるなど）、及び、任意選択で、それがルート３を抑制することを表示するように変更することができる。また、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート３についてのルートエントリも、それが被抑制側ルートであること（例えば、被抑制側フラグが設定されるなど）、及び、任意選択で、それがルート１によって抑制されることを表示するように変更することができる。別の例として、ローカルＯＳＰＦ  ＲＩＢ３２６とは異なるデータ構造を、ルート３をルート１に関連付けるために使用することもできる。
【００６２】
フローはブロック６７０からブロック６７５に進み、そこでＯＳＰＦ処理が続行される。したがって、図８に示すように、時刻Ｔ３において、ルート１はＬＳＩＤ値１０．０．０．０に関連付けられており、ルート３の抑制側であり、ルート２はＬＳＩＤ値１０．０．０．２５５に関連付けられており、ルート３は（ルート１によって抑制される）被抑制側ルートである。
【００６３】
図８のルート４［１０．０．０．２５５，２５５．２５５．２５５．２５５］は、追加されるべき次のルートである。ルート４についての暫定ＬＳＩＤは、（例えば、ブロック６２０を実行した結果としての）ルートのネットワークアドレス（１０．０．０．２５５）である。ＬＳＩＤ衝突ハンドリングモジュール４２０は、値１０．０．０．２５５は現在ルート２に関連付けられているのであるから、ＬＳＩＤの衝突が生じることを判定する。したがって、フローはブロック６２５からブロック６３５に進む。
【００６４】
ブロック６３５で、ＬＳＩＤ衝突ハンドリングモジュール４２０は、ホストルートはルート２であるかそれともルート４であるか判定する。ルート４がホストルートである（ルート４がホストマスクを有する）から、フローはブロック６６５に進む。ブロック６６５で、ホストルートの衝突のハンドリング処理４２５は、ルート４がホストルートであるから、ルート４を抑制する。ルート４は、追加される過程にある（よって、現在、ルート４についてのＬＳＡはない）のであるから、ルート４を抑制することは、ＬＳＡがルート４について発生されることを防止することを含む。一実施形態では、ホストルートを抑制することは、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート４についてのルートエントリを、ルート４が抑制されることを表示するように変更することも含む。たとえルート４が抑制されるとしても、ルート２はルート４を包含する範囲についてのＩＰ到達可能性を提供することを理解すべきである。
【００６５】
フローはブロック６６５からブロック６７０に進み、そこでホストルートの衝突のハンドリング処理４２５は、ルート４をルート２と（被抑制側ルートを抑制側ルートと）、ルート２がルート４より前に撤回される場合には、ルート４についてのＬＳＡをルート２に割当てられるＬＳＩＤで発生させることができるように関連付ける。関連付けは、ルート１及び３に関して前述したのと同様に実行することができる。フローはブロック６７０からブロック６７５に進み、そこでＯＳＰＦ処理が続行される。したがって、図８に示すように、時刻Ｔ４において、ルート１はＬＳＩＤ値１０．０．０．０に関連付けられており、ルート３の抑制側であり、ルート２はＬＳＩＤ値１０．０．０．２５５に関連付けられており、ルート４の抑制側であり、ルート３は（ルート１によって抑制される）被抑制側ルートであり、ルート４は（ルート２によって抑制される）被抑制側ルートである。
【００６６】
よって、図８の時刻Ｔ４の後で、ＬＳＤＢ３２４は、（ルート１に関連付けられた）１０．０．０．０というＬＳＩＤが割当てられているＬＳＡ、及び（ルート２に関連付けられた）１０．０．０．２５５というＬＳＩＤが割当てられているＬＳＡを含む。加えて、ルート１は、（抑制される）ルート３を包含する範囲についてのＩＰ到達可能性も提供し、ルート２は（抑制される）ルート４を包含する範囲についてのＩＰ到達可能性も提供する。
【００６７】
図７は、本発明の一実施形態による、ルート撤回処理の間に実行される例示的な動作を示すフロー図である。図７を、図８及び図９の例示的なＬＳＩＤ割当てを参照しながら説明するが、図７の動作は、他のＬＳＩＤ割当てを参照して実行することもできることを理解すべきである。加えて、図７の動作は、図５の例示的な実施形態をも参照しながら説明される。しかし、図７の動作を、図５を参照して論じた本発明の実施形態以外の実施形態によって実行することもでき、図５を参照して論じた実施形態を、図７を参照して論じる実施形態とは異なる動作を実行することもできることを理解すべきである。
【００６８】
ブロック７１０で、ＯＳＰＦモジュール３２０は、図８のルート１［１０．０．０．０，２５５．２５５．０．０］についてのルート撤回処理を開始する。ルートは多くの理由（例えば、ルートに属する加入者がそのセッションを終了したなど）で撤回され得ることを理解すべきである。フローは、ブロック７１０からブロック７１５に進み、そこでルート撤回モジュール３５５は、ルート１が抑制されるルートに関連付けられているかどうか判定する。一実施形態では、ルート撤回モジュール３５５は、抑制側フラグが設定されているかどうか判定するために、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート１についてのルートエントリにアクセスする。ルート１はルート３の抑制側ルートであるから、フローはブロック７２５に進む。
【００６９】
ブロック７２５で、抑制解除モジュール５２５は、抑制されるルート（ルート３）を抑制解除する。抑制解除モジュール５２５は、抑制側ルート（ルート１）及び抑制されるルート（ルート３）の間の関連付けによって抑制されるルートの識別情報を決定する。例えば、いくつかの実施形態では、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート１についてのルートエントリは、ルート１が抑制側ルートであることを表示するが、抑制されるルートの識別情報を表示する。そのような実施形態では、ルートルックアップが、ＬＳＩＤの値がルート１についてのＬＳＡに割当てられたＬＳＩＤであるキー（ＬＳＩＤ，ＩＰホストマスク）を用いてローカルＯＳＰＦ  ＲＩＢ３２６に対して実行される。そのようなルートルックアップは、ルート３の識別情報を返す結果になる。他の実施形態では、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート１についてのルートエントリは、ルート１が抑制側ルートであることを表示し、被抑制側ルート（ルート３）の識別情報も表示する。また、ルート３の抑制解除も、抑制解除モジュール５２５が、ルート３についてのローカルＯＳＰＦ  ＲＩＢ３２６におけるエントリを、（例えば、被抑制側フラグをクリアすることなどにより）ルート３が抑制されるルートであることの表示を除去するように変更することを含む。
【００７０】
フローはブロック７２５からブロック７３０に進み、そこでルート１に関連付けられるＬＳＡは、ＬＳＤＢ３２４からパージされ、ローカルＯＳＰＦ  ＲＩＢ３２６から除去される。フローはブロック７３０からブロック７３５に進み、そこでルート３を追加する処理が開始する（例えば、フローは図６のブロック６１０に進む）。ルート３についてのルートの追加処理では、ルート１に割当てられたＬＳＩＤ（１０．０．０．０）を有するＬＳＡがルート３について発生される。したがって、図８に示すように、時刻Ｔ５において、ルート１は撤回されており、ルート２はＬＳＩＤ値１０．０．０．２５５に関連付けられており、ルート４の抑制側であり、ルート３は、今度は抑制解除され、ＬＳＩＤ値１０．０．０．０に関連付けられており、ルート４は（ルート２によって抑制される）被抑制側ルートである。
【００７１】
本発明のいくつかの実施形態では、既存のＬＳＡ（撤回されるルートについてのＬＳＡ）をパージするステップ、及び新しいＬＳＡ（現在、発生されている撤回されるＬＳＡ（例えばホストルートについてのＬＳＡなど）と同じＬＳＩＤを有するＬＳＡ）を発生させるステップは、新しいＬＳＡが単に既存のＬＳＡを置換するだけの単一のステップにおいて実行されることを理解すべきである。
【００７２】
図８のルート２［１０．０．０．０，２５５．２５５．２５５．０］は、次の撤回されるべきルートである。フローはブロック７１０からブロック７１５に進み、そこでルート撤回モジュール３５５は、ルート２が抑制されるルートに関連付けられているかどうか判定する。ルート２はルート４の抑制側ルートであるから、フローはブロック７２５に進む。ブロック７２５で、抑制解除モジュール５２５はルート４を抑制解除し、これは、ルート４についてのローカルＯＳＰＦ  ＲＩＢ３２６におけるエントリを、（例えば、被抑制側フラグをクリアすることなどにより）ルート４が抑制されるルートであることの表示を除去するように変更することを含む。
【００７３】
フローはブロック７２５からブロック７３０に進み、そこでルート２に関連付けられるＬＳＡは、ＬＳＤＢ３２４からパージされ、ローカルＯＳＰＦ  ＲＩＢ３２６から除去される。フローはブロック７３０からブロック７３５に進み、そこでルート４を追加する処理が開始する（例えば、フローは図６のブロック６１０に進む）。ルート４についてのルートの追加処理では、ルート１に割当てられたＬＳＩＤ（１０．０．０．２５５）を有するＬＳＡがルート４について発生される。したがって、図８に示すように、時刻Ｔ６において、ルート１は撤回されており、ルート２は撤回されており、ルート３はＬＳＩＤ値１０．０．０．０に関連付けられており、ルート４は、今度は抑制解除され、ＬＳＩＤ値１０．０．０．２５５に関連付けられている。
【００７４】
図８のルート３［１０．０．０．０，２５５．２５５．２５５．２５５］は、次の撤回されるべきルートである。フローはブロック７１０からブロック７１５に進み、そこでルート撤回モジュール３５５は、ルート３が抑制されるルートに関連付けられているかどうか判定する。ルート３は抑制されるルートに関連付けられていないのであるから、フローはブロック７２０に進み、そこで代替措置が講じられる（例えば、撤回処理が正常に続行され、ルート３に関連付けられるＬＳＡがＬＳＤＢ３２４からパージされるなど）。したがって、図８に示すように、時刻Ｔ７において、ルート１は撤回されており、ルート２は撤回されており、ルート３は撤回されており、ルート４は、今度は抑制解除され、ＬＳＩＤ値１０．０．０．２５５に関連付けられている。
【００７５】
図８のルート４［１０．０．０．２５５，２５５．２５５．２５５．２５５］は、次の撤回されるべきルートである。フローはブロック７１０からブロック７１５に進み、そこでルート撤回モジュール３５５は、ルート４が抑制されるルートに関連付けられているかどうか判定する。ルート４は抑制されるルートに関連付けられていないのであるから、フローはブロック７２０に進み、そこで代替措置が講じられる（例えば、撤回処理が正常に続行され、ルート４に関連付けられるＬＳＡがＬＳＤＢ３２４からパージされるなど）。したがって、図８に示すように、時刻Ｔ８において、ルート１は撤回されており、ルート２は撤回されており、ルート３は撤回されており、ルート４は撤回される。
【００７６】
図９は、本発明の一実施形態による、図８と異なる順序で到着するルートのセットについてのＬＳＩＤ割当てを示すブロック図である。図９に示すように、同じルートが図８の場合と同様に追加される（例えば、ルート１［１０．０．０．０，２５５．２５５．０．０］、ルート２［１０．０．０．０，２５５．２５５．２５５．０］、ルート３［１０．０．０．０，２５５．２５５．２５５．２５５］、及びルート４［１０．０．０．２５５，２５５．２５５．２５５．２５５］など）。しかし、これらのルートは図８と異なる順序で追加される。
【００７７】
図９のルート２［１０．０．０．０，２５５．２５５．２５５．０］は、最初の追加されるべきルートである。ブロック６１０で、ＯＳＰＦモジュール３２０は、図９のルート２についてのルート追加処理を開始する。図８を参照して説明したのと同様に、最初は（ルート２が追加される前には）、ＬＳＤＢにＬＳＡがなく、したがって、割当てられたＬＳＩＤがない。フローはブロック６１０からブロック６１５に進み、そこでＬＳＩＤ割当て処理が開始する。図４を参照すると、ＬＳＩＤ割当てモジュール４１０は、ルート２についてのＬＳＩＤ割当てを開始している。フローは次いでブロック６２０に進み、そこで暫定ＬＳＩＤ生成器４１５は、ルート２についての暫定ＬＳＩＤを生成する。一実施形態では、暫定ＬＳＩＤは、ＲＦＣ２３２８に従って生成される。例えば、ルート２についての暫定ＬＳＩＤは、ルートのネットワークアドレス（１０．０．０．０）である。
【００７８】
フローはブロック６２０からブロック６２５に進み、そこでＬＳＩＤ衝突ハンドリングモジュール４２０は、ルート２についての暫定ＬＳＩＤが既存のルートに関連付けられるＬＳＩＤと衝突するかどうか判定する。現在割当てられているＬＳＩＤがないのであるから、衝突は生じない。したがって、フローはブロック６３０に進み、そこで処理は通常のやり方で動作する（例えば、ルート２に関連付けられるＬＳＡが発生され、１０．０．０．０というＬＳＩＤ値を割当てられるなど）。したがって、図９に示すように、時刻Ｔ１において、ルート２はＬＳＩＤ値１０．０．０．０に関連付けられている。
【００７９】
ルート３［１０．０．０．０，２５５．２５５．２５５．２５５］は、次の追加されるべきルートである。ルート３についての暫定ＬＳＩＤは、ルートのネットワークアドレス（１０．０．０．０）である。ルート２はＬＳＩＤ１０．０．０．０に関連付けられているのであるから、ＬＳＩＤの衝突が生じる。したがって、フローはブロック６２５からブロック６３５に進む。
【００８０】
ブロック６３５で、ホストルートはルート２であるかそれともルート３であるかの判定が行われる。ルート３はホストルートである（ルート３はホストマスクを有する）のであるから、フローはブロック６６５に進む。ブロック６６５で、ルート３はホストルートであるから、ホストルートの衝突のハンドリング処理４２５は、ルート３を抑制する。ルート３は追加される過程にある（よって、現在、ルート３についてのＬＳＡはない）のであるから、ルート３を抑制することは、ＬＳＡがルート３について発生されることを防止することを含む。一実施形態では、ホストルートを抑制することは、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート３についてのルートエントリを、（例えば、被抑制側フラグを設定することなどにより）ルート３が抑制されることを表示するように変更することも含む。たとえルート３が抑制される場合でさえも、ルート２はルート３を包含する範囲についてのＩＰ到達可能性を提供することを理解すべきである。
【００８１】
フローはブロック６６５からブロック６７０に進み、そこでホストルート衝突ハンドリング処理４２５は、ルート３をルート２に関連付ける（例えば、被抑制側ルートを抑制側ルートに関連付けるなど）。さらに詳細に後述するように、ルート３及びルート２は、ルート２がルート３より前に撤回される場合には、ルート３についてのＬＳＡをルート２に割当てられるＬＳＩＤで発生させることができるように関連付けられる。ルートは、前述したのと同様のやり方で関連付けることができる（例えば、ホストルートの衝突のハンドリング処理は、ルート２についてのエントリを、ルート２が抑制側ルートであること、及び、任意選択で、ルート２がルート３を抑制することを表示するように変更させる）。
【００８２】
フローはブロック６７０からブロック６７５に進み、そこでＯＳＰＦ処理が続行される。したがって、図９に示すように、時刻Ｔ２において、ルート２はＬＳＩＤ値１０．０．０．０に関連付けられており、ルート３の抑制側であり、ルート３は（ルート２によって抑制される）被抑制側ルートである。
【００８３】
図９のルート４［１０．０．０．２５５，２５５．２５５．２５５．２５５］は、次の追加されるべきルートである。ルート４についての暫定ＬＳＩＤは、ルートのネットワークアドレス（１０．０．０．２５５）である（例えば、暫定ＬＳＩＤはブロック６２０を実行した結果として生成される）。ＬＳＩＤ衝突ハンドリングモジュール４２０は、ブロック６２５で、値１０．０．０．２５５は、現在、異なるルートに関連付けられていないのであるから、ＬＳＩＤの衝突は生じないことを判定する。したがって、フローはブロック６２５からブロック６３０に進み、そこで処理は通常のやり方で動作する（例えば、ルート４に関連付けられるＬＳＡが発生され、１０．０．０．２５５というＬＳＩＤ値が割当てられる）。したがって、図９に示すように、時刻Ｔ３において、ルート２はＬＳＩＤ値１０．０．０．０に関連付けられており、ルート３の抑制側であり、ルート３は（ルート２によって抑制される）被抑制側ルートであり、ルート４はＬＳＩＤ値１０．０．０．２５５に関連付けられている。
【００８４】
図９のルート１［１０．０．０．０，２５５．２５５．０．０］は、次の追加されるべきルートである。ルート１についての暫定ＬＳＩＤは、ルートのネットワークアドレス（１０．０．０．０）である（例えば、暫定ＬＳＩＤはブロック６２０を実行した結果として生成される）。ＬＳＩＤ衝突ハンドリングモジュール４２０は、ブロック６２５で、値１０．０．０．０はルート２に関連付けられているのであるからＬＳＩＤの衝突が生じることを判定する。したがって、フローはブロック６２５からブロック６３５に進む。
【００８５】
ブロック６３５で、ＬＳＩＤ衝突ハンドリングモジュール４２０は、ホストルートはルート１であるかそれともルート２であるか判定する。これらのルートはどちらもホストルートではない（これらはどちらもホストマスクを有しない）のであるから、フローはブロック６４０に進む。ブロック６４０で、ルート２はルート１より長いルートマスクを有するのであるから、ルート２が選択される。フローはブロック６４０からブロック６４５に進む。
【００８６】
ブロック６４５で、非ホストルートの衝突のハンドリング処理４３０は、ルート２が抑制されるルートに関連付けられているかどうか判定する。例えば、非ホストルートの衝突のハンドリング処理４３０は、ルート２が抑制されるルートに関連付けられているかどうか（例えば、抑制側フラグがルート２について設定されているかどうかなど）判定するために、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート２についてのエントリにアクセスする。ルート２はルート３を抑制する抑制側ルートであるから、フローはブロック６５０に進む。
【００８７】
ブロック６５０で、非ホストルートの衝突のハンドリング処理４３０は、ルート３との関連付けをルート２からルート１に移行する。言い換えると、ルート１はルート２からルート３の抑制側ルートの役割を引き継ぐのであるから、ルート１は、今度は、ルート３に関連付けられる。いくつかの実施形態では、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート２についてのルートエントリは、（例えば、抑制側フラグをクリアすることなどにより）ルート２が抑制側であることの表示を除去するように変更され、ルート１についてのルートエントリは、（当該エントリについての抑制側フラグを設定することなどにより）ルート１が抑制側ルートであることの表示を含むように変更される。いくつかの実施形態では、ルート１についてのエントリは、被抑制側ルート（ルート３など）を識別するようにも変更される。いくつかの実施形態では、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート３についてのルートエントリは、ルート１が、今度は、ルート３を抑制するルートであることを表示するように変更される。
【００８８】
ルート１は、ルート２がＲＦＣ２３２８に従って異なるＬＳＩＤを割当てられることになる（ルート２はルート１より長いルートマスクを有する）のであるから、ルート２から抑制側ルートの役割を引き継ぐ。ルート３はルート１とのＬＳＩＤの衝突を生じるはずであり、ホストルートであるから、抑制されるルート３の状況は変化しない。よって、ルート１は、ルート３を包含する範囲についてのＩＰ到達可能性を提供する。
【００８９】
フローはブロック６５０からブロック６５５に進み、そこでルート２のマスク（２５５．２５５．２５５．０）に対してビットごとのＮＯＴ演算が実行され、０．０．０．２５５という値がもたらされる。フローはブロック６５５からブロック６６０に進み、そこで新しいルート２についての暫定ＬＳＩＤは、ビットごとのＮＯＴ演算の結果と暫定ＬＳＩＤとのビットごとのＯＲ演算の結果である。よって、新しいルート２についての暫定ＬＳＩＤは、０．０．０．２５５｜１０．０．０．０という値であり、これは１０．０．０．２５５に等しい。
【００９０】
フローはブロック６６０からブロック６２５に戻り、そこでＬＳＩＤ衝突ハンドリングモジュール４２０は、暫定ＬＳＩＤ１０．０．０．２５５が既存のルートに関連付けられるＬＳＩＤと衝突するかどうか判定する。図９に示すように、ＬＳＩＤ１０．０．０．２５５は、現在、ルート４についてのＬＳＡに割当てられている。したがって、フローはブロック６３５に進み、そこでＬＳＩＤ衝突ハンドリングモジュール４２０は、ルート２及び４の１つがホストルートであるかどうか判定する。ルート４はホストルートであるから、フローはブロック６６５に進む。
【００９１】
ブロック６６５で、ホストルートの衝突のハンドリング処理４２５は、ルート４がホストルートであるから、ルート４を抑制する。ルート４は既に１つ又は複数のＬＳＡに関連付けられているのであるから、ルート４を抑制することは、ＬＳＤＢ３２４からルート４についてのＬＳＡをパージすること、及びローカルＯＳＰＦ  ＲＩＢ３２６におけるルート４についてのルートエントリを、（例えば被抑制側フラグを設定することなどにより）ルート４が被抑制側ルートであること、及び、任意選択で、ルート２によって抑制されることを表示するように変更することを含む。ルート２は、ルート４を包含する範囲についてのＩＰ到達可能性を提供することを理解すべきである。
【００９２】
フローはブロック６６５からブロック６７０に進み、そこでホストルートの衝突のハンドリング処理４２５は、ルート４をルート２に、ルート２がルート４より前に撤回される場合には、ルート４についてのＬＳＡをルート２に関連付けられるＬＳＩＤで発生させることができるように関連付ける。ルート４及びルート２の間の関連付けは、前述と同様のやり方で実行することができる。
【００９３】
フローはブロック６７０からブロック６７５に進み、そこでＯＳＰＦ処理が通常どおり続行される。したがって、図９に示すように、時刻Ｔ４において、ルート１はＬＳＩＤ値１０．０．０．０に関連付けられており、今度は、（ルート２から移行された）ルート３の抑制側ルートであり、ルート２はもはやルート３の抑制側ルートではなく、ＬＳＩＤ値１０．０．０．２５５に関連付けられており、今度は、ルート４の抑制側ルートであり、ルート３は、ルート１によって抑制される被抑制側ルートであり、ルート４は、ルート２によって抑制される被抑制側ルートである。
【００９４】
図７を参照すると、ブロック７１０で、ＯＳＰＦモジュールは、図９のルート１［１０．０．０．０，２５５．２５５．０．０］についてのルート撤回処理を開始する。フローはブロック７１０からブロック７１５に進み、そこでルート撤回モジュール３５５は、（例えば、ルート１が抑制側ルートであるかどうか判定するために、ローカルＯＳＰＦ  ＲＩＢ３２６におけるルート１についてのルートエントリにアクセスすることなどによって）ルート１が抑制されるルートに関連付けられているかどうか判定する。ルート１はルート３の抑制側ルートであるから、フローはブロック７２５に進む。ブロック７２５で、抑制解除モジュール５２５は、ルート３を抑制解除する。例えば、抑制解除モジュール５２５は、ルート３についてのローカルＯＳＰＦ  ＲＩＢ３２６におけるエントリを、ルート３が抑制されるルートであることの表示を除去するように変更する。
【００９５】
フローはブロック７２５からブロック７３０に進み、そこでルート１に関連付けられるＬＳＡはＬＳＤＢ３２４からパージされる。いくつかの実施形態では、ルート１についてのルートエントリもローカルＯＳＰＦ  ＲＩＢ３２６から除去される。フローはブロック７３０からブロック７３５に進み、そこでルート３を追加する処理が開始する（例えば、フローは図６のブロック６１０に進む）。ルート３についてのルートの追加の処理では、ルート１に割当てられたＬＳＩＤ（１０．０．０．０）を有するＬＳＡがルート３について発生される。したがって、図９に示すように、時刻Ｔ５において、ルート１は撤回されており、ルート２はＬＳＩＤ値１０．０．０．２５５に関連付けられており、ルート４の抑制側であり、ルート３は、今度は、抑制解除され、ＬＳＩＤ値１０．０．０．０に関連付けられており、ルート４は（ルート２によって抑制される）被抑制側ルートである。
【００９６】
図９のルート４［１０．０．０．２５５，２５５．２５５．２５５．２５５］は、次の撤回されるべきルートである。フローはブロック７１０からブロック７１５に進み、そこでルート撤回モジュール３５５は、ルート４が抑制されるルートに関連付けられているかどうか判定する。ルート４はそれ自体抑制されるルートであるから、ルート４は抑制されるルートに関連付けられていない（即ち、ルート４は、現在、異なるルートの抑制側ルートとして働いていない）。したがって、フローはブロック７２０に進み、そこで代替措置が講じられる（例えば、ルート４に関連付けられるＬＳＡがＬＳＤＢ３２４からパージされ、ルート２が、ルート４を抑制する抑制側ルートであることの表示が除去されるなど）。よって、図９に示すように、時刻Ｔ６において、ルート１は撤回されており、ルート２は、ＬＳＩＤ値１０．０．０．２５５に関連付けられているが、もはやルート４の抑制側ではなく、ルート３はＬＳＩＤ値１０．０．００に関連付けられており、ルート４は、今度は、撤回される。
【００９７】
図９のルート３［１０．０．０．０，２５５．２５５．２５５．２５５］は、次の撤回されるべきルートである。フローはブロック７１０からブロック７１５に進み、そこでルート撤回モジュール３５５は、ルート３が抑制されるルートに関連付けられているかどうか判定する。図９に示すように、ルート３は抑制されるルートに関連付けられていない。したがって、フローはブロック７２０に進み、そこで代替措置が講じられる（例えば、ルート３に関連付けられるＬＳＡがＬＳＤＢ３２４からパージされるなど）。したがって、図９に示すように、時刻Ｔ７において、ルート１は撤回されており、ルート２は、ＬＳＩＤ値１０．０．０．２５５に関連付けられており、ルート３は、今度は、撤回され、ルート４は撤回されている。
【００９８】
図９のルート２［１０．０．０．０，２５５．２５５．２５５．０］は、最後の撤回されるべきルートである。フローはブロック７１０からブロック７１５に進み、そこでルート撤回モジュール３５５は、ルート２が抑制されるルートに関連付けられているかどうか判定する。図９に示すように、ルート２は抑制されるルートに関連付けられていない。したがって、フローはブロック７２０に進み、そこで代替措置が講じられる（例えば、ルート２に関連付けられるＬＳＡがＬＳＤＢ３２４からパージされるなど）。したがって、図９に示すように、時刻Ｔ８において、ルート１は撤回されており、ルート２は、今度は、撤回され、ルート３は撤回されており、ルート４は撤回されている。
【００９９】
理解すべき点は、通常は既存のルートとのＬＳＩＤの衝突を生じたはずのホストルートについてＬＳＡの発生を抑制することにより、複数の異なるルートが同じＬＳＩＤを共有することが防止されるということである。よって、同じＬＳＩＤを共有する異なるルートが原因で発生し得る問題（例えば、誤ったトポロジー、データ完全性の問題、トラフィックのブラックホール化、ソフトウェアクラッシュなど）は回避される。加えて、抑制側ルートは、ホストルートを包含する範囲についてのＩＰ到達可能性も提供する。
【０１００】
本明細書で説明した本発明の実施形態は、ＯＳＰＦタイプ３ＬＳＡ（サマリＬＳＡ）、ＯＳＰＦタイプ５ＬＳＡ（外部ＬＳＡ）、及びＯＳＰＦタイプ７（ＮＳＳＡ（Not-So-Stubby  Area）外部ＬＳＡ）を含む複数のタイプのＬＳＡについて使用され得る。しかし、他のタイプのＬＳＡが本明細書で説明した本発明の実施形態において使用されてもよいことを理解すべきである。
【０１０１】
図面のフロー図には、本発明のいくつかの実施形態によって実行される特定の順序の動作が示されているが、そのような順序は例示である（例えば、代替の実施形態はそれらの動作を異なる順序で実行してもよく、いくつかの動作を組み合わせてもよく、いくつかの動作をオーバーラップさせてもよいなど）ことを理解すべきである。
【０１０２】
以上、本発明をいくつかの実施形態に関連して説明したが、本発明は前述の実施形態だけに限定されるものではなく、添付の特許請求の範囲の趣旨及び範囲内の改変及び変更を伴って実施することができることを当業者は理解するであろう。よって説明は、限定ではなく例示とみなされるべきである。
【図１】
0005597710.tif 000002
【図２】
0005597710.tif 000003
【図３】
0005597710.tif 000004
【図４】
0005597710.tif 000005
【図５】
0005597710.tif 000006
【図６】
0005597710.tif 000007
【図７】
0005597710.tif 000008
【図８】
0005597710.tif 000009
【図９】
0005597710.tif 000010