JP2001251351A

JP2001251351A - パケット交換機における入力パケット処理方式

Info

Publication number: JP2001251351A
Application number: JP2000061806A
Authority: JP
Inventors: Yoshiaki Shioda; 佳明塩田
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2000-03-02
Filing date: 2000-03-02
Publication date: 2001-09-14
Also published as: CA2338969C; CA2338969A1; US20010021189A1; US6987762B2

Abstract

(57)【要約】【課題】 LSR において、複数回のポップ処理が実施さ
れるMPLSパケットが、後から到着したパケットの処理開
始時間に影響を与えないようにする。【解決手段】 MPLSパケットのシムヘッダの内容及び事
前に設定された情報に基づき、スワップ、プッシュ及び
ポップの内から実施すべき操作を判断しその実施に必要
な情報を取得すると共に出力方路情報を取得する処理を
流れ作業的に行うパイプラインP1を備える。ヘッダコン
トローラ７は、複数回線２から入力される各パケットの
先頭シムヘッダをパイプラインP1に順次に入力し、得ら
れた情報に基づいて各パケットの先頭シムヘッダに対し
実際の操作を実施する。ポップ操作の結果、新しく先頭
になったシムヘッダが存在する場合、その新しく先頭に
なったシムヘッダをパイプラインP1に入力する処理から
再度繰り返す。つまり、MPLSパケットのポップ処理は１
度にまとめて行うのではなく、パイプラインをループさ
せて処理する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はパケット交換機に関
し、特に複数の回線カードとスイッチとで構成されるパ
ケット交換機において回線から入力されたパケットが回
線カードを通じてスイッチに出力されるまでの処理に関
する。

【０００２】

【従来の技術】インターネットの普及によりＩＰ（イン
タネット・プロトコル）ネットワーク上のトラヒックが
増大し、従来型のＩＰルータでは、データを効率的に運
ぶことが困難であり、またサービス品質を保つことが困
難であるという問題が存在する。これら問題を解決する
ための通信方式にＭＰＬＳ（Multi Protocol Label Sw
itching)方式がある。

【０００３】ＭＰＬＳ方式の技術は、たとえば「1999年
12月、アイ・イー・イー・イー・コミュニケーションズ
・マガジン、第３７巻、第１２号、３６〜６８頁(IEEE
COMMUNICATIONS MAGAZINE, VOL.37, NO.12, DECEMBER,
1999, pp.36-68) に記載されている。

【０００４】ＭＰＬＳは、図３（Ａ）に示すようなフォ
ーマットを持つＩＰパケットを、図３（Ｂ）に示すよう
にシムヘッダと呼ばれるデータでカプセル化する。シム
ヘッダ中には、図３（Ｃ）に示すようにルーティング情
報を示す識別子であるラベルが存在する。ラベルは２０
ビットの長さを持つことにより、１００万個の入力パケ
ットを識別することができる。また、ＭＰＬＳパケット
は、図３（Ｄ）に示すように複数のシムヘッダを付加す
ることによる階層構造をとることができ、これをラベル
スタッキングと呼ぶ。ＬＳＲ(Label Switch Router)
は、ＬＳＲに到着したＭＰＬＳパケットに対しラベルを
もとにルーティングおよびスイッチング処理を行い、隣
接ルータにパケットを転送する。

【０００５】さらにパケットは、例えばＩＥＴＦのＲＦ
Ｃ１６６１で規定されたＰＰＰパケットでカプセル化さ
せて回線に送受信される。ＰＰＰはＩＰパケットもＭＰ
ＬＳパケットも運ぶことが可能で、ＰＰＰパケットを受
信したＬＳＲは受信したパケットがＩＰパケットなの
か、ＭＰＬＳパケットなのかを区別する。ＬＳＲにラベ
ル情報を設定する制御信号はＭＰＬＳパケットではな
く、ＩＰパケット上のＴＣＰをトランスポート層として
使用したＬＤＰ（Label Distribution Protocol）を用
いて行われる。

【０００６】ＬＳＲには３種類が存在し、それぞれイン
グレスエッジＬＳＲ，コアＬＳＲ、イグレスエッジＬＳ
Ｒと呼ばれる。イングレスエッジＬＳＲは、回線から入
力されたＩＰパケットを、ＩＰヘッダ中のソースアドレ
スや、デスティネーションアドレスに基づき、あらかじ
め指定しておいた特定の組み合わせに分類する。これを
ＦＥＣ（Forwarding Equivalence Class）に分類すると
呼ぶ。イングレスエッジＬＳＲは、このＦＥＣに分類さ
れたＩＰパケット群に対し、ＭＰＬＳ化の判断を行い、
必要であればＭＰＬＳパケット化して、隣接するＬＳＲ
へ転送する。コアＬＳＲは、ＭＰＬＳパケットの中継を
行う。中継の際には入力されたパケットのラベルを出力
用のラベルに付け替える（スワップと呼ぶ。シムヘッダ
中のラベルのみ付け替える）処理、パケットに新たなシ
ムヘッダを加える（プッシュと呼ばれる）処理、パケッ
トから先頭シムヘッダ（複数のシムヘッダでもよい）を
取り除く（ポップと呼ばれる）処理を行い、処理された
パケットを隣接するＬＳＲへ転送する。イグレスエッジ
ＬＳＲは、入力パケットの先頭からラベルを全て取り除
いてＩＰパケット化し、ＩＰルーティングによってパケ
ットを隣接ＩＰルータに転送する。

【０００７】ＬＳＲのＭＰＬＳパケット処理手順は、ま
ず回線入力インタフェースにＭＰＬＳパケットが到着す
ると、入力パケットのシムヘッダ中のラベルをキーとし
てＩＬＭ(Incoming Label Map)と呼ばれるテーブルを参
照する。ＩＬＭの内容はポインタであり、ＮＨＬＦＥ(N
ext Hop Label Forwarding Entry) と呼ばれる、ある入
力ラベルに対し、どの種類のラベル操作を行うかが記述
されたテーブルを指し示す。また、ＮＨＬＦＥをもとに
ルーティング処理を実施する。その後、ＬＳＲはその内
部でスイッチング処理を行い、回線出力インタフェース
からパケットを隣接ＬＳＲやＩＰルータに送信する。ま
た、イングレスエッジＬＳＲでは、ＦＥＣに分類された
ＩＰパケット群でＭＰＬＳ化の必要のあるものは、ＮＨ
ＬＦＥを参照した後ラベルをプッシュする。これらＩＬ
ＭとＮＨＬＦＥを用いる動作に関しては、ＩＥＴＦのド
ラフト仕様（ＭＰＬＳのアーキテクチャを規定してい
る）で規定されているが、その実装に関しては規定され
ない。

