(57)【特許請求の範囲】
【請求項１】
プロセッサ内に受信される複数のパケットの各々に対して複数のパケットフロー識別子のうちの対応するものを識別するための分類回路と、
該分類回路に接続された制御回路と、
該制御回路に接続され、各々がそれと関連する少なくとも１つの実行エンジンを有する複数の動作ユニットとを備えるプロセッサであって、
該制御回路は、ある与えられたパケットフロー識別子を有する複数のパケットを、ある所望のファンクション呼の順序が該与えられたパケットフロー識別子を有する該複数のパケットの期間を通じて該プロセッサ内の複数の順序依存処理タスクに対して維持されるようなやり方にて、該少なくとも１つの動作ユニットに向けるよう動作し、
該制御回路は、順序論理から成り、この順序論理は、
各々が指定されたセットのファンクションについて該所望のファンクション呼の順序を維持するために、コンテクスト識別子をそれぞれのファンクション呼識別子と関連づけて記憶する複数の順序キューと、
該複数の順序キューのそれぞれのものと関連したそれぞれのセットのファンクションを識別する情報を記憶する複数の構成レジスタと、から成るものであることを特徴とするプロセッサ。
【請求項２】
１つ或いは複数の該パケットフロー識別子の各々が該プロセッサと関連するメモリ回路内の一意のメモリ位置に対応する請求項１記載のプロセッサ。
【請求項３】
ある与えられたパケットフロー識別子に対応する該一意のメモリ位置が少なくとも関連するパケットフローに対して遂行される複数のファンクションを指定するカウンタを格納する請求項２記載のプロセッサ。
【請求項４】
該制御回路がある特定の順序依存処理タスクと関連する一つより多くのファンクションがある特定の処理期間中に該同一のパケットフロー識別子を有する複数のパケットに関して遂行されているか否かを決定する請求項１記載のプロセッサ。
【請求項５】
ある特定の順序依存処理タスクと関連する一つよりも多くのファンクションがある特定の処理期間中に該同一のパケットフロー識別子を有する複数のパケットに関して遂行されているときは、該制御回路が該所望のファンクション呼の順序を該特定の順序依存処理タスクに対して維持する請求項４記載のプロセッサ。
【請求項６】
ある特定の順序依存処理タスクと関連する一つよりも多くのファンクションがある特定の処理期間中に該同一のパケットフロー識別子を有する複数のパケットに関して遂行されてないときは、該制御回路がファンクション呼の任意な順序を該特定の順序依存処理タスクに対して許す請求項４記載のプロセッサ。
【請求項７】
該受信されたパケットの各々に、そのパケットに対してファンクション呼を発行する前に、該プロセッサ内でコンテクスト識別子が割当てられる請求項１記載のプロセッサ。
【請求項８】
該同一のパケットフロー識別子を有するある与えられたセットのパケットに異なるコンテクスト識別子が割当てられる請求項７記載のプロセッサ。
【請求項９】
該受信されたパケットに割当てられたコンテクスト識別子が該所望のファンクション呼の順序をある特定のパケットフロー識別子と関連する該受信されたパケットに対して維持するために用いられる請求項７記載のプロセッサ。
【請求項１０】
プロセッサ内でパケットを処理する際に用いるための方法であって、
該プロセッサ内に受信される複数のパケットの各々に対して複数のパケットフロー識別子のうちの対応するものを識別するステップと、
ある与えられたパケットフロー識別子を有する一つ或いは複数のパケットを、ある所望のファンクション呼の順序が該与えられたパケットフロー識別子を有する該１つ或いは複数のパケットの期間を通じて該プロセッサ内の一つ或いは複数の順序依存処理タスクに対して維持されるようなやり方にて、該プロセッサの複数の動作ユニットであって、各々がそれと関連する少なくとも１つの実行エンジンを有する複数の動作ユニットに向けるステップと、を含み、
指定されたセットのファンクションについて該所望のファンクション呼の順序を維持するために、複数の順序キューの各々が、コンテクスト識別子をそれぞれのファンクション呼識別子と関連づけて記憶し、および複数の構成レジスタが該複数の順序キューのそれぞれのものと関連したそれぞれのセットのファンクションを指定する情報を記憶するようになっている、ことを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般的にはパケット処理システム、より詳細には、このようなシステム内でパケットルーティング、パケットスイッチング及び他のパケット処理動作を遂行する際に用いるように構成された網プロセッサ或いは他のタイプのプロセッサに関する。
【０００２】
【従来の技術】
網プロセッサは一般には物理伝送媒体、例えば非同期転送モード（ＡＴＭ）網或いは同期光網（ＳＯＮＥＴ）等の物理層部分と、ルータ或いは他のタイプのパケットスイッチ内のスイッチファブリックとの間のパケットのフローを制御する。これらルータ及びスイッチは一般には複数の網プロセッサを含み、例えば、ライン或いはポートカードのアレイの形式に構成され、これらプロセッサの一つ或いは複数が各カードと関連する。
【０００３】
網プロセッサにおいては、入り或いは出パケットに対して適当な処理順序を維持することが重要となる。例えば、網プロセッサ内での多くの処理タスクは、ある与えられた動作の結果が後続動作を正常に実行するために必要となるという意味において順序依存タスクである。このような動作は典型的にはプロセッサの一つ或いは複数の動作ユニットに向けてファンクション呼（function calls）を発行することで開始される。ある与えられた動作ユニットは、一つの実施例においては、複数の実行ユニットを含み、各実行ユニットがその動作ユニットに対して複数の動作を実行する能力を有する。動作ユニットの一つのタイプとして、このような動作に対するリクエストに応答して特定の計算動作を遂行する計算ユニットがある。
【０００４】
網プロセッサ内で所望のファンクション呼の順序を維持するための従来の技法には、ファンクション呼の発行をシリアル化するアプローチや、単一の実行ユニットのみを伴うスカラーアプローチがある。
【０００５】
シリアル化アプローチにおいては、異なる動作ユニットに向けてのファンクション呼は、ある指定されるファンクション呼シーケンス（順序）に従ってシリアルに送出される。換言すれば、ある適当なファンクション呼シーケンスが決定され、ファンクション呼はその所望のシーケンスが維持されるようなやり方にてシリアルに送出される。別のファンクション呼からの結果を必要とするあるファンクション呼は、単に、その結果が入手されるのを待った上で、ある特定の動作ユニットに向けて送出される。このアプローチでは、複数の動作ユニットを用いることで並列性（parallelism）の長所をある程度は維持できるが、ただし、このような並列性を網プロセッサのスループットを増加するために完全に活用することには失敗する。
【０００６】
スカラーアプローチは、正しい処理順序を維持する問題を、単一の動作ユニットのみを利用することで克服する。このアプローチではたしかに正しい処理順序を確保することはできるが、ただし、このアプローチでは並列性によって達成でき得る利得が完全に排除されるために網プロセッサのスループットが著しく大きく制限される。
【０００７】
【発明が解決しようとする課題】
こうして、上述の従来のアプローチは両方とも、網プロセッサの最大限のスループットを達成することに失敗するという意味において欠陥を有する。これら欠陥は高データ速度、例えば、２．５ギガビット／秒（Gbps）以上のデータ速度においては富に顕著となる。
【０００８】
従って、網プロセッサ或いは他のタイプのプロセッサ内において所望のファンクション呼の順序を順序依存処理タスクに対して維持し、プロセッサのユニット間での並列性をより効率的に活用することでプロセッサのスループットを増加するための改善された技法に対する必要性が存在する。
【０００９】
【課題を解決するための手段】
本発明は、所望のファンクション呼の順序を、一つ或いは複数の動作ユニットを備える網プロセッサ或いは他のプロセッサ内でのパケットの処理のために維持するための改善された技法を提供する。
【００１０】
本発明の一面によると、パケット処理順序維持機能を有するプロセッサは、プロセッサ内に受信される複数のパケットの各々に対して対応するパケットフロー識別子を識別する分類回路、この分類回路に接続された制御回路、及びこの制御回路に接続された少なくとも一つの動作ユニットを含む。制御ユニットは、ある与えられたパケットフロー識別子を有する一つ或いは複数のパケットを、ある所望のファンクション呼の順序がその与えられたパケットフロー識別子を有する１つ或いは複数のパケットの期間を通じてプロセッサ内の一つ或いは複数の順序依存処理タスクに対して維持されるようなやり方にて動作ユニットに向ける。
【００１１】
本発明のもう一面によると、１つ或いは複数のパケットフロー識別子の各々はプロセッサと関連するメモリ回路内の一意のメモリ位置に対応する。ある与えられたパケットフロー識別子に対応するこの一意のメモリ位置は少なくとも関連するパケットフローに対して遂行される複数のファンクションを指定するカウンタを格納する。
【００１２】
本発明のもう一面によると、受信されたパケットの各々には、そのパケットに対してファンクション呼を発行する前に、プロセッサ内でコンテクスト識別子を割当てられる。
【００１３】
これらコンテクスト識別子は、一つの実施例においては、固定された数のトークン、例えば、２５６個のトークンから選択され、コンテクスト識別子は８−ビット識別子から成る。受信されたパケットに割当てられるこれらコンテクスト識別子は、所望のファンクション呼の順序をある特定のパケットフロー識別子と関連する受信された複数のパケットに対して維持するために用いられる。
【００１４】
長所として、本発明は、プロセッサの複数の動作ユニットを用いることで得ることが可能な並列性をより良く活用することでプロセッサのスループットを改善することができる。
【００１５】
【発明の実施の形態】
本発明は、ここでは特定のやり方に構成された網プロセッサを含む一例としてのパケット処理システムとの関連で説明される。ただし、本発明は、より一般的に、プロセッサの１つ或いは複数の動作ユニット内である特定のパケット処理順序を維持することが要請されるあらゆるプロセッサに適用できることに注意する。
【００１６】
ここで「プロセッサ（processor）」なる用語にて表現される物は、一例として、これらに制限されるものではないが、マイクロプロセッサ、中央処理ユニット（ＣＰＵ）、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、或いは他のタイプのデータ処理デバイス、並びにこれら及び他のデバイスの一部或いは組合せを用いて実現することができる。
【００１７】
ここで用いられる「分類回路（classification circuitry）」なる用語は、あるパケット或いはパケットの一部に関して少なくとも一つの分類動作（classification operation）の少なくとも一部を遂行する能力を有する、プロセッサ或いは他のタイプの処理回路のあらゆる部分を含むことを意図される。分類動作の例としては、これらに制限されるものではないが、プレ分類（preclassification）、再アセンブリ（reassembly）、優先順序付け（prioritization）、統計量の収集（statistics gathering）、スケジューリング、トラフィック管理、等が含まれる。より具体的な例として、以下に説明する本発明の一つの実施例は、第一のパス分類（pass classification）を遂行するように構成された第一の分類回路、例えば、プレ分類器（preclassifier）或いは他の第一のパス分類器と、第二のパス分類を遂行するように構成された第二の分類回路、例えば、第二のパス分類器を含む。第一のパス分類は、この実施例においては、大雑把に、パケット再アセンブリ動作の少なくとも一部を含み、第二のパス分類は、この実施例においては、大雑把に、スケジューリング或いはトラフィック管理動作の少なくとも一部を含む。第一と第二の分類回路は、各々、例えば、一つ或いは複数の別個の分類エンジン（classification engines）、単一の分類エンジンの異なる部分、或いはここに説明される処理動作の少なくとも一部分を提供するように構成された回路の他の構成を表す。
【００１８】
本発明は、一つの実施例においては、パケット処理システムのプロセッサスループットを、そのプロセッサの一つ或いは複数の動作ユニット内でのパケット処理の順序を、パケットフロー識別子を用いて維持することで改善する。
【００１９】
図１は内部に本発明がその内部に実現されるパケット処理システム１００を示す。システム１００は、内部メモリ１０４を有する網プロセッサ１０２を含む。網プロセッサ１０２は図示されるように外部メモリ１０６に接続され、これは網１０８とスイッチファブリック１１０との間で、セル、パケット或いは他のパケットデータをやり取りするためのインタフェースを提供するように構成される。プロセッサ１０２及びこれと関連する外部メモリ１０６は、例えば、ルータ或いはスイッチのラインカード或いはポートカード上に搭載された、一つ或いは複数の集積回路として実現される。このような構成においては、スイッチファブリック１１０は、通常、ルータ或いはスイッチの一部とみなされる。
【００２０】
図１に示すシステム要素の特定の構成は、単に例示に過ぎないことに注意する。より具体的には、前述のように、本発明はあらゆるタイプのパケットプロセッサ内に実現することができ、ある特定のパケット処理用途に制限されるものではない。
【００２１】
図２は図１の網プロセッサ１０２をより詳細に示す。網プロセッサ１０２は、この実施例においては、網１０８或いはスイッチファブリック１１０から入りデータパケットを受信する第一のパス分類器２００を含む。この第一のパス分類器２００はメモリ２０４と第二のパス分類器２０２に接続される。メモリ２０４は、内部メモリ１０４の少なくとも一部から成ることも、外部メモリ１０６から成ることも、或いはこれらの両方から成ることも考え得る。第二のパス分類器２０２もメモリ２０４に接続される。第二のパス分類器２０２の出力は後続処理回路に送られ、これには、例えば、スケジューリング回路、キューイング回路、ディスパッチ（発行）回路等が含まれる。
【００２２】
網プロセッサ１０２は、更に、第一のパスコンテクスト割当て要素（pass context assignment element）２０６、キューエンジン２０８、順序論理（ordering logic）２１０、第二のパスコンテクスト割当て要素２１２、及び第二のパスレディキュー（pass ready queue）２１４を含む。少なくとも第一のパス分類器２００と第二のパス分類器２０２は、これら要素とＮ個の動作ユニット２２２−１，２２２−２，．．．２２２−Ｎとの間のインタフェースを提供するファンクションバス（function bus）２２０に接続される。各動作ユニット２２２−ｉ（ここでｉ＝１，２，．．．Ｎ）とは、この実施例においては、複数の実行エンジン（ＥＥ）２２５−ｉ，ｊ（ここでｊ＝１，２，．．．Ｍ）が関連する。これら動作ユニット２２２−ｉは、それらと関連する実行エンジンを用いて第一と第二のパス分類器に対する計算を遂行する計算ユニットであり得る。本発明の他の幾つかの実施例においては、網プロセッサ１０２の他の要素もファンクションバス２２０に接続される。
【００２３】
図２の第一のパス分類器２００は、例えば、ある与えられたパケットに対して再アセンブリ動作、パリティチェック或いは優先決定の少なくとも一つを遂行するプレ分類器として実現され、第二のパス分類器２０２は、例えば、スケジューリング動作、キューイング動作或いはディスパッチ動作の少なくとも一つを遂行する一つ或いは複数の分類エンジンとして実現される。分類器２００、２０２の一方或いは両方にて、スケジューリング及び他のトラフィック管理機能、例えば、方針決定（policing）に用いるための統計量収集動作を実現することもできる。分類器２００、２０２のこれら及び他の動作は、当分野において周知の技法を用いて従来のやり方にて実現することができ、従ってここでは詳細には説明しない。
【００２４】
第一のパス分類器２００によって受信されるパッケトデータは、第一のパス分類器２００内に組込まれた或いは他のやり方にてこれと関連付けられた再アセンブリ回路を用いて、与えられたパケットを形成するために再アセンブリされるべき、与えられたパケットのセル或いは他の部分から成る。従って、ここで用いられる「パケット（packet）」なる用語は、再アセンブルされたパケットのみでなく、再アセンブルされたとき一つのパケットを形成する一つ或いは複数のセル或いは他のパケットデータをも含むことを意図される。
【００２５】
更に、前述のように、メモリ２０４の異なる部分を、図２に示すように単一のメモリとしてではなく、別個のメモリとして、例えば、図１の内部メモリ１０４と外部メモリ１０６の両方の部分として実現することもできる。ここで用いられる「メモリ回路（memory circuitry）」なる用語は、別個のメモリ、並びに一つの大きなメモリある特定の部分を含むことを意図されるとともに、内部メモリ、外部メモリ或いはこれらの組合せをも指すことを意図される。
【００２６】
図２示す網プロセッサ１０２は、説明のために単純化されているが、ある実施例においては、追加の回路、例えば、上述のスケジューリング回路、ディスパッチ回路及びキューイング回路、一つ或いは複数のメモリコントローラ、並びに、網１０８、スイッチファブリック１１０及び他の外部デバイス、例えば関連するホストプロセッサとインタフェースするための適当なインタフェース回路を含むことも考え得る。加えて、プロセッサ要素間の特定の接続は単に例示であり、例えば、双方向として示される接続は単方向とすることもでき、無方向として示される接続は双方向或いは単方向とすることもでき、図面には示されてない他の接続を設けることもできる。
【００２７】
図２の実施例は複数の動作ユニット２２２を含むが、本発明は、たった１つの動作ユニットのみを含む形態にて実現することもできる。加えて、ある与えられた動作ユニットと関連する実行エンジン２２５の具体的な数は、図２の実施例のように全てのユニットに同一とするのではなく、ユニット毎に変えることもできる。更に、図２においては、実行エンジンはそれらと関連する動作ユニットの外部に設けられるが、これらは、それらと関連する動作ユニット内に組込むこともできる。
【００２８】
図３は、図２の網プロセッサ１０２の順序論理２１０の部分を示す。説明の実施例においては、この順序論理は、セットの順序キュー３００を含む。これは、Ｋ個の別個のキュー３０２−１，３０２−２，．．．３０２−Ｋから成り、各キューは、ある与えられた処理パスに関してセットの異なるファンクションを順序付け（ordering）するために用いられる。Ｋに対する適当な値は、この実施例においては、４とされるが、この場合は、４つの異なるセットのファンクションを順序付けすることが可能となる。一例として、ある与えられたファンクションを第一と第二の両方のパス分類に対して順序付けすることを要求される場合は、この順序付けを行うためにこれら４つの順序キューの二つが用いられる。
【００２９】
この順序論理は、さらに、セットの構成レジスタ３１０を含む。これは、Ｌ個の別個の構成レジスタ３１２−１，３１２−２，．．．３１２−Ｌから成り、これらは、動作ユニット２２２の実行エンジン２２５によって遂行可能な複数のファンクションのどれを、網プロセッサ１０２内で順序付けするかの選択を制御するために用いられる。順序キュー３００を用いて順序付けされるこれらセットのファンクションは、従ってこれら構成レジスタ３１０内に指定されるファンクションから選択される。各順序キュー３０２に対して二つ或いはそれ以上の構成レジスタ３１２を設けることもでき、例えば、一つの好ましい実施例においては、全部で４つの順序キューに対して８個の構成レジスタが設けられる。勿論、順序キューと構成レジスタを具体的に幾つ設けるかは、実現によって異なり、あるファンクションを指定するのに必要とされるビットの数や、各構成レジスタに何ビット存在するかなどの要因によって変化する。
【００３０】
プロセッサ１２０等の網プロセッサ内で遂行される具体的なファンクションは当分野において周知であり、従ってここでは詳細には説明しない。本発明は遂行されるべき具体的なファンクションによって制限されるものではなく、より一般的に、プロセッサ内で処理される一つ或いは複数の順序依存処理タスクに対して、ある所望のファンクション呼の順序を一つ或いは複数のパケット期間を通じて維持するために用いるのに適する。各順序依存処理タスクは、典型的には、複数のファンクションの遂行を必要とし、このため、動作ユニット２２２及びこれらと関連する実行エンジン２２５への複数のファンクション呼（の発行）を伴う。一般には、本発明の技法を用いて、パケットデータの処理と関連し、ファンクションバス２２０上に送るために発行されるあらゆるファンクションを順序付けすることができる。
【００３１】
図３の順序論理２１０の少なくとも一部分をメモリ２０４内に実現することもできることに注意する。例えば、セットの順序キュー３１０及びセットの構成レジスタ３１０は、各々、網プロセッサ１０２のメモリ２０４内の特定のメモリ位置として実現することもできる。
【００３２】
以下では、網プロセッサ１０２の動作を、第一のパス分類器２００によって、ここではプロトコルデータユニット（protocol data unit, PDU）とも呼ばれるパケットに再アセンブルされるセルの処理を伴う、一つの特定の実施例との関連で説明する。この第一のパス分類器は、この実施例においては、各パケットに対して、対応するパケットフロー識別子（packet flow identifier）を決定するように構成される。パケットフロー識別子は、セルのヘッダから当分野において周知のやり方にて抽出される。
【００３３】
これら一つ或いは複数のパケットフロー識別子は、各々、メモリ２０４内、或いは網プロセッサ１０２と関連する他のメモリ回路内の、一意のメモリ位置に対応する（翻訳される）。ある与えられたパケットフロー識別子に対応するこの一意のメモリ位置は、少なくとも一つの、ある関連するパケットフローに対して遂行される複数のファンクションを指定するカウンタを格納するように構成される。この一意のメモリ位置にその与えられたパケットフローの処理と関連する他の情報も格納することもできる。
【００３４】
上述のカウンタを用いて、コンテクスト当たり、或いはセットの順序付きファンクション当たりの、順序付きファンクションの数がカウントされ；結果としてのカウントを用いて、あるコンテクストの寿命中に複数回発行されるファンクションの順序付けが行われる。例えば、処理の際に、一つ或いは複数の後続のパケットに対するファンクション呼を、先のパケットが少なくとも所定の最小数のファンクション呼の発行を終了するまで、後続のパケットが先のパケットより早くなりすぎないために、遅延することが必要となることがある。
【００３５】
網プロセッサ１０２の制御回路は、説明の実施例においては図２の一つ或いは複数の要素２０６，２０８，２１０，２１２，及び２１４から構成されるが、ある与えられたパケットフロー識別子を有する一つ或いは複数のパケットを、適当な動作ユニット２２２に、プロセッサ内で処理される一つ或いは複数の順序依存タスクに対して所望のファンクション呼の順序がその与えられたパケットフロー識別子を有する複数のパケットの期間中維持されるような望ましいやり方にて向ける。「制御回路（control circuitry）」なる用語は、パケットを、パケットフロー識別子に基づいて、プロセッサ１０２内での所望のファンクション呼の順序が維持されるようなやり方にて向けることが可能な処理要素のあらゆる構成を包含するものと解されるべきであり、従って、図２に示されるような要素２０６，２０８，２１０，２１２，及び２１４の特定の構成が要求されるものと解されるべきではない。
【００３６】
本発明のこの処理順序維持機能（processing order maintenance feature）は、説明の実施例においては、第一のパスコンテクスト或いは第二のパスコンテクスト或いはこの両方に関して、ある所定のファンクション或いはセットのファンクションへの呼が、ファンクションバス２２０上に適当な順序にて送られることを保証するために用いられる。第一のパスコンテクストに関しては、これは、これらファンクション呼がファンクションバス２２０上に、対応するセルに第一のパスコンテクスト識別子が第一のパスコンテクスト割当て要素２０６によって割当てられたのと同一の順序で、供給されることを意味する。この順序は、それらセルが網プロセッサ１０２の入力の所に「オン・ザ・ワイヤ（on the wire）」にて到着した順序に対応し、関連するファンクション呼に対してこの順序を維持する動作は、ここではコンテクストワイヤ順序付け（context wire ordering）と呼ばれる。第二のパスコンテクストに関しては、ファンクション呼はファンクションバス２２０上に、第二のパスコンテクスト識別子が第二のパスコンテクスト割当て要素２１２によって割当てられたのと同一の順序にて、供給される。この順序は、ＰＤＵが第二のパスレディキュー２１４内で、第二のパス分類器２０２に送るために順序付けされている順序に対応する。
【００３７】
これら第一のパスコンテクスト識別子は、要素２０６によって、この実施例においては、セルが第一のパス分類器２００に到着したとき数値順に割当てられる。ただし、数値順での割当ては本発明の要件ではない。より一般的に、これら第一のパスコンテクスト識別子は、異なる順序に割り当て、この割当て順を、適当な回路を用いて追跡することもできる。コンテクスト識別子は、ここでは単に「コンテクスト（contexts）」とも呼ばれ、幾つかの実施例においては、コンテクスト０、コンテクスト１、コンテクスト２等の数値識別子が用いられる。
【００３８】
これらコンテクスト識別子は、好ましくは、ある固定数のトークンから選択される。例えば、このトークンの固定数が２５６とされる場合、このコンテクスト識別子は８−ビット識別子から成る。こうして、同一のパケットフロー識別子を有するセルに、要素２０６によって異なるコンテクスト識別子が割当てられ、これらコンテクスト識別子がキューエンジン２０８及び順序論理２１０によってある特定のパケットフロー識別子を有するセル間でのコンテクストワイヤ順序を確保するために用いられる。キューエンジン２０８が割当てられた第一のパスコンテクストを数値順に解放（releases）し、要素２０６がこれらを数値順に再割当て（reassigns）することで、コンテクストワイヤ順序に従う所望のファンクション呼の順序が確保される。
【００３９】
ある与えられたＰＤＵに対する第一のパス分類が完了すると、キューエンジン２０８は、第一のパス分類器２００からそのＰＤＵを受信し、そのＰＤＵを第二のパスレディキュー２１４内に置く。これらＰＤＵは第二のパス分類器２０２に、第二のパスレディキュー内でのそれらの順序に従って送られる。ある与えられたＰＤＵが第二のパスレディキュー２１４から第二のパス分類器２０２に送られると、第二のパスコンテクスト割当て要素２１２によって第二のパスコンテクスト識別子がそのＰＤＵに割り当てられる。ＰＤＵに割当てられる第二のパスコンテクスト識別子は、数値順でないこともあり得る。キューエンジン２０８は、空いた第二のパスコンテクスト識別子のリストを維持し、ＰＤＵの第二のパス分類が開始されたとき、それらをＰＤＵに割当てる。順序論理２１０は、第二のパスコンテクストが発行された順序を追跡し、この順序に基づいてファンクションの順序を確保する。
【００４０】
図２のコンテクスト割当て要素２０６、２１２は、図面には別個の要素として示されているが、網プロセッサ１０２の関連する要素内に組み込むこともできる。例えば、第一のパスコンテクスト割当て要素２０６は、第一のパス分類器回路或いは関連する制御回路に組み込み、第二のパスコンテクスト割当て要素２１２はキューエンジン２０８或いは順序論理２１０内に組み込むこともできる。
【００４１】
前述のように、図３のセットの順序キュー３００を用いて、セットのファンクションを順序付けのために一つのグループにすることもできる。例えば、セットの順序キュー３００内の各順序キュー３０２を４つのファンクションの順序付けに用いることで、以下のようなある与えられたセットの順序付きファンクションｆＳｅｔを形成することもできる：
ｆＳｅｔ＝ｆＯｎｅ＋ｆＴｗｏ＋ｆＴｈｒｅｅ＋ｆＦｏｕｒ
ここで、ｆＯｎｅ、ｆＴｗｏ、ｆＴｈｒｅｅ及びｆＦｏｕｒは、独立したファンクションを表す。一般には、発行されたある順序キューのあるファンクションセットに属するファンクションは、そのキュー内で順序付けされる。上の例においては、４つのファンクションが用いられるが、これは単に例示に過ぎず、あるファンクションセット内のファンクションの数に特に制限があるものではない。
【００４２】
あるファンクションは、第一のパスコンテクスト内で順序付けされるべきか、第二のパスコンテクスト内で順序付けされるべきか、或いはこの両方内で順序付けされるべきかをプログラムマブルに選択することができる。あるファンクションが第一のパスコンテクストと第二のパスコンテクストの両方内で順序付けされることを要求される場合は、上述のファンクション順序キュー３０２の二つが消費されることとなる。上に説明の実施例においては、第一と第二のパスコンテクスト間での順序付けは行われず、ある与えられたファンクションは、プロセッサ１０２がそうするように構成されている場合は第一のパス処理内で順序付けされ、この与えられたファンクションは、プロセッサ１０２がそうするように構成されている場合は第二のパス処理内で順序付けされる。ただし、これは本発明の要件ではなく、説明の技法は、複数のコンテクストを順序付けするために、例えば、第一のパス処理と第二のパス処理の両方に対して順序付けするために用いることもできる。
【００４３】
更に、あるコンテクストの寿命中に、同一のファンクションを複数回発行することもできる。順序論理２１０は、説明の実施例においては、ファンクションの第一回目の発行しか順序付けしない。つまり、そのコンテクストが終端する前に、同一の順序付きファンクションに後続の呼が発行された場合、これらは順序付けされず、順序と関係なく、発行されると直ちにファンクションバス２２０上に送出される。ただし、ここでも、これは本発明の要件ではなく、説明の技法を用いて、あるコンテクストが終端する前に、あるファンクションを複数回順序付けすることもできる。
【００４４】
順序論理２１０があるコンテクストの終端を、そのコンテクストに対する順序付きファンクションを待っている間に検出した場合、これはそのコンテクストに関してその順序付きファンクションを待つのを中止し、順番においてそれより「後ろ（behind）」のコンテクストを解放する。基本的には、順序論理は、ファンクションバス２２０上に供給されるファンクションの順序が、コンテクストが開始された順序と一致することを確保する。あるコンテクストがそのコンテクストに関するある順序付きファンクションが受信される前に終端した場合、順序論理はそのコンテクストに対してそれ以上順序付きファンクションは発行されないものと決定し、それ以上ファンクションを待つのを止める。
【００４５】
ある特定のファンクション、例えば、ここでは一例としてｆＵｎｂｌｏｃｋＯｒｄｅｒＱｕｅｕｅｓと呼ばれるファンクションが、順序論理２１０に対して、そのファンクションを発行したコンテクストに関して順序キュー３０２を解除（unblock）することを指令するために用いられる。あるコンテクストがいったんｆＵｎｂｌｏｃｋＯｒｄｅｒＱｕｅｕｅｓファンクションを発行すると、そのコンテクストに関するそれ以上のファンクションは、そのコンテクストが終端し、再発行されるまで、順序付けされなくなる。
【００４６】
第二のパスコンテクストに関して順序付けされるように定義されたファンクションに対しては、順序論理２１０は、順序付けを遂行する際に優先レベルは考慮しないように構成することもできる。これはハードウェア設計を簡素化するために行われる。ただし、この場合は、低い優先のＰＤＵが高い優先のＰＤＵより前に開始された場合、低い優先のＰＤＵによって高い優先のＰＤＵがブロックされることとなる。
【００４７】
これら順序付けされるべきファンクションは、図３の構成レジスタセット３１０との関連で説明した構成レジスタ制御法とは異なる技法を用いて指定することもできる。例えば、順序付けされるべきセットのファンクションは、ある特定のファンクション空間として定義し、例えば、例えばファンクション５１１−２５６に対応する上側ファンクション空間を下側ファンクション空間例えば２５５−０にマッピングし、こうしてマッピングされたファンクションを順序付けすることもできる。ただし、一般には、上述の構成レジスタアプローチの使用がファンクションの将来の割当てに影響を与えないという点で好ましい。
【００４８】
上述の構成レジスタアプローチの一般背景内ですら、あるファンクションセット内のファンクションの順序付けを指定するために他の技法を用いることもできる。例えば、ある特定のビットパターンを示す、例えば、その最後の３ビットが００１にセットされている全てのファンクションを、マスキングを用いてあるセットに割当てることもできる。
【００４９】
以下では順序論理２１０の動作を幾つかの例を参照しながらより詳細に説明する。以下に説明する実施例はもっぱら例示のためのものであり、従って本発明の範囲をいかようにも制限するものと解されるべきではない。本発明の他の実施例は、以下に説明するそれとは異なるやり方にて動作する。以下の実施例に対しては、セットの順序キュー３００内には４つの別個の順序キュー３０２−１、３０２−２、３０２−３及び３０２−４が存在し；これら順序キューは、ある与えられたファンクション或いはファンクションセットに対して、異なるキュー間ではなく、ある特定のキュー内での順序を確保するものと想定される。例えば、以下のようなファンクションが、以下のような順序で、第一のパス分類器２００或いは第二のパス分類器２０２から発行され、コンテクスト０はコンテクスト１の前に割当てられるものと想定する：
コンテクスト１に関する順序付きファンクション１
コンテクスト０に関する順序付きファンクション１
コンテクスト０に関する順序付きファンクション２
コンテクスト１に関する順序付きファンクション２
【００５０】
順序論理２１０は、順序付きファンクション１は、ファンクションバス２２０上に、コンテクスト０に関して、コンテクスト１より前に、発行されることを確保する。ただし、説明の実施例においては、この順序論理は、コンテクスト０に関する順序付きファンクション２がファンクションバス２２０上に、コンテクスト１に関する順序付きファンクション１より前に発行されることは保証しない。
【００５１】
順序付きファンクションがあるコンテクストに関して発行されない場合は、順序論理２１０はそのコンテクストの後に続くコンテクストを、そのコンテクストに関してコンテクスト終端ファンクション、例えば、ｆＱｕｅｕｅ、ｆＱｕｅｕｅＥＯＦ、或いはｆＴｒａｎｓｉｍｉｔファンクション、或いは上述のｆＵｎｂｌｏｋＯｒｄｅｒＱｕｅｕｅｓファンクションが発行された時点で、解放（frees up）する。次に、コンテクストが数値順、つまり、コンテクスト０、コンテクスト１、コンテクスト２の順で割当てられているものと想定される以下の例について考える：
コンテクスト１に関する順序付きファンクション１
コンテクスト２に関する順序付きファンクション１
コンテクスト０に関してｆＱｕｅｕｅが発行される
【００５２】
順序論理２１０は、順序付きファンクション１をコンテクスト１と２に関して受信し、これらを保持する一方で、順序付きファンクション１がコンテクスト０に関して発行されるのを待つ。コンテクスト０に関してｆＱｕｅｕｅが発行されると、順序論理は、順序付きファンクションをコンテクスト１とコンテクスト２に関して（この順に）ファンクションバス２２０上に発行する。コンテクスト０に関するｆＱｕｅｕｅファンクションは、基本的に順序論理に対して、コンテクスト０に対する仕事が完了し、そのコンテクストは空きプール（free pool）に戻されるべきことを伝える。このコンテクストに関するそれ以上のファンクションは、それがプールから新たなセルに再割当てされるまで順序キューには送られない。あるコンテクストに関してｆＵｎｂｌｏｋＯｒｄｅｒＱｕｅｕｅｓファンクションが受信されると、そのコンテクストに関して発行される後続のファンクションは、そのコンテクストが（例えば、ｆＱｕｅｕｅファンクションによって）終端されるまで順序付けされない。他のタイプのコンテクスト終端ファンクションとしては、ｆＱｕｅｕｅＥＯＦと呼ばれる専用のファンクションの終わり（end of function, EOF）ファンクションや、ｆＴｒａｎｓｉｍｉｔとも呼ばれる送信（transmit）ファンクションが含まれる。
【００５３】
図３のレジスタセット３１０内の各構成レジスタ３１２は、各々、（１）順序キュー３０２の関連する１つ内で順序付けされるべきファンクションを、指定される最大数、例えば、４つのファンクションまで定義し；（２）そのキューに対して定義される複数の有効なファンクション、例えば、ファンクション０から４を定義し；（３）それらファンクションが第一のパスコンテクストに関して順序付けされるべきか或いは第二のパスコンテクストに関して順序付けされるべきかを定義する；ように構成される。これら及び他の類似の情報を構成レジスタセット３１０の各構成レジスタ３１２内に格納するためには、当分野において周知の様々な適当なフォーマットを用いることができる。
【００５４】
先にも言及したように、上述の順序論理２１０及びこれと関連する順序キューセット３００と構成レジスタセット３１０の動作及び構成の説明は、単に例示に過ぎず、当業者においては、様々な代替構成を用いても本発明を実現できることに注意する。
【００５５】
図４は、図１のシステム１００の部分が、一例として、ルータ或いはスイッチのラインカードとして実現される様子を示す。この実施例においては、処理システムはラインカード４００から成り、これはこの上に搭載された少なくとも一つの集積回路４０２を有する。集積回路４０２は、網プロセッサ１０２を含み、これは内部メモリ１０４を有する。網プロセッサ１０２は、ラインカード４００上の外部メモリ１０６とやり取りする。外部メモリ１０６は、例えば、網プロセッサの集積回路に対する外部木メモリ（ｔｒｅｅ  ｍｅｍｏｒｙ）として機能する。このラインカード４００上に上述のホストプロセッサも搭載することもできる。
【００５６】
図４に示される処理システムの部分は説明のためにかなり簡素化されている。ただし、この処理システムは、このようなラインカードを複数含み、各ラインカードが複数の集積回路を含む、ルータ或いはスイッチから構成することもできる。類似の態様をポストカードの形式にて実現することもできる。
【００５７】
本発明の上述の実施例は単に解説のために示されたものである。例えば、図２の実施例においては別個の第一のパス分類器と第二のパス分類器、つまり、第一のパス分類器２００と第二のパス分類器２０２が用いられるが、別の形態としてこれら要素の機能を、単一の分類エンジンに結合することも、セットの分類エンジンに結合することも、或いは他のタイプの分類回路に結合することもできる。本発明のコンテクスト識別子に基づく順序付けは、第一のパスコンテクストに対して提供することも、第二のパスコンテクストに対して提供することも、第一と第二の両方のパスコンテクストに対して提供することも、更には、単一或いは複数のコンテクストの他の構成に対して提供することもできる。網プロセッサ１０２内で具体的にどのような制御回路を用いるかは、本発明のある与えられた実現において用いられる処理構成によって変わる。加えて、メモリ２０４は、説明の実施例においては、少なくても一部は網プロセッサの内側に設けられるが、これは単に一例に過ぎない。別のやり方として、上述の機能を実現するために他の様々なタイプの内部或いは外部メモリ回路構成を用いることもできる。更に、前述のように、分類回路の具体的な分類動作は、処理用途に応じて、例えば、ホストプロセッサを介してソフトウェア制御の下で変えることもできる。当業者においては、クレームの範囲から逸脱することなく、これら及びその他の様々な代替が可能である。
【図面の簡単な説明】
【図１】本発明がその内部で実現されるパケット処理システムの一つの実施例を示す略ブロック図である。
【図２】図１のシステム内で用いられる本発明の技法に従って構成された網プロセッサをより詳細に示す図である。
【図３】図２のプロセッサ内で用いられる本発明による順序論理の順序キュー及び構成レジスタの要素を示す図である。
【図４】図２の網プロセッサがルータ或いはスイッチのラインカード上に搭載された集積回路として実現される実施例を示す図である。
【符号の説明】
１００  パケット処理システム
１０２  網プロセッサ
１０４  内部メモリ
１０６  外部メモリ
１０８  網
１１０  スイッチファブリック
２００  第一のパス分類器
２０２  第二のパス分類器
２０４  メモリ
２０６  第一のパスコンテクスト割当て要素
２０８  キューエンジン
２１０  順序論理
２１２  第二のパスコンテクスト割当て要素
２１４  第二のパスレディキュー
２２０  ファンクションバス
２２２  動作ユニット
２２５  実行エンジン（ＥＥ）
３００  セットの順序キュー
３１０  セットの構成レジスタ
４００  ラインカード
４０２  集積回路
【図１】
0004307829.tif 000002
【図２】
0004307829.tif 000003
【図３】
0004307829.tif 000004
【図４】
0004307829.tif 000005