(57)【特許請求の範囲】
【請求項１】
着信データ・パケットが、当該データ・パケットに含まれる宛先アドレス情報から得られる出力リンク情報に基づいて正しい出力リンクに送信される装置において、各着信データ・パケットに対応する出力リンク情報を獲得する方法であって、
１）  前記装置内のデータ・パイプライン部が前記データ・パケットを受け取って、前記装置内における当該データ・パケット用の出力リンク情報を獲得するための時間を確保するステップと、
２）  前記装置内のヘッダ・パーサ部が、各データ・パケットのヘッダ部を受け取り、当該ヘッダ部に含まれる明示的優先度情報を抽出しこれを評価するステップと、
３）  前記評価するステップの結果に基づき、前記ヘッダ・パーサ部が、前記装置内のキャッシュ・メモリに、前記宛先アドレス情報および前記出力リンク情報の対を新たなキャッシュ・エントリとして挿入するべきかどうかを選択するステップと、
４）  前記装置内のルックアップ・エンジン部が、前記宛先アドレス情報に基づいて、前記データ・パケットに対応する出力リンク情報を得るためのルックアップ・サーチを開始するステップと、
５）  前記選択するステップにおいて、前記装置内のキャッシュ制御部が、前記キャッシュ・メモリ内に、前記宛先アドレス情報に係るキャッシュ・エントリが既に存在するかどうかを検査するステップと、
６）  前記検査するステップにおいて、前記宛先アドレス情報に係る前記キャッシュ・エントリが発見された場合に、前記ルックアップ・エンジン部が前記ルックアップ・サーチを中止し、前記キャッシュ制御部によって発見された前記キャッシュ・エントリから得られる出力リンク情報を、前記キャッシュ制御部が、前記データ・パケットについての出力リンク情報として採用するために前記データ・パイプライン部に送るステップと、
７）  前記検査するステップにおいて、前記宛先アドレス情報に係る前記キャッシュ・エントリが発見されなかった場合に、前記ルックアップ・エンジン部が、前記ルックアップ・サーチによって得られた出力リンク情報を、新たなキャッシュ・エントリとして挿入するために前記キャッシュ制御部に送り、かつ、当該出力リンク情報を前記データ・パケットについての出力リンク情報として採用するために前記データ・パイプライン部に送るステップと、
を有する方法。
【請求項２】
前記出力リンク情報が、前記宛先アドレス情報に対応した、前記データ・パケットを前記装置から送出するための目標ポートID情報を含む、請求項１に記載の方法。
【請求項３】
前記明示的優先度情報が、ＤｉｆｆＳｅｒｖ  ＤＳＣＰビットおよびＶＬＡＮ優先度ビットのいずれかまたは両方を含む、請求項２に記載の方法。
【請求項４】
前記明示的優先度情報は、データ・パケットのバースト型転送を可能にするTCP伝送における、当該バースト型転送の開始を表すＳＹＮメッセージであり、前記評価するステップにおいて当該ＳＹＮメッセージが抽出され、有効であると評価された場合は、前記選択するステップにおいて、前記キャッシュ・メモリに、前記宛先アドレス情報および前記出力リンク情報の対を新たなキャッシュ・エントリとして挿入するべき選択をする、請求項２に記載の方法。
【請求項５】
前記明示的優先度情報が、データ・パケットのバースト型転送を可能にするTCP伝送における、当該バースト型転送の終了を表すＦＩＮメッセージであり、前記評価するステップにおいて当該ＦＩＮメッセージが抽出され、有効であると評価された場合に、前記キャッシュ制御部が、当該データ・パケットに含まれる宛先アドレス情報と同一の宛先アドレス情報に係るキャッシュ・エントリを前記キャッシュ・メモリから削除するステップをさらに有する、請求項４に記載の方法。
【請求項６】
着信データ・パケットが、当該データ・パケットに含まれる宛先アドレス情報から得られる出力リンク情報に基づいて正しい出力リンクに送信される装置において、各着信データ・パケットに対応する出力リンク情報を獲得する方法であって、
１）  前記装置内のデータ・パイプライン部が前記データ・パケットを受け取って、前記装置内における当該データ・パケット用の出力リンク情報を獲得するための時間を確保するステップと、
２）  前記装置内のヘッダ・パーサ部が、各データ・パケットのヘッダ部を受け取り、当該ヘッダ部に含まれる暗示的優先度情報を抽出しこれを前記装置内のルックアップ・エンジン部に送るステップと、
３）  前記ルックアップ・エンジン部が、前記暗示的優先度情報を評価し、その結果に基づき、前記装置内のキャッシュ・メモリに、前記暗示的優先度情報および前記出力リンク情報の対を新たなキャッシュ・エントリとして挿入するべきかどうかを選択するステップと、
４）  前記ルックアップ・エンジン部が、前記暗示的優先度情報に基づいて、前記データ・パケットに対応する出力リンク情報を得るためのルックアップ・サーチを開始するステップと、
５）  前記選択するステップにおいて、前記装置内のキャッシュ制御部が、前記キャッシュ・メモリ内に、前記暗示的優先度情報に係るキャッシュ・エントリが既に存在するかどうかを検査するステップと、
６）  前記検査するステップにおいて、前記暗示的優先度情報に係る前記キャッシュ・エントリが発見された場合に、前記ルックアップ・エンジン部が前記ルックアップ・サーチを中止し、前記キャッシュ制御部によって発見された前記キャッシュ・エントリから得られる出力リンク情報を、前記キャッシュ制御部が、前記データ・パケットについての出力リンク情報として採用するために前記データ・パイプライン部に送るステップと、
７）  前記検査するステップにおいて、前記暗示的優先度情報に係る前記キャッシュ・エントリが発見されなかった場合に、前記ルックアップ・エンジン部が、前記ルックアップ・サーチによって得られた出力リンク情報を、前記キャッシュ・エントリとして挿入するために前記キャッシュ制御部に送り、および、当該出力リンク情報を前記データ・パケットについての出力リンク情報として採用するために前記データ・パイプライン部に送るステップと、
を有する方法。
【請求項７】
前記暗示的優先度情報が、（ａ）プロトコル標識、（ｂ）ソース・アドレス、（ｃ）宛先アドレス、（ｄ）ソース・ポート、および（ｅ）宛先ポート、から成る５個組の要素を含む、請求項４に記載の方法。
【請求項８】
着信データ・パケットがアドレス情報に従って出力リンクに送信される装置において、キャッシュ・メモリ（３９）にキャッシュ・エントリを挿入する方法であって、
ａ）前記各着信データ・パケットごとに、前記データ・パケットが関連づけられるフローの形式あるいは優先度、に関連する分類情報を評価する評価ステップと、
ｂ）前記評価ステップの結果に基づき、前記データ・パケットについて、前記キャッシュ・メモリ（３９）に前記キャッシュ・エントリを挿入すべきかどうか選択する選択ステップと、
ｃ）前記選択ステップの結果、前記キャッシュ・エントリを挿入すべきであるとされる場合に、前記データ・パケットについて、前記アドレス情報および関連出力リンク情報を前記キャッシュ・メモリ（３９）に前記キャッシュ・エントリとして挿入する入力ステップと、
を有する方法。
【請求項９】
ａ）各データ・パケットについて、そのアドレス情報または関連出力リンク情報が、キャッシュ・エントリにすでに含まれているかどうか検査する検査ステップと、
ｂ）キャッシュ・エントリ中に前記アドレス情報または関連出力リンク情報が見つかった場合は、そのキャッシュ・エントリに記憶されている出力リンク情報を使用して、前記データ・パケットを転送する転送ステップと
をさらに有し、キャッシュ・エントリに前記アドレス情報または関連出力リンク情報が見つからない場合は、前記データ・パケットについて、前記評価ステップおよび前記選択ステップが実施される、請求項８に記載の方法。
【請求項１０】
キャッシュ・エントリを作成すべき場合に、経路指定テーブルを使って、ルックアップ・ステップから前記出力リンク情報を得る、請求項８ないし９に記載の方法。
【請求項１１】
前記ルックアップ・ステップを前記検査ステップと同時に開始し、キャッシュ・エントリ中に前記アドレス情報または関連出力リンク情報が見つかった場合は、それを停止する、請求項１０に記載の方法。
【請求項１２】
対応するキャッシュ・エントリを前記キャッシュ・メモリ（３９）に挿入するために、バースト形式のトラフィックに関連するデータ・パケットが選択される、請求項８ないし１１の一項に記載の方法。
【請求項１３】
対応するキャッシュ・エントリを前記キャッシュ・メモリ（３９）に挿入するために、前記データ・パケットを一連の関連データ・パケットの開始データ・パケットまたは同期データ・パケットとして識別するデータ・パケット・ヘッダ・フィールドを有するデータ・パケットが選択される、請求項８ないし１２の一項に記載の方法。
【請求項１４】
前記データ・パケットのヘッダに含まれる判定基準に基づいて、対応するキャッシュ・エントリを前記キャッシュ・メモリ（３９）に挿入するための選択が行われる、請求項８ないし１３の一項に記載の方法。
【請求項１５】
前記判定基準がアドレス情報および通信プロトコル情報を含む、請求項１４に記載の方法。
【請求項１６】
前記出力リンク情報を決定するのと同じユニットにおいて、キャッシュに入力するデータ・パケットの選択も行われる、請求項８ないし１５の一項に記載の方法。
【請求項１７】
前記キャッシュ・メモリ（３９）からキャッシュ・エントリを削除するかどうかの判断が、前記各キャッシュ・エントリが関連づけられる前記フローの形式に応じて、かつキャッシュの使用量の程度に応じて行われる、削除判断ステップ、をさらに有する、請求項８ないし１６の一項に記載の方法。
【請求項１８】
着信データ・パケットがアドレス情報に従って出力リンクに送信される装置において、キャッシュ・メモリ（３９）へのキャッシュ・エントリの挿入を制御するための機構であって、
ａ）前記各着信データ・パケットごとに、前記データ・パケットが関連づけられるフローの形式あるいは優先度、に関連する分類情報を評価する評価部（１７）と、
ｂ）前記評価ステップの結果に基づき、前記データ・パケットについて、前記キャッシュ・メモリ（３９）に前記キャッシュ・エントリを挿入すべきかどうか選択する選択部（１７）と、
ｃ）前記選択ステップの結果、前記キャッシュ・エントリを挿入すべきである場合に、前記データ・パケットについて、前記アドレス情報および関連出力リンク情報を前記キャッシュ・メモリ（３９）に前記キャッシュ・エントリとして挿入するためのキャッシュ読取り／書込みユニット（１７）と、
を有する機構。
【請求項１９】
前記キャッシュ・エントリに前記アドレス情報または関連出力リンク情報が見つかった場合、そのキャッシュ・エントリに記憶されている出力リンク情報を使用して、前記データ・パケットを転送するための出力ユニット（２９）、をさらに有する、請求項１８に記載の機構。
【請求項２０】
経路指定テーブルをさらに有する、請求項１８ないし１９に記載の機構。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各データ・パケットのヘッダに含まれるアドレス（または方向情報）に応じた、通信ネットワークにおけるデータ・パケットの経路指定に関する。詳細には、キャッシュを使用して、以前に使用したアドレスを関連する経路指定情報と一緒に記憶し、頻繁に使用されるデータ・パケット・アドレスが発生する度に、経路指定テーブルでのルックアップ（参照、照合）操作が行われることを回避する、経路指定ノードにおける大量のデータ・パケット処理に関する。例えばＣＰＵによって処理される情報単位など、どんな情報単位もデータ・パケットと見なすことができる。
【背景技術】
【０００２】
インターネットなど、データ・パケット伝送に基づく最近の通信システムでは、データ・パケット・ヘッダに含まれるアドレス情報に応じて、各交換ノード内において、入力側から複数の出力側リンクの１つに、毎秒何百万ものデータ・パケットが転送される。データ・パケット・アドレスと出力リンク（あるいは経路）との関連は、交換ノードの経路指定テーブルに記憶され、各データ・パケットごとに、出力リンク識別とも呼ばれる経路指定情報を得るために、このテーブルでルックアップまたはサーチ（検索）操作が行われる。リソースに限りがある場合は、このルックアップが遅延を引き起こすことがある。音声ストリームの周期的データ・パケット、あるいはファイル転送用データ・パケットのバーストなど、多くのデータ・パケットが同じアドレスを含むので、キャッシュ・メモリを使用して、各アドレスを、それが最初に発生したときに記憶し、また、その各関連出力または経路指定情報を、ルックアップ操作によってそれが見つかった後で記憶してきた。これによって、同じアドレスに対してルックアップ検索を何度も繰り返すことは回避されるが、それには大容量のキャッシュ・メモリが必要になる。しかし、どんなキャッシュ・メモリもそのサイズに限界があるため、キャッシュが満杯になると、新しいキャッシュ・エントリのために記憶位置をクリアしなければならない。このタスクには、しばしば、ＬＲＵ（最低使用頻度）アルゴリズムが用いられ、このようにして、明らかに一定時間使用されなかったキャッシュ・エントリが削除される。
【０００３】
しかし、キャッシュ・メモリ管理にＬＲＵアルゴリズムを用い、かつ通信システムが、音声やビデオ伝送など周期的な性質のトラフィック用に大量のデータ・パケットを転送しなければならないときは、同じ周期的伝送の連続データ・パケットの間に、多くの介在データ・パケットが生じるため、大部分のキャッシュ・エントリが、再使用される前に削除されることにもなる。言うまでもなく、これでは全く効率的でない。さらに、トラフィック・カテゴリのうちには、他のものよりも高い優先度で処理すべきものがある。したがって、処理の手間ならびに、どのみち、めったにあるいは一度しか使用しないキャッシュ・エントリのためのキャッシュ・スペースの無駄を回避するために、キャッシュ入力手順に、ある種の最適化または改善が必要になる。
【０００４】
ＩＰデータ・パケット転送システムのルータにおけるキャッシュ・メモリの使用法は、以下の文献で論じられている。Peter Newman他、「IP Switching and Gigabit Routers」、IEEE CommunicationMagazine、Vol. 35、No. 1、1997年１月、64〜69頁。この研究の結果は、毎秒１ギガビット以上の高速リンクのためにキャッシュを行うことは、アドレスに局所性を欠くために有用ではないというものであった。特定の（Ipsilon）ＩＰ交換システムを扱うという、この論文で論じられているもう１つの手法は、接続指向型のＡＴＭ（非同期転送モード）トラフィック基盤上で非接続型ＩＰトラフィックを転送することを示唆しているので、概念的に異なる。
【０００５】
データ・パケットのヘッダ内容に応じた、ＩＰ交換ノードにおけるデータ・パケットの分類については、T. V. Lakshman、D. Stiliadis、「High-speed Policy-based PacketForwarding Using Efficient Multi-dimensional Range Matching」、Proc. ACMSIGCOMM'98、Comp. Commun. Rev. Vol. 28、No. 4、1998年10月、203〜214頁、およびP. Gupta、N.McKeown、「Packet Classification on Multiple Fields」、ACM SIGCOMM'99、Comp. Commun.Rev. Vol. 29、No. 4、1999年10月、147〜160頁で論じられている。
【０００６】
これらの文献にはいずれも、非接続型データ・パケット伝送システムが、データ・パケット・ヘッダの評価に応答して、キャッシュ・メモリに入力するための特定のフローやトラフィック・カテゴリを選択して、その同じフローやトラフィック・カテゴリのデータ・パケットに対する後刻のルックアップ操作を回避し、一方で、キャッシュへの不要なキャッシュ・エントリの作成は回避するような手順は、示唆されていない。
【非特許文献１】Peter Newman他、「IP Switching andGigabit Routers」、IEEE Communication Magazine、Vol. 35、No. 1、1997年１月、64〜69頁
【非特許文献２】T. V. Lakshman、D. Stiliadis、「High-speedPolicy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching」、Proc.ACM SIGCOMM'98、Comp. Commun. Rev. Vol. 28、No. 4、1998年10月、203〜214頁
【非特許文献３】P. Gupta、N. McKeown、「PacketClassification on Multiple Fields」、ACM SIGCOMM'99、Comp. Commun. Rev. Vol. 29、No.4、1999年10月、147〜160頁
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明の目的は、キャッシュ・メモリの使用法を改善することである。
【０００８】
これは、交換ノードのデータ・パケット処理装置またはルータにおいて、特に有利である。特に、他のものよりも高い確率で使用されるキャッシュ・エントリ、あるいは、他のものよりも経路指定テーブル・ルックアップによる時間遅延の影響をより多く受けるトラフィック形式用のキャッシュ・エントリ、に特権を与えたり優先したりする事で、例えば周期的トラフィック等に対する（後続の）他のキャッシュ・エントリに有利なようにすることが必要である。
【課題を解決するための手段】
【０００９】
着信データ・パケットが、アドレス情報に応じて出力リンクに送信される、キャッシュ・メモリへのキャッシュ・エントリ挿入方法を提案する。この方法は、
ａ）各着信データ・パケットごとに、そのデータ・パケットが関連づけられる、トラフィック・フローの形式やトラフィックの優先度、に関連する分類情報の評価を行う評価ステップと、
ｂ）評価ステップの結果に基づき、そのデータ・パケットについて、キャッシュ・メモリにキャッシュ・エントリを挿入すべきかどうか選択する選択ステップと、
ｃ）選択ステップの結果、キャッシュ・エントリを挿入すべきであるとされる場合、そのデータ・パケットについて、アドレス情報および関連出力リンク情報を、キャッシュ・メモリにキャッシュ・エントリとして挿入する入力ステップと、
を有する。
【００１０】
この方法により、例えば、同じフローの連続する２つのデータ・パケット間に多数のデータ・パケットがあって、多かれ少なかれ、時間的に均一に分布し、または等間隔に配置されているトラフィック・フローに対して、データ・パケット・エントリ数ではなく、データ・パケット着信レートで測定して、同じデータ・パケット・フローの追加データ・パケットが、比較的短期間のうちに続いて発生すると予測できる場合は、そうしたデータ・パケット・フローのキャッシュ・エントリを保持することが可能になる。しかしそれでも尚、この機構を用いれば、高い優先を持つとして特に認識される周期的データ・パケット・フローを、キャッシュに入れるために選択することができる。
【００１１】
したがって、本発明の使用には以下の利点がある。キャッシュ・エントリを、将来のキャッシュ・ヒットの確率が高い候補、すなわちトラフィック・フロー、に限定することができるので、キャッシュ・サイズを通常のキャッシュ入力手順によるのものより小さくすることができる。どうしても通常のルックアップ手順を必要とする、周期的な、あるいは時折のこともある、伝送を伴うトラフィックは、それらのキャッシュ・エントリが、同じフローのデータ・パケットが２つ発生する合間に削除されるため、キャッシュ・メモリ・スペースおよびキャッシュ・エントリを処理するユニットの負担にならない。
【００１２】
本発明は、データ・パケット・ヘッダに含まれるアドレス情報に応じて、データ・パケットが、交換ノードまたはルータ内で入力側から複数の出力側リンクの１つに転送される、データ・パケット伝送に基づく通信システムにおいて、特に有用となり得る。データ・パケット・アドレスと出力リンクあるいは経路との関連は、交換ノードの経路指定テーブルに記憶され、各データ・パケットごとに、出力リンク情報とも呼ばれる経路指定情報を得るために、このテーブルでルックアップまたはサーチ操作が行われる。通常は、あるデータ・パケット・フローを共に形成する各データ・パケットが、キャッシュ・メモリにそのためのキャッシュ・エントリを挿入するために選択される。
【００１３】
この概念は、データ・パケット伝送システムに限らず、異なる頻度または緊急度で、異なるユーザがデータベースにアクセスするシステムなど、サーチ機構へのアクセスが繰り返し実施される他のシステムで使用したり、あるいはそれに適合させたりすることができる。コンピュータ・システムでは、例えば、ブランチ・スルー・テーブルとの関連で本発明を有利に適用することもできるデータ・キャッシュもまた存在し、そのデータは、同じデータがすぐに続けてアクセスされる見込みがないため、キャッシュ・メモリにキャッシュ・エントリとして挿入すべきではないが、プログラム用の頻繁に使用される変数がキャッシュ入力を推奨する対象となることになる。
【００１４】
以下で、本発明の実施形態を、添付の図面を参照して説明する。
【発明を実施するための最良の形態】
【００１５】
ネットワーク・プロセッサ
図１に、通信システムのノード内のネットワーク・プロセッサを概略的に示す。ここで、プロトコル・データ・ユニットまたはＰＤＵとも呼ばれる、着信データ・パケットのヘッダを解析して、各データ・パケットを複数の出力ポートの１つに送るか、あるいは、現行ポリシー（運用規定）で必要とされる場合は、それを止めることができるようにする。
【００１６】
バス１１上でデータ・パケットのストリームを受信し、各データ・パケットをＰＤＵパイプライン１３に入れて、ヘッダ評価ステップ用の時間を確保する。各データ・パケット・ヘッダは、入力１５を介してヘッダ・パーサ１７に入力され、そこで、ヘッダから、宛先アドレス、優先度、サービスのクラスなど、分類情報とも呼ばれる関連情報を抽出し、接続２１を介して、それをルックアップ・エンジン１９に転送する。ルックアップ・エンジン１９は、経路指定テーブルまたはルール・テーブルとも呼ばれるルックアップ・テーブルを備え、そこに、各宛先アドレスなどに対する、ノードの各ポート（目標ポート）およびその他の処理情報を記憶する。この経路指定テーブルを使用して、ルックアップ・ステップを実施する。ルックアップの結果は、線２３、ポリサ２５および線２７を介して、切り換えユニット２９に転送され、そこで、パイプライン１３からデータ・パケットを受信し、ルックアップ・エンジン１９およびポリサ２５から受信した経路指定情報に応答して、各データ・パケットを、接続３１を介して正しい目標ポートに送信する。ポリサ２５は、それが記憶するポリシーに応じて、ルックアップ・エンジン１９から得られる出力リンク情報を切り換えユニット２９に送信することもでき、あるいは、ポリシーが必要とする場合は、データ・パケット（ＰＤＵ）のさらなる転送を止めることができるように、ＮＯ−ＧＯ信号を送信することもできる。
【００１７】
また、データ・パケットを、線３３を介してＰＣＩインタフェース３５に転送し、さらに接続３７を介して、特殊処理用制御プロセッサ（図示せず）に配送することができる。
【００１８】
ルックアップ操作に使用される時間を節約するために、キャッシュ・メモリ３９を設け、そこに目標ポートＩＤなど、以前のルックアップ操作で見つかった出力情報を、入力（宛先アドレス）と一緒に記憶する。宛先アドレスまたはその他の関連入力情報が線２１上に現れると、その情報はキャッシュ・メモリ３９にも転送される。また、その情報がキャッシュ・メモリ３９で見つかった場合は、各出力情報が、線４１を介してルックアップ・エンジン１９に転送され、次いで、ルックアップ・エンジン１９は、ルックアップ操作を停止し、この出力情報を線２３上に乗せ、ポリサ２５および切り換えユニット２９に転送することができる。宛先アドレスがキャッシュ・メモリ３９にまだ記憶されていなかった場合は、サーチ操作で見つかった対応する出力情報を、線４３を介してルックアップ・エンジン１９から受け取り、キャッシュ・メモリ３９に両方を記憶することができる。
【００１９】
キャッシュ・メモリ３９は、サイズに限界があるので、一定時間が経過すると満杯になることもあり、新しいキャッシュ・エントリを記憶できるように古いキャッシュ・エントリを取り消す必要がある。公知のＬＲＵ（最低使用頻度）アルゴリズムを用いて、取り消すべきキャッシュ・エントリの選択を行うことができる。しかし、背景技術でも述べたように、ＬＲＵアルゴリズムが不適切な手順であることもある。すなわち、周期的伝送の場合、同じフローの連続する２つのデータ・パケット間には多くの介在データ・パケットが存在するため、キャッシュ・メモリ３９の多くのキャッシュ・エントリが、再利用される前に取り消されることになる。したがって、キャッシュ・メモリ３９空間の利用を最適化するための別の解決法を導入する。
【００２０】
キャッシュを行うための選択手順
キャッシュ・エントリは、例えば、優先度の高いデータ・パケット、あるいは、その後に同一アドレスを持つデータ・パケットが続くことが予想されることを暗示するフローの開始の識別子（例えばＴＣＰ−ＳＹＮ）といった、別の判定基準を有するデータ・パケットなど、選択ステップで選択されるデータ・パケットに対して作成される。そうした意味で相互にグループを形成する、１群のデータ・パケットを、データ・パケット・フローと呼ぶ。この選択ステップは、第１の実施形態について図２に示すように、各信号を、線２１を介してキャッシュ・メモリ３９およびルックアップ・エンジン１９に送信することを行うヘッダ・パーサ１７によって実施することができる。第２の実施形態について図３に示す別の解決法は、ルックアップ・エンジン１９のルックアップ操作の結果に応じての選択を行い、次いで、ルックアップ・エンジンが、各選択信号を線４３を介してキャッシュ・メモリ３９に送信するものである。この第２の方式が使用されるのは、例えば、データ・パケットの優先度をデータ・パケット・ヘッダから明示的に推定することができないが、それが、データ・パケット分類処理中に判定される場合である。評価と選択からなる、キャッシュ入力判断の第３の実施形態を図４に示す。ヘッダ・パーサ１７は、評価ステップでデータ・パケット・ヘッダを評価し、ＴＣＰ（大量）伝送の先頭または末尾を検出する。その先頭または末尾が検出された場合、その結果を使って、あるデータ・パケットについて、キャッシュ・エントリを挿入すべきかどうか判定する。
【００２１】
この選択機構を使用した操作は以下のとおりである。
各着信データ・パケットのヘッダがヘッダ・パーサ１７に入力される。宛先アドレスなどの関連情報がキャッシュ・メモリ３９およびルックアップ・エンジン１９に転送され、両者が並列にそれぞれの操作を開始し、必要な出力情報（目標ポート選択）を検索する。検査ステップでは、そのデータ・パケットのアドレス情報または関連出力リンク情報が、キャッシュ・メモリ３９にすでに含まれているかどうか検査する。
【００２２】
ヘッダ・パーサ１７またはルックアップ・エンジン１９はまた、受信情報を評価して、対応するデータ・パケット（ＰＤＵ）が、キャッシュ・メモリ３９にエントリを挿入するに値するカテゴリあるいはデータ・フローのものであるかどうか判定する。これが、評価および選択ステップである。
【００２３】
（ａ）検査ステップ中にキャッシュ・メモリ３９内に入力および対応する出力情報が見つかった場合は、ルックアップ・エンジン１９の操作を停止する。次いで、この結果を、線４１に乗せ、ルックアップ・エンジン１９およびポリサ２５を介して、切り換えユニット２９に転送する。データ・パケットは、見つかった出力情報を使って、転送ステップで転送される。
【００２４】
（ｂ）キャッシュ・メモリ３９内に入力情報が見つからなかった場合、ルックアップ・エンジン１９は、そのルックアップ・ステップを完了し、また、このルックアップ・ステップの結果（目標ポートの識別）を、ポリサ２５を介して切り換えユニット２９に転送するのに加え、線４３を介してキャッシュ・メモリ３９にも提供する。キャッシュ・メモリ３９は、ヘッダ・パーサ１７からあるいはルックアップ・エンジン１９からそれぞれ線２１または線４３で選択信号を受信した場合に限り、入力ステップで、入力情報（宛先アドレス）および対応する出力リンク情報（目標ポートＩＤ）をキャッシュ・エントリに記憶する。
【００２５】
各種キャッシュ入力選択ステップの詳細
キャッシュ・エントリを挿入するための選択の判断は、アドレス情報や、適用される通信プロトコルに関する通信プロトコル情報など、様々な判定基準に基づくことができる。以下に、受信データ・パケット（ＰＤＵ）の優先度か、あるいは大量（グループ）のデータ・パケット伝送の指示かのどちらかに基づく選択について、３つの例を示す。ある例では、データ・パケット優先度が、データ・パケット・ヘッダ中に直接指示される。別の例では、ヘッダ内容から導き出される間接的優先度指示がある。第３の例では、ＴＣＰ伝送の最初と最後のデータ・パケットの指示が、選択基準として使用される。
【００２６】
１）明示的優先度コード化に基づくキャッシュ入力選択
図２はデータ・パケットのヘッダを示しており、その中で、（ａ）キャッシュ入力の判断を行うための判定基準として評価される部分、および（ｂ）ルックアップ操作のための入力値として使用される部分をマークしてある。これらの部分は分類情報を表しており、この情報によって、データ・パケットを評価することや、それがキャッシュ・エントリを挿入する対象のデータ・パケットに属するかどうか分類することが可能になる。判定基準は、各データ・パケットの優先度と、同じデータ・フローに含まれる他のすべてのデータ・パケットの優先度とを、明示的にコード化したものである。この判定基準は、ＤｉｆｆＳｅｒｖ  ＤＳＣＰビットあるいはＶＬＡＮ優先度ビットのどちらでもよい。ヘッダ・パーサ１７は、これらのビットを評価し、その結果に応じて、ルックアップ・エンジン１９およびキャッシュ・メモリ３９に、サーチ結果をキャッシュに入れるべきかどうか知らせる。
【００２７】
ヘッダからの宛先アドレスは、ヘッダ・パーサ１７によって抽出されてルックアップ・エンジン１９に転送され、次いで、ルックアップ・エンジン１９が、その（ＩＰｖ４）経路指定テーブルで、最長マッチング接頭部サーチを行い、線２３、４３上のその出力に各出力値（目標ポートの識別）を提供する。ルックアップ・エンジン１９は次いで、宛先アドレスとサーチ結果（目標ポートおよび場合によってはキュー優先度）のキャッシュ・メモリ３９への入力を始動させる。しかし、各宛先アドレスがすでにキャッシュ・メモリ３９で見つかっている場合は、ルックアップ操作は打ち切られているはずであり、出力結果、すなわち目標ポートなどが、線４１を介してルックアップ・エンジン１９に提供され、そこから線２３およびポリサ２５を経て切り換えユニット２９に転送されることになる。
【００２８】
この例では、ヘッダ・パーサ１７が、明示的優先度指示に基づいてキャッシュ入力の判断を行い、ルックアップ・エンジン１９は、必要な目標ポートの識別（および場合によっては割り当てられた優先度の値）を得るために、最長マッチング接頭部サーチを行うだけである。
【００２９】
２）暗示的優先度コード化に基づくキャッシュ入力選択
図３もまた、データ・パケット（ＰＤＵ）・ヘッダを示し、その中で、評価に使用される、その他のフィールドをマーク、すなわち陰影を施してある。それは、（ａ）プロトコル標識、（ｂ）ソース・アドレス、（ｃ）宛先アドレス、（ｄ）ソース・ポート、および（ｅ）宛先ポートから成る５個組の要素である。これらの値は、ヘッダ・パーサ１７によって抽出され、ルックアップ・エンジン１９に提供される。ルックアップ・エンジン１９は、その一例を本明細書の最後の表１に示してある、ルール・テーブルを含んでおり、それによって、プロトコル／アドレスの５個組の要素を基準とした分類を行うことができる。ルール・テーブルでのサーチ、すなわちルックアップの結果、２つの値が提供される。その１つは、（１）各データ・パケットの優先度を決定する分類（高／低／否認）である。この優先度の値が切り換えユニット２９に提供される。これにより、例えば、優先度が高の場合にのみキャッシュ・エントリを作成するなど、キャッシュ・メモリ３９にキャッシュ・エントリを作成する必要があるかどうかも決定される。ルール・テーブルでのルックアップでさらに、（２）各データ・パケットに使用される目標ポートの識別も提供される。
【００３０】
あるデータ・パケットについて、キャッシュ・メモリ３９にキャッシュ・エントリを作成する場合、このエントリは、ヘッダから抽出された５個組の要素と、その分類結果および目標ポート識別とを含む。第１の例の場合と同様に、キャッシュ・メモリ３９がすでに、それぞれの５個組の要素を含んでいた場合は、ルックアップ・エンジン１９でのサーチが打ち切られ、優先度の値および宛先ポートＩＤが、ルックアップ・エンジン１９およびポリサ２５を介して、キャッシュ・メモリ３９から切り換えユニット２９に転送される。
【００３１】
したがって、この第２の例では、ヘッダ・パーサ１７は、データ・パケット・ヘッダから関連する５つのフィールドを抽出するに過ぎないが、ルックアップ・エンジン１９は、必要な目標ポートを検索する他に、キャッシュ入力の判断も行う。
【００３２】
３）キャッシュ入力選択のその他の判断原則
本発明の応用範囲は、もちろん、上記２つの例で与えられる場合に限られるものではない。例えば、ＭＰＬＳラベル、ＡＴＭ  ＵＰＩ／ＶＣＩラベル、イーサネット（Ｒ）ＭＡＣアドレスなど、データ・パケットのトラフィックやフロー・カテゴリ、あるいはその優先度を反映する、どのような単一のヘッダ・フィールドまたはヘッダ・フィールドの組合せも、判定基準として使用することができる。
【００３３】
以下では、図４を参照して、第３の実施形態の例において、キャッシュに入力するデータ・パケット・フローを選択する、すなわち、キャッシュ・メモリ３９にデータ・パケット・アドレスおよび出力ポート情報を入力するための、もう１つの選択肢について説明する。各局面は、ほぼ連続して、あるいは少なくとも個々のデータ・パケットの間に比較的短い間隔を置いて、同じフローのいくつかのデータ・パケットが着信すると予想できる場合である（同じフローのデータ・パケットの局所性あるいはバースト性）。そうした状況または条件は、例えば、個々のデータ・パケット・ヘッダから以下のようにして引き出すことができる（図４参照）。ＴＣＰ伝送は、通常、送信端末と受信端末の間でシーケンス番号を同期させる、いわゆるＳＹＮメッセージで始まる。ＳＹＮメッセージは、ＴＣＰヘッダ中で設定される（図４でＳＹＮとマークしてある）特定の制御ビットによって認識され、したがって、解析や検出が容易である。ヘッダ・パーサ１７（図１参照）が、キャッシュ・メモリ３９にキャッシュ入力制御信号を送信し、次いで、ＳＹＮメッセージの宛先ポート・アドレス、ならびに、そのＳＹＮメッセージに対するルックアップ操作によって得られる、アドレス情報とも呼ばれる出力リンク情報が、キャッシュ・メモリ３９に入力されることになる。後続のデータ・パケットが同じアドレス情報付きで着信する確率が高いので、大量伝送の各後続データ・パケットについて、出力リンク情報をキャッシュ・メモリ３９から直接取り出すことができる。したがって、これは、データ・パケットのバースト型トラフィックに適用される。
【００３４】
また、以下で説明するように、この同じ方式を適用して、キャッシュ・メモリ３９からそれぞれのキャッシュ・エントリを明示的に除去し、新しいキャッシュ・エントリ用に相当する空間を解放することができる。キャッシュ・メモリ３９へのキャッシュ・エントリの挿入を制御する装置は、そこから着信データ・パケットがアドレス情報に従って出力リンクに送られるので、それ故、以下の３つの機能を統合したヘッダ・パーサ１７を有する。それらは、ａ）各着信データ・パケットごとに、そのデータ・パケットが関連付けられるフローの形式や優先度に関連する分類情報を評価する評価部と、ｂ）評価ステップの結果に基づき、そのデータ・パケットについて、キャッシュ・エントリをキャッシュ・メモリ３９に挿入すべきかどうか選択する選択部と、ｃ）選択ステップの結果、キャッシュ・エントリを挿入すべきであるとされる場合に、そのデータ・パケットについて、アドレス情報および関連出力リンク情報を、キャッシュ・メモリ３９にそのキャッシュ・エントリとして挿入する、キャッシュ読取り／書込みユニットである。必ずしもこれらの機能をすべて統合する必要はなく、別個のユニットによって実施することもできる。ここでの装置は、アドレス情報または関連出力リンク情報がキャッシュ・エントリ中で見つかった場合に、そのキャッシュ・エントリに記憶されている出力リンク情報を使用してデータ・パケットを転送する、出力ユニット２９を更に備える。
【００３５】
キャッシュ・メモリからのエントリの削除
前述の方法が使用された場合でも、キャッシュ・メモリ３９は結局は満杯になることもあり、別のキャッシュ・エントリを挿入できるようにするには、事前にキャッシュ・メモリ３９からキャッシュ・エントリを削除して、記憶位置をクリアしなければならない。キャッシュ・エントリ削除のルールは、用いられるキャッシュ入力決定機構とは独立とすることができるが、同じ選択方式を使用することもまた可能である。キャッシュ位置のクリアには、もちろん、ＬＲＵルールを使用することができる。
【００３６】
（ＴＣＰ大量データ・パケット伝送のための）前述の第３の選択の例におけるキャッシュ入力決定機構に関連して、キャッシュ位置のクリアに有利だとして示唆されているもう１つの機構は以下のようなものである（図４も参照）。
【００３７】
あるＴＣＰセッションの最後のデータ・パケットには、ＴＣＰヘッダ中に（図４にマークしてある）ＦＩＮ制御ビットが設定されている。このＦＩＮメッセージは、ヘッダ・パーサ１７（図１）での解析や検出が簡単であり、ヘッダ・パーサ１７は、ＴＣＰ  ＦＩＮメッセージで見つかったものと同じ宛先ポート・アドレスをもつ、キャッシュ・メモリ３９中の各キャッシュ・エントリを削除するための制御信号を送信する。このアドレスをもつデータ・パケットがそれ以上着信しないと予想されるからである。
【００３８】
得られる利点の要約
すでに背景技術で簡単に述べたように、アドレス指定されたデータ・パケットを様々な宛先に送信する通信システムにおいて、前述した方法を使用するときに得られる主要な利点は、以下のとおりである。
【００３９】
データ・パケットの時間的局所性が高かったり、あるいは特定の優先度を有していたり、あるいはその他の選択可能な判定基準を有していたりするデータ・パケット・フローでは、キャッシュ・メモリにキャッシュ・エントリが挿入される。これにより、通常の、すなわち、非選択キャッシュ入力機構を使用する他のシステムと比べて、交換ノードにおけるデータ・パケット伝送の操作が高速化することになるのと同時に、キャッシュ・メモリのサイズを、標準のキャッシュ入力を使用するシステムに通常必要とされるものよりも、確実に小さくすることができる。
【実施例１】
【００４０】
【表１】
0004410467.tif 000002
【図面の簡単な説明】
【００４１】
【図１】経路指定テーブルでルックアップ操作を実施するためのルックアップ・エンジンおよびＩＰ交換ユニット、ならびにデータ・パケット・ヘッダ・パーサおよびキャッシュ・メモリを備え、ヘッダ・パーサおよびルックアップ・エンジンが協働して、キャッシュに入力するための特定フローのアドレスおよび出力リンク情報を選択する、交換ノードまたはルータ内の受信ネットワーク・プロセッサの構成図である。
【図２】優先度が明示的に指示されるときにキャッシュ入力決定を行うヘッダ・パーサの動作を概略的に表す、データ・パケット・ヘッダを示す図である。
【図３】優先度が明示的にコード化される場合にキャッシュ入力決定を行うための、経路指定テーブルを含むルックアップ・エンジン１９のヘッダ・パーサと連動しての動作を、概略的に表す、データ・パケット・ヘッダを示す図である。
【図４】ＴＣＰデータ・フローにおいて、そのフローについてのキャッシュ入力の決定を行うための大量データ・パケット転送のデータ・パケット・ヘッダであり、データ・パケット・グループの先頭と末尾がＳＹＮおよびＦＩＮ表示から推定可能である、データ・パケット・ヘッダを示す図である。
【符号の説明】
【００４２】
１１  バス
１３  ＰＤＵパイプライン
１５  入力
１７  ヘッダ・パーサ
１９  ルックアップ・エンジン
２１  接続
２３  線
２５  ポリサ
２７  線
２９  切り換えユニット
３１  接続
３３  線
３５  ＰＣＩインタフェース
３９  キャッシュ・メモリ
４１  線
【図１】
0004410467.tif 000003
【図２】
0004410467.tif 000004
【図３】
0004410467.tif 000005
【図４】
0004410467.tif 000006