【０００８】ここで、交換機またはルータの既存の実装
方式として、複数枚の回線カードと、スイッチカードと
で交換機またはルータを構成する方式がある。通常、回
線カードには複数の回線を搭載可能であるが、１枚の回
線カードの通信帯域はあらかじめ決められており、例え
ば帯域が２．４Ｇｂｐｓ(Giga Bit Per Sec)の場合、伝
送レートが２．４Ｇｂｐｓの回線ならば１回線、１５５
Ｍｂｐｓ(Mega Bit Per Sec)の回線ならば１６回線収容
可能である。ここで、ＭＰＬＳは回線ごとにラベル空間
を持つことが可能である。よって回線が異なれば同じラ
ベルの値を使用してもよい。この回線ごとのラベルを識
別するために、回線カード上で２０ビットのラベルに入
力回線を区別するための識別子のビットを付加すると、
１枚の回線カードに１６回線を収容する場合には、ＩＬ
Ｍの参照キーとして２４ビットが必要になる。また、１
６００万個の入力パケットが識別可能となる。

【０００９】一方、装置の設計においてはメモリの制
限、管理の複雑化などの理由で、１６００万個もの識別
子を同時に使用することは困難であり、使用する入力パ
ケットの識別子を制限することが行われる。ＭＰＬＳに
おいて、これはＩＬＭが指し示すポインタの数を装置で
使用可能な数に制限することで可能である。

【００１０】１枚の回線カード装置で使用可能な識別子
の数を６４０００個とすると、ＩＬＭの各エントリが持
つべきポインタは２バイト（１６ビット）となる。ここ
で、上記２４ビットをメモリへアクセスするためのアド
レスとするＩＬＭの実装を行うと、必要なメモリの量は
３２メガバイトである。しかし、実際に使用する領域は
１２８キロバイト（６４０００×２バイト）であるの
で、メモリのほとんどの領域が無駄になってしまう問題
がある。

【００１１】このような入力ラベルの識別処理を実施す
る従来技術が、特表平８−５１０１０２号公報「パケッ
トネットワーク内ラベル処理」に開示されている。この
技術は入力ラベルをあらかじめ第一部分および第二部分
に固定したもので構成されることを想定し、交換機は
（１）第一部分および第二部分のラベル、または（２）
第一部分のみのラベル、または（３）第二部分のみのラ
ベルという３通りの異なるモードで入力パケットの識別
処理を行うことが可能である。しかし、この技術は入力
回線番号が考慮されていない。また、ＭＰＬＳに相当す
る上記（２）のモードである入力ラベルが第一部分から
のみ構成される場合には、第一部分に対応するテーブル
を検索する際に、入力ラベルをメモリアクセス用のアド
レスとして使用する。しかしこの方法ではＭＰＬＳのラ
ベルのように第一部分のビット長が長い場合には、前述
のような大規模メモリを必要とする問題があり、メモリ
の効率的な利用方法としては不十分であった。

【００１２】一方、ＩＬＭ、ＮＨＬＦＥを参照した結
果、ポップ処理が必要になったＭＰＬＳパケットは、ラ
ベルスタックの先頭からラベルを一つ取り除く。ポップ
処理を行った結果としては、ＩＰパケットに戻る場合と
ＭＰＬＳパケットのままの場合がある。ＩＰパケットに
戻る場合には、そのＬＳＲはイグレスエッジＬＳＲであ
ることを意味し、その後前述のＩＰルーティング処理を
行う。ＭＰＬＳパケットのままの場合には、もう一度Ｉ
ＬＭとＮＨＬＦＥを参照してラベル処理を行う必要があ
る。よって、このポップ処理が複数回行われることもあ
る。装置はこのポップ処理の繰り返しに対応する必要が
あるが、これは装置の実装を複雑化するとともに、性能
を劣化させる要因でもある。例えば、一つのパケットの
全ての処理が終了するまで次のパケットを処理しない方
法では、２回のポップが発生すると後から到着したパケ
ットは、２回のポップが発生していない時よりも、パケ
ット処理１回分の処理開始遅延が発生する。よって、２
回以上のポップが実施されるパケットを多数受信した場
合には、処理待ちのパケット数が増加して、処理せずに
廃棄せざるを得ない状況に陥る恐れがあるという問題が
ある。

【００１３】さらに、これまで説明してきた通り、ＬＳ
ＲはＭＰＬＳパケットだけでなく、ルーティングを含む
ＩＰパケット処理が必要であり、ＭＰＬＳとＩＰの両方
の処理を統合し、効率的かつ高速に処理可能な方法が求
められる。

【００１４】

【発明が解決しようとする課題】本発明の目的は、複数
回のポップ処理が実施されるパケットが、後から到着し
たパケットの処理開始時間に影響を与えないようにする
ことにある。

【００１５】本発明の別の目的は、メモリを効率的に使
用可能でかつ高速なＩＬＭ検索処理を実現することにあ
る。

【００１６】本発明の他の目的は、ＭＰＬＳとＩＰの両
方の処理を統合し、効率的かつ高速な交換機を提供する
ことにある。

【００１７】

【課題を解決するための手段】第１の発明は、複数階層
によるスタッキング構成が可能なヘッダを持つプロトコ
ルのパケット（ＭＰＬＳパケット）に付加されたヘッダ
（シムヘッダ）中のラベルに基づいて転送処理を行うパ
ケット交換機において、１パケットに対する複数回のポ
ップ操作を１度にまとめて実施するのではなく、１回の
ポップ操作が終了すると、一旦パケットを処理の最初の
段階へ戻したのち、再びＩＬＭ検索からパケット処理を
実施する。具体的には、パケットのヘッダの内容および
事前に設定された情報に基づき、ラベルに対して実施す
べき操作の種類を判断してその操作の実施に必要な情報
を取得すると共に出力方路情報を取得する処理を流れ作
業的に行うパイプラインと、回線から入力される各パケ
ットの先頭ヘッダを前記パイプラインに順次に入力し、
得られた情報に基づいて各パケットの先頭ヘッダに対し
て実際の操作を実施すると共に、ポップ操作の結果、新
しく先頭になったヘッダが存在するパケットはその新し
く先頭になったヘッダを前記パイプラインに入力する段
階から処理を再度繰り返す手段とを備えている。

【００１８】第２の発明は、第１の発明において、ラベ
ルと入力回線番号を組み合わせた検索キーを二個以上の
ブロックに分割し、ブロックごとにＩＬＭのテーブルを
検索する。具体的には、前記パイプラインは、ラベルに
対してどの種類の操作を行うかを記述した第１のテーブ
ル（ＮＨＬＦＥ）と、前記第１のテーブルの該当エント
リのポインタを検索するための第２のテーブル（ＩＬ
Ｍ）とを含むヘッダ処理用テーブルを参照して、前記操
作の実施に必要な情報を取得する構成を有し、且つ、前
記パイプラインは、パケットが入力された入力回線番号
と先頭ヘッダ中のラベルとを合わせたものを検索キーと
して前記第２のテーブルを検索する手段を有し、該手段
は前記検索キーを１次からｎ次までのｎ個の分割検索キ
ーに分割して使用し、前記第２のテーブルは１次検索テ
ーブルからｎ次検索テーブルまでの複数の検索テーブル
に分割され、１次分割検索キーは、１次検索テーブルを
検索するために用い、前記１次検索テーブルを検索して
得られる結果は、２次検索テーブルを検索するための検
索キーの上位キーとして、２次分割検索キーは下位キー
として用いられ、前記上位キーと前記下位キーを合わせ
たものを前記２次検索テーブルを検索するためのキーと
して用い、ｋ−１次（ｋは１からｎまでの整数）検索テ
ーブルを検索して得られる結果は、ｋ次検索テーブルを
検索するための検索キーの上位キーとして、ｋ次分割検
索キーは下位キーとして用いられ、前記上位キーと前記
下位キーを合わせたものを前記ｋ次検索テーブルを検索
するためのキーとして用い、ｎ次検索テーブルを検索し
て得られる結果が前記第１のテーブルにアクセスするた
めのポインタとなる構成を有する。

