特許ウォッチ

公開番号2023075456
公報種別公開特許公報(A)
公開日2023-05-31
出願番号2021188369
出願日2021-11-19
発明の名称情報処理装置、パケット制御方法およびパケット制御プログラム
出願人富士通株式会社
代理人弁理士法人扶桑国際特許事務所
主分類H04L 45/748 20220101AFI20230524BHJP(電気通信技術)
要約【課題】パケットルーティングの性能を向上させる。
【解決手段】メモリ11a,11b,11cは、プレフィクス長を用いて規定される宛先アドレス範囲をそれぞれ含む複数のルーティング情報を分散して記憶する。検索部12a,12bは、複数のプレフィクス長とメモリ11a,11b,11cとの対応を示す対応情報15に基づいて、アクセス先のメモリを指定して、パケットの宛先アドレスと割り当てられるプレフィクス長とに該当するルーティング情報をそれぞれ検索する。スイッチ13は、メモリ11a,11b,11cと検索部12a,12bとを接続し、検索部12a,12bから指定されるアクセス先に基づいて、異なるメモリに並列にアクセスする。判定部14は、検索部12a,12bを用いてパケットから検索されるルーティング情報のうち、プレフィクス長が最大のルーティング情報を判定する。
【選択図】図1
特許請求の範囲【請求項１】
プレフィクス長を用いて規定される宛先アドレス範囲をそれぞれ含む複数のルーティング情報を分散して記憶する複数のメモリと、
複数のプレフィクス長と前記複数のメモリとの対応を示す対応情報に基づいて、前記複数のメモリのうちアクセス先のメモリを指定して、パケットの宛先アドレスと割り当てられるプレフィクス長とに該当するルーティング情報をそれぞれ検索する複数の検索部と、
前記複数のメモリと前記複数の検索部とを接続し、前記複数の検索部から指定される前記アクセス先に基づいて、異なるメモリに並列にアクセスするスイッチと、
前記複数の検索部を用いて前記パケットから検索されるルーティング情報のうち、プレフィクス長が最大のルーティング情報を判定する判定部と、
を有する情報処理装置。
続きを表示（約 1,200 文字）【請求項２】
前記複数の検索部には、前記複数のルーティング情報で使用中のプレフィクス長の中から互いに異なるプレフィクス長が割り当てられる、
請求項１記載の情報処理装置。
【請求項３】
検索部の個数は、ルーティング情報に使用可能なプレフィクス長の個数より少ない、
請求項１記載の情報処理装置。
【請求項４】
前記複数の検索部は、大きいプレフィクス長から優先的にルーティング情報を検索し、
前記複数のメモリでは、前記複数のルーティング情報で使用中のプレフィクス長のうち隣接するプレフィクス長をもつルーティング情報が、異なるメモリに記憶される、
請求項１記載の情報処理装置。
【請求項５】
未使用のプレフィクス長をもつ新たなルーティング情報を追加する場合、使用中のプレフィクス長と前記複数のメモリとの対応に基づいて、前記未使用のプレフィクス長に対応付けるメモリを選択する制御部を更に有する、
請求項１記載の情報処理装置。
【請求項６】
メモリの個数は検索部の個数より多い、
請求項１記載の情報処理装置。
【請求項７】
プレフィクス長を用いて規定される宛先アドレス範囲をそれぞれ含む複数のルーティング情報を分散して記憶する複数のメモリの中から、複数のプレフィクス長と前記複数のメモリとの対応を示す対応情報に基づいて、複数の検索部それぞれに割り当てられるプレフィクス長に対応するアクセス先のメモリを特定し、
前記複数の検索部と前記複数のメモリとを接続しており前記アクセス先の指定に基づいて異なるメモリに並列にアクセスするスイッチを用いて、パケットの宛先アドレスと前記割り当てられるプレフィクス長とに該当するルーティング情報を並列に検索し、
前記複数の検索部を用いて前記パケットから検索されるルーティング情報のうち、プレフィクス長が最大のルーティング情報を判定する、
処理をコンピュータが実行するパケット制御方法。
【請求項８】
プレフィクス長を用いて規定される宛先アドレス範囲をそれぞれ含む複数のルーティング情報を分散して記憶する複数のメモリの中から、複数のプレフィクス長と前記複数のメモリとの対応を示す対応情報に基づいて、複数の検索部それぞれに割り当てられるプレフィクス長に対応するアクセス先のメモリを特定し、
前記複数の検索部と前記複数のメモリとを接続しており前記アクセス先の指定に基づいて異なるメモリに並列にアクセスするスイッチを用いて、パケットの宛先アドレスと前記割り当てられるプレフィクス長とに該当するルーティング情報を並列に検索し、
前記複数の検索部を用いて前記パケットから検索されるルーティング情報のうち、プレフィクス長が最大のルーティング情報を判定する、
処理をコンピュータに実行させるパケット制御プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は情報処理装置、パケット制御方法およびパケット制御プログラムに関する。
続きを表示（約 1,800 文字）【背景技術】
【０００２】
ルータは、ルーティングテーブルを参照してパケットの出力先を決定するルーティングを行う。ルーティングテーブルには、宛先アドレス範囲とパケット出力先とを対応付けるルーティング情報が登録される。宛先アドレス範囲は、プレフィクス長を用いて表現されることがある。宛先アドレスを示すビット列のうち、先頭からプレフィクス長に相当する部分が、ネットワークを識別するプレフィクスと解釈される。プレフィクスより後ろの部分が、そのネットワークに属するノードに割り当てられるホスト部である。
【０００３】
例えば、192.168.1.0/24は、３２ビットの宛先アドレスのうち先頭２４ビット部分がプレフィクスであることを表し、192.168.1.0～192.168.1.255の宛先アドレス範囲を表す。ルータは、ルーティングテーブルから、パケットの宛先アドレスが属する宛先アドレス範囲をもつルーティング情報を検索する。ルータは、検索されたルーティング情報が示すパケット出力先に従って当該パケットを転送する。
【０００４】
ルーティングテーブルには、包含関係にある宛先アドレス範囲をもつ複数のルーティング情報が登録されることがある。例えば、ルーティングテーブルに、192.168.1.0/24というルーティング情報と、192.168.1.128/26というルーティング情報が登録されることがある。前者は192.168.1.0～192.168.1.255という宛先アドレス範囲を示し、後者は192.168.1.128～192.168.1.191という宛先アドレス範囲を示す。よって、前者の宛先アドレス範囲は後者の宛先アドレス範囲を包含する。
【０００５】
この場合、ルータは、最長プレフィクス一致（ＬＰＭ：Longest Prefix Match）ルールに基づいてルーティング情報を選択することがある。最長プレフィクス一致ルールは、パケットの宛先アドレスに該当するルーティング情報が複数ある場合、その中からプレフィクス長が最大のルーティング情報を選択するルールである。
【０００６】
なお、複数のパケット種別に対応する複数のアドレステーブルを複数のメモリに分けて格納し、受信されたパケットのパケット種別に応じたアドレステーブルにアクセスするアドレス検索システムが提案されている。また、ＩＰ（Internet Protocol）アドレスの最長一致検索を行う検索部を複数個有するアドレス検索装置が提案されている。また、異なるプレフィックス長の宛先アドレスを異なるＣＡＭ（Content Addressable Memory）に格納し、複数のＣＡＭに並列にアクセスするルータが提案されている。
【先行技術文献】
【特許文献】
【０００７】
特開２０００－１５１７０９号公報
特開２００１－６０９７０号公報
特開２００２－３３０１６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
最長プレフィクス一致ルールのもとでは、ルータは、同一のパケットからプレフィクス長の異なる複数のルーティング情報を検索することがある。よって、最長プレフィクス一致の実装方法は、パケットルーティングの性能に影響を与える。
【０００９】
全てのルーティング情報を単一のメモリに記憶すると、メモリアクセスがボトルネックとなってルーティング情報の検索が遅延し、パケットルーティングの性能が低下することがある。これに対し、前述の提案技術の１つは、３２ビットの宛先アドレスに関して３２個のメモリを用意し、プレフィクス長が異なるルーティング情報を異なるメモリに記憶し、３２通りのルーティング情報の検索を並列に実行する。しかし、ルーティング情報で使用されることがあるプレフィクス長の個数だけメモリを用意し、常に最大の並列度でルーティング情報を検索することは、ルータの回路規模を増大させる。
【００１０】
そこで、１つの側面では、本発明は、パケットルーティングの性能を向上させることを目的とする。
【課題を解決するための手段】
（【００１１】以降は省略されています）

関連特許