JP4856580B2 - ネットワーク・プロセッサにおけるソフトウェアの運転中アップグレードを実行するための方法および装置 - Google Patents

Description

本発明は一般にパケット処理システムに関し、より詳細には、そうしたシステム内のパケット処理動作の実行で使用するために構成されたネットワーク・プロセッサまたはその他の種類のプロセッサに関する。

ネットワークまたはパケット・プロセッサは一般に、例えば非同期転送モード（ＡＴＭ）ネットワークまたは同期光ネットワーク（ＳＯＮＥＴ）の物理層部分などの物理伝送媒体と、ルータまたはその他の種類のパケット・スイッチのスイッチ構造との間のパケットの流れを制御する。そうしたルータおよびスイッチは一般に、例えば回線の配列、または各々のカードに関連する１つまたは複数のプロセッサを備えたポート・カードの形態で配置された、複数のネットワーク・プロセッサを含む。

そうしたネットワーク・プロセッサは、極めて高い信頼性と可用性とをサポートしなければならないキャリア・クラスの製品の中に設計されることもある。これらの環境では製品寿命が長く、ダウン・タイム、すなわちネットワーク・プロセッサが利用できない時間が極めて少ないことが要求される。このような環境で、ネットワーク・プロセッサは、ネットワーク・プロセッサによって執行されるソフトウェア・コードが、もしあるならば最小限のダウン・タイムで、動作中のシステムでアップデートされることが可能な、運転中アップグレードを行えることが望ましい。

運転中アップグレードのための従来の方法は、ネットワーク・プロセッサによって執行されるべきソフトウェア・コードを記憶するネットワーク・プロセッサのメモリを２つの区分に分割するというものである。第１のメモリ区分は現在のソフトウェア・コードを含み、一方アップデートされるソフトウェア・コードは第２のメモリ区分にロードされる。切換えは適切な時間に実行され、アップデートされたソフトウェア・コードをアクティブにする。

しかしながら、結果的にこの方法はメモリをかなり無駄にする。つまり２つのソフトウェア・コードのコピー、すなわち現バージョンとアップデートされたバージョンとが維持されるので、ネットワーク・プロセッサに関するメモリの半分しか使用することができない。

したがって、ネットワーク・プロセッサに関連するソフトウェアの運転中アップグレードを実行するための改良された技術が必要とされる。

本発明の原理は、ネットワークまたはパケット・プロセッサに関連するソフトウェアの運転中アップグレードを実行するための改良された技術を提供する。
一例として、本発明の１つの態様で、パケット・プロセッサに関連するメモリに記憶可能で、パケット・プロセッサ上で執行可能な、第１コード・バージョンから第２コード・バージョンへのコードの運転中アップグレードを実行するための方法は以下のステップを含む。第１ステップは、第１コード・バージョンから第２コード・バージョンへのコードのアップグレードを達成するために、１つまたは複数の書き込み動作を生成することによってアップグレードの準備を行うことを含む。第２ステップは、１つまたは複数の書き込み動作をパケット・プロセッサに伝達することによって、第１コード・バージョンから第２コード・バージョンへコードをアップデートすることを含む。第３ステップは、アップデートステップの後に利用可能な１つまたは複数のメモリの場所を回収することによって、アップデートステップの後にクリーンアップを行うことを含む。このように、パケット・プロセッサに関連するメモリの中で、コードのうちの単一のバージョンのみの記憶領域が必要とされる。

アップグレードされるコードは１つまたは複数の処理要素を含んでもよく、アップデートステップは、各処理要素のために、処理要素の執行に対して責任を負うパケット・プロセッサの少なくとも一部の動作を中止することを含んでもよい。アップデートステップは、各処理要素のために、処理要素に関する１つまたは複数の書き込み動作をパケット・プロセッサに伝達することをさらに含んでもよい。またさらに、アップデートステップは各処理要素のために、パケット・プロセッサの中止された部分の動作を再開することを含んでもよい。処理要素は単に一例として、機能上分離したコードのブロック、パケットの分類に関連する１つまたは複数のプログラムを含んでもよい。第１コード・バージョンは古いコード・バージョンを含んでよく、第２コード・バージョンは新しいコード・バージョンを含んでよいということもまた理解されたい。
本発明のこれらの目的およびその他の目的、ならびに機能および利点は、添付の図面と併せて読まれるべき、以下の本発明の例示的実施形態の詳細な説明より明らかとなろう。

本発明は、パケット処理システムの一部であるネットワーク・プロセッサ上で執行可能なソフトウェアによって実行される、例示的なパケット分類機能と併せて以下で説明される。しかしながら本発明は、ネットワーク・プロセッサに関連するソフトウェアの運転中アップグレードを実行するための従来の技術で使用することによって生じる欠点を回避することが望まれる、パケット処理システムにおける任意のネットワーク・プロセッサの機能またはソフトウェアに、より広く適用可能であることを理解されたい。

