JP2008289185A - ネットワーク経路処理方法及びネットワーク経路処理装置 - Google Patents

Abstract

【課題】経路制御プログラムを通信パケット内に埋め込んだプログラマブルパケットを利用したネットワーク経路処理方法及びネットワーク経路処理装置を提供する。
【解決手段】ヘッダ部とデータ部からなる通信パケットを受信し、ヘッダ部に設けられる通信パケットの転送経路を記述した経路制御プログラムを格納する。次に、通信パケットを受信した通信ノードで格納された経路制御プログラムを読み出し、この経路制御プログラムを解釈、処理を行う。そして、転送された通信パケットの経路制御プログラムから、次に転送する通信ノードを決定して、通信パケットを転送する。
【選択図】図１

Description

本発明は、通信パケットにその転送経路を記述する経路制御プログラムを持たせて、その経路制御プログラムに従ってネットワーク上の複数の通信ノードに通信パケットを送信するようにしたネットワーク経路処理方法及びネットワーク経路処理装置に関する。

一般に、ネットワークを用いてデータのやり取りを行う方法としては、パケット通信が普及している。パケット通信用のプロトコルとしては、物理層からアプリケーション層までさまざまなプロトコルがあり、例えば、インターネット通信のＴＣＰ／ＩＰ、ホームページを参照するときのＨＴＴＰあるいはメール通信用のプロトコルであるＳＭＴＰなどはよく知られている。これらのプロトコルは、世界各国から多くの専門家が集まり長年の検討を経て標準化されたものである。

しかし、一般のユーザから見ると、標準化されたプロトコルをそのままの状態で利用することは逆に不便となることが起こりうる。例えば、ＨＴＴＰでどこかのホームページにアクセスする場合などで特別にセキュリティーを考慮したい場合や、インターネットで電子会議を行う場合などで標準の通信プロトコルを変更して利用したいなどの要求が起こることがある。そこで、従来から、標準化を待つことなく、通信プロトコルを動的に変更する方法が検討され、その手法としてアクティブネットワーク手法が開発された。
アクティブネットワークは、通信プロトコルの動的配布及び変更能力をもつネットワークであり、ネットワーク内に設けられたルータでアプリケーション層までの処理を実行させることができるものである。アクティブネットワークは、いわば、ネットワーク自体をプログラム化して取り扱うことができるネットワークであるということができる。

このアクティブネットワーク手法としては、通信ノードの通信制御プログラムを動的に変更できるようにしたアクティブノード（プログラマブルノード）手法と、通信パケットにパケット制御プログラムを内蔵させたアクティブパケット（プログラマブルパケット）と呼ばれるものとがある。アクティブノード手法としては、Ｊａｖａ（登録商標）言語による通信プロトコルの配置を行うＭＩＴ（Massachusetts Institute of Technology）のＡＮＴＳ（Active Network Script）や、Ｊａｖａ（登録商標）言語によるネットワーク管理を行うコロンビア大学のＮｅｔＳｃｒｉｐｔなどが代表的である（例えば、非特許文献１を参照。）。

ルータや端末などの通信ノードでは、通常その内部に通信プロトコルを実現するソフトウエアを持ち、このソフトウエアによる通信プロトコルに従って通信処理を行っている。上記ＡＮＴＳのようなアクティブノード手法では、通信パケットの経路処理を行うルータ上に、プロトコル処理プログラムを必要に応じて所定のサーバからダウンロードする機構が導入されている。そして、その通信ノードが通信パケットを受け取るとその通信パケットが要求するプロトコルを調べ、その通信ノードがそのパケットが要求するプロトコルを持っていない場合には、サーバからダウンロードし、そのプロトコルにより当該通信パケットを次の転送先ノードに送信する。すなわち、新しいプロトコルを定義したソフトウエアを外部から当該通信ノードに導入し、既存のソフトウエアと入れ替えて利用するようにしている。

また、アクティブパケット（プログラマブルパケット）手法としては、例えば、ＢＢＮ TechnologyのSmart Packetsやペンシルベニア大学で開発されたＰＬＡＮ（A Packet Language for Active Networks）が知られている（例えば、非特許文献２を参照）。Smart PacketsはＣ言語などの手続き型言語によって通信制御を行うものであり、ＰＬＡＮは関数型言語によってパケットの移動経路を記述したものである。これらのアクティブパケットは、通信パケットそのものにプロトコルを埋め込んだプログラム付のパケット、つまりプログラマブルパケットを実現するものである。

一般に、通常の通信パケットにおいては、そのヘッダ部分に受信先コンピュータのネットワークアドレスが書き込まれ、ルータなどのネットワークノードはそのアドレスを読んで次の転送先を決定する。アクティブパケット手法に用いられるアクティブパケット（プログラマブルパケット）ではヘッダ部分にアドレスの代わりにそれ自身の転送を制御する経路処理プログラムが書き込まれている。そして、このプログラマブルパケットがルータなどの通信ノードに転送されると、その通信ノードは、予め用意されたプログラムの解釈実行システムを通じて、そのパケットのヘッダ部分にあるプログラムを実行して次の転送先を決定する。この結果、パケットがそれ自身の転送方法を定義できるようになる。

このように、ＡＮＴＳでは、各通信ノード上にＪａｖａ（登録商標）言語の実行系とソフトウエア置換機構を予め配置しておく。そして、各通信ノードはパケットを受け取ると、そのパケットに示されたプロトコル識別子を基にして、そのパケットの通信手順を定義するプロトコルを実装したＪａｖａ（登録商標）言語プログラムを、ネットワーク上の専用サーバからダウンロードする。そしてダウンロードしたプログラムに従って受け取ったパケットを処理する。

図１５は、従来のプログラマブルノードを用いたネットワークシステムであるＡＮＴＳの例を示したものであり、このシステムは、通信元コンピュータ端末１００、配信先コンピュータ端末１０１、通信制御プログラムの配布サーバ１０２、中継通信ノードであるルータ１０３、１０４から構成される。このシステムによれば、通信元コンピュータ端末１００から、ルータ１０３に対して通信パケット１０５とそのパケットの処理に必要なプロトコルが記述された通信制御プログラム１０６が送信される（１）。ルータ１０３は、パケット１０５と通信制御プログラム１０６を受信すると、配布サーバ１０２に対してこのパケット１０５の処理に必要なプロトコルを持つ処理プログラムの転送要求を行う（２）。

配布サーバ１０２は、上記ルータ１０３からのプログラム転送要求を受けて、そのパケットの処理に必要なプログラムをルータ１０３に転送する（３）。ルータ１０３は処理が終了したパケット１０５を次のルータ１０４に送る（４）。そして、このパケット１０５を受け取ったルータ１０４は、ルータ１０３と同様に配布サーバ１０２に対してパケットを処理するためのプログラムの転送要求を行う（５）。配布サーバ１０２は、上記ルータ１０４からのプログラム転送要求を受けて、処理に必要なプログラムをルータ１０４に転送する（６）。
なお、この従来システムにおいては、パケット単位で通信処理を変更する場合、その都度、配布サーバ１０２に対して通信制御プログラムの転送要求を行い、配布サーバからプログラムを転送してもらわなければならないので、伝送効率が悪いという問題がある。

図１６は、プログラマブルパケットの従来例と本発明の比較を示したものであり、 図１６Ａは、１９９７年に発表されたペンシルベニア大学のＰＬＡＮに用いられているプログラマブルパケット、図１６Ｂは、比較のために示した本発明で用いられるプログラマブルパケットの例である。