【００１９】第３の発明は、ＩＰ処理用パイプライン、
ＭＰＬＳ処理パイプラインを具備し、入力されたパケッ
トの種類を判断してそれぞれのパイプラインにパケット
ヘッダを送信し、それぞれのパイプラインでの処理を実
施した後、パイプライン処理を合流させることでＭＰＬ
ＳとＩＰの両方の処理を統合する。具体的には、複数階
層によるスタッキング構成が可能な第１ヘッダ（シムヘ
ッダ）を持つ第１プロトコルのパケット（ＭＰＬＳパケ
ット）に付加された第１ヘッダ中のラベルに基づいて第
１プロトコルのパケットの転送処理を行うと共に、複数
階層によるスタッキング構成が不可能な第２ヘッダ（Ｉ
ＰヘッダおよびＴＣＰ／ＵＤＰヘッダ）を持つ第２プロ
トコルのパケット（ＩＰパケット）に付加された第２ヘ
ッダ中のラベルに基づいて第２プロトコルのパケットの
転送処理を行うパケット交換機における入力パケット処
理方式において、第１ヘッダの内容および事前に設定さ
れた情報に基づき、ラベルに対して実施すべき操作の種
類を判断してその操作の実施に必要な情報を取得すると
共に出力方路情報を取得する処理を流れ作業的に行い、
予め定められたフォーマットの処理結果を出力する第１
パイプラインと、第２ヘッダの内容および事前に設定さ
れた情報に基づき、第２プロトコルのパケットの第１プ
ロトコルによるパケット化の必要性を判断してその操作
の実施に必要な情報を取得すると共に出力方路情報を取
得する処理を流れ作業的に行い、前記フォーマットで処
理結果を出力する第２パイプラインと、複数の回線から
入力されるパケットのプロトコルを判断し、第１プロト
コルのパケットであれば、回線から入力された各パケッ
トの先頭ヘッダを前記第１パイプラインに順次に入力
し、得られた情報に基づいて各パケットの先頭ヘッダに
対して実際の操作を実施すると共に、ポップ操作の結
果、新しく先頭になった第１ヘッダが存在するパケット
はその新しく先頭になったヘッダを前記第１パイプライ
ンに入力する段階から処理を再度繰り返し、第２プロト
コルのパケットであれば、回線から入力された各パケッ
トのヘッダを前記第２パイプラインに順次に入力し、得
られた情報に基づいて各パケットに対して実際の操作を
実施する手段とを備えている。

【００２０】

【発明の実施の形態】次に本発明の実施の形態の例につ
いて図面を参照して詳細に説明する。

【００２１】図１を参照すると、本発明の実施の形態に
かかるＬＳＲ１は、複数枚の回線カード３とこれらに接
続されたスイッチ４とで構成されている。それぞれの回
線カード３は、対向側装置とＰＰＰパケットにより相互
接続される複数の回線２を収容し、ＩＰパケットルーテ
ィング処理、ＩＰパケットのＭＰＬＳ化処理およびＭＰ
ＬＳパケットのラベル処理を実施してＬＳＲ１上の出力
方路情報（どの回線カードのどの回線に出力するか）を
求め、スイッチ４に出力する処理および、スイッチ４か
らパケットを受信して出力方路情報に基づき該当する回
線にパケットを出力する処理機能を兼ね備えている。ま
た、スイッチ４は、各回線カード３から入力されたパケ
ットを出力方路情報に基づきスイッチング処理を行い、
該当する回線カード３に出力する機能を備えている。な
お、ＬＳＲ１はイングレス、コア、イグレスの全てのＬ
ＳＲ機能を有し、例えば或る回線カード３の或る回線は
イングレスＬＳＲ用、ある回線は通常のＩＰルーティン
グ用という使用が可能であるものとする。つまりＬＳＲ
はＩＰルータとしても動作する。

【００２２】図２は回線カード３における回線からの入
力部（回線から入力されたパケットがスイッチ４に出力
されるまでのブロック）全体を示している。この例の入
力部は、バッファコントローラ５、バッファメモリ６、
ヘッダコントローラ７、ＩＬＭ検索部８、ラベル処理部
９、フォワーディングエンジン１０、ＣＰＵ１１、ポイ
ンタ格納メモリ１２、ＮＨＬＦＥ検索部１３、ＮＨＬＦ
Ｅ格納メモリ１４、ヘッダ等格納メモリ１５、ＦＥＣ分
類部１６、ルーティングエンジン１７、マージ部１８を
含んでおり、ＩＬＭ検索部８、ＮＨＬＦＥ検索部１３お
よびラベル処理部９でＭＰＬＳ処理用のパイプラインＰ
１が構成され、ＦＥＣ分類部１６、ルーティングエンジ
ン１７、マージ部１８およびラベル処理部９でＩＰルー
ティング用かつＭＰＬＳ化判断用のパイプラインＰ２が
構成される。

【００２３】ＣＰＵ１１はオペレータや自律動作プロト
コルによって得られた情報をもとにして、回線カード３
内部の各ブロックの設定を行い、ポインタ格納メモリ１
２、ＮＨＬＦＥ格納メモリ１４、ヘッダ等格納メモリ１
５、ＦＥＣ分類部１６およびルーティングエンジン１７
に必要なデータを設定する。ヘッダ等格納メモリ１５の
各エントリには、スイッチ４で使用される出力方路情報
とパケットにプッシュすべきシムヘッダ群などが格納さ
れる。ＮＨＬＦＥ格納メモリ１４には、ラベル操作情
報、スワップする新ラベル、プッシュするシムヘッダ
長、ヘッダ等格納メモリ１５をアクセスする際のアドレ
スとして使用される出力方路情報ポインタなどを各エン
トリに持つＮＨＬＦＥが格納される。ポインタ格納メモ
リ１２には、ＮＨＬＦＥのエントリへのポインタを保持
するＩＬＭが格納される。ＦＥＣ分類部１６には、ＦＥ
Ｃ分類条件のマッチ条件、各条件毎のシムヘッダ長や出
力方路情報ポインタ（ヘッダ等格納メモリ１５をアクセ
スする際のアドレスとして使用される）などが設定さ
れ、またルーティングエンジン１７にはルーティングテ
ーブルが設定される。