単に例として、本発明の原理は、Ａｇｅｒｅ Ｓｙｓｔｅｍｓ社（ペンシルバニア州、アレンタウン）より入手可能な、例えばＡＰＰ３５０、ＡＰＰ５５０およびＡＰＰ６５０としてそれぞれ識別されるネットワーク・プロセッサなどの、パケット・プロセッサに適用可能である。しかしながら、これらのプロセッサ、または任意の特定のプロセッサに本発明の原理が限定されるわけではないことを理解されたい。

本明細書で使用されている用語の「プロセッサ」は、一例として、および限定されることなく、マイクロプロセッサ、中央処理ユニット（ＣＰＵ）、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け特定集積回路（ＡＳＩＣ）、またはその他の種類のデータ処理デバイスもしくは処理回路の他にも、これらおよびその他のデバイスまたは回路の一部、ならびにそれらの組合せを利用して、実装されてもよいということを理解されたい。

本明細書で使用される用語の「ソフトウェア」は一般に、１つまたは複数の機能を実行するためにプロセッサによって執行（実行）されてもよい、１つまたは複数の命令を指すこともまた理解されたい。「ソフトウェア」という用語はまた、「ソフトウェア・コード」、「コード」、「ソフトウェア・プログラム」または「プログラム」などの用語／術語と交換可能に本明細書で使用される。しかしながら、本発明はソフトウェアのいかなる特定の定義にも限定されることはなく、したがって本発明の運転中アップグレードの原理は、これらの定義およびその他の定義に適用可能であることを認識されたい。

図１を参照すると、本発明の実施形態が実装されるパケット処理システム１００が示されている。システム１００は、内部メモリ１０４を有するネットワーク・プロセッサ１０２を含む。ネットワーク・プロセッサ１０２は図示のように外部メモリ１０６に接続され、パケットが受信されるネットワーク１０８とパケット・データの切換えを制御するスイッチ構造１１０との間のインタフェースを提供するように構成されている。プロセッサ１０２およびその関連の外部メモリ１０６は、例えばルータまたはスイッチのライン・カード上に設置された１つまたは複数の集積回路として実装されてもよい。このような構成では、スイッチ構造１１０は一般に、ルータまたはスイッチの一部であるとみなされる。

図中で、メモリ１０６はプロセッサ１０２の外部にあるものとして示されているが、本明細書で使用される用語の「プロセッサ」は、先に示されたとおり、要素１０２および１０６を包含するのに十分に幅広いものであることが意図されている。

図１のシステム要素の特定の配置は、単に解説用の例として示されていることを理解されたい。例えば、先に述べられたとおり、本発明の原理は任意の種類のパケット・プロセッサの中で実施されることが可能であり、いかなる特定のパケット処理アプリケーションにも限定されることはない。

分類、ルーティングまたは切換えなどのパケット処理動作の実行中、ネットワーク・プロセッサは通常、各パケットの少なくとも一部を検査しなければならない。一般に、パケットはバイナリ・ビットの列から成り立っている。検査されなければならない各パケットの量は、それに関連するネットワーク通信プロトコル、使用可能なオプションおよびその他同様の要素によって決まる。

より具体的には、パケット処理の動作中、ネットワーク・プロセッサは通常、各パケットに関連する様々な特性を判断するために、すなわち１つまたは複数のデータ属性によって入力データを分類するために、ツリー検索プロセスを利用する。これは分類機能またはプロセスと呼ばれる。知られているように、（１つまたは複数のルックアップ・テーブルなどのデータ構造の形態であることが可能な）ツリー構造は通常、検索が始まる根の部分と、中間の枝と、最後に最終的な判断または照合が生じる複数の葉とを有する。したがって、ツリーの各ノードはエントリまたは決定ポイントであり、そのようなエントリまたは判断ポイントは枝によって相互に接続されている。命令またはビット・パターンは、（検索オブジェクトとも呼ばれる）入力ビット・パターンを分析するため、およびそれに応じてビット・パターンを次の適切な決定ポイントに送信するために、各決定ポイントに置かれている。

データはバイナリ・ビットの形態で示されているので、分類プロセスは入力ビットのグループをツリー構造のエントリによって表される、分かっているビット・パターンと比較する。入力ビットのグループとツリーのエントリのビットとの間の照合は、プロセスをツリー中の次の連続したエントリに向かわせる。照合プロセスは、その時点で入力ビットが特徴付けられるか、または分類される終着点に達するまで、ツリーの各エントリを通って進行する。データ・ネットワーク中で多くの数のビットが分類されなければならないので、これらのツリーは多くのメガビットのメモリ領域収容力を必要とする場合がある。