図１６Ａに示されるように、通信パケット１０５はデータ部１０７とヘッダ部１０８に分かれており、ヘッダ部１０８はプログラム部１０９と付加情報１１０を保有している。このプログラム部１０９には、宛先アドレスの代わりにパケット自身の経路を決める経路制御プログラム１１１が埋め込まれている。図１６Ａに例示されているプログラムはＰＩＮＧ機能を持つプログラムである。ＰＩＮＧ機能とは、宛先に届いたらパケットを送信元に戻す機能であり、このプログラムの例では、プログラム中の変数ｓｒｃに送信元ノード名を格納し、変数ｄｅｓｔに宛先ノード名を格納する。すなわち、このパケットは変数ｓｒｃに格納されるノードから変数ｄｅｓｔに格納されるノードに転送され、その後、再び変数ｓｒｃに格納されるノードに戻ってくるプログラムである。

このように、従来の経路制御プログラム１１１は、汎用的なプログラミング言語で記述されたものであり、汎用的な言語である点で記述能力に優れている反面、パケットに占めるバイト数が多くなるという問題があった。

図１６Ｂは、後述する本発明で用いられるプログラマブルパケットであるが、このパケットを転送するプログラムは、例えば「ｓとｄを変数とすると、変数ｓに格納されるノードから変数ｄに格納されるノードに転送され、その後、変数ｓに格納されるノードに戻って終了する。」というプログラムは、「ｓ；ｄ；ｓ；０」とノード名を記述するだけで完了する。この意味で従来の記述（図１６Ａ）に比べて大幅に短縮される。

David Tennenhouse and David J. Wetherall(Massachusetts Institute of Technology) HYPERLINK "http://nms.lcs.mit.edu/activeware/" インターネット＜ＵＲＬ：http://nms.lcs.mit.edu/activeware/＞ Scott M. Nettles and Carl A. Gunter（University of Pennsylvania） インターネット＜ＵＲＬ：HYPERLINK http://cis.upenn.edu/￣dsl/PLAN/＞

しかしながら、ＡＮＴＳに代表される従来のシステムにおいては、パケットを処理するプログラムが通信ノードにないときは、パケットのプロトコル種別ごとに、その処理プログラムをサーバから発見し、それをダウンロードする必要があった。このため、多様なプロトコルを利用する場合には、通信遅延などが起こり、その結果通信コストが大きくなるという問題があった。

また、ＡＮＴＳやＮｅｔＳｃｒｉｐｔを含む既存のアクティブノード手法では、ノード単位のプロトコルの動的変更は可能であるが、パケット単位でこの変更を行うことはできない。すなわち、ネットワークには多様なデータがパケットとして流されるが、アクティブノード手法は、通信ノード上のソフトウエアを入れ替えるものであるため、ノードに送られてくるパケット単位にプロトコルを変更することはできなかった。

また、上述したように、既存のプログラマブルパケット手法では、Ｃ言語等の汎用プログラミング言語を使用しているため、むしろその記述能力が優れている点が弊害となっていた。例えば、図１６Ａのプログラマブルパケットのように、通信パケット１０５内にネットワーク内で移動する経路を示す経路制御プログラム１１１を埋め込んだプログラム部１０９を持つようになると、プログラム部分のバイト数が増え、パケット自体のバイト数が増えてしまうという問題が生じる。すなわち、パケット通信においてパケット１０５自体の情報量が増えることはその分伝送速度の低減につながるという問題あった。また、仮にパケット１０５の大きさを固定とすれば、データ部１０７に分配されるバイト数が少なくなり、データ部１０７が圧縮されて伝送できる情報量が低減されるという問題があった。

すなわち、通信パケットは伝送スピード及び伝送効率から、そのサイズには制限がある（例えば１．５ＫＢ程度）。このため、パケットに埋め込まれるプログラムは最小化される必要があるが、これらの汎用プログラミング言語は記述能力が高い分、プログラムサイズが増大してしまうのである。そして、そのことが、パケットの大部分を経路制御プログラムが占有してデータサイズを圧迫する原因となっていた。また、データサイズを同程度に維持しようとすると、パケットサイズが増大することになり、伝送速度や伝送効率を悪化させるという問題があった。

また、汎用プログラミング言語は記述能力が高いので、通信ノード内のアクセスが容易となり、安全な実行が難しくなるという問題もあった。つまり、汎用型または関数型プログラミング言語により経路処理プログラムを記述することはセキュリティー上での問題がある。更に、プログラマブルパケットを受信した中間ノードは、そのプログラムを実行して次の宛先ノードを決定する必要があるが、記述能力の高い言語ほどその実行システムは大きくなり、ノード側処理を増大させ、実行速度が遅くなり、結果として通信遅延が大きくなるという問題もあった。

このように、既存のプログラマブルパケット手法ではＣ言語などの手続き型の汎用プログラミング言語やＭＬ（Markup Language）などの関数型プログラミング言語をもとにした言語を前提としているため、必ずしも経路制御記述に向いているとはいえず、記述自体の冗長性が高く、プログラムサイズ及び実行コストが大きくなっていた。

本発明は、これらの問題に鑑みてなされたものであり、汎用プログラミング言語を利用することなく、したがってパケットサイズを大きくすることのない専用言語を用いての経路記述を可能とするとともに、この専用言語により記述された経路制御プログラムをパケット内に埋め込んだプログラマブルパケットをパケットプールに複数格納し、このパケットプールに格納されたプログラマブルパケットの中から経路要求に応じたパケットが簡単に選択して経路処理を行うネットワーク経路処理方法及びネットワーク経路処理装置を提供することを目的とする。

上記課題を解決し、本発明の目的を達成するため、本発明のネットワーク経路処理方法は、ヘッダ部とデータ部からなる通信パケットを受信し、ヘッダ部に設けられる通信パケットの転送経路を記述した経路制御プログラムを格納するステップと、格納された前記経路制御プログラムを読み出して、前記経路制御プログラムを解釈し処理するステップとを備え、このプログラムを解釈し処理するステップは、転送された通信パケットの経路制御プログラムから、次に転送する通信ノードを決定して、通信パケットを転送するステップを含むことを特徴としている。

また、本発明のネットワーク経路処理装置は、ヘッダ部とデータ部からなる通信パケットを受信し、このヘッダ部に設けられる通信パケットの転送経路を記述した経路制御プログラムを格納するプログラム格納部と、このプログラム格納部に格納された経路制御プログラムを読み出して、経路制御プログラムを解釈し処理するプログラム処理部とを備え、このプログラム処理部において、転送された通信パケットの経路制御プログラムから、次に転送する通信ノードを決定して、通信パケットを転送するパケット転送装置を備えていることを特徴としている。

更に、本発明のネットワーク経路処理方法またはネットワーク処理装置の好ましい形態としては、経路制御プログラムが、通信パケットが転送されるノード名で記述されており、転送先の通信ノードにおいて経路制御プログラムに従った解釈処理が行われた後に、解釈処理を行ったノード名の通信ノードに前記通信パケットを転送することを特徴としている。

また、本発明のネットワーク経路処理方法またはネットワーク処理装置の好ましい形態としては、通信パケットを受信した通信ノードは、そのパケット経路制御プログラムに従った解釈処理を行った後に、解釈処理の終了したノード名を経路制御プログラムから除いて、経路制御プログラムから除いたノード名の通信ノードに通信パケットを転送することを特徴としている。

