ルータ装置、ルータ装置の制御方法
【課題】ルータを通過するパケットの通信経路に依存することなく、レイテンシの削減を図ること
【解決手段】バッファ４＿１〜４＿３は、出力待ちとなるパケットを一時的に保持する。先行出力検出回路５＿１は、あるサイクルにおける出力Ｐ１への出力を要求するパケットの入力状態と、バッファ４＿１〜４＿３の格納状態と、に基づいて調停処理の対象とならない先行出力対象パケットを検出する。出力選択回路７＿１は、先行出力対象パケットを検出した場合に当該パケットを出力Ｐ１から出力するパケットと決定し、先行出力対象パケットを検出しなかった場合に調停処理に基づいて出力Ｐ１から出力するパケットと決定する。スイッチ９は、出力選択回路７＿１の決定に基づいて、出力Ｐ１への配線切替えを制御する。
【解決手段】バッファ４＿１〜４＿３は、出力待ちとなるパケットを一時的に保持する。先行出力検出回路５＿１は、あるサイクルにおける出力Ｐ１への出力を要求するパケットの入力状態と、バッファ４＿１〜４＿３の格納状態と、に基づいて調停処理の対象とならない先行出力対象パケットを検出する。出力選択回路７＿１は、先行出力対象パケットを検出した場合に当該パケットを出力Ｐ１から出力するパケットと決定し、先行出力対象パケットを検出しなかった場合に調停処理に基づいて出力Ｐ１から出力するパケットと決定する。スイッチ９は、出力選択回路７＿１の決定に基づいて、出力Ｐ１への配線切替えを制御する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はルータ装置及びルータ装置の制御方法に関する。
【背景技術】
【０００２】
現在、単一のチップ上にプロセッサ等の設計モジュールを複数配置することが可能となっている。Ｎｅｗｗｏｒｋ−ｏｎ−Ｃｈｉｐ（以下、ＮｏＣと記載する）は、配置したＩＰコア等の設計モジュールの結合に用いられる回路である。ＮｏＣは、ルータと呼ばれるスイッチング回路を複数備える構成である。
【０００３】
図１２は、半導体におけるＩＰコアとルータの配置例を示す図である。図示するように、複数のＩＰコアがルータを経由して間接的に接続されている。ルータには、隣接するルータまたはＩＰコアからパケット化された入力データが入力される。ルータは、受信したパケットデータの出力方向を決定し、次のルータまたは送信先のＩＰコアにデータを送信する。
【０００４】
ルータの機能は、主に経路計算、スイッチ調停、スイッチ転送の３つである。ルータの標準的な構造を図１３に示す。ルータ装置１は、複数の入力ポート（入力Ｐ１〜入力Ｐ３）及び複数の出力ポート（出力Ｐ１〜出力Ｐ３）を備える。また、ルータ装置１は、ラッチ２＿１〜２＿３、経路計算回路３＿１〜３＿３、バッファ４＿１〜４＿３、調停回路６＿１〜６＿３、制御記憶回路８、及びスイッチ９を備える。ラッチ２＿１〜２＿３、経路計算回路３＿１〜３＿３、及びバッファ４＿１〜４＿３は、入力Ｐ１〜入力Ｐ３にそれぞれ対応づけられている。調停回路６＿１〜６＿３は、出力Ｐ１〜出力Ｐ３に対応づけられている。例えば、ラッチ２＿１、経路計算回路３＿１、及びバッファ４＿１は入力Ｐ１に対応づけられている。調停回路６＿１は、出力Ｐ１に対応づけられている。
【０００５】
ラッチ２＿１〜２＿３は、対応する入力ポートから入力されたパケットを一時的に保持し、その後にパケットを対応する経路計算回路３＿１〜３＿３に出力する。
【０００６】
経路計算回路３＿１〜３＿３は、経路計算を行う回路である。以下、経路計算回路３＿１を例に説明する。経路計算回路３＿１は、入力Ｐ１から入力されたパケットのヘッダに記載された送信先ＩＰコアの情報、または送信方向の情報を基に出力ポート番号を決定する。経路計算回路３＿１は、決定した出力ポート番号とともにパケットを対応するバッファ４＿１に格納する。
【０００７】
バッファ４＿１〜４＿３は、経路計算回路が出力したパケットを出力先の出力ポート番号と対応づけて一時的に格納する。バッファ４＿１〜４＿３は、複数のパケットを保持可能である。バッファ４＿１〜４＿３は、後述の制御記憶回路８からのパケット出力の要求に応じてパケットをスイッチ９に供給する。
【０００８】
調停回路６＿１〜６＿３は、バッファ４＿１〜４＿３に一時的に格納されたパケットのうち、対応する出力ポートが次サイクルに出力するパケットを選択する回路である。以下、調停回路６＿１を例に説明する。調停回路６＿１は、バッファ４＿１〜４＿３に格納されたパケット及び当該パケットの出力パケット番号を基に、対応する出力ポートである出力Ｐ１から次サイクルにおいて出力するパケットを決定する。調停回路６＿１は、決定した出力パケットが入力された入力ポート番号を制御記憶回路８に書き込む。
【０００９】
制御記憶回路８は、あるサイクルにおいて、各出力ポートが出力対象とするパケットを入力した入力ポート番号を記憶する。さらに、制御記憶回路８は、パケット出力要求をバッファ４＿１〜４＿３にそれぞれ伝達する。
【００１０】
スイッチ９は、算出された調停回路６＿１〜６＿３の調停結果（すなわち、各出力ポートが出力すべきパケットが入力された入力ポート番号）が制御記憶回路８を介して入力され、当該調停結果に応じて入力ポートと出力ポートを接続する。詳細には、スイッチ９は、接続対象の入力ポートに対応づけられているバッファからの出力を、出力先となる出力ポートに接続する。
【００１１】
一般に、ルータは経路計算回路による経路計算、調停回路によるスイッチ調停、スイッチによるスイッチ転送にそれぞれ１サイクルのレイテンシを必要とする。この場合、ルータの通過レイテンシは、３サイクルとなる。図１３に示すルータ装置の動作を図１４のタイミングチャートを参照して説明する。
【００１２】
図１４は、図１３のルータ装置において、入力Ｐ１に入力されたパケットを出力Ｐ３から出力する際の動作を示すタイミングチャートである。図１４では、図１３の各点Ａ〜Ｆを通過する信号を示している。ここで、バッファ４＿１〜４＿３には、パケットが格納されていないものとする。
【００１３】
ラッチ２＿１は、サイクルｔにおいて入力されたパケットのヘッダを保持する（図１４Ａ参照）。ラッチ２＿１は、このパケットのヘッダをサイクルｔ＋１において出力する。経路計算回路３＿１は、このパケットヘッダ及び経路計算結果をバッファ４＿１に格納する（図１４Ｂ参照）。調停回路６＿３は、サイクルｔ＋２において、出力パケットの調停を行う。これにより、サイクルｔ＋２において、このパケットヘッダは出力権を得る。すなわち、このパケットヘッダは、バッファ４＿１からの出力対象となる。
【００１４】
調停回路６＿３は、調停結果を制御記憶回路８に書き込む。詳細には、調停回路６＿３は、出力Ｐ３から出力されるパケットの入力ポートが"１"であることをサイクルｔ＋２において書き込む（図１４Ｄ参照）。サイクルｔ＋２において、制御記憶回路８から出力されるバッファ４＿１への指示信号は「停止」である（図１４Ｅ参照）。そのため、サイクルｔ＋２においては、バッファ４＿１は、パケットを出力したものとみなされない。換言すると、バッファ４＿１は、サイクルｔ＋３においてもサイクルｔ＋２と同一の出力を行い続ける（図１４Ｃ参照）。
【００１５】
調停回路６＿３が制御記憶回路８に"１"を入力したことにより、制御記憶回路８は、バッファ４＿１に出力許可（"許可"）の信号を通知する（図１４Ｅ参照）。この許可信号を受けて、バッファ４＿１は、パケットのヘッダの出力が行われたと判断し、バッファ内の更新を行う。この更新により、サイクルｔ＋４では、バッファ４＿１は、サイクルｔ＋１にて入力されたパケットのデータを出力する。このパケットのデータは、サイクルｔ＋４においてスイッチ９から出力される。
【００１６】
上述のように、ルータ内の通過レイテンシは、経路計算、スイッチ調停、スイッチ転送という３つの処理から構成される。ルータの通過レイテンシが大きい場合には半導体の処理能力の向上を妨げる。ＮｏＣでは複数のルータによる中継通信が前提となるため、ルータの通過レイテンシが半導体全体の通信レイテンシの大部分を占める。このため、ルータ内の通過レイテンシを削減することは、非常に重要である。
【００１７】
ルータ内の通過レイテンシを生じさせる処理のうち、経路計算処理及びスイッチ調停処理は、パケットのヘッダを処理対象とする。ヘッダは、パケットの最前方に位置している。ヘッダに後続するパケットのデータは、経路計算処理及びスイッチ調停処理の間は入力バッファにて停止する（格納され続ける）ことになる。これらの２つの処理（経路計算処理、スイッチ調停処理）の一部を省略することができれば、通信レイテンシも削減することができる。
【００１８】
経路計算処理を省略する手法として、パケット送信元において全ての経路計算を予め行うソースルーティングという手法が挙げられる。ソースルーティングは、オフチップネットワークでも使用される手法である。ソースルーティングでは、パケット送信時に既に経路計算が行われている。そのため、各ルータは入力されたパケットの経路を計算する必要はない。ただし、パケットが複数のルータを通過する場合、パケット内には複数の経路情報が格納される。この場合、ルータの構造を簡略化するために、使用した経路情報を破棄し、新しい経路情報を更新する場合が多い。
【００１９】
経路情報の更新は、パケット内の経路情報をシフトすることにより行われる。すでに使用された経路情報は、経路更新回路によるビットシフトによって、次に使用される経路情報により上書きされる。この経路更新により生じる遅延は、経路計算によって生じる遅延よりも小さい。そのため、一般的なルータでの経路計算によって生じる１サイクルのレイテンシを削減することが可能になる。
【００２０】
スイッチ調停のレイテンシを削減する手法として、非特許文献１に記載された予測ルータと呼ばれる手法が挙げられる。この予測ルータとは、入力されるパケットの出力方向をパケット入力前にルータ内にて予め予測し、調停を投機的に完了させておく手法である。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】松谷 宏紀、鯉渕 道紘、天野 英晴、吉永 努著、予測機構を持った低遅延オンチップルータアーキテクチャ、信学技報ｖｏｌ．１０８，ｎｏ．２８
【発明の概要】
【発明が解決しようとする課題】
【００２２】
上述の非特許文献１に記載の予測ルータという手法は、予測した出力方向が間違っていた場合には、スイッチ調停をやり直す必要が生じる。スイッチ調停をやり直した場合、スイッチ調停が全て実行されるためレイテンシの削減がなされない。この予測の失敗は、パケットの出力方向に規則性がない等の要因により発生する。このため、この予測ルータ手法では、レイテンシ削減の効果は、ルータを通過するパケットの通信経路に依存してしまう。よって、ルータを通過するパケットの通信経路次第では、十分にレイテンシの削減をできないという問題がある。
【課題を解決するための手段】
【００２３】
本発明にかかるルータ装置の一態様は、
複数の入力ポートと、第１の出力ポートを有し、前記第１の出力ポートの出力権限を制御する調停処理を行うルータ装置であって、
あるサイクルにおける前記第１の出力ポートへの出力を要求する入力パケットが、前記ルータ装置において前記第１の出力ポートへの出力を要求する唯一のパケットである場合に、当該パケットを前記調停処理の対象とせずに出力する先行出力対象パケットと決定する、ものである。
【００２４】
本発明にかかるルーティング方法の一態様は、
複数の入力ポートと、第１の出力ポートを有し、前記第１の出力ポートの出力権限を制御する調停処理を行うルータ装置の制御方法であって、
あるサイクルにおける前記第１の出力ポートへの出力を要求する入力パケットが、前記第１の出力ポートへの出力を要求する唯一のパケットである場合に、当該パケットを前記調停処理の対象とせずに出力する先行出力対象パケットと決定する、ものである。
【００２５】
本発明においては、ルータ装置は、入力パケットが、前記第１の出力ポートへの出力を要求する唯一のパケットであるか否かを判定している。唯一のパケットである場合、調停処理の対象とすることなく即座に出力することが可能である。このように、本発明にかかるルータ装置は、パケットの入力状況とパケットの保持状況に応じて先行出力対象パケットを検出し、パケットの通信経路を用いて検出処理を行う必要がない。このため、各パケットの通信経路に依存せずに調停処理を省略することが可能となる。
【発明の効果】
【００２６】
本発明によれば、ルータを通過するパケットの通信経路に依存することなく、レイテンシの削減を図ることができるルータ装置、及びルータ制御方法を提供することができる。
【図面の簡単な説明】
【００２７】
【図１】実施の形態１にかかるルータ装置の構成を示すブロック図である。
【図２】実施の形態１にかかるルータ装置によるパケット出力制御を示すフローチャートである。
【図３】実施の形態１にかかるルータ装置による先行出力判定処理を示すフローチャートである。
【図４】実施の形態１にかかるルータ装置の動作を示すタイムチャートである。
【図５】実施の形態２にかかるルータ装置の構成を示すブロック図である。
【図６】実施の形態２にかかるルータ装置の動作を示すタイムチャートである。
【図７】実施の形態３にかかるルータ装置の構成を示すブロック図である。
【図８】実施の形態３にかかるルータ装置によるパケット出力制御を示すフローチャートである。
【図９】実施の形態３にかかるルータ装置による先行出力判定処理を示すフローチャートである。
【図１０】実施の形態３にかかるルータ装置の動作を示すタイムチャートである。
【図１１】実施の形態４にかかるルータ装置の構成を示すブロック図である。
【図１２】標準的な半導体におけるＩＰコアとルータの配置例の図である。
【図１３】標準的なルータ装置の構成を示すブロック図である。
【図１４】標準的なルータ装置の動作を示すタイムチャートである。
【発明を実施するための形態】
【００２８】
＜実施の形態１＞
【００２９】
本発明の実施の形態にかかるルータ装置は、入力パケットが、あるサイクルにおいて、所定の出力ポートへの出力を要求する唯一のパケットであるか否かを判定している。唯一のパケットである場合、ルータ装置は、調停処理の対象とすることなく即座に出力対象とする。このため、本実施の形態にかかるルータ装置は、各パケットの通信経路に依存せずに調停処理を省略することが可能となる。
【００３０】
以下、図面を参照して本発明の実施の形態にかかるルータ装置の詳細について説明する。図１は、本実施の形態にかかるルータ装置の構成を示すブロック図である。ルータ装置１は、３つの入力ポート（入力Ｐ１〜入力Ｐ３）及び３つの出力ポート（出力Ｐ１〜出力Ｐ３）を持つルータ装置である。ルータ装置１は、ラッチ２＿１〜２＿３、経路計算回路３＿１〜３＿３、バッファ４＿１〜４＿３、先行出力検出回路５＿１〜５＿３、調停回路６＿１〜６＿３、出力選択回路７＿１〜７＿３、制御記憶回路８、及びスイッチ９を備える。
【００３１】
ラッチ２＿１は、入力Ｐ１から入力されたパケット（詳細には、パケットのヘッダ及びパケットのデータ）を一時的に保持して経路計算回路３＿１に供給する。ラッチ２＿１が一時的にパケットを保持することにより、ルータ装置１からのパケットの出力タイミングを調節することができる。ラッチ２＿２、ラッチ２＿３は、それぞれ入力Ｐ２、入力Ｐ３と対応するラッチであり、その動作はラッチ２＿１と同様である。
【００３２】
経路計算回路３＿１は、ラッチ２＿１から入力されたパケットから、当該パケットの出力対象のポートを特定する経路である。詳細には、経路計算回路３＿１は、パケットのヘッダを読み込み、読み込んだ情報から出力すべき出力ポートを特定する。経路計算回路３＿１は、経路計算結果である出力ポート番号と、パケットと、をバッファ４＿１に書き込む。さらに経路計算回路３＿１は、入力Ｐ１に対するパケット入力の有無と、パケット入力が有る場合に経路計算結果である出力ポート番号と、先行出力検出回路５＿１に供給する。経路計算回路３＿２、経路計算回路３＿３は、それぞれラッチ２＿２、ラッチ２＿３と対応する経路計算回路であり、その動作は経路計算回路３＿１と同様である。
【００３３】
バッファ４＿１には、出力待ち状態となっているパケットが出力ポート番号と関連付けられて格納される。バッファ４＿１は、ＦＩＦＯ（First In First Out）形式の記憶部である。バッファ４＿１は、後述の調停回路６＿１〜６＿３にパケットの格納状況（パケットの有無であり、パケットが格納されている場合には先頭に位置するパケットの出力ポート番号を含む情報）を通知する。さらに、バッファ４＿１は、後述の制御記憶回路８からの出力命令に応じて、出力対象となるパケットをスイッチ９に供給する。バッファ４＿１に格納されたパケットは、スイッチ９を介してルータ装置１外に出力された際にのみ削除される。バッファ４＿２、バッファ４＿３はそれぞれ入力Ｐ２、入力Ｐ３に対応するバッファであり、その機能はバッファ４＿１と同様である。
【００３４】
なお、本例では、入力ポート毎にバッファを持つ構成として説明するが、必ずしもこれに限られない。例えば、出力先のポート番号と関連付けてパケットを保持する１つのバッファとして構成してもよい。
【００３５】
先行出力検出回路５＿１は、先行出力対象となるパケットが有るか否かを判定する回路である。先行出力対象のパケットとは、パケット調停を実施せずにそのまま出力ポートから出力するパケットである。詳細には、先行出力検出回路５＿１は、各バッファ４＿１〜４＿３が空き状態であるか、及び、あるサイクルに入力ポートのいずれかから入力され、出力Ｐ１への出力を要求するパケットが１つだけか否か、を判定する。条件を満たす場合、先行出力検出回路５＿１は、入力ポートから入力された唯一のパケットを先行出力対象とする。
【００３６】
先行出力検出回路５＿１には、経路計算回路３＿１からサイクル毎に入力Ｐ１に対するパケット入力の有無と、パケット入力が有る場合の経路計算結果である出力ポート番号と、が入力される。同様に先行出力検出回路５＿１には、経路計算回路３＿２からサイクル毎に入力Ｐ２に対するパケット入力の有無と、パケット入力が有る場合の経路計算結果である出力ポート番号と、が入力される。先行出力検出回路５＿１には、経路計算回路３＿３からサイクル毎に入力Ｐ３に対するパケット入力の有無と、パケット入力が有る場合の経路計算結果である出力ポート番号と、が入力される。先行出力検出回路５＿１は、これらの入力を基にサイクル毎に出力Ｐ１に対する先行出力対象のパケットが有るか否か判定する。詳細な判定手法については図３を用いて後述する。
【００３７】
先行出力検出回路５＿１は、サイクル毎に出力Ｐ１に関する先行出力判定の結果を出力選択回路７＿１に供給する。詳細には、先行出力検出回路５＿１は、あるサイクルに出力Ｐ１への出力を要求するパケットが１つであり、バッファ４＿１〜４＿３が全て空である場合に、当該パケット（先行出力対象のパケット）が入力された入力ポートの番号を出力選択回路７＿１に通知する。それ以外の場合、先行出力検出回路５＿１は、先行出力対象とするパケットが無い旨を出力選択回路７＿１に通知する。先行出力検出回路５＿２及び先行出力検出回路５＿３は、それぞれ出力Ｐ２、出力Ｐ３に対応する判定回路であり、その機能は先行出力検出回路５＿１と同様である。先行出力検出回路５＿２による判定結果の出力先は出力選択回路７＿２である。先行出力検出回路５＿３による判定結果の出力先は出力選択回路７＿３である。
【００３８】
調停回路６＿１は、バッファ４＿１〜４＿３が先頭に格納しているパケットの情報から、次のサイクルにおいて出力Ｐ１が出力すべきパケットを選択する回路である。調停回路６＿１は、一般のルータ装置が備える調停回路と同等の機能を持つ。調停回路６＿１は、出力Ｐ１を出力先とするパケットがバッファ４＿１〜４＿３のいずれかの先頭位置に存在する場合に調停を行い、調停により出力権を得たパケットが入力された入力ポート番号を出力選択回路７＿１に通知する。また、調停回路６＿１は、出力Ｐ１を出力先とするパケットがバッファ４＿１〜４＿３のいずれにも存在しない場合に、出力すべきパケットが無いことを出力選択回路７＿１に通知する。調停回路６＿２、調停回路６＿３は、それぞれ出力Ｐ２、出力Ｐ３に対応する調停回路であり、その機能は調停回路６＿１と同様である。
【００３９】
出力選択回路７＿１は、先行出力検出回路５＿１からの入力（先行出力対象のパケットの有無、先行出力対象のパケットが有る場合には当該パケットが入力された入力ポートの番号）と、調停回路６＿１からの入力（次のサイクルにおいて出力Ｐ１から出力すべきパケットが入力された入力ポートの番号、または出力すべきパケットが無いこと）を基に、次のサイクルにおいて出力Ｐ１が出力するパケットを決定する回路である。出力選択回路７＿１の詳細は決定処理については図２を参照して後述する。出力選択回路７＿１は、次のサイクルにおいて出力Ｐ１から出力すべきパケットが入力された入力ポート番号を制御記憶回路８に書き込む。出力選択回路７＿２、出力選択回路７＿３は、それぞれ出力Ｐ２、出力Ｐ３に対応する選択回路であり、その機能は出力選択回路７＿１と同様である。
【００４０】
制御記憶回路８は、出力ポート毎に、次のサイクルにおいて出力すべきパケットが入力された入力ポート番号を記憶する。また、制御記憶回路８は、書き込まれた入力ポート番号と対応するバッファに対して出力許可信号を供給する。さらに、制御記憶部８は、次のサイクルにおいて出力すべきパケットが入力された入力ポート番号を、出力ポート毎にスイッチ９に通知する。
【００４１】
スイッチ９は、通知された情報を基に、各入力ポートに接続されたバッファと、各出力ポートと、の接続を変更する。これにより、各出力選択回路が選択したパケットがルータ装置１から出力される。
【００４２】
続いて、本実施の形態にかかるルータ装置１によるパケット出力制御を図２のフローチャートを用いて説明する。各先行出力検出回路（以下の例では、先行出力検出回路５＿１を例に説明する。）には、各入力ポートと対応する経路計算回路（３＿１〜３＿３）からあるサイクルにおける入力パケットの有無、及び入力パケットが有る場合にはその出力先の出力ポート番号、が入力される（Ｓ１）。さらに、先行出力検出回路５＿１には、バッファ４＿１〜４＿３から各バッファのパケット格納状況が通知される（Ｓ１）。
【００４３】
先行出力検出回路５＿１は、これらの入力を基に先行出力が可能なパケットが有るか否か、すなわち先行出力検出回路５＿１は、調停処理の対象としなくても出力してもよいパケットが有るか否かを判定する（Ｓ２）。当該処理（先行出力判定）の詳細は、図３を参照して後述する。先行出力が可能なパケットがある場合、先行出力検出回路５＿１は、当該対象が有る旨を通知する信号を当該パケットの入力された入力ポート番号とともに出力選択回路７＿１に通知する（Ｓ２）。一方、先行出力が可能なパケットがない場合、先行出力検出回路５＿１は、先行出力が可能なパケットが無い旨を出力選択回路７＿１に通知する（Ｓ２）。
【００４４】
Ｓ１及びＳ２と並行して、詳細にはＳ１及びＳ２を行ったサイクルと同一サイクルにて、各調停回路（以下の例では、調停回路６＿１を例に説明する。）は、バッファ４＿１〜４＿３の先頭に格納されているパケットを読み出し、対応する出力ポートを出力先とするパケットが有るか否かを判定する（Ｓ３）。対象となるパケットが有る場合（Ｓ３：Ｙｅｓ）、調停回路６＿１は、判定対象となるパケットから次のサイクルにて出力するパケットを選択するパケット調停処理を行う（Ｓ４）。一方、対象となるパケットが無い場合（Ｓ３：Ｎｏ）、調停回路６＿１は、パケット調停処理を行わない。調停回路６＿１は、調停処理の実施の有無、調停処理を行った場合には調停結果である入力パケット番号を出力選択回路７＿１に通知する。
【００４５】
続いて、Ｓ５〜Ｓ９の処理を各出力選択回路（以下の説明では、出力選択回路７＿１を例に説明する。）が行う。出力選択回路７＿１には、先行出力検出回路５＿１から先行出力の対象となるパケットの有無、及び当該対象が有る場合には当該パケットの入力ポート番号が入力される。さらに、出力選択回路７＿１には、調停回路６＿１から調停処理の実施の有無、調停処理を行った場合には調停結果である入力パケット番号、が入力される。
【００４６】
出力選択回路７＿１は、はじめに調停回路６＿１において調停処理が行われたか否かを判定する（Ｓ５）。調停処理が行われた場合（Ｓ５：Ｙｅｓ）、出力選択回路７＿１は、調停回路６＿１から入力された入力ポート番号を、出力Ｐ１の出力対象として制御記憶回路８に記憶させる（Ｓ６）。
【００４７】
一方、調停処理が行われなかった場合（Ｓ５：Ｎｏ）、出力選択回路７＿１は、先行出力の対象となるパケットが有るか否かを判定する（Ｓ７）。先行出力の対象となるパケットが有る場合（Ｓ７：Ｙｅｓ）、出力選択回路７＿１は、当該先行出力対象のパケットが入力された入力ポート番号を、出力Ｐ１の出力対象として制御記憶回路８に記憶させる（Ｓ８）。先行出力の対象となるパケットが無い場合（Ｓ７：Ｎｏ）、出力選択回路７＿１は、次サイクルでの出力Ｐ１の出力対象がないことを制御記憶回路８に記憶させる（Ｓ９）。
【００４８】
続いて、先行出力検出回路５＿１による先行出力判定の詳細を図３のフローチャートを参照して説明する。なお、先行出力検出回路５＿２及び先行出力検出回路５＿３についても同様の処理を行う。
【００４９】
先行出力検出回路５＿１は、入力Ｐ１に対応するバッファ４＿１が空であるか否かを判定する（Ｓ１１）。バッファ４＿１が空ではない場合（Ｓ１１：Ｎｏ）、先行出力検出回路５＿１は、先行出力の候補となるパケットを設定しない。一方、バッファ４＿１が空である場合（Ｓ１１：Ｙｅｓ）、先行出力検出回路５＿１は、入力Ｐ１に対するパケット入力状況を確認し、入力データにパケットのヘッダが含まれるか否かを確認する（Ｓ１２）。
【００５０】
入力データにパケットのヘッダが含まれない場合（Ｓ１２：Ｎｏ）、先行出力検出回路５＿１は、先行出力の候補となるパケットを設定しない。入力データにパケットのヘッダが含まれる場合（Ｓ１２：Ｙｅｓ）、先行出力検出回路５＿１は、経路計算回路３＿１にて算出された出力ポート番号が出力Ｐ１のポート番号と等しいか否かを判定する（Ｓ１３）。
【００５１】
ポート番号が合致しない場合（Ｓ１３：Ｎｏ）、先行出力検出回路５＿１は、先行出力の候補となるパケットを設定しない。ポート番号が合致する場合（Ｓ１３：Ｙｅｓ）、先行出力検出回路５＿１は、入力Ｐ１から入力されたパケットを先行出力の候補と判定する（Ｓ１４）。
【００５２】
上述のＳ１１〜Ｓ１４では、先行出力検出回路５＿１は、入力Ｐ１に関する先行出力候補の判定処理を行った。この処理と並行して、先行出力検出回路５＿１は、入力Ｐ２に対応する処理（Ｓ１５〜Ｓ１８）及び入力Ｐ３に対応する処理（Ｓ１９〜Ｓ２２）を行う。
【００５３】
先行出力検出回路５＿１は、全ての入力ポートから選択した先行出力候補のパケットの合計が１つであるかを確認する（Ｓ２３）。先行出力候補のパケットが１つである場合（Ｓ２３：Ｙｅｓ）、先行出力検出回路５＿１は、当該パケットを先行出力対象のパケットに決定する（Ｓ２４）。先行出力候補のパケットが１つではない場合（Ｓ２３：Ｎｏ）、先行出力検出回路５＿１は、先行出力の対象となるパケットが無いと判定する（Ｓ２５）。複数の先行出力候補となるパケットが有る場合、これらのパケットは次のサイクルにおいて調停回路による調停の対象となる。
【００５４】
なお、上述のように先行出力検出回路５＿１は、先行出力対象のパケットの判定においてバッファが空であるか否かを判定している（Ｓ１１、Ｓ１５、Ｓ１９）。バッファが全て空である場合、調停処理は実施されない。そのため、出力選択回路７＿１は、図２に示したＳ６の処理とＳ７の処理を逆の順序にて行ってもよい。すなわち、出力選択回路７＿１は、先行出力対象のパケットが有るか否かを判定した後に、パケット調停結果を参照してもよい。
【００５５】
続いて、図１及び図４を参照して本実施の形態にかかるルータ装置の具体的な動作例について説明する。図４は、サイクルｔにおいて入力Ｐ１から出力Ｐ３へのパケットが入力され、当該パケットが転送される場合のルータ装置１の動作例を示すタイムチャートである。本例では、バッファ４＿１〜４＿３にはパケットが格納されていない。さらに、本例では、サイクルｔにおいて、他の入力ポート（入力Ｐ２、入力Ｐ３）からの入力はない。図４におけるＡ〜Ｈは、図１における各点（Ａ〜Ｈ）における通過信号を示している。
【００５６】
はじめに、サイクルｔにおいて入力Ｐ１からパケットのヘッダがラッチ２＿１に入力される（図４Ａ参照）。このパケットのヘッダは、サイクルｔ＋１においてラッチ２＿１から出力される。出力されたパケットのヘッダは、経路計算回路３＿１により経路計算が行われた後にバッファ４＿１に格納される（図４Ｂ参照）。
【００５７】
このバッファ４＿１への格納と同時に、パケットのヘッダは先行出力検出回路５＿３にも供給される（図４Ｂ参照）。先行出力検出回路５＿３は、このパケットのヘッダを用いて出力Ｐ３の先行出力判定を行う。
【００５８】
先行出力検出回路５＿３は、サイクルｔ＋１において先行出力判定を行う。本例では、バッファ４＿１〜４＿３は全て空であり、サイクルｔにおいて入力Ｐ２、入力Ｐ３からの入力が無いため、先行出力検出回路５＿３は、入力ポート番号（１）を出力する（図４Ｃ参照）。
【００５９】
先行出力検出回路５＿３による先行出力判定と並行して、調停回路６＿３は、バッファ４＿１〜４＿３の先頭位置に格納されているパケットを用いて調停処理を行う。本例では、バッファ４＿１〜４＿３にはパケットが格納されていない。そのため、信号Ｄ等によりバッファ内のパケットが無いこと（"無"）が通知される。よって、調停回路６＿３は、サイクルｔ＋１において、パケット調停を行わなかったことを示す信号を出力選択回路７＿３に出力する。
【００６０】
サイクルｔ＋１において、出力選択回路７＿３には、先行出力検出回路５＿３から"１"が入力され、調停回路６＿３から"無"が入力される。これにより、出力選択回路７＿３は、図２におけるＳ７及びＳ８を実行し、サイクルｔ＋１において先行出力対象の入力ポート番号"１"を制御記憶回路８に入力する（図４Ｆ参照）。
【００６１】
制御記憶回路８は、サイクルｔ＋２において、バッファ４＿１に対してパケットの出力を許可する（図４Ｇ参照）。これにより、バッファ４＿１に格納されているパケットのヘッダ、すなわち先行出力対象となったパケットのヘッダは調停回路による調停の対象となることなく、スイッチに供給される（図４Ｄ参照）。スイッチを通過したパケットはルータ装置１から出力される（図４Ｈ参照）。
【００６２】
続いて、本実施の形態にかかるルータ装置１の効果について改めて説明する。前述のように、先行出力検出回路は、ある出力ポート（第１の出力ポート）を出力先とする入力パケットの入力状態（すなわち１つであるか否か）、及びバッファのパケット格納状態、から調停対象とならない先行出力対象パケットを検出している。先行出力対象パケットは、調停処理の対象となることなく出力される。この先行出力対象パケットの検出は、パケットの入力状態を使用することはない。これにより、パケットの通信経路に依存することなく、調停処理を省略することが可能になり、ルータ装置のレイテンシを削減させることができる。
【００６３】
＜実施の形態２＞
本発明の実施の形態２は、ソースルーティング方式に対応している点を特徴とする。より詳細には、ルータ装置に入力される各パケットには経路情報が予め埋め込まれており、ルータ装置は経路情報を更新する経路更新情報を備えている。これにより、経路計算処理を軽減できるとともに、ルータの構造を簡略化することができる。
【００６４】
図５を参照して本実施の形態にかかるルータ装置１の基本構成を説明する。なお、図５において、同一名及び同一符号を付した処理部、回路は実施の形態１と同様の処理を行う。そのため、重複する説明は適宜省略する。
【００６５】
ルータ装置１は、バッファ４＿１〜４＿３と、先行出力検出回路５＿１〜５＿３と、調停回路６＿１〜６＿３と、出力選択回路７＿１〜７＿３と、制御記憶回路８と、スイッチ９と、経路更新回路１０＿１〜１０＿３と、を備える。ルータ装置１は、ラッチ、経路計算回路は有さない構成である。ラッチは、経路計算回路を有さない構成であることから、入力ポートからバッファまでの遅延制約が緩和されることにより不要となる。これにより、本実施の形態にかかるルータ装置１は、実施の形態１にかかるルータ装置１と比べてルータの通過に要するレイテンシが１サイクル削減できる。
【００６６】
ルータ装置１に入力される各パケットには、既存のソースルーティング手法に沿った経路情報が埋め込まれている。これにより、ルータ装置１内でのパケットの経路計算処理が不要となる。経路更新回路１０＿１〜１０＿３は、それぞれ供給されたパケットから既に通過済みの経路情報を削除する回路である。経路更新回路１０＿１〜１０＿３による経路情報の削除処理は、前述のようにビットシフト等の簡易な処理により実現されるため、経路計算処理に比較して非常に短い時間で終了する。経路更新回路１０＿１〜１０＿３は、それぞれ既存の技術を適用することにより実現可能である。
【００６７】
続いて、本実施の形態にかかるルータ装置１の具体的な動作例を図５に加え、図６のタイムチャートを参照して説明する。図６は、サイクルｔにおいて入力Ｐ１から出力Ｐ３へのパケットが入力され、当該パケットが転送される場合のルータ装置１の動作例を示すタイムチャートである。本例では、バッファ４＿１〜４＿３にはパケットが格納されていない。さらに、本例では、サイクルｔにおいて、他の入力ポート（入力Ｐ２、入力Ｐ３）からの入力はない。図６におけるＡ〜Ｈは、図５における各点（Ａ〜Ｈ）における通過信号を示している。
【００６８】
はじめに、サイクルｔにおいて入力Ｐ１からパケットのヘッダがバッファ４＿１に入力される（図６Ａ参照）。これと同時に、入力されたパケットのヘッダの情報は先行出力検出回路５＿３に供給される。先行出力検出回路５＿３は、サイクルｔにおいて先行出力対象として"１"を出力選択回路７＿３に出力する（図６Ｂ参照）。これと同じタイミングにおいて、調停回路６＿３は、調停対象のパケットがバッファ内に無いことを示す"無"を出力選択回路７＿３に出力する（図６Ｄ参照）。この結果、出力選択回路７＿３は、サイクルｔに入力されたパケットをサイクルｔ＋１における出力パケットと判定し、制御記憶回路８にこのパケットが入力された入力ポート番号"１"を出力する（図６Ｅ参照）。
【００６９】
制御記憶回路８は、サイクルｔ＋１において、バッファ４＿１に対してパケットの出力を許可する（図４Ｆ参照）。これにより、バッファ４＿１に格納されているパケットのヘッダは、経路更新回路１０＿１に供給される（図６Ｃ参照）。経路更新回路１０＿１は入力されたパケットのヘッダの経路情報を更新する。経路更新回路１０＿１は、経路更新後にこのパケットのヘッダをスイッチ９に供給する（図６Ｇ参照）。スイッチを通過したパケットはルータ装置１から出力される（図６Ｈ参照）。
【００７０】
このように、本実施の形態にかかるルータ装置１は、ソースルーティング方式を採用し、経路計算回路、ラッチを持たない構成である。経路更新回路１０＿１〜１０＿３による処理は、経路情報を上書きする処理であり、ルータの動作周波数に与える影響が極めて少ない。このため、実施の形態１にかかるルータ装置１と比べて、本実施の形態にかかるルータ装置１は、ルータ通過に要するレイテンシを削減することができる。
【００７１】
＜実施の形態３＞
本発明の実施の形態３にかかるルータ装置は、通常のパケットに比べて優先的に送信されるべきパケット（以下、優先パケットと記載する。）を適切に扱うことができることを特徴とする。詳細には、本実施の形態にかかるルータ装置では、先行出力判定回路にて入力パケットが優先パケットか否かの判定を行い、出力選択回路は優先パケットを通常のパケットに優先して出力対象と判定する。これにより、すでにバッファ内に格納されている通常のパケットよりも優先して入力ポートから入力されたばかりの優先パケットを出力することができる。以下に、本実施の形態にかかるルータ装置について実施の形態１、２と異なる部分を中心に説明する。
【００７２】
図７は、本実施の形態にかかるルータ装置の構成を示す図である。なお、図７において、同一名及び同一符号を付した処理部、回路は実施の形態１と同様の処理を行う。そのため、重複する説明は適宜省略する。各入力ポートから入力されるバッファは、通常のパケットまたは優先パケットであり、例えばパケットヘッダを参照することによりその区別ができる。
【００７３】
ルータ装置１は、ラッチ２＿１〜２＿３と、経路計算回路３＿１〜３＿３と、バッファ４＿１〜４＿３と、優先バッファ１１＿１〜１１＿３と、優先先行出力検出回路１２＿１〜１２＿３と、バッファ選択回路１３＿１〜１３＿３と、調停回路６＿１〜６＿３と、優先出力選択回路１４＿１〜１４＿３と、制御記憶回路８と、スイッチ９と、を備える。
【００７４】
優先バッファ１１＿１〜１１＿３は、それぞれ入力Ｐ１〜入力Ｐ３に対応する格納部であり、優先パケットをＦＩＦＯ形式により格納する。また、優先バッファ１１＿１〜１１＿３は、サイクル毎に後述の優先先行出力検出回路１２＿１〜１２＿３に対して優先パケットの格納状況を通知する。優先バッファ１１＿１〜１１＿３は、スイッチ９を介してパケットを出力した場合に当該パケットをバッファから削除する。
【００７５】
優先先行出力検出回路１２＿１は、出力Ｐ１に対応し、前述の先行出力検出回路５＿１の処理を一部変更した回路である。優先先行出力検出回路１２＿１は、優先バッファ１１＿１〜１１＿３からパケット格納状況が通知されるとともに、各経路計算回路３＿１〜３＿３から優先パケットの入力の有無、及び優先パケットが有る場合にはその出力ポート番号が供給される。
【００７６】
優先先行出力検出回路１２＿１は、あるサイクルにおいて各入力ポートから出力Ｐ１を出力先とする優先パケットがただ一つ入力されたか否か、及び優先バッファ１１＿１〜１１＿３の先頭にパケットが格納されているか否か、を判定する。すなわち、優先先行出力検出回路１２＿１は、優先パケットを処理対象とする。優先先行出力検出回路１２＿１は、あるサイクルに出力Ｐ１への出力を要求するパケットが１つであり、優先バッファ１１＿１〜１１＿３が全て空である場合に当該パケットが入力された入力ポート番号を優先出力選択回路１４＿１に通知する。それ以外の場合、優先先行出力検出回路１２＿１は、先行出力の対象となるパケットが無い旨を優先出力選択回路１４＿１に通知する。優先先行出力検出回路１２＿１による処理の詳細は、図８を参照して後述する。
【００７７】
優先先行出力検出回路１２＿２、優先先行出力検出回路１２＿３は、それぞれ出力Ｐ２、出力Ｐ３に対応する判定回路であり、その動作は優先先行出力検出回路１２＿１と同様である。
【００７８】
バッファ選択回路１３＿１は、優先バッファ１１＿１及びバッファ４＿１に対応づけられて設けられた回路である。バッファ選択回路１３＿１には、制御記憶回路８から出力許可信号が供給される。バッファ選択回路１３＿１は、優先バッファ１１＿１の先頭からパケットを取り出してスイッチ９に供給する。優先バッファ１１＿１が空である場合、バッファ選択回路１３＿１は、バッファ４＿１からパケットを取り出してスイッチ９に供給する。バッファ選択回路１３＿２は、優先バッファ１１＿２及びバッファ４＿２に対応づけられて設けられた回路であり、その動作はバッファ選択回路１３＿１と同様である。バッファ選択回路１３＿３は、優先バッファ１１＿３及びバッファ４＿３に対応づけられて設けられた回路であり、その動作はバッファ選択回路１３＿１と同様である。
【００７９】
調停回路６＿１は、優先バッファ１１＿１〜１１＿３の先頭に位置するパケット、バッファ４＿１〜４＿３の先頭に位置するパケットを用いてパケット調停を行う。この際、調停回路６＿１は、優先パケットに対して優先的に出力権を与えるように調停を行う。調停回路６＿２及び調停回路６＿３についても同様である。
【００８０】
優先出力選択回路１４＿１は、出力Ｐ１と対応する選択回路であり、前述の出力選択回路７＿１の処理を一部変更した回路である。優先出力選択回路１４＿１は、調停回路６＿１からの入力、及び優先先行出力検出回路１２＿２からの入力、を基に次のサイクルにおいて出力すべきパケットを選択し、当該パケットが入力された入力ポートの番号を制御記憶回路８に通知する。
【００８１】
制御記憶回路８及びスイッチ９の動作は、実施の形態１、２と同等のものである。制御記憶回路８は、優先出力選択回路１４＿１〜１４＿３の入力に対応するバッファ選択回路１３＿１〜１３＿３に対して出力指示信号を供給する。さらに、制御記憶部８は、記憶している次のサイクルにおいて出力すべきパケットが入力された入力ポート番号を、出力ポート毎にスイッチ９に通知する。スイッチ９は、制御記憶回路８からの入力に応じて配線を切り換え、パケットを出力ポートから出力する。
【００８２】
続いて、本実施の形態にかかるルータ装置１によるパケット出力制御を図８のフローチャートを用いて説明する。
【００８３】
各優先先行出力検出回路（以下の例では、優先先行出力検出回路１２＿１を例に説明する。）には、各入力ポートと対応する経路計算回路（３＿１〜３＿３）からあるサイクルにおける優先パケットの入力有無、及び優先パケットがされた場合にはその優先パケットの出力先の出力ポート番号、が入力される（Ｓ１）。さらに、優先先行出力検出回路１２＿１には、優先バッファ１１＿１〜１１＿３から各バッファのパケット格納状況が通知される（Ｓ３１）。
【００８４】
優先先行出力検出回路１２＿１は、これらの入力を基に先行出力が可能な優先パケットが有るか否かを判定する（Ｓ３２）。当該判定処理（Ｓ３２）の詳細は、図９を参照して後述する。
【００８５】
先行出力が可能な優先パケットがある場合、優先先行出力検出回路１２＿１は、当該対象が有る旨を通知する信号を当該優先パケットの入力された入力ポート番号とともに優先出力選択回路１４＿１に通知する（Ｓ３２）。一方、先行出力が可能なパケットがない場合、優先先行出力検出回路１２＿１は、先行出力が可能な優先パケットが無い旨を優先出力選択回路１４＿１に通知する（Ｓ３２）。
【００８６】
Ｓ３１及びＳ３２と並行して、詳細にはＳ３１及びＳ３２を行ったサイクルと同一サイクルにて、各調停回路（以下の例では、調停回路６＿１を例に説明する。）は、バッファ４＿１〜４＿３及び優先バッファ１１＿１〜１１＿３の先頭に格納されているパケットのうち、対応する出力ポートを出力先とするパケットが有るか否か、すなわち調停対象のパケットが有るか否かを判定する（Ｓ３３）。
【００８７】
調停対象となるパケットが有る場合（Ｓ３３：Ｙｅｓ）、調停回路６＿１は、調停対象となるパケットから次のサイクルにて出力するパケットを、優先パケットを優先するようにして選択する調停処理を行う（Ｓ３４）。一方、調停対象となるパケットが無い場合（Ｓ３３：Ｎｏ）、調停回路６＿１は、パケット調停処理を行わない。調停回路６＿１は、調停処理の実施の有無、調停処理を行った場合には調停結果である入力パケット番号を優先出力選択回路１４＿１に通知する。
【００８８】
続くＳ３５〜Ｓ４１の処理を各優先出力選択回路（以下の説明では、優先出力選択回路１４＿１を例に説明する）にて行う。優先出力選択回路１４＿１は、はじめに調停回路６＿１において優先パケットが出力権を獲得したか否かを判定する（Ｓ３５）。優先パケットが出力権を獲得した場合（Ｓ３５：Ｙｅｓ）、優先出力選択回路１４＿１は、出力権を獲得した優先パケットが入力された入力ポート番号を制御記憶回路８に記憶させる（Ｓ３６）。
【００８９】
一方、優先パケットが出力権を獲得しなかった場合（Ｓ３５：Ｎｏ）、優先出力選択回路１４＿１は、優先先行出力検出回路１２＿１にて先行出力対象となった優先パケットが有るか否かを判定する（Ｓ３７）。
【００９０】
優先先行出力の対象となった優先パケットが有る場合（Ｓ３７：Ｙｅｓ）、優先出力選択回路１４＿１は、先行出力対象となった優先パケットが入力された入力ポート番号を制御記憶回路８に記憶させる（Ｓ３８）。
【００９１】
先行出力対象となった優先パケットが無い場合（Ｓ３７：Ｎｏ）、優先出力選択回路１４＿１は、調停回路６＿１において通常のパケットが出力権を獲得したか否かを判定する（Ｓ３９）。
【００９２】
通常のパケットが出力権を獲得した場合（Ｓ３９：Ｙｅｓ）、優先出力選択回路１４＿１は、出力権を獲得した当該通常のパケットが入力された入力ポート番号を制御記憶回路８に記憶させる（Ｓ４０）。
【００９３】
一方、通常のパケットが出力権を獲得しなかった場合（Ｓ３９：Ｎｏ）、優先出力選択回路１４＿１は、出力Ｐ１から次のサイクルにおいて出力すべきパケットが無いことを制御記憶回路８に書き込む（Ｓ４１）。
【００９４】
続いて、優先先行出力判定処理（Ｓ３２）の詳細を、図９のフローチャートを参照して説明する。優先出力選択回路１４＿１は、入力Ｐ１に対応する優先バッファ１１＿１が空になっているか否かを判定する（Ｓ５１）。
【００９５】
優先バッファ１１＿１が空ではない場合（Ｓ５１：Ｎｏ）、優先出力選択回路１４＿１は、先行出力対象を設定しない。一方、優先バッファ１１＿１が空である場合（Ｓ５１：Ｙｅｓ）、優先先行出力検出回路１２＿１は、入力Ｐ１に優先パケットのヘッダが入力されたか否かを判定する（Ｓ５２）。
【００９６】
優先パケットのヘッダが入力されていない場合（Ｓ５２：Ｎｏ）、優先出力選択回路１４＿１は、先行出力対象を設定しない。一方、優先パケットのヘッダが入力されている場合（Ｓ５２：Ｙｅｓ）、優先出力選択回路１４＿１は、経路計算回路３＿１にて算出された出力ポート番号が出力Ｐ１のポート番号と等しいか否かを判定する（Ｓ５３）。
【００９７】
ポート番号が合致しない場合（Ｓ５３：Ｎｏ）、優先出力選択回路１４＿１は、先行出力対象を設定しない。一方、ポート番号が合致する場合（Ｓ５３：Ｙｅｓ）、優先出力選択回路１４＿１は、入力Ｐ１から入力された優先パケットを先行出力の候補と判定する（Ｓ５４）。
【００９８】
上述のＳ５１〜Ｓ５４では、優先出力選択回路１４＿１は、入力Ｐ１に関する先行出力候補の判定処理を行った。この処理と並行して、優先出力選択回路１４＿１は、入力Ｐ２に対応する処理（Ｓ５５〜Ｓ５８）及び入力Ｐ３に対応する処理（Ｓ５９〜Ｓ６２）を行う。
【００９９】
優先出力選択回路１４＿１は、全ての入力ポートから選択した先行出力候補のパケットの合計が１つであるかを確認する（Ｓ６３）。先行出力候補の優先パケットが１つである場合（Ｓ６３：Ｙｅｓ）、優先出力選択回路１４＿１は、当該優先パケットを先行出力対象のパケットに決定する（Ｓ６４）。一方、先行出力候補の優先パケットが１つではない場合（Ｓ６３：Ｎｏ）、優先出力選択回路１４＿１は、先行出力対象となる優先パケットが無いと判定する（Ｓ６５）。複数の先行出力候補となる優先パケットが有る場合、これらの優先パケットは次のサイクルにおいて調停回路による調停の対象となる。
【０１００】
続いて、図７及び図１０を参照して、本実施の形態にかかるルータ装置の具体的な動作例について説明する。図１０は、サイクルｔにおいて入力Ｐ１から出力Ｐ３を出力先とする優先パケットが入力された際の動作例を示すタイムチャートである。本例では、サイクルｔ−１において通常のパケットが入力Ｐ２から入力され、バッファ４＿２に格納されている。さらに、本例では、サイクルｔにおいて、他の入力ポート（入力Ｐ２、入力Ｐ３）からの入力はない。優先バッファ１１＿１〜１１＿３は、空である。図１０におけるＡ〜Ｉは、図７における各点（Ａ〜Ｉ）における通過信号を示している。
【０１０１】
サイクルｔにおいて入力Ｐ１から優先パケットのヘッダがラッチ２＿１に入力される（図１０Ａ参照）。この優先パケットのヘッダは、サイクルｔ＋１においてラッチ２＿１から出力される。出力された優先パケットのヘッダは、経路計算回路３＿１により経路計算が行われた後に優先バッファ１１＿１に格納される（図１０Ｂ参照）。
【０１０２】
この優先バッファ１１＿１への格納と同時に、優先パケットのヘッダは優先先行出力検出回路１２＿３にも供給される。優先先行出力検出回路１２＿３は、各経路計算回路から入力された優先パケットのヘッダ、及び優先バッファ１１＿１〜１１＿３のバッファ格納状況から先行出力対象となる優先パケットが有るかを判定する。優先バッファ１１＿１〜１１＿３が空であるため、優先先行出力検出回路１２＿３は、サイクルｔにおいて入力された優先パケットを先行出力対象と判定し、入力ポート番号"１"をサイクルｔ＋１に優先出力選択回路１４＿３に供給する（図１０Ｃ参照）。
【０１０３】
サイクルｔ＋１において、調停回路６＿３は、調停処理を行う。調停回路６＿３には、各優先バッファ及びバッファからパケット格納状況が通知される。例えば、調停回路６＿３には、サイクルｔにおいて、入力Ｐ１に対応する優先パケット１１＿１に格納されているパケットが無いことが通知される（図１０Ｄ参照）。調停回路６＿３には、サイクルｔにおいて、入力Ｐ２に対応するバッファ４＿２に出力Ｐ３を出力先とするパケットが有ることが通知される（図１０Ｅ参照）。
【０１０４】
調停回路６＿３は、サイクルｔ＋１における調停処理の結果として入力Ｐ２の通常パケット（"２Ｎ"）に出力権を与えたことを優先出力選択回路１４＿３に通知する（図１０Ｆ参照）。
【０１０５】
優先出力選択回路１４＿３は、サイクルｔ＋１において、優先先行出力検出回路１２＿３からの入力（"１"）、及び調停回路６＿３からの入力（"２Ｎ"）を基に、出力対象のパケットをサイクルｔにおいて入力Ｐ１から入力された優先パケットとする。すなわち、優先出力選択回路１４＿３は、サイクルｔ＋１において、"１"を制御記憶回路８に出力する（図１０Ｇ参照）。
【０１０６】
制御記憶回路８は、サイクルｔ＋２において、バッファ選択回路１３＿１に対して出力許可信号を通知する（図１０Ｈ参照）。これにより、優先バッファ１１＿１に格納されているパケットのヘッダ、すなわち先行出力対象となった優先パケットのヘッダは調停回路による調停の対象となることなく、スイッチに供給される。スイッチを通過したパケットのヘッダは、サイクルｔ＋２においてルータ装置１から出力される（図１０Ｉ参照）。
【０１０７】
続いて、本実施の形態にかかるルータ装置の効果について説明する。本実施の形態にかかるルータ装置は、図１０に示したように、既に格納されている通常のパケットよりも優先して優先パケットを出力するように出力パケットを選択する。これにより、調停処理を短縮できるとともに、優先度の高いパケットを優先的に出力することが可能になる。
【０１０８】
＜実施の形態４＞
本実施の形態にかかるルータ装置は、優先パケットに対応し、かつソースルーティング方式に対応するものである。本実施の形態にかかるルータ装置の構成を図１１に示す。なお、図１１において、同一名及び同一符号を付した処理部、回路は実施の形態１、２、３と同様の処理を行う。そのため、重複する説明は適宜省略する。
【０１０９】
ルータ装置１は、バッファ４＿１〜４＿３と、優先バッファ１１＿１〜１１＿３と、優先先行出力検出回路１２＿１〜１２＿３と、バッファ選択回路１３＿１〜１３＿３と、調停回路６＿１〜６＿３と、優先出力選択回路１４＿１〜１４＿３と、経路更新回路１０＿１〜１０＿３と、制御記憶回路８と、スイッチ９と、を備える。各回路、処理部の動作は、前述の実施の形態１〜３と同様であるため、詳細な説明は省略する。
【０１１０】
本実施の形態にかかるルータ装置１は、実施の形態３と同様に優先バッファ１１＿１〜１１＿３を備え、既に格納されている通常のパケットよりも優先パケットを優先的に処理することができる。さらに、本実施の形態にかかるルータ装置１は、実施の形態２と同様に経路更新回路１０＿１〜１０＿３を備える構成であるため、ルータ通過に要するレイテンシを削減することができる。
【０１１１】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば、上述の例では、３つの出力ポートを持つルータ装置について説明したが、これに限られず、１以上の任意数の出力ポートを持つルータ装置に本発明を適応することが可能である。また、ルータ装置を、制御記憶回路を介さずに、出力選択回路または優先出力選択回路の判定結果をスイッチ等に通知するように構成することも可能である。
【符号の説明】
【０１１２】
１ ルータ装置
２＿１〜２＿３ ラッチ
３＿１〜３＿３ 経路計算回路
４＿１〜４＿３ バッファ
５＿１〜５＿３ 先行出力検出回路
６＿１〜６＿３ 調停回路
７＿１〜７＿３ 出力選択回路
８ 制御記憶回路
９ スイッチ
１０＿１〜１０＿３ 経路更新回路
１１＿１〜１１＿３ 優先バッファ
１２＿１〜１２＿３ 優先先行出力検出回路
１３＿１〜１３＿３ バッファ選択回路
１４＿１〜１４＿３ 優先出力選択回路
【技術分野】
【０００１】
本発明はルータ装置及びルータ装置の制御方法に関する。
【背景技術】
【０００２】
現在、単一のチップ上にプロセッサ等の設計モジュールを複数配置することが可能となっている。Ｎｅｗｗｏｒｋ−ｏｎ−Ｃｈｉｐ（以下、ＮｏＣと記載する）は、配置したＩＰコア等の設計モジュールの結合に用いられる回路である。ＮｏＣは、ルータと呼ばれるスイッチング回路を複数備える構成である。
【０００３】
図１２は、半導体におけるＩＰコアとルータの配置例を示す図である。図示するように、複数のＩＰコアがルータを経由して間接的に接続されている。ルータには、隣接するルータまたはＩＰコアからパケット化された入力データが入力される。ルータは、受信したパケットデータの出力方向を決定し、次のルータまたは送信先のＩＰコアにデータを送信する。
【０００４】
ルータの機能は、主に経路計算、スイッチ調停、スイッチ転送の３つである。ルータの標準的な構造を図１３に示す。ルータ装置１は、複数の入力ポート（入力Ｐ１〜入力Ｐ３）及び複数の出力ポート（出力Ｐ１〜出力Ｐ３）を備える。また、ルータ装置１は、ラッチ２＿１〜２＿３、経路計算回路３＿１〜３＿３、バッファ４＿１〜４＿３、調停回路６＿１〜６＿３、制御記憶回路８、及びスイッチ９を備える。ラッチ２＿１〜２＿３、経路計算回路３＿１〜３＿３、及びバッファ４＿１〜４＿３は、入力Ｐ１〜入力Ｐ３にそれぞれ対応づけられている。調停回路６＿１〜６＿３は、出力Ｐ１〜出力Ｐ３に対応づけられている。例えば、ラッチ２＿１、経路計算回路３＿１、及びバッファ４＿１は入力Ｐ１に対応づけられている。調停回路６＿１は、出力Ｐ１に対応づけられている。
【０００５】
ラッチ２＿１〜２＿３は、対応する入力ポートから入力されたパケットを一時的に保持し、その後にパケットを対応する経路計算回路３＿１〜３＿３に出力する。
【０００６】
経路計算回路３＿１〜３＿３は、経路計算を行う回路である。以下、経路計算回路３＿１を例に説明する。経路計算回路３＿１は、入力Ｐ１から入力されたパケットのヘッダに記載された送信先ＩＰコアの情報、または送信方向の情報を基に出力ポート番号を決定する。経路計算回路３＿１は、決定した出力ポート番号とともにパケットを対応するバッファ４＿１に格納する。
【０００７】
バッファ４＿１〜４＿３は、経路計算回路が出力したパケットを出力先の出力ポート番号と対応づけて一時的に格納する。バッファ４＿１〜４＿３は、複数のパケットを保持可能である。バッファ４＿１〜４＿３は、後述の制御記憶回路８からのパケット出力の要求に応じてパケットをスイッチ９に供給する。
【０００８】
調停回路６＿１〜６＿３は、バッファ４＿１〜４＿３に一時的に格納されたパケットのうち、対応する出力ポートが次サイクルに出力するパケットを選択する回路である。以下、調停回路６＿１を例に説明する。調停回路６＿１は、バッファ４＿１〜４＿３に格納されたパケット及び当該パケットの出力パケット番号を基に、対応する出力ポートである出力Ｐ１から次サイクルにおいて出力するパケットを決定する。調停回路６＿１は、決定した出力パケットが入力された入力ポート番号を制御記憶回路８に書き込む。
【０００９】
制御記憶回路８は、あるサイクルにおいて、各出力ポートが出力対象とするパケットを入力した入力ポート番号を記憶する。さらに、制御記憶回路８は、パケット出力要求をバッファ４＿１〜４＿３にそれぞれ伝達する。
【００１０】
スイッチ９は、算出された調停回路６＿１〜６＿３の調停結果（すなわち、各出力ポートが出力すべきパケットが入力された入力ポート番号）が制御記憶回路８を介して入力され、当該調停結果に応じて入力ポートと出力ポートを接続する。詳細には、スイッチ９は、接続対象の入力ポートに対応づけられているバッファからの出力を、出力先となる出力ポートに接続する。
【００１１】
一般に、ルータは経路計算回路による経路計算、調停回路によるスイッチ調停、スイッチによるスイッチ転送にそれぞれ１サイクルのレイテンシを必要とする。この場合、ルータの通過レイテンシは、３サイクルとなる。図１３に示すルータ装置の動作を図１４のタイミングチャートを参照して説明する。
【００１２】
図１４は、図１３のルータ装置において、入力Ｐ１に入力されたパケットを出力Ｐ３から出力する際の動作を示すタイミングチャートである。図１４では、図１３の各点Ａ〜Ｆを通過する信号を示している。ここで、バッファ４＿１〜４＿３には、パケットが格納されていないものとする。
【００１３】
ラッチ２＿１は、サイクルｔにおいて入力されたパケットのヘッダを保持する（図１４Ａ参照）。ラッチ２＿１は、このパケットのヘッダをサイクルｔ＋１において出力する。経路計算回路３＿１は、このパケットヘッダ及び経路計算結果をバッファ４＿１に格納する（図１４Ｂ参照）。調停回路６＿３は、サイクルｔ＋２において、出力パケットの調停を行う。これにより、サイクルｔ＋２において、このパケットヘッダは出力権を得る。すなわち、このパケットヘッダは、バッファ４＿１からの出力対象となる。
【００１４】
調停回路６＿３は、調停結果を制御記憶回路８に書き込む。詳細には、調停回路６＿３は、出力Ｐ３から出力されるパケットの入力ポートが"１"であることをサイクルｔ＋２において書き込む（図１４Ｄ参照）。サイクルｔ＋２において、制御記憶回路８から出力されるバッファ４＿１への指示信号は「停止」である（図１４Ｅ参照）。そのため、サイクルｔ＋２においては、バッファ４＿１は、パケットを出力したものとみなされない。換言すると、バッファ４＿１は、サイクルｔ＋３においてもサイクルｔ＋２と同一の出力を行い続ける（図１４Ｃ参照）。
【００１５】
調停回路６＿３が制御記憶回路８に"１"を入力したことにより、制御記憶回路８は、バッファ４＿１に出力許可（"許可"）の信号を通知する（図１４Ｅ参照）。この許可信号を受けて、バッファ４＿１は、パケットのヘッダの出力が行われたと判断し、バッファ内の更新を行う。この更新により、サイクルｔ＋４では、バッファ４＿１は、サイクルｔ＋１にて入力されたパケットのデータを出力する。このパケットのデータは、サイクルｔ＋４においてスイッチ９から出力される。
【００１６】
上述のように、ルータ内の通過レイテンシは、経路計算、スイッチ調停、スイッチ転送という３つの処理から構成される。ルータの通過レイテンシが大きい場合には半導体の処理能力の向上を妨げる。ＮｏＣでは複数のルータによる中継通信が前提となるため、ルータの通過レイテンシが半導体全体の通信レイテンシの大部分を占める。このため、ルータ内の通過レイテンシを削減することは、非常に重要である。
【００１７】
ルータ内の通過レイテンシを生じさせる処理のうち、経路計算処理及びスイッチ調停処理は、パケットのヘッダを処理対象とする。ヘッダは、パケットの最前方に位置している。ヘッダに後続するパケットのデータは、経路計算処理及びスイッチ調停処理の間は入力バッファにて停止する（格納され続ける）ことになる。これらの２つの処理（経路計算処理、スイッチ調停処理）の一部を省略することができれば、通信レイテンシも削減することができる。
【００１８】
経路計算処理を省略する手法として、パケット送信元において全ての経路計算を予め行うソースルーティングという手法が挙げられる。ソースルーティングは、オフチップネットワークでも使用される手法である。ソースルーティングでは、パケット送信時に既に経路計算が行われている。そのため、各ルータは入力されたパケットの経路を計算する必要はない。ただし、パケットが複数のルータを通過する場合、パケット内には複数の経路情報が格納される。この場合、ルータの構造を簡略化するために、使用した経路情報を破棄し、新しい経路情報を更新する場合が多い。
【００１９】
経路情報の更新は、パケット内の経路情報をシフトすることにより行われる。すでに使用された経路情報は、経路更新回路によるビットシフトによって、次に使用される経路情報により上書きされる。この経路更新により生じる遅延は、経路計算によって生じる遅延よりも小さい。そのため、一般的なルータでの経路計算によって生じる１サイクルのレイテンシを削減することが可能になる。
【００２０】
スイッチ調停のレイテンシを削減する手法として、非特許文献１に記載された予測ルータと呼ばれる手法が挙げられる。この予測ルータとは、入力されるパケットの出力方向をパケット入力前にルータ内にて予め予測し、調停を投機的に完了させておく手法である。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】松谷 宏紀、鯉渕 道紘、天野 英晴、吉永 努著、予測機構を持った低遅延オンチップルータアーキテクチャ、信学技報ｖｏｌ．１０８，ｎｏ．２８
【発明の概要】
【発明が解決しようとする課題】
【００２２】
上述の非特許文献１に記載の予測ルータという手法は、予測した出力方向が間違っていた場合には、スイッチ調停をやり直す必要が生じる。スイッチ調停をやり直した場合、スイッチ調停が全て実行されるためレイテンシの削減がなされない。この予測の失敗は、パケットの出力方向に規則性がない等の要因により発生する。このため、この予測ルータ手法では、レイテンシ削減の効果は、ルータを通過するパケットの通信経路に依存してしまう。よって、ルータを通過するパケットの通信経路次第では、十分にレイテンシの削減をできないという問題がある。
【課題を解決するための手段】
【００２３】
本発明にかかるルータ装置の一態様は、
複数の入力ポートと、第１の出力ポートを有し、前記第１の出力ポートの出力権限を制御する調停処理を行うルータ装置であって、
あるサイクルにおける前記第１の出力ポートへの出力を要求する入力パケットが、前記ルータ装置において前記第１の出力ポートへの出力を要求する唯一のパケットである場合に、当該パケットを前記調停処理の対象とせずに出力する先行出力対象パケットと決定する、ものである。
【００２４】
本発明にかかるルーティング方法の一態様は、
複数の入力ポートと、第１の出力ポートを有し、前記第１の出力ポートの出力権限を制御する調停処理を行うルータ装置の制御方法であって、
あるサイクルにおける前記第１の出力ポートへの出力を要求する入力パケットが、前記第１の出力ポートへの出力を要求する唯一のパケットである場合に、当該パケットを前記調停処理の対象とせずに出力する先行出力対象パケットと決定する、ものである。
【００２５】
本発明においては、ルータ装置は、入力パケットが、前記第１の出力ポートへの出力を要求する唯一のパケットであるか否かを判定している。唯一のパケットである場合、調停処理の対象とすることなく即座に出力することが可能である。このように、本発明にかかるルータ装置は、パケットの入力状況とパケットの保持状況に応じて先行出力対象パケットを検出し、パケットの通信経路を用いて検出処理を行う必要がない。このため、各パケットの通信経路に依存せずに調停処理を省略することが可能となる。
【発明の効果】
【００２６】
本発明によれば、ルータを通過するパケットの通信経路に依存することなく、レイテンシの削減を図ることができるルータ装置、及びルータ制御方法を提供することができる。
【図面の簡単な説明】
【００２７】
【図１】実施の形態１にかかるルータ装置の構成を示すブロック図である。
【図２】実施の形態１にかかるルータ装置によるパケット出力制御を示すフローチャートである。
【図３】実施の形態１にかかるルータ装置による先行出力判定処理を示すフローチャートである。
【図４】実施の形態１にかかるルータ装置の動作を示すタイムチャートである。
【図５】実施の形態２にかかるルータ装置の構成を示すブロック図である。
【図６】実施の形態２にかかるルータ装置の動作を示すタイムチャートである。
【図７】実施の形態３にかかるルータ装置の構成を示すブロック図である。
【図８】実施の形態３にかかるルータ装置によるパケット出力制御を示すフローチャートである。
【図９】実施の形態３にかかるルータ装置による先行出力判定処理を示すフローチャートである。
【図１０】実施の形態３にかかるルータ装置の動作を示すタイムチャートである。
【図１１】実施の形態４にかかるルータ装置の構成を示すブロック図である。
【図１２】標準的な半導体におけるＩＰコアとルータの配置例の図である。
【図１３】標準的なルータ装置の構成を示すブロック図である。
【図１４】標準的なルータ装置の動作を示すタイムチャートである。
【発明を実施するための形態】
【００２８】
＜実施の形態１＞
【００２９】
本発明の実施の形態にかかるルータ装置は、入力パケットが、あるサイクルにおいて、所定の出力ポートへの出力を要求する唯一のパケットであるか否かを判定している。唯一のパケットである場合、ルータ装置は、調停処理の対象とすることなく即座に出力対象とする。このため、本実施の形態にかかるルータ装置は、各パケットの通信経路に依存せずに調停処理を省略することが可能となる。
【００３０】
以下、図面を参照して本発明の実施の形態にかかるルータ装置の詳細について説明する。図１は、本実施の形態にかかるルータ装置の構成を示すブロック図である。ルータ装置１は、３つの入力ポート（入力Ｐ１〜入力Ｐ３）及び３つの出力ポート（出力Ｐ１〜出力Ｐ３）を持つルータ装置である。ルータ装置１は、ラッチ２＿１〜２＿３、経路計算回路３＿１〜３＿３、バッファ４＿１〜４＿３、先行出力検出回路５＿１〜５＿３、調停回路６＿１〜６＿３、出力選択回路７＿１〜７＿３、制御記憶回路８、及びスイッチ９を備える。
【００３１】
ラッチ２＿１は、入力Ｐ１から入力されたパケット（詳細には、パケットのヘッダ及びパケットのデータ）を一時的に保持して経路計算回路３＿１に供給する。ラッチ２＿１が一時的にパケットを保持することにより、ルータ装置１からのパケットの出力タイミングを調節することができる。ラッチ２＿２、ラッチ２＿３は、それぞれ入力Ｐ２、入力Ｐ３と対応するラッチであり、その動作はラッチ２＿１と同様である。
【００３２】
経路計算回路３＿１は、ラッチ２＿１から入力されたパケットから、当該パケットの出力対象のポートを特定する経路である。詳細には、経路計算回路３＿１は、パケットのヘッダを読み込み、読み込んだ情報から出力すべき出力ポートを特定する。経路計算回路３＿１は、経路計算結果である出力ポート番号と、パケットと、をバッファ４＿１に書き込む。さらに経路計算回路３＿１は、入力Ｐ１に対するパケット入力の有無と、パケット入力が有る場合に経路計算結果である出力ポート番号と、先行出力検出回路５＿１に供給する。経路計算回路３＿２、経路計算回路３＿３は、それぞれラッチ２＿２、ラッチ２＿３と対応する経路計算回路であり、その動作は経路計算回路３＿１と同様である。
【００３３】
バッファ４＿１には、出力待ち状態となっているパケットが出力ポート番号と関連付けられて格納される。バッファ４＿１は、ＦＩＦＯ（First In First Out）形式の記憶部である。バッファ４＿１は、後述の調停回路６＿１〜６＿３にパケットの格納状況（パケットの有無であり、パケットが格納されている場合には先頭に位置するパケットの出力ポート番号を含む情報）を通知する。さらに、バッファ４＿１は、後述の制御記憶回路８からの出力命令に応じて、出力対象となるパケットをスイッチ９に供給する。バッファ４＿１に格納されたパケットは、スイッチ９を介してルータ装置１外に出力された際にのみ削除される。バッファ４＿２、バッファ４＿３はそれぞれ入力Ｐ２、入力Ｐ３に対応するバッファであり、その機能はバッファ４＿１と同様である。
【００３４】
なお、本例では、入力ポート毎にバッファを持つ構成として説明するが、必ずしもこれに限られない。例えば、出力先のポート番号と関連付けてパケットを保持する１つのバッファとして構成してもよい。
【００３５】
先行出力検出回路５＿１は、先行出力対象となるパケットが有るか否かを判定する回路である。先行出力対象のパケットとは、パケット調停を実施せずにそのまま出力ポートから出力するパケットである。詳細には、先行出力検出回路５＿１は、各バッファ４＿１〜４＿３が空き状態であるか、及び、あるサイクルに入力ポートのいずれかから入力され、出力Ｐ１への出力を要求するパケットが１つだけか否か、を判定する。条件を満たす場合、先行出力検出回路５＿１は、入力ポートから入力された唯一のパケットを先行出力対象とする。
【００３６】
先行出力検出回路５＿１には、経路計算回路３＿１からサイクル毎に入力Ｐ１に対するパケット入力の有無と、パケット入力が有る場合の経路計算結果である出力ポート番号と、が入力される。同様に先行出力検出回路５＿１には、経路計算回路３＿２からサイクル毎に入力Ｐ２に対するパケット入力の有無と、パケット入力が有る場合の経路計算結果である出力ポート番号と、が入力される。先行出力検出回路５＿１には、経路計算回路３＿３からサイクル毎に入力Ｐ３に対するパケット入力の有無と、パケット入力が有る場合の経路計算結果である出力ポート番号と、が入力される。先行出力検出回路５＿１は、これらの入力を基にサイクル毎に出力Ｐ１に対する先行出力対象のパケットが有るか否か判定する。詳細な判定手法については図３を用いて後述する。
【００３７】
先行出力検出回路５＿１は、サイクル毎に出力Ｐ１に関する先行出力判定の結果を出力選択回路７＿１に供給する。詳細には、先行出力検出回路５＿１は、あるサイクルに出力Ｐ１への出力を要求するパケットが１つであり、バッファ４＿１〜４＿３が全て空である場合に、当該パケット（先行出力対象のパケット）が入力された入力ポートの番号を出力選択回路７＿１に通知する。それ以外の場合、先行出力検出回路５＿１は、先行出力対象とするパケットが無い旨を出力選択回路７＿１に通知する。先行出力検出回路５＿２及び先行出力検出回路５＿３は、それぞれ出力Ｐ２、出力Ｐ３に対応する判定回路であり、その機能は先行出力検出回路５＿１と同様である。先行出力検出回路５＿２による判定結果の出力先は出力選択回路７＿２である。先行出力検出回路５＿３による判定結果の出力先は出力選択回路７＿３である。
【００３８】
調停回路６＿１は、バッファ４＿１〜４＿３が先頭に格納しているパケットの情報から、次のサイクルにおいて出力Ｐ１が出力すべきパケットを選択する回路である。調停回路６＿１は、一般のルータ装置が備える調停回路と同等の機能を持つ。調停回路６＿１は、出力Ｐ１を出力先とするパケットがバッファ４＿１〜４＿３のいずれかの先頭位置に存在する場合に調停を行い、調停により出力権を得たパケットが入力された入力ポート番号を出力選択回路７＿１に通知する。また、調停回路６＿１は、出力Ｐ１を出力先とするパケットがバッファ４＿１〜４＿３のいずれにも存在しない場合に、出力すべきパケットが無いことを出力選択回路７＿１に通知する。調停回路６＿２、調停回路６＿３は、それぞれ出力Ｐ２、出力Ｐ３に対応する調停回路であり、その機能は調停回路６＿１と同様である。
【００３９】
出力選択回路７＿１は、先行出力検出回路５＿１からの入力（先行出力対象のパケットの有無、先行出力対象のパケットが有る場合には当該パケットが入力された入力ポートの番号）と、調停回路６＿１からの入力（次のサイクルにおいて出力Ｐ１から出力すべきパケットが入力された入力ポートの番号、または出力すべきパケットが無いこと）を基に、次のサイクルにおいて出力Ｐ１が出力するパケットを決定する回路である。出力選択回路７＿１の詳細は決定処理については図２を参照して後述する。出力選択回路７＿１は、次のサイクルにおいて出力Ｐ１から出力すべきパケットが入力された入力ポート番号を制御記憶回路８に書き込む。出力選択回路７＿２、出力選択回路７＿３は、それぞれ出力Ｐ２、出力Ｐ３に対応する選択回路であり、その機能は出力選択回路７＿１と同様である。
【００４０】
制御記憶回路８は、出力ポート毎に、次のサイクルにおいて出力すべきパケットが入力された入力ポート番号を記憶する。また、制御記憶回路８は、書き込まれた入力ポート番号と対応するバッファに対して出力許可信号を供給する。さらに、制御記憶部８は、次のサイクルにおいて出力すべきパケットが入力された入力ポート番号を、出力ポート毎にスイッチ９に通知する。
【００４１】
スイッチ９は、通知された情報を基に、各入力ポートに接続されたバッファと、各出力ポートと、の接続を変更する。これにより、各出力選択回路が選択したパケットがルータ装置１から出力される。
【００４２】
続いて、本実施の形態にかかるルータ装置１によるパケット出力制御を図２のフローチャートを用いて説明する。各先行出力検出回路（以下の例では、先行出力検出回路５＿１を例に説明する。）には、各入力ポートと対応する経路計算回路（３＿１〜３＿３）からあるサイクルにおける入力パケットの有無、及び入力パケットが有る場合にはその出力先の出力ポート番号、が入力される（Ｓ１）。さらに、先行出力検出回路５＿１には、バッファ４＿１〜４＿３から各バッファのパケット格納状況が通知される（Ｓ１）。
【００４３】
先行出力検出回路５＿１は、これらの入力を基に先行出力が可能なパケットが有るか否か、すなわち先行出力検出回路５＿１は、調停処理の対象としなくても出力してもよいパケットが有るか否かを判定する（Ｓ２）。当該処理（先行出力判定）の詳細は、図３を参照して後述する。先行出力が可能なパケットがある場合、先行出力検出回路５＿１は、当該対象が有る旨を通知する信号を当該パケットの入力された入力ポート番号とともに出力選択回路７＿１に通知する（Ｓ２）。一方、先行出力が可能なパケットがない場合、先行出力検出回路５＿１は、先行出力が可能なパケットが無い旨を出力選択回路７＿１に通知する（Ｓ２）。
【００４４】
Ｓ１及びＳ２と並行して、詳細にはＳ１及びＳ２を行ったサイクルと同一サイクルにて、各調停回路（以下の例では、調停回路６＿１を例に説明する。）は、バッファ４＿１〜４＿３の先頭に格納されているパケットを読み出し、対応する出力ポートを出力先とするパケットが有るか否かを判定する（Ｓ３）。対象となるパケットが有る場合（Ｓ３：Ｙｅｓ）、調停回路６＿１は、判定対象となるパケットから次のサイクルにて出力するパケットを選択するパケット調停処理を行う（Ｓ４）。一方、対象となるパケットが無い場合（Ｓ３：Ｎｏ）、調停回路６＿１は、パケット調停処理を行わない。調停回路６＿１は、調停処理の実施の有無、調停処理を行った場合には調停結果である入力パケット番号を出力選択回路７＿１に通知する。
【００４５】
続いて、Ｓ５〜Ｓ９の処理を各出力選択回路（以下の説明では、出力選択回路７＿１を例に説明する。）が行う。出力選択回路７＿１には、先行出力検出回路５＿１から先行出力の対象となるパケットの有無、及び当該対象が有る場合には当該パケットの入力ポート番号が入力される。さらに、出力選択回路７＿１には、調停回路６＿１から調停処理の実施の有無、調停処理を行った場合には調停結果である入力パケット番号、が入力される。
【００４６】
出力選択回路７＿１は、はじめに調停回路６＿１において調停処理が行われたか否かを判定する（Ｓ５）。調停処理が行われた場合（Ｓ５：Ｙｅｓ）、出力選択回路７＿１は、調停回路６＿１から入力された入力ポート番号を、出力Ｐ１の出力対象として制御記憶回路８に記憶させる（Ｓ６）。
【００４７】
一方、調停処理が行われなかった場合（Ｓ５：Ｎｏ）、出力選択回路７＿１は、先行出力の対象となるパケットが有るか否かを判定する（Ｓ７）。先行出力の対象となるパケットが有る場合（Ｓ７：Ｙｅｓ）、出力選択回路７＿１は、当該先行出力対象のパケットが入力された入力ポート番号を、出力Ｐ１の出力対象として制御記憶回路８に記憶させる（Ｓ８）。先行出力の対象となるパケットが無い場合（Ｓ７：Ｎｏ）、出力選択回路７＿１は、次サイクルでの出力Ｐ１の出力対象がないことを制御記憶回路８に記憶させる（Ｓ９）。
【００４８】
続いて、先行出力検出回路５＿１による先行出力判定の詳細を図３のフローチャートを参照して説明する。なお、先行出力検出回路５＿２及び先行出力検出回路５＿３についても同様の処理を行う。
【００４９】
先行出力検出回路５＿１は、入力Ｐ１に対応するバッファ４＿１が空であるか否かを判定する（Ｓ１１）。バッファ４＿１が空ではない場合（Ｓ１１：Ｎｏ）、先行出力検出回路５＿１は、先行出力の候補となるパケットを設定しない。一方、バッファ４＿１が空である場合（Ｓ１１：Ｙｅｓ）、先行出力検出回路５＿１は、入力Ｐ１に対するパケット入力状況を確認し、入力データにパケットのヘッダが含まれるか否かを確認する（Ｓ１２）。
【００５０】
入力データにパケットのヘッダが含まれない場合（Ｓ１２：Ｎｏ）、先行出力検出回路５＿１は、先行出力の候補となるパケットを設定しない。入力データにパケットのヘッダが含まれる場合（Ｓ１２：Ｙｅｓ）、先行出力検出回路５＿１は、経路計算回路３＿１にて算出された出力ポート番号が出力Ｐ１のポート番号と等しいか否かを判定する（Ｓ１３）。
【００５１】
ポート番号が合致しない場合（Ｓ１３：Ｎｏ）、先行出力検出回路５＿１は、先行出力の候補となるパケットを設定しない。ポート番号が合致する場合（Ｓ１３：Ｙｅｓ）、先行出力検出回路５＿１は、入力Ｐ１から入力されたパケットを先行出力の候補と判定する（Ｓ１４）。
【００５２】
上述のＳ１１〜Ｓ１４では、先行出力検出回路５＿１は、入力Ｐ１に関する先行出力候補の判定処理を行った。この処理と並行して、先行出力検出回路５＿１は、入力Ｐ２に対応する処理（Ｓ１５〜Ｓ１８）及び入力Ｐ３に対応する処理（Ｓ１９〜Ｓ２２）を行う。
【００５３】
先行出力検出回路５＿１は、全ての入力ポートから選択した先行出力候補のパケットの合計が１つであるかを確認する（Ｓ２３）。先行出力候補のパケットが１つである場合（Ｓ２３：Ｙｅｓ）、先行出力検出回路５＿１は、当該パケットを先行出力対象のパケットに決定する（Ｓ２４）。先行出力候補のパケットが１つではない場合（Ｓ２３：Ｎｏ）、先行出力検出回路５＿１は、先行出力の対象となるパケットが無いと判定する（Ｓ２５）。複数の先行出力候補となるパケットが有る場合、これらのパケットは次のサイクルにおいて調停回路による調停の対象となる。
【００５４】
なお、上述のように先行出力検出回路５＿１は、先行出力対象のパケットの判定においてバッファが空であるか否かを判定している（Ｓ１１、Ｓ１５、Ｓ１９）。バッファが全て空である場合、調停処理は実施されない。そのため、出力選択回路７＿１は、図２に示したＳ６の処理とＳ７の処理を逆の順序にて行ってもよい。すなわち、出力選択回路７＿１は、先行出力対象のパケットが有るか否かを判定した後に、パケット調停結果を参照してもよい。
【００５５】
続いて、図１及び図４を参照して本実施の形態にかかるルータ装置の具体的な動作例について説明する。図４は、サイクルｔにおいて入力Ｐ１から出力Ｐ３へのパケットが入力され、当該パケットが転送される場合のルータ装置１の動作例を示すタイムチャートである。本例では、バッファ４＿１〜４＿３にはパケットが格納されていない。さらに、本例では、サイクルｔにおいて、他の入力ポート（入力Ｐ２、入力Ｐ３）からの入力はない。図４におけるＡ〜Ｈは、図１における各点（Ａ〜Ｈ）における通過信号を示している。
【００５６】
はじめに、サイクルｔにおいて入力Ｐ１からパケットのヘッダがラッチ２＿１に入力される（図４Ａ参照）。このパケットのヘッダは、サイクルｔ＋１においてラッチ２＿１から出力される。出力されたパケットのヘッダは、経路計算回路３＿１により経路計算が行われた後にバッファ４＿１に格納される（図４Ｂ参照）。
【００５７】
このバッファ４＿１への格納と同時に、パケットのヘッダは先行出力検出回路５＿３にも供給される（図４Ｂ参照）。先行出力検出回路５＿３は、このパケットのヘッダを用いて出力Ｐ３の先行出力判定を行う。
【００５８】
先行出力検出回路５＿３は、サイクルｔ＋１において先行出力判定を行う。本例では、バッファ４＿１〜４＿３は全て空であり、サイクルｔにおいて入力Ｐ２、入力Ｐ３からの入力が無いため、先行出力検出回路５＿３は、入力ポート番号（１）を出力する（図４Ｃ参照）。
【００５９】
先行出力検出回路５＿３による先行出力判定と並行して、調停回路６＿３は、バッファ４＿１〜４＿３の先頭位置に格納されているパケットを用いて調停処理を行う。本例では、バッファ４＿１〜４＿３にはパケットが格納されていない。そのため、信号Ｄ等によりバッファ内のパケットが無いこと（"無"）が通知される。よって、調停回路６＿３は、サイクルｔ＋１において、パケット調停を行わなかったことを示す信号を出力選択回路７＿３に出力する。
【００６０】
サイクルｔ＋１において、出力選択回路７＿３には、先行出力検出回路５＿３から"１"が入力され、調停回路６＿３から"無"が入力される。これにより、出力選択回路７＿３は、図２におけるＳ７及びＳ８を実行し、サイクルｔ＋１において先行出力対象の入力ポート番号"１"を制御記憶回路８に入力する（図４Ｆ参照）。
【００６１】
制御記憶回路８は、サイクルｔ＋２において、バッファ４＿１に対してパケットの出力を許可する（図４Ｇ参照）。これにより、バッファ４＿１に格納されているパケットのヘッダ、すなわち先行出力対象となったパケットのヘッダは調停回路による調停の対象となることなく、スイッチに供給される（図４Ｄ参照）。スイッチを通過したパケットはルータ装置１から出力される（図４Ｈ参照）。
【００６２】
続いて、本実施の形態にかかるルータ装置１の効果について改めて説明する。前述のように、先行出力検出回路は、ある出力ポート（第１の出力ポート）を出力先とする入力パケットの入力状態（すなわち１つであるか否か）、及びバッファのパケット格納状態、から調停対象とならない先行出力対象パケットを検出している。先行出力対象パケットは、調停処理の対象となることなく出力される。この先行出力対象パケットの検出は、パケットの入力状態を使用することはない。これにより、パケットの通信経路に依存することなく、調停処理を省略することが可能になり、ルータ装置のレイテンシを削減させることができる。
【００６３】
＜実施の形態２＞
本発明の実施の形態２は、ソースルーティング方式に対応している点を特徴とする。より詳細には、ルータ装置に入力される各パケットには経路情報が予め埋め込まれており、ルータ装置は経路情報を更新する経路更新情報を備えている。これにより、経路計算処理を軽減できるとともに、ルータの構造を簡略化することができる。
【００６４】
図５を参照して本実施の形態にかかるルータ装置１の基本構成を説明する。なお、図５において、同一名及び同一符号を付した処理部、回路は実施の形態１と同様の処理を行う。そのため、重複する説明は適宜省略する。
【００６５】
ルータ装置１は、バッファ４＿１〜４＿３と、先行出力検出回路５＿１〜５＿３と、調停回路６＿１〜６＿３と、出力選択回路７＿１〜７＿３と、制御記憶回路８と、スイッチ９と、経路更新回路１０＿１〜１０＿３と、を備える。ルータ装置１は、ラッチ、経路計算回路は有さない構成である。ラッチは、経路計算回路を有さない構成であることから、入力ポートからバッファまでの遅延制約が緩和されることにより不要となる。これにより、本実施の形態にかかるルータ装置１は、実施の形態１にかかるルータ装置１と比べてルータの通過に要するレイテンシが１サイクル削減できる。
【００６６】
ルータ装置１に入力される各パケットには、既存のソースルーティング手法に沿った経路情報が埋め込まれている。これにより、ルータ装置１内でのパケットの経路計算処理が不要となる。経路更新回路１０＿１〜１０＿３は、それぞれ供給されたパケットから既に通過済みの経路情報を削除する回路である。経路更新回路１０＿１〜１０＿３による経路情報の削除処理は、前述のようにビットシフト等の簡易な処理により実現されるため、経路計算処理に比較して非常に短い時間で終了する。経路更新回路１０＿１〜１０＿３は、それぞれ既存の技術を適用することにより実現可能である。
【００６７】
続いて、本実施の形態にかかるルータ装置１の具体的な動作例を図５に加え、図６のタイムチャートを参照して説明する。図６は、サイクルｔにおいて入力Ｐ１から出力Ｐ３へのパケットが入力され、当該パケットが転送される場合のルータ装置１の動作例を示すタイムチャートである。本例では、バッファ４＿１〜４＿３にはパケットが格納されていない。さらに、本例では、サイクルｔにおいて、他の入力ポート（入力Ｐ２、入力Ｐ３）からの入力はない。図６におけるＡ〜Ｈは、図５における各点（Ａ〜Ｈ）における通過信号を示している。
【００６８】
はじめに、サイクルｔにおいて入力Ｐ１からパケットのヘッダがバッファ４＿１に入力される（図６Ａ参照）。これと同時に、入力されたパケットのヘッダの情報は先行出力検出回路５＿３に供給される。先行出力検出回路５＿３は、サイクルｔにおいて先行出力対象として"１"を出力選択回路７＿３に出力する（図６Ｂ参照）。これと同じタイミングにおいて、調停回路６＿３は、調停対象のパケットがバッファ内に無いことを示す"無"を出力選択回路７＿３に出力する（図６Ｄ参照）。この結果、出力選択回路７＿３は、サイクルｔに入力されたパケットをサイクルｔ＋１における出力パケットと判定し、制御記憶回路８にこのパケットが入力された入力ポート番号"１"を出力する（図６Ｅ参照）。
【００６９】
制御記憶回路８は、サイクルｔ＋１において、バッファ４＿１に対してパケットの出力を許可する（図４Ｆ参照）。これにより、バッファ４＿１に格納されているパケットのヘッダは、経路更新回路１０＿１に供給される（図６Ｃ参照）。経路更新回路１０＿１は入力されたパケットのヘッダの経路情報を更新する。経路更新回路１０＿１は、経路更新後にこのパケットのヘッダをスイッチ９に供給する（図６Ｇ参照）。スイッチを通過したパケットはルータ装置１から出力される（図６Ｈ参照）。
【００７０】
このように、本実施の形態にかかるルータ装置１は、ソースルーティング方式を採用し、経路計算回路、ラッチを持たない構成である。経路更新回路１０＿１〜１０＿３による処理は、経路情報を上書きする処理であり、ルータの動作周波数に与える影響が極めて少ない。このため、実施の形態１にかかるルータ装置１と比べて、本実施の形態にかかるルータ装置１は、ルータ通過に要するレイテンシを削減することができる。
【００７１】
＜実施の形態３＞
本発明の実施の形態３にかかるルータ装置は、通常のパケットに比べて優先的に送信されるべきパケット（以下、優先パケットと記載する。）を適切に扱うことができることを特徴とする。詳細には、本実施の形態にかかるルータ装置では、先行出力判定回路にて入力パケットが優先パケットか否かの判定を行い、出力選択回路は優先パケットを通常のパケットに優先して出力対象と判定する。これにより、すでにバッファ内に格納されている通常のパケットよりも優先して入力ポートから入力されたばかりの優先パケットを出力することができる。以下に、本実施の形態にかかるルータ装置について実施の形態１、２と異なる部分を中心に説明する。
【００７２】
図７は、本実施の形態にかかるルータ装置の構成を示す図である。なお、図７において、同一名及び同一符号を付した処理部、回路は実施の形態１と同様の処理を行う。そのため、重複する説明は適宜省略する。各入力ポートから入力されるバッファは、通常のパケットまたは優先パケットであり、例えばパケットヘッダを参照することによりその区別ができる。
【００７３】
ルータ装置１は、ラッチ２＿１〜２＿３と、経路計算回路３＿１〜３＿３と、バッファ４＿１〜４＿３と、優先バッファ１１＿１〜１１＿３と、優先先行出力検出回路１２＿１〜１２＿３と、バッファ選択回路１３＿１〜１３＿３と、調停回路６＿１〜６＿３と、優先出力選択回路１４＿１〜１４＿３と、制御記憶回路８と、スイッチ９と、を備える。
【００７４】
優先バッファ１１＿１〜１１＿３は、それぞれ入力Ｐ１〜入力Ｐ３に対応する格納部であり、優先パケットをＦＩＦＯ形式により格納する。また、優先バッファ１１＿１〜１１＿３は、サイクル毎に後述の優先先行出力検出回路１２＿１〜１２＿３に対して優先パケットの格納状況を通知する。優先バッファ１１＿１〜１１＿３は、スイッチ９を介してパケットを出力した場合に当該パケットをバッファから削除する。
【００７５】
優先先行出力検出回路１２＿１は、出力Ｐ１に対応し、前述の先行出力検出回路５＿１の処理を一部変更した回路である。優先先行出力検出回路１２＿１は、優先バッファ１１＿１〜１１＿３からパケット格納状況が通知されるとともに、各経路計算回路３＿１〜３＿３から優先パケットの入力の有無、及び優先パケットが有る場合にはその出力ポート番号が供給される。
【００７６】
優先先行出力検出回路１２＿１は、あるサイクルにおいて各入力ポートから出力Ｐ１を出力先とする優先パケットがただ一つ入力されたか否か、及び優先バッファ１１＿１〜１１＿３の先頭にパケットが格納されているか否か、を判定する。すなわち、優先先行出力検出回路１２＿１は、優先パケットを処理対象とする。優先先行出力検出回路１２＿１は、あるサイクルに出力Ｐ１への出力を要求するパケットが１つであり、優先バッファ１１＿１〜１１＿３が全て空である場合に当該パケットが入力された入力ポート番号を優先出力選択回路１４＿１に通知する。それ以外の場合、優先先行出力検出回路１２＿１は、先行出力の対象となるパケットが無い旨を優先出力選択回路１４＿１に通知する。優先先行出力検出回路１２＿１による処理の詳細は、図８を参照して後述する。
【００７７】
優先先行出力検出回路１２＿２、優先先行出力検出回路１２＿３は、それぞれ出力Ｐ２、出力Ｐ３に対応する判定回路であり、その動作は優先先行出力検出回路１２＿１と同様である。
【００７８】
バッファ選択回路１３＿１は、優先バッファ１１＿１及びバッファ４＿１に対応づけられて設けられた回路である。バッファ選択回路１３＿１には、制御記憶回路８から出力許可信号が供給される。バッファ選択回路１３＿１は、優先バッファ１１＿１の先頭からパケットを取り出してスイッチ９に供給する。優先バッファ１１＿１が空である場合、バッファ選択回路１３＿１は、バッファ４＿１からパケットを取り出してスイッチ９に供給する。バッファ選択回路１３＿２は、優先バッファ１１＿２及びバッファ４＿２に対応づけられて設けられた回路であり、その動作はバッファ選択回路１３＿１と同様である。バッファ選択回路１３＿３は、優先バッファ１１＿３及びバッファ４＿３に対応づけられて設けられた回路であり、その動作はバッファ選択回路１３＿１と同様である。
【００７９】
調停回路６＿１は、優先バッファ１１＿１〜１１＿３の先頭に位置するパケット、バッファ４＿１〜４＿３の先頭に位置するパケットを用いてパケット調停を行う。この際、調停回路６＿１は、優先パケットに対して優先的に出力権を与えるように調停を行う。調停回路６＿２及び調停回路６＿３についても同様である。
【００８０】
優先出力選択回路１４＿１は、出力Ｐ１と対応する選択回路であり、前述の出力選択回路７＿１の処理を一部変更した回路である。優先出力選択回路１４＿１は、調停回路６＿１からの入力、及び優先先行出力検出回路１２＿２からの入力、を基に次のサイクルにおいて出力すべきパケットを選択し、当該パケットが入力された入力ポートの番号を制御記憶回路８に通知する。
【００８１】
制御記憶回路８及びスイッチ９の動作は、実施の形態１、２と同等のものである。制御記憶回路８は、優先出力選択回路１４＿１〜１４＿３の入力に対応するバッファ選択回路１３＿１〜１３＿３に対して出力指示信号を供給する。さらに、制御記憶部８は、記憶している次のサイクルにおいて出力すべきパケットが入力された入力ポート番号を、出力ポート毎にスイッチ９に通知する。スイッチ９は、制御記憶回路８からの入力に応じて配線を切り換え、パケットを出力ポートから出力する。
【００８２】
続いて、本実施の形態にかかるルータ装置１によるパケット出力制御を図８のフローチャートを用いて説明する。
【００８３】
各優先先行出力検出回路（以下の例では、優先先行出力検出回路１２＿１を例に説明する。）には、各入力ポートと対応する経路計算回路（３＿１〜３＿３）からあるサイクルにおける優先パケットの入力有無、及び優先パケットがされた場合にはその優先パケットの出力先の出力ポート番号、が入力される（Ｓ１）。さらに、優先先行出力検出回路１２＿１には、優先バッファ１１＿１〜１１＿３から各バッファのパケット格納状況が通知される（Ｓ３１）。
【００８４】
優先先行出力検出回路１２＿１は、これらの入力を基に先行出力が可能な優先パケットが有るか否かを判定する（Ｓ３２）。当該判定処理（Ｓ３２）の詳細は、図９を参照して後述する。
【００８５】
先行出力が可能な優先パケットがある場合、優先先行出力検出回路１２＿１は、当該対象が有る旨を通知する信号を当該優先パケットの入力された入力ポート番号とともに優先出力選択回路１４＿１に通知する（Ｓ３２）。一方、先行出力が可能なパケットがない場合、優先先行出力検出回路１２＿１は、先行出力が可能な優先パケットが無い旨を優先出力選択回路１４＿１に通知する（Ｓ３２）。
【００８６】
Ｓ３１及びＳ３２と並行して、詳細にはＳ３１及びＳ３２を行ったサイクルと同一サイクルにて、各調停回路（以下の例では、調停回路６＿１を例に説明する。）は、バッファ４＿１〜４＿３及び優先バッファ１１＿１〜１１＿３の先頭に格納されているパケットのうち、対応する出力ポートを出力先とするパケットが有るか否か、すなわち調停対象のパケットが有るか否かを判定する（Ｓ３３）。
【００８７】
調停対象となるパケットが有る場合（Ｓ３３：Ｙｅｓ）、調停回路６＿１は、調停対象となるパケットから次のサイクルにて出力するパケットを、優先パケットを優先するようにして選択する調停処理を行う（Ｓ３４）。一方、調停対象となるパケットが無い場合（Ｓ３３：Ｎｏ）、調停回路６＿１は、パケット調停処理を行わない。調停回路６＿１は、調停処理の実施の有無、調停処理を行った場合には調停結果である入力パケット番号を優先出力選択回路１４＿１に通知する。
【００８８】
続くＳ３５〜Ｓ４１の処理を各優先出力選択回路（以下の説明では、優先出力選択回路１４＿１を例に説明する）にて行う。優先出力選択回路１４＿１は、はじめに調停回路６＿１において優先パケットが出力権を獲得したか否かを判定する（Ｓ３５）。優先パケットが出力権を獲得した場合（Ｓ３５：Ｙｅｓ）、優先出力選択回路１４＿１は、出力権を獲得した優先パケットが入力された入力ポート番号を制御記憶回路８に記憶させる（Ｓ３６）。
【００８９】
一方、優先パケットが出力権を獲得しなかった場合（Ｓ３５：Ｎｏ）、優先出力選択回路１４＿１は、優先先行出力検出回路１２＿１にて先行出力対象となった優先パケットが有るか否かを判定する（Ｓ３７）。
【００９０】
優先先行出力の対象となった優先パケットが有る場合（Ｓ３７：Ｙｅｓ）、優先出力選択回路１４＿１は、先行出力対象となった優先パケットが入力された入力ポート番号を制御記憶回路８に記憶させる（Ｓ３８）。
【００９１】
先行出力対象となった優先パケットが無い場合（Ｓ３７：Ｎｏ）、優先出力選択回路１４＿１は、調停回路６＿１において通常のパケットが出力権を獲得したか否かを判定する（Ｓ３９）。
【００９２】
通常のパケットが出力権を獲得した場合（Ｓ３９：Ｙｅｓ）、優先出力選択回路１４＿１は、出力権を獲得した当該通常のパケットが入力された入力ポート番号を制御記憶回路８に記憶させる（Ｓ４０）。
【００９３】
一方、通常のパケットが出力権を獲得しなかった場合（Ｓ３９：Ｎｏ）、優先出力選択回路１４＿１は、出力Ｐ１から次のサイクルにおいて出力すべきパケットが無いことを制御記憶回路８に書き込む（Ｓ４１）。
【００９４】
続いて、優先先行出力判定処理（Ｓ３２）の詳細を、図９のフローチャートを参照して説明する。優先出力選択回路１４＿１は、入力Ｐ１に対応する優先バッファ１１＿１が空になっているか否かを判定する（Ｓ５１）。
【００９５】
優先バッファ１１＿１が空ではない場合（Ｓ５１：Ｎｏ）、優先出力選択回路１４＿１は、先行出力対象を設定しない。一方、優先バッファ１１＿１が空である場合（Ｓ５１：Ｙｅｓ）、優先先行出力検出回路１２＿１は、入力Ｐ１に優先パケットのヘッダが入力されたか否かを判定する（Ｓ５２）。
【００９６】
優先パケットのヘッダが入力されていない場合（Ｓ５２：Ｎｏ）、優先出力選択回路１４＿１は、先行出力対象を設定しない。一方、優先パケットのヘッダが入力されている場合（Ｓ５２：Ｙｅｓ）、優先出力選択回路１４＿１は、経路計算回路３＿１にて算出された出力ポート番号が出力Ｐ１のポート番号と等しいか否かを判定する（Ｓ５３）。
【００９７】
ポート番号が合致しない場合（Ｓ５３：Ｎｏ）、優先出力選択回路１４＿１は、先行出力対象を設定しない。一方、ポート番号が合致する場合（Ｓ５３：Ｙｅｓ）、優先出力選択回路１４＿１は、入力Ｐ１から入力された優先パケットを先行出力の候補と判定する（Ｓ５４）。
【００９８】
上述のＳ５１〜Ｓ５４では、優先出力選択回路１４＿１は、入力Ｐ１に関する先行出力候補の判定処理を行った。この処理と並行して、優先出力選択回路１４＿１は、入力Ｐ２に対応する処理（Ｓ５５〜Ｓ５８）及び入力Ｐ３に対応する処理（Ｓ５９〜Ｓ６２）を行う。
【００９９】
優先出力選択回路１４＿１は、全ての入力ポートから選択した先行出力候補のパケットの合計が１つであるかを確認する（Ｓ６３）。先行出力候補の優先パケットが１つである場合（Ｓ６３：Ｙｅｓ）、優先出力選択回路１４＿１は、当該優先パケットを先行出力対象のパケットに決定する（Ｓ６４）。一方、先行出力候補の優先パケットが１つではない場合（Ｓ６３：Ｎｏ）、優先出力選択回路１４＿１は、先行出力対象となる優先パケットが無いと判定する（Ｓ６５）。複数の先行出力候補となる優先パケットが有る場合、これらの優先パケットは次のサイクルにおいて調停回路による調停の対象となる。
【０１００】
続いて、図７及び図１０を参照して、本実施の形態にかかるルータ装置の具体的な動作例について説明する。図１０は、サイクルｔにおいて入力Ｐ１から出力Ｐ３を出力先とする優先パケットが入力された際の動作例を示すタイムチャートである。本例では、サイクルｔ−１において通常のパケットが入力Ｐ２から入力され、バッファ４＿２に格納されている。さらに、本例では、サイクルｔにおいて、他の入力ポート（入力Ｐ２、入力Ｐ３）からの入力はない。優先バッファ１１＿１〜１１＿３は、空である。図１０におけるＡ〜Ｉは、図７における各点（Ａ〜Ｉ）における通過信号を示している。
【０１０１】
サイクルｔにおいて入力Ｐ１から優先パケットのヘッダがラッチ２＿１に入力される（図１０Ａ参照）。この優先パケットのヘッダは、サイクルｔ＋１においてラッチ２＿１から出力される。出力された優先パケットのヘッダは、経路計算回路３＿１により経路計算が行われた後に優先バッファ１１＿１に格納される（図１０Ｂ参照）。
【０１０２】
この優先バッファ１１＿１への格納と同時に、優先パケットのヘッダは優先先行出力検出回路１２＿３にも供給される。優先先行出力検出回路１２＿３は、各経路計算回路から入力された優先パケットのヘッダ、及び優先バッファ１１＿１〜１１＿３のバッファ格納状況から先行出力対象となる優先パケットが有るかを判定する。優先バッファ１１＿１〜１１＿３が空であるため、優先先行出力検出回路１２＿３は、サイクルｔにおいて入力された優先パケットを先行出力対象と判定し、入力ポート番号"１"をサイクルｔ＋１に優先出力選択回路１４＿３に供給する（図１０Ｃ参照）。
【０１０３】
サイクルｔ＋１において、調停回路６＿３は、調停処理を行う。調停回路６＿３には、各優先バッファ及びバッファからパケット格納状況が通知される。例えば、調停回路６＿３には、サイクルｔにおいて、入力Ｐ１に対応する優先パケット１１＿１に格納されているパケットが無いことが通知される（図１０Ｄ参照）。調停回路６＿３には、サイクルｔにおいて、入力Ｐ２に対応するバッファ４＿２に出力Ｐ３を出力先とするパケットが有ることが通知される（図１０Ｅ参照）。
【０１０４】
調停回路６＿３は、サイクルｔ＋１における調停処理の結果として入力Ｐ２の通常パケット（"２Ｎ"）に出力権を与えたことを優先出力選択回路１４＿３に通知する（図１０Ｆ参照）。
【０１０５】
優先出力選択回路１４＿３は、サイクルｔ＋１において、優先先行出力検出回路１２＿３からの入力（"１"）、及び調停回路６＿３からの入力（"２Ｎ"）を基に、出力対象のパケットをサイクルｔにおいて入力Ｐ１から入力された優先パケットとする。すなわち、優先出力選択回路１４＿３は、サイクルｔ＋１において、"１"を制御記憶回路８に出力する（図１０Ｇ参照）。
【０１０６】
制御記憶回路８は、サイクルｔ＋２において、バッファ選択回路１３＿１に対して出力許可信号を通知する（図１０Ｈ参照）。これにより、優先バッファ１１＿１に格納されているパケットのヘッダ、すなわち先行出力対象となった優先パケットのヘッダは調停回路による調停の対象となることなく、スイッチに供給される。スイッチを通過したパケットのヘッダは、サイクルｔ＋２においてルータ装置１から出力される（図１０Ｉ参照）。
【０１０７】
続いて、本実施の形態にかかるルータ装置の効果について説明する。本実施の形態にかかるルータ装置は、図１０に示したように、既に格納されている通常のパケットよりも優先して優先パケットを出力するように出力パケットを選択する。これにより、調停処理を短縮できるとともに、優先度の高いパケットを優先的に出力することが可能になる。
【０１０８】
＜実施の形態４＞
本実施の形態にかかるルータ装置は、優先パケットに対応し、かつソースルーティング方式に対応するものである。本実施の形態にかかるルータ装置の構成を図１１に示す。なお、図１１において、同一名及び同一符号を付した処理部、回路は実施の形態１、２、３と同様の処理を行う。そのため、重複する説明は適宜省略する。
【０１０９】
ルータ装置１は、バッファ４＿１〜４＿３と、優先バッファ１１＿１〜１１＿３と、優先先行出力検出回路１２＿１〜１２＿３と、バッファ選択回路１３＿１〜１３＿３と、調停回路６＿１〜６＿３と、優先出力選択回路１４＿１〜１４＿３と、経路更新回路１０＿１〜１０＿３と、制御記憶回路８と、スイッチ９と、を備える。各回路、処理部の動作は、前述の実施の形態１〜３と同様であるため、詳細な説明は省略する。
【０１１０】
本実施の形態にかかるルータ装置１は、実施の形態３と同様に優先バッファ１１＿１〜１１＿３を備え、既に格納されている通常のパケットよりも優先パケットを優先的に処理することができる。さらに、本実施の形態にかかるルータ装置１は、実施の形態２と同様に経路更新回路１０＿１〜１０＿３を備える構成であるため、ルータ通過に要するレイテンシを削減することができる。
【０１１１】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば、上述の例では、３つの出力ポートを持つルータ装置について説明したが、これに限られず、１以上の任意数の出力ポートを持つルータ装置に本発明を適応することが可能である。また、ルータ装置を、制御記憶回路を介さずに、出力選択回路または優先出力選択回路の判定結果をスイッチ等に通知するように構成することも可能である。
【符号の説明】
【０１１２】
１ ルータ装置
２＿１〜２＿３ ラッチ
３＿１〜３＿３ 経路計算回路
４＿１〜４＿３ バッファ
５＿１〜５＿３ 先行出力検出回路
６＿１〜６＿３ 調停回路
７＿１〜７＿３ 出力選択回路
８ 制御記憶回路
９ スイッチ
１０＿１〜１０＿３ 経路更新回路
１１＿１〜１１＿３ 優先バッファ
１２＿１〜１２＿３ 優先先行出力検出回路
１３＿１〜１３＿３ バッファ選択回路
１４＿１〜１４＿３ 優先出力選択回路
【特許請求の範囲】
【請求項１】
複数の入力ポートと、第１の出力ポートを有し、前記第１の出力ポートの出力権限を制御する調停処理を行うルータ装置であって、
あるサイクルにおける前記第１の出力ポートへの出力を要求する入力パケットが、前記ルータ装置において前記第１の出力ポートへの出力を要求する唯一のパケットである場合に、当該パケットを前記調停処理の対象とせずに出力する先行出力対象パケットと決定する、ルータ装置。
【請求項２】
出力待ちとなるパケットを一時的に保持する記憶部と、
前記サイクルにおける前記第１の出力ポートへの出力を要求するパケットの入力状態と、前記記憶部の格納状態と、に基づいて前記先行出力対象パケットを検出する先行出力検出回路と、
前記先行出力対象パケットを検出した場合に当該パケットを前記第１の出力ポートから出力するパケットと決定し、前記先行出力対象パケットを検出しなかった場合に前記調停処理に基づいて前記第１の出力ポートから出力するパケットを決定する出力選択回路と、
前記出力選択部の決定に基づいて、前記第１の出力ポートへの配線切替えを制御するスイッチ部と、を備えること、
を特徴とする請求項１に記載のルータ装置。
【請求項３】
前記先行出力検出回路は、前記サイクルにおいて、前記記憶部にて出力待ちとなっているパケットがなく、前記第１の出力ポートを出力先とするパケットの入力が１つである場合に、当該パケットを前記先行出力対象パケットとして検出すること、
を特徴とする請求項２に記載のルータ装置。
【請求項４】
前記先行出力検出回路は、前記サイクルにおいて、前記記憶部に優先的に送信されるべき優先パケットがなく、前記第１の出力ポートを出力先とする前記優先パケットの入力が１つである場合に、当該優先パケットを前記先行出力対象パケットとして検出すること、
を特徴とする請求項２に記載のルータ装置。
【請求項５】
前記調停処理を行う調停回路を備え、
前記調停回路は、前記優先パケットに優先的に前記第１の出力ポートからの出力権限を与えること、
を特徴とする請求項４に記載のルータ装置。
【請求項６】
サイクル単位での前記第１の出力ポートの出力にかかるパケットの情報を記憶し、当該情報を前記スイッチ部に通知する制御記憶回路を備え、
前記出力選択部は、前記第１の出力ポートから出力するパケットの決定情報を前記制御記憶回路に書込むこと、
を特徴とする請求項２乃至請求項５のいずれか１項に記載のルータ装置。
【請求項７】
第２の出力ポートと、
前記複数の入力パケットのいずれかに入力されたパケットのヘッダ情報から出力すべき出力ポートを決定する経路計算回路と、を備えること、
を特徴とする請求項２乃至請求項６のいずれか１項に記載のルータ装置。
【請求項８】
第２の出力ポートを備え、
前記ルータ装置に入力されるパケットに通信経路情報が含まれていること、
を特徴とする請求項２乃至請求項６のいずれか１項に記載のルータ装置。
【請求項９】
前記通信経路情報から既に通過した経路にかかる情報を削除する経路更新回路を備えること、
を特徴とする請求項８に記載のルータ装置。
【請求項１０】
複数の入力ポートと、第１の出力ポートを有し、前記第１の出力ポートの出力権限を制御する調停処理を行うルータ装置の制御方法であって、
あるサイクルにおける前記第１の出力ポートへの出力を要求する入力パケットが、前記ルータ装置において前記第１の出力ポートへの出力を要求する唯一のパケットである場合に、当該パケットを前記調停処理の対象とせずに出力する先行出力対象パケットと決定する、制御方法。
【請求項１】
複数の入力ポートと、第１の出力ポートを有し、前記第１の出力ポートの出力権限を制御する調停処理を行うルータ装置であって、
あるサイクルにおける前記第１の出力ポートへの出力を要求する入力パケットが、前記ルータ装置において前記第１の出力ポートへの出力を要求する唯一のパケットである場合に、当該パケットを前記調停処理の対象とせずに出力する先行出力対象パケットと決定する、ルータ装置。
【請求項２】
出力待ちとなるパケットを一時的に保持する記憶部と、
前記サイクルにおける前記第１の出力ポートへの出力を要求するパケットの入力状態と、前記記憶部の格納状態と、に基づいて前記先行出力対象パケットを検出する先行出力検出回路と、
前記先行出力対象パケットを検出した場合に当該パケットを前記第１の出力ポートから出力するパケットと決定し、前記先行出力対象パケットを検出しなかった場合に前記調停処理に基づいて前記第１の出力ポートから出力するパケットを決定する出力選択回路と、
前記出力選択部の決定に基づいて、前記第１の出力ポートへの配線切替えを制御するスイッチ部と、を備えること、
を特徴とする請求項１に記載のルータ装置。
【請求項３】
前記先行出力検出回路は、前記サイクルにおいて、前記記憶部にて出力待ちとなっているパケットがなく、前記第１の出力ポートを出力先とするパケットの入力が１つである場合に、当該パケットを前記先行出力対象パケットとして検出すること、
を特徴とする請求項２に記載のルータ装置。
【請求項４】
前記先行出力検出回路は、前記サイクルにおいて、前記記憶部に優先的に送信されるべき優先パケットがなく、前記第１の出力ポートを出力先とする前記優先パケットの入力が１つである場合に、当該優先パケットを前記先行出力対象パケットとして検出すること、
を特徴とする請求項２に記載のルータ装置。
【請求項５】
前記調停処理を行う調停回路を備え、
前記調停回路は、前記優先パケットに優先的に前記第１の出力ポートからの出力権限を与えること、
を特徴とする請求項４に記載のルータ装置。
【請求項６】
サイクル単位での前記第１の出力ポートの出力にかかるパケットの情報を記憶し、当該情報を前記スイッチ部に通知する制御記憶回路を備え、
前記出力選択部は、前記第１の出力ポートから出力するパケットの決定情報を前記制御記憶回路に書込むこと、
を特徴とする請求項２乃至請求項５のいずれか１項に記載のルータ装置。
【請求項７】
第２の出力ポートと、
前記複数の入力パケットのいずれかに入力されたパケットのヘッダ情報から出力すべき出力ポートを決定する経路計算回路と、を備えること、
を特徴とする請求項２乃至請求項６のいずれか１項に記載のルータ装置。
【請求項８】
第２の出力ポートを備え、
前記ルータ装置に入力されるパケットに通信経路情報が含まれていること、
を特徴とする請求項２乃至請求項６のいずれか１項に記載のルータ装置。
【請求項９】
前記通信経路情報から既に通過した経路にかかる情報を削除する経路更新回路を備えること、
を特徴とする請求項８に記載のルータ装置。
【請求項１０】
複数の入力ポートと、第１の出力ポートを有し、前記第１の出力ポートの出力権限を制御する調停処理を行うルータ装置の制御方法であって、
あるサイクルにおける前記第１の出力ポートへの出力を要求する入力パケットが、前記ルータ装置において前記第１の出力ポートへの出力を要求する唯一のパケットである場合に、当該パケットを前記調停処理の対象とせずに出力する先行出力対象パケットと決定する、制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１２−１８６５３９（Ｐ２０１２−１８６５３９Ａ）
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願番号】特願２０１１−４６４６３（Ｐ２０１１−４６４６３）
【出願日】平成２３年３月３日（２０１１．３．３）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願日】平成２３年３月３日（２０１１．３．３）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
[ Back to top ]