JP6450276B2

JP6450276B2 - 集約経路計算システムおよび集約経路計算方法

Info

Publication number: JP6450276B2
Application number: JP2015149095A
Authority: JP
Inventors: 俊宏横井; 高橋　賢; 賢高橋; 隆典岩井
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2015-07-29
Filing date: 2015-07-29
Publication date: 2019-01-09
Anticipated expiration: 2035-07-29
Also published as: JP2017034321A

Description

本発明は、ＩＰネットワークにおける経路集約に関する集約経路計算システムおよび集約経路計算方法に関する。

一般的に、ＩＰネットワークにおいて、流通する経路数を削減するために、複数の経路をまとめて１つの経路に置き換える経路集約技術が用いられる。一般的に、効率的に経路集約が行えるように経路設計を行う。

当初ＩＰアドレスは３つのクラスに分けられて割り当てが行われていた。各クラスは８ビット、１６ビット、２４ビットと８ビットおきに分けられた。しかしこれは、アドレス数にすると、２５６個、６５５３６個、１６７７７２１６個に分けられることになり、最も少ない２５６個では少ないが、次の６５５３６個では多すぎるなど非効率な割り当てとなっていた。これに対し、非特許文献１に記載のように、プレフィックス長を可変長で割り当て可能とするＣＩＤＲ（Classless Inter-Domain Routing）が考案された。これにより、クラスに縛られない効率的なアドレス割り当てが可能となった。また、複数の連続するプレフィックスを集約して１つのアドレスとして扱い、インターネットのルーティングテーブルのエントリ数を削減する事を可能とした。

ルータでは、予め集約する単位を装置に設定して該当の経路が配布された場合に、集約して他の装置に経路広告するような機能が具備されている（非特許文献２）。
図９は、比較例のＩＰネットワーク７の構成図である。
ＩＰネットワーク７は、ルータ９ｄと、このルータ９ｄにスター接続されたエッジルータ９ａ，９ｂ，９ｃとを含んで構成される。このＩＰネットワーク７では、経路数を削減するために、複数の経路を１つの経路に置きかえる経路集約が行われる。比較例では、効率的に集約できるように経路が設計され、予めエッジルータ６１ａ〜６１ｃに経路集約する設定がされている。
エッジルータ９ａは、内部ネットワーク６ａのエッジルータ６１ａに接続され、このエッジルータ６１ａは、10.1.1.0/24から10.1.100.0/24までの経路を管理している。エッジルータ９ａは、これら内部ネットワーク６ａの各経路の集約経路である10.1.0.0/16が設定されており、この集約経路を広告する。
同様にエッジルータ９ｂは、内部ネットワーク６ｂのエッジルータ６１ｂに接続され、このエッジルータ６１ｂは、10.2.1.0/24から10.2.100.0/24までの経路を管理している。エッジルータ９ｂは、これら内部ネットワーク６ｂの各経路の集約経路である10.2.0.0/16が設定されており、この集約経路を広告する。
更にエッジルータ９ｃは、内部ネットワーク６ｃのエッジルータ６１ｃに接続され、このエッジルータ６１ｃは、10.3.1.0/24から10.3.100.0/24までの経路を管理している。エッジルータ９ｃは、これら内部ネットワーク６ｃの各経路の集約経路である10.3.0.0/16が設定されており、この集約経路を広告する。

Network Working Group,"Request for Comments: 4632,Classless Inter-domain Routing (CIDR):The Internet Address Assignment and Aggregation Plan",[online],2006,The Internet Society,［平成２７年７月１３日検索］,インターネット<URL:https://tools.ietf.org/html/rfc4632> 「BGP ケーススタディ」,[online],CISCO,2010年5月7日,［平成２７年７月１３日検索］,インターネット<URL:http://www.cisco.com/cisco/web/support/JP/100/1007/1007994_bgp-toc-j.html#cidragg>

図９の比較例では、予めどのような経路が広告されるか把握できる場合を示しており、この場合には経路集約を実施可能である。しかし、外部の管理していない別網から経路が広告されるような場合は、どのような経路が広告されるかを予め把握する事ができず、経路集約を実施できない。このように経路集約できない場合、ネットワーク内の流通経路が増加するが、それによって経路テーブルエントリが溢れて通信不能となるおそれがあり、障害時の経路切り替え計算が長時間化してパケットロスが増大するおそれがある。