【００２４】バッファコントローラ５は複数回線２から
入力されたパケットをバッファメモリ６に書き込むと同
時に、回線から入力されるパケットのヘッダ情報（ＩＰ
パケットの場合は、ＩＰヘッダおよびＴＣＰ/ ＵＤＰヘ
ッダ、ＭＰＬＳパケットの場合は全てのシムヘッダおよ
びＩＰヘッダ、ＴＣＰ/ ＵＤＰヘッダを指す）を、パケ
ットを受信しながら抜き出して入力回線番号とともにヘ
ッダコントローラ７へ送信する。また、バッファコント
ローラ５はバッファメモリ６内部の未使用領域を管理し
ている。ヘッダコントローラ７に対して、パケット全体
を送信せずにヘッダのみを送信する理由は、ＭＰＬＳラ
ベル処理またはＩＰルーティング、ＩＰパケットのＭＰ
ＬＳ化処理を行うにはパケットのヘッダのみを参照すれ
ば十分であり、パケット全体を送信するのは無駄である
ことによる。

【００２５】ヘッダコントローラ７はパケットのヘッダ
情報や入力回線番号をＩＬＭ検索部８、ＦＥＣ分類部１
６、ルーティングエンジン１７に送信する機能と、ヘッ
ダ処理終了をラベル処理部９から通知された後にＭＰＬ
Ｓパケットのポップ処理、バッファメモリ６内部のデー
タの変更およびフォワーディングエンジン１０へパケッ
トの転送依頼も行う。フォワーディングエンジン１０は
ヘッダ処理が終了したパケットをスイッチ４へ転送す
る。

【００２６】ＩＬＭ検索部８はヘッダ情報をもとにポイ
ンタ格納メモリ１２上のＩＬＭを検索し、ＮＨＬＦＥ検
索部１３で使用されるポインタを得る。ＮＨＬＦＥ検索
部１３はポインタに基づきＮＨＬＦＥ格納メモリ１４を
検索して、ラベル処理情報およびラベル処理部９で使用
するポインタを得るとともに、必要であればＭＰＬＳパ
ケットのスワップ処理を行う。

【００２７】ＦＥＣ分類部１６は、パケットをＩＰやＴ
ＣＰのヘッダ情報の組であるＦＥＣ（Forwarding Equiv
alence Classes）に分類して、パケットをＭＰＬＳ化す
るかどうかを判定する。ルーティングエンジン１７はＩ
Ｐパケットのルーティング処理を行う。マージ部１８は
ＦＥＣ分類部１６の結果とルーティングエンジン１７の
結果をマージして、結果をラベル処理部９に送信する。

【００２８】ラベル処理部９はヘッダ等格納メモリ１５
にアクセスし、プッシュするシムヘッダや出力方路など
のスイッチング情報を得て、結果をヘッダコントローラ
７に通知する。

【００２９】複数回線２から受信するパケットのフォー
マットを図３に示す。実際はこれらパケットはＰＰＰパ
ケットにカプセル化されている。図３（Ａ）はＩＰパケ
ットを示す。（Ｂ）はＭＰＬＳパケットを示す。（Ｃ）
は（Ｂ）のシムヘッダの詳細を示す。（Ｄ）はラベルス
タッキングされているＭＰＬＳパケットの例を示す。

【００３０】次に、本発明の実施の形態のより詳しい構
成とその動作を説明する。

【００３１】図２を参照すると、複数回線２からバッフ
ァコントローラ５へ入力される複数のパケットは、バッ
ファメモリ６に十分な空き容量があれば、バッファコン
トローラ５によってバッファメモリ６に書き込まれる
（空き容量が無い場合には、バッファコントローラ５で
廃棄される）。この際、シムヘッダのプッシュが行われ
る場合には、バッファメモリ６に書き込まれたパケット
の先頭にシムヘッダが追加されるので、あらかじめパケ
ットバッファの先頭部分を、想定されるシムヘッダの長
さに合わせて空けて書き込む。同時に、当該パケットバ
ッファの先頭アドレス、パケットのヘッダ情報および入
力回線番号情報がシーケンス番号と共に一時的にバッフ
ァコントローラ５内部に保持される。このとき、パケッ
トの種類がＩＰパケットか、ＭＰＬＳパケットかを判別
する。

【００３２】入力パケットにおけるヘッダ部分の受信が
完了すると、バッファコントローラ５は保持していたバ
ッファの先頭アドレス、ヘッダ情報（ＩＰパケットの場
合は、ＩＰヘッダおよびＴＣＰ/ ＵＤＰヘッダ、ＭＰＬ
Ｓパケットの場合は全てのシムヘッダおよびＩＰヘッ
ダ、ＴＣＰ/ ＵＤＰヘッダを指す）、入力回線番号、パ
ケットの種類、およびシーケンス番号をヘッダコントロ
ーラ７に送信する。ヘッダコントローラ７に送信するデ
ータのフォーマットを図４に示す。ここでシーケンス番
号は、スイッチ４への転送が終了していないパケットを
管理するために使用される。また、ヘッダコントローラ
７は、受信イネーブル信号をバッファコントローラ５に
送信しており、バッファコントローラ５はこのイネーブ
ル信号がアクティブのときにのみ前記データを送信可能
である。

【００３３】パケットの受信およびバッファメモリ６へ
の書き込みが終了すると、バッファコントローラ５はパ
ケットの伝送誤りをチェックし、正常であれば処理開始
依頼信号をヘッダコントローラ７へ送信すると共に、フ
ォワ―ディングエンジン１０にシーケンス番号およびパ
ケットが格納されているバッファメモリ６中のアドレス
を通知する。バッファコントローラ５はヘッダ情報など
の転送が終了すると、その内部にシーケンス番号とバッ
ファメモリ６に保存されているパケットのバッファアド
レスを保存する。伝送誤りチェックの結果が異常であれ
ば、ヘッダコントローラ７に対し、渡したヘッダ情報な
どの廃棄を廃棄依頼信号によって指示する。

【００３４】処理開始依頼を受信したヘッダコントロー
ラ７はバッファコントローラ５から受信したパケットの
種類の情報がＭＰＬＳであれば、ヘッダ情報、入力回線
番号、シーケンス番号をＩＬＭ検索部８に渡す。ＩＰで
あれば同じくＦＥＣ分類部１６とルーティングエンジン
１７に渡す。ここで各部８、１６、１７からヘッダコン
トローラ７には受信イネーブル信号による送信制御が実
施される。また、ヘッダコントローラ７はバッファコン
トローラ５から受信した情報（図４）を、フォワーディ
ングエンジン１０へパケット送信依頼を行うまで保存す
る。