データ通信ネットワークの中で、分類プロセスは多くの用途を見出す。入力データ・パケットは、判定経路が異なるネットワークの優先レベルを表すツリー構造を使用して、パケット内の優先順位標識に基づいて分類されることが可能である。利用可能なネットワークの優先レベルを表す入力ビットとツリービットとの間の照合に基づいて、一旦各パケットのために優先レベルが判定されると、その後パケットは優先順に処理されることが可能である。その結果、時間に関係するパケット（例えばビデオ会議データを運ぶパケットなど）は、時間にあまり関係のないパケット（例えばファイル転送プロトコル（ＦＴＰ）データの転送など）より先に処理される。その他のパケット分類プロセスは、（例えば、ファイヤウォールが１つまたは複数のソースからのすべてのデータをブロックすることができるように）パケットのソースを判定し、最もよくデータをサービスすることができるウェブサーバを判定するために、またはネットワークの顧客の課金情報を判定するために、パケット・プロトコルを検査する。ネットワーク・プロセッサを通した処理のためにデータ・ブロックに分割されていたパケットの再組立てに必要とされる情報もまた、データ・ブロック中の特定の領域を検査する分類プロセスによって判定されることが可能である。パケットは、通信媒体をトラバースするときに遭遇する次のデバイスによってグループ分けされることが可能であるように、それらの宛先アドレスによって分類されることもまた可能である。

知られているように、例示的に上で説明されたツリー構造、および分類プロセスを指示する関連の命令（本明細書ではまとめて「分類ソフトウェア」と呼ばれる）は、通常ネットワーク・プロセッサの内部メモリ（例えば図１のネットワーク・プロセッサ１０２のメモリ１０４など）に記憶され、必要な場合にロードされ、執行される。分類ソフトウェアの異なる部分は、内部メモリの異なる部分に記憶されることが可能である。しかしながら、キャリア・クラスのネットワーク・プロセッサの高い信頼性と可用性とが必要とされることから、こうした分類ソフトウェアのアップグレードは、好ましくは、ネットワーク・プロセッサがソフトウェア・コードを実行しているときに（すなわち運転中に）、（もしあるとすれば）非常に少ないダウン・タイムで、ネットワーク・プロセッサ上で達成されるべきである。

一例として、（１）ソフトウェアを構成する１つまたは複数のプログラムは軽度のエラー（バグ）を含み、修正される必要がある、（２）新たなプロトコルはソフトウェアによってサポートされる必要があるという、分類ソフトウェアの運転中アップグレードを実行するための２つの理由がある。

そうした運転中のソフトウェアのアップグレードとは、かなり大きな課題を提起することがわかる。それらのうちの一部は以下で説明される。
最高レベルで、分類ソフトウェアは（１）フローと（２）ツリーとの２種類の機能から成り立っている。フローはプログラムの制御フローを定義し、ツリーは実行時にアップデートされても、されなくてもよいテーブルを定義する。このような（フローとツリーとの）機能の分割は、分類ソフトウェアとその関連のツリーとの上述の一般的な説明と矛盾しないことに注意されたい。

ツリーはネットワーク・プロセッサのメモリのツリー・メモリ区分に記憶され、（例えばマイクロ・ルート、ルート、およびネットワーク・プロセッサの外部のメモリがツリー構造の一部を記憶するために用いられる場合には外部など）様々なレベルの機能に組織されることが可能である。フローはネットワーク・プロセッサのメモリのフロー・メモリ区分に記憶される。１つの実施形態で、フロー・コード全体はツリー・メモリの中に保存され、フロー機能のセット（モジュール）は実行時にフロー・メモリの内外で動かされる。

関連のコンパイラにおける実施ロジスティクスと同様、互換性に関してエンド・ユーザ側と、関連のアプリケーション・プログラミング・インタフェース（ＡＰＩ）との両方からのパケット・トラフィックへの影響は最小限にして、実行中のプログラムをアップデートすることには多くの課題がある。

様々な点で、新たな（変更された）プログラムは古いプログラムと互換性がなければならない。例えば、パケットを処理するために記憶・転送モデルを用いるネットワーク・プロセッサには、古いプログラムの第１パス論理によって待ち行列の中に入れられたパケットが存在するかもしれない。古いソフトウェアから新たなソフトウェアへの切換えが起こるとき、これらのパケットは新たなプログラムの第２パス論理によって処理され、この互換性は維持されなければならない。しかしながらソフトウェアの機能によっては、維持されることを必要とする多くのその他の互換性が多数あるかもしれない。通常、これらの互換性を維持することは、エンド・ユーザ／アプリケーションの責任である。

通常、ソフトウェアに関連する機能は固有の名称を有していてもよく、固有の数字にマップされてもよい。数字は、実行時の動作のためのＡＰＩにおける機能識別子としての役割を果たす。コンパイラは自動的にこれらの数字を、ユーザによってまだマップされていない機能に割り当てる。プログラムが変更され、再コンパイルされる場合、数字の割当は変更されてもよく、これが先の制御フローを無効にしてもよい。古いプログラムから新たなプログラムへ機能をマッピングするための手段がないことから、一般に機能名が変更されることは望ましくない。