具体的にいうと例えば、ＶＰＮ（Virtual Private Network）サービスを提供するキャリア網では、ＶＰＮサービスのユーザの経路はユーザが自由に設計するものであるため事前に把握する事はできず、経路集約できない。さらに、ＶＰＮサービスは１つの物理網に複数のユーザが重畳されるため、経路数が膨大となる恐れがある。これを図１０の比較例にて説明する。

図１０は、比較例のＩＰネットワークの問題点の説明図である。
比較例のＩＰネットワーク７は、ルータ９ｄと、このルータ９ｄにスター接続されたエッジルータ９ａ，９ｂ，９ｃとを含んで構成される。
エッジルータ９ａは、外部の拠点群８１に接続され、この拠点群８１は、10.1.1.0/24から10.1.100.0/24までの経路を含んでいる。外部から広告される経路は予め把握することができないので、これらの外部の経路を集約することができない。エッジルータ９ａは、拠点群８１の各経路を広告する。

同様にエッジルータ９ｂは、外部の拠点群８１，８２に接続され、拠点群８２は、10.2.1.0/24から10.2.100.0/24までの経路を含んでいる。エッジルータ９ｂは、拠点群８１，８２の各経路を広告する。更にエッジルータ９ｃは、外部の拠点群８３に接続され、この拠点群８３は、10.3.1.0/24から10.3.100.0/24までの経路を含んでいる。エッジルータ９ｃは、拠点群８３の各経路を広告する。
各エッジルータ９ａ，９ｂ，９ｃは、10.1.1.0/24から10.1.100.0/24までの経路、10.2.1.0/24から10.2.100.0/24までの経路、10.3.1.0/24から10.2.100.0/24までの経路をそれぞれの経路エントリテーブルに格納するので、この経路テーブルエントリが溢れて通信不能となるおそれがある。

更にルータ９ｄとエッジルータ９ａとの間に通信障害が発生した場合を考える。エッジルータ９ｃが10.1.1.0/24から10.1.100.0/24までの経路にパケットを送信する際、通常はエッジルータ９ａを介して送信するが、通信障害以降はエッジルータ９ｂを介して送信する。この経路切り替え計算が長時間化すると、パケットロスが増大するおそれがある。

本発明は、前記した問題を解決し、自身のネットワークの外部の経路を集約することを課題とする。

前記課題を解決するため、請求項１に記載の発明では、外部と接続する各エッジ装置と、各前記エッジ装置で受信した経路を集約するコントローラとを含んで構成される集約経路計算システムであって、前記コントローラは、各前記エッジ装置から経路を収集する経路収集部と、前記エッジ装置ごとに、前記経路収集部が収集した経路をアドレスの昇順にソートし、ソートした第１番目から順番に経路を集約し、第１番目から第ｉ番目までの経路の集約が他のエッジ装置から収集した経路と交差した場合、第１番目から第（ｉ−１）番目までの経路を集約して集約経路を算出する集約計算部と、前記集約計算部が計算した集約経路がネットワークに広告されるように各前記エッジ装置を設定する集約経路設定部と、を備えることを特徴とする集約経路計算システムとした。

このようにすることで、自身のネットワークの外部の経路を集約することができ、更にネットワークの経路数を効率的に削減することができる。

請求項２に記載の発明では、外部と接続する各エッジ装置と、各前記エッジ装置で受信した経路を集約するコントローラとを含んで構成される集約経路計算システムであって、前記コントローラは、各前記エッジ装置から経路を収集する経路収集部と、前記エッジ装置ごとに、前記経路収集部が収集した経路をアドレスの昇順にソートし、ソートした第１番目から順番に経路を集約し、第１番目から第ｉ番目までの経路の集約が他のエッジ装置から収集した経路と交差した場合、第１番目から第（ｉ−１）番目までの経路を集約して集約経路を算出する集約計算部と、前記集約計算部が計算した集約経路をネットワークに広告する集約経路設定部と、を備えることを特徴とする集約経路計算システムとした。

このようにすることで、自身のネットワークの外部の経路を集約して広告することができ、更にネットワークの経路数を効率的に削減することができる。

請求項３に記載の発明では、前記集約計算部は、前記エッジ装置ごとに、前記経路収集部が収集した経路を全て集約しても、他のエッジ装置から収集した経路と交差しなかった場合、全ての経路を集約した集約経路を算出する、ことを特徴とする請求項１または請求項２に記載の集約経路計算システムとした。