【００３５】ここで、ヘッダコントローラ７が情報をＩ
ＬＭ検索部８に送信する動作から、後述するラベル処理
部９での動作まではパイプラインＰ１によるパイプライ
ン処理で実施される。例えば、ＩＬＭ検索部８は、ＩＬ
Ｍ処理が終了して結果をＮＨＬＦＥ検索部１３へ送信す
ると、すぐにヘッダコントローラ７から次のパケットヘ
ッダを受信することが可能である。また、ＮＨＬＦＥ検
索部１３は処理結果をラベル処理部９へ送信すると、す
ぐにＩＬＭ検索部８から次のデータを受信することが可
能である。同様にヘッダコントローラ７が情報をＦＥＣ
分類部１６、ルーティングエンジン１７に送信する動作
から、後述するラベル処理部９での動作まではパイプラ
インＰ２によるパイプライン処理で実施される。例え
ば、ＦＥＣ分類部１６およびルーティングエンジン１７
は処理結果をマージ部１８へ送信すると、すぐにヘッダ
コントローラ７から次のパケットヘッダを受信すること
が可能である。また、マージ部１８は処理結果をラベル
処理部９に送信すると、すぐにＦＥＣ分類部１６、ルー
ティングエンジン１７から次のデータを受信することが
可能である。双方のパイプラインＰ１、Ｐ２による処理
時間は同じとされ、双方のパイプラインＰ１、Ｐ２によ
る処理はラベル処理部９において合流する。

【００３６】ヘッダコントローラ７がＩＬＭ検索部８へ
渡すデータの構成を図５に示す。複数のシムヘッダによ
る多階層のＭＰＬＳパケットの場合でも、渡すシムヘッ
ダは先頭のみである。回線カードに収容される回線数が
例えば１６の場合、入力回線番号情報は４ビット（２の
４乗＝１６）となり、ラベルの２０ビットと合計して２
４ビットのデータ（ＩＬＭ検索キー）となる。ＩＬＭ検
索部８では、このＩＬＭ検索キーおよび検索テーブルを
複数個のブロックに分割してＩＬＭの検索を実施する。
図６（Ａ）に例として２個に分割した場合の例を示す。
２４ビットのキーをｍビットと２４−ｍビットのブロッ
クに分割し、それぞれを１次分割検索キー、２次分割検
索キーとする。また、図６（Ｂ）、（Ｃ）に示すような
１次検索テーブル８１および複数のサブテーブル８２か
ら構成される２次検索テーブル８３を用意する。１次検
索テーブル８１の内容は２次検索テーブル８３中のサブ
テーブル８２にアクセスするためのポインタの集合であ
り、２次検索テーブル８３の内容は次段のＮＨＬＦＥ検
索部１３で使用されるポインタの集合である。１次、２
次検索テーブル８１、８３はポインタ格納メモリ１２内
部に格納される。それぞれのテーブル８１、８３は、図
７に示すように別々の物理メモリ上に置き、各物理メモ
リをＩＬＭ検索部８に対して並列に配置することで同時
アクセスを可能にする。勿論、両方のテーブルを同一メ
モリ上に置いても良い。処理速度を優先する場合には、
別々の物理メモリ上に配置する。

【００３７】１次検索テーブル８１は、図６（Ｂ）に示
すように２のｍ乗個のエントリをもつ。回線カード３で
識別可能な入力ラベル（入力回線番号を含む）を（１６
００万個中）６４０００個に制限するとき、各エントリ
は２バイト（１６ビット）のポインタをエントリ内容と
して持つ（２の１６乗＝６５５３６）。つまり、エント
リ自体は２のｍ乗個だが、ポインタ数は最大２の１６乗
個分である。ＩＬＭ検索部８は、２×１次分割検索キー
をアドレスとしてポインタ格納メモリ１２上に置かれた
１次検索テーブル８１にアクセスし、２バイトのポイン
タを得る。続いてこのポインタと残りの２４−ｍビット
のデータブロックである２次分割検索キーを結合する
（ポインタが上位ビット側）。ＩＬＭ検索部８は、この
結果をアドレスとしてポインタ格納メモリ１２上に置か
れた２次検索テーブル８３にアクセスし、ＮＨＬＦＥ検
索部１３で使用される２バイトのポインタを得る。ここ
で図６（Ｃ）に示す通り、２次検索テーブル８３は最大
で６４０００個のサブテーブル８２の集合で構成され、
各サブテーブル８２は２の（２４−ｍ）乗個のエントリ
を持っている。

【００３８】ポインタを取得したＩＬＭ検索部８は、そ
のポインタと、ヘッダコントローラ７から受信したシム
ヘッダ及びシーケンス番号をＮＨＬＦＥ検索部１３に送
信する。上記において、ｍの値を変更することでＩＬＭ
の総使用メモリ量は変更される。総メモリ量は式１で表
される。２（２^m ＋２^(24-m)×６４０００）バイト … （式１）

【００３９】式１は、ｍ＝２０のときに最も少ないメモ
リ量（１次、２次検索テーブル共に１メガバイトで、合
計２メガバイト）となる。よって、図７の各物理メモリ
には各々１メガバイト以上の容量を持つメモリを用意す
ればよい。ラベルと入力回線番号の２４ビットをメモリ
へアクセスするためのアドレスとするＩＬＭ検索の方法
と比較して、必要なメモリ量は１６分の１である。

【００４０】上記例では２分割の場合を説明したが、さ
らに分割することで、使用メモリ量をより一層削減する
ことができる。

【００４１】例えばｎ個に分割する場合、ＩＬＭ検索キ
ーを１次からｎ次までのｎ個の分割検索キー、検索テー
ブルを１次からｎ次までの複数の検索テーブルに分割
し、１次分割検索キーは、１次検索テーブルを検索する
ために用い、１次検索テーブルを検索して得られる結果
は、２次検索テーブルを検索するための検索キーの上位
キーとして、２次分割検索キーは下位キーとして用いら
れ、上位キーと下位キーを合わせたものを２次検索テー
ブルを検索するためのキーとして用い、ｋ−１次（ｋは
１からｎまでの整数）検索テーブルを検索して得られる
結果は、ｋ次検索テーブルを検索するための検索キーの
上位キーとして、ｋ次分割検索キーは下位キーとして用
いられ、上位キーと下位キーを合わせたものをｋ次検索
テーブルを検索するためのキーとして用いる。最終的に
ｎ次検索テーブルを検索して得られる結果は、ＮＨＬＦ
Ｅ検索部１３で使用されるポインタである。総メモリ量
は、ｋ次分割検索キーのビット幅をｋｊとすると式２で
表される。２｛（２^k1＋６４０００（２^k2＋……＋２^kn）｝バイト … （式２）

【００４２】検索キーの分割個数を決定すると、式２の
結果を最小化するｋｊの値が求まる。よって、具体的な
分割個数の決定は、装置に搭載可能なメモリ量を決め、
このメモリ量を満たす検索キーの分割個数、各分割検索
キーのビット幅を式２を用いて求めることで実施可能で
ある。

【００４３】次にＮＨＬＦＥ検索部１３は、ＩＬＭ検索
部８からポインタとシムヘッダとシーケンス番号を受信
すると、受信したポインタをアドレスとして、ＮＨＬＦ
Ｅ格納メモリ１４にアクセスし、結果としてラベル操作
のうちスワップ、プッシュ、ポップのどの操作を行うの
かが書かれたラベル操作情報、スワップする新ラベル、
プッシュするシムヘッダの長さ、およびラベル処理部９
で使用する出力方路情報ポインタ（ヘッダ等格納メモリ
１５のアドレスとなる）を得る。これら情報のフォーマ
ット例を図８に示す。ラベル操作情報は図９のフォーマ
ットに示すようにスワップ、プッシュ、ポップの可否を
それぞれ１ビットで示す合計３ビットで構成される。次
に、ラベル操作情報のスワップビットが有効である場
合、ＩＬＭ検索部８から受信したシムヘッダ中のラベル
を、得られた新ラベルで置き換える。ラベル操作情報の
プッシュビット、ポップビットが有効であっても、プッ
シュ、ポップの処理はＮＨＬＦＥ検索部１３では実施せ
ず、後にプッシュはラベル処理部９で、ポップはヘッダ
コントローラ７でそれぞれ実施される。