更に、本発明のネットワーク経路処理方法またはネットワーク処理装置の好ましい形態としては、通信パケットを受信した通信ノードは、経路制御プログラムに従った解釈処理を行った後に、経路を示す列の何番目の記号まで転送したかを示す番号を経路制御プログラムに付記し、この番号が付記されたノード名の通信ノードに通信パケットを転送するとともに、その通信パケットを受け取った通信ノードでは、その番号が示す次の経路から解釈処理を行うことを特徴としている。

また、本発明のネットワーク経路処理方法またはネットワーク処理装置の好ましい形態としては、通信ノードにおいて経路制御プログラムの変数の解釈処理を行った後に、この解釈処理の終了した変数名を経路制御プログラムから除いて、処理の終了した通信ノードに通信パケットを転送することを特徴としている。

また、本発明のネットワーク経路処理方法またはネットワーク処理装置の好ましい形態としては、通信ノードにおいて経路制御プログラムの変数の解釈処理を行った後に、経路制御プログラムの経路列の何番目の記号まで転送したかを示す番号を経路制御プログラムに付記して、この番号が付記されたノード名の通信ノードに通信パケットを転送するとともに、この転送された通信パケットを受け取った通信ノードにおいて、この番号が示す次の経路から解釈処理を行うことを特徴としている。

なお、本発明のネットワーク経路処理方法及びネットワーク経路処理装置に共通の好ましい形態において利用される経路制御プログラムは、経路記述専用のプログラミング言語により転送先及び転送順序を記述するものであることを特徴としている。

本発明のネットワーク経路処理方法またはネットワーク経路処理装置によれば、各通信ノードにおいて経路制御プログラムの処理が行われるごとに、経路制御プログラムからそのノード名が取り除かれるか、処理が行われたノード名までの番号が付記されるので、間違って同じ通信ノードに転送されることがない。

また、本発明のネットワーク経路選択方法、ネットワーク経路処理方法、ネットワーク経路選択システム及びネットワーク経路処理装置に共通に用いられるプログラマブルパケットの経路制御プログラム及び外部から受信される経路要求プログラムは、汎用的プログラミング言語あるいは関数型プログラミング言語ではない本発明者が独自に開発した経路記述専用のプログラミング言語を用いているので、プログラムサイズを極小に抑えることができる。また、両社の比較対照が容易となるため、パケットプールから経路要求を満足するパケットの選択も極めて簡単に行うことができる。

また、本発明のネットワーク経路処理方法及びネットワーク経路処理装置によれば、経路制御プログラムが転送先となるノード名をその転送順序に従って並べた列として記述されるため、その記述サイズを短くするとともに、実行箇所を明示することができる。

本発明のネットワーク経路処理方法及びネットワーク経路処理装置の好ましい形態によれば、経路制御プログラムにノード名を直接記述する代わりに関数として変数名と変数に対応するノード名を記述しているので、予め通信パケットを転送する順序を固定することなく、転送先ノードで次の転送先ノードを決定することが可能である。このため、ネットワークのトラフィック事情等を考慮した柔軟な転送先ノードの決定を行うことができる。

以上説明したように、一般的なプログラマブルパケットは、経路プログラムを保有している分、パケットサイズの増大（またはデータ領域の圧迫）や転送コストの増大を招くが、本発明のネットワーク経路処理方法及び経路処理装置に用いられるプログラマブルパケットは、経路記述に簡単な専用言語を用いるため、プログラマブルパケットのサイズを大幅に小さくすることができる。

また、本発明のネットワーク経路処理方法またはネットワーク経路処理装置によれば、各通信ノードにおいて経路制御プログラムの処理が行われるごとに、経路制御プログラムからそのノード名が取り除かれるか、処理が行われたノード名までの番号が付記されるので、間違って同じ通信ノードに転送されることがない。

まず、本発明の実施の形態であるネットワーク経路処理方法及びネットワーク経路処理装置について説明する前に、その前提となるネットワーク経路選択を行う方法について説明する。
図１は、ネットワーク経路選択を行うシステムの全体構成図を示したものである。このネットワーク経路選択システムにおいては、パケットプール１が、ネットワーク２を介して通信ノードａ、ｂ、ｃと接続されている。パケットプール１は、一種のサーバのようなもので、ヘッダ部３とデータ部４から構成される複数のプログラマブルパケット５と、外部からの経路要求プログラム（リクエスト）６を受け取る経路要求入力部７と、外部からの経路要求プログラムとプログラマブルパケット５のヘッダ部３に記憶された経路制御プログラムとを比較する比較装置８から構成されている。

また、通信ノードａ、ｂ、ｃは、外部から転送されてくるプログラマブルパケット５が順番に記憶される待ち行列記憶部９と、この待ち行列に記録されているプログラマブルパケット５を読み出して処理のための解釈を加える経路解釈部１０と、経路解釈部１０で経路制御プログラムを解釈した結果をもって、次の転送先の通信ノードに転送するパケット転送装置１１から構成される。

図２は、本発明のネットワーク経路選択方法及びネットワーク経路選択システムに用いられるプログラマブルパケット５の構造を示したものであり、このプログラマブルパケット５のヘッダ部３は、パケットの転送先となる通信ノード名を記述した経路制御プログラムが格納されるプログラム格納領域１２と、変数名及び変数データを格納する変数名格納領域１３とから構成される。また、ヘッダ部３には、更に、送信元ホスト名を格納する送信元ホスト名格納領域１４及びバージョン番号を格納するバージョン番号格納部１５が設けられているが、これらの格納領域１４と１５は省略してもよい。

図３は本発明に利用されるパケットプール１の詳細な構成を示す図であり、比較装置７は木構造生成装置１６と木構造比較装置１７から構成されている。このパケットプール１に蓄積されている待機中のパケット５は、それぞれパケットの転送経路、すなわち経路制御プログラムが記述されたヘッダ部３と転送するデータが記憶されるデータ部４とから構成され、比較装置７において、ヘッダ部３に格納されている経路制御プログラムが、経路要求入力部６に入力される経路要求プログラムと比較される。

この比較は、まず木構造生成装置１６により経路要求プログラム及びそれと比較される経路制御プログラムの木構造が生成された後、木構造比較装置１７において両者の木構造の比較が行われる。

次に、図４に基づいて、本発明に用いられる経路用言語について説明する。図４に示す経路用言語は、経路要求用の言語と経路記述用の言語からなる。経路比較を容易にするために両者は類似した言語として構成されるが、経路記述用の言語は、経路要求用の言語を制限したものとなっている。そして、プログラマブルパケットには、経路記述用の言語で書かれた経路が予め与えられている。経路要求用の言語を経路記述用の言語を拡張したものとしているのは、経路要求には任意性を含ませることが必要であるからである。例えば、経路要求用の言語には「複数あるノードのうちの１つでも転送されれば十分である」とか、「複数ノードに転送する際に、その順番は問わない（任意でかまわない）」とか、「あるノードを通過する回数は任意の回数でかまわない」といった要求を表現できる記述性が求められるからである。