このようにすることで、ネットワークの経路数を効率的に削減することができる。

請求項４に記載の発明では、前記集約計算部は、各前記エッジ装置が収集した経路から集約経路を計算したのち、最も多くの集約経路を有する一のエッジ装置につき、当該一のエッジ装置が有する集約経路を更に集約した二次集約経路を計算する、ことを特徴とする請求項１または請求項２に記載の集約経路計算システムとした。

このようにすることで、最も多くの集約経路を有する一のエッジ装置に係る経路数を更に削減することができる。

請求項５に記載の発明では、前記集約計算部は、前記一のエッジ装置以外の他のエッジ装置につき、当該他のエッジ装置が有する集約経路から、既に作成した二次集約経路の生成に使用した集約経路と互いに交差しないように集約した二次集約経路を計算する、ことを特徴とする請求項４に記載の集約経路計算システムとした。

このようにすることで、一のエッジ装置以外の他のエッジ装置についても経路数を削減することができる。

請求項６に記載の発明では、前記集約計算部は、複数の経路のアドレスのビットパターンに共通する上位部分が１、共通しない下位部分が０のサブネットマスク、および、当該サブネットマスクと経路との論理積であるアドレスを計算して集約経路とする、ことを特徴とする請求項１または請求項２に記載の集約経路計算システムとした。

このようにすることで、外部の経路を手作業によらずに集約することができる。

請求項７に記載の発明では、外部と接続する各エッジ装置で受信した経路を集約するコントローラが実行する集約経路計算方法であって、前記コントローラは、各前記エッジ装置から経路を収集するステップと、前記エッジ装置ごとに、収集した経路をアドレスの昇順にソートするステップと、ソートした第１番目から順番に経路を集約するステップと、第１番目から第ｉ番目までの経路の集約が他のエッジ装置から収集した経路と交差した場合、第１番目から第（ｉ−１）番目までの経路を集約して集約経路を計算するステップと、計算した集約経路が広告されるように各前記エッジ装置を設定するステップと、を実行することを特徴とする集約経路計算方法とした。

請求項８に記載の発明では、外部と接続する各エッジ装置で受信した経路を集約するコントローラが実行する集約経路計算方法であって、前記コントローラは、各前記エッジ装置から経路を収集するステップと、前記エッジ装置ごとに、収集した経路をアドレスの昇順にソートするステップと、ソートした第１番目から順番に経路を集約するステップと、第１番目から第ｉ番目までの経路の集約が他のエッジ装置から収集した経路と交差した場合、第１番目から第（ｉ−１）番目までの経路を集約して集約経路を計算するステップと、計算した集約経路をネットワークに広告するステップと、を実行することを特徴とする集約経路計算方法とした。

本発明によれば、自身のネットワークの外部の経路を集約することが可能となる。

本実施形態における集約経路計算システムの一例の構成図である。集約計算結果の一例を示す図である。集約経路計算処理のフローチャートである。グルーピング処理のフローチャートである。一次集約経路計算処理のフローチャートである。各集約経路計算処理のフローチャートである。交差判定処理のフローチャートである。二次集約経路計算処理のフローチャートである。比較例のＩＰネットワークの構成図である。比較例のＩＰネットワークの問題点の説明図である。

次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
図１は、本実施形態における集約経路計算システム１の一例の構成図である。
集約経路計算システム１は、ルータ９ｄと、このルータ９ｄにスター接続されたエッジルータ９ａ，９ｂ，９ｃと、これらの通信ノードを制御するコントローラ２を含んで構成され、自身のネットワークの外部の経路の集約を行う。ルータ９ｄと、このルータ９ｄにスター接続されたエッジルータ９ａ，９ｂ，９ｃとは、ＩＰネットワーク７を構成する。
エッジルータ９ａは、外部の拠点８ａ，８ｂ，８ｃに接続される。拠点８ａは10.1.1.0/24の経路を有し、拠点８ｂは10.1.7.0/24の経路を有し、拠点８ｃは、10.1.100.0/24の経路を有する。このエッジルータ９ａは、集約計算においてノード＃１として処理される。