【００４４】最終的に、ＮＨＬＦＥ検索部１３はシムヘ
ッダ、出力方路情報ポインタ、ラベル操作情報、シムヘ
ッダ長、シーケンス番号の各データをラベル処理部９に
送信する。この送信データのフォーマットを図１０に示
す。なお、ＮＨＬＦＥ検索部１３にはラベル処理部９か
ら受信イネーブル信号による送信制御が実施される。

【００４５】図１１はＭＰＬＳパケットに対するラベル
処理部９の動作を示すものである。ラベル処理部９で
は、ＮＨＬＦＥ検索部１３から受信した出力方路情報ポ
インタをアドレスとしてヘッダ等格納メモリ１５にアク
セスする（１０１、１０２）。結果としてスイッチ４で
使用される出力方路情報、およびパケットにプッシュす
べきシムヘッダ群を得る（１０３）。このデータフォー
マットを図１２に示す。ヘッダ等格納メモリ１５から読
み込むシムヘッダ群に含まれるシムヘッダの数はパケッ
トによらず一定である。ＮＨＬＦＥ検索部１３から出力
されるシムヘッダ長の値により実際にプッシュするシム
ヘッダの数が決定される。次にラベル処理部９は、ラベ
ル操作情報のプッシュビットが立っていれば、シムヘッ
ダ長情報に書かれた数のシムヘッダを内部保持ヘッダ
（ＮＨＬＦＥ検索部１３から受信したシムヘッダを指
す）に追加する（１０４、１０５）。プッシュビットが
立っていない場合には追加せず、得たシムヘッダ群を無
視する。いずれの場合にも、出力方路情報は内部保持ヘ
ッダに追加される（１０６）。処理が終了するとラベル
処理部９は、内部保持ヘッダおよびラベル処理操作情
報、シムヘッダ長、出力方路情報、シーケンス番号をヘ
ッダコントローラ７に対して送信する（１０７）。この
データフォーマットを図１３に示す。なお、ラベル処理
部９にはヘッダコントローラ７から受信イネーブル信号
による送信制御が実施される。

【００４６】続いてＦＥＣ分類部１６とルーティングエ
ンジン１７の動作について説明する。ＦＥＣ分類部１６
はヘッダコントローラ７からＩＰヘッダ、ＴＣＰ/ ＵＤ
Ｐヘッダ、シーケンス番号を受信し、例えばＩＰヘッダ
中のソースアドレスフィールドとＴＣＰヘッダ中のソー
スポートフィールドが特定の値を持っているとき（ＦＥ
Ｃ分類条件がマッチ）に、そのＩＰパケットをＭＰＬＳ
化する判断を行うと共に、出力方路情報ポインタを決定
する。特定の値をもっていないときには、ダミーの出力
方路情報ポインタを決定する。なお、ここで決定した出
力方路情報ポインタは、前述のＭＰＬＳと同様にラベル
処理部９がヘッダ等格納メモリ１５から出力方路情報な
どを取り出す際のアドレスとして使用される。処理終了
後、ＦＥＣ分類部１６は出力方路情報ポインタ、ＭＰＬ
Ｓ化情報、マッチ情報、シムヘッダ長、シーケンス番号
をマージ部１８に送信する。ここで、マージ部１８から
はＦＥＣ分類部１６に対し受信イネーブル信号による送
信制御が実施される。

【００４７】ルーティングエンジン１７はヘッダコント
ローラ７からシーケンス番号、ＩＰヘッダを受信し、Ｉ
Ｐヘッダ中のデスティネーションアドレスからルーティ
ングテーブルを検索して、出力方路情報（出力方路情報
ポインタとは異なり、スイッチ４で使用する出力方路情
報そのもの。ＦＥＣ分類部１６で有効な出力方路情報ポ
インタが決定されなかった場合に使用される）を得て、
シーケンス番号と共にマージ部１８に送信する。マージ
部１８からはルーティングエンジン１７に対し受信イネ
ーブル信号による送信制御が実施される。ここで得られ
る出力方路情報は、ＩＰルーティング処理によるもので
あり、ＦＥＣ分類部１６で条件がマッチせずに出力方路
情報ポインタが得られない場合に用いられることとな
る。

【００４８】マージ部１８は、ＦＥＣ分類部１６とルー
ティングエンジン１７の情報を単純にマージして（ただ
し双方の情報のシーケンス番号の一致を確認して一致し
た場合にマージする）ラベル処理部９にマージ結果を送
信する。図１４に送信する情報のフォーマットを示す。
ラベル処理部９からはマージ部１８に対し受信イネーブ
ル信号による送信制御が実施される。

【００４９】図１５はＩＰパケットに対するラベル処理
部９の動作を示すものである。ラベル処理部９では、マ
ージ部１８から受信した情報（図１４）中のマッチ情報
が有効であれば、出力方路情報ポインタを用いてヘッダ
等格納メモリ１５にアクセスし、スイッチ４で使用する
出力方路情報、パケットにプッシュすべきシムヘッダ群
を前述のＭＰＬＳパケットの処理と同様に得る（２０
１、２０２、２０４、２０５）。さらに、ＭＰＬＳ化情
報が有効であれば、シムヘッダ長情報に書かれた数のシ
ムヘッダを内部保持ヘッダとして作成する（２０６、２
０７）。ここで、プッシュビットが立っていない場合に
は追加せず、得たシムヘッダ群データを無視する。その
後、ＭＰＬＳ化情報にかかわらず、ヘッダ等格納メモリ
１５から取得した出力方路情報を内部ヘッダに付加する
（２０８）。マッチ情報が無効であれば、ヘッダ等格納
メモリ１５にはアクセスせず、内部ヘッダにマージ部１
８から受信した出力方路情報のみを追加し（２０３）、
結果をヘッダコントローラに送信する（２０９）。この
データフォーマットは図１３のＭＰＬＳの場合と同じで
あるが、シムヘッダ１９はオール０またはオール１とす
る。また、ラベル操作情報フィールドのプッシュビット
はラベル処理部９が有効化する。処理終了後、結果はヘ
ッダコントローラ７に渡される。ヘッダコントローラ７
からはラベル処理部９に対し受信イネーブル信号による
送信制御が実施される。

