(57)【要約】【課題】  マルチキャストＭＰＬＳノードのテーブル構成と初期登録・追加登録・削除処理・検索処理において、テーブルのメモリ使用効率を向上させ、検索時間を軽減することを可能とする。【解決手段】  本発明は、１つの入力ラベルに対して複数の出力ラベルをもつポイントツーポイントのラベル交換において、入力ラベルを出力ラベルの格納位置情報を関連付けれる入力ラベルテーブルと、出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルを構成に、当該入力ラベルテーブルと出力ラベルテーブルを用いて、初期登録、追加登録、削除処理、検索処理を行う。【選択図】  図１
2005072905.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャストＭＰＬＳノードのコンピュータ上にＭＰＬＳテーブルを構成するマルチキャストＭＰＬＳノードのテーブル構成方法において、
入力ラベルを複数の出力ラベルに交換することによりＭＰＬＳパケットをポイントツーマルチキャストポイントでラベル転送可能な、マルチキャストＭＰＬＳノードの記憶手段上に、テーブルを構成する場合には、
前記マルチキャストＭＰＬＳノードは、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルを記憶手段上に設けることを特徴とするマルチキャストＭＰＬＳノードのテーブル構成方法。
【請求項２】
マルチキャストＭＰＬＳノードのコンピュータ上に設けられたＭＰＬＳテーブルに対して初期登録を行う、マルチキャストＭＰＬＳノードのテーブル初期登録方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルに、ポイントツーマルチポイントのラベルを初期登録する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
前記入力ラベルに対して複数の前記出力ラベルの登録が必要な場合に、
前記入力ラベルテーブルの空エントリを検索し、入力ラベルを登録する初期登録第１過程と、
前記出力ラベルテーブルの空エントリを検索し、１番目の出力ラベルを登録する初期登録第２過程と、
前記入力ラベルテーブルにおいて、前記出力ラベルの１番目に登録された格納位置情報を登録する初期登録第３過程と、
前記出力ラベルテーブルの空エントリを検索し、２番目の出力ラベルを登録し、１番目に登録された出力ラベルの格納位置情報を登録する初期登録第４過程と、
前記出力ラベルテーブルにおいて、１番目に登録された出力ラベルに対して、２番目に登録された出力ラベルの格納位置情報を登録する初期登録第５過程と、
前記出力ラベルテーブルにおいて、前記初期登録第４過程から前記初期登録第５過程を、最後の出力ラベルを登録するまで繰り返すことにより、
前記出力ラベルテーブルの空エントリを検索し、ｋ番目の出力ラベルを登録し、ｋ−１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、ｋ−１番目に登録された出力ラベルに対して、ｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルの空エントリを検索し、ｋ＋１番目の出力ラベルを登録し、ｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、ｋ番目に登録された出力ラベルに対して、ｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、最後に登録された出力ラベルに対して、最後から２番目に登録された出力ラベルの格納位置情報を登録し、最後の出力ラベルであることを示すフラグ情報を登録し、該出力ラベルテーブルにおいて、最後から２番目に登録された出力ラベルに対して、最後に登録された出力ラベルの格納位置情報を登録し、
最後に、前記入力ラベルテーブルにおいて、出力ラベルの最後に登録された格納位置情報を登録することを特徴とするマルチキャストＭＰＬＳノードのテーブル初期登録方法。
【請求項３】
マルチキャストＭＰＬＳノードのコンピュータ上に設けられたＭＰＬＳテーブルに対して追加登録を行う、マルチキャストＭＰＬＳノードのテーブル追加登録方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルに追加登録する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
前記入力ラベルテーブルの同一の入力ラベルを検索し、現時点で最後に登録された出力ラベルの格納位置情報を取得する追加登録第１過程と、
前記出力ラベルテーブルの空エントリを検索し、出力ラベルを登録する追加登録第２過程と、
前記出力ラベルテーブルにおいて、追加登録された１番目の出力ラベルに対して、現時点で最後に登録された出力ラベルの格納位置情報を登録する追加登録第３過程と、
前記出力ラベルテーブルにおいて、現時点で最後に登録された出力ラベルに対して、追加登録された１番目の出力ラベルの格納位置情報を登録し、最後の出力ラベルであることを示すフラグ情報を削除する追加登録第４の過程と、
前記出力ラベルテーブルの空エントリを検索し、追加登録された２番目の出力ラベルを登録し、追加登録された１番目に登録された出力ラベルの格納位置情報を登録する追加登録第５の過程と、
前記出力ラベルテーブルにおいて、追加登録された１番目に登録された出力ラベルに対して、追加登録された２番目に登録された出力ラベルの格納位置情報を登録する追加登録第６の過程と、
前記出力ラベルテーブルにおいて、前記追加登録第５の過程から前記追加登録第６の過程までの手順を追加登録された最後の出力ラベルを登録するまで繰り返すことにより、
前記出力ラベルテーブルの空エントリを検索し、追加登録されたｋ番目の出力ラベルを登録し、追加登録されたｋ−１番目に登録された出力ラベルに対して、追加登録されたｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルの空エントリを検索し、追加登録されたｋ＋１番目の出力ラベルを登録し、追加登録されたｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、追加登録されたｋ番目に登録された出力ラベルに対して、追加登録されたｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、追加登録された最後の出力ラベルに対して、追加登録された最後から２番目の出力ラベルの格納位置情報を登録し、追加登録された最後の出力ラベルであることを示すフラグ情報を登録し、該出力ラベルテーブルにおいて、追加登録された最後から２番目の出力ラベルに対して、追加登録された最後の出力ラベルの格納位置情報を登録し、
最後に、前記入力ラベルテーブルにおいて、現時点で最後に登録された出力ラベルの格納位置情報から追加登録された最後の出力ラベルの格納位置情報に変更することを特徴とするマルチキャストＭＰＬＳノードのテーブル追加登録方法。
【請求項４】
マルチキャストＭＰＬＳノードのコンピュータ上に設けられたＭＰＬＳテーブルに対して削除処理を行う、マルチキャストＭＰＬＳノードのテーブル削除方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルからポイントツーマルチポイントのラベルを削除する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
削除するラベルの入力ラベルを特定する削除第１過程と、
前記入力ラベルテーブルの特定した前記入力ラベルを検索し、最初に登録された出力ラベルの格納位置情報を取得する削除第２過程と、
前記出力ラベルテーブルの最初に登録された出力ラベルを検索する削除第３過程と、
前記出力ラベルテーブルの２番目に登録された出力ラベルを検索し、ｋ番目に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、該出力ラベルテーブルにおいて、ｋ−１番目に登録された出力ラベルから、削除された出力ラベルの格納位置情報を削除し、ｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、ｋ＋１番目に登録された出力ラベルから、削除された出力ラベルの格納位置情報を削除し、ｋ−１番目に登録された出力ラベルの格納位置情報を登録する削除第４過程と、
最初に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、２番目に登録された出力ラベルの格納位置情報を検索し、最初に登録された出力ラベルの格納位置情報を削除し、次に、入力ラベルにおいて、最初に登録された出力ラベルの格納位置情報から２番目に登録された出力ラベルの格納位置情報に変更する削除第５過程と、
最後に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、最後から２番目に登録された出力ラベルの格納位置情報を検索し、最後に登録された出力ラベルの格納位置情報を削除し、次に入力ラベルにおいて、最後に登録された出力ラベルの格納位置情報から最後から２番目に登録された出力ラベルの格納位置情報に変更する削除第６過程と、を行うことを特徴とするマルチキャストＭＰＬＳノードのテーブル削除方法。
【請求項５】
マルチキャストＭＰＬＳノードのテーブルに置けるポイントツーマルチポイントのラベルを検索するマルチキャストＭＰＬＳノードのテーブル検索方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルを検索する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
前記入力ラベルテーブルの該当する入力ラベルを検索する検索第１過程と、
前記入力ラベルテーブルにおいて、該当する入力ラベルから最初に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第２過程と、
前記出力ラベルテーブルにおいて、最初に登録された格納位置情報から出力ラベルを確定し、２番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第３過程と、
前記出力ラベルテーブルにおいて、２番目に登録された格納位置情報から出力ラベルを確定し、３番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第４過程と、
前記出力ラベルテーブルにおいて、ｋ番目に登録された格納位置情報から出力ラベルを確定し、ｋ＋１番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第５過程と、
前記出力ラベルテーブルにおいて、最後から２番目に登録された格納位置情報から出ラベルを確定し、最後に登録された出力ラベルの格納位置情報を取得し、検索を実施し、複数の出力ラベルを特定する検索第６過程と、
を行うことを特徴とするマルチキャストＭＰＬＳノードのテーブル検索方法。
【請求項６】
マルチキャストＭＰＬＳノードのテーブルにおける、１つの入力ラベルに対して単一の出力ラベルを持つポイントツーポイントのラベルを登録するマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル登録方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルに、ポイントツーポイントのラベルを初期登録する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
前記入力ラベルテーブルの空エントリを検索し、入力ラベルを登録する過程と、
前記出力ラベルテーブルの空エントリを検索し、出力ラベルを登録する過程と、
前記入力ラベルテーブルにおいて、登録された出力ラベルの格納位置情報を登録する過程と、
前記出力ラベルテーブルにおいて、登録された出力ラベルに対して、最後の出力ラベルであることを示すフラグ情報を登録する過程と、
を行うことを特徴とするマルチキャストＭＰＬＳテーブルのポイントツーポイントラベル登録方法。
【請求項７】
マルチキャストＭＰＬＳノードのテーブルにおける、１つの入力ラベルに対して単一の出力ラベルを持つポイントツーポイントのラベルを検索するマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル検索方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルの、ポイントツーポイントのラベルを検索する要求を受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
前記入力ラベルテーブルの該当する入力ラベルを検索する過程と、
前記入力ラベルテーブルにおいて、前記該当する入力ラベルから登録された出力ラベルの格納位置情報を取得し、検索を実施する過程と、
前記出力ラベルテーブルにおいて、単一の出力ラベルを特定する過程と、
を行うことを特徴とするマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル検索方法。
【請求項８】
マルチキャストＭＰＬＳノードのコンピュータ上にＭＰＬＳテーブルを構成するマルチキャストＭＰＬＳノードのテーブル構成方法において、
入力ラベルを複数の出力ラベルに交換することによりＭＰＬＳパケットをポイントツーマルチキャストポイントでラベル転送可能な、マルチキャストＭＰＬＳノードの記憶手段上に、テーブルを構成する場合には、
前記マルチキャストＭＰＬＳノードは、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルを記憶手段上に設け、
前記ＭＰＬＳテーブルに、ポイントツーマルチポイントのラベルを初期登録する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
前記入力ラベルに対して複数の前記出力ラベルの登録が必要な場合に、
前記入力ラベルテーブルの空エントリを検索し、入力ラベルを登録する初期登録第１過程と、
前記出力ラベルテーブルの空エントリを検索し、１番目の出力ラベルを登録する初期登録第２過程と、
前記入力ラベルテーブルにおいて、前記出力ラベルの１番目に登録された格納位置情報を登録する初期登録第３過程と、
前記出力ラベルテーブルの空エントリを検索し、２番目の出力ラベルを登録し、１番目に登録された出力ラベルの格納位置情報を登録する初期登録第４過程と、
前記出力ラベルテーブルにおいて、１番目に登録された出力ラベルに対して、２番目に登録された出力ラベルの格納位置情報を登録する初期登録第５過程と、
前記出力ラベルテーブルにおいて、前記初期登録第４過程から前記初期登録第５過程を、最後の出力ラベルを登録するまで繰り返すことにより、
前記出力ラベルテーブルの空エントリを検索し、ｋ番目の出力ラベルを登録し、ｋ−１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、ｋ−１番目に登録された出力ラベルに対して、ｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルの空エントリを検索し、ｋ＋１番目の出力ラベルを登録し、ｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、ｋ番目に登録された出力ラベルに対して、ｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、最後に登録された出力ラベルに対して、最後から２番目に登録された出力ラベルの格納位置情報を登録し、最後の出力ラベルであることを示すフラグ情報を登録し、該出力ラベルテーブルにおいて、最後から２番目に登録された出力ラベルに対して、最後に登録された出力ラベルの格納位置情報を登録し、
最後に、前記入力ラベルテーブルにおいて、出力ラベルの最後に登録された格納位置情報を登録する初期登録過程と、
前記ＭＰＬＳテーブルに追加登録する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
前記入力ラベルテーブルの同一の入力ラベルを検索し、現時点で最後に登録された出力ラベルの格納位置情報を取得する追加登録第１過程と、
前記出力ラベルテーブルの空エントリを検索し、出力ラベルを登録する追加登録第２過程と、
前記出力ラベルテーブルにおいて、追加登録された１番目の出力ラベルに対して、現時点で最後に登録された出力ラベルの格納位置情報を登録する追加登録第３過程と、
前記出力ラベルテーブルにおいて、現時点で最後に登録された出力ラベルに対して、追加登録された１番目の出力ラベルの格納位置情報を登録し、最後の出力ラベルであることを示すフラグ情報を削除する追加登録第４の過程と、
前記出力ラベルテーブルの空エントリを検索し、追加登録された２番目の出力ラベルを登録し、追加登録された１番目に登録された出力ラベルの格納位置情報を登録する追加登録第５の過程と、
前記出力ラベルテーブルにおいて、追加登録された１番目に登録された出力ラベルに対して、追加登録された２番目に登録された出力ラベルの格納位置情報を登録する追加登録第６の過程と、
前記出力ラベルテーブルにおいて、前記追加登録第５の過程から前記追加登録第６の過程までの手順を追加登録された最後の出力ラベルを登録するまで繰り返すことにより、
前記出力ラベルテーブルの空エントリを検索し、追加登録されたｋ番目の出力ラベルを登録し、追加登録されたｋ−１番目に登録された出力ラベルに対して、追加登録されたｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルの空エントリを検索し、追加登録されたｋ＋１番目の出力ラベルを登録し、追加登録されたｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、追加登録されたｋ番目に登録された出力ラベルに対して、追加登録されたｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、追加登録された最後の出力ラベルに対して、追加登録された最後から２番目の出力ラベルの格納位置情報を登録し、追加登録された最後の出力ラベルであることを示すフラグ情報を登録し、該出力ラベルテーブルにおいて、追加登録された最後から２番目の出力ラベルに対して、追加登録された最後の出力ラベルの格納位置情報を登録し、
最後に、前記入力ラベルテーブルにおいて、現時点で最後に登録された出力ラベルの格納位置情報から追加登録された最後の出力ラベルの格納位置情報に変更する追加登録過程と、
前記ＭＰＬＳテーブルからポイントツーマルチポイントのラベルを削除する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
削除するラベルの入力ラベルを特定する削除第１過程と、
前記入力ラベルテーブルの特定した前記入力ラベルを検索し、最初に登録された出力ラベルの格納位置情報を取得する削除第２過程と、
前記出力ラベルテーブルの最初に登録された出力ラベルを検索する削除第３過程と、
前記出力ラベルテーブルの２番目に登録された出力ラベルを検索し、ｋ番目に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、該出力ラベルテーブルにおいて、ｋ−１番目に登録された出力ラベルから、削除された出力ラベルの格納位置情報を削除し、ｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、ｋ＋１番目に登録された出力ラベルから、削除された出力ラベルの格納位置情報を削除し、ｋ−１番目に登録された出力ラベルの格納位置情報を登録する削除第４過程と、
最初に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、２番目に登録された出力ラベルの格納位置情報を検索し、最初に登録された出力ラベルの格納位置情報を削除し、次に、入力ラベルにおいて、最初に登録された出力ラベルの格納位置情報から２番目に登録された出力ラベルの格納位置情報に変更する削除第５過程と、
最後に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、最後から２番目に登録された出力ラベルの格納位置情報を検索し、最後に登録された出力ラベルの格納位置情報を削除し、次に入力ラベルにおいて、最後に登録された出力ラベルの格納位置情報から最後から２番目に登録された出力ラベルの格納位置情報に変更する削除第６過程と、からなる削除過程と、
前記ＭＰＬＳテーブルを検索する要求をノードから受け付けた場合には、
前記マルチキャストＭＰＬＳノードは、
前記入力ラベルテーブルの該当する入力ラベルを検索する検索第１過程と、
前記入力ラベルテーブルにおいて、該当する入力ラベルから最初に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第２過程と、
前記出力ラベルテーブルにおいて、最初に登録された格納位置情報から出力ラベルを確定し、２番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第３過程と、
前記出力ラベルテーブルにおいて、２番目に登録された格納位置情報から出力ラベルを確定し、３番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第４過程と、
前記出力ラベルテーブルにおいて、ｋ番目に登録された格納位置情報から出力ラベルを確定し、ｋ＋１番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第５過程と、
前記出力ラベルテーブルにおいて、最後から２番目に登録された格納位置情報から出ラベルを確定し、最後に登録された出力ラベルの格納位置情報を取得し、検索を実施し、複数の出力ラベルを特定する検索第６過程と、からなる検索過程と、
を行うマルチキャストＭＰＬＳノードのテーブル運用方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャストＭＰＬＳノード技術に係り、特に、マルチキャストＭＰＬＳノードのテーブル構成、初期登録処理、追加登録処理、削除処理及び検索処理を行うための、マルチキャストＭＰＬＳノードのテーブル構成方法及びマルチキャストＭＰＬＳノードのテーブル初期登録方法及びマルチキャストＭＰＬＳノードのテーブル追加登録方法及びマルチキャストＭＰＬＳノードのテーブル削除方法及びマルチキャストＭＰＬＳノードのテーブル検索方法及びマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル登録方法及びマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル検索方法及びマルチキャストＭＰＬＳノードのテーブル運用方法に関する。
【背景技術】
【０００２】
従来のＭＰＬＳノードの場合、１つの入力ラベルに対して単一の出力ラベルを持つポイントツーポイントのラベルを処理する機能しか持たない。そのため、１つの入力ラベルに対して１つの出力ラベルを登録するエントリ機能しか持たない。ここで、１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベルを処理するためには、１つの入力ラベルに対して１つの出力ラベルを登録するエントリを出力ラベルの数だけ用意し、入力ラベルは同一のラベル識別子として登録する必要がある。
【０００３】
そのとき、１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベルを登録するために、複数の出力ラベルを登録するエントリ分の同一入力ラベルを登録するための領域を確保する必要があるため、メモリ使用効率が悪い。また、ここでは、ラベルが１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベルであることを解釈できないため、同一の入力ラベルを持つ出力ラベルをテーブルから決定するために、全エントリを検索する必要があるため、検索時間の効率が悪い（例えば、非特許文献１参照）。
【非特許文献１】www.itf.org/ofc.rfc303/txt
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上記従来の方式を使用した場合、以下のような問題がある。
【０００５】
（１）  メモリ領域の割当を、１つの入力ラベルに対して複数の出力ラベルを持つ、ポイントツーマルチポイントのラベルを登録するために、複数の出力ラベル分、同一入力ラベルを登録するエントリを用意する必要があるため、メモリ使用効率が悪い。
【０００６】
（２）  検索時に検索終了のフラグがないため、テーブル内の全てのエントリを検索する必要があり、検索のための時間効率が悪い。
【０００７】
本発明は、上記の点に鑑みなされたもので、マルチキャストＭＰＬＳノードのテーブルのメモリ使用効率を低減し、さらに、検索時間を短縮することが可能なマルチキャストＭＰＬＳノードのテーブル構成方法及びマルチキャストＭＰＬＳノードのテーブル初期登録方法及びマルチキャストＭＰＬＳノードのテーブル追加登録方法及びマルチキャストＭＰＬＳノードのテーブル削除方法及びマルチキャストＭＰＬＳノードのテーブル検索方法及びマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル登録方法及びマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル検索方法及びマルチキャストＭＰＬＳノードのテーブル運用方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、マルチキャストＭＰＬＳノードのコンピュータ上にＭＰＬＳテーブルを構成するマルチキャストＭＰＬＳノードのテーブル構成方法において、
入力ラベルを複数の出力ラベルに交換することによりＭＰＬＳパケットをポイントツーマルチキャストポイントでラベル転送可能な、マルチキャストＭＰＬＳノードの記憶手段上に、テーブルを構成する場合には、
ＭＰＬＳノードは、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルを記憶手段に設ける。
【０００９】
本発明は、マルチキャストＭＰＬＳノードのコンピュータ上に設けられたＭＰＬＳテーブルに対して初期登録を行う、マルチキャストＭＰＬＳノードのテーブル初期登録方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルに、ポイントツーマルチポイントのラベルを初期登録する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
入力ラベルに対して複数の出力ラベルの登録が必要な場合に、
入力ラベルテーブルの空エントリを検索し、入力ラベルを登録する初期登録第１過程と、
出力ラベルテーブルの空エントリを検索し、１番目の出力ラベルを登録する初期登録第２過程と、
入力ラベルテーブルにおいて、出力ラベルの１番目に登録された格納位置情報を登録する初期登録第３過程と、
出力ラベルテーブルの空エントリを検索し、２番目の出力ラベルを登録し、１番目に登録された出力ラベルの格納位置情報を登録する初期登録第４過程と、
出力ラベルテーブルにおいて、１番目に登録された出力ラベルに対して、２番目に登録された出力ラベルの格納位置情報を登録する初期登録第５過程と、
出力ラベルテーブルにおいて、初期登録第４過程から初期登録第５過程を、最後の出力ラベルを登録するまで繰り返すことにより、
出力ラベルテーブルの空エントリを検索し、ｋ番目の出力ラベルを登録し、ｋ−１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、ｋ−１番目に登録された出力ラベルに対して、ｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルの空エントリを検索し、ｋ＋１番目の出力ラベルを登録し、ｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、ｋ番目に登録された出力ラベルに対して、ｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、最後に登録された出力ラベルに対して、最後から２番目に登録された出力ラベルの格納位置情報を登録し、最後の出力ラベルであることを示すフラグ情報を登録し、該出力ラベルテーブルにおいて、最後から２番目に登録された出力ラベルに対して、最後に登録された出力ラベルの格納位置情報を登録し、
最後に、入力ラベルテーブルにおいて、出力ラベルの最後に登録された格納位置情報を登録する。
【００１０】
本発明は、マルチキャストＭＰＬＳノードのコンピュータ上に設けられたＭＰＬＳテーブルに対して追加登録を行う、マルチキャストＭＰＬＳノードのテーブル追加登録方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルに追加登録する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
入力ラベルテーブルの同一の入力ラベルを検索し、現時点で最後に登録された出力ラベルの格納位置情報を取得する追加登録第１過程と、
出力ラベルテーブルの空エントリを検索し、出力ラベルを登録する追加登録第２過程と、
出力ラベルテーブルにおいて、追加登録された１番目の出力ラベルに対して、現時点で最後に登録された出力ラベルの格納位置情報を登録する追加登録第３過程と、
出力ラベルテーブルにおいて、現時点で最後に登録された出力ラベルに対して、追加登録された１番目の出力ラベルの格納位置情報を登録し、最後の出力ラベルであることを示すフラグ情報を削除する追加登録第４の過程と、
出力ラベルテーブルの空エントリを検索し、追加登録された２番目の出力ラベルを登録し、追加登録された１番目に登録された出力ラベルの格納位置情報を登録する追加登録第５の過程と、
出力ラベルテーブルにおいて、追加登録された１番目に登録された出力ラベルに対して、追加登録された２番目に登録された出力ラベルの格納位置情報を登録する追加登録第６の過程と、
出力ラベルテーブルにおいて、追加登録第５の過程から追加登録第６の過程までの手順を追加登録された最後の出力ラベルを登録するまで繰り返すことにより、
出力ラベルテーブルの空エントリを検索し、追加登録されたｋ番目の出力ラベルを登録し、追加登録されたｋ−１番目に登録された出力ラベルに対して、追加登録されたｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルの空エントリを検索し、追加登録されたｋ＋１番目の出力ラベルを登録し、追加登録されたｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、追加登録されたｋ番目に登録された出力ラベルに対して、追加登録されたｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、追加登録された最後の出力ラベルに対して、追加登録された最後から２番目の出力ラベルの格納位置情報を登録し、追加登録された最後の出力ラベルであることを示すフラグ情報を登録し、該出力ラベルテーブルにおいて、追加登録された最後から２番目の出力ラベルに対して、追加登録された最後の出力ラベルの格納位置情報を登録し、
最後に、入力ラベルテーブルにおいて、現時点で最後に登録された出力ラベルの格納位置情報から追加登録された最後の出力ラベルの格納位置情報に変更する。
【００１１】
本発明は、マルチキャストＭＰＬＳノードのコンピュータ上に設けられたＭＰＬＳテーブルに対して削除処理を行う、マルチキャストＭＰＬＳノードのテーブル削除方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルからポイントツーマルチポイントのラベルを削除する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
削除するラベルの入力ラベルを特定する削除第１過程と、
入力ラベルテーブルの特定した入力ラベルを検索し、最初に登録された出力ラベルの格納位置情報を取得する削除第２過程と、
出力ラベルテーブルの最初に登録された出力ラベルを検索する削除第３過程と、
出力ラベルテーブルの２番目に登録された出力ラベルを検索し、ｋ番目に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、該出力ラベルテーブルにおいて、ｋ−１番目に登録された出力ラベルから、削除された出力ラベルの格納位置情報を削除し、ｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、ｋ＋１番目に登録された出力ラベルから、削除された出力ラベルの格納位置情報を削除し、ｋ−１番目に登録された出力ラベルの格納位置情報を登録する削除第４過程と、
最初に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、２番目に登録された出力ラベルの格納位置情報を検索し、最初に登録された出力ラベルの格納位置情報を削除し、次に、入力ラベルにおいて、最初に登録された出力ラベルの格納位置情報から２番目に登録された出力ラベルの格納位置情報に変更する削除第５過程と、
最後に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、最後から２番目に登録された出力ラベルの格納位置情報を検索し、最後に登録された出力ラベルの格納位置情報を削除し、次に入力ラベルにおいて、最後に登録された出力ラベルの格納位置情報から最後から２番目に登録された出力ラベルの格納位置情報に変更する削除第６過程と、を行う。
【００１２】
本発明は、マルチキャストＭＰＬＳノードのテーブルに置けるポイントツーマルチポイントのラベルを検索するマルチキャストＭＰＬＳノードのテーブル検索方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルを検索する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
入力ラベルテーブルの該当する入力ラベルを検索する検索第１過程と、
入力ラベルテーブルにおいて、該当する入力ラベルから最初に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第２過程と、
出力ラベルテーブルにおいて、最初に登録された格納位置情報から出力ラベルを確定し、２番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第３過程と、
出力ラベルテーブルにおいて、２番目に登録された格納位置情報から出力ラベルを確定し、３番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第４過程と、
出力ラベルテーブルにおいて、ｋ番目に登録された格納位置情報から出力ラベルを確定し、ｋ＋１番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第５過程と、
出力ラベルテーブルにおいて、最後から２番目に登録された格納位置情報から出ラベルを確定し、最後に登録された出力ラベルの格納位置情報を取得し、検索を実施し、複数の出力ラベルを特定する検索第６過程と、を行う。
【００１３】
本発明は、マルチキャストＭＰＬＳノードのテーブルにおける、１つの入力ラベルに対して単一の出力ラベルを持つポイントツーポイントのラベルを登録するマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル登録方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルに、ポイントツーポイントのラベルを初期登録する要求を受け付けた場合には、
マルチキャストＭＰＬＳノードは、
入力ラベルテーブルの空エントリを検索し、入力ラベルを登録する過程と、
出力ラベルテーブルの空エントリを検索し、出力ラベルを登録する過程と、
入力ラベルテーブルにおいて、登録された出力ラベルの格納位置情報を登録する過程と、
出力ラベルテーブルにおいて、登録された出力ラベルに対して、最後の出力ラベルであることを示すフラグ情報を登録する過程と、を行う。
【００１４】
本発明は、マルチキャストＭＰＬＳノードのテーブルにおける、１つの入力ラベルに対して単一の出力ラベルを持つポイントツーポイントのラベルを検索するマルチキャストＭＰＬＳテーブルのポイントツーポイントのラベル検索方法において、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルからなるＭＰＬＳテーブルの、ポイントツーポイントのラベルを検索する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
入力ラベルテーブルの該当する入力ラベルを検索する過程と、
入力ラベルテーブルにおいて、該当する入力ラベルから登録された出力ラベルの格納位置情報を取得し、検索を実施する過程と、
出力ラベルテーブルにおいて、単一の出力ラベルを特定する過程と、を行う。
【００１５】
本発明は、マルチキャストＭＰＬＳノードのコンピュータ上にＭＰＬＳテーブルを構成するマルチキャストＭＰＬＳノードのテーブル構成方法において、
入力ラベルを複数の出力ラベルに交換することによりＭＰＬＳパケットをポイントツーマルチキャストポイントでラベル転送可能な、マルチキャストＭＰＬＳノードの記憶手段上に、テーブルを構成する場合には、
マルチキャストＭＰＬＳノードは、
１つの入力ラベルに対して複数の出力ラベルを持つポイントツーマルチポイントのラベル交換において、該入力ラベルと該出力ラベルの格納位置情報を関連付ける入力ラベルテーブルと、該出力ラベルの各々の格納位置情報を関連付ける出力ラベルテーブルを記憶手段上に設け、
ＭＰＬＳテーブルに、ポイントツーマルチポイントのラベルを初期登録する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
入力ラベルに対して複数の出力ラベルの登録が必要な場合に、
入力ラベルテーブルの空エントリを検索し、入力ラベルを登録する初期登録第１過程と、
出力ラベルテーブルの空エントリを検索し、１番目の出力ラベルを登録する初期登録第２過程と、
入力ラベルテーブルにおいて、出力ラベルの１番目に登録された格納位置情報を登録する初期登録第３過程と、
出力ラベルテーブルの空エントリを検索し、２番目の出力ラベルを登録し、１番目に登録された出力ラベルの格納位置情報を登録する初期登録第４過程と、
出力ラベルテーブルにおいて、１番目に登録された出力ラベルに対して、２番目に登録された出力ラベルの格納位置情報を登録する初期登録第５過程と、
出力ラベルテーブルにおいて、初期登録第４過程から初期登録第５過程を、最後の出力ラベルを登録するまで繰り返すことにより、
出力ラベルテーブルの空エントリを検索し、ｋ番目の出力ラベルを登録し、ｋ−１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、ｋ−１番目に登録された出力ラベルに対して、ｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルの空エントリを検索し、ｋ＋１番目の出力ラベルを登録し、ｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、ｋ番目に登録された出力ラベルに対して、ｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、最後に登録された出力ラベルに対して、最後から２番目に登録された出力ラベルの格納位置情報を登録し、最後の出力ラベルであることを示すフラグ情報を登録し、該出力ラベルテーブルにおいて、最後から２番目に登録された出力ラベルに対して、最後に登録された出力ラベルの格納位置情報を登録し、
最後に、入力ラベルテーブルにおいて、出力ラベルの最後に登録された格納位置情報を登録する初期登録過程と、
ＭＰＬＳテーブルに追加登録する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
入力ラベルテーブルの同一の入力ラベルを検索し、現時点で最後に登録された出力ラベルの格納位置情報を取得する追加登録第１過程と、
出力ラベルテーブルの空エントリを検索し、出力ラベルを登録する追加登録第２過程と、
出力ラベルテーブルにおいて、追加登録された１番目の出力ラベルに対して、現時点で最後に登録された出力ラベルの格納位置情報を登録する追加登録第３過程と、
出力ラベルテーブルにおいて、現時点で最後に登録された出力ラベルに対して、追加登録された１番目の出力ラベルの格納位置情報を登録し、最後の出力ラベルであることを示すフラグ情報を削除する追加登録第４の過程と、
出力ラベルテーブルの空エントリを検索し、追加登録された２番目の出力ラベルを登録し、追加登録された１番目に登録された出力ラベルの格納位置情報を登録する追加登録第５の過程と、
出力ラベルテーブルにおいて、追加登録された１番目に登録された出力ラベルに対して、追加登録された２番目に登録された出力ラベルの格納位置情報を登録する追加登録第６の過程と、
出力ラベルテーブルにおいて、追加登録第５の過程から追加登録第６の過程までの手順を追加登録された最後の出力ラベルを登録するまで繰り返すことにより、
出力ラベルテーブルの空エントリを検索し、追加登録されたｋ番目の出力ラベルを登録し、追加登録されたｋ−１番目に登録された出力ラベルに対して、追加登録されたｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルの空エントリを検索し、追加登録されたｋ＋１番目の出力ラベルを登録し、追加登録されたｋ番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、追加登録されたｋ番目に登録された出力ラベルに対して、追加登録されたｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、該出力ラベルテーブルにおいて、追加登録された最後の出力ラベルに対して、追加登録された最後から２番目の出力ラベルの格納位置情報を登録し、追加登録された最後の出力ラベルであることを示すフラグ情報を登録し、該出力ラベルテーブルにおいて、追加登録された最後から２番目の出力ラベルに対して、追加登録された最後の出力ラベルの格納位置情報を登録し、
最後に、入力ラベルテーブルにおいて、現時点で最後に登録された出力ラベルの格納位置情報から追加登録された最後の出力ラベルの格納位置情報に変更する追加登録過程と、
ＭＰＬＳテーブルからポイントツーマルチポイントのラベルを削除する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
削除するラベルの入力ラベルを特定する削除第１過程と、
入力ラベルテーブルの特定した入力ラベルを検索し、最初に登録された出力ラベルの格納位置情報を取得する削除第２過程と、
出力ラベルテーブルの最初に登録された出力ラベルを検索する削除第３過程と、
出力ラベルテーブルの２番目に登録された出力ラベルを検索し、ｋ番目に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、該出力ラベルテーブルにおいて、ｋ−１番目に登録された出力ラベルから、削除された出力ラベルの格納位置情報を削除し、ｋ＋１番目に登録された出力ラベルの格納位置情報を登録し、ｋ＋１番目に登録された出力ラベルから、削除された出力ラベルの格納位置情報を削除し、ｋ−１番目に登録された出力ラベルの格納位置情報を登録する削除第４過程と、
最初に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、２番目に登録された出力ラベルの格納位置情報を検索し、最初に登録された出力ラベルの格納位置情報を削除し、次に、入力ラベルにおいて、最初に登録された出力ラベルの格納位置情報から２番目に登録された出力ラベルの格納位置情報に変更する削除第５過程と、
最後に登録された出力ラベルを検出した場合、該出力ラベルの削除を実施し、次に、最後から２番目に登録された出力ラベルの格納位置情報を検索し、最後に登録された出力ラベルの格納位置情報を削除し、次に入力ラベルにおいて、最後に登録された出力ラベルの格納位置情報から最後から２番目に登録された出力ラベルの格納位置情報に変更する削除第６過程と、からなる削除過程と、
ＭＰＬＳテーブルを検索する要求をノードから受け付けた場合には、
マルチキャストＭＰＬＳノードは、
入力ラベルテーブルの該当する入力ラベルを検索する検索第１過程と、
入力ラベルテーブルにおいて、該当する入力ラベルから最初に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第２過程と、
出力ラベルテーブルにおいて、最初に登録された格納位置情報から出力ラベルを確定し、２番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第３過程と、
出力ラベルテーブルにおいて、２番目に登録された格納位置情報から出力ラベルを確定し、３番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第４過程と、
出力ラベルテーブルにおいて、ｋ番目に登録された格納位置情報から出力ラベルを確定し、ｋ＋１番目に登録された出力ラベルの格納位置情報を取得し、検索を実施する検索第５過程と、
出力ラベルテーブルにおいて、最後から２番目に登録された格納位置情報から出ラベルを確定し、最後に登録された出力ラベルの格納位置情報を取得し、検索を実施し、複数の出力ラベルを特定する検索第６過程と、からなる検索過程と、を行う。
【発明の効果】
【００１６】
本発明では、マルチキャストＭＰＬＳノードのテーブル構成と初期登録／追加登録／削除処理／検索処理において、メモリ使用効率を高め、検索を高速化することが可能である。また、ポイントツーポイントのラベルについても処理可能である。
【発明を実施するための最良の形態】
【００１７】
以下、図面と共に本発明の一実施の形態を説明する。なお、以下の各処理は、ＭＰＬＳノードのコンピュータ上で実行されるものである。また、以下に示すＭＰＬＳテーブルは、ＭＰＬＳノード内のハードディスク等の記憶手段上に構成されるものである。
【００１８】
［ＭＰＬＳテーブル構成］
まず、ＭＰＬＳテーブルの構成について説明する。
【００１９】
図１は、本発明の一実施の形態におけるＭＰＬＳテーブルの構成を示す。
【００２０】
同図に示すように、ＭＰＬＳノード上に構成されるＭＰＬＳテーブルは、入力ラベルテーブルと出力ラベルテーブル２つのテーブルを持つ。入力ラベルテーブルは、入力ラベル、出力先頭アドレス、出力最後尾アドレスによって構成され、出力ラベルテーブルは、格納位置情報アドレス、出力ラベル、先登録アドレス（ＰＥＡ：Previous entry address），次登録アドレス（ＮＥＡ：Next entry address）、Ｅｎｄによって構成される。ポイントツーマルチポイントエントリは、入力ラベルテーブル内の１エントリと出力ラベルテーブル内の複数のポイントツーポイントエントリによって構成される。出力先頭アドレスは、出力ラベルに登録された最初のポイントツーマルチポイントエントリの格納位置情報アドレスを示し、出力最後尾アドレスは、出力ラベルに登録された最後のポイントツーマルチポイントエントリの格納位置情報アドレスを示す。ＰＥＡは、同じ入力ラベルを持つ１つ前に登録したエントリの格納位置情報アドレスを示し、ＮＥＡは、同じ入力ラベルを持つ１つ次に登録されたエントリの格納位置情報アドレスを示し、Ｅｎｄは、同じ入力ラベルを持つ最後のエントリを示す（最後のリストであれば１、そうでなければ０と設定する）。
【００２１】
［初期テーブル登録処理］
図２は、本発明の一実施の形態における初期登録時のテーブルを示し、図３は、本発明の一実施の形態における初期テーブル登録処理のフローチャートであり、図４は、本発明の一実施の形態における初期登録時のテーブルのメモリブロックの動作を示す。
【００２２】
初期登録時に、入力ラベル＝１、出力ラベル＝１１，２９，１７，３８を持つポイントツーマルチポイントのエントリを格納するとき（図２）、入力ラベルテーブル内に同一の入力ラベルを持つエントリがないため、空きエントリを検索し（ステップ１０２）、入力ラベルを登録（ステップ１０１）、また、出力ラベルテーブル空きエントリを検索し（格納位置情報アドレス＝３）に最初に登録する出力ラベル＝１１を格納する。このとき、入力ラベルテーブルの先頭アドレスに最初の出力ラベルを格納した出力ラベルテーブルの格納位置情報アドレス（＝３）を登録し、出力ラベルテーブルのＥｎｄ＝０と設定する（ステップ１０３）。
【００２３】
次に、出力ラベルテーブル空きエントリを検索し（格納位置情報アドレス＝６）に２番目に登録する出力ラベル＝２９を格納する。このとき、出力ラベルテーブルの最初の出力ラベルを格納した格納位置情報アドレス（＝３）を、先登録アドレス（ＰＥＡ）に登録し、出力ラベルテーブルのＥｎｄ＝０と設定する（ステップ１０４）。また、出力ラベルテーブルの最初の出力ラベルを格納したエントリは、２番目に出力ラベルを格納した格納位置情報アドレス（＝６）をＮＥＡに登録する（ステップ１０５）。
【００２４】
次に、出力ラベルテーブル空きエントリを検索し、格納位置情報アドレス（＝８）に３番目に登録する出力ラベル＝１７を格納する。このとき、出力ラベルテーブルの２番目の出力ラベルを格納した格納位置情報アドレス（＝６）をＰＥＡに登録し、出力ラベルテーブルのＥｎｄ＝０と設定する（ステップ１０６）。また、出力ラベルテーブルの２番目の出力ラベルを格納したエントリは、３番目に出力ラベルを格納した格納位置情報アドレス（＝８）をＮＥＡに登録する（ステップ１０７）。
【００２５】
最後に、出力ラベルテーブル空きエントリを検索し、格納位置情報アドレス（＝１０）に最後に登録する出力ラベル＝３８を格納する。このとき、出力ラベルテーブルの３番目の出力ラベルを格納した格納位置情報アドレス（＝８）をＰＥＡに登録し、出力ラベルテーブルのＥｎｄ＝１と設定する。次に、入力ラベルテーブルの最後尾アドレスに最後に出力ラベルを格納した出力ラベルテーブルの格納位置情報アドレス（＝１０）を登録する（ステップ１０８）。
【００２６】
また、出力ラベルテーブルの３番目の出力ラベルを格納したエントリは、３番目に出力ラベルを格納した格納位置情報アドレス（＝１０）をＮＥＡに登録する（ステップ１０９）。
【００２７】
［追加登録処理］
図５は、本発明の一実施の形態における追加登録時のテーブルを示し、図６は、本発明の一実施の形態における追加登録処理のフローチャートを示し、図７は、本発明の一実施の形態における追加登録時のテーブルのメモリブロックの動作を示す。
【００２８】
ポイントツーマルチポイントのマルチキャスト転送ツリーは、動的に変化するため、グループメンバシップを動的に変更させるための検索アルゴリズムが必要となる。図７において、入力ラベル＝１、出力ラベル＝５，６１のエントリを格納するとき、既に同一の入力ラベルのエントリが存在するため、入力ラベルテーブルの入力ラベル＝１のエントリの最後尾アドレスに格納された格納位置情報アドレス（＝１０）を確認する（ステップ２０１）。情報から現時点で最後に格納された出力ラベルの格納位置情報アドレス（＝１０）を確認し、次に出力ラベルテーブルの空きエントリを検索し（ステップ２０２）、格納位置情報アドレス（＝１１）を追加登録する最初の出力ラベルを格納する。このとき、出力ラベルテーブルの格納位置情報アドレス（＝１１）のエントリのＰＥＡ値を、格納位置情報アドレス（＝１０）、Ｅｎｄ＝０とし（ステップ２０３）、格納位置情報アドレス＝１０のエントリのＮＥＡ値を格納位置情報アドレス＝１１、Ｅｎｄ＝０と変更する（ステップ２０４）。
【００２９】
次に、出力ラベルテーブルの空きエントリを検索し（ステップ２０５）、格納位置情報アドレス＝１２を追加登録する２番目（最後）の出力ラベルを格納する。このとき、出力ラベルテーブルの格納位置情報アドレス＝１２のエントリＰＥＡ値を格納位置情報アドレス＝１１、Ｅｎｄ＝１とし（ステップ２０６）、格納位置情報アドレス＝１１のエントリのＮＥＡ値を格納位置情報アドレス＝１２と変更する（ステップ２０７）。
【００３０】
次に、入力ラベルテーブルの入力ラベル＝１の最後尾アドレス＝１２と変更する（ステップ２０８）。このように、最後尾アドレスを用いることにより追加時の検索スピードが向上する。上記のような手順でポイントツーマルチポイントの追加処理が完了する。
【００３１】
［削除処理］
図８は、本発明の一実施の形態における削除処理時のテーブルを示し、図９は、本発明の一実施の形態における削除処理のフローチャートであり、図１０は、本発明の一実施の形態における削除処理時のテーブルのメモリブロックの動作を示す。
【００３２】
削除処理では、削除時に、下流からセッションを特定し、削除するラベルの入力ラベルを特定する（ステップ３０１）。そして、ポイントツーマルチポイントの部分ツリーが削除されるため、ポイントツーマルチポイントエントリのＰＥＡ，ＮＥＡ、Ｅｎｄを連続したリストに再処理する必要がある。図１０において、出力ラベルテーブルの格納位置情報アドレス＝６に格納された出力ラベル＝２９のエントリを削除するとき（ステップ３０２，３０３）、ＰＥＡ，ＮＥＡが、格納位置情報アドレス＝３，８のため、格納位置情報アドレス＝３に格納されたＮＥＡ値を格納位置情報アドレス＝８へ（ステップ３０４）、格納位置情報アドレス＝８に格納されたＰＥＡ値を格納位置情報アドレス＝３へ変更する（ステップ３０５）。
【００３３】
これにより、ポイントツーマルチポイントの部分ツリーが削除され、削除処理が完了する。
【００３４】
上記のテーブル構成と、初期登録処理、追加登録処理、削除処理により、メモリ使用効率を高めることができる。
【００３５】
［検索処理］
図１１は、本発明の一実施の形態における検索時のテーブルを示し、図１２は、本発明の一実施の形態におけるテーブル検索処理のフローチャートであり、図１３は、本発明の一実施の形態における検索処理時のテーブルのメモリブロックの動作を示す。
【００３６】
テーブル検索時に、入力ラベル＝１の出力ラベルを検索するとき、入力ラベルテーブルの先頭アドレスから格納位置情報アドレス＝３の出力ラベルテーブルを検索する（ステップ４０１）。
【００３７】
次に、格納位置情報アドレス＝３を検索し、出力ラベル１１を特定する（ステップ４０２）。
【００３８】
次に、ＮＥＡから格納位置情報アドレス＝６の出力ラベルテーブルを検索し、出力ラベル２９を特定する（ステップ４０３）。
【００３９】
次に、ＮＥＡから格納位置情報アドレス＝８の出力ラベルテーブルを検索し、出力ラベル１７を特定する（ステップ４０４）。
【００４０】
次に、ＮＥＡから格納位置情報アドレス＝１０の出力ラベルテーブルを検索し、出力ラベル３８を特定する（ステップ４０５）。
【００４１】
次に、ＮＥＡから格納位置情報アドレス＝１１の出力ラベルテーブルを検索し、出力ラベル５を特定する（ステップ４０６）。
【００４２】
これを、Ｅｎｄ＝１のエントリを検索するまで繰り返し、出力ラベル＝１１，２９，１７，３８，５を特定し、ポイントツーマルチポイントエントリを検索する。
【００４３】
上記のような検索処理を行うことにより、検索時間を短縮できる。
【００４４】
［ポイントツーポイントのテーブル登録処理］
図１４は、本発明の一実施の形態におけるポイントツーポイント登録処理時のテーブルを示し、図１５は、本発明の一実施の形態におけるポイントツーポイント登録処理のフローチャートであり、図１６は、本発明の一実施の形態におけるポイントツーポイント登録処理時のテーブルのメモリブロックの動作を示す。
【００４５】
図１４に示す入力ラベル＝３、出力ラベル＝７を持つポイントツーポイントのエントリを格納するとき、空きエントリ（先頭アドレス＝７）を検索し、入力ラベルを登録（ステップ５０１）、また、出力ラベルテーブルの格納位置情報アドレス＝７に出力ラベルを格納する（ステップ５０２，５０３）。このとき、入力ラベルテーブルの最後尾アドレスに出力ラベルを格納した出力ラベルテーブルの格納位置情報アドレスを登録し、また、出力ラベルテーブルにおいて、Ｅｎｄ＝１と設定する。これで、入力ラベル＝３のポイントツーポイントエントリがこれのみであることを示す。
【００４６】
これにより、ポイントツーポイントのラベル登録が完了する。
【００４７】
［ポイントツーポイントのテーブル検索処理］
図１７は、本発明の一実施の形態におけるポイントツーポイント検索時のテーブルを示し、図１８は、本発明の一実施の形態におけるポイントツーポイント検索処理のフローチャートであり、図１９は、本発明の一実施の形態におけるポイントツーポイント検索時のテーブルのメモリブロックの動作を示す。
【００４８】
図１７に示す入力ラベル＝３の出力ラベルを検索するとき、入力ラベルテーブルの先頭アドレスから格納位置情報アドレス＝７の出力ラベルテーブルを検索し、出力ラベル＝７を特定し（ステップ６０１）、次に、格納位置情報アドレス＝７のＥｎｄ＝１のため検索を終了し、ポイントツーポイントエントリを検索する（ステップ６０２）。
【００４９】
このように、ポイントツーポイントのラベル処理も可能となる。
【００５０】
また、本発明は、上記の実施の形態における新規登録、追加登録、削除、検索の各処理をプログラムとして構築し、ＭＰＬＳノードのコンピュータにインストールする、または、ネットワークを介して流通させることも可能である。
【００５１】
また、構築されたプログラムをＭＰＬＳノードのコンピュータに接続されるハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、実行時にインストールすることも可能である。
【００５２】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００５３】
本発明は、マルチキャストＭＰＬＳノードのテーブル構成とテーブルへの初期登録・追加登録・削除・テーブル検索に適用可能である。
【図面の簡単な説明】
【００５４】
【図１】本発明の一実施の形態におけるＭＰＬＳテーブルの構成図である。
【図２】本発明の一実施の形態における初期登録時のテーブルを示す図である。
【図３】本発明の一実施の形態における初期テーブル登録処理のフローチャートである。
【図４】本発明の一実施の形態における初期登録時のテーブルのメモリブロックの動作を示す図である。
【図５】本発明の一実施の形態における追加登録時のテーブルを示す図である。
【図６】本発明の一実施の形態における追加登録処理のフローチャートである。
【図７】本発明の一実施の形態における追加登録時のテーブルのメモリブロックの動作を示す図である。
【図８】本発明の一実施の形態における削除処理時のテーブルを示す図である。
【図９】本発明の一実施の形態における削除処理のフローチャートである。
【図１０】本発明の一実施の形態における削除処理時のテーブルのメモリブロックの動作を示す図である。
【図１１】本発明の一実施の形態における検索時のテーブルを示す図である。
【図１２】本発明の一実施の形態におけるテーブル検索処理のフローチャートである。
【図１３】本発明の一実施の形態における検索処理時のテーブルのメモリブロックの動作を示す図である。
【図１４】本発明の一実施の形態におけるポイントツーポイント登録処理時のテーブルを示す図である。
【図１５】本発明の一実施の形態におけるポイントツーポイント登録処理のフローチャートである。
【図１６】本発明の一実施の形態におけるポイントツーポイント登録処理時のテーブルのメモリブロックの動作を示す図である。
【図１７】本発明の一実施の形態におけるポイントツーポイント検索時のテーブルを示す図である。
【図１８】本発明の一実施の形態におけるポイントツーポイント検索処理のフローチャートである。
【図１９】本発明の一実施の形態におけるポイントツーポイント検索時のテーブルのメモリブロックの動作を示す図である。
【図１】
2005072905.tif 000003
【図２】
2005072905.tif 000004
【図３】
2005072905.tif 000005
【図４】
2005072905.tif 000006
【図５】
2005072905.tif 000007
【図６】
2005072905.tif 000008
【図７】
2005072905.tif 000009
【図８】
2005072905.tif 000010
【図９】
2005072905.tif 000011
【図１０】
2005072905.tif 000012
【図１１】
2005072905.tif 000013
【図１２】
2005072905.tif 000014
【図１３】
2005072905.tif 000015
【図１４】
2005072905.tif 000016
【図１５】
2005072905.tif 000017
【図１６】
2005072905.tif 000018
【図１７】
2005072905.tif 000019
【図１８】
2005072905.tif 000020
【図１９】
2005072905.tif 000021