同様にエッジルータ９ｂは、外部の拠点８ａ〜８ｅに接続される。拠点８ｄは10.1.8.0/24の経路を有し、拠点８ｅは10.2.1.0/24の経路を有する。拠点８ａ〜８ｃは、エッジルータ９ａ，９ｂの両方に接続される。エッジルータ９ｂは、集約計算においてノード＃２として処理される。
エッジルータ９ｃは、外部の拠点８ｆ，８ｇに接続される。拠点８ｆは10.3.1.0/24の経路を有し、拠点８ｇは10.3.1.0/24の経路を有する。このエッジルータ９ｃは、集約計算においてノード＃３として処理される。

本実施形態のコントローラ２は、経路収集部２１、集約計算部２２、集約経路設定部２３を備えており、エッジルータ９ａ〜９ｃなどを制御する。コントローラ２は、外部と接続するエッジルータ９ａ〜９ｃなどの通信ノードで受信した経路をに通知し経路を収集する。コントローラ２は、エッジルータ９ａ〜９ｃで経路を収集した後、集約経路を計算し、適切に集約経路が広告されるように各エッジルータ９ａ〜９ｃに設定を行う。これによって、エッジルータ９ａ〜９ｃは、外部から取得した経路を集約してネットワーク内に広告する。

経路収集部２１は、自身のネットワークの外部の経路情報をエッジルータ９ａ〜９ｃから収集する。経路収集部２１が収集する経路情報は、宛先アドレスおよび広告された通信ノード情報である。また、収集方法は、エッジルータ９ａ〜９ｃからの通知を経路収集部２１が受信する方法と、コントローラ２から定期的にエッジルータ９ａ〜９ｃが取得する外部等の経路情報を取得する方法のいずれでもよく、限定されない。
経路収集部２１が通信ノードからの通知を受信する形態としては、コントローラ２と通信ノード間でBGP（Border Gateway Protocol：RFC4271）やBMP（BGP Monitoring Protocol：draft-ietf-grow-bmp-08）といったプロトコルによって実現できる。また、コントローラ２が定期的に情報を取得する形態は、SNMP（Simple Network Management Protocol）によって実現できる。

集約計算部２２は、経路収集部２１で収集した経路に基づいて集約経路を計算し、集約経路テーブル２４を作成する。集約計算のアルゴリズム例は以降で示す。
集約経路設定部２３は、集約計算部２２で作成した集約経路テーブル２４により、経路を通信ノードに通知する。経路通知方法は、通信ノードへ集約経路を広告させる設定を実施する方法と、集約経路の広告先通信ノードへ経路情報を直接通知する方法のうちいずれでもよく、限定されない。
通信ノードへ集約経路を広告させる設定は、netconf(RFC6241等)を始めとする通信ノードの設定を変更するプロトコルで実現可能である。また、集約経路の広告先通信ノードへの経路情報の直接通知は、BGPのプロトコルで実現可能である。

図２は、集約計算結果の一例を示す図である。
ＧＰ欄には、広告されたノードの組み合わせ単位でグルーピングされたグループ番号が格納される。
ノード欄には、各エッジルータ９ａ〜９ｃを示すノード番号が格納される。
詳細経路アドレス欄には各ノードが収集する経路のアドレスが格納され、詳細経路サブネットマスク欄には、各ノードが収集する経路のアドレスサブネットマスクが格納される。

一次集約経路アドレス欄には一次集約した経路のアドレスが格納され、一次集約経路サブネットマスク欄には、一次集約した経路のアドレスサブネットマスクが格納される。この一次集約経路は、各詳細経路を一次集約したものである。

二次集約経路アドレス欄には二次集約した経路のアドレスが格納され、二次集約経路サブネットマスク欄には、二次集約した経路のアドレスサブネットマスクが格納される。この二次集約経路は、各一次集約経路を更に集約したものである。

図３は、集約経路計算処理のフローチャートである。
経路収集部２１が各エッジルータ９ａ〜９ｃから詳細経路を収集したのち、集約計算部２２が図３の処理を開始する。
集約計算部２２は最初、広告されたノードの組み合わせ単位でグルーピングする（ステップＳ１０）。例えばノード＃１，＃２に同一経路が広告された場合は、これら経路を同一グループとする。次いで集約計算部２２は、一次集約経路計算により他グループの詳細経路を含まない集約経路を作成し（ステップＳ１１）、二次集約経路計算により他グループの詳細経路が含まれる集約経路を作成する（ステップＳ１２）。二次集約経路が他グループの詳細経路を含んでいる場合でも、通信パケットは、ロンゲストマッチによって適切な宛先に転送される。
各ステップＳ１０〜Ｓ１２の詳細を以下図４、図５、図８で説明する。