ネットワーク・プロセッサの分類ソフトウェアはユーザによる編集が可能なので、これは、アップデート目的のために何が変更されたのかを判定する際の多くの課題を提起することにもなる。この問題はフローとツリーのために異なっている。

先に述べたように、フロー機能はプログラムの制御フローを定義し、いかなる変更であってもプログラム全体にわたる影響を有することがある。例えば、コンパイラがプログラムを分析することによって、物理レジスタに国際的なレジスタ名を割り当てる場合には、いかなるわずかな変更であっても制御フローに大きな影響を及ぼし、プログラム全体を通してレジスタの割当を変える可能性もある。

ツリーは本質的に動的なものであることが可能であり、大規模なパターンのテーブルを構築するために使用されることが可能である。そのようなツリーが他の分類機能への参照を有する場合、結果的に、参照された機能のアドレスが新しいコードの中で変わる場合、多くのノードかアップデートされなければならないこともある。

本質的により実用的で、分かっているパターンを行為にマップするために使用される別のツリーがある。これらはフロー機能などの制御フローを定義するためのものがより多く存在し、ここでのいかなる変更もプログラムに影響を及ぼす場合がある。

言語の文法から見ると、分類ソフトウェアは自由に流れており、ユーザは、コンパイラが構造に適合させるために潜在的フローおよびツリーに分割してもよい文の任意の順序を定義することができる。プログラム中のわずかな変更が異なる潜在的フローおよびツリーを生成することもあり、これらは適切に処理される必要がある。

理想的な状況では、新たなプログラムはトラフィックへの影響を伴わずに実行中のシステムにインストールされる。しかしながら、問題の性質とメモリの制限とを考えると、これは達成不可能であり、トラフィックが落とされるか、または低速で処理されるかもしれないところで、許可される領域（ｗｉｎｄｏｗ）の量は少ない。典型的に、この領域は１桁のミリ秒で測定される。したがって、ネットワーク・プロセッサ構造の性質を考えると、少ない時間領域で新たなコードがハードウェアにダウンロードされなければならないということは明白である。

アップグレードが新しいコード（特にツリー）を伴う場合、システムの状態によってはこれらのツリーを構築する際に問題がある場合がある。実行中のシステムのメモリが著しく断片化されている場合、新たなツリーのうちのいくつかを構築するための十分な連続したスペースを見つけることができないかもしれない。

上で説明したような課題を踏まえて、上述、ならびにその他の欠点および課題に対処し、それらを克服する、ネットワーク・プロセッサに関する分類ソフトウェアの運転中アップグレードのための例示的な実施形態をここで述べる。

分類ソフトウェアのアップグレードの性質は、新しいコードをインストールするために、かなりの数のメモリ書き込み動作（または、より単純に言うと「書き込み」）を伴うことがわかる。これは、全体的にフロー・コードを適切に再構築することと、場合によっては何十万にもなるかもしれない参照を伴う大規模なツリーを適切にアップデートすることとを含む。最大限のダウン・タイムがミリ秒で測定される時間制限を踏まえて、本発明の原理は、このことが、ある種の準備またはクリーンアップがダウン・タイム以外で行われ、少量であっても予測可能な書き込みのセットが原子切換えのために行われる、段階的、または局面的な方法を必要とするということを認識する。

図２は本発明の実施形態による、ネットワーク・プロセッサに関連するソフトウェアの運転中アップグレードの段階的（または局面的）方法を示す。図示のとおり、分類ソフトウェア２０１の運転中アップグレード２００は、準備段階２０２、アップデート段階２０４およびクリーンアップ段階２０６を含む３段階の方法において、ＡＰＩ２０８を介してエンド・ユーザ（不図示）によって実行される。

一般に、準備段階２０２はアップグレードのための準備を行うことを伴う。この局面では様々なメモリの書き込みが行われることができるが、ハードウェアは依然として古いコードを執行している。準備は命令の構築、およびアップデート中にメモリの書き込みがハードウェア（ネットワーク・プロセッサ１０２）に伝達される準備ができているように、メモリの書き込みをバッファすることなど、アップデータのための準備を行うことを含むことも可能である。

一般に、アップデード段階２０４では、ハードウェアを新しいコードに切り換えるために、限定された書き込みのセットが実行される。この段階は、切替えの周辺でプロセッサの機能を停止／停止解除することを伴う。このように、この段階の最優先の目標は、アップグレードによって影響を受けるプロセッサのメモリ部分への、できる限り少ないブロック書き込みを生成することである。この段階の後、ハードウェアは新しいコードを執行する。