図４に示される経路要求用の言語で具体的に説明すると、符号ＥあるいはＦは、経路を示すものであり、「０」は移動終了を意味し、「ａ」は名前ａのノード（ホスト）への移動を意味する。ノードとしては通常のコンピュータ端末である場合とルータである場合とがある。経路Ｅ、Ｆは、通常はパケットを転送するノード名であることが多いが、２つのノードを関連付けた演算子を含む式である場合もある。したがって、単純に「ａ；０」と記述した場合は、ノードａにパケットを転送してから、そのパケットの転送を終了させることを意味する。

「Ｅ；Ｆ」（逐次合成）は、経路Ｅに従って移動した後に、経路Ｆに従って移動することを意味する。例えば、経路制御プログラムが「ａ；ｂ」と記述されたパケットは、まず、最初に通信ノードａにパケットが転送され、続いて通信ノードｂにパケットが転送されることを意味する。

また、「Ｅ＋Ｆ」（選択合成）は、経路Ｅまたは経路Ｆのどちらか一方に従って移動するが、その選択は処理内容によって明示的に決められていることを意味している。すなわち、この場合の選択基準は、両経路において最初に移動するノードが存在する経路を選択するようにする。例えば、ノードａとノードｂがあって、「ａ＋ｂ」と記述されると、ノードａまたはノードｂのいずれかに転送されるのであるが、ノードａが最初に移動する経路にある場合には、ノードａを選択し、ノードｂにはパケットの転送を行わない。

同様に、「Ｅ＃Ｆ」（非決定的選択合成）は、経路Ｅと経路Ｆのどちらか一方の経路を選択することを意味し、最初に移動するノードが存在する経路を優先的に選択するかどうかは問わない点が「Ｅ＋Ｆ」と異なっている。つまり、タスク依頼のＥとＦのどちらの経路を辿ってもよいことを意味する。例えば、ノードａ、ｂ、ｃに対してパケットに要求する経路が「（ａ＃ｂ）；ｃ」と記述されると、ノードａを経由してノードｃに行く経路と、ノードｂを経由してノードｃに行く経路のいずれかを選択的にとることを意味するが、どちらの経路を優先するかは問わない。

また、「Ｅ％Ｆ」（非決定的可換合成）は、経路ＥとＦの両方の経路をとることを意味するが、２つの経路のいずれを先にとるかは任意であることを意味している。つまり、タスク依頼の経路要求において、経路Ｅと経路Ｆの順序は入れ換えて移動してもよいことを示す。例えば、「（ａ％ｂ）；ｃ」と記述されたプログラムは、ノードａからノードｂを通ってノードｃに行く経路と、ノードｂからノードａを通ってノードｃに行く経路のいずれかの経路、すなわち「ａ；ｂ；ｃ」あるいは「ｂ；ａ：ｃ」のいずれかの経路をとること意味するプログラムである。

「Ｅ＆Ｆ」（非同期合成）は、経路Ｅと経路Ｆ移動を非同期に実行してもよいことを意味するプログラムである。言い換えると、経路Ｅの転送中に経路Ｆに従って転送されてもよく、またその逆でもよいことを意味する。

「Ｅ^＊」（閉包）は、タスク要求において、エージェントが経路Ｅによる転送を０回以上の任意の回数繰り返して行ってもよいことを意味する。

この言語は、ラベルつき遷移システムとしてその動作が定義され、以下のような自明な等価関係は構造合同性「≡」により予め定義される。
（１）０；Ｅ≡Ｅ
（２）Ｅ＋０≡Ｅ、Ｅ＋Ｅ≡Ｅ、Ｅ＋Ｆ≡Ｆ＋Ｅ、（Ｅ＋Ｆ）＋Ｇ≡Ｅ＋（Ｆ＋Ｇ）
（３）Ｅ＃Ｅ≡Ｅ、Ｅ＃Ｆ≡Ｆ＃Ｅ、（Ｅ＃Ｆ）＃Ｇ≡Ｅ＃（Ｆ＃Ｇ）
（４）Ｅ％０≡Ｅ、Ｅ％Ｆ≡Ｆ％Ｅ、（Ｅ％Ｆ）％Ｇ≡Ｅ％（Ｆ％Ｇ）
（５）Ｅ＆０≡Ｅ、Ｅ＆Ｆ≡Ｆ＆Ｅ、（Ｅ＆Ｆ）＆Ｇ≡Ｅ＆（Ｆ＆Ｇ）
（６）Ｅ^＊≡０＃（Ｅ；Ｅ^＊）

以上、経路要求用の言語について簡単な説明を行ったが、経路記述用の言語は経路要求用の言語の部分集合であるので、特に説明は要しない。

次に、図５と図６に基づいてパケットプールの中の経路が記述された複数のプログラマブルパケットの中から、経路要求に合致したプログラマブルパケットを選択するときの経路比較アルゴリズムについて説明する。
この選択は各パケットに記述されている転送経路（記述経路）と通信要求の転送経路（要求経路）が互いにその経路をたどれるかどうかを調べることによって行われる。

図５は経路要求プログラムまたは経路記述プログラムの木構造の生成について説明するための図である。
まず、経路記述と経路要求を木構造に展開する手順について説明する。ここで「ａ」はノード名、ＥとＦは経路記述または経路要求に対応した記号列である。
（１）「ａ；Ｅ」の形の時は、Ｅに対応した木構造につなげる１つの枝を持ち、その枝には「ａ」というラベルがついた直列木（「決定木」ともいう。）と呼ぶ木構造に展開する。
（２）「Ｅ＋Ｆ」の形の時は、ＥとＦは選択木と呼ぶ木構造に展開する。これはＥとＦに対応する木構造の根を結合したものを根とする木構造である。この選択木という木構造は、節から２本以上の枝があり、それぞれの枝に異なるラベルがついているものをいう。
（３）「Ｅ＃Ｆ」の形の時は、ＥとＦは非決定選択木と呼ぶ木構造に展開する。これはＥとＦに対応する木構造のどちらか一方を任意に選択する木構造である。この非決定選択木（「非決定木」ともいう。）の木構造は、節から２本以上の枝があり、それぞれの枝にはラベルがついているが、そのラベル名は同じである場合もある。
（４）「Ｅ％Ｆ」の形の時は、「Ｅ；Ｆ＃Ｆ；Ｅ」に変換した後、木構造に展開する。
（５）「Ｅ＆Ｆ」の形の時は、ＥとＦは並列木と呼ぶ木構造に展開する。これは経路Ｅと経路Ｆに対応する木構造を重ねたものとなるが、両木構造は排他的に選択されることはない。この並列木と呼ばれる木構造は、節から２本以上の枝があり、それぞれの枝にラベルがついているものである。このような木構造の比較では、それぞれの枝について並列に比較を行うようにしている。
（６）「Ｅ^＊」の形の時は、「０＃Ｅ；Ｅ^＊」に変換した後、木構造に展開する。

図５は、木構造に展開するアルゴリズムを示したフロー図である。
まず、最初に、経路要求または経路記述の用語に用いられている記号を読む（ステップＳ１）。次に、その記号がノード名か変数名かが判断される（ステップＳ２）。ここで、記号がノード名か変数名である場合は、ノード名をアーク（枝）の名前とし（ステップＳ３）、記号の左辺からなる部分経路から決定木を生成する（ステップＳ４）。

判断ステップＳ２で、記号がノード名または変数名でないと判断されると、次に記号が演算子「＋」であるか否かが判断される（ステップＳ５）。記号が「＋」であると判断されると、その「＋」の両辺（Ａ，Ｂ）から２つの部分経路ＡとＢを生成し（ステップＳ６）、この部分経路から選択木を生成する（ステップＳ７）。