図４は、グルーピング処理のフローチャートであり、図３のステップＳ１０の処理によって呼び出される。
集約計算部２２は、所定のルールに従って、収容する通信ノードの組み合わせで詳細経路をグルーピングし、集約経路テーブル２４（図１参照）に出力する（ステップＳ２０）。ここで集約計算部２２は、各グループをノード数が少ない順に並べるルールと、ノード数が同数の場合には、より若いノード番号を持つものから順番に並べるルールに従ってグルーピングする。
集約計算部２２は更に、各グループの詳細経路をアドレスの昇順にソートし（ステップＳ２１）、図４のグルーピング処理を終了する。ここで集約計算部２２は、アドレスの数字が小さいものから大きいものまで順番に並べ、アドレスが同一の場合は、サブネットマスクの数字が大きいものから小さいものまで順番に並べる。

図５は、一次集約経路計算処理のフローチャートであり、図３のステップＳ１１の処理によって呼び出される。
集約計算部２２は、この一次集約経路計算により、集約経路テーブル２４（図１参照）に一次集約経路（図２参照）を出力する。
集約計算部２２は、グループgのi番目の詳細経路をX_g_iとしたのち、各変数g,s,tに、g=1,s=1,t=2を設定する（ステップＳ３０）。ここで変数gはグループを示すインデックスである。変数s,tは、各詳細経路を示すインデックスである。

集約計算部２２は、詳細経路X_g_s，X_g_tを含む最もプレフィックス長の長い集約経路X_stを集約経路計算（図６参照）により導出する（ステップＳ３１）。具体的にいうと、図２に示す各詳細経路にてグループgが1のとき、X_1_1である10.1.8.0/24の詳細経路と、X_1_2である10.2.0.0/24の詳細経路を含む最もプレフィックス長の長い集約経路X_stを計算する。このとき集約経路X_stは10.0.0.0/14となる。グループgが3のとき、X_3_1である10.1.1.0/24の詳細経路と、X_3_2である10.1.7.0/24の詳細経路を含む最もプレフィックス長の長い集約経路X_12を計算する。このとき集約経路X_12は10.1.0.0/21となる。

集約計算部２２は、この集約経路X_stに別グループの経路が含まれるか否かを集約交差判定（図７参照）により判定する（ステップＳ３２）。集約計算部２２は、別グループの経路が含まれない（交差しない）場合は（ステップＳ３２→Ｎｏ）、変数tをインクリメントする（ステップＳ３８）。具体的にいうと、図２に示す各詳細経路では、グループ3の集約経路X_12てある10.1.0.0/21が、別グループの経路が含まれていない場合である。

集約計算部２２は、変数tがグループgの経路数を超えるか否かを判定する（ステップＳ３９）。集約計算部２２は、変数tがグループgの経路数を超えない場合には、ステップＳ３１の処理に戻って新たな詳細経路の集約を試み、超える場合には、集約経路X_s(t-1)を出力し（ステップＳ４０）、ステップＳ４１の処理に進む。

集約計算部２２は、別グループの経路が含まれる（交差する）場合には（ステップＳ３２→Ｙｅｓ）、変数tをディクリメントし（ステップＳ３３）、集約経路X_stを一次集約経路として出力し（ステップＳ３４）、変数s=t+1、t=t+2とする（ステップＳ３５）。ここで集約経路X_stは、詳細経路X_g_s，X_g_tを含む最小の集約経路である。具体的にいうと、図２に示す各詳細経路では、グループ1の集約経路X_12が10.0.0.0/14のとき、グループ3の10.1.1.0/24の詳細経路が含まれる。このときには、集約経路X_11を一次集約経路として出力する。ここで集約経路X_11とは、詳細経路X_1_1と詳細経路X_1_1とを含む最小の集約経路であり、則ち詳細経路X_1_1そのものである。

ここで集約計算部２２は、変数tがグループの経路数を超えるか否かを判定し（ステップＳ３６）、超える場合には、詳細経路X_g_sを一次集約経路としてステップＳ４１の処理に進む。ステップＳ３６にて変数tがグループの経路数を超えない場合、集約計算部２２は、変数sがグループ経路数を超えるか否かを判定し（ステップＳ３７）、超える場合は、ステップＳ４１の処理へ進む。それ以外は、ステップＳ３１の処理に戻る。