一般に、クリーンアップ段階２０６は、行われるべき任意のクリーンアップを伴う。これは、メモリの解放および回収、周辺へのツリーの移動等を含んでもよい。
一例として、ネットワーク・プロセッサでアップデートを実行する状況において、アップデートは、機能的に集積回路の出力側に最も近い処理ポイントで始まる。プロセッサを通した処理は、（データを廃棄するか、または処理ポイントの前で待ち行列に入れるかのいずれかで）一時停止される。一旦プロセッサが休止ポイントに置かれると、続いてそのプロセッサのためのコードはアップデートされる。その後、集積回路のその部分を通るトラフィックは再開される。

さらに、このプロセスはコードの各機能ブロック（すなわち処理要素）のために実行されてもよく、機能ブロックによって、機能ブロックを集積回路の入力側の方へ移動させる。機能ブロックの１つの例は、本明細書で述べられる分類プログラムである。しかしながら、分類プログラム自体は、本明細書で述べられる方法で、（以下で述べられるような、関連のツリーとフローとを伴う）ブロックに分割され、処理されることが可能である。

したがって、アップグレード段階２０４は、アップグレードされるコードに関連する各処理要素（例えばブロック）のために、処理要素の執行に対して責任を負うネットワーク・プロセッサの少なくとも一部の動作を中止（すなわち停止または中断）することと、処理要素に関連する１つまたは複数の書き込み動作をネットワーク・プロセッサに伝達することと、その後、ネットワーク・プロセッサの中止された部分の動作を再開することとを含む。

プロセッサに関連するソフトウェアでは、有利に、１度につき１つの処理要素がアップグレードされてもよい。（各処理要素のために）実際のアップデートステップを比較的短くしておくことによって、ネットワーク・トラフィックへの影響は最小限にされる。したがって、１度につき１つの処理要素の実際のアップデートステップを実行し、各要素を効果的に停止／再開することによって、プロセッサの停止期間が著しく長くなることが回避される。

このような運転中アップグレードの手順を踏まえて、様々な問題およびそれらの解決法が以下で述べられ、それらを適用可能な箇所で、この続きにマッピングする。

Ａ．フロー
上述のように、フロー機能によって定義される制御フロー経路のいかなるものにおいても、わずかな変更がプログラム全体にわたる影響を与える場合がある。さらに、メモリ配置の中で、フロー機能には非常に厳密な必要条件がある。個々の変更を判定し、できないかもしれない既存のフロー・コードへの改造を試みるよりもむしろ、フロー・コードは新たなコードによって全体的に置き換えられる。

ネットワーク・プロセッサの例示的実施形態によって、ネットワーク・プロセッサで実行されるアプリケーションは、アプリケーションのサービスをソフトウェア・モジュールに分割し、フロー・メモリからそうしたモジュールを個々にロード、またはアンロードすることによって、実行時にフロー・メモリを管理する。フロー・メモリは、ネットワーク・プロセッサの内部メモリ（図１の１０４）の一部であることが可能である。

例えば、最初のロードで、モジュールはプレロードした優先順位に基づいてフロー・メモリの中にロードされる。実行時に、アプリケーションは様々なロード／アンロードの動作を実行してもよく、定められたモジュールのサブセットは所与の時間でフロー・メモリの中にロードされる。そのようなアプリケーションのために、（アップグレードの前にロードされた）現時点でロードされているモジュールは、アップグレードの後も、フロー・メモリの中にロードされるべきである。このことを踏まえて、アップグレードの後、フロー・メモリの状態を判定するために以下の方法が続けられる。任意の、古いコードから事前にロードされたモジュールは、新しいコードからロードされる。残りのモジュールは、プレロードした優先順位に基づいてロードされる。すなわち、アップグレードのプロセスは、フロー・メモリの中にロードされていた古いコードからのモジュールがアップグレードの後にもロードされ、その後、任意の新たなモジュールがロードされることを確認する。

例示的なネットワーク・プロセッサの上述の特徴を踏まえて、運転中アップグレードの間にフロー・コードをアップグレードするために使用される図２の段階は、以下のとおりである。フロー・コードのアップグレードのプロセスは、図３の状況の中で説明される。これらの実施形態の中でネットワーク・プロセッサの「メモリ」（例えばツリー・メモリ、フロー・メモリ等）という言及は、内部メモリ１０４、外部メモリ１０６、または内部メモリ１０４と外部メモリ１０６との組合せを指してもよいということを再度理解されたい。