判断ステップＳ５で、記号が演算子「＋」でないと判断されると、次に、記号が演算子「％」であるか否かが判断される（ステップＳ８）。記号が「％」であると判断されると、その「％」の両辺（Ａ，Ｂ）から２つの部分経路Ａ；ＢとＢ；Ａを生成し（ステップＳ９）、各部分経路から選択木を生成する（ステップＳ１０）。

判断ステップＳ８で、記号が演算子「％」でないと判断されると、次に、記号が演算子「＃」であるか否かが判断される（ステップＳ１１）。記号が「＃」であると判断されると、その「＃」の両辺（Ａ，Ｂ）から２つの部分経路ＡとＢを生成し（ステップＳ１２）、各部分経路から非決定木を生成する（ステップＳ１３）。

判断ステップＳ１１で、記号が演算子「＃」でないと判断されると、次に、記号が演算子「＆」であるか否かが判断される（ステップＳ１４）。記号が「＆」であると判断されると、その「＆」の両辺（Ａ，Ｂ）から２つの部分経路ＡとＢを生成し（ステップＳ１５）、各部分経路から並列木を生成する（ステップＳ１６）。

判断ステップＳ１４で、記号が演算子「＆」でないと判断されると、次に、記号が演算子「^＊」であるか否かが判断される（ステップＳ１７）。記号が「^＊」であると判断されると、部分経路Ａ＃Ａ^＊と０を生成し（ステップＳ１８）、各部分経路から選択木を生成する（ステップＳ１９）。

判断ステップＳ１７で、記号が演算子「^＊」でないと判断されると、次の記号を読み（ステップＳ２０）、判断ステップＳ２に戻る。以上の手順を経て、要求経路または記述経路に対応した木構造が生成展開される（ステップＳ２１）。

次に、図６に基づいて、経路要求と経路記述の木構造の比較のアルゴリズムについて説明する。この比較は経路要求と経路記述のそれぞれの対応する木構造を比較して経路記述が経路要求を満足するか否かを判断するためのものである。ここで経路記述が経路要求を満足するとは、経路記述が経路要求に示された必要な転送先ノードに、要求された転送順序で転送可能であり、逆に、経路記述が経路要求に示された以外のノードや、経路要求に示された転送順序以外の順序の転送を含まないことを意味する。

以下、図６に基づいて経路要求と経路記述の比較の手順を説明する。なお、ここでは、経路要求の木構造をＲ、経路記述の木構造をＳとして説明する。
まず、図５で説明したフロー図により、経路要求に対応した木構造Ｒと経路記述に対応した木構造Ｓが生成され（ステップＳ２２）、この２つの木構造が比較される（ステップＳ２３）。この比較は、木構造Ｒの根から伸びている枝のラベルと木構造Ｓの根から伸びている枝のラベルを比較することによって行われる。

まず、経路要求の木構造Ｒが直列木（決定木）であるか否かが判断される（ステップＳ２４）。木構造Ｒが直列木のときは、経路記述Ｓの部分木の節点が経路要求Ｒと同じラベルを持つかどうかを調べ（ステップＳ２５）、ラベルが一致したか否かが判断される（ステップＳ２６）。ここでは、ＳはＲと同じラベルを持った枝を持ち、ＲもＳと同じラベルを持った枝を持っていることが一致の条件となる。ラベルが一致した場合には、経路要求Ｒと経路記述Ｓの他の部分木について比較を行う（ステップＳ２８）。

判断ステップＳ２４で経路要求の木構造Ｒが直列木でないと判断されると、次に、木構造Ｒが選択木であるか否かが判断される（ステップＳ２９）。木構造Ｒが選択木のときは、選択木のすべての部分木の節点が経路記述の木構造Ｓの部分木と同じラベルを持っているか否かを調べる（ステップＳ３０）。ここで、同じラベルを持つとは、木構造Ｓがその選択可能なすべての枝について木構造Ｒのすべての枝と同じラベル名を持ち、かつ木構造Ｒも木構造Ｓが持つすべての枝について同じラベル名を持つことを意味する。次に、木構造Ｒと木構造Ｓに同じラベル名をもつ節点が存在しているか否かが判断され（ステップＳ３１）、同じラベルを持つ節点が存在していれば、経路要求Ｒと経路記述Ｓの他の部分木について比較を行う（ステップＳ３２）。

判断ステップＳ２９で経路要求の木構造Ｒが選択木でないと判断されると、次に、木構造Ｒが非決定選択木（「非決定木」あるいは「非選択木」という。）であるか否かが判断される（ステップＳ３３）。木構造Ｒが非決定木のときは、非決定木のすべての部分木の節点が経路記述の木構造Ｓの部分木と同じラベルを持っているか否かを調べる（ステップＳ３４）。ここで、木構造Ｒの枝が非決定木のときは、木構造Ｒの枝の１つ以上と同じラベルを持った枝を木構造Ｓも持っていることが必要条件である。次に、木構造Ｒと木構造Ｓに同じラベル名をもつ節点が存在しているか否かが判断され（ステップＳ３５）、同じラベルを持つ節点が存在していれば、経路要求Ｒと経路記述Ｓのそれぞれのラベルが一致した節を持つ他の部分木について比較を行う（ステップＳ３６）。この比較は、それぞれの木構造ＲとＳの同じラベル名のついた枝の先にある木構造についても同様に比較されることを意味する。

判断ステップＳ３３で経路要求の木構造Ｒが非決定選択木でないと判断されると、次に、木構造Ｒが並列木であるか否かが判断される（ステップＳ３７）。木構造Ｒが並列木のときは、並列木のすべての部分木の節点が経路記述の木構造Ｓの部分木と同じラベルを持っているか否かを調べる（ステップＳ３８）。ここで、木構造Ｒの枝が並列木のときは、木構造Ｒの枝の１つ以上と同じラベルを持った枝を木構造Ｓも持っていることが必要条件である。次に、木構造Ｒと木構造Ｓに同じラベル名をもつ節点が存在しているか否かが判断され（ステップＳ３９）、同じラベルを持つ節点が存在していれば、経路要求Ｒと経路記述Ｓのそれぞれの他の部分木について比較を行う（ステップＳ４０）。この比較は、それぞれの木構造ＲとＳにおいて、その一致したそれぞれの枝の先にある木構造を同様に比較し、かつ木構造Ｒにおいて一致した枝以外の先にある木構造と、木構造Ｓにおいて一致した枝以外の先にある木構造とを同様に比較することを意味する。

経路要求の木構造Ｒと経路記述の木構造Ｓの比較は上記ステップＳ２３からＳ４０を繰り返し、最終的にその木構造の末端までの比較が行われる（ステップＳ４１）。そして、経路記述の木構造Ｓが経路要求の木構造Ｒを満足すると判定された木構造Ｓがパケットプール１より選定される。ここで、経路要求の木構造Ｒを満足する経路記述の木構造Ｓが複数存在するときは、木の深さが最小となるものを選ぶことにより、必要な転送回数が最小となる経路記述を選択することができる。

判断ステップＳ２６でラベルが一致しないとき、及び判断ステップＳ３１、Ｓ３５、Ｓ３９で同じラベルを持つ節点が存在しないときは、経路要求の木構造Ｒを満足する経路記述の木構造はないと判断される（ステップＳ４２）。