ステップＳ４１にて、集約計算部２２は、当該グループの全アドレスに対して処理が終わったので、グループのインデックスgをインクリメントしてs=1,t=2に初期化する。集約計算部２２は、全グループに対して処理を行ったか否かを判定する（ステップＳ４２）。集約計算部２２は、未だ処理していないグループが有ったならばステップＳ３１の処理に戻り、全てのグルーブの処理を行ったならば、図５の処理を終了する。

図６は、各集約経路計算処理のフローチャートであり、図５のステップＳ３１の処理と、後記する図８のステップＳ８４，Ｓ８５の処理にて呼び出される。
集約計算部２２は、詳細経路X_g_s，X_g_tのアドレスの排他的論理和を算出してT_stに代入し（ステップＳ５０）、T_stのビットを反転する（ステップＳ５１）。具体的にいうと、詳細経路が10.1.1.0/24と10.1.7.0/24のとき、T_stは255.255.249.255となる。

集約計算部２２は、変数kを１で初期化し（ステップＳ５２）、変数kが詳細経路X_g_s，X_g_tのサブネットマスクのうち小さい方のプレフィックス長Pre_min以下か否かを判定する（ステップＳ５３）。集約計算部２２は、変数kがプレフィックス長Pre_min以下ならば、ステップＳ５４の処理に進み、変数kがプレフィックス長Pre_minを超えるならば、詳細経路X_g_sのアドレスを集約アドレスとしてY_stに代入し（ステップＳ５８）、ステップＳ５９の処理に進む。

ステップＳ５４にて、集約計算部２２は、T_stの上位kビット目が１であるか否かを判定する（ステップＳ５４）。集約計算部２２は、T_stの上位kビット目が１であるならば、kをインクリメントして（ステップＳ５５）ステップＳ５３の処理に戻り、T_stの上位kビット目が１でないならば、ステップＳ５６の処理に進む。ステップＳ５６にて、集約計算部２２は、T_stの上位kビット目から末尾のビットまでを全て０として集約サブネットマスクとし、その後T_stと詳細経路X_g_sのアドレスとの論理積を算出し、これを集約アドレスとしてY_stに代入し（ステップＳ５７）、ステップＳ５９の処理に進む。
具体的にいうと、ステップＳ５４にてT_stが255.255.249.255のとき、ステップＳ５７にてT_stは255.255.248.0となり、Y_stは10.1.0.0となる。
ステップＳ５９にて、集約計算部２２は、集約サブネットマスクをT_st、集約アドレスY_stとして出力し、図６の処理を終了する。

図７は、交差判定処理のフローチャートであり、図５のステップＳ３２の処理と、後記する図８のステップＳ８６，Ｓ９２の処理にて実行される。
ここでは、交差判定元経路のアドレスをXとし、サブネットマスクをT_xとする。その他経路のアドレスをG_iとし、サブネットマスクをT_g_iとする。ここで変数iは、その他経路のうち１つを示すインデックスであり、変数gはグループのインデックスである。
最初、集約計算部２２は、変数iを1に初期化する（ステップＳ７０）。

ステップＳ７１にて、集約計算部２２は、交差判定元経路のサブネットマスクT_xとその他のアドレスのサブネットマスクT_g_iと交差判定元経路のアドレスXとの論理積を算出し、交差判定元経路のサブネットマスクT_xとその他のアドレスのサブネットマスクT_g_iとその他経路のアドレスG_iとの論理積を算出し、これらの値が等しいか否かを判定する。集約計算部２２は、これらの値が等しいと判定したならば、交差が存在すると判定し（ステップＳ７５）、図７の処理を終了する。

集約計算部２２は、これらの値が等しくないと判定したならば、変数iをインクリメントして（ステップＳ７２）、その他経路数以下であるか否かを判定する（ステップＳ７３）。集約計算部２２は、変数iがその他経路数以下ならば、ステップＳ７１の処理に戻る。集約計算部２２は、変数iがその他経路数を超えたならば、交差が存在しないと判定し（ステップＳ７４）、図７の処理を終了する。

図８は、二次集約経路計算処理のフローチャートであり、図３のステップＳ１２から呼び出される。
集約計算部２２は、二次集約経路計算により集約経路テーブル２４（図３参照）に二次集約経路を出力する。ここではグループgのi番目の一次集約経路をX1_g_i、二次集約経路をX2_iとする。

