(57)【要約】【課題】経路の集約効率を向上させる。【解決手段】経路集約装置１は、ネットワークを介して他のネットワーク装置２との間で経路を交換する。経路集約装置１は、前記経路を特定する情報として宛先と隣接する送信先とを記憶する記憶部２１と、前記経路を二分木の形式で含む経路表４０を作成し、未広告経路も集約可能な経路として経路表４０に追加し、経路表４０に追加された未広告経路と、任意の隣接する送信先の情報を保持する経路と、の集約を行う制御部２０と、を備える。【選択図】図１
2019036778.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介して他の装置との間で経路を交換する経路集約装置であって、
前記経路を特定する情報として宛先と隣接する送信先とを記憶する記憶部と、
前記経路を二分木の形式で含む経路表を作成し、未広告経路も集約可能な経路として前記経路表に追加し、前記経路表に追加された未広告経路と、任意の隣接する送信先の情報を保持する経路と、の集約を行う処理部と、を備える経路集約装置。
【請求項２】
前記処理部は、前記未広告経路を転送しない経路として前記経路表に追加し、経路の集約時に前記経路表からは削除しない請求項１に記載の経路集約装置。
【請求項３】
前記処理部は、未広告経路の保持する宛先のプリフィックス長と同一のプリフィックス長を保持すると共に、前記経路表の二分木において前記未広告経路を模擬的に配置したときに同一の親を有するような第１経路を探索し、前記第１経路が存在する場合、前記未広告経路を前記経路表の二分木に確定的に追加してから経路の集約を行い、前記第１経路が存在しない場合、前記未広告経路を前記二分木に追加せず集約も行わない請求項１または請求項２に記載の経路集約装置。
【請求項４】
前記処理部は、所定の第１時間を経過しても広告経路を受信しない場合、経路の集約を行い、集約を行っていない時間が所定の第２時間を経過した場合、経路の集約を行う請求項１から請求項３のいずれか一項に記載の経路集約装置。
【請求項５】
前記処理部は、前記経路表に格納された経路数が所定の上限値を超過した場合、経路の集約を行う請求項１から請求項４のいずれか一項に記載の経路集約装置。
【請求項６】
ネットワークを介して他の装置との間で経路を交換し前記経路を特定する情報として宛先と隣接する送信先とを記憶する記憶部と処理部とを有する経路集約装置の経路集約方法であって、
前記経路を二分木の形式で含む経路表を作成するステップと、
未広告経路も集約可能な経路として前記経路表に追加するステップと、
前記経路表に追加された未広告経路と、任意の隣接する送信先の情報を保持する経路と、の集約を行うステップと、を含む経路集約方法。
【請求項７】
コンピュータを、請求項１から請求項５のいずれか一項に記載の経路集約装置として機能させるための経路集約プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを介して他の装置との間で経路の情報を交換し経路の集約を行う経路集約装置、経路集約方法および経路集約プログラムに関する。
【背景技術】
【０００２】
従来、インターネットをはじめとしたＩＰ（Internet Protocol）を用いた通信は、一方のＩＰ装置が経路を他方のＩＰ装置に広告し、経路交換を行うことで、宛先に向けて、隣接する送信先を決定する方法がとられている。ＩＰ装置は、自身で設定した経路および、他装置から広告された経路を経路表に保有する。経路は、基数が２の木構造、すなわち、二分木で表現することができる。二分木で表す場合に保有する情報は、宛先と、隣接する送信先である。従来、この二分木の効率的な保持をする方法は検討されており、その１つに集約を行う手法がある（非特許文献１参照）。
【０００３】
インターネットの運用上において、一部の経路について、広告してはならない経路が存在している。このような経路のことを以下では未広告経路と呼ぶ。具体的な未広告経路としては、ＲＦＣ５７３５やＲＦＣ６５９８に記載されている他、インターネット上に公開され、随時更新されているリスト（非特許文献２参照）が知られている。それら未広告経路をフィルタする場合、そのフィルタはBogon Filterと呼ばれている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Jonathan Turner et al., “Routing Table Compression Using Binary Tree Collapse”, Washington University, Number:wucs-98-13 (1998).
【非特許文献２】［online］、［平成29年8月4日検索］、インターネット〈URL:http://www.team-cymru.org/Services/Bogons/fullbogons-ipv4.txt〉
【発明の概要】
【発明が解決しようとする課題】
【０００５】
未広告経路は、元々広告されない経路であるため、従来、経路表には存在しない。また、二分木で表した経路表に未広告経路が存在したとしても、経路の集約において、未広告経路は、必ず経路集約対象から外れる。二分木上で集約対象から外れるノード（経路）があると、当該ノードやその親のノードの集約ができない。そのため、従来技術の手法だけでは、集約時の効率が低下するという問題があった。
【０００６】
本発明は、このような背景に鑑みてなされたものであり、経路の集約効率を向上させることのできる経路集約装置、経路集約方法および経路集約プログラムを提供することを課題とする。
【課題を解決するための手段】
【０００７】
前記した課題を解決するため、本発明にかかる経路集約装置は、ネットワークを介して他の装置との間で経路を交換する経路集約装置であって、前記経路を特定する情報として宛先と隣接する送信先とを記憶する記憶部と、前記経路を二分木の形式で含む経路表を作成し、未広告経路も集約可能な経路として前記経路表に追加し、前記経路表に追加された未広告経路と、任意の隣接する送信先の情報を保持する経路と、の集約を行う処理部と、を備えることを特徴とする。
【０００８】
また、本発明にかかる経路集約方法は、ネットワークを介して他の装置との間で経路を交換し前記経路を特定する情報として宛先と隣接する送信先とを記憶する記憶部と処理部とを有する経路集約装置の経路集約方法であって、前記経路を二分木の形式で含む経路表を作成するステップと、未広告経路も集約可能な経路として前記経路表に追加するステップと、前記経路表に追加された未広告経路と、任意の隣接する送信先の情報を保持する経路と、の集約を行うステップと、を含む、ことを特徴とする。
【０００９】
かかる構成の経路集約装置、および、かかる手順の経路集約方法によれば、経路集約装置の処理部が、経路を二分木の形式で含む経路表に未広告経路も追加し（図６（ａ）参照）、任意の隣接する送信先の情報を保持する経路との集約を行う（図６（ｂ）および図６（ｃ）参照）。これにより、従来手法（図５（ｂ）参照）よりも経路の集約効率を向上させることができる。
【００１０】
また、本発明にかかる経路集約装置は、前記処理部が、前記未広告経路を転送しない経路として前記経路表に追加し、経路の集約時に前記経路表からは削除しないこととしてもよい。
【００１１】
かかる構成によれば、経路集約装置では、未広告経路を転送しない経路として二分木に追加するので通常の処理と同様の集約を行うことができる。また、集約時に経路表からは削除しなくても、未広告経路は集約後の各経路と比べてロンゲストマッチにより優先されるので、未広告経路宛のパケットは転送されることがない。
【００１２】
また、本発明にかかる経路集約装置は、前記処理部が、未広告経路の保持する宛先のプリフィックス長と同一のプリフィックス長を保持すると共に、前記経路表の二分木において前記未広告経路を模擬的に配置したときに同一の親を有するような第１経路を探索し、前記第１経路が存在する場合、前記未広告経路を前記経路表の二分木に確定的に追加してから経路の集約を行い、前記第１経路が存在しない場合、前記未広告経路を前記二分木に追加せず集約も行わないこととしてもよい。
【００１３】
かかる構成によれば、経路集約装置では、経路表の二分木に未広告経路を追加した場合のシミュレーションを事前に行う。そして、シミュレーションに成功する場合にだけ未広告経路を経路表に追加した上で集約を行うので、未広告経路の確実な集約を行うことができる。
【００１４】
また、本発明にかかる経路集約装置は、前記処理部が、所定の第１時間を経過しても広告経路を受信しない場合、経路の集約を行い、集約を行っていない時間が所定の第２時間を経過した場合、経路の集約を行うこととしてもよい。
【００１５】
かかる構成によれば、経路集約装置では、第１時間を閾値として他の装置との広告経路の交換を行っていない期間に経路の集約を行うので、集約の計算に伴う装置全体の処理負荷を低減できる。また、経路集約装置では、他の装置との広告経路の交換を切れ目なく頻繁に行っていたとしても第２時間を閾値として経路の集約のための計算を開始することができる。
【００１６】
また、本発明にかかる経路集約装置は、前記処理部が、前記経路表に格納された経路数が所定の上限値を超過した場合、経路の集約を行うこととしてもよい。
【００１７】
かかる構成によれば、経路集約装置では、経路数の上限値を閾値として経路の集約を行うので、経路表に余裕がある場合には、他の装置から受信した広告経路の追加や削除の情報にしたがって経路変更を反映する計算を行うことができる。
なお、本発明は、コンピュータを、前記経路集約装置として機能させるための経路集約プログラムによっても実現することができる。
【発明の効果】
【００１８】
本発明によれば、経路の集約効率を向上させることができる。
【図面の簡単な説明】
【００１９】
【図１】本実施形態の経路集約装置の構成を示すブロック図である。
【図２】二分木を用いた経路表の模式図である。
【図３】経路表の模式図であり、（ａ）〜（ｃ）は、典型的な経路の集約過程を示している。
【図４】二分木において親ノードと子ノードの間に中間ノードが存在する場合の経路表の模式図であって、（ａ）、（ｂ）は集約できる例、（ｃ）は集約できない例をそれぞれ示している。
【図５】課題を説明するための経路表の模式図であって、（ａ）、（ｂ）は集約過程を示している。
【図６】本実施形態において未広告経路を含めた経路表の一例であって、（ａ）〜（ｃ）は集約過程を示している。
【図７】本実施形態の経路集約装置に記憶される情報の一例であって、（ａ）は未広告経路一覧表、（ｂ）は設定表を示している。
【図８】本実施形態において未広告経路を含む経路の集約処理の流れを示すフローチャートである。
【図９】本実施形態において未広告経路を含めた経路表の他の例であって、（ａ）〜（ｃ）は集約過程を示している。
【図１０】本実施形態において経路表更新処理の全体の流れを示すフローチャートである。
【図１１】本実施形態の経路集約装置の集約処理で作成される経路表の記憶領域を示す模式図である。
【発明を実施するための形態】
【００２０】
以下、本発明の経路集約装置および経路集約方法について図面を参照して詳細に説明する。
図１に示すように、経路集約装置１は、リンク（ネットワーク）を介してネットワーク装置２に接続されており、ネットワーク装置２との間で、経路を交換する。経路は、宛先と隣接する送信先とを情報として保持する。経路集約装置１およびネットワーク装置２は、例えば、ルータまたはＬ３スイッチ等のＩＰ装置として構成されている。経路集約装置１は、他の装置を介して受信した経路を、記憶部２１に記憶する。同様に、ネットワーク装置２は、他の装置を介して受信した経路を、記憶部に記憶する。各装置には、ＩＰアドレスが設定されている。なお、図１では、ネットワーク装置２を２台示したが、台数は例示した２台に限定されるものではない。
【００２１】
［経路集約装置の構成］
図１に示すように、経路集約装置１は、転送部１０と、制御部（処理部）２０と、を備えて構成されている。
転送部１０は、ネットワークに接続するネットワークＩ／Ｏとして機能する。この転送部１０は、ＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等によって実現される。ここでは、転送部１０は、パケットの転送処理の用途に適合するように専用に設計された特定用途向けのＬＳＩ（Large Scale Integration）であるＡＳＩＣ（Application Specific Integrated Circuit）等のハードウェアチップによって実現されている。
【００２２】
例えば、転送部１０は、複数のインタフェース（ＩＦ）１１と、メモリ１２と、を備えて構成されている。
インタフェース１１は、自己の経路集約装置１を他のネットワーク装置２等に物理的に接続するためのものである。インタフェース１１の個数は、特に限定されないが少なくともリンクの数と同じ個数は備えている。ここでは、２つのインタフェース１１が、それぞれのリンクを介して２つのネットワーク装置２に接続されている。図示するように未使用のインタフェース１１があっても構わない。
【００２３】
メモリ１２には、ハードウェア転送テーブル１３が記憶されている。
ハードウェア転送テーブル１３は、転送部１０に記憶された転送に特化したテーブルである。ハードウェア転送テーブル１３は、制御部２０で作成されて制御部２０の記憶部２１に記憶されている経路表４０が書き込まれたものである。ハードウェア転送テーブル１３の内容は、記憶部２１に記憶される経路表４０と同じ内容である。このような構成とした理由は、制御部２０と転送部１０は、図１に示すように１対１の組み合わせもありうるが、１対Ｎの組み合わせもありうるからである。ちなみに、一般に、転送部は、制御部よりも高速性を求められるため、検索用途特化のメモリ等が利用されることがある。この検索用途特化のメモリ等は、汎用ＰＣ用途のメモリ等に比べて容量や格納できるエントリ数が少ない場合があることから、制御部２０と転送部１０に対して１対Ｎの組み合わせが考慮される。図示した１対１の組み合わせの場合、基本的に、経路表４０とハードウェア転送テーブル１３は同一の情報を保持すればよい。これに対して、１対Ｎの組み合わせの場合、経路表４０の一部の情報をハードウェア転送テーブル１３に保持するケースもある。そのようなケースとしては、例えば、Ｎ個のハードウェア転送テーブルを用いて、経路表４０の全体の情報をカバーする場合が挙げられる。
【００２４】
転送部１０は、例えば、パケットに応じて、メモリ１２に記憶されているハードウェア転送テーブル１３を参照し、対応するインタフェース１１を判定し、判定したインタフェース１１にパケットを送出する。
【００２５】
［制御部２０］
制御部（処理部）２０は、経路計算および装置全体の制御を行うものである。
制御部２０は、記憶部２１と、経路表−転送テーブル変換処理部２２と、集約処理部２３と、を含んで構成されている。なお、ここでは、経路表−転送テーブル変換処理部２２の中に集約処理部２３を含む構成としたが、経路表−転送テーブル変換処理部２２の外に集約処理部２３を設けてもよい。また、経路表−転送テーブル変換処理部２２と、集約処理部２３とは、例えば、記憶部２１に格納されたプログラムをＣＰＵがＲＡＭ（Random Access Memory）に展開し実行することにより実現される。
例えば、制御部２０は、汎用用途向けのＬＳＩで実現されており、転送部１０とはネットワークＩ／Ｏによって通信可能に接続されている。
【００２６】
［記憶部２１］
記憶部２１は、ハードディスクやフラッシュメモリ、ＲＡＭ等により構成される。また、記憶部２１には、制御部２０の各機能を実行させるためのプログラムや、制御部２０の処理に必要な情報が一時的に記憶される。この記憶部２１には、ルーティングソフトウェア３０等が記憶される。なお、図１では、ルーティングソフトウェア３０が、経路表−転送テーブル変換処理部２２の上位であることをプロトコルスタックの形式で模式的に示している。
【００２７】
ルーティングソフトウェア３０は、経路計算部として機能し、経路表４０を作成する。
ルーティングソフトウェア３０は、所定のルーティングプロトコルを用いて、経路をネットワーク装置２との間で相互に通知する。これらの経路は、様々な手法で交換されるが、１つの経路表４０に書き込まれる。ルーティングプロトコルとしては、ＢＧＰ（Border Gateway Protocol）、ＯＳＰＦ（Open Shortest Path First）、ＩＳ−ＩＳ（Intermediate System to Intermediate System）等を挙げることができる。
【００２８】
図１では、ルーティングソフトウェア３０は、ＢＧＰプロセス、ＯＳＰＦプロセス、ＩＳ−ＩＳプロセスを備えるように図示したが、いずれか1つでもよいし、すべて備えていてもよい。ルーティングソフトウェア３０のプロセスは、例えば内部ＡＰＩ（Application Programming Interface）等を用いて経路表４０を作成する。経路表４０を作成するために、内部ＡＰＩとしては、情報を取得するＡＰＩ、情報を記憶部２１にキャッシュするＡＰＩ、キャッシュから情報を検索するＡＰＩ等の複数のＡＰＩを用いることができる。
【００２９】
また、記憶部２１には、経路表４０が記憶されている。経路は、情報として宛先と隣接する送信先とを保持している。経路表４０は、ルーティングソフトウェア３０によって作成され、経路表−転送テーブル変換処理部２２によって、編集および更新される。なお、詳細は後記するが、経路表４０について、集約を行う前後やその途中（編集中）における経路表を区別する場合、集約前経路表４０Ａ、集約中経路表４０Ｂ、集約後経路表４０Ｃのように表記する（図１１参照）。また、この場合、記憶部２１は、例えば、集約前経路表記憶領域２１Ａと、集約中経路表記憶領域２１Ｂと、集約後経路表記憶領域２１Ｃと、を備えるように構成することもできる（図１１参照）。
【００３０】
また、記憶部２１には、未広告経路一覧表５１と、設定表５２と、が記憶されている。
未広告経路一覧表５１は、例えば、インターネットに公開されている未広告経路を蓄積したデータである。未広告経路一覧表５１の一例を図７（ａ）に例示する。未広告経路は、ソートされたデータ構造、または、二分木として保持することが望ましい。
未広告経路一覧表５１は、例えば、経路集約装置１の保守者による手動操作によりインターネットから取得されて、記憶部２１に記憶される。または、集約処理部２３が一定時刻単位で転送部１０（ネットワークＩ／Ｏ）を介して、インターネットに接続して、未広告経路を自動的に取得して記憶部２１に記憶することとしてもよい。
【００３１】
設定表５２は、経路集約装置１の好適な動作を実現するための各種設定値をテーブル形式で記憶部２１に蓄積したデータである。設定表５２の一例を図７（ｂ）に例示する。ここでは、後記する集約処理部２３が実行する集約処理の好適な動作を実現するために、一例として、時間閾値である広告速度閾値（アクティブ、インアクティブ）や、メモリ容量閾値である上限経路数を設定している。設定表５２の詳細については後記する。なお、設定表５２において４行目、５行目は未設定であるが他の複数の設定条件が格納できることを示している。
【００３２】
経路表−転送テーブル変換処理部２２は、上位のルーティングソフトウェア３０が持つ経路表４０と、ハードウェア転送テーブル１３の情報とを変換するものである。
経路表−転送テーブル変換処理部２２は、集約処理部２３を備えている。
経路表−転送テーブル変換処理部２２は、上位のルーティングソフトウェア３０のプロセスから、経路表４０の経路（広告された経路）を、例えば、netlink等のＡＰＩ（Application Programming Interface）で入手する。経路表−転送テーブル変換処理部２２は、Patricia Tree Algorithm（基数木アルゴリズム）により二分木を作成する機能を有する。なお、netlinkに関しては、例えば、下記参考文献１に記載されているので、ここでは説明を省略する。
（参考文献１）
Network Working Group RFC (Request for Comments) 3549, “Linux Netlink as an IP Services Protocol”, July 2003.
【００３３】
経路表−転送テーブル変換処理部２２は、集約処理部２３による集約機能を使わない場合、入手した経路を、例えば、OpenFlow等のハードウェア書き込みに適した方法により変換する。その上で、経路表−転送テーブル変換処理部２２は、変換した経路を、ネットワークＩ／Ｏを介してハードウェア転送テーブル１３に送信し、ハードウェア転送テーブル１３へ書き込む機能を有する。なお、OpenFlowに関しては、下記参考文献２に記載されているので、ここでは説明を省略する。
（参考文献２）
OpenFlow Switch Specification Version 1.3.4 ( Protocol version 0x04 ), March 27, 2014. <URL:https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-switch-v1.3.4.pdf＞
【００３４】
また、経路表−転送テーブル変換処理部２２は、集約処理部２３による集約機能を使う場合、入手した広告経路を記憶部２１の経路表４０に保持する。ここで、経路表は、図３（ａ）〜図３（ｃ）の下側に示すように、保守者に対してテーブル形式で表示可能だが、検索効率などを踏まえ、内部的には二分木の形式の経路表（集約前経路表４０Ａ）として保持される。なお、上位のルーティングソフトウェア３０のプロセスが保有する経路表４０と、集約前経路表４０Ａが保持している情報とは原則同一になる。
経路表−転送テーブル変換処理部２２は、集約処理部２３による集約結果を、例えば、OpenFlow等のハードウェア書き込みに適した方法により変換して、ハードウェア転送テーブル１３へ書き込む。
【００３５】
集約処理部２３は、非特許文献１記載の方法と、後記する本実施形態の経路集約方法のアルゴリズムにより、経路を集約する。集約処理部２３は、未広告経路を転送しない経路として経路表４０に追加し、経路の集約時に経路表４０からは削除しない。
集約処理部２３は、未広告経路の集約処理の中で集約を確定する前にシミュレーションを行う。また、二分木のツリー上では、段階的に複数回の集約を可能である。この回数を以下では、集約可能回数という。ここでは、例えば、集約可能回数が１回であるものとして説明する。この場合、集約処理部２３は、未広告経路の保持する宛先のプリフィックス長と同一のプリフィックス長を保持し、経路表の二分木において未広告経路を模擬的に配置したときに同一の親を有する第１経路を探索する。そして、このような第１経路が存在する場合、未広告経路を経路表の二分木に確定的に追加してから経路の集約を行う。一方、第１経路が存在しない場合、前広告経路を二分木に追加せず集約も行わない。なお、集約可能回数は１回に限らない。
【００３６】
以下、集約処理部２３による処理について、例えば非特許文献１に記載の従来手法と対比させて図２〜図６を参照（適宜、図１参照）しながら詳細に説明する。なお、後記する経路集約装置１の動作の説明（図７および図８）においても集約処理部２３のさらなる説明を行う。
【００３７】
まず、二分木を用いた経路表について図２を参照して説明する。
図２では、全体で３２ビットあるネットワークアドレスの先頭８ビットの例として、「0000 0000」、「0000 0001」、「0000 0010」、「0000 0011」をそれぞれ挙げて説明する。この８ビットの下位４ビット部分の二分木を図２に示す。この経路表（二分木）では、９個のノードと８本のリンクからなるツリー構造の部分を表示している。ノード形状は円形でも構わないが、ここでは角丸の矩形で表している。各ノードは経路を表している。経路は、宛先と隣接する送信先（隣接送信先）の情報を保持している。ノード内の上部（１行目）には、宛先として、プリフィックス／プリフィックス長（Prefix/PrefixLength）が記載されている。プリフィックス長はプリフィックス（またはアドレスプリフィックス）を構成するビット列の長さである。ノード内の下部（２行目）には、隣接送信先（NextHop）が記載されている。なお、二分木の４個の子ノードにそれぞれ記載されたプリフィックスの最初の数値は「０」、「１」、「２」、「３」である。これらは、例示した下位４ビット部分に記載した二進数のビット列を十進数で表したものである。なお、二分木では、注目しているノード（図２では、例示した下位４ビット部分を表示した４つのノード）以外のノードは、Prefix/PrefixLengthおよびNextHopの表示を省略してノード内部を空白表示している。また、二分木に関する以下の図面においてもノードの表記は同様の意味である。
【００３８】
図３は、経路表の模式図であり、（ａ）〜（ｃ）は、典型的な経路の集約過程を示している。ここでは、分かり易くするために、二分木形式の経路表の下部に、同一内容のテーブル形式の経路表をそれぞれ示している。経路の集約を行う方法としては、非特許文献１に記載の既知の手法を用いることができる。この手法では、図３（ａ）〜図３（ｃ）に示すように、同一の親ノード（経路）に属す２つの子ノード（経路）が同一の隣接送信先を示している場合、その２つの子ノードを親ノードへ順次集約する。
【００３９】
図４（ａ）および図４（ｂ）に示すように、親ノードと子ノードが同一の隣接送信先を示している場合、子ノードは親ノードへ集約することができる。ここで、親ノードと子ノードの間に、中間ノードが存在していても構わない。ただし、図４（ｃ）に示すように、親ノードと子ノードの間に存在する中間ノードの隣接送信先が、親ノードの隣接送信先とは異なる場合、集約を行うことができない。
【００４０】
図５（ａ）および図５（ｂ）において、ハッチングを付したノードは、未広告経路を表している。並置したテーブル形式の従来の経路表に示すように、未広告経路については、元々、広告されない経路のため、二分木に存在せず、従来の経路表には記載されず、経路集約の対象から外れている。図５（ａ）および図５（ｂ）に示すように、未広告経路は、必ず経路集約対象から外れる。対比として、図３（ａ）に示すようなプリフィックスや隣接送信先を保持する４つの広告経路からなる二分木であれば、２回の集約を行うことで、経路表に記載の経路を１つにまとめることができる。なお、集約されたノードやリンクは破線で示している。
これに対して、図５の例では、二分木に未広告経路として、０．０．０．０／８を付加した場合を想定している。この未広告経路が二分木上で集約対象から外れると、当該ノードの集約をすることができない。一方、同じプリフィックスを有する他の枝の２つのノードに関しては、図３（ｂ）と同様の集約を行うことが可能である。しかしながら、その集約結果についてはさらなる集約を行うことができない。つまり、未広告経路のノードや、その親のノードの集約を行うことができない。このため、従来の手法だけでは、集約時の集約効率の低下を招く。
【００４１】
本実施形態は、非特許文献２のリストに登場する経路については、転送できない経路、例えば自身を示す１２７．０．０．１（図６のNextHopを参照）として、経路表に追加することにする。図６の例では、０．０．０．０／８が未広告経路である。この未広告経路に関しては、経路表に１．０．０．０／８の経路が既に存在するか、または、１．０．０．０／８の経路が広告され保持されたタイミングで、経路の集約が行われる。
【００４２】
ここで、経路集約の面においては、１２７．０．０．１は、例示した８．１．２．３に限らず、任意の隣接送信先に対して集約ができることとする。また、いずれかの隣接送信先を未広告経路と集約した場合においても、未広告経路そのものは経路表から削除しない。未広告経路は、転送してはならない経路であり、未広告経路と任意の経路で集約した結果よりも未広告経路の方がロンゲストマッチにより優先される。
【００４３】
具体的には、図６（ａ）から図６（ｂ）に示すように、０．０．０．０／８の経路（未広告経路）についての集約の結果は、０．０．０．０／７の経路である。
また、図６（ｂ）から図６（ｃ）に示すように、０．０．０．０／７の経路についての集約の結果は、０．０．０．０／６の経路である。
０．０．０．０／７の経路や０．０．０．０／６の経路よりも０．０．０．０／８の経路（未広告経路）の方が優先されるので、０．０．０．０〜０．２５５．２５５．２５５宛のパケットは転送されることがない。上記のように、集約処理部２３は、未広告経路を転送しない経路として経路表４０に追加する。
【００４４】
［設定表について］
ここで、記憶部２１に設定された設定表１２３について図７（ｂ）を参照（適宜、図１参照）して説明する。
経路表−転送テーブル変換処理部２２に対しては、上位のルーティングソフトウェア３０のプロセスで受信した経路が送信される。そのため、経路表−転送テーブル変換処理部２２に対して、経路が一定時間連続で通知され、その後、経路が通知されない時間が続く。つまり、時間が空く。このように、一定時間だけ経路が通知され、空き時間の後、次の経路通知が行われることから、本実施形態では、空き時間に対して設けた時間閾値を超える場合に、集約処理部２３が経路集約を開始することとした。具体的には、空き時間が、記憶部２１に設定された設定表１２３に設定された広告速度閾値（インアクティブ）を超える場合、集約処理部２３は経路集約を開始する。つまり、集約処理部２３は、所定の第１時間（インアクティブ）を経過しても広告経路を受信しない場合、経路の集約を行う。
【００４５】
言い換えると、いつまで経っても空き時間が広告速度閾値（インアクティブ）を超えなければ、集約処理部２３は経路集約を開始しないことになる。例えば広告速度閾値（インアクティブ）内の一定時間ごとに、経路変更通知（経路の追加／削除通知）が来る場合は、通知された経路変更を全く反映できない可能性がある。そこで、この事態を未然に防ぐため、経路集約を行っていない時間が、記憶部２１に設定された設定表１２３に記載された広告速度閾値（アクティブ）を超える場合、集約処理部２３は経路集約を開始することとした。つまり、集約処理部２３は、集約を行っていない時間が所定の第２時間（アクティブ）を経過した場合、経路の集約を行う。
【００４６】
これにより、経路通知が継続し実施されている場合でも、広告速度閾値（アクティブ）の時間単位で経路集約を行うことが可能である。なお、広告速度閾値（アクティブ）の時間は、計算が連続しないように、つまり、計算完了前に次の計算が発生しないように見込まれる計算時間以上の値で時間設定することが望ましい。例えば、見込まれる計算時間が１０００ｍｓであれば、広告速度閾値（アクティブ）の時間は２０００ｍｓ程度にする。
【００４７】
設定表１２３に設定された上限経路数は、所定の上限値であって、ハードウェア転送テーブル１３に保持された経路数の上限値を規定するものである。言い換えると、上限経路数は、記憶部２１に記憶された集約前経路表４０Ａに保持された経路数の上限値を規定するものである。この上限経路数は、経路表−転送テーブル変換処理部２２または集約処理部２３の処理を、以下の２つの観点（第１の観点、第２の観点）で規定する。
【００４８】
第１の観点では、集約前経路表４０Ａに保持された経路数が上限経路数より小さい場合、経路表−転送テーブル変換処理部２２は、次の２つの処理を並行して行う。すなわち、集約前経路表４０Ａの構築および経路集約処理と並行して、経路の集約を行わずに通知された経路をハードウェア転送テーブル１３へ即時に反映する処理（即時反映処理）を実行する。
【００４９】
一方、集約前経路表４０Ａに保持された経路数が上限経路数以上になった場合、経路表−転送テーブル変換処理部２２は、即時反映処理をやめ、集約処理部２３は、経路の集約を行う。経路表−転送テーブル変換処理部２２は、経路集約後の結果をハードウェア転送テーブル１３へ送信する。このようにする理由は、経路の集約をする場合、集約結果を経路表４０に反映させるまでには、経路集約の計算時間の分だけ余計に多くの時間がかかるからである。なお、上限経路数を超過することで動作が切り替わる場合、ハードウェア転送テーブル１３の内容は、追記するのではなく、過去の情報を一旦すべて削除してから書き込む（上書きする）。
【００５０】
第２の観点では、集約前経路表４０Ａに保持された経路数が上限経路数より小さい場合、集約処理部２３は、空き時間が広告速度閾値（インアクティブ）を超えた場合、経路集約を実行する。また、経路表−転送テーブル変換処理部２２は、集約処理部２３が経路集約の計算を実行している最中に、新規の通知を受けた場合、経路集約の計算をキャンセルする。言い換えると、経路表−転送テーブル変換処理部２２において、経路集約処理以外の他の処理が動作していない場合に限ってのみ、経路集約の計算が実行される。
【００５１】
一方、集約前経路表４０Ａに保持された経路数が上限経路数以上になった場合、経路表−転送テーブル変換処理部２２は、空き時間が広告速度閾値（インアクティブ）を超えると、経路集約を実行する。または、集約前経路表４０Ａに保持された経路数が上限経路数以上になった場合、経路表−転送テーブル変換処理部２２は、経路集約を行っていない時間が広告速度閾値（アクティブ）を超えると、経路集約を実行する。
なお、以下では、経路集約を実行する条件として、第２の観点でいくつか場合分けしたそれぞれの条件を、経路集約実行条件と呼ぶ。経路集約実行条件が満たされた場合に、集約処理部２３は経路集約を実行する。
【００５２】
［経路集約装置の動作］
＜経路集約方法＞
次に、本実施形態にかかる経路集約装置における経路集約方法について図８を参照（適宜図１および図９参照）して説明する。なお、図８および図９において、集約可能回数が２回である場合の一例として説明する。
【００５３】
集約処理部２３は、未広告経路一覧表５１から、次の未広告経路（以下、経路Ａと呼ぶ）を読み込む（ステップＳ１０１）。図９（ａ）の例では、経路Ａは、１．０．２４０．０／２１の経路である。そして、集約処理部２３は、経路Ａと同一のプリフィックス長を有し、プリフィックス長が１少ない場合に経路Ａと同一プリフィックスであるような第１経路（以下、経路Ｂと呼ぶ）を探索する（ステップＳ１０２）。集約処理部２３は、経路Ａと同一の親を持つような経路Ｂが存在しないと判別した場合（ステップＳ１０３：Ｎｏ）、読み込んだ経路Ａを追加することなく、集約も行わないまま、ステップＳ１０１に戻る。
【００５４】
図９（ａ）の例では、経路Ｂとして、１．０．２４８．０／２１の経路が存在する。経路Ｂが存在すると判別した場合（ステップＳ１０３：Ｙｅｓ）、集約処理部２３は、次のような経路（以下、経路Ｄと呼ぶ）を探索する（ステップＳ１０４）。経路Ｄとは、経路Ａと経路Ｂとの親ノード（以下、経路Ｃと呼ぶ）と同一のプリフィックス長を有し、プリフィックス長が１少ない場合に同一プリフィックスであり、隣接送信先が同一であるような経路である。集約処理部２３は、経路Ｄが存在しないと判別した場合（ステップＳ１０５：Ｎｏ）、読み込んだ経路Ａを追加することなく、集約も行わないまま、ステップＳ１０１に戻る。
【００５５】
図９（ａ）の例では、経路Ｄとして、１．０．２２４．０／２０の経路が存在する。経路Ｄが存在すると判別した場合（ステップＳ１０５：Ｙｅｓ）、集約処理部２３は、経路Ａを集約可能な経路として経路表に追加し（図９（ａ）参照：ステップＳ１０６）、経路Ｂを削除する（図９（ｂ）参照）。そして、集約処理部２３は、経路表に追加された経路Ａと、経路Ｂとの集約を行い、経路Ａ、Ｂの集約として経路Ｃを作成する（ステップＳ１０７）。図９（ｂ）の例では、経路Ｃは、１．０．２４０．０／２０の経路である。
【００５６】
そして、集約処理部２３は、経路表から経路Ａを削除することなく経路Ａを保持したまま、経路Ｃに対して集約を実施する（ステップＳ１０８）。図９（ｃ）の例では、経路Ｃ、Ｄの集約結果は、１．０．２２４．０／１９の経路となる。
【００５７】
＜経路表の作成処理の流れ＞
次に、本実施形態にかかる経路集約装置における経路表の作成処理の流れについて図１０を参照（適宜図１および図１１参照）して説明する。
【００５８】
まず、経路集約装置１は、ネットワーク装置２との経路交換により、経路変更（追加または削除）を契機とした経路情報を受信する（ステップＳ２０１）。
詳細には、例えばネットワーク装置２がＢＧＰルータである場合、経路集約装置１のルーティングソフトウェア３０のＢＧＰプロセスは、ＢＧＰ広告経路を通じて、このＢＧＰルータから経路情報を受信する。ここで、ＢＧＰ広告経路は、ネットワーク装置２と経路集約装置１との間の物理リンク、インタフェース１１、および、経路表−転送テーブル変換処理部２２等である。
【００５９】
そして、経路集約装置１の集約処理部２３は、経路変更後に集約前経路表４０Ａの経路総数は上限経路数（上限値）を超過することになるか否かを判別する（ステップＳ２０２）。ここで、経路変更後とは、集約処理部２３が集約処理の中で集約を確定する前に、シミュレーションで経路変更を行った後を意味する。
経路変更後において集約前経路表４０Ａの経路総数が上限値を超過しない場合（ステップＳ２０２：Ｎｏ）、集約処理部２３は、経路の集約を行わない。そして、集約処理部２３は、受信した経路変更を実際に反映し（ステップＳ２１１）、経路表−転送テーブル変換処理部２２から、ハードウェア転送テーブル１３へ、その変更情報を送信する（ステップＳ２０９）。
【００６０】
一方、経路変更後において集約前経路表４０Ａの経路総数が上限値を超過する場合（ステップＳ２０２：Ｙｅｓ）、集約処理部２３は、集約後経路表４０Ｃが存在する否かを判別する（ステップＳ２０３）。つまり、集約を行うのは初めてなのか否かを判別する。
【００６１】
初めて集約を行う場合、つまり、集約後経路表４０Ｃが未作成の場合（ステップＳ２０３：Ｎｏ）、集約処理部２３は、受信した経路変更を実際に反映した集約前経路表４０Ａを基に経路の集約を行う。そして、集約処理部２３は、集約後経路表４０Ｃを生成し（ステップＳ２１０）、ステップＳ２０９に進む。なお、ステップＳ２１０では、集約処理部２３は、広告経路の集約は従来と同様の手法で集約し、未広告経路の集約については図８のフローチャートにしたがって集約を行う。
【００６２】
前記ステップＳ２０３において、既に集約後経路表４０Ｃが存在する場合（ステップＳ２０３：Ｙｅｓ）、集約処理部２３は、集約前経路表４０Ａの経路総数を上限経路数（上限値）と比較する。ただし、受信した経路変更を反映させるシミュレーションをした後の経路総数ではなく、受信した経路変更を反映させる前の経路総数を用いる。すなわち、集約処理部２３は、経路変更前の状態において、集約前経路表４０Ａの経路総数は上限値を超過しているか否かを判別する（ステップＳ２０４）。経路変更を行う前の状態において集約前経路表４０Ａの経路総数が上限値を超過していない場合（ステップＳ２０４：Ｎｏ）、集約処理部２３は、前記したステップＳ２１０に進み、経路の集約を行う。
【００６３】
一方、経路変更を行う前の状態において集約前経路表４０Ａの経路総数が上限値を超過している場合（ステップＳ２０４：Ｙｅｓ）、集約処理部２３は、通知された経路（ノード）に関して次の処理を行う。この場合、集約処理部２３は、受信したノードを頂点として、そこから下（子ノード）の経路の集約を行い（ステップＳ２０５〜ステップＳ２０８）、前記したステップＳ２０９に進む。以下に、この一連の処理を分節して説明する。
【００６４】
まず、集約処理部２３は、集約後経路表４０Ｃを集約中経路表４０Ｂにコピーする（ステップＳ２０５）。ここでは、経路を二分木の形式で含む集約中経路表４０Ｂを作成する。より詳細には、記憶部２１の集約後経路表記憶領域２１Ｃ（図１１参照）に格納されている集約後経路表４０Ｃを複製し、その複製を、集約中経路表記憶領域２１Ｂに上書きする。これにより、集約中経路表記憶領域２１Ｂ上では、集約中経路表４０Ｂは、集約後経路表４０Ｃがコピーされたデータとなる。
【００６５】
次に、集約処理部２３は、集約前経路表４０Ａの変更対象経路から二分木上で従属する経路を集約中経路表４０Ｂにコピーする（ステップＳ２０６）。より詳細には、集約前経路表記憶領域２１Ａ（図１１参照）に格納された集約前経路表４０Ａの追加された経路（変更対象経路）とその下に従属する経路からなる部分（以下、変更対象経路から従属する部分）を複製する。そして、集約処理部２３は、変更対象経路から従属する部分の複製を、集約中経路表記憶領域２１Ｂに格納されている集約中経路表４０Ｂにおいて該当する部分の経路に上書きする。なお、ここで、該当する未広告経路も集約可能な経路として集約中経路表４０Ｂに追加する。
【００６６】
次に、集約処理部２３は、集約中経路表４０Ｂ上で変更対象経路から従属する部分の経路の集約を行う（ステップＳ２０７）。より詳細には、記憶部２１の集約中経路表記憶領域２１Ｂ（図１１参照）に格納されている集約中経路表４０Ｂの全体ではなく、変更対象経路が上書きされたノード（経路）から下（子ノード）について経路集約を行う。その後、その追加した経路（変更対象経路）自身が、その親ノード（よりプリフィックス長の短い経路）と集約可能か否かを判別し、集約できる場合、さらなる集約を行う。なお、ここで、集約中経路表４０Ｂに追加された未広告経路と、任意の隣接する送信先の情報を保持する経路と、の集約も行う。
【００６７】
集約後、集約処理部２３は、集約結果を集約中経路表４０Ｂから集約後経路表４０Ｃにコピーし（ステップＳ２０８）、ステップＳ２０９に進む。より詳細には、集約中経路表記憶領域２１Ｂ（図１１参照）に格納された集約中経路表４０Ｂ（集約結果の経路表）を複製し、その複製を、集約後経路表記憶領域２１Ｃに格納されている集約後経路表４０Ｃに上書きする。これにより、集約後経路表記憶領域２１Ｃ上では、集約後経路表４０Ｃは、集約中経路表４０Ｂがコピーされたデータとなる。上記一連の処理（ステップＳ２０５〜ステップＳ２０８）を行うことで計算量を削減することができる。
【００６８】
集約処理部２３は、上記経路集約を行う場合（ステップＳ２０５〜Ｓ２０８，Ｓ２１０）、未広告経路一覧表５１上に存在する経路（未広告経路）を、図８で示す判断方法にしたがって経路表４０に追加する。この場合、集約処理部２３は、集約前経路表４０Ａをコピーした集約中経路表４０Ｂに対して、上記方法で未広告経路を追加してから集約を行う。つまり、計算時に利用する編集可能な集約中経路表４０Ｂとしては、集約後経路表４０Ｃに、集約前経路表４０Ａにおける通知された経路を頂点として、そこから下を追加した表（二分木）を作成したものを用いる。そして、集約処理部２３は、その二分木に対して未広告経路を追加して集約計算を行うことで、計算量を抑制することができる。
【００６９】
なお、経路集約の計算については、前記経路集約実行条件が整った時点で、集約前経路表４０Ａの全体を計算対象として、集約後経路表４０Ｃを生成し直すのが最も間違いのない確実な方法である。しかしながら、この計算方法では計算量が大きくなり、更新されない部分に対して同一の計算を繰り返す無駄が発生する。そこで、計算量を削減するために、前記ステップＳ２０５〜ステップＳ２０８の一連の処理は、通知された経路を頂点として、そこから下（子ノード）について経路の集約を行う。その上で、その追加した経路自身が、親ノード（よりプリフィックス長の短い経路）と集約可能か否かを確認する。この場合、判断に用いる未広告経路一覧表５１も、その経路の範囲のみを参照することとする。従ってこれら経路もソートされたデータ構造または二分木として保持することが望ましい。
【００７０】
本実施形態によれば、経路集約装置では、未広告経路を転送することなく、いずれの隣接送信先を持つ二分木ノード（経路）とも集約可能なアドレスとして、自己の二分木形式の経路表に保持する。また、経路集約装置は、経路表に追加した未広告経路について経路の集約を行うので、集約効率を向上させることができる。
【００７１】
経路集約装置は、未広告経路（経路Ａ）と同一プリフィックス長を持ち同一の親を持つ経路Ｂが経路Ａと集約された結果（経路Ｃ）が経路Ｄと集約可能かシミュレートした結果に応じて経路Ａの集約を行うかを決定する。つまり、シミュレートが成功する場合のみ、実際に未広告経路を追加して集約を行い、失敗する場合、未広告経路の追加をやめ、集約も行わないので未広告経路の確実な集約を行うことができる。
【００７２】
本発明は前記した実施形態に限定されるものではなく、種々の変形が可能である。また、以下のように変形してもよい。例えば、経路集約装置１は、ルータやスイッチによって実現することも可能であるし、一般的なコンピュータを、経路集約装置１として機能させるプログラムにより動作させることで実現することも可能である。
また、一般的なコンピュータを、経路集約機能に特化した経路表−転送テーブル変換処理部２２または集約処理部２３として機能させる経路集約プログラムにより動作させることで実現することも可能である。
これらのプログラムは、通信回線を介して提供することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００７３】
また、経路集約装置１の構成は図１に示した形態に限定されるものではなく、例えば、電源、各種センサ類、表示用ＬＥＤなどもハードウェアとして備えることもできる。また、例えば、経路表４０等を恒久的に二次記憶装置等に記録させる場合には、ディスクＩ／Ｏコントローラ等を備える構成としてもよい。また、手動操作をする場合、Ｉ／Ｏとして、マウスやキーボード等の入力操作部と、液晶ディスプレイ等の画像表示出力部とを備える構成としてもよい。
【００７４】
また、経路表−転送テーブル変換処理部２２は、上位のルーティングソフトウェア３０から取得した経路を変換して、ネットワークＩ／Ｏを介してハードウェア転送テーブル１３に送信するものとしたが、これに限らない。経路表−転送テーブル変換処理部２２が、ハードウェア転送テーブル１３を持つ転送部１０のＣＰＵで動作する場合、転送部１０のハードウェア内部のバスを介してハードウェア転送テーブル１３に送信する。
【００７５】
また、経路の集約の計算時に、集約中経路表４０Ｂを、集約前経路表４０Ａや集約後経路表４０Ｃとは別のメモリ空間において作成し、コピーを行うとしたが、これに限定されない。例えば、集約中経路表４０Ｂおよび集約後経路表４０Ｃのポインタを変更し、ポインタ変更前の集約後経路表４０Ｃを次の計算用の集約中経路表４０Ｂとし、ポインタ変更前の集約中経路表４０Ｂを集約後経路表４０Ｃとしてもよい。
【００７６】
具体的には、経路集約を行う一連の処理（ステップＳ２０５〜ステップＳ２０８）を、次の一連の処理（ステップＳ３０５〜ステップＳ３０８）へ変形してもよい。まず、集約処理部２３は、集約後経路４０Ｃをポインタの変更をして、次の計算用の集約中経路４０Ｂとする（ステップＳ３０５）。次に、集約処理部２３は、集約前経路４０Ａの変更対象経路から二分木上で従属する経路を、集約中経路４０Ｂにポインタの変更をする（ステップＳ３０６）。次に、集約処理部２３は、集約中経路４０Ｂ上で変更対象経路から従属する部分に対して、経路の集約を実施する（ステップＳ３０７）。集約後、集約処理部２３は、集約結果である集約中経路４０Ｂを、集約後経路４０Ｃとするポインタの変更を行う（ステップＳ３０８）。この方法によれば、メモリコピーコストが低減される。
【００７７】
また、既知の未広告経路を集約可能なノードとして追加するに際し、集約処理部２３は、シミュレートにより、集約可能回数を事前に調査するようにしてもよい。この場合、集約処理部２３は、例えば、集約可能回数が所定値以上であるか否かを判別し、所定値以上である場合に、当該未広告経路を経路表に追加する。このようにすることで、集約効率をコントロールすることができる。
【符号の説明】
【００７８】
１      経路集約装置
２０    制御部（処理部）
２１    記憶部
２２    経路表−転送テーブル変換処理部
２３    集約処理部
３０    ルーティングソフトウェア
４０    経路表
４０Ａ  集約前経路表
４０Ｂ  集約中経路表
４０Ｃ  集約後経路表
５１    未広告経路一覧表
５２    設定表
２      ネットワーク装置
【図１】
2019036778.tif 000003
【図２】
2019036778.tif 000004
【図３】
2019036778.tif 000005
【図４】
2019036778.tif 000006
【図５】
2019036778.tif 000007
【図６】
2019036778.tif 000008
【図７】
2019036778.tif 000009
【図８】
2019036778.tif 000010
【図９】
2019036778.tif 000011
【図１０】
2019036778.tif 000012
【図１１】
2019036778.tif 000013