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