ステップＳ８０にて、集約計算部２２は、二次集約を作成していない未処理グループが有るか否かを判定する。集約計算部２２は、未処理グループが無ければ図８の処理を終了する。
未処理グループが有れば、集約計算部２２は、二次集約を作成していないグループの中で一次集約経路が最も多いグループgを選択し（ステップＳ８１）、グループの一次集約経路が同数の場合は、若番のグループを選択する。具体的にいうと、図２に示す各詳細経路では、グループ3が最初に選択される。

集約計算部２２は、変数i=1とし、変数kに現時点での二次集約経路数を代入する（ステップＳ８２）。集約計算部２２は、変数kが0であるか否かを判定し（ステップＳ８３）、k=0の場合には、グループg内の全ての一次集約経路を集約し、1つの二次集約経路として出力し（ステップＳ８４）、ステップＳ８０に戻る。集約計算部２２は、変数kが0以外の場合は、一次集約経路X1_g_s，X1_g_tの集約経路Y1_stを求める（ステップＳ８５）。

ステップＳ８６にて、集約計算部２２は、集約経路Y1_stに二次集約経路X2_iを生成するのに使用した一次集約経路が交差するか否かを判定し、交差する場合にはステップＳ９２の処理に進む。集約計算部２２は、ステップＳ８６の判定にて交差しない場合、変数iをインクリメントし（ステップＳ８７）、変数iが変数k以下であるか否かを判定する（ステップＳ８８）。集約計算部２２は、変数iが変数k以下ならばステップＳ８６の処理に戻り、変数iが変数kを超えるならば、変数tをインクリメントする（ステップＳ８９）。

集約計算部２２は、変数tがグループgの一次集約経路数よりも大きい場合には（ステップＳ９０）、Y1_s(t-1)を二次集約経路として出力し（ステップＳ９１）、ステップＳ８０の処理に戻る。集約計算部２２は、変数tがグループgの一次集約経路数以下の場合は、ステップＳ８６の処理に戻り、交差判定を繰り返す。

ステップＳ９２にて、集約計算部２２は、二次集約経路X2_iが集約経路Y1_stに含まれる一次集約経路と交差するかを判定する。集約計算部２２は、交差する場合には、集約経路Y1_s(t-1)を二次集約経路として出力し（ステップＳ９３）、変数s=t、t=t+1を設定する（ステップＳ９４）。交差しない場合には、変数iをインクリメントして（ステップＳ９５）、ステップＳ８６の処理に戻る。
これら一連の処理により、集約計算部２２は、二次集約経路を導出することができる。なお、本実施形態の集約経路設定部２３は、各通信ノードに二次集約経路を広告させる設定を実施するが、集約経路の広告先通信ノードに経路情報を通知してもよく、限定されない。

比較例では、外部の経路は制御対象でなかった。これに対して本実施形態によれば、外部から広告される経路を集約して自ネットワーク内に広告することで、外部に対して影響を与えずに、自ネットワーク内に広告される経路数が削減できる。それによって、通信ノードの経路テーブルの利用率を低減し、さらに障害時の経路切り替え時間を短縮できる。

（変形例）
本実施の形態に係る集約経路計算システムは、前記したような処理を実行させるプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体（ＣＤ−ＲＯＭ等）に記憶して提供することが可能である。また、そのプログラムを、インターネット等のネットワークを通して提供することも可能である。
本発明は、上記実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で、変更実施が可能であり、例えば、次の（ａ）〜（ｃ）のようなものがある。

（ａ）集約経路計算システム１は、一次集約処理と二次集約処理とを実施し、二次集約経路が各通信装置の経路テーブルに格納されるようにエッジルータを設定している。しかし、これに限られず、一次集約処理のみを実施し、一次集約経路が各通信装置の経路テーブルに格納されるようにエッジルータを設定してもよい。
（ｂ）集約経路計算システム１は、任意のタイミングで集約処理を実行してよい。例えば集約経路計算システム１は、定期的に集約処理を実行してもよく、外部から新たな経路情報を取得する度に集約処理を実行してもよく、限定されない。
（ｃ）二次集約処理における最初の処理グループは、一次集約経路が最多のグループに限定されない。