図３に示すように、準備段階（図２の２０２）の間、新しいコードからのモジュールはネットワーク・プロセッサ（ＮＰ）のツリー・メモリの中にロードされ、古いコードからのフロー・コードのツリー・メモリのコピーを上書きする（ステップ３０２）。次に、ロードされるべきモジュールを判定するために、ＮＰのフロー・メモリの現在の状態が検査される（ステップ３０４）。優先順位をプレロードしたモジュールによって判定される、これらのモジュールおよびその他のモジュールは、フロー・メモリ、および調整されたすべての機能参照を模倣するホスト・メモリ・バッファの中にコピーされる（ステップ３０６）。「ホスト・メモリ・バッファ」は、エンド・ユーザがＡＰＩ２０８（図２）を介してネットワーク・プロセッサとインタフェースする、ホスト・コンピュータ・システム（不図示）上にあるということを理解されたい。このバッファの大きさは、ＮＰのフロー・メモリの量と少なくとも同等であることが好ましい。

アップデート段階（図２の２０４）の間、ホスト・メモリ・バッファはＮＰに書き込まれ、フロー・メモリの内容を変更する（ステップ３０８）。
クリーンアップ段階（図２の２０６）の間、任意の必要なクリーンアップ動作が実行される（ステップ３１０）。そうした動作の１つは、割り当てられたホスト・メモリ・バッファを解放することである。

特定のネットワーク・プロセッサの構造の中で、インライン（ｉｎｌｉｎｅ）のパターン照合、抽出等の動作を実行するために、複数のフロー機能がツリー命令を使用するということを理解されたい。これらのツリー命令は、可能なルート（またはマイクロ・ルート）メモリの中にロードされてもよい。新しいコードでは、処理能力を保つとともに、同様のメモリ割当が行われることが必要となる。しかしながら、システムの状態によっては、古いコードのツリー命令は、一旦古いコードが置き換えられると使用されなくなるが、この高速の（ｆａｓｔｅｒ）メモリは利用できない場合がある。

新しいコードのツリー・メモリのコピーを構築する間、古いコードのツリー・アドレスはそれらの内容を変更することなく、（あたかもそれらが使用されていなかったかのように）再利用される。それらの新たなデータを伴うこれらのアドレスは待ち行列に入れられ、アップデートの局面でハードウェアにダウンロードされる。

古いコードのためにこれらのアドレスを割り当てる間、特定のバッファは、アドレスをできるだけ連続させておくために、新たなコードに加わることができるように事前に割り当てられることを必要とする場合がある。

Ｂ．ツリー
ツリー・データ構造は、フロー・データ構造とは異なる課題群を提起する。本発明の原理は（１）静的ツリーと（２）非静的ツリーとの、２種類のツリーの分類を定義する。説明されるとおり、各分類は運転中アップグレードの中で、異なるやり方で処理される。エンド・ユーザは、ツリーが静的であるのか非静的であるのかを（以下の例示的な定義に基づいて）判定することができるということを理解されたい。しかしながら、自動および半自動の判定プロセスが用いられてもよい。

１．静的ツリー
「静的ツリー」は、実行時、すなわちネットワーク・プロセッサのソフトウェアの実行の間に変化することがないツリーとして定義される。静的ツリーはアップデートされているソフトウェア中で完全に特定されるので、実行時に管理（および変更）されることはない。そのようなツリーの一例は、例えばプロトコル型の領域がプロトコル特有の機能にマップされる、プロトコル・マッピングを定義するものである。これらのツリーはプログラムの制御フローに必要不可欠であるため、アップグレードの間に完全に再構築される。

静的ツリーの上述の特徴を踏まえて、運転中アップグレードの間に静的ツリー・コードをアップグレードするために使用される図２の段階は、以下のとおりである。静的ツリー・コードのアップグレードのプロセスは、図４の状況の中で説明される。

図４に示すように、準備段階（図２の２０２）の間、新しいコードのためにすべての静的ツリーが構築される（ステップ４０２）。これは、古いコードの中にはないかもしれないが、新たなコードでは必要とされる新たなツリーを構築することと同様に、古いコードから新しいコードへ変化するツリーを再構築することを含む。メモリは著しく断片化している可能性もあり、８、１２または１６ビット・テーブルのための連続したメモリは保証されない可能性もあるので、静的ツリーは最初に４ビットのテーブルで構築される。これは、１６の連続する空き場所があり、十分な空きメモリがある限り、ツリーは構築されることが可能であり、すべてのパターンは習得されるということを保証する。

ここで、（最初のテーブルおよび引き続き起こる命令を備えた）主要なツリー構造は空きメモリ（すなわちＮＰの空きメモリの使用されていない部分）の中で構築され、先に具体化したもの（ｐｒｅｖｉｏｕｓ ｉｎｃａｒｎａｔｉｏｎ）（古いツリー）からのルート・アドレスが再利用される。ルート・アドレスは、ツリーの根を示すメモリのアドレスである。ルート・アドレスは新たなツリー（テーブル）を示すために書き込まれるが、書き込みはハードウェア（ＮＰ）には伝達されない。これらの書き込みは、アップデートの局面まで待ち行列に入れられる（記憶される）（ステップ４０４）。