【００５０】次に、ＭＰＬＳパケット、ＩＰパケットの
両方に共通である、ラベル処理部９での処理終了後に実
施される処理に関して説明する。図１６はヘッダコント
ローラ７の動作に関するものである。ヘッダコントロー
ラ７はラベル処理部９から受信したデータ（図１３）に
関し、シーケンス番号を照合し( ３０１、３０２) 、該
当するパケットがＭＰＬＳパケットであれば、ラベル操
作情報のポップビットを参照する（３０３、３０４）。
ここで、ポップ処理が必要な場合には、保持していたヘ
ッダデータ中の、先頭のシムヘッダをポップする（３０
５）。結果、残されたヘッダデータがＭＰＬＳヘッダで
あれば、ＩＬＭ検索部８へ、ＩＰデータであればＦＥＣ
分類部１６およびルーティングエンジン１７へ再びヘッ
ダデータ等を送信して処理を依頼する（３０６、３０
７、３０８）。この際、もしバッファコントローラ５か
ら新規に受信したパケットヘッダ等の送信処理と競合す
る場合には、ポップ処理後のデータの送信処理を優先す
る。３０４において、ポップ処理が実施されていないこ
とが判明したパケットは、続いてスワップビットのチェ
ックを行い（３０９）、（ＮＨＬＦＥ検索部１３で）ス
ワップが実施されたパケットは、保持していたヘッダデ
ータ中の先頭シムヘッダ中のラベルを新ラベルで置き換
える（３１０）。次に、プッシュビットのチェックを行
う（３１１）。ここで、３０３で分岐したＩＰパケット
もこの処理をＭＰＬＳパケットと同様に実施する（３１
１）。プッシュビットが有効である場合には、シムヘッ
ダ群（ＭＰＬＳの仕様では、一度に複数シムヘッダのプ
ッシュが可能である）を保持していたヘッダデータの先
頭に追加する（３１２）。以上でヘッダコントローラ７
中の内部保持ヘッダデータの処理が完了となる。つま
り、ひとつのパケットの一連のパイプライン処理の終了
は、ポップ以外の処理が行われた場合である。

【００５１】全てのヘッダ処理を終了したヘッダコント
ローラ７は、更新した内部保持ヘッダを、バッファメモ
リ６中の該当パケットの先頭部分に対して上書き処理す
る（３１３）。これはバッファコントローラ５から最初
に受け取ったバッファの先頭アドレスを用いて実施され
る。ヘッダコントローラ７は最後に、処理が終了したパ
ケットのシーケンス番号をフォワーディングエンジン１
０に通知する（３１４）。

【００５２】通知を受けたフォワーディングエンジン１
０は、シーケンス番号に対応するポインタ情報を用いて
バッファメモリ６からパケットを読み出して、スイッチ
４方向へパケットを転送する。ここで、シーケンス番号
に対応するパケットがバッファメモリ６に格納されてい
る位置（ポインタ情報）は、あらかじめバッファコント
ローラ５から受信しておく。

【００５３】パケットのスイッチ４への転送が終了する
と、パケットのシーケンス番号をバッファコントローラ
５へ通知する。バッファコントローラ５は受信したシー
ケンス番号のパケットが使用していたバッファメモリを
開放し、未使用バッファリストに追加する。以上で、一
連のパケット処理が完了する。

【００５４】一連の処理においてヘッダコントローラ７
は、パイプライン処理が実施されているパケット群のヘ
ッダおよびシーケンス番号をその内部に保持している
が、保持できるヘッダの数は、あらかじめ上限となる閾
値を固定値として設定しておく。保持ヘッダ数はバッフ
ァコントローラ５からヘッダを受信するとインクリメン
トされ、フォワーディングエンジン１０にパケットの送
信を指示するとデクリメントされるが、ポップ処理が頻
繁に発生すると保持ヘッダ数が増加し、閾値を超えてし
まう場合がある。このときバッファコントローラ５へ送
信しているヘッダ受信イネーブル信号をインアクティブ
にすることによって、バッファコントローラ５からの新
規ヘッダの受信を停止する。この場合、バッファコント
ローラ５はヘッダコントローラ７からのイネーブル信号
がアクティブになるまでヘッダ情報を保持するが、バッ
ファコントローラ５内部のヘッダメモリ格納領域の空き
容量が無くなった場合には、複数回線２から受信する新
規パケットをバッファメモリ６に書き込まずに廃棄す
る。しかし、パイプライン処理により、ヘッダコントロ
ーラ７からＩＬＭ検索部８などに送信されるヘッダデー
タの送信間隔は、ＩＬＭ検索部８、ＦＥＣ分類部１６、
ルーティングエンジン１７の処理時間のうち、最大のも
のに、ほぼ左右されるため、その時間は、ひとつのパケ
ットの全ての処理が終了するまで次のパケットを処理し
ない方法に比べて短い。よってパケットの廃棄も起こり
にくい。

【００５５】

【発明の効果】第１の効果は、２回以上のポップ処理が
実施されるパケットが多数到着した場合に、後から到着
したパケットが廃棄される可能性が低くなることであ
る。その理由は、ヘッダ処理過程はパイプライン処理で
行われ、一度に複数ヘッダの処理が行われることと、Ｍ
ＰＬＳパケットのラベル処理においてポップ処理が発生
した場合、パイプライン処理過程をループさせることに
より、後から到着したパケットの待ち時間はパイプライ
ン処理過程に配置された各処理ブロックのうち、最も処
理時間がかかるブロックの処理時間にほぼ等しく、複数
回のポップ処理をまとめて処理する方法の待ち時間（ポ
ップ回数分の全パケット処理過程が必要）に比べて少な
いからである。

【００５６】第２の効果は、ＩＬＭを実現するメモリ量
が、ラベルと入力回線をＩＬＭ検索キーとして直接メモ
リにアクセスする場合と比べて、例えば１６回線を収容
する回線カードの場合には１６分の１以下になることで
ある。その理由は、ＩＬＭ検索用のキーを複数に分割
し、分割後の複数のキーを用いてＩＬＭの検索を実施す
るからである。さらに、検索キーの分割個数および各分
割検索キーのビット幅は、入力回線数と設計者の方針に
より変更可能であるからである。

【００５７】第３の効果は、ＭＰＬＳとＩＰの両方の処
理が効率的に統合されることである。その理由は、ヘッ
ダ処理過程はパイプライン処理で行われ、パイプライン
処理はＭＰＬＳ用と、ＩＰ用に２系統に分かれている
が、ラベル処理部で合流し、双方のパイプラインの処理
結果が同じフォーマットで表現されてヘッダコントロー
ラで処理されるからである。

【図面の簡単な説明】

【図１】本発明の実施の形態にかかるＬＳＲのブロック
図である。

【図２】ＬＳＲ中の回線カードにおける回線からの入力
側のブロック図である。

【図３】複数回線から入力されるＩＰ、ＭＰＬＳパケッ
トのフォーマットを示す図である。

【図４】バッファコントローラがヘッダコントローラに
送信するデータのフォーマットを示す図である。

【図５】ヘッダコントローラがＩＬＭ検索部へ渡すデー
タのフォーマットを示す図である。

【図６】ＩＬＭ検索部で使用される検索キーの説明図で
ある。

【図７】ポインタ格納メモリの物理構成を示す図であ
る。

【図８】ＮＨＬＦＥ検索部がＮＨＬＦＥ格納メモリから
得るデータのフォーマットを示す図である。