１集約経路計算システム
２コントローラ
２１経路収集部
２２集約計算部
２３集約経路設定部
２４集約経路テーブル
８ａ〜８ｇ拠点
６ａ〜６ｃ内部ネットワーク
６１ａ〜６１ｃエッジルータ
７ＩＰネットワーク
８１〜８３拠点群
９ａ〜９ｃエッジルータ（エッジ装置）
９ｄルータ

Claims

外部と接続する各エッジ装置と、
各前記エッジ装置で受信した経路を集約するコントローラとを含んで構成される集約経路計算システムであって、
前記コントローラは、
各前記エッジ装置から経路を収集する経路収集部と、
前記エッジ装置ごとに、前記経路収集部が収集した経路をアドレスの昇順にソートし、ソートした第１番目から順番に経路を集約し、第１番目から第ｉ番目までの経路の集約が他のエッジ装置から収集した経路と交差した場合、第１番目から第（ｉ−１）番目までの経路を集約して集約経路を算出する集約計算部と、
前記集約計算部が計算した集約経路がネットワークに広告されるように各前記エッジ装置を設定する集約経路設定部と、
を備えることを特徴とする集約経路計算システム。
外部と接続する各エッジ装置と、
各前記エッジ装置で受信した経路を集約するコントローラとを含んで構成される集約経路計算システムであって、
前記コントローラは、
各前記エッジ装置から経路を収集する経路収集部と、
前記エッジ装置ごとに、前記経路収集部が収集した経路をアドレスの昇順にソートし、ソートした第１番目から順番に経路を集約し、第１番目から第ｉ番目までの経路の集約が他のエッジ装置から収集した経路と交差した場合、第１番目から第（ｉ−１）番目までの経路を集約して集約経路を算出する集約計算部と、
前記集約計算部が計算した集約経路をネットワークに広告する集約経路設定部と、
を備えることを特徴とする集約経路計算システム。
前記集約計算部は、前記エッジ装置ごとに、前記経路収集部が収集した経路を全て集約しても、他のエッジ装置から収集した経路と交差しなかった場合、全ての経路を集約した集約経路を算出する、
ことを特徴とする請求項１または請求項２に記載の集約経路計算システム。
前記集約計算部は、各前記エッジ装置が収集した経路から集約経路を計算したのち、最も多くの集約経路を有する一のエッジ装置につき、当該一のエッジ装置が有する集約経路を更に集約した二次集約経路を計算する、
ことを特徴とする請求項１または請求項２に記載の集約経路計算システム。
前記集約計算部は、前記一のエッジ装置以外の他のエッジ装置につき、当該他のエッジ装置が有する集約経路から、既に作成した二次集約経路の生成に使用した集約経路と互いに交差しないように集約した二次集約経路を計算する、
ことを特徴とする請求項４に記載の集約経路計算システム。
前記集約計算部は、複数の経路のアドレスのビットパターンに共通する上位部分が１、共通しない下位部分が０のサブネットマスク、および、当該サブネットマスクと経路との論理積であるアドレスを計算して集約経路とする、
ことを特徴とする請求項１または請求項２に記載の集約経路計算システム。
外部と接続する各エッジ装置で受信した経路を集約するコントローラが実行する集約経路計算方法であって、
前記コントローラは、
各前記エッジ装置から経路を収集するステップと、
前記エッジ装置ごとに、収集した経路をアドレスの昇順にソートするステップと、
ソートした第１番目から順番に経路を集約するステップと、
第１番目から第ｉ番目までの経路の集約が他のエッジ装置から収集した経路と交差した場合、第１番目から第（ｉ−１）番目までの経路を集約して集約経路を計算するステップと、
計算した集約経路が広告されるように各前記エッジ装置を設定するステップと、
を実行することを特徴とする集約経路計算方法。
外部と接続する各エッジ装置で受信した経路を集約するコントローラが実行する集約経路計算方法であって、
前記コントローラは、
各前記エッジ装置から経路を収集するステップと、
前記エッジ装置ごとに、収集した経路をアドレスの昇順にソートするステップと、
ソートした第１番目から順番に経路を集約するステップと、
第１番目から第ｉ番目までの経路の集約が他のエッジ装置から収集した経路と交差した場合、第１番目から第（ｉ−１）番目までの経路を集約して集約経路を計算するステップと、
計算した集約経路をネットワークに広告するステップと、
を実行することを特徴とする集約経路計算方法。