アップデート段階（図２の２０４）の間、（ステップ４０４で記憶された）ルート・アドレスの書き込みはＮＰに伝達される（ステップ４０６）。ツリーのルート・アドレスが一緒に割り当てられた場合、これは再び単一のブロック書き込みに変わることが可能である。

クリーンアップ段階（図２の２０６）の間、すなわち一旦新しいコードがインストールされ、実行されると、古いコードからの先のテーブル、およびすべての静的ツリーのためのサブ・ツリーはルート・アドレスを除いて削除され、メモリが回収される（ステップ４０８）。一旦このメモリが回収されると、新しいコードからの静的ツリーは、通常の優先順序に基づいて、この空きスペースの中で再構築される。このことを行うために、すべての静的ツリーのための規則は、新たなテーブルに記憶され、再び習得されることを必要としてもよい。

「静的ツリー」の概念を使用することは、運転中アップグレード以外に、ネットワーク・プロセッサ動作において利点がある。例えば、（定義によって、実行時に変更されることが不可能な）静的ツリーは、処理能力を最大限にして、メモリの使用を最小にすることを実現するためのより良い分析と最適な配置とに役立つ。

２．非静的ツリー
「静的」と定義されないすべてのツリーは、実行時に変化するか、または（アプリケーションによって）管理される、「非静的」または動的なものであるとみなされる。したがって、非静的ツリーはアップグレードで再構築されることはない。そのようなツリーの例は、ルーティング・テーブルおよびアクセス制御リストを含む。これらのツリーに対して行われる唯一の変更は、（別の機能へジャンプする）新しいコードへの任意の機能参照をアップデートすることである。これらの機能参照は、フロー機能のためのものである。ツリーのルート・アドレスは変わることがないので、ツリー対ツリーの参照はアップデートされることを必要としない。

しかしながら、これらの非静的ツリーは非常に大きい（ルーティン・テーブル）場合があるので、単一の機能参照が何千ものノードの中で複製されてもよい。時間が制限されるやり方で、これらの参照をトラバースしたり、アップデートしたりすることはできない。その代わり、図５に示されるような以下の方法が使用される。

非静的ツリーによって参照される各フロー機能のために、ツリー・メモリに間接指定アドレスが割り当てられる。通常、この間接指定アドレスは単に古いコードからフロー・アドレスに切り換えられる（ステップ５０２）。準備段階（図２の２０２）では、好ましくは終わりの方で、すべての非静的ツリーはトラバースされ、任意のフロー機能参照はフローの間接指定アドレスを示すために変更される（ステップ５０４）。この時点で、すべてのツリーは依然として、追加の命令ペナルティを伴う古いコードを参照している。ここで、これらの間接指定命令は、（新たなコードからの）フローのための新たなアドレスを示すためにアップデートされるが、書き込みは待ち行列に入れられ（記憶され）、ハードウェアに伝達されることはない。

アップデート段階（図２の２０４）の間、これらの待ち行列に入れられた書き込みはＮＰに書き込まれる（ステップ５０６）。これらのアドレスが連続している場合、このプロセスは単一のブロック書き込みで行われることが可能である。

アップデート段階が一旦完了すると、ハードウェアはすべての新たなコードを実行し、ツリーは追加の命令ペナルティを伴う新しいアドレスを参照する。この時点で、クリーンアップ段階（図２の２０６）においてツリーは再びトラバースされ、間接指定アドレスへの参照は真の機能アドレスと置き換えられる（ステップ５０８）。

任意の新たな静的ツリー（すなわち、アップデートされたコードのバージョンには全く存在しない静的ツリー）は、静的ツリーのための全般的な機構によって処理されるということを理解されたい。任意の新たな非静的ツリーは、通常の優先順序によって準備段階の間に構築される。メモリが著しく断片化されている場合、これらのツリーのためにルート・テーブル構造を割る当てることができなくてもよいということは可能である。ＡＰＩは、テーブルのサイズを小さくすることを試みるバックオフ方式を用いてもよい。４ビットのテーブルでさえも割り当てることができない場合、アップグレード・プロセスのエラーとして扱われる。ユーザは変更の必要性に適応するために、最初の分類プログラムでいくつかのダミー・ツリーを定義してもよい。新しいコードから削除された任意のツリーは解放され、メモリが回収される。

明らかに、本発明の段階的な運転中アップグレード方法に関連するダウン・タイムの量は、アップデート段階の間に実行される書き込み動作の数に関係している。アップデート段階の間、各ツリーのためのルート・アドレス、および各機能参照のための間接指定テーブルは、メモリに書き込まれる。１Ｋのツリーと１Ｋのフローとを最大とすると、多くとも２Ｋのアドレスがアップデートのために存在する。しかしながらアップデートの数はもっと少なくてもよい。これらのアドレスは単一のブロックとして列の中に割り当てられることが可能であり、ブロック全体は単一の直接メモリ・アクセス（ＤＭＡ）転送としてネットワーク・プロセッサに書き込まれることが可能である。すなわち、フロー・コード、静的ツリー・コードおよび非静的ツリー・コードをアップグレードするために必要なすべての書き込みは、好ましくは単一のＤＭＡ転送として実行されることが可能である。

