Pat
J-GLOBAL ID：200903046666982865
情報中継方法および装置
Inventor：
,
,
Applicant, Patent owner：
Agent (1)：
筒井 大和
Gazette classification：公開公報
Application number (International application number)：1998362987
Publication number (International publication number)：2000188608
Application date： Dec. 21, 1998
Publication date： Jul. 04, 2000
Summary：
【要約】【課題】 経路制御テーブルに木構造データを用いる経路検索の高速化を実現する。【解決手段】 コンピュータネットワークで情報中継を行うルータ装置を、経路情報を2分木構造の経路管理テーブルTBL0で管理する経路管理部F0と、経路情報を2のp乗分木構造の経路検索テーブルTBL1で持ち、複数のポート50の一つから受信したパケット51内の宛先アドレス情報にて検索し転送先(出力すべき一つのポート50)を決定する経路検索部F1とで構成し、経路管理部F0は、経路情報エントリEの追加等に応じて経路管理テーブルTBL0の2分木構造の各ノードを更新した後、更新結果を経路検索テーブルTBL1の2のp乗分木構造に反映させるメンテナンス処理を行う。
Claim (excerpt)：
コンピュータネットワーク内におけるパケットの中継を行う複数の情報中継装置の各々に、前記パケットを次に送信すべき中継先のアドレスおよび当該中継先に対応した回線情報を含む経路情報を保持する経路制御テーブルを持たせ、個々の前記情報中継装置では、受信した前記パケットの宛先アドレスにて前記経路制御テーブルを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定する情報中継方法であって、前記経路制御テーブルを、前記経路情報を前記アドレスのマスク長の昇順で2分木構造の各2分木ノードに格納し、前記経路情報を持つ2分木ノードと分岐が発生する2分木ノードを残して縮退した構成をとる経路管理テーブルと、1つの2分木ノードと、その直下につながる(p-1)段分の合計(2のp乗-1)個分の2分木ノードを1つの2のp乗分木ノードに集約し、集約した最下段の2の(p-1)乗個の2分木ノードに、その2分木ノードより上段の2分木ノードに割り付けた前記経路情報を埋め込み、2のp乗分木ノードを、2分木を2の(p-1)乗個分併せた形で構成する2のp乗分木構造に前記アドレスのマスク長の昇順で格納し、前記経路情報を持つ2のp乗分木ノードと分岐が発生する2のp乗分木ノードを残して縮退した構造をとる経路検索テーブルと、で構成し、前記経路情報の追加、削除、変更が発生した場合に、前記経路管理テーブルの前記2分木構造における2分木ノード間の親子関係から追加、削除、変更を行うべき2分木ノードの位置を決定して前記2分木構造を更新し、前記2分木構造の更新結果に基づいて、前記経路検索テーブルの前記2のp乗分木構造に対して追加、削除、変更の必要な前記2のp乗分木ノードを更新し、受信した前記パケットの宛先アドレスにて前記経路検索テーブルの前記2のp乗分木ノードを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定することを特徴とする情報中継方法。
IPC (3)：
H04L 12/56
, G06F 17/30
, H04L 12/28
H04L 11/20 102 D
, G06F 15/413 310 A
, H04L 11/00 310 Z
5B075ND02
, 5B075ND36
, 5B075NK44
, 5B075NK54
, 5B075PQ05
, 5B075QS11
, 5K030GA01
, 5K030HA08
, 5K030HB11
, 5K030HD03
, 5K030KA05
, 5K030LB05
, 5K033AA02
, 5K033BA04
, 5K033CC01
, 5K033DA16
, 5K033DB12
, 5K033DB19
, 5K033EC02
, 5K033EC04
Cited by applicant (1)
-
Fast address lookup for Internet routers
Return to Previous Page