次に、図７にもとづいて、本発明の実施の形態例としてのネットワークノード側の処理について説明する。図１のネットワーク経路選択の全体システムの構成図において既に説明したように、通信ノード側の構成は、プログラマブルパケット５が供給されて記憶される待ち行列記憶部９と、この待ち行列記憶部９に記憶されているパケット５を順番に取り出して処理する経路解釈部１０と、経路制御プログラムを処理した後に次の転送アドレスにパケットを転送するパケット転送装置１１から構成される。

ここで、経路解釈部１０は、待ち行列記憶部９から取り出したパケット５のヘッダ部３に記憶されている経路制御プログラムを読み出して入力するプログラム格納部１８と、プログラム格納部に格納された先頭記号を読み込むプログラム処理部１９と、プログラムに変数が使用されている場合にその変数がどのノードに対応しているかを示す変数−ノード対照テーブル２０から構成されている。

上述の通信ノードにおいて、読み込まれた経路の先頭の記号がノード名である場合の動作について説明する。まず、不図示のネットワークから転送されたプログラマブルパケット５は、到着順に待ち行列記憶部９に格納される。この待ち行列記憶部９に格納されたプログラマブルパケット５のヘッダ部３に記憶されている経路制御プログラムはプログラム格納部１８にいったん格納される。一例として、この経路記述プログラムは「ａ；ｂ；ｃ；０」というプログラムであるとする。すなわち、このプログラムを持つパケットは、最初通信ノードａに、次に通信ノードｂに、最後に通信ノードｃに転送されて終了するプログラムである。

次に、プログラム格納部１８に格納された先頭記号「ａ」がプログラム処理部１９に読み込まれる。プログラム処理部１９は、読み込んだ記号「ａ」が、次にパケットを転送するノード名であると解釈し、パケット転送装置１１とネットワーク２を介してこのパケットを通信ノードａに転送する。このとき、プログラム処理部１９は、この記号「ａ」を経路制御プログラムから除去し、転送するパケットに記録される経路記述プログラムを「ｂ；ｃ；０；０」とする。

次に、図８に基づいて、経路制御プログラムの先頭アドレスが変数名である場合について、本発明のネットワークノード側の処理を説明する。すなわち、図８の例では、待ち行列記憶部９に記憶されているパケット５の制御プログラムが、例えば「ｙ；ｂ；ｙ；０」のように変数「ｙ」を含む場合について説明する。

まず、変数名が含まれているプログラムが待ち行列記憶部９からプログラム格納部１８に格納されると、プログラム処理部１９は、この経路制御プログラムの経路を順に読み込み、これが変数名であれば変数―ノード対照テーブル２０からその変数名を探す。１番目の記号と３番目の記号「ｙ」は変数であり、変数−ノード対照テーブル２０から、これが通信ノードａを表していると認識する。そして、この認識結果に基づいて、パケット転送装置１１を介してネットワーク２に送信し、通信ノードａにこのパケット５を転送する。このとき、プログラム処理部１９は、この１番目の記号「ｙ」を経路制御プログラムから除去するとともに、３番目の記号「ｙ」をノード名「ａ」に書き換え、通信ノードａに転送するパケットの経路記述プログラムを「ｂ；ａ；０；０」に変更する。この変更された経路制御プログラムは、通信ノードａに転送された後に、通信ノードｂに転送され、再び通信ノードａに転送されて終了することを意味している。

次に、図７または図８に示す本発明の実施形態例におけるノード側のネットワーク経路処理の動作について、図９のフロー図に基づいて説明する。
まず、待ち行列記憶部９の先頭パケット５を処理し（ステップＳ５０）、そのパケットの経路制御プログラムを経路解釈部１０のプログラム格納部１８に呼び出す（ステップＳ５１）。

次に、この呼び出したパケットから経路記号を読み（ステップＳ５２）、その先頭記号が変数かどうかを判断する（ステップＳ５３）。先頭記号が変数である場合は、変数−ノード対照テーブル２０にその変数と対応するノード名があるか否かが判断される（ステップＳ５４）。この結果、変数に対応するノード名があれば、その経路の変数部分を対応するノード名で書き換え（ステップＳ５５）、次の経路記号を読む（ステップＳ５６）。判断ステップＳ５３で読み込んだ経路記号が変数でない場合は、ステップＳ５６に進み、次の経路記号を読む。

続いて、読み込んだ記号が経路の終端にあるか否かを判断する（ステップＳ５７）。読み込んだ記号が経路の終端であれば、次の記号を読み込み（ステップＳ５８）、続いてその記号がノード名か否かが判断される（ステップＳ５９）。このステップＳ５９でノード名でないと判断されると再びステップＳ５８に戻り、新たな記号を読み込む。

次に、判断ステップＳ５９で読み込んだ記号がノード名であると判断されれば、そのノード名を不図示のパケットの転送先候補リストに登録し（ステップＳ６０）、次の記号を読む（ステップＳ６１）。そして、記号がノード名であるか否かが判断される（ステップＳ６２）。この結果、読み込んだ記号がノード名であれば、再度ステップＳ６１戻って次の記号を読み込み、記号がノード名でなければ、記号が演算子であるか否かが判断される（ステップＳ６３）。

そして、判断ステップＳ６３で、記号が演算子であると判断されると、次の記号が読まれ（ステップＳ６４）、転送先の候補リストに登録される（ステップＳ６５）。そして、登録後はステップＳ６１に進み、次の記号を読む。

判断ステップＳ６３で、記号が演算子でないと判断されると、次に、記号が経路の終端のものか否かが判断される（ステップＳ６６）。経路の終端でなければ再びステップＳ６１に戻り、次の記号を読み、経路の終端であると判断されれば、続いて転送先候補リストが空、すなわち「０」か否かが判断される（ステップＳ６７）。

転送先の候補リストが空、すなわち「０」であれば、接続可能リストから１つのノードを選択し、転送先ノードに対応したノード名より後（右側）の部分経路にパケット内の経路を書き換える（ステップＳ６９）。そして、パケット転送装置１１より、パケットを選定したノードに転送する（ステップＳ７０）。

判断ステップＳ６７で、転送先候補リストが空でない場合は、候補に対応したノードと接続可能か否かが判断され（ステップＳ６４）、接続可能であれば、候補を接続可能リストに登録する（ステップＳ７２）。そして、その候補を転送先候補リストから削除し（ステップＳ７３）、判断ステップＳ６７に戻る。判断ステップＳ７１で候補に対応するノードと接続可能でないと判断された場合も判断ステップＳ６７に戻り、再び転送先の候補リストが空か否かが判断される。

次に、図１０に基づいて、ネットワークノード側処理について説明する。図７と図８に示すシステムでは、経路処理が終了したパケットを転送するノード名を経路制御プログラムから消去したが、図１０に示す例では、パケットの処理が終了したノードの経路番号を経路制御プログラムに書き込み、パケットが転送された経路を消去せずに記憶保持するようにしている。図７及び図８と共通の部分は同一符号を付して示す。

