(57)【要約】   【課題】  小規模なレジスタにより順序補償が可能なキューイング装置、優先制御機構およびルータを提供する。  【解決手段】  キューイング装置は、キューの深度がより深くなるように命令が順方向に移動する複数の順方向ステージと、キューの深度がより浅くなるように命令が逆方向に移動し、それぞれが同一の優先度を示す同一クラスの命令のシーケンス番号を格納する順序記録レジスタを有する複数の逆方向ステージとを有する。順方向ステージが、命令を受信すると、分岐路を経て命令が移動可能な、同じレベルの逆方向ステージから、受信した命令の優先度に対応するシーケンス番号を取得し、受信した命令のシーケンス番号と、逆方向ステージから取得したシーケンス番号とを比較して、命令が分岐路を経てバイパス可能か否かを判断し、その判断にしたがって、命令は、順方向ステージ或いは前記同じレベルの逆方向ステージに移動する。【選択図】  図１
2005217760.tif 000002
【特許請求の範囲】
【請求項１】
入口から出口に至る経路において、直列に配置された、パイプラインステージにおいて、キューの深度がより深くなるように命令が順方向に移動する複数の順方向ステージと、
キューの深度がより浅くなるように命令が逆方向に移動する逆方向ステージであって、それぞれが同一の優先度を示す同一クラスの命令のシーケンス番号を格納する順序記録レジスタを有する複数の逆方向ステージと、
前記順方向の経路上において、各々が所定のステージ間に配置された、少なくとも１以上の分岐回路と、
前記逆方向の経路上において、各々が所定のステージ間に配置された、少なくとも１以上の合流回路と、
それぞれが、前記分岐回路と、対応する合流回路とを接続する、少なくとも１以上の分岐路とを備え、
データの優先度およびシーケンス番号を含むヘッダ部と、データ本体とを有する命令が、前記入口から投入されると、前記ステージ間を、前記命令が順方向および逆方向に送信され、
前記逆方向ステージが、前記命令を受信すると、前記順序記録レジスタ中、前記優先度に対応する値として、前記受信した命令のシーケンス番号を格納し、かつ、
前記順方向ステージが、前記命令を受信すると、前記分岐路を経て命令が移動可能な、同じレベルの逆方向ステージから、前記受信した命令の優先度に対応するシーケンス番号を取得し、前記受信した命令のシーケンス番号と、前記逆方向ステージから取得したシーケンス番号とを比較して、命令が分岐路を経てバイパス可能か否かを判断し、前記判断にしたがって、前記命令が、順方向ステージ或いは前記同じレベルの逆方向ステージに移動するように構成されたことを特徴とするキューイング装置。
【請求項２】
前記順方向ステージが、前記受信した命令のシーケンス番号と前記逆方向ステージから取得したシーケンス番号の差分が「１」であるときに、前記命令が分岐路を経てバイパス可能であると判断するように構成されたことを特徴とする請求項１に記載のキューイング装置。
【請求項３】
前記優先度ごとのシーケンス番号が、一定の周期でリサイクルし、
前記先頭のシーケンス番号を有する命令が、順方向ステージから前記分岐路を経て同じレベルの逆方向ステージに移動したときに、前記優先度および先頭のシーケンス番号を有するダミー命令が、前記順方向ステージから順方向に移動し、
前記順方向のステージがダミー命令を受信したときに、前記順方向ステージと同じレベルの逆方向ステージが、前記順序記録レジスタ中、前記優先度に対応する値として、前記ダミー命令のシーケンス番号を格納するように構成されたことを特徴とする請求項１または２に記載のキューイング装置。
【請求項４】
優先度にしたがって命令が破棄されるキューの深度が決定され、
前記逆方向ステージが、優先度ごとに命令が廃棄されたことを示す廃棄フラグを有し、
ある深度の順方向ステージにおいて、ある優先度の命令が破棄されたときに、前記順方向ステージと同じレベルの逆方向ステージが、当該優先度の廃棄フラグをオンするとともに、当該逆方向ステージに受信された命令が、次の逆方向ステージに向けて逆方向に移動するのにともなって、前記廃棄フラグおよび前記優先度に対応するシーケンス番号を、前記次の逆方向ステージに伝えるように構成されたことを特徴とする請求項１ないし３の何れか一項に記載のキューイング装置。
【請求項５】
前記命令のヘッダ部が、分岐路を経たバイパスの可否を示すカットインフラグを含み、
前記順方向ステージが、命令が分岐路を経て移動可能なときに、受信した命令のヘッダ部のカットインフラグをオンするように構成されたことを特徴とする請求項１ないし４の何れか一項に記載のキューイング装置。
【請求項６】
前記順方向ステージに受信された命令であって、前記カットインフラグがオンである命令が、前記同じレベルの逆方向ステージに逆方向に移動する命令の優先度にしたがって、順方向ステージへ移動し、或いは、分岐路を経て同レベルの逆方向ステージに移動するように構成されたことを特徴とする請求項５に記載のキューイング装置。
【請求項７】
請求項１ないし６の何れか一項に記載のキューイング装置を用いた優先制御機構であって、
データを受け入れて、必要な命令を生成し、かつ、前記キューイング装置のパイプラインステージ数を考慮して、前記命令をキューイング装置の入口に投入する整合手段を備え、
前記キューイング装置において、所定の優先度にしたがった経路、および、場合によって分岐路を経由して命令が出力されるように構成されたことを特徴とする優先制御機構。
【請求項８】
請求項１ないし６の何れか一項に記載のキューイング装置を用いて、与えられたデータパケットを、連想されたネクストホップに送信するルータであって、
与えられたデータパケットのうち、データ長および優先度を含む、優先制御に必要な第１の部分と、それ以外の第２の部分に分解するデータ分解手段と、
前記第２の部分を記憶するメモリと、
前記第１の部分を受け入れて、必要な命令を生成し、かつ、前記キューイング装置のパイプラインステージ数を考慮して、前記命令をキューイング装置の入口に投入する整合手段と、
前記キューイング装置から出力された命令と、前記メモリからの第２の部分の少なくとも一部とを受信して、前記データパケット中のヘッダ部を合成するヘッダ処理手段と、
前記ヘッダ処理手段からヘッダ部を受け入れ、前記ネクストホップを取得する検索手段と、
前記メモリのうち、前記第２の部分の他の一部と、前記ヘッダ部とからなるデータパケットを再合成するとともに、当該データパケットに前記ネクストホップを付加するデータ合成手段と、
前記データ合成手段により再合成されたデータパケットを送信するデータ送信手段とを備えたことを特徴とするルータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キューイング装置に関し、より詳細には、キューイングの優先制御を実現する装置に関する。
【背景技術】
【０００２】
光伝送技術を始めとした、各種高速デジタル伝送技術の進展に伴い、インターネットシステムは高速大容量化の一途を辿っている。このような技術進展を前提とし、また、今後のネットワークの広帯域性を期待し、様々なサービスの導入が進められつつある。
【０００３】
このようなネットワークでは、多様なサービスに対し、それぞれに適切な品質を提供するＱｏＳ(Quality of Service)技術が必要とされてきている。これまでに、数多くのＱｏＳに関する研究が行われてきたが、ほとんどが複雑な処理機構を必要とし、実装上の課題が残されている。このような背景から、適切かつ簡易にＱｏＳ制御が実現できる、自律型ＱｏＳ制御機構が考案されている（特許文献１参照）。
【０００４】
特許文献に開示された機構は、折り返し型パイプライン構成によるキューイング機構である。より詳細には、このキューイング機構では、優先度に応じてパケットが自律的に、左ステージ（キューの深度が深くなるように順方向に送信されるステージ）から右ステージ（キューの深度が浅くなるように逆方向に送信されるステージ）へのバイパスの可否を判断して機構内を移動し、遅延や廃棄率の差別化が自律的に実現できる。
【特許文献１】特開２００３−１１０６１０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
折り返し型自律ＱｏＳ機構においては、局所的に優先制御を行うことができる。しかしながら、その柔軟さの反面として、優先度の高いクラスのパケットが優先度の低いパケットを追い越すときに、結果として、同じ優先度のパケットの順序逆転が生じる可能性がある。
【０００６】
これは、同一フローの遅延揺らぎ（ジッタ）を招き、アプリケーションによってはその影響が無視できない場合がある。たとえば、ＴＣＰ(Transmission Control Protocol)のフロー制御のように、end-to-endでシーケンス番号順序を整える方式では、順序逆転による受信側の待ち合わせ時間が増大し、スループットに大きな影響を及ぼす。このため、パケットの順序を補償する機構が望まれることになる。ただし、順序逆転を補償するために大きなバッファや複雑な処理を要し、コストが大きいと順序逆転を補償する効果が薄れてしまう。
【０００７】
本発明は、小規模なレジスタにより順序補償が可能なキューイング装置、優先制御機構およびルータを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明においては、自律的なリフレッシュレジスタを適用し、順序記録レジスタの領域を小さくすることを実現した。
【０００９】
より詳細には、本発明の目的は、入口から出口に至る経路において、直列に配置された、パイプラインステージにおいて、キューの深度がより深くなるように命令が順方向に移動する複数の順方向ステージと、キューの深度がより浅くなるように命令が逆方向に移動する逆方向ステージであって、それぞれが同一の優先度を示す同一クラスの命令のシーケンス番号を格納する順序記録レジスタを有する複数の逆方向ステージと、前記順方向の経路上において、各々が所定のステージ間に配置された、少なくとも１以上の分岐回路と、前記逆方向の経路上において、各々が所定のステージ間に配置された、少なくとも１以上の合流回路と、それぞれが、前記分岐回路と、対応する合流回路とを接続する、少なくとも１以上の分岐路とを備え、データの優先度およびシーケンス番号を含むヘッダ部と、データ本体とを有する命令が、前記入口から投入されると、前記ステージ間を、前記命令が順方向および逆方向に送信され、前記逆方向ステージが、前記命令を受信すると、前記順序記録レジスタ中、前記優先度に対応する値として、前記受信した命令のシーケンス番号を格納し、かつ、前記順方向ステージが、前記命令を受信すると、前記分岐路を経て命令が移動可能な、同じレベルの逆方向ステージから、前記受信した命令の優先度に対応するシーケンス番号を取得し、前記受信した命令のシーケンス番号と、前記逆方向ステージから取得したシーケンス番号とを比較して、命令が分岐路を経てバイパス可能か否かを判断し、前記判断にしたがって、前記命令が、順方向ステージ或いは前記同じレベルの逆方向ステージに移動するように構成されたことを特徴とするキューイング装置により達成される。
【００１０】
本発明によれば、優先度ごとにシーケンス番号を格納する順序記録レジスタを逆方向ステージのみが保持すれば足りる。したがって、レジスタ領域を小さくすることが可能となる。また、順方向ステージが、同じレベルの逆方向ステージの順位記憶レジスタの値を参照すればよいため、処理の複雑化を防止することもできる。なお、ここで、順方向ステージと、当該順方向ステージから分岐回路、分岐路および合流回路を経て命令が受信される逆方向ステージとは、同じレベルであると称する。
【００１１】
好ましい実施態様においては、前記順方向ステージが、前記受信した命令のシーケンス番号と前記逆方向ステージから取得したシーケンス番号の差分が「１」であるときに、前記命令が分岐路を経てバイパス可能であると判断する。
【００１２】
別の好ましい実施態様においては、前記優先度ごとのシーケンス番号が、一定の周期でリサイクルし、前記先頭のシーケンス番号を有する命令が、順方向ステージから前記分岐路を経て同じレベルの逆方向ステージに移動したときに、前記優先度および先頭のシーケンス番号を有するダミー命令が、前記順方向ステージから順方向に移動し、前記順方向のステージがダミー命令を受信したときに、前記順方向ステージと同じレベルの逆方向ステージが、前記順序記録レジスタ中、前記優先度に対応する値として、前記ダミー命令のシーケンス番号を格納するように構成されている。
【００１３】
さらに別の好ましい実施態様においては、優先度にしたがって命令が破棄されるキューの深度が決定され、前記逆方向ステージが、優先度ごとに命令が廃棄されたことを示す廃棄フラグを有し、ある深度の順方向ステージにおいて、ある優先度の命令が破棄されたときに、前記順方向ステージと同じレベルの逆方向ステージが、当該優先度の廃棄フラグをオンするとともに、当該逆方向ステージに受信された命令が、次の逆方向ステージに向けて逆方向に移動するのにともなって、前記廃棄フラグおよび前記優先度に対応するシーケンス番号を、前記次の逆方向ステージに伝えるように構成されている。
【００１４】
また、好ましい実施態様においては、前記命令のヘッダ部が、分岐路を経たバイパスの可否を示すカットインフラグを含み、前記順方向ステージが、命令が分岐路を経て移動可能なときに、受信した命令のヘッダ部のカットインフラグをオンする。
【００１５】
より好ましくは、前記順方向ステージに受信された命令であって、前記カットインフラグがオンである命令が、前記同じレベルの逆方向ステージに逆方向に移動する命令の優先度にしたがって、順方向ステージへ移動し、或いは、分岐路を経て同レベルの逆方向ステージに移動する。
【００１６】
本発明の目的は、上述したキューイング装置を用いた優先制御機構であって、データを受け入れて、必要な命令を生成し、かつ、前記キューイング装置のパイプラインステージ数を考慮して、前記命令をキューイング装置の入口に投入する整合手段を備え、前記キューイング装置において、所定の優先度にしたがった経路、および、場合によって分岐路を経由して命令が出力されるように構成されたことを特徴とする優先制御機構によっても達成される。
【００１７】
また、本発明の目的は、上述したキューイング装置を用いて、与えられたデータパケットを、連想されたネクストホップに送信するルータであって、与えられたデータパケットのうち、データ長および優先度を含む、優先制御に必要な第１の部分と、それ以外の第２の部分に分解するデータ分解手段と、前記第２の部分を記憶するメモリと、前記第１の部分を受け入れて、必要な命令を生成し、かつ、前記キューイング装置のパイプラインステージ数を考慮して、前記命令をキューイング装置の入口に投入する整合手段と、前記キューイング装置から出力された命令と、前記メモリからの第２の部分の少なくとも一部とを受信して、前記データパケット中のヘッダ部を合成するヘッダ処理手段と、前記ヘッダ処理手段からヘッダ部を受け入れ、前記ネクストホップを取得する検索手段と、前記メモリのうち、前記第２の部分の他の一部と、前記ヘッダ部とからなるデータパケットを再合成するとともに、当該データパケットに前記ネクストホップを付加するデータ合成手段と、前記データ合成手段により再合成されたデータパケットを送信するデータ送信手段とを備えたことを特徴とするルータによっても達成される。
【発明の効果】
【００１８】
本発明によれば、小規模なレジスタにより順序補償が可能なキューイング装置、優先制御機構およびルータを提供することが可能となる。
【発明を実施するための最良の形態】
【００１９】
以下、添付図面を参照して、本発明の実施の形態について説明する。図１は、本発明の実施の形態にかかる自律抑制型フロー制御方法を採用したシステムの例を示す図である。
【００２０】
まず、本発明に先立って優先制御処理の可能なキューイングシステムを搭載したルータについて、添付図面を参照して説明する。図１は、優先制御処理部を搭載したルータの構成を示すブロックダイヤグラムである。図１に示すように、ルータ１０は、入力されたデータパケットを受信して、これを、分解してデータ駆動パケットを生成するデータパケット分解部１２と、優先制御処理に利用するパケットの部分である優先制御処理部分を受け入れて、優先制御のために必要な種々の処理を実行する整合処理部１４と、後述する構成の折り返し自己同期パイプラインを利用してキューイングを実現するキューイング装置として機能する優先制御処理部１６と、前記データパケットのうち、優先制御処理に利用しないパケットの部分である非優先制御処理部分を受け入れて、これを一時的に記憶するメモリ１８と、優先制御処理部１６からの出力と、メモリ１８からの出力のうち、パケットのヘッダに対応する部分とを受信して、伝送プロトコルに特有の必要な処理（たとえば、ＣＲＣチェックなど）を実行するヘッダ処理部２０と、ルーティングテーブルを有し、当該ヘッダ処理部２０で処理されたヘッダ情報を受け入れて、アドレス検索を実行して、適切なネクストホップを取得するアドレス検索部２２と、ヘッダ部およびペイロード部を合成するとともに、アドレス検索部２２にて得られたネクストホップを付加するデータパケット合成部２４と、データパケットを目的の出力ポートに送信するスイッチ部２６とを備えている。
【００２１】
上記ルータにおいて、優先制御処理部１６は、後に詳述するようなデータ駆動型プログラム構造を備え、自己同期パイプラインにより、優先パケットの追い越し、先出しを実現している。また、アドレス検索部２２として、たとえば、レベル圧縮トライ木構造を利用した情報検索装置（特開２００２−２５９４５２号）を用いることができる。
【００２２】
図２は、上記ルータにて実行される処理の概略を示すフローチャートである。ルータ１０にデータパケットが入力され、データパケット分解部１２がこれを受信する（ステップ２０１）と、ルータ内部での複数のデータ駆動パケットが生成される（ステップ２０２）。
【００２３】
図３は、上記ルータにおけるパケットを説明するための図である。図３に示すように、パケット３００は、ヘッダ部３０１と、ユーザデータなどを含むペイロード部３０２とから構成される。データパケット分解部１２は、もとのデータパケットを所定の長さに分解し、各々の部分（データ部）３１１−１、３１１−２、・・・、３１１−ｎに、必要なヘッダ部（データ駆動ヘッダ部）３１２−１、３１２−２、・・・、３１２−ｎを付加して、データ駆動パケット３１０−１、３１０−２、・・・、３１０−ｎを生成する。このデータ駆動ヘッダ部３１２には、たとえば、パケットのクラス、シーケンス番号、追い越し処理の際に利用されるカットインフラグなどが含まれる。後に詳述するが、カットインフラグが「１」にセットされている場合には、データ駆動命令が、経路に沿ってキューのより深い方向に移動するのではなく、分岐路を通ることが可能となる。
【００２４】
次いで、データ駆動パケットのうち、優先制御処理に必要な部分、たとえば、Ｄｉｆｆｓｅｒｖ方式が適用されている場合には、ＤＳＣＰ形成に必要なパケットのヘッダ部情報（ＩＰｖ４パケットではＴＯＳフィールド）が、優先制御処理部分として、整合処理部１４に与えられる。上記優先制御処理部分には、たとえば、パケット長を示す情報なども含まれる。残りの部分は、非優先制御処理部分として、メモリ１８に与えられ、所定の領域に記憶される（ステップ２０３）。
【００２５】
その一方、優先制御処理部分が整合処理部１４に受信されると、整合処理部１４は、優先制御処理部１６のキューの深度（キューデプス）を管理するための必要な演算等を施すとともに、オペレーションコード、行き先、世代番号など、データ駆動型プログラム構造を備えた優先制御処理部１６における演算が可能となるように、優先制御処理部分に必要な情報を付加したデータ駆動命令（以下、単に「命令」と称する。）を生成する。生成された命令は、優先制御処理部１６に投入され、ここでキューイングが実行される（ステップ２０５）。
【００２６】
図４は、上記ルータの整合処理部１４および優先制御処理部１６の構成を示すブロックダイヤグラムである。図４に示すように、優先制御処理部１６は、データ（優先制御処理部分）の入口から出口に至るまで、直列に配置された複数のステージ（また、図面においては、「ＳＴ」と表記している。）６０−１、６０−２、・・・、６０−ｉを有し、「ｉ」段のパイプラインを構成している。
【００２７】
上記ルータにおいて、優先制御処理部１６のステージ６０は、機能的に、命令が徐々にキューの深い部分に進み（矢印４０１参照）、折り返し点から、徐々に浅い部分に戻るような（矢印４０２参照）構造となっている。本明細書において、このような構造を「折り返し構造」と称し、また、キューの深い部分に進む方向を順方向、キューの浅い部分に進む方向を逆方向と称する。
【００２８】
優先制御処理部１６において、矢印４０１に示す第１の方向には、隣接するステージの間に、分岐回路（図面において、「Ｂ」と表記している。）３２−１、３２−２、・・・が配置されている。その一方、矢印４０２に示す第２の方向には、隣接するステージの間に、合流回路（図面において、「Ｊ」と表記している。）３８−１、３８−２、・・・が配置されている。
【００２９】
図４に示すように、ある分岐回路、たとえば、分岐回路３２−１は、分岐路４１０−１を経て、ある合流回路３８−１と接続されている。つまり、上記優先制御処理部１６においては、命令の入口、および、命令の出口と、同じ距離だけ離間して配置された分岐回路および合流回路が、分岐路にて接続されている。このように分岐路で結ばれた分岐回路および合流回路は、同じレベルであると称する。たとえば、図４における分岐回路３２−１と合流回路３８−１は同じレベルにある。また、課題を解決するための手段において定義したように、分岐回路にデータを送信する、順方向の経路上のステージ（順方向ステージ）と、当該分岐回路と同じレベルにある合流回路からデータを受信する、逆方向の経路上のステージ（逆方向ステージ）とは同じレベルであると称する。たとえば、図４におけるステージにおいて、ステージ６０−１と、ステージ６０−ｉとは同じレベルにある。
【００３０】
また、優先制御処理部１６は、ステージ６０間のデータ転送を制御する制御回路（図面において「Ｃ」と表記している。）３４−１、３４−２、・・・、３４−ｉと、制御回路間の信号伝送に、必要な遅延を与える遅延回路（図面において、「Ｄｅｌａｙ」と表記している。）３６−１、３６−２、・・・、３６−(i-1)を有している。
【００３１】
上記構成の優先制御処理部１６の動作について以下に説明する。命令が投入されると、データラッチは、オペレーションコードや行き先を参照して、命令を分岐回路３２−１に送信する。たとえば、優先度が最も低い命令（本実施の形態では、優先度「Ｃ」の命令）であれば、ステージ６０−１、分岐回路３２−１、ステージ６０−２、分岐回路３２−２、・・・という順で、他の優先度の命令と較べて、徐々に、順方向（矢印４０１の方向）の経路に沿って進められる可能性が高くなる。分岐点に到達すると、今度は、逆方向（矢印４０２の方向）の経路に沿って順次戻され、合流回路３８−２、ステージ６０−(i-1)、合流回路３８−１、ステージ６０−ｉを経て出力される。
【００３２】
その一方、優先度が高い命令（たとえば、優先度「Ａ」の命令など）であれば、ある分岐回路（たとえば、分岐回路３２−２）において、同じレベルの合流回路に逆方向４０２から入力されようとする他の命令と比較して優先度が高ければ、第１の方向４０１のステージ（たとえば、ステージ６０−３）に命令が送信されるのではなく、分岐路（たとえば、分岐路４１０−２）を経て、同レベルに位置する合流回路（たとえば、合流回路３８−２）に送信される。この命令は、ステージ６０−（ｉ−１）を経て、出口の最も近くに配置されたステージ６０−ｉに送信され、その後、優先制御処理部１６から出力される。これにより、分岐路を使わずに順次ステージに送信されるような命令を追い越して、先出しするようなキューイングを実現することができる。
【００３３】
上記ルータにおいては、優先度が高いほど、より入口および出口に近いレベルの分岐路を利用することができるように設定されている。したがって、優先度に応じて、経路の長さ（つまり、入口から出口に至るまでに通るべきステージの数）を、所望のように制御することが可能である。
【００３４】
次に、制御回路３４について説明を加える。上記ルータにおいて、制御回路３４は、ステージに、ラッチしている命令の送信を求めるトリガを出力する。接続されたステージにトリガを与えるのに先立って、制御回路は、隣接して配置された他の制御回路であって、命令の送信方向（順方向４０１或いは逆方向４０２）に配置されている他の制御回路に、SEND信号を送信する。SEND信号を受信した他の制御回路は、接続されたステージが命令を受け入れ可能であれば、ACK信号を、SEND信号を出力した制御回路に返送する。
【００３５】
ここで、ACK信号は、遅延回路３６を介して、所定の遅延が与えられて、SEND信号の送信元の制御回路に送信される。この遅延Ｄは、元のパケットの長さＬに比例するように設定される。上記ルータにおいては、ルータ１０中に優先制御処理部１６を配置している。したがって、与えられるパケットは可変長のものであり、パケットの長さＬを考慮しないと、優先制御処理後のパケット処理や出力のタイミングを誤るおそれがある。たとえば、長さＬが比較的長いパケット（先行パケット）に関する優先制御が終了した直後に、次のパケット（後続パケット）の優先制御を行える状態とすると、先行パケットに関する上記パケット処理や出力の途中で、後続パケットに関する上記パケット処理や出力が割り込む可能性があるからである。そこで、元のパケット長を考慮して、パケット処理および終了するタイミングを見計らって、処理を進めるような構造としている。したがって、後続パケットは、直前に優先制御処理部１６において処理されたパケットの本来のパケット長に応じた時間、入力や割り込みを待たされることになる。
【００３６】
パケットのペイロード部まで含めてキューイングをすれば、上述した待機をする必要は無いが、優先制御に不要なデータ駆動パケットまで、優先制御処理部１６を通過させることは冗長であり、また、そのようなパケットを受け入れるためには、優先制御処理部１６の回路を大規模なものにしなければならず、製造コストが著しく増大する。そこで、上記ルータにおいては、優先制御に必要な部分のみをとりだして、これを優先制御処理部１６に投入し、残りの部分はメモリに記憶して、後にパケットを再合成するように構成している。
【００３７】
また、上記ルータにおいて、整合処理部１４は、優先制御処理部分を受信して、これを命令として優先制御処理部１６に投入するときに、優先制御処理部１６におけるキューデプス残量Ｑを、Ｑ＝Ｑ−Ｌに更新する（Ｌは、前述したように元のパケット長）。その一方、元のパケット長がＭであるような命令を、優先制御処理部１６から受信した際に、これを出力する前に、キューデプス残量Ｑを、Ｑ＝Ｑ＋Ｍに更新する。これにより、たとえば、投入する命令数が、パイプラインステージ数を超えないように、優先制御処理部１６に投入可能な命令数を管理することが可能となる。
【００３８】
なお、整合処理部１４においてパケットを廃棄（Ｄｒｏｐ）する代わりに、或いは、整合処理部１４におけるパケットの廃棄に加えて、優先制御処理部１６においてパケットを廃棄するような構成をとっても良い。ここでは、図４に示す分岐回路３２−ｊ（ｊ＝１、２、・・・）においてパケットの廃棄が実現される。本実施の形態においては、後述するように、優先度に応じてパケットを破棄するレベル（キューの深度のレベル）が決定されている。
【００３９】
優先制御処理部１６から処理の終了した命令が出力されると、整合処理部１４を介して、ヘッダ処理部２０に与えられる。また、整合処理部１４から、出力された命令に関するヘッダ部の読み出し要求がメモリ１８に与えられ（符号１０１参照）、メモリ１８から、対応するパケットの非優先処理部分が読み出される（ステップ２０６）。メモリ１８から読み出された非優先処理部分のうち、元のパケットのヘッダ部に対応する部分がヘッダ処理部２０に与えられる。ヘッダ処理部２０においては、元のパケットのヘッダ部（図３の符号３０１参照）により、データ駆動パケットのデータ部（図３の符号３１１−１、３１１−２、・・・）が処理される（ステップ２０７）。
【００４０】
再生成されたヘッダ部は、アドレス検索部２２に与えられ、そこで、パケットの次の宛先であるネクストホップが取得され（ステップ２０８）、ヘッダ部とともにネクストホップが、データパケット合成部２４に与えられる。その一方、メモリから読み出された非優先処理部分のうち、元のパケットのペイロードに対応する部分も、データパケット合成部２４に与えられる。
【００４１】
データパケット合成部２４は、ヘッダ部とペイロード部とを合成し、かつ、ネクストホップを付加して（ステップ２０９）、これをスイッチ部２６に送信する。スイッチ部２６は、受信したパケットを目的の出力ポートにスイッチする（ステップ２１０）。このようにして、ルータ１０に入力されたパケットが、次の目的地に向けて送信される。
【００４２】
このように上記優先制御処理部１６においては、折り返しを有する自己同期パイプラインにより、当該優先制御処理部１６を構成し、優先パケットの追い越し、先出しを実現している。また、データ駆動型プログラム構造を採用することにより、優先度の設定を所望のように変更することができる。また、元のパケット長を考慮して、データラッチ間の命令の伝送を制御することにより、優先制御に必要なパケット中の部分のみを優先制御処理部１６に投入すればよく、回路規模の小さな優先制御処理部１６を実現することができる。
【００４３】
ところで、上記ルータにおいて、折り返しを有する自己同期パイプラインにより優先制御処理部１６を構成しているので、命令の折り返しの可否についてなんら制御を行わないと、同一のデータパケット３１０を分解して生成した同一クラスの複数の命令の順序が優先制御処理部１６の中で逆転してしまう可能性がある。たとえば、図５示すように、最も優先度の高い優先度「Ａ」の命令「Ａ１」、最も優先度の低い優先度「Ｃ」の命令「Ｃ２」〜「Ｃ４」とともに、優先度「Ａ」と優先度「Ｃ」との間の優先度を有する優先度「Ｂ」の命令「Ｂ１」〜「Ｂ３」が、それぞれのステージに位置している場合を考える。なお、命令における最初のアルファベットが、その命令の優先度を示し、後続する番号が命令のシーケンス番号(Sequence Number)を示す。ここで、命令「Ｂ３」に後続すべき命令「Ｂ２」が、優先度のみを考慮して、ステージ６０−３から分岐路４１０−３を経てステージ６０−（ｉ−２）に移動すると、ステージ６０−５に位置する命令「Ｂ２」との順序の逆転が生じる。
【００４４】
そこで、本実施の形態では、このような順序逆転現象を防止するため、以下に詳細に説明するような順序逆転防止機構を設けた。また、順序逆転防止機構において、大きなバッファを設けることや、機構を複雑にすることは、順序補償の効果が薄れてしまう。そこで、本実施の形態では、優先度ごとに命令のシーケンス番号を記録する順序記録レジスタを最小限にすることでバッファ容量を小さくするとともに、フラグを用いることで機構の複雑さを回避している。
【００４５】
図６（ａ）、（ｂ）は、本実施の形態にかかるステージ６０の構成を示すブロックダイヤグラムである。図６（ａ）は、順方向に配置されたステージ（以下、「順方向ステージ」とも称する。）６０を示し、図６（ｂ）は、逆方向に配置されたステージ（以下、「逆方向ステージ」とも称する。）６０を示す。図６（ａ）（ｂ）に示すように、ステージ６０は、プロセッシングファンクション（図面において、「ＰＦ」と表記し、かつ、以下図面表記と同様に「ＰＦ」とも称する。）６５とデータラッチ３０から構成されている。
【００４６】
ＰＦ６５は、優先度を比較して、分岐回路３２や合流回路３８のスイッチを切り換えて、パケットの分岐路４１０を経た送信を制御する。また、ＰＦ６５は、データラッチ３０に一時的に位置したパケットのフラグをオン／オフする機能も有する。さらに、逆方向ステージに含まれるＰＦ６５のみが、順序補償のための順序記録レジスタ６５０を有する。図６（ｂ）に示すように、逆方向ステージに含まれるＰＦ６５は、優先度ごとの順序記録レジスタ６５０と、優先度ごとの廃棄フラグ６５１を有している。本実施の形態においては、優先度の高い順に、「Ａ」、「Ｂ」および「Ｃ」の３つの優先度を有している。したがって、順序記憶レジスタ６５０にも、優先度「Ａ」〜「Ｃ」のそれぞれのシーケンス番号(Sequential Number)が格納できる。また、優先度「Ａ」〜「Ｃ」のそれぞれの廃棄フラグの値は初期的には「０」である。
【００４７】
このように構成された順序記録レジスタを用いた命令の移動制御について以下に説明する。命令が、逆方向ステージ６０のデータラッチ３０に受信されると、当該ステージのＰＦ６５は、命令の優先度およびシーケンス番号を取得し、順序記録レジスタ中、対応する優先度について取得したシーケンス番号を記録する。図７は、本実施の形態にかかる優先制御機構の部分を示す。図７においては、説明の便宜上、分岐回路、合流回路および制御回路を省略し、順方向ステージ間の経路、逆方向ステージ間の経路、および、同じレベルの順方向ステージと逆方向ステージとの間の分岐路のみを示す。また、図７において、順方向ステージでは基本的に上向きに命令が移動し、かつ、逆方向ステージでは基本的に下向きに命令が移動するようになっている。
【００４８】
図７（ａ）に示すように、逆方向ステージ６０−（ｑ−１）に、命令「Ｂ２」が位置している。したがって、このステージの順序記録レジスタ６５０−（ｑ−１）の値（Ａ，Ｂ，Ｃ）は、（ｘ，２，ｙ）となっている。ここに、ｘおよびｙは任意の値である。その一方、逆方向ステージ６０−（ｑ−１）に逆方向の経路で接続された逆方向ステージ６０−ｑにおいては、命令「Ｂ１」（図示せず）が通過したため、順序記録レジスタ６５０−ｑの値（Ａ，Ｂ，Ｃ）は、（ｘ，１，ｙ）である。ここで、図７（ａ）に示すように、順方向ステージ６０−ｐに命令「Ｂ３」が受信されたとする。図８は、命令を受信した順方向ステージにて実行される処理を示すフローチャートである。
【００４９】
順方向ステージ６０−ｐのＰＦ（図７では図示せず）は、受信した命令の優先度（この場合には「Ｂ」）を取得して（ステップ８０１）、同じレベルの逆方向ステージ６０−ｑのＰＦに保持された順序記録レジスタ中、取得した優先度に対応する値を調べる（ステップ８０２）。図７（ａ）の例では、対応する値は「１」である。
【００５０】
次いで、順方向ステージ６０−ｐのＰＦは、受信した命令のシーケンス番号を参照して、「受信した命令のシーケンス番号−順序記録レジスタ中のシーケンス番号＝１」であれば（ステップ８０３でイエス(Yes)）、命令のデータ駆動ヘッダ部（図３参照）に設けられたカットインフラグを「１」にセットする（ステップ８０４）。その一方、ステップ８０３でノー(No)であれば、命令のデータ駆動ヘッダ部のカットインフラグは、オフ状態（つまり「０」のまま維持される。図７（ａ）の例では、「３−１≠１」であるため、命令「Ｂ３」のカットインフラグは「０」のまま維持される（ステップ８０５：このステップにおいて、実際にはＰＦは何ら処理を実行しない）。したがって、分岐路を通って追い越しをすることはできず（Disable）、順方向の経路を通って次の順方向ステージ６０−（ｐ＋１）に移動する（図７（ａ）の矢印７０１および図７（ｂ）参照）。
【００５１】
その一方、図７（ｂ）の状態で、順方向ステージ６０−（ｐ＋１）のＰＦが、同じレベルの逆方向ステージ６０−（ｑ−１）のＰＦに保持された順序記録レジスタ中、優先度「Ｂ」のシーケンス番号を取得する。この状態で、「受信した命令のシーケンス番号−順序記録レジスタ中のシーケンス番号」を算出すると、「３−２＝１」であるため、順方向ステージ６０−（ｐ＋１）のＰＦは、命令「Ｂ３」のデータ駆動ヘッダ部のカットインフラグを「１」にセットする。これにより、命令「Ｂ３」は、他の条件がそろえば、分岐路を通って逆方向ステージに移動することができる（矢印７０２参照）。なお、いったんカットインフラグが「１」とされると、他のステージのＰＦは、図８に示す処理を実行する必要はない。つまり、ＰＦは、まずカットインフラグが「０」である場合のみ、図８の処理を実行すれば足りる。
【００５２】
カットインフラグが「１」となった命令は、優先度に応じて、分岐路を通ってバイパスすることが可能となる。図９（ａ）の例において、順方向ステージ６０−ｐに命令「Ｂ３」が移動すると、順方向ステージ６０−ｐのＰＦは、図８に示す処理を実行して、「受信した命令のシーケンス番号−順序記録レジスタ中のシーケンス番号」が「１」であるか否かを判断する。この例では、上記差分は「１」になるため、命令「Ｂ３」のカットインフラグは「１」にセットされ、イネーブル（Enable）な状態となる。無論、命令「Ｂ３」がそれより以前に位置していた順方向ステージにおいて、そのカットインフラグが「１」にセットされている可能性もある。
【００５３】
このような場合には、逆方向ステージにおける逆方向の経路の移動（図９（ａ）の符号９０２参照）と競合がある場合には、命令の優先度に応じて、バイパスの可否が決定される。この場合、順方向ステージ６０−ｐから分岐路を経た逆方向ステージへの移動（図９（ａ）の符号９０１参照）と競合する移動は、逆方向ステージ６０−（ｑ−１）からの命令「Ｃｋ」（ｋは適当なシーケンス番号）の移動である。優先度は、「Ｂ＞Ｃ」であるから、命令「Ｂ３」のバイパスが優先される。これにより、図９（ｂ）に示すように、命令「Ｂ３」が、分岐路を経てバイパスされ、逆方向パケット６０−ｑに移動する。
【００５４】
このように、本実施の形態によれば、逆方向ステージのみが順序記録レジスタを保持し、当該逆方向ステージのデータラッチに命令が受信されたときに、逆方向ステージのＰＦが、命令の優先度に対応する順序記録レジスタに、当該命令のシーケンス番号を書き込む。また、順方向ステージのデータラッチに命令が受信されたときに、当該順方向ステージのＰＦは、同じレベルの逆方向ステージの順序記録レジスタ中、優先度が対応するシーケンス番号を取得して、受信した命令が分岐路を通ってバイパス（追い越し）可能であるかを判断する。バイパス可能であれば、命令中のカットインフラグを「１」にセットして、その命令が他の条件を満たすとき（逆方向ステージで競合する命令の優先度が自己の優先度より低いとき）に、分岐路を通ることができる状態にする。これにより、レジスタ領域を小さくすることができ、かつ、複雑な処理を経ることなく、順序補償を実現することが可能となる。
【００５５】
次に、廃棄フラグについて説明する。本実施の形態においては、一定のキューの深度のレベルで、命令が廃棄されるように構成されている。図１０に示すように、破線Ａが優先度「Ａ」の命令が廃棄されるレベルを示し、破線Ｂが優先度「Ｂ」の命令が廃棄されるレベルを示す。したがって、優先度「Ａ」の命令が、順方向ステージ６０−３に達し、分岐路４１０−３を介して同レベルの逆方向ステージに移動できなければ、順方向６０−４に移動することなく廃棄される。同様に、優先度「Ｂ」の命令が、順方向ステージ６０−６に達し、分岐路４１０−６を介して同レベルの逆方向ステージに移動できなければ、順方向６０−７に移動することなく廃棄される。命令が廃棄されると、後続する命令が適切に追い越しをすることができなくなる。したがって、本実施の形態では、ある優先度の命令が廃棄されたことを廃棄フラグによって記録する。
【００５６】
なお、図１０では、順方向および逆方向にそれぞれ８つのステージが設けられ、キューの深度も８レベルになっているが、キューの深度はこれに限定されない。また、命令が廃棄されるレベルについても、上記図１０の例に限定されないことは言うまでもない。
【００５７】
たとえば、図１１（ａ）に示すように、順方向ステージ６０−６に移動した優先度「Ｂ」の命令「Ｂ３」が、分岐路４１０−６を通って、同じレベルの逆方向ステージ６０−１１にバイパスできない場合を考える（符号１１０１参照）。この場合、命令「Ｂ３」は、順方向に、より深いレベルの順方向ステージに移動することなく廃棄される。命令が廃棄されると、当該順方向ステージ６０−６のＰＦは、同じレベルの逆方向ステージ６０−１１のＰＦに、廃棄された命令の優先度およびシーケンス番号を伝える。逆方向ステージ６０−１１のＰＦは、これらを受信すると、優先度「Ｂ」に対応する廃棄フラグを「１」にセットするとともに（符号６５１−１１および１１０２参照）、順序記録レジスタ６５０−１１中、優先度「Ｂ」に対応するシーケンス番号を「３」にセットする。
【００５８】
廃棄フラグが「１」にセットされると、逆方向ステージを命令が移動するのに伴って、当該廃棄フラグがセットされた優先度のシーケンス番号も、廃棄フラグとともに、次の逆方向ステージに移動される。シーケンス番号の移動元の逆方向ステージにおいては、シーケンス番号を移動させた後、廃棄フラグがリセットされる。図１１（ａ）の例では、逆方向ステージ６０−１１に位置する命令「Ｃ２」が、次の逆方向ステージ６０−１２に移動すると、優先度「Ｂ」の廃棄フラグが「１」であるため、これに伴って、優先度「Ｂ」の廃棄フラグ、および、順序記録レジスタ中、優先度「Ｂ」のシーケンス番号が、逆方向ステージ６０−１２に移動する（符号６５０−１２、６５１−１２参照）。また、図示はしないが、移動の後、移動元の廃棄フラグはリセットされる。これにより、逆方向ステージのそれぞれに、廃棄された命令のシーケンス番号を伝えることができる。
【００５９】
次に、本実施の形態における順序記録レジスタのリフレッシュについて説明する。順序記録レジスタのビット数は有限であるため、優先度ごとにシーケンス番号は、リサイクルされる。同じシーケンス番号が、異なるサイクル（或いは、周期）では用いられ得る。シーケンス番号のリサイクル時のシーケンスの誤認識を防止するため、一周期に一度、全パイプラインにおいて、順序記録レジスタの、当該優先度の値をリセットする必要がある。
【００６０】
具体的には、一周期が終了した後、次の周期の先頭のシーケンス番号を有する命令が、分岐路を経てバイパスし、或いは、廃棄されたときに、順方向ステージに、当該優先度でかつ同じシーケンス番号を有するダミー命令を移動させる。
【００６１】
図１２に示すように、たとえば、優先度「Ｂ」で、かつ、先頭のシーケンス番号「０」を有する命令「Ｂ０」が、順方向ステージ６０−２に移動した段階で、そのカットインフラグが「１」であったと考える。ここでは、逆方向ステージ６０−（ｒ−２）からの、優先度「Ｃ」の命令「Ｃ２」と移動が競合するが、優先度にしたがって、命令「Ｂ０」が、分岐路４１０−１を経て移動できる（矢印１２０１参照）。命令Ｂ０の移動により、逆方向ステージ６０−（ｒ−１）においては、通常と同様に、順序記録レジスタ中、優先度「Ｂ」に対応する値に、シーケンス番号「０」が記録される。
【００６２】
また、命令「Ｂ０」が逆方向ステージに移動すると、次の順方向ステージに、順方向に、同じ優先度およびシーケンス番号を有するダミー命令が移動される。このダミー命令は、順方向に、順次移動されていく（符号１２０２〜１２０４参照）。ダミー命令は、分岐路を経て逆方向ステージに移動することはない。ダミー命令が順方向ステージ６０−３に移動すると、順方向ステージ６０−３のＰＦは、同じレベルの逆方向ステージに、ダミー命令の優先度およびシーケンス番号を伝える。逆方向ステージ６０−（ｒ−２）のＰＦは、ダミー命令の優先度およびシーケンス番号を受信すると、順序記録レジスタ中、受信した優先度「Ｂ」に対応する値に、受信したシーケンス番号「０」を記録する。この処理が、順方向ステージにダミー命令が移動するたびに実行される。これにより、図１２の右端に示すように、逆方向ステージにおいて、順序記録レジスタ中、リフレッシュの必要な優先度に対応する値が「０」にリセットされる。ダミーパケットは、最後の順方向ステージ、つまり、キューにおいて最も深いレベルの順方向ステージまで移動した後に消滅する。
【００６３】
なお、命令「Ｂ０」が、逆方向ステージを、逆方向、つまり、データ出力に向けて移動する。したがって、命令「Ｂ０」が移動した逆方向ステージにおいては、通常通り、順序記録レジスタ中、優先度「Ｂ」に対応する値が、「０」に更新される。これにより、全ての逆方向レジスタにおいて、順位記憶レジスタ中、リフレッシュの必要な優先度に対応する値を「０」にすることができる。
【００６４】
本発明は、上記実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【００６５】
図１０に関連して説明したように、ステージのレベルは上記実施の形態に限定されるものではない。また、シーケンス番号の最大値は、順序記録レジスタにおいて記録できる値の最大値よりも小さければよい。
【図面の簡単な説明】
【００６６】
【図１】図１は、本発明の実施の形態にかかる優先制御機構を採用したシステムの例を示す図である。
【図２】図２は、本実施の形態にかかるルータにて実行される処理の概略を示すフローチャートである。
【図３】図３は、本実施の形態にかかるルータにおけるパケットを説明するための図である。
【図４】図４は、ルータの整合処理部および優先制御処理部の構成を示すブロックダイヤグラムである。
【図５】図５は、優先制御処理部のステージ間の命令の移動を説明するための図である。
【図６】図６（ａ）、（ｂ）は、本実施の形態にかかるステージの構成を示すブロックダイヤグラム、図６（ｃ）は、逆方向ステージに設けられた順序記録レジスタおよび廃棄フラグを示す図である。
【図７】図７は、本実施の形態におけるステージ間の命令の移動の例を説明する図である。
【図８】図８は、本実施の形態において、命令を受信した順方向ステージにて実行される処理を示すフローチャートである。
【図９】図９は、本実施の形態におけるステージ間の命令の移動の他の例を説明する図である。
【図１０】図１０は、本実施の形態における命令の廃棄レベルの例を示す図である。
【図１１】図１１は、本実施の形態において、命令を廃棄された際に実行される処理を説明する図である。
【図１２】図１２は、本実施の形態において、レジスタをリフレッシュする際に実行される処理を説明する図である。
【符号の説明】
【００６７】
１０    ルータ
１２    データパケット分解部
１４    整合処理部
１６    優先制御処理部
１８    メモリ
２０    ヘッダ処理部
２２    アドレス検索部
２４    データパケット合成部
２６    スイッチ部
３０    データラッチ
３２    分岐回路
３４    制御回路
２６    遅延回路
３８    合流回路
６０    ステージ
６５    プロセッシングファンクション（ＰＦ）
４１０  分岐路
【図１】
2005217760.tif 000003
【図２】
2005217760.tif 000004
【図３】
2005217760.tif 000005
【図４】
2005217760.tif 000006
【図５】
2005217760.tif 000007
【図６】
2005217760.tif 000008
【図７】
2005217760.tif 000009
【図８】
2005217760.tif 000010
【図９】
2005217760.tif 000011
【図１０】
2005217760.tif 000012
【図１１】
2005217760.tif 000013
【図１２】
2005217760.tif 000014