ルータ装置及びルーティング検索制御方法
【課題】ハードウェアの記憶容量が比較的低容量であっても高スループットを維持可能とするルータ装置を得る。
【解決手段】ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンと、パケットの送受信を行う複数のネットワークデバイスとを有する装置であって、ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２と、Ｈ／Ｗ経路探索を行う経路テーブルとを備え、ＣＰＵ１１０は、ソフトウェアによるＳ／Ｗパケット転送手段１１１と、ソフトウェアによるＳ／Ｗ経路テーブルから経路を探索する経路探索手段と、ルーティング検索エンジンの制御を行うルーティング検索エンジン制御手段１１２と、前記Ｓ／Ｗ経路テーブルに対して経路を登録する経路登録手段を含み、ルーティング検索エンジン制御手段１１２は、指示された経路をＨ／Ｗ経路テーブル１３３に登録する経路登録機能を備える。
【解決手段】ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンと、パケットの送受信を行う複数のネットワークデバイスとを有する装置であって、ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２と、Ｈ／Ｗ経路探索を行う経路テーブルとを備え、ＣＰＵ１１０は、ソフトウェアによるＳ／Ｗパケット転送手段１１１と、ソフトウェアによるＳ／Ｗ経路テーブルから経路を探索する経路探索手段と、ルーティング検索エンジンの制御を行うルーティング検索エンジン制御手段１１２と、前記Ｓ／Ｗ経路テーブルに対して経路を登録する経路登録手段を含み、ルーティング検索エンジン制御手段１１２は、指示された経路をＨ／Ｗ経路テーブル１３３に登録する経路登録機能を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰネットワーク上のルータ装置及びルータ装置におけるルーティング検索制御方法に関し、特に、インターネット接続におけるパケット転送経路を検索するルーティング検索エンジンの制御に関する。
【背景技術】
【０００２】
ルータ装置は、異なるネットワーク間を相互に接続するための中継機器として用いられるものであり、パケットに付与された宛先ＩＰアドレスを識別し検索テーブルにしたがって転送するルーティング処理が行われるが、その高速化を図るため例えば特許文献１や特許文献２に示されるような種々の検索制御方法が提案されている。
【特許文献１】特開２０００−１７４８０５号公報
【特許文献２】特開平１１−３４１０７６号公報
【０００３】
ルータ装置において、受信パケットの送信先を検索するルーティング検索制御については、通常ソフトウェアを用いてＣＰＵ（中央演算装置）で処理している。ルーティング検索制御に関する処理は、パケットの通過・廃棄の可否を設定されたフィルタリング情報に基づいて単に判定する処理と異なり、検出したパケットの転送先を検索する処理が発生するため大きくなり、その結果ＣＰＵに負担をかけることになる。
【０００４】
近年、光ファイバによるインターネット接続サービスの普及が進み、エントリークラスのルータ装置においてもＧｂｐｓクラスのパケット転送能力が求められている。Ｇｂｐｓクラスのルータ装置は、パケット転送能力を向上させるために、ルーティング検索エンジンとしてハードウェア資質を用いるのが一般的である。
ハードウェア資質を用いるルータ装置は、例えば、最初のパケットの転送先をソフトウェア処理により検索し、この時の検索結果をハードウェア検索用の経路テーブルに設定する。そして、以降の同一宛先のパケットについては、この経路テーブルを検索することによるハードウェア処理により転送が行われる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
一般的に、経路テーブルの記憶容量は、ハードウェア資質によるものよりソフトウェア処理による方が大きくなる。ハードウェア資質を用いるルータ装置は、経路総数がハードウェアの記憶容量を超えた場合、パケット転送を維持するため各種の対策が採られる。
例えば、ルータ装置において、全てのパケット転送をソフトウェア処理に移行することでパケット転送を維持する。この場合、スループットが激減する問題が生じる。
【０００６】
また、別の例では、ルータ装置において、ハードウェアから任意の経路を削除することでハードウェアによるパケット転送をある程度維持することが行われる。この結果、ハードウェア処理による経路探索結果と、ソフトウェア処理による経路探索結果との矛盾が発生し、パケット転送が実行できない場合があるという問題が生じる。
【０００７】
これらの問題を防ぐ一つの方法として、十分な記憶容量を備えたハードウェアを使用することが考えられるが、記憶容量が大きくなるほどルータ装置が高価となるという問題がある。
【０００８】
本発明は、上記実情に鑑みて提案されたもので、ハードウェアの記憶容量が比較的低容量であっても高スループットを維持可能とし、且つ、装置全体で経路探索結果の一貫性が維持できるルータ装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記問題点を解決するため本発明の請求項１に記載したルータ装置は、ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンと、該ルーティング検索エンジンに接続しパケットの送受信を行う複数のネットワークデバイスとを有する装置であって、次の各構成を含むことを特徴としている。
前記ルーティング検索エンジンは、ハードウェアによるＨ／Ｗパケット転送機能と、ハードウェアによるＨ／Ｗ経路探索を行う経路テーブルとを備え、前記ネットワークデバイスを介して転送された受信パケットの宛先ＩＰアドレスに一致する経路を前記Ｈ／Ｗ経路テーブルから探索し、前記受信パケットの当該経路が示すネットワークデバイスへの転送、又は、前記ＣＰＵへの転送を行う。
前記ＣＰＵは、ソフトウェアによるＳ／Ｗパケット転送手段と、ソフトウェアによるＳ／Ｗ経路テーブルから経路を探索する経路探索手段と、ルーティング検索エンジンの制御を行うルーティング検索エンジン制御手段と、前記Ｓ／Ｗ経路テーブルに対して経路を登録する経路登録手段（ネットワークアプリケーション機能）とを含み、前記ルーティング検索エンジンから転送された受信パケットに対し、宛先ＩＰアドレスに一致する経路を前記Ｓ／Ｗ経路テーブルから探索し、前記受信パケットの当該経路が示すネットワークデバイスへの転送、又は、前記受信パケットの廃棄を行う。
前記ルーティング検索エンジン制御手段は、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路のうち、前記宛先ＩＰアドレスの宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブルから削除し、指示された経路をＨ／Ｗ経路テーブルに登録する経路登録機能を備える。
【００１０】
請求項２のルータ装置は、請求項１において、前記ルーティング検索エンジンは、前記Ｈ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｈ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＨ／Ｗ使用頻度カウンタを有し、
前記ＣＰＵは、前記Ｓ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｓ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＳ／Ｗ使用頻度カウンタを有し、
前記ルーティング検索エンジン制御手段は、前記経路登録機能に代えて、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路を宛先ネットワークアドレスの一部が重複する複数グループに分類し、各グループの宛先プリフィクスが最短の経路に対して、前記Ｓ／Ｗ使用頻度カウンタと前記Ｈ／Ｗ使用頻度ウンタから求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路を前記Ｈ／Ｗ経路テーブルから削除し、指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録機能を備えて成ることを特徴としている。
【００１１】
請求項３のルーティング検索制御方法は、ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンを備え、一方のネットワークデバイスから受信したパケットを他方のネットワークデバイスへ送信する際の経路検索の制御を行う方法であって、次の各手順を含むことを特徴としている。
前記ルーティング検索エンジンにより、前記ネットワークデバイスを介して転送された受信パケットの宛先ＩＰアドレスに一致する経路をハードウェアによるＨ／Ｗ経路テーブルから探索し、一致する経路が見つかれば前記受信パケットを当該経路が示すネットワークデバイスに転送し、一致する経路が見つからない時には前記受信パケットを前記ＣＰＵに転送する第１の転送手順。
前記ＣＰＵにより、前記ルーティング検索エンジンから転送された受信パケットに対し、宛先ＩＰアドレスに一致する経路をソフトウェアによるＳ／Ｗ経路テーブルから探索し、一致する経路が見つかれば前記受信パケットを当該経路が示すネットワークデバイスに転送し、一致する経路が見つからない時には前記受信パケットを廃棄する第２の転送手順。
前記ＣＰＵにより、前記Ｓ／Ｗ経路テーブルで指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路を前記Ｈ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路のうち、前記宛先ＩＰアドレスの宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブルから削除し、指示された経路をＨ／Ｗ経路テーブルに登録する経路登録手順。
【００１２】
請求項４のルーティング検索制御方法は、請求項３において、前記ルーティング検索エンジンは、前記Ｈ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｈ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＨ／Ｗ使用頻度カウンタを有し、
前記ＣＰＵは、前記Ｓ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｓ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＳ／Ｗ使用頻度カウンタを有する一方、
前記ＣＰＵは、前記経路登録手順に代えて、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路を宛先ネットワークアドレスの一部が重複する複数グループに分類し、各グループの宛先プリフィクスが最短の経路に対して、前記Ｓ／Ｗ使用頻度カウンタと前記Ｈ／Ｗ使用頻度ウンタから求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路を前記Ｈ／Ｗ経路テーブルから削除し、指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録手順を具備することを特徴としている。
【発明の効果】
【００１３】
本発明のルータ装置及びルーティング検索制御方法によれば、先ず、受信パケットの宛先ＩＰアドレスに一致する経路をハードウェアによるＨ／Ｗ経路テーブルから探索し、一致する経路が見つからない時にのみ受信パケットをＣＰＵに転送して宛先ＩＰアドレスに一致する経路をソフトウェアによるＳ／Ｗ経路テーブルから探索するので、ハードウェアの記憶量が比較的低容量であってもパケット転送における高スループットを維持可能とすることができるとともに、ルータ装置全体で経路探索結果の一貫性が維持できる。
【００１４】
本発明のルータ装置及びルーティング検索制御方法によれば、転送先に指示された経路をＨ／Ｗ経路テーブルに登録する経路登録手順を有することで、経路探索に際しての高速化を図ることができる。
また、転送先に指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録手順を有することで、使用頻度の高い経路に対しての経路探索に際して、更なる高速化を図ることができる。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明の最良の実施形態について詳細に説明する。図１は、本発明のルータ装置が適用されるＩＰボタン電話装置１００の主要部の構成を示したブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００１６】
このＩＰボタン電話装置１００は、外線としてアナログ回線、ナンバーディスプレイ契約回線、網番号ダイヤルイン回線、アナログ専用線、デジタル専用線およびISDN回線などのレガシー（従来型・旧型）外線のみならず、ＩＰ専用回線、VoＩＰ回線、NGN (next generation network：次世代ネットワーク)回線を利用できる。また、内線端末として一般アナログ端末、ISDN端末、ホテルフォンおよびFAXなどのレガシー端末のみならず、デジタルボタン電話機やＩＰ電話機などのＩＰ端末を収容し、各外線と各内線端末との間の通信を制御する。
【００１７】
ＩＰボタン電話装置１００において、主制御ユニットCCU (Central Control Unit)１は、システム全体を制御する。TDM制御ユニットTCCU２は、各レガシー端末とＩＰ網との間および各レガシー外線とＩＰ端末との間で時分割多重化通信(TDM)を制御する。カスタマエッジユニットCEU (Customer Edge Unite)３は、音声データと制御データとを多重化してＩＰ通信を行う高速ブロードバンドルータとしての機能を備える。音声変換ユニットVCU (Voice Conversion Unit)４は、音声データを高ビットレートの高音質データまたは低ビットレートの標準音質データに変換する。
【００１８】
前記TCCU２には、ファックス端末８１、ホテルフォン端末８２、デジタルボタン電話機８３、単体電話機８４などのレガシー端末、および一般外線、ISDNネット回線、デジタル専用線、アナログ専用線などのレガシー外線が、各種の専用インターフェースおよびTDM通信用のTDMバス５を介して接続されている。前記TDMバス５は、制御データを送受信するDチャネルおよび音声信号を送受信するBチャネルを備える。
【００１９】
前記CCU１とTCCU２とは音声用LAN８および制御用LAN９の２本のLANで接続されている。CCU１とCEU３およびVCU４とは制御用LANで接続されている。前記CCU１には更に、保守用LAN１０を介して保守用コンピュータ９５が接続されると共に、ＩＰ内線LAN６を介してHUB７が接続されている。前記HUB７には、専用インターフェースを介してＩＰ電話機９１や音声会議装置９２が接続され、無線アクセスポイント(AP)にはＩＰコードレスフォン９３が収容され、さらにソフトフォン９４のアプリケーションが実装されたコンピュータが接続されている。
【００２０】
前記CCU１は、CPU１１、DDR メモリ（RAM）１２、フラッシュメモリ１３、パケット転送の制御に特化した専用チップ１４、挿抜自在のコンパクトフラッシュ(登録商標)（CF）メモリ１５およびレイヤ2(L2)スイッチ１６を主要な構成としている。
前記TCCU２は、CPU２１、DDR メモリ２２、フラッシュメモリ２３、ファイ(PHY)２４、前記Bチャネルを制御するハイウエイスイッチ２５、前記Dチャネルを制御するDch制御信号通信チップ２６およびDSP(Digital Signal Processor)２７を主要な構成としている。前記PHY２４は、Ethernet(登録商標)(図示せず)の物理層を制御するLSIである。
【００２１】
前記CEU３は、CPU３１、DDRメモリ３２、フラッシュメモリ３３、パケット転送の制御に特化した専用チップ３４およびL2スイッチ３５を主要な構成としている。VCU４は、CPU４１、DDRメモリ４２、フラッシュメモリ４３、L2スイッチ４４およびDSP４５を主要な構成としている。DSP４５は、音声情報を高品質から標準音質への変換、若しくはその逆の変換を行う。
【００２２】
このように、本実施形態ではCCU１、TCCU２、CEU３およびVCU４のそれぞれにCPU１１，２１，３１，４１を分散配置することで負荷分散を実現すると共に、CCU１およびCEU３には更に、パケット転送に特化した専用チップ１４，３４を搭載することでCPUにおけるパケット転送の処理を軽減し、更なる負荷分散を実現している。
【００２３】
このような構成において、レガシー端末（例えば、単体電話機８４）がNGN経由で発着信した場合、レガシー端末とTCCU２との間ではPCM変換された音声信号がTDMバス５上で時分割多重化通信により送受信される。TCCU２とCCU１との間にはＩＰセッションが確立され、このＩＰセッションにおいて音声信号のデータパケットが交換される。CEU３では前記L2スイッチ３５によりNGNが選択されており、CCU１およびCEU３は、それぞれの専用チップ１４，３４を利用してパケットを交換する。
【００２４】
また、ＩＰ端末がレガシー外線（例えば、ISDNネット）経由で発着信した場合は、TDMバス５，TCCU２，CCU１およびHUB７を介してデータが送受信される。さらに、ＩＰ端末がNGN経由で発着信した場合は、CEU３，CCU１およびHUB７を介してデータが送受信される。
【００２５】
本発明のルータ装置は、図１におけるCCU１又はCEU３内に適用されるものであり、その詳細な構成について、図２〜図６を参照しながら説明する。CEU３は回線数が多数である場合にCCU１に加えて接続されるものであり、ＩＰボタン電話装置１００がCCU１のみで構成される場合には本発明のルータ装置はCCU１内に、ＩＰボタン電話装置１００がCCU１及びCEU３で構成する場合には本発明のルータ装置はCEU３内に適用される。
【００２６】
ルータ装置は、図２のブロック図に示すように、所望のソフトウェアが実行されることで各種手段を機能させるＣＰＵ１１０（図１ではＣＰＵ１１，３１に対応）と、所望のソフトウェアが実行されることでＳ／Ｗ経路テーブル１２１となるＲＡＭ１２０（図１ではＤＤＲメモリ１２，３２に対応）と、ハードウェア資質である集積回路で構成されたＡＳＩＣ１３０（図１では専用チップ１３，３４に対応）がローカルバス１０１を介して接続されている。
【００２７】
ＡＳＩＣ１３０は、ルーティング検索エンジン１３１と、パケットの送受信を行うネットワークデバイスとして２系統のＭＡＣ（Media Access Control）１３５，１３５を備えている。各ＭＡＣ１３５は、ケーブル線で構成されたＰＨＹ（物理層）１４０，１４０に接続され、ＰＨＹ（物理層）１４０，１４０を介して外部よりパケットを受信し、送信するように構成されている。
パケットの送受信を行うためのＰＨＹ（物理層）１４０は、図１においては接続線１０２，１０３，１０４に該当している。すなわち、ＩＰボタン電話装置１００がCCU１及びCEU３で構成される場合は、ＰＨＹ（物理層）１４０は接続線１０３（ＷＡＮ側），接続線１０４（ＬＡＮ側）に該当し、ＩＰボタン電話装置１００がCCU１のみで構成される場合は、ＰＨＹ（物理層）１４０は接続線１０２（ＩＰ内線LAN６），接続線１０４（ＷＡＮ側）に該当することで、ＨＵＢ７に接続されるＬＡＮ側及びＩＰ網に接続されるＷＡＮ側に対してパケットを送受信可能なように構成されている。
各パケットには、ＩＰｖ４の場合、２進表記による最大で３２桁の宛先ＩＰアドレス（ネットワークアドレス）が、ＩＰｖ６の場合、２進表記による最大で１２８桁の宛先ＩＰアドレス（ネットワークアドレス）が割り当てられている。この宛先ＩＰアドレスにおいて、既に「０」か「１」のいずれかに決まっている桁数の数が宛先プリフィクスであり、その値はＩＰｖ４の場合は「３２」が、ＩＰｖ６の場合は「１２８」が最長となり、「０」が最低となる。
【００２８】
ルーティング検索エンジン１３１は、受信パケットを指示された経路に転送するＨ／Ｗパケット転送手段１３２と、過去の送信先経路が複数個登録されたＨ／Ｗ経路テーブル１３３を有し、ＭＡＣ１３５を介して転送された受信パケットの宛先ＩＰアドレスに一致する経路を、Ｈ／Ｗ経路テーブル１３３から探索し、一致する経路が見つかれば受信パケットを経路が示すネットワークデバイスにＨ／Ｗパケット転送手段１３２により転送し、一致する経路が見つからない時には受信パケットをＣＰＵ１１０に転送する処理が行われる。
【００２９】
ＣＰＵ１１０は、ルーティング検索エンジン１３１から転送された受信パケットを指示された経路に転送するＳ／Ｗパケット転送手段１１１と、ルーティング検索エンジン制御手段１１２と、ネットワークアプリケーション（経路登録手段）１１３と、ＡＰＩ１１４を備えている。Ｓ／Ｗパケット転送手段１１１は、ソフトウェアにより受信パケットを転送する機能を有している。
【００３０】
ルーティング検索エンジン制御手段１１２は、ＡＳＩＣ１３０を介して転送された受信パケットの宛先ＩＰアドレスに一致する経路を、Ｓ／Ｗ経路テーブル１２１から探索し、一致する経路が見つかれば受信パケットを経路が示すネットワークデバイスにＳ／Ｗパケット転送手段１１１により転送し、一致する経路が見つからない時には受信パケットを廃棄する処理が行われる。
【００３１】
ネットワークアプリケーション１１３は、Ｓ／Ｗ経路テーブルに対して経路を登録する経路登録機能（ネットワークアプリケーション機能）を有している。
ＡＰＩ１１４は、ネットワークアプリケーション１１３からの指示により指示された経路をＳ／Ｗ経路テーブル１２１に登録し、指示された経路をルーティング検索エンジン制御機能１１２に通知する処理を行うものである。
【００３２】
したがって、ＣＰＵ上で動作するソフトウェアは、Ｓ／Ｗパケット転送手段１１１による転送機能と、Ｓ／Ｗ経路テーブル１２１から経路を探索する機能と、ルーティング検索エンジン制御手段１１２を制御する機能と、ネットワークアプリケーション１１３及びＡＰＩ１１４を制御するプログラムから構成されている。
【００３３】
上記した構成のルータ装置によるパケット転送動作について、図３のフローチャート図を参照しながら説明する。
ネットワークデバイス（ＭＡＣ１３５）は、パケットを受信すると、受信パケットをＡＳＩＣ１３０のルーティング検索エンジン１３１に転送する（ステップ２０１）。
ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２によって、受信パケットの宛先ＩＰアドレスに一致する経路を最長一致探索によりＨ／Ｗ経路テーブル１３３から探索し（ステップ２０２）、一致する経路が見つかれば、受信パケットを、当該経路が示すネットワークデバイスにパケットを転送し、パケット送信が行われる（ステップ２０３）。
Ｈ／Ｗ経路テーブル１３３での探索において、受信パケットの宛先ＩＰアドレスに一致する経路が見つからなければ、受信パケットをＣＰＵ１１０に転送する（ステップ２０２）。
【００３４】
ＣＰＵ上のソフトウェアで実行されるルーティング検索エンジン制御手段１１２により、Ｓ／Ｗパケット転送手段１１１の転送機能によって、受信パケットの宛先ＩＰアドレスに一致する経路を最長一致探索によりＳ／Ｗ経路テーブル１２１から探索し（ステップ２０４）、一致する経路が見つかれば、受信パケットを、当該経路が示すネットワークデバイスにパケットを転送し（ステップ２０３）、一致する経路が見つからなければ、受信パケットを廃棄する（ステップ２０５）。
【００３５】
次に、ルータ装置による新規経路登録動作について、図４のフローチャートを参照しながら説明する。
ネットワークアプリケーション１１３が新規経路を登録することをＡＰＩ１１４に通知する（ステップ２１０）。
ＡＰＩ１１４は、ネットワークアプリケーション１１３からの指示により、指示された経路をＳ／Ｗ経路テーブルに登録するとともに、指示された経路をルーティング検索エンジン制御手段１１２に通知する（ステップ２１１）。
【００３６】
ルーティング検索エンジン制御手段１１２は、指示された経路を含めた経路総数がＨ／Ｗ経路テーブル１３３の記憶容量を越えるかを判定し（ステップ２１２）、超えていなければ、指示された経路をＨ／Ｗ経路テーブル１３３に登録する（ステップ２１３）。超えている場合には、Ｓ／Ｗ経路テーブル１２１に記憶された経路を含めた全ての経路のうち、宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブル１３３から削除し（ステップ２１４）、指示された経路をＨ／Ｗ経路テーブル１３３に登録する（ステップ２１３）。
【００３７】
上記したルータ装置におけるルーティング検索エンジン制御の動作について、図５及び図６を参照しながら説明する。図５及び図６は、ルータ装置において、Ｓ／Ｗ経路テーブル１２１の記憶容量が無制限であり、Ｈ／Ｗ経路テーブル１３１の記憶容量が６経路である例について説明する。
図５（ケース１）は、経路総数≦Ｈ／Ｗ経路テーブルの記憶容量の関係にある場合を示している。この場合、Ｓ／Ｗ経路テーブル１２１とＨ／Ｗ経路テーブル１３３はいずれも経路数が６であり、同一である。
【００３８】
図６（ケース２）は、前記状態において、ネットワークアプリケーションがＡＰＩを使用して新たに経路を追加することで、経路総数＞Ｈ／Ｗ経路テーブルの記憶容量の関係となる場合を示している。このケースの場合、ルーティング検索エンジン制御手段１１２により、宛先プリフィクス最短の経路である経路１に相当する経路がＨ／Ｗ経路テーブル１３３から削除され、新規経路（宛先プリフィクスの値が「２０」）がＨ／Ｗ経路テーブル１３３に登録されている。
【００３９】
以下に、図６のケース２において、パケット転送がルーティング検索エンジン１３１内で完結する事例と、ＣＰＵ１１０上のソフトウェアで処理される事例について、受信パケットの経路検索動作を説明する。
【００４０】
（パケット転送がルーティング検索エンジン１３１で完結する事例）
ルータ装置が宛先ＩＰアドレスの「０」「１」の値が「１６」桁まで決まっている経路４（宛先プリフィクスの値が「１６」）に一致するパケットを受信した場合の動作について、図６及び図２を参照して説明する。
先ず、パケット入出力部であるＭＡＣ１３５は、受信パケットをルーティング検索エンジン１３１に転送する。ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２において、受信パケットの宛先ＩＰアドレスに一致する経路を、最長一致探索によってＨ／Ｗ経路テーブル１３３から探索する。最長一致探索とは、宛先ＩＰアドレスにおいて一致する桁数が多い方から優先的に探索を行うものである。
【００４１】
図６の場合、宛先プリフィクスの高い経路から順に探索され、経路を選択する処理が行われる。すなわち、Ｈ／Ｗ経路テーブル１３３において、経路Ｆ，Ｅ，Ｄ，Ｃの順に探索され、宛先プリフィクスの値が「１６」である経路Ｃ（＝経路４）を選択し、パケット転送が完結する。この検索では、宛先プリフィクスの高い経路から順に探索されるので、最初に見つけた経路が宛先プリフィクスの高い経路となる。
また、仮に、この状態でＳ／Ｗパケット転送手段１１において探索処理が行われた場合、Ｓ／Ｗ経路テーブル１２１から、経路７，６，５，４の順に探索され、経路４を選択するので、Ｈ／Ｗ経路テーブル１３３で探索した場合と同一の結果となる。
以上のように、受信パケットに該当する経路がルーティング検索エンジン１３１に存在する場合は、ルーティング検索エンジン１３１でパケット転送が完結され、且つ、ルータ装置全体として経路探索結果の一貫性が維持されている。
【００４２】
（パケット転送がＣＰＵ１１０のソフトウェアで処理される事例）
ルータ装置が宛先プリフィクスの値が「４」である経路１に一致するパケットを受信した場合の動作を説明する。
パケット入出力部は、例１と同様に、受信パケットをルーティング検索エンジン１３１に転送する。ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２において、受信パケットの宛先ＩＰアドレスに一致する経路を、最長一致探索によってＨ／Ｗ経路テーブル１３３から探索する。図６の場合、宛先プリフィクスの高い経路から順に探索され、最初に見つけた経路を選択する。すなわち、経路Ｆ，Ｅ，Ｄ，Ｃ，Ｂ，Ａの順に探索されるが、いずれにも一致しないため、ＣＰＵ１１０に受信パケットを転送する。
【００４３】
ＣＰＵ１１０上のソフトウェアは、Ｓ／Ｗパケット転送手段１１１において最長一致探索によってＳ／Ｗ経路テーブル１２１から探索する。図６の場合、宛先プリフィクスの高い経路から順に探索され、最初に見つけた経路を選択する。すなわち、経路７，６，５，４，３，２，１の順に探索され、宛先プリフィクスの値が「４」である経路１を選択する。
したがって、受信パケットに該当する経路がルーティング検索エンジン１３１に無い場合でも、ＣＰＵ１１０上のソフトウェア（Ｓ／Ｗパケット転送手段１１１）でパケット転送が実行され、且つ、ルータ装置全体として経路探索結果の一貫性が維持されている。
【００４４】
上述した構成によれば、ＣＰＵ１１０上のソフトウェア（Ｓ／Ｗパケット転送手段１１１）によるパケット転送を併用することで、ハードウェア資質により構成されたルーティング検索エンジン１３１の記憶容量が低容量であっても高いパケット転送能力を維持することができる。
【００４５】
本発明のルータ装置の実施形態の他の例について、図７〜図１０を参照しながら説明する。
図７に示したルータ装置は、図２のルータ装置と同様に、所望のソフトウェアが実行されることで各種手段を機能させるＣＰＵ１１０と、所望のソフトウェアが実行されることでＳ／Ｗ経路テーブル１２１となるＲＡＭ１２０と、ハードウェア資質である集積回路で構成されたＡＳＩＣ１３０がローカルバス１０１を介して接続されている。図７において、図２と同様の構成を採る部分については、同一符号を付している。
【００４６】
すなわち、このルータ装置は、図２と同様に、ＣＰＵ１１０、ＲＡＭ１２０、ＡＳＩＣ１３０、ＰＨＹ１４０から構成され、ＣＰＵ１１０は、ソフトウェアにより実行されるＳ／Ｗパケット転送手段１１１、ルーティング検索エンジン制御手段１１２を備え、ＲＡＭ１２０上にＳ／Ｗ経路テーブル１２１を備える。また、ＡＳＩＣ１３０は、ルーティング検索エンジンと、２系統のＭＡＣ１３５，１３５を備え、ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２、Ｈ／Ｗ経路テーブル１３３を備える。
【００４７】
そして、このルータ装置は、図２のルータ装置の構成に加えて、ＣＰＵ１１０上にソフトウェアで動作するＳ／Ｗ使用頻度カウンタ１１５を備えるともに、ＡＳＩＣ１３０のルーティング検索エンジン１３１にＨ／Ｗ使用頻度カウンタ１３４を備えている。
【００４８】
Ｓ／Ｗ使用頻度カウンタ１１５は、Ｓ／Ｗ経路テーブル１２１が記憶する経路毎にカウンタ値を備え、ＣＰＵ１１０上のソフトウェアによるＳ／Ｗパケット転送手段１１１によって探索された経路に応じたカウンタ値を加算する。
Ｈ／Ｗ使用頻度カウンタ１３４は、Ｈ／Ｗ経路テーブル１３３が記憶する経路毎にカウンタ値を備え、ルーティング検索エンジン１３１のＨ／Ｗパケット転送機能１３２によって探索された経路に応じたカウンタ値を加算する。
【００４９】
Ｓ／Ｗ使用頻度カウンタ１１５及びＨ／Ｗ使用頻度カウンタ１３４を備えたルータ装置による新規経路登録動作について、図８のフローチャートを参照しながら説明する。
先ず、ネットワークアプリケーション１１３が新規経路を登録することをＡＰＩ１１４に通知する（ステップ１１０）。
ＡＰＩ１１４は、ネットワークアプリケーション１１３からの指示により、指示された経路をＳ／Ｗ経路テーブル１２１に登録するとともに、指示された経路をルーティング検索エンジン制御手段１１２に通知する（ステップ２１１）。
【００５０】
ルーティング検索エンジン制御手段１１２は、指示された経路を含めた経路総数がＨ／Ｗ経路テーブル１３３の記憶容量を越えるかを判定し（ステップ２１２）、超えていなければ、指示された経路をＨ／Ｗ経路テーブル１３３に登録する（ステップ２１３）。ここまでの処理は、図２のルータ装置のルーティング検索エンジン制御手段１１２と同様である。
【００５１】
そして、経路総数がＨ／Ｗ経路テーブル１３３の記憶容量を越えている場合、Ｓ／Ｗ経路テーブル１２１に記憶されたすべての経路を宛先ネットワークアドレスが重複するグループに分類し（ステップ２１５）、各グループの宛先プリフィクスが最短の経路に対して、Ｓ／Ｗ使用頻度カウンタ１１５とＨ／Ｗ使用頻度カウンタ１３４から求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路をＨ／Ｗ経路テーブル１３３から削除し（ステップ２１６）、指示された経路をＨ／Ｗ経路テーブル１３３に登録する（ステップ２１３）。
【００５２】
図７のルータ装置におけるルーティング検索エンジン制御の動作について、図９及び図１０を参照しながら説明する。図９及び図１０は、ルータ装置において、Ｓ／Ｗ経路テーブル１２１の記憶容量が無制限であり、Ｈ／Ｗ経路テーブル１３３の記憶容量が６経路である例について説明する。
図９（ケース１）は、経路総数≦Ｈ／Ｗ経路テーブルの記憶容量の関係にある場合を示している。この場合、Ｓ／Ｗ経路テーブル１２１とＨ／Ｗ経路テーブル１３３はいずれも経路数が６であり、同一である。
【００５３】
図１０（ケース２）は、前記状態において、ネットワークアプリケーションがＡＰＩを使用して新たに経路を追加することで、経路総数＞Ｈ／Ｗ経路テーブルの記憶容量の関係となる場合を示している。この場合、ルーティング検索エンジン制御手段１１２により、Ｓ／Ｗ経路テーブル１２１の全ての経路を、宛先ネットワークアドレスが重複するグループに分類する。図１０のケース２の場合、グループＡとグループＢの二つのグループに分類している。そして、各グループの宛先プリフィクス最短の経路の使用頻度を、Ｓ／Ｗ使用頻度カウンタ１１５とＨ／Ｗ使用頻度カウンタ１３４の値を合算することで求め、使用頻度が最低の経路である経路２−１に相当する経路をＨ／Ｗ経路テーブル１３３から削除し、新規経路をＨ／Ｗ経路テーブル１３３に登録する。
【００５４】
以下に、図１０のケース２において、パケット転送がルーティング検索エンジン１３１内で完結する事例と、ＣＰＵ１１０上のソフトウェアで処理される事例について、受信パケットの経路検索動作を説明する。
【００５５】
（パケット転送がルーティング検索エンジン３１で完結する事例）
ルータ装置がＳ／Ｗ経路テーブル１２１に登録された経路２−２に一致するパケットを受信した場合の動作を説明する。
パケット入出力部は、受信パケットをルーティング検索エンジン１３１に転送する。ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２において、受信パケットの宛先ＩＰアドレスに一致する経路を、最長一致探索によってＨ／Ｗ経路テーブル１３３から探索する。図１０の場合、宛先プリフィクスの高い経路から順に探索されるので、最初に一致した経路が宛先プリフィクスの高い経路となるのでこれを選択する。すなわち、経路Ｆ，Ｅ，Ｄ，Ｃの順に探索され、経路Ｃ（＝経路２−２）を選択し、パケット転送が完結する。
仮に、この状態でＳ／Ｗパケット転送手段１１１においてＳ／Ｗ経路テーブル１２１から探索した場合、経路２−２，１−４，１−３，２−２の順に探索され、経路２−２を選択する。
以上のように、受信パケットに該当する経路がルーティング検索エンジンに在る場合は、ルーティング検索エンジンでパケット転送が完結され、且つ、ルータ全体として経路探索結果の一貫性が維持されている。
【００５６】
（パケット転送がＣＰＵ１１０上のソフトウェアで処理される事例）
ルータ装置がＳ／Ｗ経路テーブル１２１に登録された経路２−１に一致するパケットを受信した場合の動作を説明する。
パケット入出力部は、受信パケットをルーティング検索エンジンに転送する。ルーティング検索エンジンは、Ｈ／Ｗパケット転送機能において、受信パケットの宛先ＩＰアドレスに一致する経路を、最長一致探索によってＨ／Ｗ経路テーブル１３３から探索する。図１０の場合、宛先プリフィクスの高い経路から順に探索されるので、最初に一致した経路が宛先プリフィクスの高い経路となるのでこれを選択する。すなわち、経路Ｆ，Ｅ，Ｄ，Ｃ，Ｂ，Ａの順に探索されるが、いずれにも一致しないため、ＣＰＵに受信パケットを転送する。ＣＰＵ１１０上のソフトウェアは、Ｓ／Ｗパケット転送手段１１１において最長一致探索によってＳ／Ｗ経路テーブル１２１から探索する。図１０の場合、宛先プリフィクスの高い経路から順に探索されるので、最初に一致した経路が宛先プリフィクスの高い経路となるのでこれを選択する。すなわち、経路２−３，１−４，１−３，２−２，１−２，２−１の順に探索され、経路２−１を選択する。
以上のように、受信パケットに該当する経路がルーティング検索エンジン１３１に無い場合でも、ＣＰＵ１１０上のソフトウェアでパケット転送され、且つ、ルータ全体として経路探索結果の一貫性が維持されている。
【００５７】
次に、図７のルータ装置におけるルーティング検索エンジンの経路検索についての制御動作をより明確にするために、図１１と図１２を用いて説明する。
図１１は、ルータ装置が具備するＳ／Ｗ経路テーブル１２１を示しており、ネットワークアプリケーションによって、経路ア、イ、ウ、エの４つの経路が登録されており、経路毎にＳ／Ｗ使用頻度カウンタとＨ／Ｗ使用頻度カウンタの値を合算し、カウンタ合算値を所定のしきい値で２分割して使用頻度を高・低に２値化して管理している。また、カウンタの合算値をそのまま使用頻度としてもよいし、高・低の２値ではなく、例えば４つの使用頻度に分割してもよい。
【００５８】
図１２は、すべてのＩＰアドレスを、デフォルトゲートウェイを根とし、ネットワークアドレスの先頭ビットから順に２値で枝分かれする二分木のうち、先頭４ビットまでを示した図である。
【００５９】
ルーティング検索エンジン制御機能は、経路総数＞Ｈ／Ｗ経路テーブルの記憶容量の関係を満たした場合、Ｓ／Ｗ経路テーブルのすべての経路を、宛先ネットワークアドレスが重複するグループに分類する。ここで、宛先ネットワークアドレスが重複するグループとは、図１２の登録済の経路（白塗りの丸）を根とする枝木に含まれる経路を意味する。すなわち、経路アを根とする枝木をグループＡとすると、経路イがこの枝木に含まれるため、グループＡに含まれる経路は経路ア、イとなる。また、経路ウを根とする枝木をグループＢとすると、経路エがこの枝木に含まれるため、グループＢに含まれる経路は経路ウ、エとなる。
グループＡとグループＢは、宛先ネットワークアドレスの先頭ビットが互いに重複しないことは、図１２から明らかである。従って、受信パケットの宛先ネットワークアドレスがあるグループの経路に一致する場合、別のグループの経路には一致しない。つまり、「最長一致探索において、異なるグループの経路に一致することは起こりえない」という特徴を持つ。
上記の特徴により、分類したグループのうち、いずれのグループの宛先プリフィクス最短の経路を削除しても、ルータ装置全体での経路探索結果の一貫性は維持される。
【００６０】
上述の構造によれば、各経路の使用頻度について、削除経路を選択する条件に加えることにより、経路の使用頻度を管理することで図２の例に比較して、更に高いパケット転送能力を維持することができる。
【００６１】
上述した各ルータ装置によれば、高スループットを維持可能な構成を低コストで作製することが可能となる。
【図面の簡単な説明】
【００６２】
【図１】本発明のルータ装置が適用されるＩＰボタン電話装置のブロック図である。
【図２】本発明のルータ装置の実施形態の一例を示すブロック図である。
【図３】本発明のルータ装置におけるパケット転送の動作を説明するためのフローチャート図である。
【図４】図２のルータ装置における新規経路登録の動作を説明するためのフローチャート図である。
【図５】図２のルータ装置におけるルーティング検索エンジン制御の動作を示す図である。
【図６】図２のルータ装置におけるルーティング検索エンジン制御の動作を示す図である。
【図７】本発明のルータ装置の実施形態の他の例を示すブロック図である。
【図８】図７のルータ装置における新規経路登録の動作を説明するためのフローチャート図である。
【図９】図７のルータ装置におけるルーティング検索エンジン制御の動作を示す図である。
【図１０】図７のルータ装置におけるルーティング検索エンジン制御の動作を示す図である。
【図１１】Ｓ／Ｗ経路テーブルに登録された宛先ＩＰアドレスを説明するための図である。
【図１２】Ｓ／Ｗ経路テーブルに登録された宛先ＩＰアドレスの属性を二分木で表現した図である。
【符号の説明】
【００６３】
１…ＣＣＵ、 ３…ＣＥＵ、 ６…ＩＰ内線ＬＡＮ、 １４，３４…専用チップ、 １００…ＩＰボタン電話装置、 １０１…ローカルバス、 １１０…ＣＰＵ、 １１１…Ｓ／Ｗパケット転送手段、 １１２…ルーティング検索エンジン制御手段、 １１３…ネットワークアプリケーション（経路登録手段）、 １１５…Ｓ／Ｗ使用頻度カウンタ、１２０…ＲＡＭ、 １２１…Ｓ／Ｗ経路テーブル、 １３０…ＡＳＩＣ、 １３１…ルーティング検索エンジン、 １３２…Ｈ／Ｗパケット転送機能、 １３３…Ｈ／Ｗ経路テーブル、 １３４…Ｈ／Ｗ使用頻度カウンタ、 １３５…ＭＡＣ、 １４０…ＰＨＹ。
【技術分野】
【０００１】
本発明は、ＩＰネットワーク上のルータ装置及びルータ装置におけるルーティング検索制御方法に関し、特に、インターネット接続におけるパケット転送経路を検索するルーティング検索エンジンの制御に関する。
【背景技術】
【０００２】
ルータ装置は、異なるネットワーク間を相互に接続するための中継機器として用いられるものであり、パケットに付与された宛先ＩＰアドレスを識別し検索テーブルにしたがって転送するルーティング処理が行われるが、その高速化を図るため例えば特許文献１や特許文献２に示されるような種々の検索制御方法が提案されている。
【特許文献１】特開２０００−１７４８０５号公報
【特許文献２】特開平１１−３４１０７６号公報
【０００３】
ルータ装置において、受信パケットの送信先を検索するルーティング検索制御については、通常ソフトウェアを用いてＣＰＵ（中央演算装置）で処理している。ルーティング検索制御に関する処理は、パケットの通過・廃棄の可否を設定されたフィルタリング情報に基づいて単に判定する処理と異なり、検出したパケットの転送先を検索する処理が発生するため大きくなり、その結果ＣＰＵに負担をかけることになる。
【０００４】
近年、光ファイバによるインターネット接続サービスの普及が進み、エントリークラスのルータ装置においてもＧｂｐｓクラスのパケット転送能力が求められている。Ｇｂｐｓクラスのルータ装置は、パケット転送能力を向上させるために、ルーティング検索エンジンとしてハードウェア資質を用いるのが一般的である。
ハードウェア資質を用いるルータ装置は、例えば、最初のパケットの転送先をソフトウェア処理により検索し、この時の検索結果をハードウェア検索用の経路テーブルに設定する。そして、以降の同一宛先のパケットについては、この経路テーブルを検索することによるハードウェア処理により転送が行われる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
一般的に、経路テーブルの記憶容量は、ハードウェア資質によるものよりソフトウェア処理による方が大きくなる。ハードウェア資質を用いるルータ装置は、経路総数がハードウェアの記憶容量を超えた場合、パケット転送を維持するため各種の対策が採られる。
例えば、ルータ装置において、全てのパケット転送をソフトウェア処理に移行することでパケット転送を維持する。この場合、スループットが激減する問題が生じる。
【０００６】
また、別の例では、ルータ装置において、ハードウェアから任意の経路を削除することでハードウェアによるパケット転送をある程度維持することが行われる。この結果、ハードウェア処理による経路探索結果と、ソフトウェア処理による経路探索結果との矛盾が発生し、パケット転送が実行できない場合があるという問題が生じる。
【０００７】
これらの問題を防ぐ一つの方法として、十分な記憶容量を備えたハードウェアを使用することが考えられるが、記憶容量が大きくなるほどルータ装置が高価となるという問題がある。
【０００８】
本発明は、上記実情に鑑みて提案されたもので、ハードウェアの記憶容量が比較的低容量であっても高スループットを維持可能とし、且つ、装置全体で経路探索結果の一貫性が維持できるルータ装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記問題点を解決するため本発明の請求項１に記載したルータ装置は、ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンと、該ルーティング検索エンジンに接続しパケットの送受信を行う複数のネットワークデバイスとを有する装置であって、次の各構成を含むことを特徴としている。
前記ルーティング検索エンジンは、ハードウェアによるＨ／Ｗパケット転送機能と、ハードウェアによるＨ／Ｗ経路探索を行う経路テーブルとを備え、前記ネットワークデバイスを介して転送された受信パケットの宛先ＩＰアドレスに一致する経路を前記Ｈ／Ｗ経路テーブルから探索し、前記受信パケットの当該経路が示すネットワークデバイスへの転送、又は、前記ＣＰＵへの転送を行う。
前記ＣＰＵは、ソフトウェアによるＳ／Ｗパケット転送手段と、ソフトウェアによるＳ／Ｗ経路テーブルから経路を探索する経路探索手段と、ルーティング検索エンジンの制御を行うルーティング検索エンジン制御手段と、前記Ｓ／Ｗ経路テーブルに対して経路を登録する経路登録手段（ネットワークアプリケーション機能）とを含み、前記ルーティング検索エンジンから転送された受信パケットに対し、宛先ＩＰアドレスに一致する経路を前記Ｓ／Ｗ経路テーブルから探索し、前記受信パケットの当該経路が示すネットワークデバイスへの転送、又は、前記受信パケットの廃棄を行う。
前記ルーティング検索エンジン制御手段は、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路のうち、前記宛先ＩＰアドレスの宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブルから削除し、指示された経路をＨ／Ｗ経路テーブルに登録する経路登録機能を備える。
【００１０】
請求項２のルータ装置は、請求項１において、前記ルーティング検索エンジンは、前記Ｈ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｈ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＨ／Ｗ使用頻度カウンタを有し、
前記ＣＰＵは、前記Ｓ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｓ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＳ／Ｗ使用頻度カウンタを有し、
前記ルーティング検索エンジン制御手段は、前記経路登録機能に代えて、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路を宛先ネットワークアドレスの一部が重複する複数グループに分類し、各グループの宛先プリフィクスが最短の経路に対して、前記Ｓ／Ｗ使用頻度カウンタと前記Ｈ／Ｗ使用頻度ウンタから求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路を前記Ｈ／Ｗ経路テーブルから削除し、指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録機能を備えて成ることを特徴としている。
【００１１】
請求項３のルーティング検索制御方法は、ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンを備え、一方のネットワークデバイスから受信したパケットを他方のネットワークデバイスへ送信する際の経路検索の制御を行う方法であって、次の各手順を含むことを特徴としている。
前記ルーティング検索エンジンにより、前記ネットワークデバイスを介して転送された受信パケットの宛先ＩＰアドレスに一致する経路をハードウェアによるＨ／Ｗ経路テーブルから探索し、一致する経路が見つかれば前記受信パケットを当該経路が示すネットワークデバイスに転送し、一致する経路が見つからない時には前記受信パケットを前記ＣＰＵに転送する第１の転送手順。
前記ＣＰＵにより、前記ルーティング検索エンジンから転送された受信パケットに対し、宛先ＩＰアドレスに一致する経路をソフトウェアによるＳ／Ｗ経路テーブルから探索し、一致する経路が見つかれば前記受信パケットを当該経路が示すネットワークデバイスに転送し、一致する経路が見つからない時には前記受信パケットを廃棄する第２の転送手順。
前記ＣＰＵにより、前記Ｓ／Ｗ経路テーブルで指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路を前記Ｈ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路のうち、前記宛先ＩＰアドレスの宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブルから削除し、指示された経路をＨ／Ｗ経路テーブルに登録する経路登録手順。
【００１２】
請求項４のルーティング検索制御方法は、請求項３において、前記ルーティング検索エンジンは、前記Ｈ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｈ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＨ／Ｗ使用頻度カウンタを有し、
前記ＣＰＵは、前記Ｓ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｓ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＳ／Ｗ使用頻度カウンタを有する一方、
前記ＣＰＵは、前記経路登録手順に代えて、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路を宛先ネットワークアドレスの一部が重複する複数グループに分類し、各グループの宛先プリフィクスが最短の経路に対して、前記Ｓ／Ｗ使用頻度カウンタと前記Ｈ／Ｗ使用頻度ウンタから求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路を前記Ｈ／Ｗ経路テーブルから削除し、指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録手順を具備することを特徴としている。
【発明の効果】
【００１３】
本発明のルータ装置及びルーティング検索制御方法によれば、先ず、受信パケットの宛先ＩＰアドレスに一致する経路をハードウェアによるＨ／Ｗ経路テーブルから探索し、一致する経路が見つからない時にのみ受信パケットをＣＰＵに転送して宛先ＩＰアドレスに一致する経路をソフトウェアによるＳ／Ｗ経路テーブルから探索するので、ハードウェアの記憶量が比較的低容量であってもパケット転送における高スループットを維持可能とすることができるとともに、ルータ装置全体で経路探索結果の一貫性が維持できる。
【００１４】
本発明のルータ装置及びルーティング検索制御方法によれば、転送先に指示された経路をＨ／Ｗ経路テーブルに登録する経路登録手順を有することで、経路探索に際しての高速化を図ることができる。
また、転送先に指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録手順を有することで、使用頻度の高い経路に対しての経路探索に際して、更なる高速化を図ることができる。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明の最良の実施形態について詳細に説明する。図１は、本発明のルータ装置が適用されるＩＰボタン電話装置１００の主要部の構成を示したブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００１６】
このＩＰボタン電話装置１００は、外線としてアナログ回線、ナンバーディスプレイ契約回線、網番号ダイヤルイン回線、アナログ専用線、デジタル専用線およびISDN回線などのレガシー（従来型・旧型）外線のみならず、ＩＰ専用回線、VoＩＰ回線、NGN (next generation network：次世代ネットワーク)回線を利用できる。また、内線端末として一般アナログ端末、ISDN端末、ホテルフォンおよびFAXなどのレガシー端末のみならず、デジタルボタン電話機やＩＰ電話機などのＩＰ端末を収容し、各外線と各内線端末との間の通信を制御する。
【００１７】
ＩＰボタン電話装置１００において、主制御ユニットCCU (Central Control Unit)１は、システム全体を制御する。TDM制御ユニットTCCU２は、各レガシー端末とＩＰ網との間および各レガシー外線とＩＰ端末との間で時分割多重化通信(TDM)を制御する。カスタマエッジユニットCEU (Customer Edge Unite)３は、音声データと制御データとを多重化してＩＰ通信を行う高速ブロードバンドルータとしての機能を備える。音声変換ユニットVCU (Voice Conversion Unit)４は、音声データを高ビットレートの高音質データまたは低ビットレートの標準音質データに変換する。
【００１８】
前記TCCU２には、ファックス端末８１、ホテルフォン端末８２、デジタルボタン電話機８３、単体電話機８４などのレガシー端末、および一般外線、ISDNネット回線、デジタル専用線、アナログ専用線などのレガシー外線が、各種の専用インターフェースおよびTDM通信用のTDMバス５を介して接続されている。前記TDMバス５は、制御データを送受信するDチャネルおよび音声信号を送受信するBチャネルを備える。
【００１９】
前記CCU１とTCCU２とは音声用LAN８および制御用LAN９の２本のLANで接続されている。CCU１とCEU３およびVCU４とは制御用LANで接続されている。前記CCU１には更に、保守用LAN１０を介して保守用コンピュータ９５が接続されると共に、ＩＰ内線LAN６を介してHUB７が接続されている。前記HUB７には、専用インターフェースを介してＩＰ電話機９１や音声会議装置９２が接続され、無線アクセスポイント(AP)にはＩＰコードレスフォン９３が収容され、さらにソフトフォン９４のアプリケーションが実装されたコンピュータが接続されている。
【００２０】
前記CCU１は、CPU１１、DDR メモリ（RAM）１２、フラッシュメモリ１３、パケット転送の制御に特化した専用チップ１４、挿抜自在のコンパクトフラッシュ(登録商標)（CF）メモリ１５およびレイヤ2(L2)スイッチ１６を主要な構成としている。
前記TCCU２は、CPU２１、DDR メモリ２２、フラッシュメモリ２３、ファイ(PHY)２４、前記Bチャネルを制御するハイウエイスイッチ２５、前記Dチャネルを制御するDch制御信号通信チップ２６およびDSP(Digital Signal Processor)２７を主要な構成としている。前記PHY２４は、Ethernet(登録商標)(図示せず)の物理層を制御するLSIである。
【００２１】
前記CEU３は、CPU３１、DDRメモリ３２、フラッシュメモリ３３、パケット転送の制御に特化した専用チップ３４およびL2スイッチ３５を主要な構成としている。VCU４は、CPU４１、DDRメモリ４２、フラッシュメモリ４３、L2スイッチ４４およびDSP４５を主要な構成としている。DSP４５は、音声情報を高品質から標準音質への変換、若しくはその逆の変換を行う。
【００２２】
このように、本実施形態ではCCU１、TCCU２、CEU３およびVCU４のそれぞれにCPU１１，２１，３１，４１を分散配置することで負荷分散を実現すると共に、CCU１およびCEU３には更に、パケット転送に特化した専用チップ１４，３４を搭載することでCPUにおけるパケット転送の処理を軽減し、更なる負荷分散を実現している。
【００２３】
このような構成において、レガシー端末（例えば、単体電話機８４）がNGN経由で発着信した場合、レガシー端末とTCCU２との間ではPCM変換された音声信号がTDMバス５上で時分割多重化通信により送受信される。TCCU２とCCU１との間にはＩＰセッションが確立され、このＩＰセッションにおいて音声信号のデータパケットが交換される。CEU３では前記L2スイッチ３５によりNGNが選択されており、CCU１およびCEU３は、それぞれの専用チップ１４，３４を利用してパケットを交換する。
【００２４】
また、ＩＰ端末がレガシー外線（例えば、ISDNネット）経由で発着信した場合は、TDMバス５，TCCU２，CCU１およびHUB７を介してデータが送受信される。さらに、ＩＰ端末がNGN経由で発着信した場合は、CEU３，CCU１およびHUB７を介してデータが送受信される。
【００２５】
本発明のルータ装置は、図１におけるCCU１又はCEU３内に適用されるものであり、その詳細な構成について、図２〜図６を参照しながら説明する。CEU３は回線数が多数である場合にCCU１に加えて接続されるものであり、ＩＰボタン電話装置１００がCCU１のみで構成される場合には本発明のルータ装置はCCU１内に、ＩＰボタン電話装置１００がCCU１及びCEU３で構成する場合には本発明のルータ装置はCEU３内に適用される。
【００２６】
ルータ装置は、図２のブロック図に示すように、所望のソフトウェアが実行されることで各種手段を機能させるＣＰＵ１１０（図１ではＣＰＵ１１，３１に対応）と、所望のソフトウェアが実行されることでＳ／Ｗ経路テーブル１２１となるＲＡＭ１２０（図１ではＤＤＲメモリ１２，３２に対応）と、ハードウェア資質である集積回路で構成されたＡＳＩＣ１３０（図１では専用チップ１３，３４に対応）がローカルバス１０１を介して接続されている。
【００２７】
ＡＳＩＣ１３０は、ルーティング検索エンジン１３１と、パケットの送受信を行うネットワークデバイスとして２系統のＭＡＣ（Media Access Control）１３５，１３５を備えている。各ＭＡＣ１３５は、ケーブル線で構成されたＰＨＹ（物理層）１４０，１４０に接続され、ＰＨＹ（物理層）１４０，１４０を介して外部よりパケットを受信し、送信するように構成されている。
パケットの送受信を行うためのＰＨＹ（物理層）１４０は、図１においては接続線１０２，１０３，１０４に該当している。すなわち、ＩＰボタン電話装置１００がCCU１及びCEU３で構成される場合は、ＰＨＹ（物理層）１４０は接続線１０３（ＷＡＮ側），接続線１０４（ＬＡＮ側）に該当し、ＩＰボタン電話装置１００がCCU１のみで構成される場合は、ＰＨＹ（物理層）１４０は接続線１０２（ＩＰ内線LAN６），接続線１０４（ＷＡＮ側）に該当することで、ＨＵＢ７に接続されるＬＡＮ側及びＩＰ網に接続されるＷＡＮ側に対してパケットを送受信可能なように構成されている。
各パケットには、ＩＰｖ４の場合、２進表記による最大で３２桁の宛先ＩＰアドレス（ネットワークアドレス）が、ＩＰｖ６の場合、２進表記による最大で１２８桁の宛先ＩＰアドレス（ネットワークアドレス）が割り当てられている。この宛先ＩＰアドレスにおいて、既に「０」か「１」のいずれかに決まっている桁数の数が宛先プリフィクスであり、その値はＩＰｖ４の場合は「３２」が、ＩＰｖ６の場合は「１２８」が最長となり、「０」が最低となる。
【００２８】
ルーティング検索エンジン１３１は、受信パケットを指示された経路に転送するＨ／Ｗパケット転送手段１３２と、過去の送信先経路が複数個登録されたＨ／Ｗ経路テーブル１３３を有し、ＭＡＣ１３５を介して転送された受信パケットの宛先ＩＰアドレスに一致する経路を、Ｈ／Ｗ経路テーブル１３３から探索し、一致する経路が見つかれば受信パケットを経路が示すネットワークデバイスにＨ／Ｗパケット転送手段１３２により転送し、一致する経路が見つからない時には受信パケットをＣＰＵ１１０に転送する処理が行われる。
【００２９】
ＣＰＵ１１０は、ルーティング検索エンジン１３１から転送された受信パケットを指示された経路に転送するＳ／Ｗパケット転送手段１１１と、ルーティング検索エンジン制御手段１１２と、ネットワークアプリケーション（経路登録手段）１１３と、ＡＰＩ１１４を備えている。Ｓ／Ｗパケット転送手段１１１は、ソフトウェアにより受信パケットを転送する機能を有している。
【００３０】
ルーティング検索エンジン制御手段１１２は、ＡＳＩＣ１３０を介して転送された受信パケットの宛先ＩＰアドレスに一致する経路を、Ｓ／Ｗ経路テーブル１２１から探索し、一致する経路が見つかれば受信パケットを経路が示すネットワークデバイスにＳ／Ｗパケット転送手段１１１により転送し、一致する経路が見つからない時には受信パケットを廃棄する処理が行われる。
【００３１】
ネットワークアプリケーション１１３は、Ｓ／Ｗ経路テーブルに対して経路を登録する経路登録機能（ネットワークアプリケーション機能）を有している。
ＡＰＩ１１４は、ネットワークアプリケーション１１３からの指示により指示された経路をＳ／Ｗ経路テーブル１２１に登録し、指示された経路をルーティング検索エンジン制御機能１１２に通知する処理を行うものである。
【００３２】
したがって、ＣＰＵ上で動作するソフトウェアは、Ｓ／Ｗパケット転送手段１１１による転送機能と、Ｓ／Ｗ経路テーブル１２１から経路を探索する機能と、ルーティング検索エンジン制御手段１１２を制御する機能と、ネットワークアプリケーション１１３及びＡＰＩ１１４を制御するプログラムから構成されている。
【００３３】
上記した構成のルータ装置によるパケット転送動作について、図３のフローチャート図を参照しながら説明する。
ネットワークデバイス（ＭＡＣ１３５）は、パケットを受信すると、受信パケットをＡＳＩＣ１３０のルーティング検索エンジン１３１に転送する（ステップ２０１）。
ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２によって、受信パケットの宛先ＩＰアドレスに一致する経路を最長一致探索によりＨ／Ｗ経路テーブル１３３から探索し（ステップ２０２）、一致する経路が見つかれば、受信パケットを、当該経路が示すネットワークデバイスにパケットを転送し、パケット送信が行われる（ステップ２０３）。
Ｈ／Ｗ経路テーブル１３３での探索において、受信パケットの宛先ＩＰアドレスに一致する経路が見つからなければ、受信パケットをＣＰＵ１１０に転送する（ステップ２０２）。
【００３４】
ＣＰＵ上のソフトウェアで実行されるルーティング検索エンジン制御手段１１２により、Ｓ／Ｗパケット転送手段１１１の転送機能によって、受信パケットの宛先ＩＰアドレスに一致する経路を最長一致探索によりＳ／Ｗ経路テーブル１２１から探索し（ステップ２０４）、一致する経路が見つかれば、受信パケットを、当該経路が示すネットワークデバイスにパケットを転送し（ステップ２０３）、一致する経路が見つからなければ、受信パケットを廃棄する（ステップ２０５）。
【００３５】
次に、ルータ装置による新規経路登録動作について、図４のフローチャートを参照しながら説明する。
ネットワークアプリケーション１１３が新規経路を登録することをＡＰＩ１１４に通知する（ステップ２１０）。
ＡＰＩ１１４は、ネットワークアプリケーション１１３からの指示により、指示された経路をＳ／Ｗ経路テーブルに登録するとともに、指示された経路をルーティング検索エンジン制御手段１１２に通知する（ステップ２１１）。
【００３６】
ルーティング検索エンジン制御手段１１２は、指示された経路を含めた経路総数がＨ／Ｗ経路テーブル１３３の記憶容量を越えるかを判定し（ステップ２１２）、超えていなければ、指示された経路をＨ／Ｗ経路テーブル１３３に登録する（ステップ２１３）。超えている場合には、Ｓ／Ｗ経路テーブル１２１に記憶された経路を含めた全ての経路のうち、宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブル１３３から削除し（ステップ２１４）、指示された経路をＨ／Ｗ経路テーブル１３３に登録する（ステップ２１３）。
【００３７】
上記したルータ装置におけるルーティング検索エンジン制御の動作について、図５及び図６を参照しながら説明する。図５及び図６は、ルータ装置において、Ｓ／Ｗ経路テーブル１２１の記憶容量が無制限であり、Ｈ／Ｗ経路テーブル１３１の記憶容量が６経路である例について説明する。
図５（ケース１）は、経路総数≦Ｈ／Ｗ経路テーブルの記憶容量の関係にある場合を示している。この場合、Ｓ／Ｗ経路テーブル１２１とＨ／Ｗ経路テーブル１３３はいずれも経路数が６であり、同一である。
【００３８】
図６（ケース２）は、前記状態において、ネットワークアプリケーションがＡＰＩを使用して新たに経路を追加することで、経路総数＞Ｈ／Ｗ経路テーブルの記憶容量の関係となる場合を示している。このケースの場合、ルーティング検索エンジン制御手段１１２により、宛先プリフィクス最短の経路である経路１に相当する経路がＨ／Ｗ経路テーブル１３３から削除され、新規経路（宛先プリフィクスの値が「２０」）がＨ／Ｗ経路テーブル１３３に登録されている。
【００３９】
以下に、図６のケース２において、パケット転送がルーティング検索エンジン１３１内で完結する事例と、ＣＰＵ１１０上のソフトウェアで処理される事例について、受信パケットの経路検索動作を説明する。
【００４０】
（パケット転送がルーティング検索エンジン１３１で完結する事例）
ルータ装置が宛先ＩＰアドレスの「０」「１」の値が「１６」桁まで決まっている経路４（宛先プリフィクスの値が「１６」）に一致するパケットを受信した場合の動作について、図６及び図２を参照して説明する。
先ず、パケット入出力部であるＭＡＣ１３５は、受信パケットをルーティング検索エンジン１３１に転送する。ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２において、受信パケットの宛先ＩＰアドレスに一致する経路を、最長一致探索によってＨ／Ｗ経路テーブル１３３から探索する。最長一致探索とは、宛先ＩＰアドレスにおいて一致する桁数が多い方から優先的に探索を行うものである。
【００４１】
図６の場合、宛先プリフィクスの高い経路から順に探索され、経路を選択する処理が行われる。すなわち、Ｈ／Ｗ経路テーブル１３３において、経路Ｆ，Ｅ，Ｄ，Ｃの順に探索され、宛先プリフィクスの値が「１６」である経路Ｃ（＝経路４）を選択し、パケット転送が完結する。この検索では、宛先プリフィクスの高い経路から順に探索されるので、最初に見つけた経路が宛先プリフィクスの高い経路となる。
また、仮に、この状態でＳ／Ｗパケット転送手段１１において探索処理が行われた場合、Ｓ／Ｗ経路テーブル１２１から、経路７，６，５，４の順に探索され、経路４を選択するので、Ｈ／Ｗ経路テーブル１３３で探索した場合と同一の結果となる。
以上のように、受信パケットに該当する経路がルーティング検索エンジン１３１に存在する場合は、ルーティング検索エンジン１３１でパケット転送が完結され、且つ、ルータ装置全体として経路探索結果の一貫性が維持されている。
【００４２】
（パケット転送がＣＰＵ１１０のソフトウェアで処理される事例）
ルータ装置が宛先プリフィクスの値が「４」である経路１に一致するパケットを受信した場合の動作を説明する。
パケット入出力部は、例１と同様に、受信パケットをルーティング検索エンジン１３１に転送する。ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２において、受信パケットの宛先ＩＰアドレスに一致する経路を、最長一致探索によってＨ／Ｗ経路テーブル１３３から探索する。図６の場合、宛先プリフィクスの高い経路から順に探索され、最初に見つけた経路を選択する。すなわち、経路Ｆ，Ｅ，Ｄ，Ｃ，Ｂ，Ａの順に探索されるが、いずれにも一致しないため、ＣＰＵ１１０に受信パケットを転送する。
【００４３】
ＣＰＵ１１０上のソフトウェアは、Ｓ／Ｗパケット転送手段１１１において最長一致探索によってＳ／Ｗ経路テーブル１２１から探索する。図６の場合、宛先プリフィクスの高い経路から順に探索され、最初に見つけた経路を選択する。すなわち、経路７，６，５，４，３，２，１の順に探索され、宛先プリフィクスの値が「４」である経路１を選択する。
したがって、受信パケットに該当する経路がルーティング検索エンジン１３１に無い場合でも、ＣＰＵ１１０上のソフトウェア（Ｓ／Ｗパケット転送手段１１１）でパケット転送が実行され、且つ、ルータ装置全体として経路探索結果の一貫性が維持されている。
【００４４】
上述した構成によれば、ＣＰＵ１１０上のソフトウェア（Ｓ／Ｗパケット転送手段１１１）によるパケット転送を併用することで、ハードウェア資質により構成されたルーティング検索エンジン１３１の記憶容量が低容量であっても高いパケット転送能力を維持することができる。
【００４５】
本発明のルータ装置の実施形態の他の例について、図７〜図１０を参照しながら説明する。
図７に示したルータ装置は、図２のルータ装置と同様に、所望のソフトウェアが実行されることで各種手段を機能させるＣＰＵ１１０と、所望のソフトウェアが実行されることでＳ／Ｗ経路テーブル１２１となるＲＡＭ１２０と、ハードウェア資質である集積回路で構成されたＡＳＩＣ１３０がローカルバス１０１を介して接続されている。図７において、図２と同様の構成を採る部分については、同一符号を付している。
【００４６】
すなわち、このルータ装置は、図２と同様に、ＣＰＵ１１０、ＲＡＭ１２０、ＡＳＩＣ１３０、ＰＨＹ１４０から構成され、ＣＰＵ１１０は、ソフトウェアにより実行されるＳ／Ｗパケット転送手段１１１、ルーティング検索エンジン制御手段１１２を備え、ＲＡＭ１２０上にＳ／Ｗ経路テーブル１２１を備える。また、ＡＳＩＣ１３０は、ルーティング検索エンジンと、２系統のＭＡＣ１３５，１３５を備え、ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２、Ｈ／Ｗ経路テーブル１３３を備える。
【００４７】
そして、このルータ装置は、図２のルータ装置の構成に加えて、ＣＰＵ１１０上にソフトウェアで動作するＳ／Ｗ使用頻度カウンタ１１５を備えるともに、ＡＳＩＣ１３０のルーティング検索エンジン１３１にＨ／Ｗ使用頻度カウンタ１３４を備えている。
【００４８】
Ｓ／Ｗ使用頻度カウンタ１１５は、Ｓ／Ｗ経路テーブル１２１が記憶する経路毎にカウンタ値を備え、ＣＰＵ１１０上のソフトウェアによるＳ／Ｗパケット転送手段１１１によって探索された経路に応じたカウンタ値を加算する。
Ｈ／Ｗ使用頻度カウンタ１３４は、Ｈ／Ｗ経路テーブル１３３が記憶する経路毎にカウンタ値を備え、ルーティング検索エンジン１３１のＨ／Ｗパケット転送機能１３２によって探索された経路に応じたカウンタ値を加算する。
【００４９】
Ｓ／Ｗ使用頻度カウンタ１１５及びＨ／Ｗ使用頻度カウンタ１３４を備えたルータ装置による新規経路登録動作について、図８のフローチャートを参照しながら説明する。
先ず、ネットワークアプリケーション１１３が新規経路を登録することをＡＰＩ１１４に通知する（ステップ１１０）。
ＡＰＩ１１４は、ネットワークアプリケーション１１３からの指示により、指示された経路をＳ／Ｗ経路テーブル１２１に登録するとともに、指示された経路をルーティング検索エンジン制御手段１１２に通知する（ステップ２１１）。
【００５０】
ルーティング検索エンジン制御手段１１２は、指示された経路を含めた経路総数がＨ／Ｗ経路テーブル１３３の記憶容量を越えるかを判定し（ステップ２１２）、超えていなければ、指示された経路をＨ／Ｗ経路テーブル１３３に登録する（ステップ２１３）。ここまでの処理は、図２のルータ装置のルーティング検索エンジン制御手段１１２と同様である。
【００５１】
そして、経路総数がＨ／Ｗ経路テーブル１３３の記憶容量を越えている場合、Ｓ／Ｗ経路テーブル１２１に記憶されたすべての経路を宛先ネットワークアドレスが重複するグループに分類し（ステップ２１５）、各グループの宛先プリフィクスが最短の経路に対して、Ｓ／Ｗ使用頻度カウンタ１１５とＨ／Ｗ使用頻度カウンタ１３４から求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路をＨ／Ｗ経路テーブル１３３から削除し（ステップ２１６）、指示された経路をＨ／Ｗ経路テーブル１３３に登録する（ステップ２１３）。
【００５２】
図７のルータ装置におけるルーティング検索エンジン制御の動作について、図９及び図１０を参照しながら説明する。図９及び図１０は、ルータ装置において、Ｓ／Ｗ経路テーブル１２１の記憶容量が無制限であり、Ｈ／Ｗ経路テーブル１３３の記憶容量が６経路である例について説明する。
図９（ケース１）は、経路総数≦Ｈ／Ｗ経路テーブルの記憶容量の関係にある場合を示している。この場合、Ｓ／Ｗ経路テーブル１２１とＨ／Ｗ経路テーブル１３３はいずれも経路数が６であり、同一である。
【００５３】
図１０（ケース２）は、前記状態において、ネットワークアプリケーションがＡＰＩを使用して新たに経路を追加することで、経路総数＞Ｈ／Ｗ経路テーブルの記憶容量の関係となる場合を示している。この場合、ルーティング検索エンジン制御手段１１２により、Ｓ／Ｗ経路テーブル１２１の全ての経路を、宛先ネットワークアドレスが重複するグループに分類する。図１０のケース２の場合、グループＡとグループＢの二つのグループに分類している。そして、各グループの宛先プリフィクス最短の経路の使用頻度を、Ｓ／Ｗ使用頻度カウンタ１１５とＨ／Ｗ使用頻度カウンタ１３４の値を合算することで求め、使用頻度が最低の経路である経路２−１に相当する経路をＨ／Ｗ経路テーブル１３３から削除し、新規経路をＨ／Ｗ経路テーブル１３３に登録する。
【００５４】
以下に、図１０のケース２において、パケット転送がルーティング検索エンジン１３１内で完結する事例と、ＣＰＵ１１０上のソフトウェアで処理される事例について、受信パケットの経路検索動作を説明する。
【００５５】
（パケット転送がルーティング検索エンジン３１で完結する事例）
ルータ装置がＳ／Ｗ経路テーブル１２１に登録された経路２−２に一致するパケットを受信した場合の動作を説明する。
パケット入出力部は、受信パケットをルーティング検索エンジン１３１に転送する。ルーティング検索エンジン１３１は、Ｈ／Ｗパケット転送機能１３２において、受信パケットの宛先ＩＰアドレスに一致する経路を、最長一致探索によってＨ／Ｗ経路テーブル１３３から探索する。図１０の場合、宛先プリフィクスの高い経路から順に探索されるので、最初に一致した経路が宛先プリフィクスの高い経路となるのでこれを選択する。すなわち、経路Ｆ，Ｅ，Ｄ，Ｃの順に探索され、経路Ｃ（＝経路２−２）を選択し、パケット転送が完結する。
仮に、この状態でＳ／Ｗパケット転送手段１１１においてＳ／Ｗ経路テーブル１２１から探索した場合、経路２−２，１−４，１−３，２−２の順に探索され、経路２−２を選択する。
以上のように、受信パケットに該当する経路がルーティング検索エンジンに在る場合は、ルーティング検索エンジンでパケット転送が完結され、且つ、ルータ全体として経路探索結果の一貫性が維持されている。
【００５６】
（パケット転送がＣＰＵ１１０上のソフトウェアで処理される事例）
ルータ装置がＳ／Ｗ経路テーブル１２１に登録された経路２−１に一致するパケットを受信した場合の動作を説明する。
パケット入出力部は、受信パケットをルーティング検索エンジンに転送する。ルーティング検索エンジンは、Ｈ／Ｗパケット転送機能において、受信パケットの宛先ＩＰアドレスに一致する経路を、最長一致探索によってＨ／Ｗ経路テーブル１３３から探索する。図１０の場合、宛先プリフィクスの高い経路から順に探索されるので、最初に一致した経路が宛先プリフィクスの高い経路となるのでこれを選択する。すなわち、経路Ｆ，Ｅ，Ｄ，Ｃ，Ｂ，Ａの順に探索されるが、いずれにも一致しないため、ＣＰＵに受信パケットを転送する。ＣＰＵ１１０上のソフトウェアは、Ｓ／Ｗパケット転送手段１１１において最長一致探索によってＳ／Ｗ経路テーブル１２１から探索する。図１０の場合、宛先プリフィクスの高い経路から順に探索されるので、最初に一致した経路が宛先プリフィクスの高い経路となるのでこれを選択する。すなわち、経路２−３，１−４，１−３，２−２，１−２，２−１の順に探索され、経路２−１を選択する。
以上のように、受信パケットに該当する経路がルーティング検索エンジン１３１に無い場合でも、ＣＰＵ１１０上のソフトウェアでパケット転送され、且つ、ルータ全体として経路探索結果の一貫性が維持されている。
【００５７】
次に、図７のルータ装置におけるルーティング検索エンジンの経路検索についての制御動作をより明確にするために、図１１と図１２を用いて説明する。
図１１は、ルータ装置が具備するＳ／Ｗ経路テーブル１２１を示しており、ネットワークアプリケーションによって、経路ア、イ、ウ、エの４つの経路が登録されており、経路毎にＳ／Ｗ使用頻度カウンタとＨ／Ｗ使用頻度カウンタの値を合算し、カウンタ合算値を所定のしきい値で２分割して使用頻度を高・低に２値化して管理している。また、カウンタの合算値をそのまま使用頻度としてもよいし、高・低の２値ではなく、例えば４つの使用頻度に分割してもよい。
【００５８】
図１２は、すべてのＩＰアドレスを、デフォルトゲートウェイを根とし、ネットワークアドレスの先頭ビットから順に２値で枝分かれする二分木のうち、先頭４ビットまでを示した図である。
【００５９】
ルーティング検索エンジン制御機能は、経路総数＞Ｈ／Ｗ経路テーブルの記憶容量の関係を満たした場合、Ｓ／Ｗ経路テーブルのすべての経路を、宛先ネットワークアドレスが重複するグループに分類する。ここで、宛先ネットワークアドレスが重複するグループとは、図１２の登録済の経路（白塗りの丸）を根とする枝木に含まれる経路を意味する。すなわち、経路アを根とする枝木をグループＡとすると、経路イがこの枝木に含まれるため、グループＡに含まれる経路は経路ア、イとなる。また、経路ウを根とする枝木をグループＢとすると、経路エがこの枝木に含まれるため、グループＢに含まれる経路は経路ウ、エとなる。
グループＡとグループＢは、宛先ネットワークアドレスの先頭ビットが互いに重複しないことは、図１２から明らかである。従って、受信パケットの宛先ネットワークアドレスがあるグループの経路に一致する場合、別のグループの経路には一致しない。つまり、「最長一致探索において、異なるグループの経路に一致することは起こりえない」という特徴を持つ。
上記の特徴により、分類したグループのうち、いずれのグループの宛先プリフィクス最短の経路を削除しても、ルータ装置全体での経路探索結果の一貫性は維持される。
【００６０】
上述の構造によれば、各経路の使用頻度について、削除経路を選択する条件に加えることにより、経路の使用頻度を管理することで図２の例に比較して、更に高いパケット転送能力を維持することができる。
【００６１】
上述した各ルータ装置によれば、高スループットを維持可能な構成を低コストで作製することが可能となる。
【図面の簡単な説明】
【００６２】
【図１】本発明のルータ装置が適用されるＩＰボタン電話装置のブロック図である。
【図２】本発明のルータ装置の実施形態の一例を示すブロック図である。
【図３】本発明のルータ装置におけるパケット転送の動作を説明するためのフローチャート図である。
【図４】図２のルータ装置における新規経路登録の動作を説明するためのフローチャート図である。
【図５】図２のルータ装置におけるルーティング検索エンジン制御の動作を示す図である。
【図６】図２のルータ装置におけるルーティング検索エンジン制御の動作を示す図である。
【図７】本発明のルータ装置の実施形態の他の例を示すブロック図である。
【図８】図７のルータ装置における新規経路登録の動作を説明するためのフローチャート図である。
【図９】図７のルータ装置におけるルーティング検索エンジン制御の動作を示す図である。
【図１０】図７のルータ装置におけるルーティング検索エンジン制御の動作を示す図である。
【図１１】Ｓ／Ｗ経路テーブルに登録された宛先ＩＰアドレスを説明するための図である。
【図１２】Ｓ／Ｗ経路テーブルに登録された宛先ＩＰアドレスの属性を二分木で表現した図である。
【符号の説明】
【００６３】
１…ＣＣＵ、 ３…ＣＥＵ、 ６…ＩＰ内線ＬＡＮ、 １４，３４…専用チップ、 １００…ＩＰボタン電話装置、 １０１…ローカルバス、 １１０…ＣＰＵ、 １１１…Ｓ／Ｗパケット転送手段、 １１２…ルーティング検索エンジン制御手段、 １１３…ネットワークアプリケーション（経路登録手段）、 １１５…Ｓ／Ｗ使用頻度カウンタ、１２０…ＲＡＭ、 １２１…Ｓ／Ｗ経路テーブル、 １３０…ＡＳＩＣ、 １３１…ルーティング検索エンジン、 １３２…Ｈ／Ｗパケット転送機能、 １３３…Ｈ／Ｗ経路テーブル、 １３４…Ｈ／Ｗ使用頻度カウンタ、 １３５…ＭＡＣ、 １４０…ＰＨＹ。
【特許請求の範囲】
【請求項１】
ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンと、該ルーティング検索エンジンに接続しパケットの送受信を行う複数のネットワークデバイスとを有する装置であって、
前記ルーティング検索エンジンは、ハードウェアによるＨ／Ｗパケット転送機能と、ハードウェアによるＨ／Ｗ経路探索を行う経路テーブルとを備え、前記ネットワークデバイスを介して転送された受信パケットの宛先ＩＰアドレスに一致する経路を前記Ｈ／Ｗ経路テーブルから探索し、前記受信パケットの当該経路が示すネットワークデバイスへの転送、又は、前記ＣＰＵへの転送を行う一方、
前記ＣＰＵは、ソフトウェアによるＳ／Ｗパケット転送手段と、ソフトウェアによるＳ／Ｗ経路テーブルから経路を探索する経路探索手段と、ルーティング検索エンジンの制御を行うルーティング検索エンジン制御手段と、前記Ｓ／Ｗ経路テーブルに対して経路を登録する経路登録手段とを含み、前記ルーティング検索エンジンから転送された受信パケットに対し、宛先ＩＰアドレスに一致する経路を前記Ｓ／Ｗ経路テーブルから探索し、前記受信パケットの当該経路が示すネットワークデバイスへの転送、又は、前記受信パケットの廃棄を行うとともに、
前記ルーティング検索エンジン制御手段は、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路のうち、前記宛先ＩＰアドレスの宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブルから削除し、指示された経路をＨ／Ｗ経路テーブルに登録する経路登録機能を備えて成る
ことを特徴とするルータ装置。
【請求項２】
前記ルーティング検索エンジンは、前記Ｈ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｈ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＨ／Ｗ使用頻度カウンタを有し、
前記ＣＰＵは、前記Ｓ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｓ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＳ／Ｗ使用頻度カウンタを有し、
前記ルーティング検索エンジン制御手段は、前記経路登録機能に代えて、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路を宛先ネットワークアドレスの一部が重複する複数グループに分類し、各グループの宛先プリフィクスが最短の経路に対して、前記Ｓ／Ｗ使用頻度カウンタと前記Ｈ／Ｗ使用頻度ウンタから求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路を前記Ｈ／Ｗ経路テーブルから削除し、指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録機能を備えて成る
請求項１に記載のルータ装置。
【請求項３】
ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンを備え、一方のネットワークデバイスから受信したパケットを他方のネットワークデバイスへ送信する際の経路検索の制御を行うルーティング検索制御方法であって、
前記ルーティング検索エンジンにより、前記ネットワークデバイスを介して転送された受信パケットの宛先ＩＰアドレスに一致する経路をハードウェアによるＨ／Ｗ経路テーブルから探索し、一致する経路が見つかれば前記受信パケットを当該経路が示すネットワークデバイスに転送し、一致する経路が見つからない時には前記受信パケットを前記ＣＰＵに転送する第１の転送手順と、
前記ＣＰＵにより、前記ルーティング検索エンジンから転送された受信パケットに対し、宛先ＩＰアドレスに一致する経路をソフトウェアによるＳ／Ｗ経路テーブルから探索し、一致する経路が見つかれば前記受信パケットを当該経路が示すネットワークデバイスに転送し、一致する経路が見つからない時には前記受信パケットを廃棄する第２の転送手順と、
前記ＣＰＵにより、前記Ｓ／Ｗ経路テーブルで指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路を前記Ｈ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路のうち、前記宛先ＩＰアドレスの宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブルから削除し、指示された経路をＨ／Ｗ経路テーブルに登録する経路登録手順を具備する
ことを特徴とするルーティング検索制御方法。
【請求項４】
前記ルーティング検索エンジンは、前記Ｈ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｈ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＨ／Ｗ使用頻度カウンタを有し、
前記ＣＰＵは、前記Ｓ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｓ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＳ／Ｗ使用頻度カウンタを有する一方、
前記ＣＰＵは、前記経路登録手順に代えて、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路を宛先ネットワークアドレスの一部が重複する複数グループに分類し、各グループの宛先プリフィクスが最短の経路に対して、前記Ｓ／Ｗ使用頻度カウンタと前記Ｈ／Ｗ使用頻度ウンタから求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路を前記Ｈ／Ｗ経路テーブルから削除し、指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録手順を具備する
請求項３に記載のルーティング検索制御方法。
【請求項１】
ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンと、該ルーティング検索エンジンに接続しパケットの送受信を行う複数のネットワークデバイスとを有する装置であって、
前記ルーティング検索エンジンは、ハードウェアによるＨ／Ｗパケット転送機能と、ハードウェアによるＨ／Ｗ経路探索を行う経路テーブルとを備え、前記ネットワークデバイスを介して転送された受信パケットの宛先ＩＰアドレスに一致する経路を前記Ｈ／Ｗ経路テーブルから探索し、前記受信パケットの当該経路が示すネットワークデバイスへの転送、又は、前記ＣＰＵへの転送を行う一方、
前記ＣＰＵは、ソフトウェアによるＳ／Ｗパケット転送手段と、ソフトウェアによるＳ／Ｗ経路テーブルから経路を探索する経路探索手段と、ルーティング検索エンジンの制御を行うルーティング検索エンジン制御手段と、前記Ｓ／Ｗ経路テーブルに対して経路を登録する経路登録手段とを含み、前記ルーティング検索エンジンから転送された受信パケットに対し、宛先ＩＰアドレスに一致する経路を前記Ｓ／Ｗ経路テーブルから探索し、前記受信パケットの当該経路が示すネットワークデバイスへの転送、又は、前記受信パケットの廃棄を行うとともに、
前記ルーティング検索エンジン制御手段は、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路のうち、前記宛先ＩＰアドレスの宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブルから削除し、指示された経路をＨ／Ｗ経路テーブルに登録する経路登録機能を備えて成る
ことを特徴とするルータ装置。
【請求項２】
前記ルーティング検索エンジンは、前記Ｈ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｈ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＨ／Ｗ使用頻度カウンタを有し、
前記ＣＰＵは、前記Ｓ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｓ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＳ／Ｗ使用頻度カウンタを有し、
前記ルーティング検索エンジン制御手段は、前記経路登録機能に代えて、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路を宛先ネットワークアドレスの一部が重複する複数グループに分類し、各グループの宛先プリフィクスが最短の経路に対して、前記Ｓ／Ｗ使用頻度カウンタと前記Ｈ／Ｗ使用頻度ウンタから求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路を前記Ｈ／Ｗ経路テーブルから削除し、指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録機能を備えて成る
請求項１に記載のルータ装置。
【請求項３】
ＣＰＵと、ハードウェア資質で構成されたルーティング検索エンジンを備え、一方のネットワークデバイスから受信したパケットを他方のネットワークデバイスへ送信する際の経路検索の制御を行うルーティング検索制御方法であって、
前記ルーティング検索エンジンにより、前記ネットワークデバイスを介して転送された受信パケットの宛先ＩＰアドレスに一致する経路をハードウェアによるＨ／Ｗ経路テーブルから探索し、一致する経路が見つかれば前記受信パケットを当該経路が示すネットワークデバイスに転送し、一致する経路が見つからない時には前記受信パケットを前記ＣＰＵに転送する第１の転送手順と、
前記ＣＰＵにより、前記ルーティング検索エンジンから転送された受信パケットに対し、宛先ＩＰアドレスに一致する経路をソフトウェアによるＳ／Ｗ経路テーブルから探索し、一致する経路が見つかれば前記受信パケットを当該経路が示すネットワークデバイスに転送し、一致する経路が見つからない時には前記受信パケットを廃棄する第２の転送手順と、
前記ＣＰＵにより、前記Ｓ／Ｗ経路テーブルで指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路を前記Ｈ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路のうち、前記宛先ＩＰアドレスの宛先プリフィクスが最短の経路をＨ／Ｗ経路テーブルから削除し、指示された経路をＨ／Ｗ経路テーブルに登録する経路登録手順を具備する
ことを特徴とするルーティング検索制御方法。
【請求項４】
前記ルーティング検索エンジンは、前記Ｈ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｈ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＨ／Ｗ使用頻度カウンタを有し、
前記ＣＰＵは、前記Ｓ／Ｗ経路テーブルが記憶する経路毎にカウンタ値を備え、前記Ｓ／Ｗパケット転送機能によって探索された経路に応じたカウンタ値を加算するＳ／Ｗ使用頻度カウンタを有する一方、
前記ＣＰＵは、前記経路登録手順に代えて、指示された経路を含めた経路総数がＨ／Ｗ経路テーブルの記憶容量を越えるかを判定し、超えていなければ、指示された経路をＨ／Ｗ経路テーブルに登録し、超えていれば、Ｓ／Ｗ経路テーブルに記憶されたすべての経路を宛先ネットワークアドレスの一部が重複する複数グループに分類し、各グループの宛先プリフィクスが最短の経路に対して、前記Ｓ／Ｗ使用頻度カウンタと前記Ｈ／Ｗ使用頻度ウンタから求めたカウンタ値を合算して使用頻度を求め、使用頻度が最低の経路を前記Ｈ／Ｗ経路テーブルから削除し、指示された経路を前記Ｈ／Ｗ経路テーブルに登録する使用頻度経路登録手順を具備する
請求項３に記載のルーティング検索制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−１０９７３５（Ｐ２０１０−１０９７３５Ａ）
【公開日】平成２２年５月１３日（２０１０．５．１３）
【国際特許分類】
【出願番号】特願２００８−２８０１２５（Ｐ２００８−２８０１２５）
【出願日】平成２０年１０月３０日（２００８．１０．３０）
【出願人】（００００００１８１）岩崎通信機株式会社 (133)
【出願人】（３９９０４０４０５）東日本電信電話株式会社 (286)
【出願人】（３９９０４１１５８）西日本電信電話株式会社 (215)
【Ｆターム（参考）】
【公開日】平成２２年５月１３日（２０１０．５．１３）
【国際特許分類】
【出願日】平成２０年１０月３０日（２００８．１０．３０）
【出願人】（００００００１８１）岩崎通信機株式会社 (133)
【出願人】（３９９０４０４０５）東日本電信電話株式会社 (286)
【出願人】（３９９０４１１５８）西日本電信電話株式会社 (215)
【Ｆターム（参考）】
[ Back to top ]