(57)【要約】【課題】  マルチキャストＭＰＬＳノードのテーブルの検索時間を軽減する。【解決手段】  本発明は、入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、を有し、当該テーブルを用いて、新規登録、追加登録、削除、検索を行う。【選択図】  図１
2005252815.tif 000002
【特許請求の範囲】
【請求項１】
入力ラベルを複数の出力ラベルに交換することによりＭＰＬＳパケットをポイントツーマルチポイントでラベル転送可能な、マルチキャストＭＰＬＳノードのテーブルであって、
入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、
前記入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、
前記入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、を有することを特徴とするマルチキャストＭＰＬＳノードのテーブル。
【請求項２】
入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、
前記入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、
前記入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、からなるマルチキャストＭＰＬＳノードのテーブルの制御方法において、
入力ラベルに対して複数の出力ラベルの初期登録を行う場合には、
前記入力用ＣＡＭキューにおいて、前記入力用ＣＡＭテーブルの登録する出力ラベル分の空き行アドレス情報を検索し、
前記入力用ＣＡＭテーブルにおいて、検索された出力ラベル分の空き行アドレスの、入力ラベル格納メモリに、それぞれ出力ラベル分、入力ラベルを登録し、
前記出力テーブルにおいて、出力ラベル分、前記入力ラベルが登録された行アドレス情報を検索し、
前記出力テーブルにおいて、検索された出力ラベル分の行アドレス情報を格納する出力ラベル格納メモリに、それぞれ出力ラベル分、出力ラベルを登録する初期登録処理と、
入力ラベルに対して複数の出力ラベルの追加登録が必要な場合には、
前記入力用ＣＡＭキューにおいて、前記入力用ＣＡＭテーブルの登録する出力ラベル分の空き行アドレス情報を検索し、
前記入力用ＣＡＭテーブルにおいて、検索された出力ラベル分の空き行アドレスの、入力ラベル格納メモリに、それぞれ出力ラベル分、入力ラベルを登録し、
前記出力用テーブルにおいて、出力ラベル分、前記入力ラベルが登録された行アドレス情報を検索し、
前記出力用テーブルにおいて、検索された出力ラベル分の行アドレス情報を格納する出力ラベル格納メモリに、それぞれ出力ラベル分、出力ラベルを登録する追加登録処理と、
ポイントツーマルチポイントのラベルをテーブルから削除する場合には、
削除するラベルの入力ラベルを特定し、
前記入力用ＣＡＭテーブルにおいて、削除する入力ラベルを完全一致検索し、
前記入力用ＣＡＭテーブルにおいて、ポイントツーポイントのラベル情報は、前記入力ラベルに対して複数の出力ラベルが関連付けられているため、該入力ラベルが格納された出力ラベル分のＣＡＭ行アドレス情報を抽出し、
前記出力用テーブルにおいて、抽出した出力ラベル分のＣＡＭアドレス情報を検索し、
前記出力用テーブルにおいて、検索した前記出力ラベル分の行アドレス情報を格納する出力ラベル格納メモリに登録された出力ラベルを抽出し、
前記出力用テーブルにおいて、抽出された出力ラベル分の出力ラベルのうち、削除すべき出力ラベルを特定し、
前記出力用テーブルにおいて、削除すべき出力ラベルを前記出力ラベル格納メモリから削除し、
前記出力用テーブルにおいて、削除した前記出力ラベルを格納する行アドレス情報を抽出し、
前記入力用ＣＡＭテーブルにおいて、削除した行アドレス情報を格納するＣＡＭ行アドレス情報を検索し、
前記入力用ＣＡＭテーブルにおいて、検索した前記ＣＡＭ行アドレス情報を格納する入力ＣＡＭメモリに登録された入力ラベルを削除し、
前記入力用ＣＡＭキューにおいて、削除した入力ラベルを格納した行アドレス情報を入力ＣＡＭキューに登録する削除処理と、を行うことを特徴とするマルチキャストＭＰＬＳノードのテーブルの制御方法。
【請求項３】
入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、
前記入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、
前記入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、からなるマルチキャストＭＰＬＳノードのテーブルの制御方法において、
入力ラベルに対して複数の出力ラベルをラベル交換する場合に、
検索するラベルの入力ラベルを特定し、
前記入力用ＣＡＭテーブルにおいて、検索するラベルの入力ラベルを完全一致検索し、
前記入力用ＣＡＭテーブルにおいて、入力ラベルが格納された出力ラベル分のＣＡＭ行アドレス情報を抽出し、
前記出力用テーブルにおいて、抽出した前記出力ラベル分のＣＡＭ行アドレス情報を検索し、
前記出力用テーブルにおいて、検索した出力ラベル分のＣＡＭ行アドレス情報を格納する出力ラベル格納メモリに登録された出力ラベルを抽出する処理を行うことを特徴とするマルチキャストＭＰＬＳノードのテーブルの制御方法。
【請求項４】
入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、
前記入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、
前記入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、からなるマルチキャストＭＰＬＳノードのテーブルにおけるマルチキャストＭＰＬＳノードのテーブルの制御方法において、
１つの入力ラベルに対して単一の出力ラベルを持つポイントツーマルチポイントのラベル登録する場合に、
前記入力用ＣＡＭキューにおいて、前記入力用ＣＡＭテーブルの空き行アドレス情報を検索し、
前記入力用ＣＡＭキューにおいて、前記入力用ＣＡＭテーブルの登録すべき空きエントリを決定し
前記入力用ＣＡＭテーブルにおいて、決定された空き行アドレスの入力ラベル格納メモリに入力ラベルを登録し、
前記出力用テーブルにおいて、前記入力ラベルが登録された行アドレス情報を検索し、
前記出力用テーブルにおいて、検索された前記行アドレス情報を格納する出力ラベル格納メモリに出力ラベルを登録する、初期登録処理を行い、
１つの入力ラベルに対して単一の出力ラベルを持つポイントツーマルチポイントのラベルをテーブルへ追加登録する場合には、
前記入力用ＣＡＭキューにおいて、入力用ＣＡＭテーブルの空き行アドレス情報を検索し、
前記入力用ＣＡＭキューにおいて、入力用ＣＡＭテーブルの登録すべき空きエントリを決定し、
前記入力用ＣＡＭテーブルにおいて、決定された空き行アドレスの入力ラベル格納メモリに入力ラベルを登録し、
前記出力用テーブルにおいて、前記入力ラベルが登録された行アドレス情報を検索し、
前記出力用テーブルにおいて、検索された前記行アドレス情報を格納する出力ラベル格納メモリに出力ラベルを登録する、追加登録処理を行い、
前記ポイントツーポイントのラベルをテーブルから削除する場合には、
削除するラベルの入力ラベルを特定し、
前記入力用ＣＡＭテーブルにおいて、削除するラベルの入力ラベルを完全一致検索し、
前記入力用ＣＡＭテーブルにおいて、入力ラベルが格納されたＣＡＭ行アドレス情報を抽出し、
前記出力用テーブルにおいて、抽出した前記ＣＡＭ行アドレス情報を検索し、
前記出力用テーブルにおいて、検索した行アドレス情報を格納する出力ラベル格納メモリに登録された出力ラベルを削除し、
前記出力テーブルにおいて、削除した前記出力ラベルを格納する行アドレス情報を抽出し、
前記入力用ＣＡＭテーブルにおいて、削除した行アドレス情報を格納するＣＡＭ行アドレス情報を検索し、
前記入力用ＣＡＭテーブルにおいて、検索した前記行アドレス情報を格納する入力ＣＡＭメモリに登録された入力ラベルを削除し、
前記入力用ＣＡＭキューにおいて、削除した前記入力ラベルを格納した行アドレス情報を該入力用ＣＡＭキューに登録する、削除処理を行う、ことを特徴とするマルチキャストＭＰＬＳノードのテーブルの制御方法。
【請求項５】
入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、
前記入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、
前記入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、からなるマルチキャストＭＰＬＳノードのテーブルにおけるマルチキャストＭＰＬＳノードのテーブルの制御方法において、
入力ラベルに対して１つの出力ラベルをラベル交換する必要のある場合に、
検索するラベルの入力ラベルを特定し、
前記入力用ＣＡＭテーブルにおいて、検索するラベルの入力ラベルを完全一致検索し、
前記入力用ＣＡＭテーブルにおいて、前記入力ラベルが格納された１つのＣＡＭ行アドレス情報を抽出し、
前記出力用テーブルにおいて、抽出した前記ＣＡＭ行アドレス情報を検索し、
前記出力用テーブルにおいて、検索した前記ＣＡＭ行アドレス情報を格納する出力ラベル格納メモリに登録された出力ラベルを抽出することを特徴とするマルチキャストＭＰＬＳノードのテーブルの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャストＭＰＬＳノードテーブル及びマルチキャストＭＰＬＳノードテーブル制御方法に係り、特に、マルチキャストＭＰＬＳノード技術において、ＣＡＭ(Content Addressable Memory)を用いたマルチキャストＭＰＬＳノードのテーブル構成・テーブルへの初期登録・追加登録・削除処理を行うためのマルチキャストＭＰＬＳノードテーブル及びマルチキャストＭＰＬＳノードテーブル制御方法に関する。
【背景技術】
【０００２】
従来のＭＰＬＳノードの場合、１つの入力ラベルに対して単一の出力ラベルを持つポイントツーポイントのラベルを処理する機能しか持たない。そのため、１つの入力ラベルに対して１つの出力ラベルを登録するエントリ機能しか持たない（例えば、非特許文献１参照）。ここで、１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベルを処理するためには、１つの入力ラベルに対して１つの出力ラベルを登録するエントリを出力ラベルの数だけ用意し、入力ラベルは同一のラベル識別子として登録する必要がある。その時、同一の入力ラベルを持つ出力ラベルをテーブルから決定するために、全エントリを検索する必要があるため、検索時間の効率が悪い。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
上記の従来の方式を使用した場合、同一の入力ラベルを持つ出力ラベルをテーブルから決定するために、全エントリを検索する必要があるため、検索時間の効率が悪いという問題がある。
【０００４】
本発明は、上記の点に鑑みなされたもので、検索時間を軽減することが可能な、マルチキャストＭＰＬＳノードのテーブル及び、マルチキャストＭＰＬＳノードのテーブルの制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
図１は、本発明の原理を説明するための図である。
【０００６】
本発明は、入力ラベルを複数の出力ラベルに交換することによりＭＰＬＳパケットをポイントツーマルチポイントでラベル転送可能な、マルチキャストＭＰＬＳノードのテーブルであって、
入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブル１００と、
入力用ＣＡＭテーブル１００の空き行アドレス情報を格納する入力用ＣＡＭキュー１１０と、
入力用ＣＡＭテーブル１００の行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブル２００と、を有する。
【０００７】
本発明は、入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、からなるマルチキャストＭＰＬＳノードのテーブルの制御方法において、
入力ラベルに対して複数の出力ラベルの初期登録を行う場合には、
入力用ＣＡＭキューにおいて、入力用ＣＡＭテーブルの登録する出力ラベル分の空き行アドレス情報を検索し、
入力用ＣＡＭテーブルにおいて、検索された出力ラベル分の空き行アドレスの、入力ラベル格納メモリに、それぞれ出力ラベル分、入力ラベルを登録し、
出力テーブルにおいて、出力ラベル分、入力ラベルが登録された行アドレス情報を検索し、
出力テーブルにおいて、検索された出力ラベル分の行アドレス情報を格納する出力ラベル格納メモリに、それぞれ出力ラベル分、出力ラベルを登録する、初期登録処理と、
入力ラベルに対して複数の出力ラベルの追加登録が必要な場合には、
入力用ＣＡＭキューにおいて、入力用ＣＡＭテーブルの登録する出力ラベル分の空き行アドレス情報を検索し、
入力用ＣＡＭテーブルにおいて、検索された出力ラベル分の空き行アドレスの、入力ラベル格納メモリに、それぞれ出力ラベル分、入力ラベルを登録し、
出力用テーブルにおいて、出力ラベル分、入力ラベルが登録された行アドレス情報を検索し、
出力用テーブルにおいて、検索された出力ラベル分の行アドレス情報を格納する出力ラベル格納メモリに、それぞれ出力ラベル分、出力ラベルを登録する、追加登録処理と、
ポイントツーマルチポイントのラベルをテーブルから削除する場合には、
削除するラベルの入力ラベルを特定し、
入力用ＣＡＭテーブルにおいて、削除する入力ラベルを完全一致検索し、
入力用ＣＡＭテーブルにおいて、ポイントツーポイントのラベル情報は、入力ラベルに対して複数の出力ラベルが関連付けられているため、該入力ラベルが格納された出力ラベル分のＣＡＭ行アドレス情報を抽出し、
出力用テーブルにおいて、抽出した出力ラベル分のＣＡＭアドレス情報を検索し、
出力用テーブルにおいて、検索した出力ラベル分の行アドレス情報を格納する出力ラベル格納メモリに登録された出力ラベルを抽出し、
出力用テーブルにおいて、抽出された出力ラベル分の出力ラベルのうち、削除すべき出力ラベルを特定し、
出力用テーブルにおいて、削除すべき出力ラベルを出力ラベル格納メモリから削除し、
出力用テーブルにおいて、削除した出力ラベルを格納する行アドレス情報を抽出し、
入力用ＣＡＭテーブルにおいて、削除した行アドレス情報を格納するＣＡＭ行アドレス情報を検索し、
入力用ＣＡＭテーブルにおいて、検索した行アドレス情報を格納する入力ＣＡＭメモリに登録された入力ラベルを削除し、
入力用ＣＡＭキューにおいて、削除した入力ラベルを格納した行アドレス情報を入力ＣＡＭキューに登録する、削除処理と、を行う。
【０００８】
本発明は、入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、からなるマルチキャストＭＰＬＳノードのテーブルの制御方法において、
入力ラベルに対して複数の出力ラベルをラベル交換する場合に、
検索するラベルの入力ラベルを特定し、
入力用ＣＡＭテーブルにおいて、検索するラベルの入力ラベルを完全一致検索し、
入力用ＣＡＭテーブルにおいて、入力ラベルが格納された出力ラベル分のＣＡＭ行アドレス情報を抽出し、
出力用テーブルにおいて、抽出した出力ラベル分のＣＡＭ行アドレス情報を検索し、
出力用テーブルにおいて、検索した出力ラベル分の行アドレス情報を格納する出力ラベル格納メモリに登録された出力ラベルを抽出する処理を行う。
【０００９】
本発明は、入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、からなるマルチキャストＭＰＬＳノードのテーブルにおけるマルチキャストＭＰＬＳノードのテーブルの制御方法において、
１つの入力ラベルに対して単一の出力ラベルを持つポイントツーマルチポイントのラベル登録する場合に、
入力用ＣＡＭキューにおいて、入力用ＣＡＭテーブルの空き行アドレス情報を検索し、
入力用ＣＡＭキューにおいて、入力用ＣＡＭテーブルの登録すべき空きエントリを決定し
入力用ＣＡＭテーブルにおいて、決定された空き行アドレスの入力ラベル格納メモリに入力ラベルを登録し、
出力用テーブルにおいて、入力ラベルが登録された行アドレス情報を検索し、
出力用テーブルにおいて、検索された行アドレス情報を格納する出力ラベル格納メモリに出力ラベルを登録する、初期登録処理を行い、
１つの入力ラベルに対して単一の出力ラベルを持つポイントツーマルチポイントのラベルをテーブルへ追加登録する場合には、
入力用ＣＡＭキューにおいて、入力用ＣＡＭテーブルの空き行アドレス情報を検索し、
入力用ＣＡＭキューにおいて、入力用ＣＡＭテーブルの登録すべき空きエントリを決定し、
入力用ＣＡＭテーブルにおいて、決定された空き行アドレスの入力ラベル格納メモリに入力ラベルを登録し、
出力用テーブルにおいて、入力ラベルが登録された行アドレス情報を検索し、
出力用テーブルにおいて、検索された行アドレス情報を格納する出力ラベル格納メモリに出力ラベルを登録する、追加登録処理を行い、
ポイントツーポイントのラベルをテーブルから削除する場合には、
削除するラベルの入力ラベルを特定し、
入力用ＣＡＭテーブルにおいて、削除するラベルの入力ラベルを完全一致検索し、
入力用ＣＡＭテーブルにおいて、入力ラベルが格納されたＣＡＭ行アドレス情報を抽出し、
出力用テーブルにおいて、抽出したＣＡＭ行アドレス情報を検索し、
出力用テーブルにおいて、検索した行アドレス情報を格納する出力ラベル格納メモリに登録された出力ラベルを削除し、
出力テーブルにおいて、削除した出力ラベルを格納する行アドレス情報を抽出し、
入力用ＣＡＭテーブルにおいて、削除した行アドレス情報を格納するＣＡＭ行アドレス情報を検索し、
入力用ＣＡＭテーブルにおいて、検索した行アドレス情報を格納する入力ＣＡＭメモリに登録された入力ラベルを削除し、
入力用ＣＡＭキューにおいて、削除した入力ラベルを格納した行アドレス情報を該入力用ＣＡＭキューに登録する、削除処理を行う。
【００１０】
本発明は、入力ラベル情報と該入力ラベル情報に関連付けられた行アドレス情報を格納する入力用ＣＡＭテーブルと、入力用ＣＡＭテーブルの空き行アドレス情報を格納する入力用ＣＡＭキューと、入力用ＣＡＭテーブルの行アドレス情報と該行アドレス情報に関連付けられた出力ラベル情報を格納する出力用テーブルと、からなるマルチキャストＭＰＬＳノードのテーブルにおけるマルチキャストＭＰＬＳノードのテーブルの制御方法において、
入力ラベルに対して１つの出力ラベルをラベル交換する必要のある場合に、
検索するラベルの入力ラベルを特定し、
入力用ＣＡＭテーブルにおいて、検索するラベルの入力ラベルを完全一致検索し、
入力用ＣＡＭテーブルにおいて、入力ラベルが格納された１つのＣＡＭ行アドレス情報を抽出し、
出力用テーブルにおいて、抽出したＣＡＭ行アドレス情報を検索し、
出力用テーブルにおいて、検索した行アドレス情報を格納する出力ラベル格納メモリに登録された出力ラベルを抽出する。
【発明の効果】
【００１１】
本発明のＣＡＭによってマルチキャストＭＰＬＳノードのテーブル構成と初期登録／追加登録／削除処理法と検索処理を行うことにより、検索を高速化することが可能である。
【発明を実施するための最良の形態】
【００１２】
以下、図面と共に本発明の実施の形態を説明する。
【００１３】
最初に、本発明の概要を図２を用いて説明する。
【００１４】
ＣＡＭ(Content Addressable Memory)（MUSIC Semiconductors Inc., “Binary CAMs Product Briefs,” http://www.music-ic.com）１００は、ＲＡＭとは異なり、入力は検索キーであり、出力は、一致するエントリのインデックスである。インデックスは、出力ラベルに関連付けられている。ＳＤＲＡＭ２００のメモリにインデックスと対応するＭＰＬＳの出力ラベル情報が格納されており、インデックス情報から出力ラベルを検索する。また、ＣＡＭ１００には、バイナリＣＡＭ、ターナリーＣＡＭの２種類があり、バイナリＣＡＭの各セルは、０あるいは１だけを格納することができるので、ＭＰＬＳラベルのような完全一致検索型に利用可能である。
【００１５】
［第１の実施の形態］
本実施の形態では、初期登録処理について説明する。
【００１６】
図２は、本発明の第１の実施の形態における初期登録テーブル構成を示す。
【００１７】
同図に示すマルチキャストＭＰＬＳノードのテーブル構造は、入力ラベルを格納するＣＡＭ１００、ＣＡＭ１００の空き行アドレス情報が格納されたＣＡＭキュー１１０、ＣＡＭ１００の行アドレスに対する出力ラベル情報を格納するＳＤＲＡＭ２００から構成される。
【００１８】
同図に沿って、入力ラベル［５］、出力ラベル［３４］［４３］［４６］のラベルエントリ情報を、ＣＡＭ１００，ＳＤＲＡＭ２００に登録するときの初期登録処理について説明する。図２において、括弧内の数字１，２，３，４は、図３のステップ番号１０１，１０２，１０３，１０４とそれぞれ対応する。
【００１９】
図３は、本発明の第１の実施の形態における初期登録動作のフローチャートである。
【００２０】
ステップ１０１）  まず、ＣＡＭ１００の空きエントリを検索する。ここで、ＣＡＭ１００の空き行アドレス情報を格納したＣＡＭキュー１１０から登録すべきエントリを決定する。
【００２１】
ステップ１０２）  これにより、ＣＡＭ１００の行アドレス［６］［８］［９］に入力ラベル［５］を登録し、ＣＡＭキュー１１０の［６］［８］［９］を解除する。
【００２２】
ステップ１０３）  次に、ＣＡＭ１００の行アドレス［６］［８］［９］を格納するＳＤＲＡＭ２００上のメモリドレスにアクセスする。
【００２３】
ステップ１０４）  最後に、ＣＡＭ１００の行アドレスを格納するＳＤＲＡＭテーブルに出力ラベルエントリ［３４］［４３］［４６］をそれぞれ登録する。
【００２４】
以上により、初期登録を実現する。
【００２５】
［第２の実施の形態］
本実施の形態では、テーブルの追加登録（Graft）について説明する。
【００２６】
図４は、本発明の第２の実施の形態におけるテーブル構成図である。
【００２７】
同図に示すテーブル構成は、前述の第１の実施の形態と同様である。
【００２８】
図５は、本発明の第２の実施の形態における追加登録動作のフローチャートである。
【００２９】
以下では、入力ラベル［５］、出力ラベル［３４］［４３］［４６］のラベルエントリ情報をＣＡＭ１００，ＳＤＲＡＭ２００に追加登録する動作を説明する。
【００３０】
図４における括弧内の数字１，２，３，４は、それぞれ以下のステップ２０１，２０２，２０３，２０４にそれぞれ対応する。
【００３１】
ステップ２０１）  まず、ＣＡＭ１００の空きエントリを検索する。ここで、ＣＡＭ１００の空き行アドレス情報を格納したＣＡＭキュー１１０から登録すべきエントリを決定する。
【００３２】
ステップ２０２）  これにより、ＣＡＭ１００の行アドレス［６］［８］［９］に入力ラベル［５］を登録し、ＣＡＭキューの［６］［８］［９］を解除する。
【００３３】
ステップ２０３）  次に、ＣＡＭ１００の行アドレス［６］［８］［９］を格納するＳＤＲＡＭ２００上のメモリアドレスにアクセスする。
【００３４】
ステップ２０４）  最後に、ＣＡＭ１００の行アドレスを格納するＳＤＲＡＭ２００テーブルに出力ラベルエントリ［３４］［４３］［４６］をそれぞれ登録する。
【００３５】
以上で、追加登録処理(Graft登録)を実現する。
【００３６】
［第３の実施の形態］
本実施の形態では、削除処理（prune）について説明する。
【００３７】
図６は、本発明の第３の実施の形態におけるテーブル構成を示す。
【００３８】
同図に示すテーブル構成は、前述の第１の実施の形態と同様である。
【００３９】
以下では、入力ラベル［５］、出力ラベル［３４］［４３］［４６］のラベルエントリ情報をＣＡＭ１００，ＳＤＲＡＭ２００から削除する時の動作を説明する。
【００４０】
図７は、本発明の第３の実施の形態における削除動作のフローチャートである。
【００４１】
図６に示す括弧内の数字１，２，３，４，５と以下のステップ３０１，３０２，３０３，３０４，３０５はそれぞれ対応する。
【００４２】
ステップ３０１）  まず、ＣＡＭ１００の入力ラベル［５］のエントリ情報を持つ行アドレスを一致検索する。
【００４３】
ステップ３０２）  ここで、ＣＡＭ１００の行アドレス［６］［８］［９］［１０］が抽出される。
【００４４】
ステップ３０３）  次に、ＣＡＭ１００の行アドレス［６］［８］［９］［１０］を格納するＳＤＲＡＭ２００上のメモリアドレスにアクセスする。
【００４５】
ステップ３０４）  ＣＡＭ１００の行アドレスを格納するＳＤＲＡＭ２００のテーブルの出力ラベルエントリ［２３］［３４］［４３］［４６］を抽出する。ここで、［３４］［４３］［４６］を持つエントリをそれぞれ削除する。
【００４６】
ステップ３０５）  そして、ＣＡＭ１００の行アドレス［６］［８］［９］を格納するエントリを空にする。また、ここで、ＣＡＭキュー１１０に対して、削除したエントリ情報［６］［８］［９］をキューに追加する。
【００４７】
以上により削除処理（prune処理）を実現する。
【００４８】
[第４の実施の形態]
本実施の形態では、入力ラベルの出力ラベルの検索について説明する。
【００４９】
図８は、本発明の第４の実施の形態におけるテーブル構成を示す。
【００５０】
同図に示すテーブルは、第１の実施の形態と同様である。
【００５１】
以下では、入力ラベル［５］の出力ラベルを検索する処理について説明する。
【００５２】
図９は、本発明の第４の実施の形態における検索動作のフローチャートである。
【００５３】
図８における括弧内の数字１，２，３，４は、図９におけるステップ４０１，４０２，４０３，４０４にそれぞれ対応する。
【００５４】
ステップ４０１）  まず、ＣＡＭ１００の入力ラベル［５］を格納するエントリを一致検索する。
【００５５】
ステップ４０２）  一致したエントリのＣＡＭ１００の行アドレス（ここでは、行アドレス［１０］，［９］［８］［６］）を確認する。
【００５６】
ステップ４０３）  次に、ＣＡＭ１００の行アドレスを格納するＳＤＲＡＭ２００上のメモリアドレスにアクセスする。
【００５７】
ステップ４０４）  最後に、ＣＡＭ１００の行アドレスを格納するＳＤＲＡＭ２００のテーブルのエントリを検索し、出力ラベルを抽出する（ここでは、出力ラベル［２３］［３４］［４３］［１７］）。
【００５８】
以上により検索処理が実現する。
【００５９】
図２、図４、図６、図８における構成において、高密度ＣＡＭ１００は、単一のチップ中に、１８Ｍｂのメモリを格納する。また、ＭＰＬＳエントリは２０ビットであるため、720,000エントリを確保できる。ＭＰＬＳのラベルエントリはルータの規定で約100,000経路となっており、単一のＣＡＭで十分なエントリを確保できる。
【００６０】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【産業上の利用可能性】
【００６１】
本発明は、マルチキャストＭＰＬＳノード技術に適用可能である。
【図面の簡単な説明】
【００６２】
【図１】本発明の原理構成図である。
【図２】本発明の第１の実施の形態における初期登録テーブル構成図である。
【図３】本発明の第１の実施の形態における初期登録動作のフローチャートである。
【図４】本発明の第２の実施の形態におけるテーブル構成図である。
【図５】本発明の第２の実施の形態における追加登録動作のフローチャートである。
【図６】本発明の第３の実施の形態におけるテーブル構成図である。
【図７】本発明の第３の実施の形態における削除動作のフローチャートである。
【図８】本発明の第４の実施の形態におけるテーブル構成図である。
【図９】本発明の第４の実施の形態における検索動作のフローチャートである。
【符号の説明】
【００６３】
１００  入力用ＣＡＭテーブル、ＣＡＭ
１１０  入力用ＣＡＭキュー
２００  出力用テーブル、ＳＤＲＡＭ（ＭＰＬＳテーブル）
【図１】
2005252815.tif 000003
【図２】
2005252815.tif 000004
【図３】
2005252815.tif 000005
【図４】
2005252815.tif 000006
【図５】
2005252815.tif 000007
【図６】
2005252815.tif 000008
【図７】
2005252815.tif 000009
【図８】
2005252815.tif 000010
【図９】
2005252815.tif 000011