(57)【要約】【課題】バッファの数にかかわらずにルータの伝送性能を向上させるのは困難であること。【解決手段】ルータは、パケットを入力する複数の入力ポートと、複数の入力ポートから入力されたパケットを記憶する複数の入力バッファと、複数の出力ポートと、複数の出力ポートから出力するパケットを記憶する複数の出力バッファと、調停ユニットとを有する。調停ユニットは、入力バッファ中のパケットの宛先に対応する出力バッファに前回転送した転送済パケットの宛先と入力バッファ中のパケットの宛先とを比較した結果に基づいて、複数の入力バッファから複数の出力バッファへ次に転送するパケットを決定する。【選択図】図２７
2019029738.tif 000002
【特許請求の範囲】
【請求項１】
パケットを入力する複数の入力ポートと、
前記複数の入力ポートから入力された前記パケットを記憶する複数の入力バッファと、
複数の出力ポートと、
前記複数の出力ポートから出力する前記パケットを記憶する複数の出力バッファと、
前記入力バッファ中のパケットの宛先に対応する前記出力バッファに前回転送した転送済パケットの宛先と前記入力バッファ中のパケットの宛先とを比較した結果に基づいて、前記複数の入力バッファから前記複数の出力バッファへ次に転送するパケットを決定する調停ユニットと、
を含む中継装置。
【請求項２】
前記調停ユニットは、前記転送済パケットの宛先を前記出力バッファ毎に記憶する宛先記憶領域を有する、
請求項１に記載の中継装置。
【請求項３】
前記調停ユニットは、次に転送するパケットを１つ決定すると、前記複数の入力バッファをラウンドロビンで順番に１つ選択し、前記選択した入力バッファ中のパケットが次に転送するパケットであるか否かを決定する、
請求項１または２に記載の中継装置。
【請求項４】
前記調停ユニットは、１つの前記入力バッファ中に複数のパケットがある場合、前記入力バッファに記憶された時刻の古いパケットから順番に次に転送するパケットであるか否かを決定する、
請求項１乃至３の何れかに記載の中継装置。
【請求項５】
前記出力ポートは、前記出力バッファに記憶された時刻の古いパケットから順番にパケットを出力する、
請求項１乃至４の何れかに記載の中継装置。
【請求項６】
前記調停ユニットは、前記出力バッファに前回転送した転送済パケットの宛先と一致する１以上のパケットだけが前記複数の入力バッファに存在することを検出すると、前記出力バッファに前回転送した転送済パケットの宛先と一致する１以上のパケットから次に転送するパケットを決定する、
請求項１乃至５の何れかに記載の中継装置。
【請求項７】
請求項１乃至６の何れか１項に記載された中継装置を複数備えるネットワークオンチップ装置。
【請求項８】
複数の入力ポートと複数の出力ポートと複数の入力バッファと複数の出力バッファと調停ユニットとを備える中継装置が実行する中継方法であって、
前記複数の入力ポートが、複数のパケットを入力し、
前記複数の入力バッファが、前記複数の入力ポートから入力された前記パケットを記憶し、
前記調停ユニットが、前記入力バッファに記憶されたパケットの宛先に対応する前記出力バッファに前回転送した転送済パケットの宛先と前記入力バッファに記憶された前記パケットの宛先とを比較した結果に基づいて、前記複数の入力バッファから前記複数の出力バッファへ次に転送するパケットを決定し、
前記複数の出力バッファが前記転送された前記パケットを記憶し、
前記複数の出力ポートが、前記複数の出力バッファに記憶された前記パケットを出力する、
中継方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、中継装置、中継方法、およびネットワークオンチップ装置に関する。
【背景技術】
【０００２】
近年のＬＳＩ設計は、ＣＯＲＥ（計算コア）、メモリ、ルータ（中継装置）などのモジュール間をルータおよび伝送路（チャネル）により接続したネットワークオンチップ技術を採用するようになってきた。
【０００３】
このようなネットワークオンチップ上の各ルータは、ルータに接続されるモジュール毎に入力ポート、出力ポート、入力バッファ、および出力バッファを有する。また、ルータは、入力バッファから出力バッファへパケットを転送する調停装置を有する。ルータは、ルータに接続されるモジュールから入力ポートを通じてパケットが入力されると、入力されたパケットを入力バッファに一旦格納する。また調停装置は、入力バッファにパケットが存在すれば、パケットの調停を行い、入力バッファのパケットをそのパケットの宛先に基づいて決定される出力ポートに対応する出力バッファに転送する。出力ポートは、対応する出力バッファにパケットが存在すれば、出力バッファのパケットを出力ポートにつながる伝送路に送出する。
【０００４】
このようなネットワークオンチップ上のルータにおいては、入力バッファが同一の宛先へ向うパケットによって占有されると、ルータの伝送性能の低下を引き起こすことが知られている。
【０００５】
そこで、上記課題を解決するために、宛先が同一か否かにより、複数の仮想チャネルの各々に格納されているデータ単位の送信先のルータの仮想チャネルの割当順序を決定する宛先比較部と、送信先のルータの仮想チャネルの割当が決定された仮想チャネルから、格納されたデータ単位を出力する出力部とを備えたルータが、本発明に関連する第１の関連技術として提案されている（例えば特許文献１参照）。この第１の関連技術によれば、送信元のルータは、送信先のルータの複数の仮想チャネルにおいて、宛先の異なるパケットが均一に格納されるようにパケットを送信先のルータに送信することができる。このため、送信先のルータは、宛先が同じパケットによって全ての仮想チャネルが占有されてしまう状況を回避することができる。ここで、仮想チャネルの実体はルータのバッファである。即ち、入力ポート毎に複数の仮想チャネルを備えるとは、入力ポート毎に複数のバッファを備え、宛先の異なる複数のパケットを入力ポート毎に平行して送信処理することである。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】再特ＷＯ２０１２／０２９２１５
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、ネットワークオンチップは、ルータがオーバーヘッドとなるため、ルータの面積を小さく実現する必要がある。そのため、ルータの入力ポート毎のバッファの数は少なくなる傾向があり、最低１つの場合もあり得る。本発明に関連する第１の関連技術は、複数の仮想チャネルの各々に格納されているデータ単位の送信先のルータの仮想チャネルの割当順序を決定する宛先比較部を有するため、単一の仮想チャネルしか存在しないルータ、すなわち入力ポート毎のバッファの数が１であるルータには、適用できない。そのため、入力ポート毎のバッファの数にかかわらずにルータの伝送性能を向上させるのは困難である。
【０００８】
本発明の目的は、上述した課題、即ち、バッファの数にかかわらずにルータの伝送性能を向上させるのは困難である、という課題を解決するルータを提供することにある。
【課題を解決するための手段】
【０００９】
本発明の一形態に係る中継装置は、
パケットを入力する複数の入力ポートと、
前記複数の入力ポートから入力された前記パケットを記憶する複数の入力バッファと、
複数の出力ポートと、
前記複数の出力ポートから出力する前記パケットを記憶する複数の出力バッファと、
前記入力バッファ中のパケットの宛先に対応する前記出力バッファに前回転送した転送済パケットの宛先と前記入力バッファ中のパケットの宛先とを比較した結果に基づいて、前記複数の入力バッファから前記複数の出力バッファへ次に転送するパケットを決定する調停ユニットと、
を含む。
【００１０】
本発明の他の形態に係る中継方法は、
複数の入力ポートと複数の出力ポートと複数の入力バッファと複数の出力バッファと調停ユニットとを備える中継装置が実行する中継方法であって、
前記複数の入力ポートが、複数のパケットを入力し、
前記複数の入力バッファが、前記複数の入力ポートから入力された前記パケットを記憶し、
前記調停ユニットが、前記入力バッファに記憶されたパケットの宛先に対応する前記出力バッファに前回転送した転送済パケットの宛先と前記入力バッファに記憶された前記パケットの宛先とを比較した結果に基づいて、前記複数の入力バッファから前記複数の出力バッファへ次に転送するパケットを決定し、
前記複数の出力バッファが前記転送された前記パケットを記憶し、
前記複数の出力ポートが、前記複数の出力バッファに記憶された前記パケットを出力する。
【００１１】
本発明の他の形態に係るネットワークオンチップ装置は、
本発明の形態に係る中継装置を複数備える。
【発明の効果】
【００１２】
本発明は上述した構成を有することにより、バッファの数にかかわらずにルータの伝送性能を向上させることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１の実施形態に係るＬＳＩチップのハードウェア構成の一例を示す図である。
【図２】本発明の第１の実施形態に係るルータのハードウェア構成の一例を示す図である。
【図３】本発明の第１の実施形態に係るルータの調停装置のハードウェア構成の一例を示す図である。
【図４】本発明の第１の実施形態に係るルータの調停装置のコントローラが実行する処理の一例を示すフローチャートである。
【図５】本発明の第１の実施形態に係るＬＳＩチップの構成要素の一部分を示す図である。
【図６】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図７】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図８】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図９】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１０】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１１】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１２】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１３】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１４】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１５】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１６】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１７】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１８】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図１９】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図２０】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図２１】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図２２】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図２３】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図２４】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図２５】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図２６】本発明の第１の実施形態に係るルータの動作例を示す図である。
【図２７】本発明の第２の実施形態に係るルータの構成例を示す図である。
【発明を実施するための形態】
【００１４】
次に本発明の実施の形態について図面を参照して詳細に説明する。
[第１の実施形態]
図１は本発明の第１の実施形態に係るＬＳＩチップ１００のハードウェア構成の一例を示す。図１を参照すると、ＬＳＩチップ１００は、複数のルータ１３０を格子状に並べて複数の伝送路１４０によって接続したメッシュ型トポロジーを有するネットワークオンチップ装置である。また、ＬＳＩチップ１００の各ルータ１３０には、伝送路１５０を通じてＣＯＲＥ（計算コア）１１０が接続されている。さらに、ＬＳＩチップ１００の一部のルータ１３０には、伝送路１６０を通じてメモリ１２０が接続されている。なお、本発明はメッシュ型トポロジーを有するネットワークオンチップ装置にのみ適用されるものではなく、上下左右でルータをリング状に接続したトーラス型トポロジー、伝送路を階層的に接続した階層型トポロジー等を有するネットワークオンチップ装置にも適用できる。
【００１５】
図２はルータ１３０のハードウェア構成の一例を示す。この例のルータ１３０は、ルータ１３０に接続されるモジュール毎に入力ポート１３１、入力ポート１３１から入力されたパケットをバッファリングするための入力バッファ１３２、出力ポート１３３、および出力ポート１３３から出力するパケットをバッファリングするための出力バッファ１３４を有する。
【００１６】
入力ポート１３１から入力されるパケットは、ヘッダとデータとで構成される。ヘッダは、パケットの送信元、およびパケットの宛先を含んでいる。パケットの送信元は、例えばパケットの送信モジュールのアドレスである。パケットの宛先は、例えばパケットの受信モジュールのアドレスである。
【００１７】
また、ルータ１３０は、入力バッファ１３２から出力バッファ１３４へパケットを転送する調停装置１３５を有する。ルータ１３０は、ルータ１３０に接続されるモジュールから入力ポート１３１を通じてパケットが入力されると、入力されたパケットを入力バッファ１３２に格納する。調停装置１３５は、入力バッファ１３２にパケットが存在すれば、パケットの調停を行い、入力バッファ１３２のパケットをそのパケットの宛先に基づいて決定される出力ポートに対応する出力バッファ１３４に転送する。以下、パケットの宛先に基づいて決定される出力ポートに対応する出力バッファを、単に、パケットの宛先に対応する出力バッファと記載する。出力ポート１３３は、出力バッファ１３４にパケットが存在すれば、出力バッファ１３４のパケットを伝送路によって接続されている隣接のモジュールに送信する。
【００１８】
図３は調停装置１３５のハードウェア構成の一例を示す。この例の調停装置１３５は、クロスバスイッチ１３６とコントローラ１３７とから構成されている。クロスバスイッチ１３６は、入力バッファ１３２から出力バッファ１３４へパケットを転送するための経路を提供する。コントローラ１３７は、複数の入力バッファ１３２に記憶されている１以上のパケットから転送対象とするパケットを選択し、その選択したパケットをそのパケットの宛先に対応する出力バッファ１３４へ転送するためにクロスバスイッチ１３６の切り換えを行う。コントローラ１３７は、出力バッファ１３４に前回転送した転送済パケットの宛先を出力バッファ１３４毎に記憶する宛先記憶領域１３８を有する。コントローラ１３７は、入力バッファ１３２中のパケットの宛先に対応して宛先記憶領域１３８に記憶された宛先と入力バッファ１３２中のパケットの宛先とを比較した結果に基づいて、複数の入力バッファ１３２から複数の出力バッファ１３４へ次に転送するパケットを決定する。
【００１９】
図４はコントローラ１３７の処理の一例を示すフローチャートである。コントローラ１３７は、起動されると、図４に示す処理を開始する。まずコントローラ１３７は、初期化処理を行う（ステップＳ１）。コントローラ１３７は、初期化処理では、宛先記憶領域１３８の記憶内容をクリアする。次にコントローラ１３７は、ルータ１３０の複数の入力ポート１３１のうちの予め定められた１つの入力ポート１３１に注目する（ステップＳ２）。次にコントローラ１３７は、注目中の入力ポート１３１に対応する入力バッファ１３２が空か否かを判定する（ステップＳ３）。コントローラ１３７は、注目中の入力ポート１３１に対応する入力バッファ１３２が空であれば、注目中の入力ポート１３１に対する処理を終えてステップＳ１５へ進む。
【００２０】
コントローラ１３７は、注目中の入力ポート１３１に対応する入力バッファ１３２が空でなければ、その入力バッファ１３２に格納されている１以上のパケットのうち最も早くにその入力バッファ１３２に格納されたパケット（即ち最古のパケット）に注目する（ステップＳ４）。次にコントローラ１３７は、注目中のパケットの宛先がルータ１３０に隣接するモジュールか否かを決定する（ステップＳ５）。換言すれば、コントローラ１３７は、注目中のパケットの宛先がルータ１３０に他のルータを介すること無く接続されているメモリあるいはＣＯＲＥであるか否かを決定する（ステップＳ５）。
【００２１】
次にコントローラ１３７は、注目中のパケットの宛先がルータ１３０に隣接するモジュール（メモリあるいはＣＯＲＥ）でなかった場合、注目中のパケットの宛先に対応する出力バッファに関連付けて宛先記憶領域１３８に記憶されている前回転送した転送済パケットの宛先と注目中のパケットの宛先とを比較する（ステップＳ６）。次にコントローラ１３７は、注目中のパケットの宛先に対応する出力バッファに前回転送した転送済パケットの宛先と注目中のパケットの宛先とが一致する場合（ステップＳ７でＹＥＳ）、ステップＳ１１へ進む。またコントローラ１３７は、注目中のパケットの宛先に対応する出力バッファに前回転送した転送済パケットの宛先と注目中のパケットの宛先とが相違する場合（ステップＳ７でＮＯ）、注目中のパケットの宛先に対応する出力バッファ１３４が空か否かを判定する（ステップＳ８）。次にコントローラ１３７は、注目中のパケットの宛先に対応する出力バッファ１３４が空でなければ（ステップＳ８でＮＯ）、ステップＳ１１へ進む。またコントローラ１３７は、注目中のパケットの宛先に対応する出力バッファ１３４が空であれば（ステップＳ８でＹＥＳ）、注目中のパケットを記憶する入力バッファ１３２とその宛先に対応する出力バッファ１３４とを接続するようにクロスバスイッチ１３６を切り換えて、注目中のパケットを入力バッファ１３２から出力バッファ１３４へ転送する（ステップＳ９）。次にコントローラ１３７は、注目中のパケットの宛先を前回転送した転送済パケットの宛先として転送先の出力バッファに対応付けて宛先記憶領域１３８に記憶する（ステップＳ１０）。そして、コントローラ１３７は、ステップＳ１５へ進む。
【００２２】
またコントローラ１３７は、注目中のパケットの宛先がルータ１３０に隣接するモジュール（メモリあるいはＣＯＲＥ）であった場合、注目中のパケットの宛先に対応する出力バッファ１３４が空か否かを判定する（ステップＳ１３）。次にコントローラ１３７は、注目中のパケットの宛先に対応する出力バッファ１３４が空でなければ（ステップＳ８でＮＯ）、ステップＳ１１へ進む。またコントローラ１３７は、注目中のパケットの宛先に対応する出力バッファ１３４が空であれば（ステップＳ１３でＹＥＳ）、注目中のパケットを記憶する入力バッファ１３２とその宛先に対応する出力バッファ１３４とを接続するようにクロスバスイッチ１３６を切り換えて、注目中のパケットを入力バッファ１３２から出力バッファ１３４へ転送する（ステップＳ９）。次にコントローラ１３７は、ステップＳ１５へ進む。
【００２３】
コントローラ１３７は、ステップＳ１１では、注目中の入力ポートに対応する入力バッファ１３２に記憶されている、注目中パケットの次に古いパケットに注目を移す。次にコントローラ１３７は、そのようなパケットが存在していれば（ステップＳ１２でＮＯ）、ステップＳ５に戻って、上述した処理と同様の処理を繰り返す。またコントローラ１３７は、そのようなパケットが存在していなければ（ステップＳ１２でＹＥＳ）、ステップＳ１５へ進む。
【００２４】
コントローラ１３７は、ステップＳ１５では、ラウンドロビン方式に従い、次の１つの入力ポート１３１に注目を移す。次にコントローラ１３７は、ステップＳ３に戻って、上述した処理と同様の処理を繰り返す。
【００２５】
次に、ルータ１３０の動作を簡単な例を挙げて説明する。
【００２６】
図５は、図１に示したＬＳＩチップ１００の構成要素の一部分を示している。今、図５に示すように、ＬＳＩチップ１００上のルータ１３０−１が、隣接するルータ１３０−２、ＣＯＲＥ１１０−１、ルータ１３０−３、ルータ１３０−４のそれぞれから、メモリ１２０−１を宛先とするパケットＰ１１〜Ｐ１４とＣＯＲＥ１１０−２を宛先とするパケットＰ２１〜Ｐ２４とをその順番で入力する状態を想定する。また各ルータ１３０は、宛先の異なる２つのパケットを入力ポート毎に平行して送信処理することができるものとする。また、各ルータ１３０の入力バッファ１３２および出力バッファ１３４のバッファ数は２（最大２パケットまで蓄積可能）とし、最初のパケットの入力時点では何れも空であるものとする。更に、宛先記憶領域１３８はクリアされているものとする。このときルータ１３０−１が、宛先のモジュールが接続するルータ１３０−５にパケットＰ１１〜Ｐ１４、Ｐ２１〜Ｐ２４を転送する動作について、図６〜図１０を参照して説明する。
【００２７】
先ずルータ１３０−１は、図６に示すように、入力ポート１３１−１１を通じてルータ１３０−２からパケットＰ１１、Ｐ２１をその順に入力し、入力バッファ１３２−１１に格納する。また、ルータ１３０−１は、図６に示すように、入力ポート１３１−１２を通じてＣＯＲＥ１１０−１からパケットＰ１２、Ｐ２２をその順に入力し、入力バッファ１３２−１２に格納する。また、ルータ１３０−１は、図６に示すように、入力ポート１３１−１３を通じてルータ１３０−３からパケットＰ１３、Ｐ２３をその順に入力し、入力バッファ１３２−１３に格納する。また、ルータ１３０−１は、図６に示すように、入力ポート１３１−１４を通じてルータ１３０−４からパケットＰ１４、Ｐ２４をその順に入力し、入力バッファ１３２−１４に格納する。
【００２８】
次にルータ１３０−１は、入力ポート１３１−１１に注目する。次にルータ１３０−１は、入力ポート１３１−１１に対応する入力バッファ１３２−１１に格納されている最古のパケットＰ１１に注目する。次にルータ１３０−１は、パケットＰ１１の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットの宛先（クリアされている）とが一致せず、出力バッファ１３４−１１に空きがあるので、入力バッファ１３２−１１と出力バッファ１３４−１１とを接続するようにクロスバスイッチ１３６を切り換えて、図７に示すように、パケットＰ１１を入力バッファ１３２−１１から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ１１は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。次にルータ１３０−１は、パケットＰ１１の宛先（メモリ１２０−１）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００２９】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１２に注目を移す。次にルータ１３０−１は、入力ポート１３１−１２に対応する入力バッファ１３２−１２に格納されている最古のパケットＰ１２に注目する。次にルータ１３０−１は、パケットＰ１２の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ１１の宛先（メモリ１２０−１）とが一致するため、パケットＰ１２の次に古いパケットＰ２２に注目を移す。次にルータ１３０−１は、パケットＰ２２の宛先（ＣＯＲＥ１１０−２）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ１１の宛先（メモリ１２０−１）とが一致せず、出力バッファ１３４−１１に空きがあるので、図７に示すように、パケットＰ２２を入力バッファ１３２−１２から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ２２は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。次にルータ１３０−１は、パケットＰ２２の宛先（ＣＯＲＥ１１０−２）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００３０】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１３に注目を移す。次にルータ１３０−１は、入力ポート１３１−１３に対応する入力バッファ１３２−１３に格納されている最古のパケットＰ１３に注目する。次にルータ１３０−１は、パケットＰ１３の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ２２の宛先（ＣＯＲＥ１１０−２）とが一致せず、出力バッファ１３４−１１に空きがあるので、図８に示すように、パケットＰ１３を入力バッファ１３２−１３から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ１３は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。次にルータ１３０−１は、パケットＰ１３の宛先（メモリ１２０−１）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００３１】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１４に注目を移す。次にルータ１３０−１は、入力ポート１３１−１４に対応する入力バッファ１３２−１１に格納されている最古のパケットＰ１４に注目する。次にルータ１３０−１は、パケットＰ１４の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ１３の宛先（メモリ１２０−１）とが一致するため、パケットＰ１４の次に古いパケットＰ２４に注目を移す。次にルータ１３０−１は、パケットＰ２４の宛先（ＣＯＲＥ１１０−２）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ１３の宛先（メモリ１２０−１）とが一致せず、出力バッファ１３４−１１に空きがあるので、図８に示すように、パケットＰ２４を入力バッファ１３２−１４から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ２４は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。次にルータ１３０−１は、パケットＰ２４の宛先（ＣＯＲＥ１１０−２）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００３２】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１５に注目を移すが、入力ポート１３１−１５に対応する入力バッファ１３２−１５が空なので、ラウンドロビン方式に従い、入力ポート１３１−１１に注目を移す。次にルータ１３０−１は、入力ポート１３１−１１に対応する入力バッファ１３２−１１に格納されている最古のパケットＰ２１に注目する。次にルータ１３０−１は、パケットＰ２１の宛先（ＣＯＲＥ１１０−２）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ２４の宛先（ＣＯＲＥ１１０−２）とが一致し、かつ入力バッファ１３２−１１にパケットＰ２１以外のパケットが存在しないので、ラウンドロビン方式に従い、入力ポート１３１−１２に注目を移す。次にルータ１３０−１は、入力ポート１３１−１２に対応する入力バッファ１３２−１２に格納されている最古のパケットＰ１２に注目する。次にルータ１３０−１は、パケットＰ２１の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ２４の宛先（ＣＯＲＥ１１０−２）が一致せず、出力バッファ１３４−１１に空きがあるので、図９に示すように、パケットＰ１２を入力バッファ１３２−１２から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ１２は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。次にルータ１３０−１は、パケットＰ１２の宛先（メモリ１２０−１）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００３３】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１３に注目を移す。次にルータ１３０−１は、入力ポート１３１−１３に対応する入力バッファ１３２−１３に格納されている最古のパケットＰ２３に注目する。次にルータ１３０−１は、パケットＰ２３の宛先（ＣＯＲＥ１１０−２）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ１２の宛先（メモリ１２０−１）とが一致せず、出力バッファ１３４−１１に空きがあるので、図９に示すように、パケットＰ２３を入力バッファ１３２−１３から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ２３は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。次にルータ１３０−１は、パケットＰ２３の宛先（ＣＯＲＥ１１０−２）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００３４】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１４に注目を移す。次にルータ１３０−１は、入力ポート１３１−１４に対応する入力バッファ１３２−１４に格納されている最古のパケットＰ１４に注目する。次にルータ１３０−１は、パケットＰ１４の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ２３の宛先（ＣＯＲＥ１１０−２）とが一致せず、出力バッファ１３４−１１に空きがあるので、図１０に示すように、パケットＰ１４を入力バッファ１３２−１４から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ１４は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。次にルータ１３０−１は、パケットＰ１４の宛先（メモリ１２０−１）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００３５】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１５に注目を移すが、入力ポート１３１−１５に対応する入力バッファ１３２−１５が空なので、ラウンドロビン方式に従い、入力ポート１３１−１１に注目を移す。次にルータ１３０−１は、入力ポート１３１−１１に対応する入力バッファ１３２−１１に格納されている最古のパケットＰ２１に注目する。次にルータ１３０−１は、パケットＰ２１の宛先（ＣＯＲＥ１１０−２）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ１４の宛先（メモリ１２０−１）とが一致せず、出力バッファ１３４−１１に空きがあるので、図１０に示すように、パケットＰ２１を入力バッファ１３２−１１から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ２１は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。
【００３６】
このようにして、ルータ１３０−１からルータ１３０−５へは、パケットＰ１１、パケットＰ２２、パケットＰ１３、パケットＰ２４、パケットＰ１２、パケットＰ２３、パケットＰ１４、パケットＰ２１の順に送られる。即ち、ルータ１３０−１からルータ１３０−５へは、同じ宛先のパケットは複数連続して送信されない。上記の順番でルータ１３０−５の入力バッファにパケットが格納されると、同じ宛先のパケットで入力バッファが占有されることはなくなる。このため、ルータ１３０−５とルータ１３０−５に接続される何れかのモジュール間で転送待ちが発生した場合でも、ルータ１３０−５の入力バッファには同じ宛先のパケットが連続して格納されないため、転送待ちの発生していないモジュールを宛先とするパケットを転送することができる。その結果、ルータ１３０のバッファリソースを有効に使うことができ、スループット及びレイテンシが向上する。
【００３７】
次に、上述したパケットの順番でルータ１３０−１からルータ１３０−５へパケットが送信された場合のルータ１３０−５の動作を、図１１〜図１８を参照して説明する。なお、最初のパケットの入力時点では何れのバッファも空であるものとする。また、転送待ちは、ルータ１３０−５とメモリ１２０−１間で一時的に発生するものとする。
【００３８】
ルータ１３０−５は、図１１に示すように、入力ポート１３１−５１を通じてルータ１３０−１からパケットＰ１１、Ｐ２２をその順に入力し、入力バッファ１３２−５１に格納する。次にルータ１３０−５は、入力ポート１３１−５１に注目する。次にルータ１３０−５は、入力ポート１３１−５１に対応する入力バッファ１３２−５１に格納されている最古のパケットＰ１１に注目する。次にルータ１３０−５は、パケットＰ１１の宛先（メモリ１２０−１）がルータ１３０−５の隣接モジュールであり、パケットＰ１１の宛先に対応する出力バッファ１３４−５１に空きがあるので、図１２に示すように、パケットＰ１１を入力バッファ１３２−５１から出力バッファ１３４−５１へ転送する。出力バッファ１３４−５１に格納されたパケットＰ１１は、出力ポート１３３−５１により、メモリ１２０−１に向けて送信されようとするが、ルータ１３０−５とメモリ１２０−１間に転送待ちが発生しているため、その送信は保留される。そのため、転送待ちが解消されるまで、出力バッファ１３４−５１にパケットＰ１１が残存する。
【００３９】
次にルータ１３０−５は、ラウンドロビン方式に従い、入力ポート１３１−５２、入力ポート１３１−５３、入力ポート１３１−５４、入力ポート１３１−５５の順に注目を移すが、それらの入力ポート１３１−５２〜１３１−５５に対応する入力バッファ１３２−５２〜１３２−５５が空なので、ラウンドロビン方式に従い、入力ポート１３１−５１に再び注目を移す。次にルータ１３０−５は、入力ポート１３１−５１に対応する入力バッファ１３２−５１に格納されている最古のパケットＰ２２に注目する。次にルータ１３０−５は、注目中のパケットＰ２２の宛先（ＣＯＲＥ１１０−２）がルータ１３０−５の隣接モジュールであり、パケットＰ２２の宛先に対応する出力バッファ１３４−５２に空きがあるので、図１２に示すように、パケットＰ２２を入力バッファ１３２−５１から出力バッファ１３４−５２へ転送する。出力バッファ１３４−５２に格納されたパケットＰ２２は、出力ポート１３３−５２により、ＣＯＲＥ１１０−２へ送信される。
【００４０】
他方、パケットＰ１１、Ｐ２２の転送によってルータ１３０−５の入力バッファ１３２−５１に空きが生じると、図１３に示すように、ルータ１３０−１からルータ１３０−５に向けて送信されたパケットＰ１３、Ｐ２４が入力ポート１３１−５１を通じて入力バッファ１３２−５１に格納される。
【００４１】
次にルータ１３０−５は、入力ポート１３１−５１に再び注目したとき、入力ポート１３１−５１に対応する入力バッファ１３２−５１に格納されている最古のパケットＰ１３に注目する。次にルータ１３０−５は、注目中のパケットＰ１３の宛先（メモリ１２０−１）がルータ１３０−５の隣接モジュールであり、パケットＰ１３の宛先に対応する出力バッファ１３４−５１に空きがあるので、パケットＰ１３を入力バッファ１３２−５１から出力バッファ１３４−５１に転送する。
【００４２】
続いてルータ１３０−５は、入力ポート１３１−５１に再び注目したとき、入力ポート１３１−５１に対応する入力バッファ１３２−５１に格納されている最古のパケットＰ２４に注目する。次にルータ１３０−５は、注目中のパケットＰ２４の宛先（ＣＯＲＥ１１０−２）がルータ１３０−５の隣接モジュールであり、パケットＰ２４の宛先に対応する出力バッファ１３４−５２に空きがあるので、パケットＰ２４を入力バッファ１３２−５１から出力バッファ１３４−５２に転送する。ルータ１３０−５とメモリ１２０−１間の転送待ちが継続している場合、出力バッファ１３４−５１にパケットＰ１１、Ｐ１３がなおも残存する。他方、出力バッファ１３４−５２に格納されたパケットＰ２４は、出力ポート１３３−５２によりＣＯＲＥ１１０−２へ送信される。
【００４３】
パケットＰ１３、Ｐ２４の転送によって図１４に示すようにルータ１３０−５の入力バッファ１３２−５１に空きが生じると、図１５に示すように、ルータ１３０−１からルータ１３０−５に向けて送信されたパケットＰ１２、Ｐ２３が入力ポート１３１−５１を通じて入力バッファ１３２−５１に格納される。ルータ１３０−５は、入力バッファ１３２−５１に格納されたパケットＰ１２の宛先に対応する出力バッファ１３４−５１に空きがないため、パケットＰ１２の転送を保留し、入力バッファ１３２−５１に格納されたパケットＰ２３を処理する。その結果、パケットＰ２３は、図１６に示すように、宛先に対応する出力バッファ１３４−５２に転送され、その後、出力ポート１３３−５２からＣＯＲＥ１１０−２に送信される。そして、図１６に示すようにルータ１３０−５の入力バッファ１３２−５１に空きが生じることによって、図１７に示すように、ルータ１３０−１からルータ１３０−５に向けて送信されたパケットＰ１４が入力ポート１３１−５１を通じて入力バッファ１３２−５１に格納される。
【００４４】
図１７に示すように、入力バッファ１３２−５１がメモリ１２０−１宛てのパケットＰ１２、Ｐ１４で占有され、その宛先に対応する出力バッファ１３４−５１に空きがない状態になると、ルータ１３０−５はルータ１３０−１から後続のパケットを受信することができなくなる。しかし、ルータ１３０−５は、ルータ１３０−１から後続のパケットを受信することができなくなるまで、合計７個のパケットＰ１１、Ｐ２２、Ｐ１３、Ｐ２４、Ｐ１２、Ｐ２３、Ｐ１４をルータＰ１３０−１から受信しており、しかも、そのうちの合計３個のパケットＰ２２、Ｐ２４、Ｐ２３を宛先のＣＯＲＥ１１０−２へ送信している。
【００４５】
次に、本実施形態と比較するために、ルータ１３０−１の調停装置１３５−１が、前回転送したパケットの宛先と異なる宛先を有するパケットか否かを考慮せずに、ラウンドロビン方式で選択した入力ポートに対応する入力バッファから最古のパケットを選択して出力バッファへ転送する調停方式を採った場合の動作を説明する。
【００４６】
ルータ１３０−１が、隣接するルータ１３０−２、ＣＯＲＥ１１０−１、ルータ１３０−３、ルータ１３０−４のそれぞれから、メモリ１２０−１を宛先とするパケットＰ１１〜Ｐ１４とＣＯＲＥ１１０−２を宛先とするパケットＰ２１〜Ｐ２４とをその順番で入力したときのルータ１３０−１の状態は、前述した図６と同じである。図６の状態において、調停装置１３５−１は、最初に注目した入力バッファ１３２−１１から最古のパケットＰ１１を選択して出力バッファ１３４−１１へ転送する。次に調停装置１３５−１は、ラウンドロビン方式に従って次に注目した入力バッファ１３２−１２から最古のパケットＰ１２を選択して出力バッファ１３４−１１へ転送する。以下同様に、調停装置１３５−１は、ラウンドロビン方式に従って順に注目した入力バッファ１３２−１３、１３２−１４から最古のパケットＰ１３、Ｐ１４を選択して出力バッファ１３４−１１へ転送する。同様に調停装置１３５−１は、残りのパケットＰ２１、Ｐ２２、Ｐ２３、Ｐ２４をその順に出力バッファ１３４−１１へ転送する。その結果、ルータ１３０−１からルータ１３０−５へは、パケットＰ１１、Ｐ１２、Ｐ１３、Ｐ１４、Ｐ２１、Ｐ２２、Ｐ２３、Ｐ２４の順に送信される。即ち、ルータ１３０−１からルータ１３０−５へ、同じメモリ１２０−１を宛先とする４個のパケットＰ１１〜Ｐ１４が連続して送信され、その後、同じＣＯＲＥ１１０−２を宛先とする４個のパケットＰ２１〜Ｐ２４が連続して送信される。
【００４７】
その結果、ルータ１３０−５は、ルータ１３０−５とメモリ１２０−１との間に転送待ちが発生している場合、先頭の４個のパケットＰ１１〜Ｐ１４を受信した状態で、図１８に示すように、出力バッファ１３４−５１にパケットＰ１１、Ｐ１２が格納され、入力バッファ１３２−５１にパケットＰ１３、Ｐ１４が格納された状態になり、その時点でルータ１３０−５はルータ１３０−１から後続のパケットを受信することができなくなる。このような状態にいたるまで、ルータ１３０−５は、高々４個のパケットＰ１１〜Ｐ１４をルータＰ１３０−１から受信しただけであり、しかもＣＯＲＥ１１０−２へは１つもパケットを送信できていない。
【００４８】
図６乃至図１８では、ルータ１３０の入力バッファおよび出力バッファのバッファ数を２とした。続いて、ルータ１３０の入力バッファおよび出力バッファのバッファ数が１（最大１パケットを蓄積可能）である場合の動作について、図１９〜図２６を参照して説明する。バッファ数以外の条件は上述した例と同じである。
【００４９】
先ずルータ１３０−１は、図１９に示すように、入力ポート１３１−１１を通じてルータ１３０−２からパケットＰ１１を入力し、入力バッファ１３２−１１に格納する。また、ルータ１３０−１は、入力ポート１３１−１２を通じてＣＯＲＥ１１０−１からパケットＰ１２を入力し、図１９に示すように、入力バッファ１３２−１２に格納する。また、ルータ１３０−１は、入力ポート１３１−１３を通じてルータ１３０−３からパケットＰ１３を入力し、図１９に示すように、入力バッファ１３２−１３に格納する。また、ルータ１３０−１は、入力ポート１３１−１４を通じてルータ１３０−４からパケットＰ１４を入力し、図１９に示すように、入力バッファ１３２−１４に格納する。
【００５０】
次にルータ１３０−１は、入力ポート１３１−１１に注目する。次にルータ１３０−１は、入力ポート１３１−１１に対応する入力バッファ１３２−１１に格納されている最古のパケットＰ１１に注目する。次にルータ１３０−１は、パケットＰ１１の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットの宛先（クリアされている）とが一致せず、宛先に対応する出力バッファ１３４−１１に空きがあるので、図２０に示すように、パケットＰ１１を入力バッファ１３２−１１から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ１１は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。パケットＰ１１の転送によってルータ１３０−１の入力バッファ１３２−１１に空きが生じると、図２０に示すように、ルータ１３０−２から送信されたパケットＰ２１が入力ポート１３１−１１を通じて入力バッファ１３２−１１に格納される。次にルータ１３０−１は、パケットＰ１１の宛先（メモリ１２０−１）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００５１】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１２に注目を移す。次にルータ１３０−１は、入力ポート１３１−１２に対応する入力バッファ１３２−１２に格納されている最古のパケットＰ１２に注目する。次にルータ１３０−１は、パケットＰ１２の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ１１の宛先（メモリ１２０−１）とが一致し、入力バッファ１３２−１２にはパケットＰ１２以外のパケットが存在しないため、ラウンドロビン方式に従い、入力ポート１３１−１３に注目を移す。以後、ルータ１３０−１は、パケットの転送を行うことなく入力ポート１３１−１４、入力ポート１３１−１５へと注目を移し、再び入力ポート１３１−１１に注目する。
【００５２】
次にルータ１３０−１は、入力ポート１３１−１１に対応する入力バッファ１３２−１１に格納されている最古のパケットＰ２１に注目する。次にルータ１３０−１は、パケットＰ２１の宛先（ＣＯＲＥ１１０−２）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ１１の宛先（メモリ１２０−１）とが一致せず、出力バッファ１３４−１１に空きがあるので、図２１に示すように、パケットＰ２１を入力バッファ１３２−１１から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ２１は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。次にルータ１３０−１は、パケットＰ２１の宛先（ＣＯＲＥ１１０−２）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００５３】
次にルータ１３０−１は、ラウンドロビン方式に従い、入力ポート１３１−１２に注目を移す。次にルータ１３０−１は、入力ポート１３１−１２に対応する入力バッファ１３２−１２に格納されている最古のパケットＰ１２に注目する。次にルータ１３０−１は、パケットＰ１２の宛先（メモリ１２０−１）とその宛先に対応する出力バッファ１３４−１１に前回転送したパケットＰ２１の宛先（ＣＯＲＥ１１０−２）とが一致せず、出力バッファ１３４−１１に空きがあるので、図２２に示すように、パケットＰ１２を入力バッファ１３２−１２から出力バッファ１３４−１１へ転送する。出力バッファ１３４−１１に格納されたパケットＰ１２は、出力ポート１３３−１１により、ルータ１３０−５へ送信される。パケットＰ１２の転送によってルータ１３０−１の入力バッファ１３２−１２に空きが生じると、図２２に示すように、ＣＯＲＥ１１０−１から送信されたパケットＰ２２が入力ポート１３１−１２を通じて入力バッファ１３２−１２に格納される。次にルータ１３０−１は、パケットＰ１２の宛先（メモリ１２０−１）を出力バッファ１３４−１１に対応付けて宛先記憶領域１３８に記憶する。
【００５４】
以降、上述した処理と同様の処理がルータ１３０−１で繰り返されることにより、最終的に、ルータ１３０−１からルータ１３０−５へは、パケットＰ１１、パケットＰ２１、パケットＰ１２、パケットＰ２２、パケットＰ１３、パケットＰ２３、パケットＰ１４、パケットＰ２４の順にパケットが送られる。即ち、ルータ１３０−１からルータ１３０−５へは、同じ宛先のパケットは複数連続して送信されない。このため、ルータ１３０−５とルータ１３０−５に接続される何れかのモジュール間で転送待ちが発生した場合でも、ルータ１３０−５の入力バッファには同じ宛先のパケットが連続して格納されないため、転送待ちの発生していないモジュールを宛先とするパケットを転送することができる。その結果、ルータ１３０のバッファリソースを有効に使うことができ、スループット及びレイテンシが向上する。
【００５５】
次に、上述したパケットの順番でルータ１３０−１からルータ１３０−５へパケットが送信された場合のルータ１３０−５の動作を、図２３〜図２６を参照して説明する。なお、最初のパケットＰ１１の入力時点では何れのバッファも空であるものとする。また、転送待ちは、ルータ１３０−５とメモリ１２０−１間で一時的に発生するものとする。
【００５６】
ルータ１３０−５は、図２３に示すように、入力ポート１３１−５１を通じてルータ１３０−１からパケットＰ１１を入力し、入力バッファ１３２−５１にパケットＰ１１を格納する。次にルータ１３０−５は、入力ポート１３１−５１に注目する。次にルータ１３０−５は、入力ポート１３１−５１に対応する入力バッファ１３２−５１に格納されている最古のパケットＰ１１に注目する。次にルータ１３０−５は、パケットＰ１１の宛先（メモリ１２０−１）がルータ１３０−５の隣接モジュールであり、宛先に対応する出力バッファ１３４−５１に空きがあるので、図２４に示すように、パケットＰ１１を入力バッファ１３２−５１から出力バッファ１３４−５１へ転送する。出力バッファ１３４−５１に格納されたパケットＰ１１は、出力ポート１３３−５１により、メモリ１２０−１に向けて送信されようとするが、ルータ１３０−５とメモリ１２０−１間に転送待ちが発生しているため、その送信は保留される。そのため、転送待ちが解消されるまで、出力バッファ１３４−５１にパケットＰ１１が残存する。パケットＰ１１の転送によってルータ１３０−５の入力バッファ１３２−５１に空きが生じると、図２４に示すように、ルータ１３０−１から送信されたパケットＰ２１が入力ポート１３１−５１を通じて入力バッファ１３２−５１に格納される。
【００５７】
次にルータ１３０−５は、ラウンドロビン方式に従い、入力ポート１３１−５２、入力ポート１３１−５３、入力ポート１３１−５４、入力ポート１３１−５５の順に注目を移すが、それらの入力ポート１３１−５２〜１３１−５５に対応する入力バッファ１３２−５２〜１３２−５５が空なので、ラウンドロビン方式に従い、入力ポート１３１−５１に再び注目を移す。次にルータ１３０−５は、入力ポート１３１−５１に対応する入力バッファ１３２−５１に格納されている最古のパケットＰ２１に注目する。次にルータ１３０−５は、パケットＰ２１の宛先（ＣＯＲＥ１１０−２）がルータ１３０−５の隣接モジュールであり、宛先に対応する出力バッファ１３４−５２に空きがあるので、図２５に示すように、パケットＰ２１を入力バッファ１３２−５１から出力バッファ１３４−５２へ転送する。出力バッファ１３４−５２に格納されたパケットＰ２１は、出力ポート１３３−５２により、ＣＯＲＥ１１０−２へ送信される。パケットＰ２１の転送によってルータ１３０−５の入力バッファ１３２−５１に空きが生じると、図２５に示すように、ルータ１３０−１から送信されたパケットＰ１２が入力ポート１３１−５１を通じて入力バッファ１３２−５１に格納される。
【００５８】
図２５に示すように、入力バッファ１３２−５１がメモリ１２０−１宛てのパケットＰ１２で占有され、その宛先に対応する出力バッファ１３４−５１に空きがない状態になると、ルータ１３０−５はルータ１３０−１から後続のパケットを受信することができなくなる。しかし、ルータ１３０−５は、ルータ１３０−１から後続のパケットを受信することができなくなるまで、合計３個のパケットＰ１１、Ｐ２１、Ｐ１２をルータＰ１３０−１から受信しており、しかも、そのうちの１個のパケットＰ２１を宛先のＣＯＲＥ１１０−２へ送信している。
【００５９】
これに対して、ルータ１３０−５が、ルータ１３０−１から宛先が同じパケットＰ１１〜Ｐ１２を連続して受信する場合、図２６に示すように、出力バッファ１３４−５１にパケットＰ１１が格納され、入力バッファ１３２−５１にパケットＰ１２が格納された状態になった時点で、ルータ１３０−５はルータ１３０−１から後続のパケットを受信することができなくなる。このような状態にいたるまで、ルータ１３０−５は、高々２個のパケットＰ１１、Ｐ１２をルータＰ１３０−１から受信しただけであり、しかもＣＯＲＥ１１０−２へは１つもパケットを送信できていない。
【００６０】
[第２の実施形態]
図２７は本発明の第２の実施形態に係るルータ２００の構成の一例を示す図である。図２７を参照すると、ルータ２００は、複数の入力ポート２１０と、複数の出力ポート２２０と、複数の入力バッファ２３０と、複数の出力バッファ２４０と、調停ユニット２５０とを含んで構成される。
【００６１】
複数の入力ポート２１０は、ルータ２００に接続されるモジュールに１対１に対応して設けられている。ルータ２００に接続されるモジュールは、メモリ、計算コア、ルータなどであってよい。入力バッファ２３０は、入力ポート２１０に１対１に対応して設けられる。入力バッファ２３０は、少なくとも１つのパケットを格納する容量のバッファを有する。入力バッファ２３０は、対応する入力ポート２１０から入力されたパケットを格納する。
【００６２】
複数の出力ポート２２０は、ルータ２００に接続されるモジュールに１対１に対応して設けられている。出力バッファ２４０は、出力ポート２２０に１対１に対応して設けられる。出力バッファ２４０は、少なくとも１つのパケットを格納する容量のバッファを有する。出力バッファ２４０は、対応する出力ポート２２０から出力するパケットを格納する。
【００６３】
調停ユニット２５０は、複数の入力バッファ２３０と複数の出力バッファ２４０とに接続される。調停ユニット２５０は、複数の入力バッファ２３０から複数の出力バッファ２４０へパケットを転送する。調停ユニット２５０は、入力バッファ２３０中のパケットの宛先に対応する出力バッファ２４０に前回転送した転送済パケットの宛先と入力バッファ２３０中のパケットの宛先とを比較した結果に基づいて、複数の入力バッファ２３０から複数の出力バッファ２４０へ次に転送するパケットを決定する。
【００６４】
このように構成されたルータ２００は、以下のように機能する。即ち、先ず複数の入力ポート２１０が、複数のパケットを入力する。次に、複数の入力バッファ２３０が、複数の入力ポート２１０から入力されたパケットを記憶する。次に、調停ユニット２５０が、複数の入力バッファ２３０から複数の出力バッファ２４０へパケットを転送する。その際、調停ユニット２５０は、入力バッファ２３０中のパケットの宛先に対応する出力バッファ２４０に前回転送した転送済パケットの宛先と入力バッファ２３０中のパケットの宛先とを比較した結果に基づいて、複数の入力バッファ２３０から複数の出力バッファ２４０へ次に転送するパケットを決定する。次に、複数の出力バッファ２４０が、転送されたパケットを記憶する。次に、複数の出力ポート２２０が、複数の出力バッファ２４０に記憶されたパケットを隣接するメモリ、計算コア、あるいはルータ等に出力する。
【００６５】
このように構成されたルータ２００によれば、それぞれの入力バッファ２３０および出力バッファ２４０のバッファの数にかかわらずに、ルータ２００の伝送性能を向上させることができる。その理由は、調停ユニット２５０が、入力バッファ２３０中のパケットの宛先に対応する出力バッファ２４０に前回転送した転送済パケットの宛先と入力バッファ２３０中のパケットの宛先とを比較した結果に基づいて、複数の入力バッファ２３０から複数の出力バッファ２４０へ次に転送するパケットを決定するため、ルータ２００のそれぞれの出力ポート２２０から同じ宛先の複数のパケットが連続して送信されることを防止できる。そのため、ルータ２００に接続される次のルータ２００において、入力ポートを通じて同じ宛先の複数のパケットが連続して入力バッファに入力される事態を防止できるためである。
【００６６】
以上、上記各実施形態を参照して本発明を説明したが、本発明は、上述した実施形態に限定されるものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解しうる様々な変更をすることができる。
【００６７】
例えば、調停ユニットのコントローラは、出力バッファに前回転送した転送済パケットの宛先と一致する１以上のパケットだけが複数の入力バッファに存在することを検出すると、出力バッファに前回転送した転送済パケットの宛先と一致する１以上のパケットの中から次に転送するパケットを決定するように構成されていてよい。
【産業上の利用可能性】
【００６８】
本発明は、ベクトルプロセッサ、ＧＰＵ等、グローバルなレイテンシおよびスループットの公平性を持ったネットワークオンチップ、並びにネットワークオンチップ上のルータ（中継装置）に適用できる。
【符号の説明】
【００６９】
１００…ＬＳＩチップ
１１０…ＣＯＲＥ
１２０…メモリ
１３０…ルータ
１３１…入力ポート
１３２…入力バッファ
１３３…出力ポート
１３４…出力バッファ
１３５…調停装置
１３６…クロスバスイッチ
１３７…コントローラ
１３８…宛先記憶領域
１４０…伝送路
１５０…伝送路
１６０…伝送路
２００…ルータ
２１０…入力ポート
２２０…出力ポート
２３０…入力バッファ
２４０…出力バッファ
２５０…調停ユニット
【図１】
2019029738.tif 000003
【図２】
2019029738.tif 000004
【図３】
2019029738.tif 000005
【図４】
2019029738.tif 000006
【図５】
2019029738.tif 000007
【図６】
2019029738.tif 000008
【図７】
2019029738.tif 000009
【図８】
2019029738.tif 000010
【図９】
2019029738.tif 000011
【図１０】
2019029738.tif 000012
【図１１】
2019029738.tif 000013
【図１２】
2019029738.tif 000014
【図１３】
2019029738.tif 000015
【図１４】
2019029738.tif 000016
【図１５】
2019029738.tif 000017
【図１６】
2019029738.tif 000018
【図１７】
2019029738.tif 000019
【図１８】
2019029738.tif 000020
【図１９】
2019029738.tif 000021
【図２０】
2019029738.tif 000022
【図２１】
2019029738.tif 000023
【図２２】
2019029738.tif 000024
【図２３】
2019029738.tif 000025
【図２４】
2019029738.tif 000026
【図２５】
2019029738.tif 000027
【図２６】
2019029738.tif 000028
【図２７】
2019029738.tif 000029
【手続補正書】
【提出日】平成30年8月24日(2018.8.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
パケットを入力する複数の入力ポートと、
前記複数の入力ポートから入力された前記パケットを記憶する複数の入力バッファと、
複数の出力ポートと、
前記複数の出力ポートから出力する前記パケットを記憶する複数の出力バッファと、
前記入力バッファ中のパケットの宛先に対応する前記出力バッファに前回転送した転送済パケットの宛先と前記入力バッファ中のパケットの宛先とを比較した結果に基づいて、前記複数の入力バッファから前記複数の出力バッファへ次に転送するパケットを決定し、且つ、前記出力バッファに前回転送した転送済パケットの宛先と一致する１以上のパケットだけが前記複数の入力バッファに存在することを検出すると、前記出力バッファに前回転送した転送済パケットの宛先と一致する１以上のパケットから次に転送するパケットを決定する調停ユニットと、
を含む中継装置。
【請求項２】
前記調停ユニットは、前記転送済パケットの宛先を前記出力バッファ毎に記憶する宛先記憶領域を有する、
請求項１に記載の中継装置。
【請求項３】
前記調停ユニットは、次に転送するパケットを１つ決定すると、前記複数の入力バッファをラウンドロビンで順番に１つ選択し、前記選択した入力バッファ中のパケットが次に転送するパケットであるか否かを決定する、
請求項１または２に記載の中継装置。
【請求項４】
前記調停ユニットは、１つの前記入力バッファ中に複数のパケットがある場合、前記入力バッファに記憶された時刻の古いパケットから順番に次に転送するパケットであるか否かを決定する、
請求項１乃至３の何れかに記載の中継装置。
【請求項５】
前記出力ポートは、前記出力バッファに記憶された時刻の古いパケットから順番にパケットを出力する、
請求項１乃至４の何れかに記載の中継装置。
【請求項６】
請求項１乃至５の何れか１項に記載された中継装置を複数備えるネットワークオンチップ装置。
【請求項７】
複数の入力ポートと複数の出力ポートと複数の入力バッファと複数の出力バッファと調停ユニットとを備える中継装置が実行する中継方法であって、
前記複数の入力ポートが、複数のパケットを入力し、
前記複数の入力バッファが、前記複数の入力ポートから入力された前記パケットを記憶し、
前記調停ユニットが、前記入力バッファに記憶されたパケットの宛先に対応する前記出力バッファに前回転送した転送済パケットの宛先と前記入力バッファに記憶された前記パケットの宛先とを比較した結果に基づいて、前記複数の入力バッファから前記複数の出力バッファへ次に転送するパケットを決定し、該決定では、前記出力バッファに前回転送した転送済パケットの宛先と一致する１以上のパケットだけが前記複数の入力バッファに存在することを検出すると、前記出力バッファに前回転送した転送済パケットの宛先と一致する１以上のパケットから次に転送するパケットを決定し、
前記複数の出力バッファが前記転送された前記パケットを記憶し、
前記複数の出力ポートが、前記複数の出力バッファに記憶された前記パケットを出力する、
中継方法。