(57)【要約】【課題】キューイング装置において、動的かつ柔軟に優先制御の形態を変更可能にする。【解決手段】キューイング装置（優先制御処理部１６）は、入口から出口に至る経路において、直列に配置された、パイプラインステージを構成する複数のステージ６０であって、それぞれが同一の優先度を示す同一クラスの命令をカウントする機構をもつプロセッシングファンクション６５及びデータラッチ３０を有し、所定数のステージが、順方向に配置されるとともに、残りのステージが折り返し点から逆方向に配置されたステージと、分岐回路３２と、合流回路３８と、分岐路４１０とを備えている。データの優先度を示す情報およびデータ本体を含む命令が前記入口から投入されると、前記ステージ間を命令が伝達され、かつ、優先度及び命令の属するクラスのカウント値にしたがって、割り込みが行われる。【選択図】　図５
2004056451.tif 000002
【特許請求の範囲】
【請求項１】
入口から出口に至る経路において、直列に配置された、パイプラインステージを構成する複数のステージであって、それぞれが同一の優先度を示す同一クラスの命令をカウントする機構をもつプロセッシングファンクション及びデータラッチを有し、所定数のステージが、順方向に配置されるとともに、残りのステージが折り返し点から逆方向に配置されたステージと、
前記順方向の経路上において、各々が所定のステージ間に配置された、少なくとも１以上の分岐回路と、
前記逆方向の経路上において、各々が所定のステージ間に配置された、少なくとも１以上の合流回路と、
前記分岐回路の各々と、何れかの合流回路とを接続する分岐路とを備え、
データの優先度を示す情報およびデータ本体を含む命令が、前記入口から投入されると、前記ステージ間を、前記命令が順方向および逆方向に伝達され、かつ、前記優先度および前記命令の属するクラスのカウント値にしたがって、割り込みとして、順方向に配置された転送元のステージから、所定の分岐回路から分岐路および対する合流回路を経て、逆方向に配置された転送先のステージに命令が伝達されることを特徴とするキューイング装置。
【請求項２】
前記ステージは、前記命令の割り込みが生じた場合の転送元ステージのカウンタ値をａ、転送先ステージのカウント値をｘとおいたときに、ａ＝ｘ＋１の関係を満たせば、前記割り込みを行うよう構成されていることを特徴とする請求項１記載のキューイング装置。
【請求項３】
前記順方向の経路上に位置するプロセッシングファンクションは、伝達される前記命令が属するクラスに対応する転送元ステージのカウンタ値および転送先ステージのカウンタ値の差分をカウントする機構をさらに備えていることを特徴とする請求項１記載のキューイング装置。
【請求項４】
前記ステージは、前記命令の転送元ステージのカウンタ値をａ、差分カウンタ値をｙ、転送先ステージのカウンタ値をｘとおいたときに、ａ＝ｘ＋ｙの関係を満たせば割り込みを行うよう構成されていることを特徴とする請求項３記載のキューイング装置。
【請求項５】
自己同期パイプラインを利用したデータ駆動プログラム構造を備え、前記制御回路により、前記経路を経た前記ステージから他のステージへの命令の伝達、および／または、前記分岐回路、分岐路並びに合流回路を経たさらに他のステージへの命令の伝達が実現されることを特徴とする請求項１ないし４のいずれか一項に記載のキューイング装置。
【請求項６】
さらに、前記分岐回路の何れかが、優先度にしたがって、受理したパケットを廃棄するように構成されたことを特徴とする請求項１ないし５のいずれか一項に記載のキューイング装置。
【請求項７】
請求項１ないし６の何れか一項に記載のキューイング装置を用いた優先制御機構であって、
データを受け入れて、必要な命令を生成し、かつ、前記キューイング装置のパイプラインステージ数を考慮して、前記命令をキューイング装置の入口に投入する整合手段を備え、
前記キューイング装置において、所定の優先度にしたがった経路、および、場合によって分岐路を経由して命令が出力されるように構成されたことを特徴とする優先制御機構。
【請求項８】
請求項１ないし６の何れか一項に記載のキューイング装置を用いて、与えられたデータパケットを、連想されたネクストホップに送出するルータであって、
与えられたデータパケットのうち、データ長および優先度を含む、優先制御に必要な第１の部分と、それ以外の第２の部分に分解するデータ分解手段と、
前記第２の部分を記憶するメモリと、
前記第１の部分を受け入れて、必要な命令を生成し、かつ、前記キューイング装置のパイプラインステージ数を考慮して、前記命令をキューイング装置の入口に投入する整合手段と、
前記キューイング装置から出力された命令と、前記メモリからの第２の部分の少なくとも一部とを受理して、前記データパケット中のヘッダ部を合成するヘッダ処理手段と、
前記ヘッダ処理手段からヘッダ部を受け入れ、前記ネクストホップを取得する検索手段と、
前記メモリのうち、前記第２の部分の他の一部と、前記ヘッダ部とからなるデータパケットを再合成するとともに、当該データパケットに前記ネクストホップを付加するデータ合成手段と、
前記データ合成手段により再合成されたデータパケットを送出するデータ送出手段とを備えたことを特徴とするルータ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、キューイング装置に関し、より詳細には、キューイングの優先制御を実現する装置に関する。
【０００２】
【従来の技術】
超広帯域光伝送技術の著しい進展に伴い、高度の機能や通信品質を必要とする多様な通信サービスの提供が求められている。これに伴い、多様なサービスとそれを実現する種々のプロトコルを柔軟に超高速処理可能な、パケットルータの技術の確立が求められる。
【０００３】
Ｄｉｆｆｓｅｒｖ（Ｄｉｆｆｅｒｅｎｔｉａｔｅｄ
Ｓｅｒｖｉｃｅｓ）によるクラス別優先制御では、主として、パケットヘッダ内のＤＳＣＰ（Ｄｉｆｆｓｅｒｖｅ　Ｃｏｄｅ　Ｐｏｉｎｔ）に基づき、ホップごとにパケットを分類してキューイングする。したがって、クラスごとのキューイングにキューイングの優先制御を実行する必要がある。
従来、代表的なキューイング技術であるＦＩＦＯ（Ｆｉｒｓｔ−Ｉｎ　Ｆｉｒｓｔ−Ｏｕｔ）は、最先のパケットを最初に出すようなロジックである。したがって、キューイング装置内にパケットが詰まってくると、先に入ったパケットが出力されないために、優先パケットであっても、メモリ内で破棄される可能性がある。
【０００４】
【発明が解決しようとする課題】
固定的にパラメータを設定して、静的な優先制御を実施することは可能であるが、優先制御の形態を動的に変更することは著しく困難である。また、複数のキューイングシステムを採用して、それぞれ優先度に応じて、パケットを所定のキューイングシステム中に入力することにより、優先制御を実現することもできる。しかしながら、このような手法を利用しても、柔軟に優先制御の形態を変形することは不可能であった。たとえば、４つのキューイングシステムを採用すれば、入力したパケットを４つのクラスのいずれかに分類し、クラスに応じたキューイングを実行することはできるが、クラス数の変更などに対応することは事実上不可能である。
また、動的かつ柔軟に優先制御の形態を変更可能な装置を提供するにあたって、あらたに生じる可能性のある問題を解決する必要も出てくる。
【０００５】
本発明は、動的かつ柔軟に優先制御の形態を変更可能な装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
本発明の目的は、入口から出口に至る経路において、直列に配置された、パイプラインステージを構成する複数のステージであって、それぞれが同一の優先度を示す同一クラスの命令をカウントする機構をもつプロセッシングファンクション及びデータラッチを有し、所定数のステージが、順方向に配置されるとともに、残りのステージが折り返し点から逆方向に配置されたステージと、前記順方向の経路上において、各々が所定のステージ間に配置された、少なくとも１以上の分岐回路と、前記逆方向の経路上において、各々が所定のステージ間に配置された、少なくとも１以上の合流回路と、前記分岐回路の各々と、何れかの合流回路とを接続する分岐路とを備え、データの優先度を示す情報およびデータ本体を含む命令が、前記入口から投入されると、前記ステージ間を、前記命令が順方向および逆方向に伝達され、かつ、前記優先度および前記命令の属するクラスのカウント値にしたがって、割り込みとして、順方向に配置された転送元のステージから、所定の分岐回路から分岐路および対する合流回路を経て、逆方向に配置された転送先のステージに命令が伝達されることを特徴とするキューイング装置により達成される。
【０００７】
本発明によれば、優先度の高い命令を分岐回路、分岐路及び合流回路を経由して追い越しや先出しを実現できる。また、優先度の種別やその経路設定を柔軟に変更することが可能である。また、各ステージが同一クラスの命令のカウント値を管理することで、同一クラスの命令の順序逆転を防止することも可能である。
【０００８】
好ましい実施態様においては、前記ステージは、前記命令の割り込みが生じた場合の転送元ステージのカウンタ値をａ、転送先ステージのカウント値をｘとおいたときに、ａ＝ｘ＋１の関係を満たせば、割り込みを行うよう構成されている
【０００９】
また、好ましい実施態様においては、前記順方向の経路上に位置するプロセッシングファンクションは、伝達される前記命令が属するクラスに対応する転送元ステージのカウンタ値および転送先ステージのカウンタ値の差分をカウントする機構をさらに備えている
【００１０】
前記キューイング装置は、自己同期パイプラインを利用したデータ駆動プログラム構造を備え、前記制御回路により、前記経路を経た前記ステージから他のステージへの命令の伝達、および／または、前記分岐回路、分岐路並びに合流回路を経たさらに他のステージへの命令の伝達が実現されるのが望ましい。
【００１１】
より好ましい実施態様においては、さらに、前記分岐回路の何れかが、優先度にしたがって、受理したパケットを廃棄するように構成されている。この実施態様では、優先度に応じて設定された深さ、つまり、設定された前記パイプラインの段数に到達したパケットが、当該深さに対応する位置の分岐回路において廃棄される。
【００１２】
また、本発明の目的は、上記キューイング装置を用いた優先制御機構であって、データを受け入れて、必要な命令を生成し、かつ、前記キューイング装置のパイプラインステージ数を考慮して、前記命令をキューイング装置の入口に投入する整合手段を備え、キューイング装置において、所定の優先度にしたがった経路、および、場合によって分岐路を経由して命令が出力されるように構成されている。
【００１３】
また、本発明の目的は、上記キューイング装置を用いて、与えられたデータパケットを、連想されたネクストホップに送出するルータであって、与えられたデータパケットのうち、データ長および優先度を含む、優先制御に必要な第１の部分と、それ以外の第２の部分に分解するデータ分解手段と、前記第２の部分を記憶するメモリと、前記第１の部分を受け入れて、必要な命令を生成し、かつ、前記キューイング装置のパイプラインステージ数を考慮して、前記命令をキューイング装置の入口に投入する整合手段と、前記キューイング装置から出力された命令と、前記メモリからの第２の部分の少なくとも一部とを受理して、前記データパケット中のヘッダ部を合成するヘッダ処理手段と、前記ヘッダ処理手段からヘッダ部を受け入れ、前記ネクストホップを取得する検索手段と、前記メモリのうち、前記第２の部分の他の一部と、前記ヘッダ部とからなるデータパケットを再合成するとともに、当該データパケットに前記ネクストホップを付加するデータ合成手段と、前記データ合成手段により再合成されたデータパケットを送出するデータ送出手段とを備えたことを特徴とするルータによっても達成される。
【００１４】
【発明の実施の形態】
（背景技術）
まず、本発明に先立って本出願人等が開発した優先制御処理の可能なキューイングシステムを搭載したルータ（特願２００１−３０３２７６）について、添付図面を参照して説明する。図１は、優先制御処理部を搭載したルータの構成を示すブロックダイヤグラムである。図１に示すように、ルータ１０は、入力されたデータパケットを受理して、これを、分解してデータ駆動パケットを生成するデータパケット分解部１２と、優先制御処理に利用するパケットの部分である優先制御処理部分を受け入れて、優先制御のために必要な種々の処理を実行する整合処理部１４と、後述する構成の折り返し自己同期パイプラインを利用してキューイングを実現するキューイング装置として優先制御処理部１６と、前記データパケットのうち、優先制御処理に利用しないパケットの部分である非優先制御処理部分を受け入れて、これを一時的に記憶するメモリ１８と、優先制御処理部１６からの出力と、メモリ１８からの出力のうち、パケットのヘッダに対応する部分とを受理して、伝送プロトコルに特有の必要な処理（たとえば、ＣＲＣチェックなど）を実行するヘッダ処理部２０と、ルーティングテーブルを有し、当該ヘッダ処理部２０で処理されたヘッダ情報を受け入れて、アドレス検索を実行して、適切なネクストホップを取得するアドレス検索部２２と、ヘッダ部およびペイロード部を合成するとともに、アドレス検索部２２にて得られたネクストホップを付加するデータパケット合成部２４と、データパケットを目的の出力ポートに送出するスイッチ部２６とを備えている。
【００１５】
上記ルータにおいて、優先制御処理部１６は、後に詳述するようなデータ駆動型プログラム構造を備え、自己同期パイプラインにより、優先パケットの追い越し、先出しを実現している。
【００１６】
また、アドレス検索部２２として、たとえば、レベル圧縮トライ木構造を利用した情報検索装置（特願２００１−０５６２８９）を用いることができる。
【００１７】
図２は、上記ルータにて実行される処理の概略を示すフローチャートである。ルータ１０にデータパケットが入力され、データパケット分解部１２がこれを受理する（ステップ２０１）と、ルータ内部での複数のデータ駆動パケットが生成される（ステップ２０２）。
【００１８】
図３は、上記ルータにおけるパケットを説明するための図である。図３に示すように、パケット３００は、ヘッダ部３０１と、ユーザデータなどを含むペイロード部３０２とから構成される。データパケット分解部１２は、もとのデータパケットを所定の長さに分解し、各々の部分（データ部）３１１−１、３１１−２、・・・、３１１−ｎに、必要なヘッダ部（データ駆動ヘッダ部）３１２−１、３１２−２、・・・、３１２−ｎを付加して、データ駆動パケット３１０−１、３１０−２、・・・、３１０−ｎを生成する。このデータ駆動ヘッダ部３１２には、たとえば、パケットやパケット中の位置などが示されている。
【００１９】
次いで、データ駆動パケットのうち、優先制御処理に必要な部分、たとえば、Ｄｉｆｆｓｅｒｖ方式が適用されている場合には、ＤＳＣＰ形成に必要なパケットのヘッダ部情報（ＩＰｖ４パケットではＴＯＳフィールド）が、優先制御処理部分として、整合処理部１４に与えられる。上記優先制御処理部分には、たとえば、パケット長を示す情報なども含まれる。残りの部分は、非優先制御処理部分として、メモリ１８に与えられ、所定の領域に記憶される（ステップ２０３）。
【００２０】
その一方、優先制御処理部分が整合処理部１４に受理されると、整合処理部１４は、優先制御処理部１６のキューの深さ（キューデプス）を管理するための必要な演算等を施すとともに、オペレーションコード、行き先、世代番号など、データ駆動型プログラム構造を備えた優先制御処理部１６における演算が可能となるように、優先制御処理部分に必要な情報を付加したデータ駆動命令（以下、単に「命令」と称する。）を生成する。生成された命令は、優先制御処理部１６に投入され、ここでキューイングが実行される（ステップ２０５）。
【００２１】
図４は、上記ルータの整合処理部１４および優先制御処理部１６の構成を示すブロックダイヤグラムである。図４に示すように、優先制御処理部１６は、データ（優先制御処理部分）の入口から出口に至るまで、直列に配置された複数のデータラッチ（図面において、「ＤＬ」と表記している。）３０−１、３０−２、・・・、３０−ｉを有し、「ｉ」段のパイプラインステージを構成している。
【００２２】
上記ルータにおいて、優先制御処理部１６のデータラッチ３０は、機能的に、命令が徐々にキューの深い部分に進み（矢印４０１参照）、折り返し点から、徐々に浅い部分に戻るような（矢印４０２参照）構造となっている。本明細書において、このような構造を「折り返し構造」と称し、また、キューの深い部分に進む方向を順方向、キューの浅い部分に進む方向を逆方向と称する。
【００２３】
優先制御処理部１６において、矢印４０１に示す第１の方向には、隣接するデータラッチの間に、分岐回路（図面において、「Ｂ」と表記している。）３２−１、３２−２、・・・が配置されている。その一方、矢印４０２に示す第２の方向には、隣接するデータラッチの間に、合流回路（図面において、「Ｊ」と表記している。）３８−１、３８−２、・・・が配置されている。図４に示すように、ある分岐回路、たとえば、分岐回路３２−１は、分岐路４１０−１を経て、ある合流回路３８−１と接続されている。つまり、上記優先制御処理部１６においては、命令の入口、および、命令の出口と、同じ距離だけ離間して配置された分岐回路および合流回路が、分岐路にて接続されている。このように分岐路で結ばれた分岐回路および合流回路は、同じレベルであると称する。
【００２４】
また、優先制御処理部１６は、データラッチ３０間のデータ転送を制御する制御回路（図面において「Ｃ」と表記している。）３４−１、３４−２、・・・、３４−ｉと、制御回路間の信号伝送に、後述するように必要な遅延を与える遅延回路（図面において、「Ｄｅｌａｙ」と表記している。）３６−１、３６−２、・・・、３６−（ｉ−１）を有している。
【００２５】
上記構成の優先制御処理部１６の動作について以下に説明する。命令が投入されると、データラッチは、オペレーションコードや行き先を参照して、命令を分岐回路３２−１に伝達する。たとえば、優先度が最も低く設定された命令であれば、データラッチ３０−１、分岐回路３２−１、データラッチ３０−２、分岐回路３２−２、・・・という順で、他の優先度の命令と較べて、徐々に、順方向（矢印４０１の方向）に進められる可能性が高くなる。分岐点に到達すると、今度は、逆方向（矢印４０２の方向）に順次戻され、合流回路３８−２、データラッチ３０−（ｉ−１）、合流回路３８−１、データラッチ３０−ｉを経て出力される。
【００２６】
その一方、優先度が所定の高さに設定された命令であれば、ある分岐回路（たとえば、分岐回路３２−２）において、同じレベルの合流回路に逆方向４０２から入力されようとする他の命令と比較して優先度が高ければ、第１の方向４０１のデータラッチ（たとえば、データラッチ３０−３）に命令が伝達されるのではなく、分岐路（たとえば、分岐路４１０−２）を経て、同レベルに位置する合流回路（たとえば、合流回路３８−２）に伝達される。この命令は、次に、出口の最も近くに配置されたデータラッチ３０−ｉに伝達され、その後、優先制御処理部１６から出力される。これにより、分岐路を使わずに順次データラッチに伝達されるような命令を追い越して、先出しするようなキューイングを実現することができる。
【００２７】
上記ルータにおいては、優先度が高いほど、より入口および出口に近いレベルの分岐路を利用することができるように設定されている。したがって、優先度に応じて、経路の長さ（つまり、入口から出口に至るまでに通るべきデータラッチの数）を、所望のように制御することが可能である。
【００２８】
次に、制御回路３４について説明を加える。上記ルータにおいて、制御回路３４は、データラッチに、ラッチしている命令の送出を求めるトリガを出力する。接続されたデータラッチにトリガを与えるのに先立って、制御回路は、隣接して配置された他の制御回路であって、命令の送出方向（順方向４０１或いは逆方向４０２）に配置されている他の制御回路に、ＳＥＮＤ信号を送信する。ＳＥＮＤ信号を受理した他の制御回路は、接続されたデータラッチが命令を受け入れ可能であれば、ＡＣＫ信号を、ＳＥＮＤ信号を出力した制御回路に返送する。
【００２９】
ここで、ＡＣＫ信号は、遅延回路３６を介して、所定の遅延が与えられて、ＳＥＮＤ信号の送信元の制御回路に伝達される。この遅延Ｄは、もとのパケットの長さＬに比例するように設定される。上記ルータにおいては、ルータ１０中に優先制御処理部１６を配置している。したがって、与えられるパケットは可変長のものであり、パケットの長さＬを考慮しないと、優先制御処理後のパケット処理や出力のタイミングを誤るおそれがある。たとえば、長さＬが比較的長いパケット（先行パケット）に関する優先制御が終了した直後に、次のパケット（後続パケット）の優先制御を行える状態とすると、先行パケットに関する上記パケット処理や出力の途中で、後続パケットに関する上記パケット処理や出力が割り込む可能性があるからである。そこで、元のパケット長を考慮して、パケット処理および終了するタイミングを見計らって、処理を進めるような構造としている。したがって、後続パケットは、直前に優先制御処理部１６において処理されたパケットの本来のパケット長に応じた時間、入力や割り込みを待たされることになる。
【００３０】
パケットのペイロード部まで含めてキューイングをすれば、上述した待機をする必要は無いが、優先制御に不要なデータ駆動パケットまで、優先制御処理部１６を通過させることは冗長であり、また、そのようなパケットを受け入れるためには、優先制御処理部１６の回路を大規模なものにしなければならず、製造コストが著しく増大する。そこで、上記ルータにおいては、優先制御に必要な部分のみをとりだして、これを優先制御処理部１６に投入し、残りの部分はメモリに記憶して、後にパケットを再合成するように構成している。
【００３１】
また、上記ルータにおいて、整合処理部１４は、優先制御処理部分を受理して、これを命令として優先制御処理部１６に投入するときに、優先制御処理部１６におけるキューデプス残量Ｑを、Ｑ＝Ｑ−Ｌに更新する（Ｌは、前述したように元のパケット長）。その一方、元のパケット長がＭであるような命令を、優先制御処理部１６から受理した際に、これを出力する前に、キューデプス残量Ｑを、Ｑ＝Ｑ＋Ｍに更新する。これにより、たとえば、投入する命令数が、パイプラインステージ数を超えないように、優先制御処理部１６に投入可能な命令数を管理することが可能となる。
【００３２】
なお、整合処理部１４においてパケットを廃棄（Ｄｒｏｐ）する代わりに、或いは、整合処理部１４におけるパケットの廃棄に加えて、優先制御処理部１６においてパケットを廃棄するような構成をとっても良い。ここでは、図４に示す分岐回路３２−ｊ（ｊ＝１、２、・・・）においてパケットの廃棄が実現される。一般に、（優先制御処理部１６におけるキューイングの総容量−キューデプス残量）と、優先制御処理部１６においてパケットが到達する深さとの間には相関関係がある。したがって、これを応用して、優先度を示す情報に応じて優先制御処理部１６中でパケットを廃棄する。たとえば、優先度の高いパケットは、分岐路を介することでより早く優先制御処理部１６から出力されるが、比較的浅い位置の（入口および出口に近いレベルに位置する）分岐回路にて廃棄されて良いという要求があれば、当該分岐回路においてパケットを破棄しても良いことになる。
【００３３】
優先制御処理部１６から処理の終了した命令が出力されると、整合処理部１４を介して、ヘッダ処理部２０に与えられる。また、整合処理部１４から、出力された命令に関するヘッダ部の読み出し要求がメモリ１８に与えられ（符号１０１参照）、メモリ１８から、対応するパケットの非優先処理部分が読み出される（ステップ２０６）。メモリ１８から読み出された非優先処理部分のうち、元のパケットのヘッダ部に対応する部分がヘッダ処理部２０に与えられる。ヘッダ処理部２０においては、元のパケットのヘッダ部（図３の符号３０１参照）により、データ駆動パケットのデータ部（図３の符号３１１−１、３１１−２、・・・）が処理される（ステップ２０７）。
【００３４】
再生成されたヘッダ部は、アドレス検索部２２に与えられ、そこで、パケットの次の宛先であるネクストホップが取得され（ステップ２０８）、ヘッダ部とともにネクストホップが、データパケット合成部２４に与えられる。その一方、メモリから読み出された非優先処理部分のうち、元のパケットのペイロードに対応する部分も、データパケット合成部２４に与えられる。
データパケット合成部２４は、ヘッダ部とペイロード部とを合成し、かつ、ネクストホップを付加して（ステップ２０９）、これをスイッチ部２６に伝達する。スイッチ部２６は、受理したパケットを目的の出力ポートにスイッチする（ステップ２１０）。このようにして、ルータ１０に入力されたパケットが、次の目的地に向けて送出される。
【００３５】
このように上記優先制御処理部１６においては、折り返しを有する自己同期パイプラインにより、当該優先制御処理部１６を構成し、優先パケットの追い越し、先出しを実現している。また、データ駆動型プログラム構造を採用することにより、優先度の設定を所望のように変更することができる。また、元のパケット長を考慮して、データラッチ間の命令の伝送を制御することにより、優先制御に必要なパケット中の部分のみを優先制御処理部１６に投入すればよく、回路規模の小さな優先制御処理部１６を実現することができる。
【００３６】
ところで、上記ルータにおいては、折り返しを有する自己同期パイプラインにより優先制御処理部１６を構成しているので、同一のデータパケット３１０を分解して生成した同一クラスの複数の命令の順序が優先制御処理部１６の中で逆転してしまう可能性がある。
例えば、ある優先データパケット３００を分解して生成されたデータ駆動パケット３１０−１、３２０−２、・・・、３１０−ｎの中から優先制御処理部分として整合整理部１４に受理され、生成された同一クラスの命令をＡ１、Ａ２、・・・、Ａ３とし、命令Ａ１、Ａ２が、それぞれデータラッチ３０−２、３０−１にラッチされている状態で考えてみる。
【００３７】
この優先制御処理部１６は自律処理型であるため、この状態で、制御回路３４−１が、命令Ａ２を分岐路４１０−２を経てデータラッチ３０−ｉに伝達するためのＳＥＮＤ信号を制御回路３４−ｉに送信し、ＡＣＫ信号を受信すると、命令Ａ２がデータラッチ３０−ｉに伝達されることになる。そうすると、命令Ａ１よりも命令Ａ２が先に優先制御処理部１６から出力されることになり、順序の逆転が生じてしまう。
【００３８】
このような順序逆転現象が起きると、後から順序通りに並べ直す必要が生じ、アプリケーションによっては無視できない影響を与える可能性がある。
本出願人は、このような順序逆転現象を防止するため、下記に示す順序逆転防止機構を備えたキューイング装置及びルータを開発した。
【００３９】
（発明の実施の形態）
以下、添付図面を参照して本発明の実施の形態につき説明を加える。本実施の形態に係るルータは基本的な構成は上記ルータと同じであり、優先制御処理部１６の構成が上記ルータと異なる。よって、上記ルータと同様の構成については説明を省略し、優先制御処理部１６の構成を中心に説明する。
【００４０】
図５は、本実施の形態にかかる整合処理部１４および優先制御処理部１６の構成を示すブロックダイヤグラムである。優先制御処理部１６の基本的な構成は、図４に示した上記ルータのものと同じである。図５においては、図４のデータラッチ３０−１、３０−２、・・・、３０−ｉの位置に、ステージ（図面において、「ＳＴ」と表記している）６０−１、６０−２、・・・、６０−ｉが設けられている。
【００４１】
図６は、本実施の形態にかかるステージ６０の構成を示すブロックダイヤグラムである。図６に示すように、ステージ６０は、プロセッシングファンクション（図面において、「ＰＦ」と表記している）６５とデータラッチ３０から構成されている。
プロセッシングファンクション６５は、データラッチが保持している命令の同一クラス毎のカウンタ情報（カウント値）を管理するものである。例えば、データ駆動命令が優先制御処理部１６に投入される際には、同一クラスの命令に連番が付与されるように、クラス毎にプロセッシングファンクション６５−１がカウントを行う。プロセッシングファンクション６５−１にて管理されるカウント値は、同一のステージに属するデータラッチに保持される。なお、図４においても、データラッチには、プロセッシングファンクションが接続されている。しかしながら、先に説明したように、図４の例では、プロセッシングファンクションが、クラスごとのカウントを実行しないため、その表示および説明を省略している。
【００４２】
以下、本実施の形態にかかる優先制御処理部１６の動作について詳細に説明する。ここでは、３つのデータパケットＡ、Ｂ、Ｃ（優先度は、Ａ＞Ｂ＞Ｃ）が入力されてくるケースを想定し、分解されて優先制御処理部１６に入ってくる命令を、それぞれ、クラスＡ：Ａ１〜Ａ８、クラスＢ：Ｂ１〜Ｂ８、クラスＣ：Ｃ１〜Ｃ８としている。
【００４３】
図７は、優先制御処理部１６の動作を説明するために、優先制御処理部１６を概念的に表した概念図である。説明の便宜上、ステージ６０は６０−１〜６０−１６の１６個存在するとしている。また、図中、ステージ６０の左半分をプロセッシングファンクション６５にて管理されるカウンタ値を表すため、３つのブロックに分割している。これは、Ａ１−８、Ｂ１−８、Ｃ１−８をそれぞれカウントして管理するためであり、図中上から順にＡ、Ｂ、Ｃ用のカウンタを表している。以下、各プロセッシングファンクション６５にて管理され、かつ、データラッチ６０にて保持されるカウンタの値を（Ａ，Ｂ，Ｃ）と表す。なお、これ以降、本明細書において、便宜上、カウンタ値について、プロセッシングファンクション６５にて管理されるものとして表すが、実際には、プロセッシングファンクション６５にて管理され、その値は、データラッチ６０にて保持されるものであることは言うまでもない。
【００４４】
また、ステージ６０の右半分は、命令を保持するデータラッチ３０を表している。また、分岐回路３２、合流回路３８等その他の構成については、図面を簡略化するため省略している。なお、以下に参照する図８ないし図１２において、符号は省略しているが、これらにおいて、矩形のブロックは、ステージを表している。また、その左半分には当該ステージにおけるカウント値が表示され、かつ、その右半分には、当該ステージのデータラッチが配置されている。
また、図７において、ステージ間を結ぶ線（経路）は、命令が移動可能であることを示している。経路には、順方向４０１の経路（たとえば、符号４０３参照）および逆方向４０２の経路（たとえば、符号４０４参照）のほか、同じレベルのステージ間の経路（たとえば、符号４０５参照）が含まれる。
【００４５】
図８および図９は、優先制御処理部１６の基本的な処理を説明するために、上記概念図を用いて優先制御処理部の処理を時系列に表した図である。
まず、図８（ａ）は、命令Ｂ１がステージ６０−１６に位置し、次にステージ６０−１のデータラッチ３０−１に命令Ａ１を入力する指令が出されている状態を示す。命令Ｂ１はデータラッチ３０−１から分岐路を経てデータラッチ３０−１６に伝達されたものであり、プロセッシングファンクション６５−１及び６５−１６にて管理されるカウンタ値は、（０，１，０）となっている。すなわち、各命令が隣のステージに伝達されると、移動元のステージで持っていたカウンタ情報が移動先ステージにコピーされるように構成されている。ただし、後述するように、優先制御により、優先度の高い命令が分岐路を経て他のクラスの命令に割り込んで伝達される場合には、自己の属するクラスのカウンタ情報のみをコピーして更新するように構成されている。
【００４６】
続いて、図８（ｂ）は、命令Ａ１がステージ６０−１に入力され、次に命令Ａ１をステージ６０−２に伝達する指令が出されている状態を示す。なお、本実施の形態にかかる優先処理制御部１６は、自己同期システムであり、各ステージ６０に対応した各制御回路３４が自律して指令を出しているので、ステージ６０−１の命令Ａ１に対しては隣接するステージへの伝達指令が出されているのに対して、ステージ６０−１６の命令Ｂ１に対しては伝達指令が出されていない。プロセッシングファンクション６５−１にて管理されるカウンタ値は、命令Ａ１がステージ６０−１に入力されたので、（１，１，０）と更新されている。
【００４７】
続いて、図８（ｃ）は、命令Ａ１がステージ６０−２に伝達され、次に、命令Ａ２をステージ６０−１に入力する指令、命令Ａ１をステージ６０−１５に伝達する指令、命令Ｂ１を整合処理部１４に出力する指令が出されている状態を示す。命令Ａ１がステージ６０−２に伝達されているので、プロセッシングファンクション６０−２にて管理されるカウンタ値が、（１，１，０）と更新されている。
【００４８】
続いて、図９（ａ）は、命令Ａ２がステージ６０−１に入力され、命令Ａ１がステージ６０−１５に伝達され、命令Ｂ１が出力され、次に、命令Ａ２をステージ６０−２に伝達する指令、命令Ａ１をステージ６０−１６に伝達する指令が出されている状態を示す。カウンタ値は、プロセッシングファンクション６５−１について（２，１，０）、プロセッシングファンクション６５−１５について（１，１，０）と更新されている。
【００４９】
続いて、図９（ｂ）は、命令Ａ２がステージ６０−２に伝達され、命令Ａ１がステージ６０−１６に伝達され、次に、命令Ａ３をステージ６０−１に入力する指令、命令Ａ２をステージ６０−１５に伝達する指令が出されている状態を示す。カウンタ値は、プロセッシングファンクション６５−２について（２，１，０）、プロセッシングファンクション６５−１６について（１，１，０）と更新されている。
【００５０】
続いて、図９（ｃ）は、命令Ａ３がステージ６０−１に入力され、命令Ａ２がステージ６０−１５に伝達され、次に、命令Ａ３がステージ６０−２、続いてステージ６０−３へと伝達する指令が出されている状態を示す。カウンタ値は、プロセッシングファンクション６５−１について（３，１，０）、プロセッシングファンクション６５−１５について（２，１，０）と更新されている。
続いて、図９（ｄ）は、命令Ａ３がステージ６０−２を経てステージ６０−３まで伝達されて位置している状態を示している。カウンタ値は、プロセッシングファンクション６５−２について（３，１，０）、プロセッシングユニット６５−３について（３，１，０）と更新されている。
【００５１】
次に、優先度の高いクラスの命令が、優先度の低いクラスの命令に割り込みされる場合の優先制御処理部１６の処理について説明する。
図１０は、優先度の高いクラスの命令が割り込みされる処理を説明するために、図７に示す概念図を用いて優先制御処理部の処理を時系列に表した図である。
【００５２】
図１０（ａ）は、ステージ６０−１に命令Ｂ５、ステージ６０−３に命令Ｂ４、ステージ６０−５に命令Ｃ７、ステージ６０−１３に命令Ｃ６、ステージ６０−１５に命令Ｃ５、ステージ６０−１６に命令Ｃ４が位置し、命令Ｂ５をステージ６０−２に伝達する指令、命令Ｂ４をステージ６０−１４に割り込みする指令、命令Ｃ７をステージ６０−１２に伝達する指令、命令Ｃ５をステージ６０−１６に伝達する指令、命令Ｃ４をステージ６０−１６から出力する指令が出されている状態を示す。
【００５３】
この時、プロセッシングファンクション６５−１〜６５−５にて管理されるカウンタ値が、順に、（８，５，７）、（８，４，７）、（８，４，７）、（８，３，７）、（８，３，７）、プロセッシングファンクション６５−１２〜６５−１６にて管理されるカウンタ値が、順に、（８，３，６）、（８，３，６）、（８，３，５）、（８，３，５）、（８，３，４）となっている。
図１０（ｂ）は、命令Ｂ５がステージ６０−２に位置し、命令Ｃ７がステージ６０−１２に位置し、命令Ｃ６がステージ６０−１３に位置し、命令Ｂ４がステージ６０−１４に位置し、命令Ｃ５がステージ６０−１５に位置している状態を示している。
【００５４】
この時、プロセッシングファンクション６５−１〜６５−５にて管理されるカウンタ値が、順に、（８，５，７）、（８，５，７）、（８，４，７）、（８，３，７）、（８，３，７）、プロセッシングファンクション６５−１２〜６５−１６にて管理されるカウンタ値が、順に、（８，３，７）、（８，３，６）、（８，４，５）、（８，３，５）、（８，３，５）と更新されている。このように、命令Ａ４が割り込みされたステージ６０−１４では、プロセッシングファンクション６５−１４にて管理されるカウンタ値ののうち、クラスＢに対応するカウンタ値のみが更新されている。
【００５５】
そして、この命令Ｂ４が割り込まれたプロセッシングファンクション６５−１４により、クラスＢの対応するカウンタ値はロックされ、次にクラスＢの命令が伝達されてくるまでその値が変化しないように制御される。すなわち、他のクラスの命令Ｃがステージ６０−１４に伝達されてきても、クラスＢに対応するカウンタ値以外が更新されるだけである。このように制御することで割り込み処理の行われたクラスＢにおいて生じる可能性のある誤カウントや誤った順序逆転を防止することができる。
【００５６】
次に、優先制御処理部１６において同一のデータパケットから生成された命令の順序逆転を防止する場合の処理について説明する。
図１１は、この順序逆転を防止する処理を説明するために、図７に示す概念図での処理を時系列に並べた遷移図である。
【００５７】
図１１（ａ）は、命令Ｂ５がステージ６０−１に位置し、命令Ｃ７がステージ６０−３に位置し、命令Ｃ６がステージ６０−５に位置し、命令Ｃ５がステージ６０−７に位置し、命令Ｃ４がステージ６０−９に位置し、命令Ｂ４がステージ６０−１０に位置し、命令Ｃ３がステージステージ６０−１１に位置し、命令Ｂ３がステージ６０−１３に位置し、命令Ｃ２がステージ６０−１４に位置し、命令Ｃ１がステージ６０−１５に位置している状態を示している。この状態で、命令Ｂ５をステージ６０−２に伝達する指令、命令Ｃ７をステージ６０−４に伝達する指令、命令Ｃ６をステージ６０−６に伝達する指令、命令Ｃ５をステージ６０−８に伝達する指令、命令Ｃ３をステージ６０−１２に伝達する指令、命令Ｃ１をステージＣ６０−１６に伝達する指令が出されている。
【００５８】
ここで命令Ｂの優先度が命令Ｃの優先度よりも高いため、命令Ｃ１をステージ６０−１６に伝達するよりも命令Ｂ５を優先させてステージ６０−１６に伝達して割り込ませることも可能である。しかし、命令Ｂ５をステージ６０−１６に伝達させると、命令Ｂ３，Ｂ４よりも先に命令Ｂ５が優先制御処理部１６から出力されることになり、このような順序逆転は上述したように好ましくない。
【００５９】
本実施の形態にかかる優先制御処理部１６においては、以下のような割り込み判定の制御を行うことで、同一クラスの命令の順序逆転を防止している。
つまり、移動元のプロセッシングファンクション６５−１にて管理される命令Ｂに対応するカウンタ値ａと移動先のプロセッシングファンクション６５−１６にて管理される命令Ｂに対応するカウンタ値ｘとを対比し、カウンタ値ａがカウンタ値ｘに続く値であるか、すなわちａ＝ｘ＋１となる場合のみ、命令Ｂの割り込み移動を行うように制御している。このように、同一クラス内でカウンタ値により割り込み判定を行うことで、同一クラスの命令の順序逆転を防止することができる。
【００６０】
図１１において上記割り込み判定を行うと、命令Ｂ５の移動元ステージ６０−１のａ＝５、移動先ステージ６０−１６のｘ＝２であり、ａ≠ｘ＋２であるから、図１１（ｂ）に示すように、命令Ｃ１よりも優先度の高い命令Ｂ５がステージ６０−２に伝達されている。
なお、カウンタ値はサイクルするように設定されており、優先制御処理部１６のステージの数、すなわちパイプラインの段数に合わせて決定されたサイクル値が設定されている。そして、カウンタ値が上記サイクル値に達するとリセットされるように構成されており、永久にカウンタ値が上昇していくことを防止している。
【００６１】
参考までに、図１０で命令Ｂ４が割り込み伝達された場合についてみると、図１０（ａ）において転送元ステージ６０−３のクラスＢに対応するカウンタ値ａは４、転送先ステージ６０−１４のカウンタ値ｘは３であり、ａ＝ｘ＋１の関係を満たしている。
また、本実施の形態にかかる優先制御処理部１６では、各クラスの優先度にしたがって、最終ステージが定められており、最終ステージで折り返すことができない命令は廃棄される。
【００６２】
図１２は、上記最終ステージの概念を説明するための図である。図１２に示すように、本実施の形態では、命令Ａのクラスの最終ステージはステージ６０−３、命令Ｂのクラスの最終ステージはステージ６０−６に設定されている。そして、命令Ａ１〜Ａ８がステージ６０−３に伝達されてきてステージ６０−１４に割り込むことができなかった場合には、その命令Ａは廃棄されることになる。また、命令Ｂ１〜Ｂ８がステージ６０−６に伝達されてきてステージ６０−１１に割り込むことができなかった場合には、その命令Ｂは廃棄されることになる。
【００６３】
このように廃棄される場合におけるプロセッシングファンクション６５でのカウント処理は、割り込みの場合と同様である。すなわち、廃棄された命令の最終ステージのカウンタ値で、割り込みできなかった転送先ステージのカウンタの該当クラスの値を上書きすることになる。
【００６４】
このように、命令の優先度にしたがって、最終ステージを設定し、廃棄を行うことで、当初予定されたタイミングでキューイングされないパケット、つまり、後の処理（たとえば、ネクストホップの検索）の対象たり得なくなったパケットを、優先制御処理部１６中に残留させることなく、効率よく廃棄することが可能となる。
【００６５】
次に、本実施の形態にかかる優先制御処理部１６の変形例について説明する。図１３および図１４は、本変形例にかかる優先制御処理部１６の概念を示す図である。図１３および図１４に示すように、本変形例にかかる優先制御処理部１６は、上述した本実施の形態の各ステージ６０のうち順方向のプロセッシングファンクション６５−１〜６５−８に、さらに差分カウンタ６５ａを設けたことが特徴である。差分カウンタ６５ａは、プロセッシングファクション６５により管理され、かつ、そのカウンタ値は、プロセッシングファンクション６５が属するステージのデータラッチ６０に保持される。
【００６６】
この差分カウンタ６５ａは、各命令が各プロセッシングファンクション６５のカウンタ値を上書きする際に、自己の命令の属するクラスのカウンタ値の上書き前の値と上書き後の値との差を保持するように構成されている。
さらに、本変形例では、上述の割り込み判定に換えて、以下のような割り込み判定を行っている。すなわち、移動元のステージのカウンタ値ａ、移動先のステージのカウンタ値ｘ、および移動元のステージの差分カウンタ値ｙとを対比し、ａ＝ｘ＋ｙとなる場合のみ、割り込みを行うように制御している。
【００６７】
図１３および図１４を参照して、本変形例にかかる優先制御処理部１６の動作について、具体的に説明する。
図１３（ａ）は、命令Ｂ６がステージ６０−１に位置し、命令Ｂ５がステージ６０−２に位置し、命令Ｂ４がステージ６０−５に位置し、命令Ｃ８がステージ６０−７に位置し、命令Ｃ７がステージ６０−９に位置し、命令Ｃ６がステージ６０−１１に位置し、命令Ｂ３がステージ６０−１４に位置し、命令Ａ２がステージ６０−１６に位置している状態を示している。この状態で、命令Ｂ５をステージ６０−３に伝達する指令、命令Ｂ４をステージ６０−１２に割り込ませる指令、命令Ｃ８をステージ６０−８に伝達する指令、命令Ｃ７をステージ６０−１０に伝達する指令、命令Ｂ３をステージ６０−１５に伝達する指令、命令Ａ２を整合処理部１４に出力する指令が出されている。
【００６８】
この時、プロセッシングファンクション６５−１〜６５−８にて管理されるカウンタ値が、順に、（２，６，８）、（２，５，８）、（２，４，８）、（２，４，８）、（２，４，８）、（２，３，８）、（２，３，８）、（２，３，７）、プロセッシングファンクション６５−９〜６５−１６にて管理されるカウンタ値が、順に、（２，３，７）、（２，３，６）、（２，３，６）、（２，３，５）、（２，３，５）、（２，３，５）、（２，２，５）、（２，２，５）となっている。また、プロセッシングファンクション６０−１〜６０−８にて管理される差分カウンタ値は、すべて（１，１，１）となっている。
【００６９】
続いて、図１３（ｂ）は、命令Ｂ６がステージ６０−１に位置し、命令Ｂ５がステージ６０−３に位置し、命令Ｂ４がステージ６０−１２に割り込んで位置し、命令Ｃ８がステージ６０−８に位置し、命令Ｃ７がステージ６０−１０に位置し、命令Ｃ６がステージ６０−１１に位置し、命令Ｂ３がステージ６０−１５に位置している状態を示している。この状態で、命令Ｂ６をステージ６０−２に伝達する指令、命令Ｂ５をステージ６０−４に伝達する指令、命令Ｃ８をステージ６０−９に伝達する指令、命令Ｂ４をステージ６０−１３に伝達する指令、命令Ｂ３をステージ６０−１６に伝達する指令が出されている。
【００７０】
この時、プロセッシングファンクション６５−１〜６５−８にて管理されるカウンタ値が、順に、（２，６，８）、（２，５，８）、（２，５，８）、（２，４，８）、（２，４，８）、（２，３，８）、（２，３，８）、（２，３，８）、プロセッシングファンクション６５−９〜６５−１６にて管理されるカウンタ値が、順に、（２，３，７）、（２，３，７）、（２，３，６）、（２，４，５）、（２，３，５）、（２，３，５）、（２，３，５）、（２，２，５）となっている。ここで、上述した実施の形態と同様に、命令Ｂ４が割り込み伝達されたステージ６０−１２のクラスＢに対応するカウンタ値は４にロックされ、次にクラスＢの命令が伝達されてくるまで、書き換えられない。また、プロセッシングファンクション６０−１〜６０−８にて管理される差分カウンタ値は、すべて（１，１，１）となっている。
【００７１】
続いて、図１３（ｃ）は、命令Ｂ６がステージ６０−２に位置し、命令Ｂ５がステージ６０−４に位置し、命令Ｃ８がステージ６０−９に位置し、命令Ｃ７がステージ６０−１０に位置し、命令Ｃ６がステージ６０−１１に位置し、命令Ｂ４がステージ６０−１３に位置し、命令Ｂ３がステージ６０−１６に位置している状態を示している。この状態で、命令Ｂ６をステージ６０−３に伝達する指令、命令Ｂ５をステージ６０−５に伝達する指令、命令Ｃ６をステージ６０−１２に伝達する指令、命令Ｂ４をステージ６０−１４に伝達する指令が出されている。
【００７２】
この時、プロセッシングファンクション６５−１〜６５−８にて管理されるカウンタ値が、順に、（２，６，８）、（２，６，８）、（２，５，８）、（２，５，８）、（２，４，８）、（２，３，８）、（２，３，８）、（２，３，８）、プロセッシングファンクション６５−９〜６５−１６にて管理されるカウンタ値が、順に、（２，３，８）、（２，３，７）、（２，３，６）、（２，４，５）、（２，４，５）、（２，３，５）、（２，３，５）、（２，３，５）となっている。また、プロセッシングファンクション６０−１〜６０−８にて管理される差分カウンタ値は、すべて（１，１，１）となっている。
【００７３】
続いて、図１４（ａ）は、命令Ｂ６がステージ６０−３に位置し、命令Ｂ５がステージ６０−５に位置し、命令Ｃ８がステージ６０−９に位置し、命令Ｃ７がステージ６０−１０に位置し、命令Ｃ６がステージ６０−１２に位置し、命令Ｂ４がステージ６０−１４に位置し、命令Ｂ３がステージ６０−１６に位置している状態を示している。この状態で、命令Ｂ６をステージ６０−４に伝達する指令、命令Ｂ５をステージ６０−６に伝達する指令、命令Ｂ４をステージ６０−１５に伝達する指令が出されている。
【００７４】
この時、プロセッシングファンクション６５−１〜６５−８にて管理されるカウンタ値が、順に、（２，６，８）、（２，６，８）、（２，６，８）、（２，５，８）、（２，５，８）、（２，３，８）、（２，３，８）、（２，３，８）、プロセッシングファンクション６５−９〜６５−１６にて管理されるカウンタ値が、順に、（２，３，８）、（２，３，７）、（２，３，６）、（２，４，６）、（２，４，５）、（２，４，５）、（２，３，５）、（２，３，５）となっている。また、プロセッシングファンクション６０−１〜６０−８にて管理される差分カウンタ値は、すべて（１，１，１）となっている。
【００７５】
続いて、図１４（ｂ）は、命令Ｂ６がステージ６０−４に位置し、命令Ｂ５がステージ６０−６に位置し、命令Ｃ８がステージ６０−９に位置し、命令Ｃ７がステージ６０−１０に位置し、命令Ｃ６がステージ６０−１２に位置し、命令Ｂ４がステージ６０−１５に位置している状態を示している。この状態で、命令Ｂ６をステージ６０−５に伝達する指令、命令Ｂ５をステージ６０−１１に割り込みする指令、命令Ｂ４をステージ６０−１６に伝達する指令が出されている。
【００７６】
この時、プロセッシングファンクション６５−１〜６５−８にて管理されるカウンタ値が、順に、（２，６，８）、（２，６，８）、（２，６，８）、（２，６，８）、（２，５，８）、（２，５，８）、（２，３，８）、（２，３，８）、プロセッシングファンクション６５−９〜６５−１６にて管理されるカウンタ値が、順に、（２，３，８）、（２，３，７）、（２，３，６）、（２，４，６）、（２，４，５）、（２，４，５）、（２，４，５）、（２，３，５）となっている。また、プロセッシングファンクション６０−６にて管理される差分カウンタ値は、命令Ｂ５が書き込まれるときにクラスＢの差分が２であったため、（１，２，１）となっているが、その他のプロセッシングファンクション６０−１〜６０−５，６０−７，６０−８にて管理される差分カウンタ値は、（１，１，１）である。
【００７７】
ここで、命令Ｂ６についてステージ６０−１３への割り込み判定に着目してみると、転送元ステージ６０−４のクラスＢのカウンタ値ａ＝６、差分カウンタ値ｙ＝１、転送先ステージ６０−１３のクラスＢのカウンタ値ｘ＝４であって、ａ≠ｘ＋ｙであるので、割り込みはできず、ステージ６０−５への伝達の指令が出されている。
また、命令Ｂ５についてステージ６０−１１への割り込み判定に着目してみると、転送元ステージ６０−６のクラスＢのカウンタ値ａ＝５、差分カウンタ値ｙ＝２、転送先ステージ６０−１１のクラスＢのカウンタ値ｘ＝３であって、ａ＝ｘ＋ｙであるので、割り込み伝達が可能であり、ステージ６０−１１への割り込み伝達の指令が出されている。
【００７８】
本変形例のように、プロセッシングファンクション６５に差分カウントを行わせることで、より正確な割り込み判定を実現できる。
【００７９】
【発明の効果】
本発明によれば、動的かつ柔軟に優先制御の形態を変更可能であって、同一クラスの命令の順序が逆転するのを防止可能な装置を提供することが可能となる。
【図面の簡単な説明】
【図１】図１は、本発明の実施の形態にかかる優先制御処理部を搭載したルータの構成を示すブロックダイヤグラムである。
【図２】図２は、本実施の形態にかかるルータにて実行される処理の概略を示すフローチャートである。
【図３】図３は、本実施の形態におけるパケットを説明するための図である。
【図４】図４は、本実施の形態にかかる整合処理部および優先制御処理部の構成を示すブロックダイヤグラムである。
【図５】図５は、本発明に先立って開発された整合処理部および優先制御処理部の構成を示すブロックダイヤグラムである。
【図６】図６は、本実施の形態にかかるステージの構成を示すブロックダイヤグラムである。
【図７】図７は、本実施の形態にかかる優先制御処理部を概念的に示した概念図である。
【図８】図８は、図７の概念図を用いて本実施の形態にかかる優先制御処理部の処理を時系列に表した図である。
【図９】図９は、図７の概念図を用いて本実施の形態にかかる優先制御処理部の処理を時系列に表した図である。
【図１０】図１０は、図７の概念図を用いて本実施の形態にかかる優先制御処理部の処理を時系列に表した図である。
【図１１】図１１は、図７の概念図を用いて本実施の形態にかかる優先制御処理部の処理を時系列に表した図である
【図１２】図１２は、図７の概念図を用いて本実施の形態にかかる優先制御処理部での命令の廃棄を説明するための図である。
【図１３】図１３は、図７の概念図を用いて本実施の形態の変形例にかかる優勢制御部での処理を時系列に表した図である。
【図１４】図１４は、図７の概念図を用いて本実施の形態の変形例にかかる優勢制御部での処理を時系列に表した図である。
【符号の説明】
１０　　ルータ
１２　　データパケット分解部
１４　　整合処理部
１６　　優先制御処理部
１８　　メモリ
２０　　ヘッダ処理部
２４　　データパケット合成部
２６　　スイッチ部
３０　　データラッチ
３２　　分岐回路
３４　　制御回路
２６　　遅延回路
３８　　合流回路
６０　　ステージ
６５　　プロセッシングファンクション
【図１】
2004056451.tif 000003
【図２】
2004056451.tif 000004
【図３】
2004056451.tif 000005
【図４】
2004056451.tif 000006
【図５】
2004056451.tif 000007
【図６】
2004056451.tif 000008
【図７】
2004056451.tif 000009
【図８】
2004056451.tif 000010
【図９】
2004056451.tif 000011
【図１０】
2004056451.tif 000012
【図１１】
2004056451.tif 000013
【図１２】
2004056451.tif 000014
【図１３】
2004056451.tif 000015
【図１４】
2004056451.tif 000016