この例では、プログラマブルパケット５のヘッダ部３は経路制御プログラムを格納するプログラム格納領域１２と、既に処理が行われた経路の番号を記録する実行位置番号格納部１２ａを備えている。図１０の例では、ノードａからノードｂに到着するパケット５のヘッダ部３のプログラム格納領域１２に「ａ；ｂ；ｃ」という経路制御プログラムが記述されており、実行位置番号格納部１２ａに「２」という数字が記憶されている。このプログラムは、「ノードａに転送された後、ノードｂに転送され、最後にノードｃに転送される。」ことを意味するプログラムであり、実行位置番号格納部１２ａに記憶されている「２」という数字は、既に１番目の経路処理が終了して、転送先の通信ノードにおいて２番目の経路処理を行うことを示している。

したがって、このパケット５はノードａから現在の処理ノードｂに転送されたことがわかり、待ち行列格納部９に記憶されている先頭パケットはノードｂの経路解釈部１０のプログラム格納部１８に読み込まれる。経路解釈部１０のプログラム処理部１９は、まず、プログラム格納部１８に読み込まれた実行位置番号「２」を読み込み、かつ処理する実行位置番号の次にある経路記号「ｃ」を読み込む。

次に、実行位置番号記憶部１２ａに記憶されている実行位置番号「２」の次の経路をプログラム処理部１９で解釈した経路番号（ここでは経路ｃに対応する番号「３」）に変更し、これを実行位置番号記憶部１２ａに格納する。
こうして、次のノードに転送されるパケット５は、経路制御プログラムは「ａ；ｂ；ｃ」と実行位置番号「３」を有している。実行位置番号が「３」という数字なので、このパケット５は、２番目の経路ｂまで転送が終了し、次は３番目のノードｃに転送されることを意味する。すなわち、このように処理されたパケット５は、パケット転送装置１１を経て、ノードｃに転送される。

次に、図１１のフロー図に基づいて、図１０に示すような実行位置番号を書き換える例の動作について説明する。図１１のフロー図は、図９のフロー図と概略一致しているので、同じ部分は同一符合を付して説明する。
図１１において、ステップＳ５０からステップＳ５７までは図９のフロー図と同じであるので、その部分の説明は省略する。本例においては、図１１の判断ステップＳ５７で記号が終端であると判断された場合は、実行位置番号を読み取る（ステップＳ８０）。そして、実行位置番号にある記号を読み（ステップＳ８１）、記号がノード名か否かが判断される（ステップＳ５９）。以下、ステップＳ６０からＳ６４までは図９のフロー図と同じであるので説明を省略する。

判断ステップＳ６３で記号が演算子であると判断された場合は、次の記号を読み（ステップＳ６４）、転送先の候補とその経路上の位置をリストに登録する（ステップＳ８２）。
また、判断ステップＳ６７で転送先候補リストが空であると判断された場合は、接続可能リストから１つのノードを選択し（ステップＳ６８）、続いて転送先となったノードの経路上の位置を１つ足した数字を実行位置番号とする（ステップＳ８３）。ステップ７１からステップＳ７３の処理は図９と同じであるので省略する。

次に、図１２に基づいて、本発明のネットワーク経路選択方法を実現するシステムについて説明する。
ここでは、パケットプール１に蓄積されるパケット５は、パケット５ａ、５ｂ、５ｃの３つから構成されている。ネットワーク２には３つの通信ノード、例えば、ノードａ、ノードｂ、ノードｃが接続されている。

吹き出しの部分はパケット５ａ〜５ｃとリクエスト６に格納されている記述経路または要求経路を示している。すなわち、パケット５ａでは、「ａ；ｃ；０」、パケット５ｂでは「ａ；ｂ；ａ；ｃ；ａ；０」、パケット５ｃでは「ａ；ｂ；ｃ；ａ；０」と記述されている。リクエスト６は「ａ；（（ｂ；ｃ）＆ａ^＊）である。

次に、図１２に基づいて、本実施形態例であるネットワーク経路処理方法及び装置の前提となる、プログラマブルパケットの選択のシステムの動作について説明する。まず、ユーザからのリクエスト（転送要求）を受けると、パケットプール１において、リクエスト６が要求する要求経路を満足するプログラマぶるパケットが選択される。このパケットの選択は、すでに図５と図６で説明したように、要求経路と記述経路を木構造に展開して行われる。

この例では、ユーザのリクエストの経路「ａ；（（ｂ；ｃ）＆ａ＊）」に対して、パケットプール１の中のどのパケットをどのような手順で選択するかについて以下に説明する。

最初に木構造により要求経路と記述経路を比較する。ここでは木構造は特に示すことはしないが、ユーザからのリクエスト６は、ノードａに転送してからノードｂへ転送し、更にノードｃに転送せよというものであるが、「（ｂ；ｃ）＆ａ＊」の部分の要求経路は、ノードｂとノードｃへの転送中にノードａに任意回数転送されてよいことを意味している。このため、パケット５ｂに記述されている記述経路「ａ；ｂ；ａ；ｃ；ａ；０」はユーザのリクエスト６を満足する。また、パケット５ｃの「ａ；ｂ；ｃ；ａ；０」もユーザのリクエストを満足することになる。このように、複数のパケットがユーザのリクエストを満足する場合には、転送回数が最小のパケットが選択されるように予め定めておく。この結果、本例の場合は、パケット５ｃが選択され、ネットワーク２を経てノードａに転送される。

次に、本実施形態例のネットワーク経路処理方法及びネットワーク経路処理装置の前提となるネットワーク経路選択方法について、図１３と図１４のフロー図に基づいて説明する。図１３は、本発明によるプログラマブルパケット５の転送経路をパケットプール１に予め登録する方法を示すフロー図である。まず、プログラマブルパケット５はパケットプール１に転送される（ステップＳ１０１）。次に、パケットプール１は転送されたプログラマブルパケット５を格納する（ステップＳ１０２）。続いて、プログラマブルパケット５はそれ自身の転送経路を記述したプログラムのコピーをパケットプール１に通知し（ステップＳ１０３）、パケットプールはプログラマブルパケットの経路プログラムを受け取る（ステップＳ１０４）。

次に、パケットプール１はプログラマブルパケットから受け取った経路プログラムを木構造に変換し（ステップＳ１０５）、この変換した木構造をそれ自身のデータベースに登録する（ステップＳ１０６）。ここで、リクエスト６が到達した際に、その都度、各プログラマブルパケット５を木構造に変換して経路比較を行うこともできるが、それには転送するまでの時間も増えるので、パケットプール１にプログラマブルパケット５を登録する段階で木構造に変換して登録するようにしている。

図１４は、パケットプール１がユーザからのリクエスト６（転送要求）を受けたときのプログラマブルパケットの選択方法を示すフロー図である。パケットプール１に転送要求が来ると（ステップＳ１１０）、パケットプール１は転送要求中のデータを取り出すとともに、要求経路を示すプログラムを取り出す（ステップＳ１１１）。次に、要求経路を木構造に変換し（ステップＳ１１２）、続いて要求経路の木構造と予め登録されているパケット５の木構造を比較する（ステップＳ１１３）。この結果、要求経路を満足するパケットが選択され（ステップＳ１１４）、その選択したパケットに転送要求から取り出したデータを転送してパケットの選択が終了する（ステップＳ１１５）。

以上、本発明の実施形態例について説明したが、本発明はこの実施形態例に限定されるものではなく、特許請求の範囲に記載された本発明の要旨を逸脱しない限り、種々の変形例、応用例を含むことはいうまでもない。

