(57)【特許請求の範囲】
【請求項１】
少なくとも１つのメッセージメモリ（２１２ａ、２１２ｂ）を備え、メッセージの受信および転送を行う、ネットワーク（１００）内のネットワークコントローラ（２１０）において、
−前記ネットワークコントローラ（２１０）は、少なくとも１つの隣接コントローラ（２２０）から、前記隣接ネットワークコントローラ（２２０）に格納されているメッセージ（２０２、２０４）の優先度情報を受信し、前記隣接コントローラ（２２０）は、前記ネットワーク（１００）内の前記ネットワークコントローラ（２１０）に隣接する第２のネットワークコントローラであり、
−前記ネットワークコントローラ（２１０）は、前記隣接コントローラ（２２０）に格納されたメッセージ（２０２、２０４）の前記優先度情報と、前記メッセージメモリ（２１２ａ、２１２ｂ）に格納されたメッセージ（２０１、２０３）の優先度情報とを比較し、
−前記ネットワークコントローラ（２１０）は、前記ネットワークコントローラ（２１０）と前記隣接コントローラ（２２０）との間のメッセージ輻輳の場合に、前記優先度情報の前記比較にしたがって、前記メッセージメモリ（２１２ａ、２１２ｂ）に格納された少なくとも第１のメッセージ（２０３）を前記隣接コントローラ（２２０）へと送信し、前記第１のメッセージ（２０３）を前記メッセージメモリ（２１２ａ、２１２ｂ）から消去し、および、前記隣接コントローラ（２２０）に格納された少なくとも第２のメッセージ（２０４）を前記隣接コントローラ（２２０）から受信し、前記第２のメッセージ（２０４）を前記メッセージメモリ（２１２ａ、２１２ｂ）に格納することを特徴とする、ネットワークコントローラ（２１０）。
【請求項２】
前記ネットワークコントローラ（２１０）は、
前記メッセージ輻輳が少なくとも部分的に、前記メッセージメモリ（２１２ａ、２１２ｂ）が満杯であることにより発生した場合に、前記メッセージメモリ（２１２ａ、２１２ｂ）に格納された前記第１のメッセージ（２０３）が、前記隣接コントローラ（２２０）に格納され前記ネットワークコントローラ（２１０）への伝送または前記ネットワークコントローラ（２１０）を介した伝送のために設けられた前記第２のメッセージ（２０４）よりも低い優先度を有するかという第１の結果に応じて、前記優先度情報を比較し、
前記第１の結果に当てはまる場合には、前記第１のメッセージ（２０３）を前記隣接コントローラ（２２０）へと送信し、前記メッセージメモリ（２１２ａ、２１２ｂ）内で、前記第１のメッセージ（２０３）を前記第２のメッセージ（２０４）により置換することを特徴とする、請求項１に記載のメッセージコントローラ（２１０）。
【請求項３】
前記ネットワークコントローラ（２１０）は、
前記メッセージ輻輳が少なくとも部分的に、前記隣接コントローラ（２２０）の第１のメモリ（２２２ａ、２２２ｂ）が満杯であることにより発生した場合に、前記メッセージメモリ（２１２ａ、２１２ｂ）に格納され前記隣接コントローラ（２２０）への伝送または前記隣接コントローラ（２２０）を介した伝送のために設けられた第１のメッセージ（２０３）が、前記隣接コントローラ（２２０）に格納された前記第２のメッセージ（２０４）よりも高い優先度を有するかという前記第２に結果に応じて、前記優先度情報を比較し、
前記第２の結果に当てはまる場合には、前記第１のメッセージ（２０３）を前記隣接コントローラ（２２０）へと送信し、前記メッセージメモリ（２１２ａ、２１２ｂ）内で、前記第１のメッセージ（２０３）を前記第２のメッセージ（２０４）により置換することを特徴とする、請求項１〜２のいずれか１項に記載のネットワークコントローラ（２１０）。
【請求項４】
前記ネットワークコントローラ（２１０）は、置換プロセスの数、および／または、前記第１のメッセージ（２０３）が経由したネットワークコントローラの数にしたがって、前記置換された第１のメッセージ（２０３）の前記優先度を上げることを特徴とする、請求項２に記載のネットワークコントローラ（２１０）。
【請求項５】
前記ネットワークコントローラ（２１０）は、置換プロセスの数、および／または、前記第２のメッセージ（２０４）が経由したネットワークコントローラの数にしたがって、前記置換された第２のメッセージ（２０４）の優先度を上げることを特徴とする請求項３に記載のネットワークコントローラ（２１０）。
【請求項６】
前記ネットワークコントローラは、前記第１のメッセージ（２０３）と前記第２のメッセージ（２０４）との前記交換の際に、メッセージ（２０４）を一時格納するための少なくとも１つの予約された記憶位置を有することを特徴とする、請求項１〜５のいずれか１項に記載のネットワークコントローラ（２１０）。
【請求項７】
前記予約された記憶位置は、別の一時的メモリ（２１１）により実現されることを特徴とする、請求項６に記載のネットワークコントローラ（２１０）。
【請求項８】
メッセージの受信、一時格納、および転送のためのネットワークコントローラ（２１０、２２０）を備えたネットワーク（１００）において、
−少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）は、前記２つの隣接するネットワークコントローラ（２１０、２２０）に格納されたメッセージの優先度情報を交換し、
−前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）の少なくとも第１または第２のネットワークコントローラは、前記優先度情報を比較し、
−前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）は、前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）の第１のネットワークコントローラのメッセージメモリが満杯の場合に、前記第１のネットワークコントローラの前記満杯のメッセージメモリからの、より優先度の低い第１のメッセージを、前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）の前記第２のネットワークコントローラへと送信し、前記第１のメッセージを、前記第１のネットワークコントローラの前記満杯のメッセージメモリから消去し、前記第２のネットワークコントローラのメッセージメモリからの、より優先度の高い第２のメッセージであって、前記第１のネットワークコントローラへの伝送または前記第１のネットワークコントローラを介した伝送のために決定される上記第２のメッセージを、前記第２のネットワークコントローラから前記第１のネットワークコントローラへと送信し、前記第２のネットワークコントローラの前記メッセージメモリから、前記第２のメッセージを消去することを特徴とする、ネットワーク（１００）。
【請求項９】
前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）間の前記優先度情報の前記交換は、前記メッセージの伝送とは異なるデータチャネルを介して行われることを特徴とする、請求項８に記載のネットワーク（１００）。
【請求項１０】
前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）間の前記優先度情報の前記交換は、前記メッセージの伝送のためのデータチャネルを介して行われることを特徴とする、請求項８に記載のネットワーク（１００）。
【請求項１１】
ネットワーク（１００）内でのメッセージの経路選択方法であって、前記ネットワーク（１００）は、メッセージの受信、一時格納、および転送のためにネットワークコントローラ（２１０、２２０）を有する、前記経路選択方法において、
−少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）は、前記２つの隣接するネットワークコントローラ（２１０、２２０）に格納されたメッセージの優先度情報を交換し、
−前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）の第１または第２のネットワークコントローラが、前記優先度情報を比較し、
−前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）の前記第１のネットワークコントローラのメッセージメモリが満杯の場合には、前記第１のネットワークコントローラの前記満杯のメッセージメモリからの、より優先度の低い第１のメッセージが、前記少なくとも２つの隣接するネットワークコントローラ（２１０、２２０）の前記第２のネットワークコントローラへと送信され、前記第１のメッセージが、前記第１のネットワークコントローラの前記満杯のメッセージメモリから消去され、前記第２のネットワークコントローラのメッセージメモリからの、より優先度の高い第２のメッセージであって、前記第１のネットワークコントローラへの伝送または前記第１のネットワークコントローラを介した伝送のために決定された上記第２のメッセージが、前記第２のネットワークコントローラから前記第１のネットワークコントローラへと送信され、前記第２のネットワークコントローラの前記メッセージメモリから、前記第２のメッセージが消去されることを特徴とする、経路選択方法。
【請求項１２】
前記メッセージの前記優先度情報は、前記メッセージのデータパケット形式で格納されることを特徴とする、請求項１１に記載の経路選択方法。
【請求項１３】
前記メッセージの前記優先度情報は、前記メッセージに追加して伝送されることを特徴とする、請求項１１に記載の経路選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク内の制御装置、ネットワーク、および、ネットワークにおけるメッセージの経路選択方法に関する。
【背景技術】
【０００２】
今日では、多くの分野においてネットワークが利用されており、すなわち、構成要素が、ネットワークコントローラのようなネットワーク構造を介してデータパケットを交換する。しかしながら、ネットワークの構造にしたがって、ネットワークコントローラからネットワークコントローラへの転送の際に輻輳（Ｓｔａｕ）が発生する可能性があり、すなわち、後続のコントローラのバッファがさらなるパケットを受け入れられないために、パケットを転送することができない。この影響は、事実上全てのネットワーク構造において観察され、最善の場合には、発生確率が最小化される。
【０００３】
研究では、輻輳問題の解決のために、輻輳を検出し対応してデータパケットのための代替的なルートを利用する最適経路選択アルゴリズム（ａｄａｐｔｉｖｅ  Ｒｏｕｔｉｎｇａｌｇｏｒｉｔｈｍｅｎ）が大抵利用される。しかしながら、この方法は、複数の可能なルートを必要とし、同様に輻輳問題を完全に解決することはできない。欧州特許出願公開第１８９５７２０号明細書は、オン・チップ・ネットワークでの最適経路選択方法に関する問題の解決アプローチの例をしている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ネットワーク、例えば、車両制御装置内のオン・チップ・ネットワークの特定の利用にとっては、輻輳も、最適経路選択アルゴリズムも、パケットの伝達時間（Ｐａｋｅｔｌａｕｆｚｅｉｔ）は決定論的とならず（ｎｉｃｈｔ−ｄｅｔｅｒｍｉｎｉｓｔｉｓｃｈ）、したがって、制御装置内での全タイミング動作（Ｇｅｓａｍｔ−Ｔｉｍｉｎｇ−Ｖｅｒｈａｌｔｅｎ）が予測可能ではない。さらに、最適経路選択方法には、経路を最適に決定しうるために、例えば、コントローラ上の追加的なロジックによる追加的な場所のような、追加的なコストがかかる。
【課題を解決するための手段】
【０００５】
独立請求項にかかる本発明は、ネットワーク内でのネットワークコントローラ、ネットワーク、または、ネットワークにおけるメッセージのための経路選択方法に関する。その際に、ネットワーク内のネットワークコントローラは、自身のメッセージメモリに格納されたメッセージの優先度情報を交換する。メッセージ輻輳（Ｎａｃｈｒｉｃｈｔｅｎｓｔａｕ）、すなわち、ネットワークコントローラのうちの第１のネットワークコントローラのメッセージメモリが満杯の場合には、優先度情報の比較により、満杯のメッセージメモリ内のより優先度の低い第１のメッセージが、隣接する第２のネットワークコントローラのメッセージメモリからの、より優先度の高い第２のメッセージにより交換されまたは置換され、その際に、第２のメッセージは第１のネットワークコントローラの満杯のメッセージメモリへの伝送のために設けられる、というプロセスが開始される。したがって、本発明は、メッセージ輻輳のネガティブ（ｎｅｇａｔｉｖ）な影響の低減、または比較的小さな計算コストによるメッセージ輻輳の低減のための好適な経路選択方法を記載し、本方法は特に、メッセージ輻輳の場合の、優先度がより高い／最も高いメッセージの伝達時間を低減しうる。その際に、特別な利点は、経路選択が、最適／動的な経路計画のためにコストがかかるコンピュータ機器が無くても行われ、伝達時間表等のような情報格納が必要ではなく、輻輳問題が、ネットワークの２つの隣接するネットワークコントローラで容易に行われる通信により対処されることである。これにより、技術的な負荷およびコストが節約される。したがって、本発明にかかる経路選択は、例えば、場所およびコストの節約が特に重要な、基板上でのオン・チップ・ネットワークまたはネットワークのために特に有利である。
【０００６】
さらなる効果および改善点は、従属請求項の特徴から明らかとなろう。
【０００７】
好適な構成において、ネットワークコントローラは、自身のメッセージメモリが満杯であり、かつ、自身のメッセージの優先度情報と、隣接コントローラのメッセージの受信された優先度情報との比較により、自身の満杯のメッセージメモリに格納されたメッセージ優先度よりも優先度の高いメッセージが、隣接コントローラ内で、上記満杯のメッセージメモリへの伝送のために設けられていることを確認した場合には、メッセージ交換を開始する。この構成により、本発明にかかるネットワークコントローラのメッセージメモリが満杯の場合のための経路検索方法の上記の利点が実現される。その際に、好適には、メッセージ交換を開始するネットワークコントローラのみが、優先度情報を比較しおよびメッセージ交換を開始するように構成される必要があり、例えば、このようなネットワークコントローラは、メッセージメモリが特に満杯になりやすいネットワークノードで利用されうる。
【０００８】
さらなる別の好適な実施は、自身の隣接コントローラのメッセージメモリが満杯であり、自身のメッセージの優先度情報と、隣接コントローラのメッセージの優先度情報との比較により、隣接コントローラ内に、ネットワークコントローラの自身のメッセージメモリに格納され隣接コントローラのメッセージメモリへの伝送のために設けられたメッセージよりも低い優先度を有するメッセージが格納されていることを自身が確認した場合に、メッセージ交換を開始するネットワークコントローラに基づいている。その際に、好適には、メッセージ交換を開始するネットワークコントローラのみが、優先度情を比較しおよびメッセージ交換を開始するように構成される必要があり、例えば、このようなネットワークコントローラは、メッセージメモリが特に満杯になりやすいネットワークノードで利用されうる。
【０００９】
さらに、例えば、置換プロセスの数、および／または、経由した（ｂｅｓｕｃｈｔｅｎ）ネットワークコントローラの数にしたがって、ネットワークコントローラによって、より優先度が低いメッセージの優先度を上げることは、有利な構成でありうる。これにより、より優先度の低いメッセージが、メッセージ輻輳によって、および特に、より優先度の高いメッセージとの交換によっても非常に長い伝達時間を有し、または、極端な場合に送り先に全く到達しないということが防止されうる。
【００１０】
好適には、本発明にかかるネットワークコントローラは、様々な優先度のメッセージの交換の際にメッセージを一時格納するための予約された記憶場所を有しうる。特別な構成において、この記憶位置は、ネットワークコントローラの別の一時的メモリとして実現される。予約された記憶位置によって、データ伝送路または関与するネットワークコントローラまたは交換されるメッセージが、同時伝送のためまたは同時メッセージ交換のために適していない場合にも、メッセージ輻輳の際に様々な優先度のメッセージのメッセージ交換が進行しうる。
【００１１】
好適な実施例において、優先度情報が、２つの隣接するネットワークコントローラの間で、メッセージとは異なるデータチャネルを介して伝送される。これにより、同一のデータチャネル上でのさらなる別の伝送による、メッセージ伝送レートの負荷が防止される。好適な代替的な構成において、優先度情報は、メッセージと同じデータチャネルを介して伝送される。これにより、好適に、さらなる別の接続のコストが防止されうる。
【００１２】
優先度情報の追加的な伝送のコストまたはデータ負荷が防止されるために、メッセージの優先度情報を、メッセージのデータパケット形式で設けることは有利でありうる。場合によっては、例えば、定められたデータパケット形式が、このような情報の格納を見込んでおらずまたは許容しない場合のためには、メッセージとは別にまたはメッセージに追加して優先度情報を伝送することも有利でありうる。
【図面の簡単な説明】
【００１３】
本発明の実施例が図面に記載され、以下の記載においてより詳細に解説される。図面は単に例示的なものであり、発明の思想全般を制限するものではない。その際に、符号の下２桁が同じ場合は、同一または比較可能な構成要素を示す。
【図１】ネットワークを示す。
【図２】ネットワークの２つの隣接するネットワークコントローラ間の様々な優先度のメッセージの本発明にかかる交換の例を示す。
【発明を実施するための形態】
【００１４】
以下では、本発明にかかる経路選択（Ｒｏｕｔｉｎｇ）、または、本発明にかかるネットワークコントローラ、および、本発明にかかるネットワークが、特に好適なオン・チップ・ネットワークの例において解説されるが、これにより、本発明は、この形態のネットワークに限定されるものではない。むしろ、本発明は、他のネットワークのためにも限定されることなく利用可能である。
【００１５】
典型的なオン・チップ・ネットワーク（Ｏｎ−Ｃｈｉｐ−Ｎｅｔｚｗｅｒｋ）は、複数のネットワークコントローラにより、チップ（Ｃｈｉｐ）の構成要素を接続する。これらのコントローラは、標準的に大抵、転送の前にデータパケットを一時格納しうる少なくとも１つの内部バッファを有する。図１は、オン・チップ・ネットワークを示しており、これに基づいてメッセージ輻輳の例を解説する。ここでは、オン・チップ・ネットワーク１００は、ネットワークコントローラ１１０、１２０、１３０、１４０、１５０、１６０、１７０、１８０を有し、それぞれが内部のメモリ構成１１５、１２５、１３５、１４５、１５５、１６５、１７５、１８５を備える。さらに、ネットワークコントローラ１１０は、通信接続１９１および１９２と接続され、ネットワークコントローラ１２０も同様に、通信接続１９２と、さらに通信接続１９３と接続され、ネットワークコントローラ１３０も同様に、通信接続１９３と接続される。さらなる別の通信接続を介して、ネットワークコントローラ１１０は１５０と、１５０は１６０と、１６０は１２０と、１３０は１７０と、１３０は１４０と、１４０は１８０と、１７０は１８０と互いに接続される。ネットワークコントローラ１１０、１５０、１６０、１７０および１８０はそれぞれ、図１に図示されない隣接するネットワークコントローラへのさらなる別の通信接続を有する。
【００１６】
このオン・チップ・ネットワーク１００内では、従来技術にしたがって、メッセージは、固定の経路を介して、または例えば、動的に決定される経路を介しても、ネットワークによって導かれる。ネットワークコントローラのバッファ／メッセージメモリが満杯の場合には、当該ネットワークコントローラは、通常の構成では、さらなるパケットの受信を阻止する。本発明にかかるシステム構造では、この阻止しているネットワークコントローラにデータを送信したい隣接するネットワークコントローラは、当該阻止しているネットワークコントローラと優先度情報を交換し、より優先度が高いメッセージを当該阻止しているネットワークコントローラへと送信する準備ができている。その際に、輻輳の場合には、２つのネットワークコントローラ間での、優先度が異なるメッセージの合目的的な交換が行われる。その際に、阻止されたより優先度の高いメッセージは、自身の経路上において、阻止されたより優先度の低いメッセージの場所を取る。よけられたメッセージは、より優先度の高いメッセージの、開いた場所に割り当てられる。このようにして、特定の状況において、最も優先度の高いメッセージに、一意に決定可能な最大伝達時間を割り当てることができる。さらに、メッセージの優先度は、例えば、データパケットの形式で組み込まれ、または別に伝送される。
【００１７】
例えば、ネットワークコントローラ１２０のメッセージメモリ１２５が満杯であり、または、ネットワークコントローラ１１０からのメッセージのためには満杯である場合に、ネットワークコントローラ１１０と１２０との間で、図１のオン・チップ・ネットワーク１００においてメッセージ輻輳が発生する。このようなメッセージ輻輳の原因は、例えば、通信接続１９２を介して特定の時間内に、通信接続１９３を介した転送のために設けられたメッセージが、ネットワークコントローラが通信接続１９３を介して当該特定の時間内に転送しうるよりも多く、メッセージコントローラ１２０に到着することにある。本発明にかかる手続きにより特に良好に解決可能なメッセージ輻輳のさらなる別の例は、通信接続１９３が、ネットワークコントローラ１２０からのより優先度の低いメッセージについてブロックされ、ネットワークコントローラ１２０が、より優先度が低いメッセージで満杯のメモリ構成１２５を有する場合である。
【００１８】
とくにクリティカル（ｋｒｉｔｉｓｃｈ）なのは、ネットワークコントローラ１１０のメッセージメモリ１１５内に格納されネットワークコントローラ１２０への（ａｕｆ）伝送、または、ネットワークコントローラ１２０を介したおよびさらに例えば通信接続１９３を介した伝送のために決定された優先度が高いメッセージについてのメッセージ輻輳である。
【００１９】
本発明にかかる経路選択が、図２を用いて、様々な輻輳問題、例えば、図１を用いて記載されたメッセージ輻輳についても解説される。その際に、図２は、図１のネットワークコントローラ１１０および１２０と比較可能に、オン・チップ・ネットワークに組み込まれたネットワークコントローラ２１０および２２０を示す。ネットワークコントローラ２１０は、内部のメモリ構成２１１、２１２ａ、２１２ｂを有し、これら内部のメモリ構成２１１、２１２ａ、２１２ｂは、一時的メモリ２１１、並びに、メッセージメモリセグメント２１２ａおよび２１２ｂを有する。さらに、ネットワークコントローラ２１０は、通信接続２９１、２９２、および２９４と接続される。ネットワークコントローラ２２０は、内部のメモリ構成２２１、２２２ａ、２２２ｂを有し、この内部のメモリ構成２２１、２２２ａ、２２２ｂは、一時的メモリ２２１、並びに、メッセージメモリセグメント２２２ａおよび２２２ｂを有する。さらに、ネットワークコントローラ２２０は、通信接続２９２、２９３、および２９５と接続される。図２に示されるケースでは、ネットワークコントローラ２１０のメッセージメモリセグメント２１２ａにはメッセージ２０１が格納され、ネットワークコントローラ２２０のメッセージメモリセグメント２２２ａには、メッセージ２０２が格納される。図２に示す経路選択の開始に際して、メッセージ２０３が、ネットワークコントローラ２１０のメッセージメモリセグメント２１２ｂに格納され、および、メッセージ２０４が、ネットワークコントローラ２２０のメッセージメモリセグメント２２２ｂに格納されているとする。図１に記載したメッセージ輻輳のケースと同じように、ネットワークコントローラ２２０のメッセージメモリセグメント２２２ａ、２２２ｂは、メッセージ２０２および２０４で満杯である。ここで示される例ではさらに、ネットワークコントローラ２１０のメッセージメモリ２１２ａ、２１２ｂも、メッセージ２０１および２０３で満杯である。
【００２０】
本発明によれば、メッセージ輻輳問題の解決のために、少なくともより優先度が高いメッセージについて、ネットワークコントローラ２１と２２０とは、自身のメッセージメモリ２１２ａ、２１２ｂまたは２２２ａ、２２２ｂに格納されたメッセージ２０１、２０３、または、２０２、２０４についての優先度情報を交換する。例えば、交換された優先度情報の比較により、ネットワークコントローラ２１０に格納されたメッセージ２０３が、通信接続２９２を介したネットワークコントローラ２２０への伝送、または、ネットワークコントロー２２０を介してさらに通信接続２９３または２０５への伝送のために構想されているということ、さらに、このメッセージ２０３が、ネットワークコントローラ２２０に格納されたメッセージ２０４よりも優先度が高いということが確認される。この確認、および、満杯のメッセージメモリ２２２ａ、２２２ｂにより確認されるメッセージ輻輳に基づいて、さらに、本発明によれば、メッセージ２０３と２０４とが、ネットワークコントローラ２１０と２２０との間で交換され、すなわち、メッセージ２０３は、ネットワークコントローラ２１０からネットワークコントローラ２２０へと伝送され、メッセージネットワークコントローラ２１０のメッセージメモリセグメント２１２ｂから消去される。同様に、メッセージ２０４が、ネットワークコントローラ２２０からネットワークコントローラ２１０へと伝送され、ネットワークコントローラ２１０のメッセージメモリセグメント２２２ｂから消去される。
【００２１】
この本発明にかかるメッセージ交換は、通信接続２９２と、ネットワークコントローラ２１０および２２０がそのために構成される場合には、例えば同時に行うことができる。
【００２２】
代替的に、ネットワークコントローラ２１０と２２０とは、図２に示すように、メッセージ２０３と２０４とがメッセージ交換の際に一時格納されうる一時的メモリ２１１または２２１も有する。
【００２３】
以下では、図２および２つの代替的な例を用いて、ネットワークコントローラ２１０とその隣接コントローラ２２０との間の交換プロトコルが詳細に記載される。
【００２４】
第１の例では、ネットワークコントローラ２１０のメッセージメモリ２１２ａ、２１２ｂが満杯であり、隣接コントローラ２２０が、通信接続２９２を介したネットワークコントローラ２１０への伝送のため、または、通信接続２９２を介し、および、ネットワークコントローラ２１０を介し、およびさらに通信接続２９１または２９４を介した伝送のために設けられた少なくとも１つのメッセージ２０４を、自身のメッセージメモリ２２２ａ、２２２ｂに格納している。したがって、ネットワークコントローラ２１０と隣接コントローラ２２０との間にメッセージ輻輳が存在する。本例では、隣接コントローラ２２０は、メッセージコントローラ２１０への伝送またはメッセージコントローラ２１０を介した伝送のために設けられた、最も優先度が高いメッセージ、例えばメッセージ２０４の優先度情報を、ネットワークコントローラ２１０へと伝送する。代替的に、メッセージコントローラ２２０が、自身のメッセージメモリ２２２ａ、２２２ｂに格納された全てのメッセージ２０２および２０４の優先度情報、または、ネットワークコントローラ２１０への伝送のために設けられた少なくとも全てのメッセージの優先度情報を、このネットワークコントローラ２１０へと伝送することも構想されうる。ネットワークコントローラ２１０は、隣接コントローラ２１０により受信された優先度情報と、自身のメッセージメモリ２１２ａ、２１２ｂに格納されたメッセージ２０１および２０３の優先度情報と、を比較する。メッセージ２０４の優先度が、メッセージ２０１および２０３のうちの１つの優先度よりも高い場合には、ネットワークコントローラ２１０は、信号を介して、隣接コントローラ２２０とのメッセージ交換を開始する。図１と同じように、例えば、メッセージ２０３の優先度は、メッセージ２０４の優先度よりも低い。ネットワークコントローラ２１０は、計画されたメッセージ２０３と２０４との交換についての通知を、隣接コントローラ２２０へと送信し、この隣接コントローラ２２０は、場合によっては確認信号により、ネットワークコントローラ２１０に対して受領確認する。さらに、メッセージ２０４が、隣接コントローラ２２０のメッセージメモリセグメント２２２ｂから、ネットワークコントローラ２１０のメッセージメモリセグメント２１２ｂへと伝送され、したがって、メッセージ２０３が上書きされ、同時に、メッセージ２０３が、ネットワークコントローラ２１０のメッセージメモリセグメント２１２ｂから隣接コントローラ２２０のメッセージメモリセグメント２２２ｂへと伝送され、したがって、メッセージ２０４が上書きされる。代替的に、同時のメッセージ伝送がサポートされていない場合には、メッセージ２０３、２０４の一方が、最初に一時的メモリ２１１、２２１に伝送され、対応するメッセージメモリセグメントから消去され、その後、メッセージ２０３、２０４の他方が伝送され、対応されるメッセージメモリセグメントから消去される。
【００２５】
第２の例では、隣接コントローラ２２０のメッセージメモリ２２２ａ、２２２ｂが満杯であり、ネットワークコントローラ２１０と隣接コントローラ２２０との間にメッセージ輻輳が存在する。本例では、隣接コントローラ２２０が、格納された自身の全てのメッセージ２０２および２０４の優先度情報、または好適に、メッセージ２０２と２０４のうちの、優先度が低いメッセージの優先度情報を、ネットワークコントローラ２１０へと送信する。ネットワークコントローラ２１０は、先に記載したように、受信された優先度情報と、自身のメッセージ２０１および２０３の優先度情報と、を比較し、自身のメッセージ２０１および２０３のうちの１つが、メッセージ２０２または２０４のうちの１つよりも高い優先度を有し、このメッセージ、図２と同様にメッセージ２０３が、隣接コントローラ２２０への伝送、または隣接コントローラ２２０を介した伝送のために決定されている場合について、メッセージ交換を開始する。メッセージ２０３と２０４とのメッセージ交換は、先に記載したように行われる。
【００２６】
本発明にかかるメッセージ交換の際にメッセージを一時格納するための、図２に示した一時的メモリの代わりに、および、本発明にかかるメッセージ交換の際の同時のメッセージ伝送の代わりに、ネットワークコントローラのメッセージメモリ内の別の記憶位置も、本発明にかかるメッセージ交換の場合にメッセージが一時格納できるために開放されうる。
【００２７】
メッセージの優先度情報は、好適に、メッセージのデータパケット形式において、例えば、メッセージヘッダ内に格納されうる。代替的な可能性は、メッセージ伝送の通信接続を介した別の伝送、または、オン・チップ・ネットワークのネットワークコントローラ間の別の通信接続を介した別の伝送である。その際、図１および図２に描かれた通信接続は、単線伝送（Ｅｉｎ−Ｄｒａｈｔ−Ｌｅｉｔｕｎｇ）に限定されない。例えば、先に代替例として記載したように、データ交換時の並列データ伝送のために、ネットワークコントローラ間での並列のデータチャネルも利用可能である必要がある。メッセージ／データ伝送と並んで、本発明にかかる方法のために、制御情報（交換の開始または確認）および優先度情報も、ネットワークコントローラ間で伝送される必要がある。この要求は、プロトコルレベルで複数のデータ線を介して、または、マルチプレックス方式（Ｍｕｌｔｉｐｌｅｘｖｅｒｆａｈｒｅｎ）を介して満たされうる。
【００２８】
システム／ネットワークレベルでは、本発明が好適に、全てのネットワークコントローラが本発明に基づいて機能しうるように実施される。例えば、全てのコントローラは、自身のバッファ内の最高の優先度のパケットの優先度情報を、このメッセージの経路上に存在する隣接ノードへと導く。輻輳状況のために自身の満杯のメッセージメモリ内のメッセージを転送できないネットワークコントローラは、自身のメッセージ入力口で、自身の隣接コントローラの優先度情報を検査する。メッセージメモリが満杯のネットワークコントローラは、一時格納している自身のメッセージの優先度よりも優先度の高いメッセージが、自身の隣接ネットワークコントローラのうちの１つにより受信される必要があるかどうかを検出する。この場合には、メッセージメモリが満杯のネットワークコントローラは、先に記載したようにメッセージ交換を開始する。プロトコルを開始するネットワークコントローラの役割も同様に、先に記載したように交換されうる。さらに、メッセージメモリが満杯の隣接コントローラは、自身のメッセージメモリ内のメッセージの、最も低いメッセージ優先度の情報を、全ての隣接するネットワークコントローラへと導く。ネットワークコントローラは、より優先度が高いメッセージを隣接コントローラへと送信する必要がある場合には検出し、メッセージ交換を開始する。
【００２９】
ネットワークレベルでは好適に、ネットワークコントローラが、隣接コントローラのみならず複数の隣接コントローラと、場合によっては同時に、本発明によれば、優先度情報およびメッセージを交換することも構想されうる。このような場合には、ネットワークコントローラは、１つのメッセージメモリおよび／または一時的メモリのみならず、複数のメッセージメモリまたは一時的メモリを、好適に各メッセージコントローラについて１つのメッセージメモリおよび／または１つの一時的メモリを、有しうる。
【００３０】
本発明にかかる方法により、輻輳の場合には、最も優先度の高いパケット（メッセージ）は、発生するプロトコルの負荷によってのみ、転送が妨げられる。輻輳によって転送が妨げられる可能性のあるより優先度の低いパケットの明らかな依存性が無くなる（ｅｎｔｆａｌｌｅｎ）。したがって、以下の公式にしたがって、優先度が最も高いパケットの最大伝達時間を決定することができる。ｎは、開始コントローラ（Ｓｔａｒｔｃｏｎｔｒｏｌｌｅｒ）から最終コントローラ（Ｅｎｄｃｏｎｔｒｏｌｌｅｒ）へと、パケットを自身の経路上で通過させる必要があるネットワークコントローラの数である。最悪の場合には、このｎ個の各コントローラのために、上記の方法が実施される必要がある。さらに、ｍは、メッセージ交換のために本方法が必要とする時間単位であり、ｔは、２つの隣接するコントローラ間でパケットを伝送するために必要な時間単位（例えば、クロックサイクル、または、非同時のネットワーク（Ｎｅｔｚ）の場合の所要時間）である。したがって、既知の経路を直接的に進む場合の優先度が最も高いパケットのための最大伝達時間は、以下のようになる。
Ｔ＝（ｎ−１）＊（ｍ＋ｔ）
【００３１】
ただし、その際、ネットワーク内に、１つのメッセージ／パケットのみ、または、十分に少ない、最も優先度の高いメッセージ／パケットが存在するということに基づいている。本方法は、輻輳が、例えば、優先度が最も高いメッセージによってのみ引き起こされるであろう（すなわち、ネットワークコントローラのメッセージメモリが、優先度が最も高いメッセージで満杯であり、および、これらのメッセージの転送が可能ではなく、この輻輳のために、隣接するネットワークコントローラ内で、優先度が最も高いさらなる別のメッセージが待機する必要がある）場合には、決定論的に伝達時間を予測することはない。
【００３２】
より優先度が低いパケットについては、いずれの場合も伝達時間の予測が困難なままである。本発明にかかる方法により、より優先度が低いメッセージが非常に長い伝送時間を有し、または、場合によっては自身の宛先に全く到達しないということを防止するために、より優先度が低いメッセージが、例えば、通過した（ｄｕｒｃｈｌａｕｆｅｎ）ネットワークコントローラの数にしたがって、および／または、当該ネットワークコントローラが関与する本発明にかかるメッセージ交換プロセスの数にしたがって、自身の優先度が上がったことが分かることが提案される。
【００３３】
オン・チップ・ネットワーク内でのメッセージ経路選択を特に効率良く構成するために、本発明にかかる方法を、公知の経路選択方法、例えば、動的な経路選択方法と組み合わせることも提案される。このような場合に、本発明にかかる方法は、動的な経路決定のアルゴリズムにおいて考慮されうる。
【図１】
0005260791.tif 000002
【図２】
0005260791.tif 000003