本明細書では、本発明の例示的実施形態が添付の図面を参照して説明されてきたが、本発明がそれと寸分違わない実施形態に限定されるわけではなく、本発明の範囲または精神から逸脱することなく、様々なその他の変更および修正が当業者によって行われてもよいことを理解されたい。

本発明の実施形態が実装されてもよいパケット処理システムを示すブロック図である。 本発明の実施形態による、ネットワーク・プロセッサに関連するソフトウェアの運転中アップグレードのための展開手順を示すブロック図である。 本発明の実施形態による、ネットワーク・プロセッサに関連するフロー・コードの運転中アップグレードのための展開手順を示すフロー図である。 本発明の実施形態による、ネットワーク・プロセッサに関連する静的ツリー・コードの運転中アップグレードのための展開手順を示すフロー図である。 本発明の実施形態による、ネットワーク・プロセッサに関連する非静的ツリー・コードの運転中アップグレードのための展開手順を示すフロー図である。

Claims (10)

1. パケット・プロセッサに関連するメモリに記憶可能で、前記パケット・プロセッサ上で執行可能な、第１コード・バージョンから第２コード・バージョンへのコードの運転中アップグレードを実行するための方法であって、
   前記第１コード・バージョンから前記第２コード・バージョンへの前記コードのアップグレードを達成するために、１つまたは複数の書き込み動作を生成することによって前記アップグレードの準備を行うステップと、
   前記１つまたは複数の書き込み動作を前記パケット・プロセッサに伝達することによって、前記第１コード・バージョンから前記第２コード・バージョンへ前記コードをアップデートするステップと、
   前記アップデートステップの後に利用可能な１つまたは複数のメモリの場所を回収することによって、前記アップデートステップの後にクリーンアップを行うステップとを含み、
   前記準備ステップと前記アップデートステップと前記クリーンアップステップとが、前記パケット・プロセッサに関連する前記メモリの中で、前記コードのうちの単一のバージョンの記憶領域のみを必要とする方法。
2. アップグレードされる前記コードは１つまたは複数の処理要素を含み、前記アップデートステップは、各処理要素のために、前記処理要素の執行に対して責任を負う前記パケット・プロセッサの少なくとも一部の動作を中止することをさらに含む請求項１に記載の方法。
3. 前記アップデートステップは、各処理要素のために、前記処理要素に関連する前記１つまたは複数の書き込み動作を前記パケット・プロセッサに伝達することをさらに含む請求項２に記載の方法。
4. 前記アップデートステップは、各処理要素のために、前記パケット・プロセッサの中止された部分の動作を再開することをさらに含む請求項３に記載の方法。
5. 前記処理要素は、機能上分離したコードのブロックを含む請求項４に記載の方法。
6. 前記第１コード・バージョンは古いコード・バージョンを含み、前記第２コード・バージョンは新しいコード・バージョンを含む請求項１に記載の方法。
7. 前記パケット・プロセッサ上で執行可能な前記コードは、パケット分類機能を執行するためのコードを含む請求項１に記載の方法。
8. パケット・プロセッサに関連するメモリに記憶可能で、前記パケット・プロセッサ上で執行可能であり
   第１コード・バージョンから第２コード・バージョンへのコードのアップグレードを達成するために、１つまたは複数の書き込み動作を生成することによって前記アップグレードの準備を行うステップと、
   前記１つまたは複数の書き込み動作を前記パケット・プロセッサに伝達することによって、前記第１コード・バージョンから前記第２コード・バージョンへ前記コードをアップデートするステップと、
   前記アップデートステップの後に利用可能な１つまたは複数のメモリの場所を回収することによって、前記アップデートステップの後にクリーンアップを行うステップとを含むプロセスによって、第１コード・バージョンから第２コード・バージョンへアップグレードされるコードを有するように構成されたパケット・プロセッサであって、
   前記準備ステップと前記アップデートステップと前記クリーンアップステップとが、前記パケット・プロセッサに関連する前記メモリの中で、前記コードのうちの単一のバージョンの記憶領域のみを必要とするパケット・プロセッサ。
9. アップグレードされる前記コードは１つまたは複数の処理要素を含み、前記アップデートステップは、各処理要素のために、前記処理要素の執行に対して責任を負う前記パケット・プロセッサの少なくとも一部の動作を中止することをさらに含む請求項８に記載のパケット・プロセッサ。
10. 前記第１コード・バージョンは古いコード・バージョンを含み、前記第２コード・バージョンは新しいコード・バージョンを含む請求項８に記載のパケット・プロセッサ。

Images