本発明のパケットプール及び通信ノードの関係を示す全体システムの構成図である。 本発明に用いられるプログラマブルパケットの構造を示す図である。 本発明に用いられるパケットプールの構造を示す図である。 本発明に用いられる経路用言語を示す図である。 本発明に用いられる木構造の生成のアルゴリズムを示すフロー図である。 本発明に用いられる木構造の比較のアルゴリズムを示すフロー図である。 リクエストがノード名の場合のネットワークノード側の処理を説明するための図である。 リクエストが変数名を含む場合のネットワークノード側の処理を説明するための図である。 経路解釈を終えた経路を消去する場合の、ネットワークノード側における経路解釈、パケット転送処理を説明するためのフロー図である。 実行位置を記録する場合の本発明のネットワークノード側の処理を説明するための図である。 経路解釈を終えた実行位置の番号を記録する場合の、ネットワークノード側における経路解釈、パケット転送処理を説明するためのフロー図である。 プログラマブルパケットの選択方法を説明するための図である。 プログラマブルパケットをパケットプールに登録する方法を示すフロー図である。 プログラマブルパケットをパケットプールから選択する方法を示すフロー図である。 従来のプログラマブルネットワークの構成と作用を説明するための図である。 従来のプログラマブルパケットと本発明に用いられるプログラマブルパケットを比較して示す例である。

符号の説明

１・・・パケットプール、２・・・ネットワーク、３・・・ヘッダ部、４・・・データ部、６・・・リクエスト（経路要求）、７・・・経路要求入力部、８・・・比較装置、９・・・待ち行列記憶部、１０・・・経路解釈部、１１・・・パケット転送部、１６・・・木構造生成装置、１７・・・木構造比較装置、１８・・・プログラム格納部、１９・・・プログラム処理部、２０・・・変数−ノード対照テーブル

Claims (15)

1. ヘッダ部とデータ部からなる通信パケットを受信し、前記ヘッダ部に設けられる前記通信パケットの転送経路を記述した経路制御プログラムを格納するステップと、
   前記格納された前記経路制御プログラムを読み出して、前記経路制御プログラムを解釈し処理するステップと、を備えたネットワーク経路処理方法であって、
   前記プログラムを解釈し処理するステップは、転送された前記通信パケットの前記経路制御プログラムから、次に転送する通信ノードを決定して、前記通信パケットを転送するステップを含むことを特徴とするネットワーク経路処理方法。
2. 前記経路制御プログラムは、前記通信パケットが転送されるノード名で記述されており、転送先の通信ノードにおいて前記経路制御プログラムに従った解釈処理が行われた後に、前記解釈処理を行ったノード名の通信ノードに前記通信パケットを転送することを特徴とする請求項１に記載のネットワーク経路処理方法。
3. 前記通信ノードは、前記経路制御プログラムに従った解釈処理を行った後に、前記解釈処理の終了した前記ノード名を前記経路制御プログラムから除いて、前記経路制御プログラムから除いた前記ノード名の通信ノードに前記通信パケットを転送することを特徴とする請求項２に記載のネットワーク経路処理方法。
4. 前記通信ノードは、前記経路制御プログラムに従った解釈処理を行った後に、前記経路制御プログラムの経路列の何番目の記号まで転送したかを示す番号を前記経路制御プログラムに付記して、前記番号が付記されたノード名の通信ノードに前記通信パケットを転送するとともに、前記通信パケットを受け取った通信ノードにおいて、前記番号が示す次の経路から解釈処理を行うことを特徴とする請求項２に記載のネットワーク経路処理方法。
5. 前記経路制御プログラムは、前記通信パケットが転送される通信ノードのノード名及びそれを格納する変数、経路手順を規定する演算子からなる列として記述されており、前記通信ノードにおいて前記経路制御プログラムの解釈処理を行った後に、前記通信ノードに記憶されている変数とノード名の対照テーブルより次に転送されるノード名を確定し、前記確定した通信ノードに前記通信パケットを転送することを特徴とする請求項２または３に記載のネットワーク経路処理方法。
6. 前記通信ノードにおいて前記経路制御プログラムの前記変数の解釈処理を行った後に、前記解釈処理の終了した前記変数名を前記経路制御プログラムから除いて、前記処理の終了した通信ノードに前記通信パケットを転送することを特徴とする請求項５に記載のネットワーク経路処理方法。
7. 前記通信ノードにおいて前記経路制御プログラムの前記変数の解釈処理を行った後に、前記解釈処理の終了した前記変数名までの番号を前記経路制御プログラムに付記して、前記番号の付記された通信ノードに前記通信パケットを転送することを特徴とする請求項５に記載のネットワーク経路処理方法。
8. 前記経路制御プログラムは、経路記述専用のプログラミング言語により転送先及び転送順序を記述するものであることを特徴とする請求項１〜７のいずれかに記載のネットワーク経路処理方法。
9. ヘッダ部とデータ部からなる通信パケットを受信し、前記ヘッダ部に設けられる前記通信パケットの転送経路を記述した経路制御プログラムを格納するプログラム格納部と、
   前記プログラム格納部に格納された前記経路制御プログラムを読み出して、前記経路制御プログラムを解釈し処理するプログラム処理部と、
   を備えたネットワーク経路処理装置であって、
   前記プログラム処理部は、転送された前記通信パケットの前記経路制御プログラムから、次に転送する通信ノードを決定して、前記通信パケットを転送するパケット転送装置を
   備えていることを特徴とするネットワーク経路処理装置。
10. 前記経路制御プログラムは、前記通信パケットを転送する各通信ノードのノード名を順番に記述し配置するものであり、各通信ノードにおいて前記経路制御プログラムの解釈処理を行った後に、前記解釈処理を行ったノード名の通信ノードに前記通信パケットを送ることを特徴とする請求項９に記載のネットワーク経路処理装置。
11. 前記各通信ノードにおいて前記経路制御プログラムの解釈処理を行った後に、該解釈処理を行ったノード名を前記経路制御プログラムから除いて、前記解釈処理の終了したノード名の通信ノードに前記通信パケットを送ることを特徴とする請求項１０に記載のネットワーク経路処理装置。
12. 前記各通信ノードにおいて前記経路制御プログラムの解釈処理を行った後に、前記経路制御プログラムの経路列の何番目の記号まで転送したかを示す番号を前記経路制御プログラムに付記して、前記番号が付記されたノード名の通信ノードに前記通信パケットを転送するとともに、前記通信パケットを受け取った通信ノードにおいて、前記番号が示す次の経路から解釈処理を行うことを特徴とする請求項１０に記載のネットワーク経路処理装置。
13. 前記経路制御プログラムは、前記通信パケットが転送される通信ノードのノード名及びそれを格納する変数、経路手順を規定する演算子からなる列として記述されており、各通信ノードにおける前記経路制御プログラムの前記変数の解釈処理を行って、前記変数の解釈処理を行ったノード名の通信ノードに前記通信パケットを転送することを特徴とする請求項１０に記載のネットワーク経路処理装置。
14. 前記各通信ノードにおける前記経路制御プログラムの変数の解釈処理を行った後に、前記解釈処理を行った変数名を除去して、前記解釈処理を行った変数からノード名を確定し、前記確定した通信ノードに前記通信パケットを転送することを特徴とする請求項１３に記載のネットワーク経路処理装置。
15. 前記通信パケットに内蔵される前記経路制御プログラムは、経路記述専用のプログラミング言語により転送先及び転送順序を記述するものであることを特徴とする請求項１０〜１４のいずれかに記載のネットワーク経路処理装置。

Images