【図９】図８のデータ中のラベル操作情報の詳細を示す
図である。

【図１０】ＮＨＬＦＥ検索部がラベル処理部に送信する
データのフォーマットを示す図である。

【図１１】ラベル処理部のＭＰＬＳパケット処理のフロ
ーチャートである。

【図１２】ラベル処理部がヘッダ等格納メモリから得る
データのフォーマットを示す図である。

【図１３】ラベル処理部がヘッダコントローラへ送信す
るデータのフォーマットを示す図である。

【図１４】マージ部がラベル処理部へ出力するデータの
フォーマットを示す図である。

【図１５】ラベル処理部のＩＰパケット処理のフローチ
ャートである。

【図１６】ヘッダコントローラが、ラベル処理部から各
種データを受信してから、フォワーディングエンジンに
パケットのスイッチへの送信を依頼するまでの処理のフ
ローチャートである。

【符号の説明】

１…ＬＳＲ２…複数回線３…回線カード４…スイッチ５…バッファコントローラ６…バッファメモリ７…ヘッダコントローラ８…ＩＬＭ検索部９…ラベル処理部１０…フォワーディングエンジン１１…ＣＰＵ１２…ポインタ格納メモリ１３…ＮＨＬＦＥ検索部１４…ＮＨＬＦＥ格納メモリ１５…ヘッダ等格納メモリ１６…ＦＥＣ分類部１７…ルーティングエンジン１８…マージ部１９…シムヘッダ

───────────────────────────────────────────────────── フロントページの続きＦターム(参考） 5K030 GA01 GA05 HA08 HB28 HB29 HC01 JA05 KA15 LB05 LB11 LB18 LE06 MA12 5K034 AA02 AA09 AA11 BB06 DD01 EE11 FF04 FF08 GG03 HH02 HH04 HH06 JJ12 JJ23 KK27 MM25 SS02 9A001 BB03 BB04 CC06 DD10 FF03 JJ18 JJ25 KK56 LL09

Claims

【特許請求の範囲】

【請求項１】複数階層によるスタッキング構成が可能
なヘッダを持つプロトコルのパケットに付加されたヘッ
ダ中のラベルに基づいて転送処理を行うパケット交換機
における入力パケット処理方式において、パケットのヘッダの内容および事前に設定された情報に
基づき、ラベルに対して実施すべき操作の種類を判断し
てその操作の実施に必要な情報を取得すると共に出力方
路情報を取得する処理を流れ作業的に行うパイプライン
と、回線から入力される各パケットの先頭ヘッダを前記パイ
プラインに順次に入力し、得られた情報に基づいて各パ
ケットの先頭ヘッダに対して実際の操作を実施すると共
に、ポップ操作の結果、新しく先頭になったヘッダが存
在するパケットはその新しく先頭になったヘッダを前記
パイプラインに入力する段階から処理を再度繰り返す手
段とを備えたことを特徴とするパケット交換機における
入力パケット処理方式。
【請求項２】前記パケットがＭＰＬＳパケットであ
り、前記ヘッダがシムヘッダである請求項１記載のパケ
ット交換機における入力パケット処理方式。
【請求項３】前記パイプラインは、ラベルに対してど
の種類の操作を行うかを記述した第１のテーブルと、前
記第１のテーブルの該当エントリのポインタを検索する
ための第２のテーブルとを含むヘッダ処理用テーブルを
参照して、前記操作の実施に必要な情報を取得する請求
項１記載のパケット交換機における入力パケット処理方
式。
【請求項４】前記パイプラインは、パケットが入力さ
れた入力回線番号と先頭ヘッダ中のラベルとを合わせた
ものを検索キーとして前記第２のテーブルを検索する手
段を有し、該手段は前記検索キーを１次からｎ次までの
ｎ個の分割検索キーに分割して使用し、前記第２のテー
ブルは１次検索テーブルからｎ次検索テーブルまでの複
数の検索テーブルに分割され、１次分割検索キーは、１
次検索テーブルを検索するために用い、前記１次検索テ
ーブルを検索して得られる結果は、２次検索テーブルを
検索するための検索キーの上位キーとして、２次分割検
索キーは下位キーとして用いられ、前記上位キーと前記
下位キーを合わせたものを前記２次検索テーブルを検索
するためのキーとして用い、ｋ−１次（ｋは１からｎま
での整数）検索テーブルを検索して得られる結果は、ｋ
次検索テーブルを検索するための検索キーの上位キーと
して、ｋ次分割検索キーは下位キーとして用いられ、前
記上位キーと前記下位キーを合わせたものを前記ｋ次検
索テーブルを検索するためのキーとして用い、ｎ次検索
テーブルを検索して得られる結果が前記第１のテーブル
にアクセスするためのポインタとなる構成を有する請求
項３記載のパケット交換機における入力パケット処理方
式。
【請求項５】複数階層によるスタッキング構成が可能
な第１ヘッダを持つ第１プロトコルのパケットに付加さ
れた第１ヘッダ中のラベルに基づいて第１プロトコルの
パケットの転送処理を行うと共に、複数階層によるスタ
ッキング構成が不可能な第２ヘッダを持つ第２プロトコ
ルのパケットに付加された第２ヘッダ中のラベルに基づ
いて第２プロトコルのパケットの転送処理を行うパケッ
ト交換機における入力パケット処理方式において、第１ヘッダの内容および事前に設定された情報に基づ
き、ラベルに対して実施すべき操作の種類を判断してそ
の操作の実施に必要な情報を取得すると共に出力方路情
報を取得する処理を流れ作業的に行い、予め定められた
フォーマットの処理結果を出力する第１パイプライン
と、第２ヘッダの内容および事前に設定された情報に基づ
き、第２プロトコルのパケットの第１プロトコルによる
パケット化の必要性を判断してその操作の実施に必要な
情報を取得すると共に出力方路情報を取得する処理を流
れ作業的に行い、前記フォーマットで処理結果を出力す
る第２パイプラインと、複数の回線から入力されるパケットのプロトコルを判断
し、第１プロトコルのパケットであれば、回線から入力
された各パケットの先頭ヘッダを前記第１パイプライン
に順次に入力し、得られた情報に基づいて各パケットの
先頭ヘッダに対して実際の操作を実施すると共に、ポッ
プ操作の結果、新しく先頭になった第１ヘッダが存在す
るパケットはその新しく先頭になったヘッダを前記第１
パイプラインに入力する段階から処理を再度繰り返し、
第２プロトコルのパケットであれば、回線から入力され
た各パケットのヘッダを前記第２パイプラインに順次に
入力し、得られた情報に基づいて各パケットに対して実
際の操作を実施する手段とを備えたことを特徴とするパ
ケット交換機における入力パケット処理方式。
【請求項６】前記第１プロトコルのパケットがＭＰＬ
Ｓパケット、前記第１ヘッダがシムヘッダであり、前記
第２プロトコルのパケットがＩＰパケット、前記第２ヘ
ッダがＩＰヘッダおよびＴＣＰ／ＵＤＰヘッダである請
求項５記載のパケット交換機における入力パケット処理
方式。