JP2008512021A - ２つの通信コントローラを使用する分散通信システムおよびそのような通信システムを動作させる方法 - Google Patents

Abstract

いくつかのノード（１００、１００’、１００”）が少なくとも２本のチャネル（１０、２０）を含む少なくとも１本の通信リンクによって相互接続される分散通信システムを動作させるための、特にそのような分散通信システム中のクロックを同期させるための方法であって、通信コントローラ（３０、３２）に接続されたチャネル（１０、２０）のうちの少なくとも１つへの、アプリケーション・ホスト（６０）のアクセスを、この通信コントローラ（３０、３２）が故障したり壊れたりした場合にも維持することが可能な方法を提供するために、各チャネル（１０、２０）がそれ自体の通信コントローラ（３０、３２）によって制御されることが提案される。

Description

本発明は一般に、フォールト・トレラント時間トリガ通信システム用のアーキテクチャに関する。

本発明は特に、いくつかのノードが少なくとも２本のチャネルを含む少なくとも１本の通信リンクによって相互接続される分散通信システムを動作させるための、特にそのような分散通信システム中のクロックを同期させるための方法に関する。

本発明はさらに、いくつかのノードが少なくとも２本のチャネルを含む少なくとも１本の通信リンクによって相互接続される分散通信システムのノードに関する。

図１では、典型的なフォールト・トレラント時間トリガ・ネットワークが、概略図で示されている。このネットワークは、２本のチャネルＣ１、Ｃ２を含んでおり、それらにそれぞれのノードＮが接続される。これらのノードＮはそれぞれ、バス・ドライバＢ１、Ｂ２、プロトコル・エンジンＰおよびコントローラ・ホスト・インターフェースＣＩをもつ通信コントローラＣＣ、オプションで各バス・ドライバＢ１、Ｂ２ごとのバス・ガーディアン装置、ならびにアプリケーション・ホストＨを含む。

バス・ドライバＢ１、Ｂ２は、通信コントローラＣＣによって提供されるビットおよびバイトをその接続チャネルＣ１、Ｃ２上に送信し、今度はチャネルＣ１、Ｃ２上で受信される情報を通信コントローラＣＣに提供する。通信コントローラＣＣは、そのバス・ドライバＢ１、Ｂ２を介して両チャネルＣ１、Ｃ２に接続され、該当データをホスト・アプリケーションＨに送達し、データをホスト・アプリケーションＨから受け取り、そのホスト・アプリケーションＨは、データをフレームに組み立て、そのデータをバス・ドライバＢ１、Ｂ２に送達する。

バス・ドライバＢ１、Ｂ２、（オプションの）バス・ガーディアン、およびホスト装置Ｈは、少なくとも一部、時間トリガされ、すなわち時間が、各サイクルがいくつかのセグメントを含む循環サイクルに、スライスされる。各ノードＮは、それ自体の組込みクロックに従って、新しいサイクルの開始を確定する。

少なくとも１つのセグメントが、固定数のスロットに分割され、ここで各スロットには、最大でもせいぜい１つの通信コントローラＣＣが割り当てられ、その場合、その通信コントローラＣＣだけが、送信する権限を有する。そのサイクルの他のセグメントは、動的アービトレーション方式またはその他の目的に使用されることができる。

バス・ガーディアンとは、構成セットによって指定されるスロット中のみ、バス上の送信を可能にする、独立した１組の構成データをもつ装置である。

ホスト・アプリケーションＨは、データ・ソースおよびデータ・シンクを含んでおり、一般にプロトコル・アクティビティには関わらない。通信コントローラＣＣが単独で行うことのできない判断だけが、ホスト・アプリケーションＨによって行われる。

各ノードＮが、サイクルの開始を独自に得、それによって時間におけるすべてのセグメントおよびスロットの配置を得るので、ノードＮは、互いに同期される必要がある。各ノードＮは、その故障がシステム全体に障害を起こすことになる単一のマスタ・クロックに依存しないようにするために、自分のクロックを有する。同期ノード（またはシンク・ノード）と呼ばれる、それ自体のクロックとシステムのノードの何らかのサブセットのクロックとの差が、フォールト・トレラントな仕方でそれ自体のクロックを補正するために使用される。

２種類のクロック補正、すなわち、
純粋オフセット補正、および
オフセット補正とレート補正の組合せ
が可能である。

オフセット補正は単に、クロック・オフセットを補正し、一方、レート補正は、システム中のクロックの異なるレートを整合させようとも試み、それによって、クロックを互いにより近くに維持する（必要なオフセット補正量を低減させ、それによって、相互送信ギャップが小さくなるので、利用可能な帯域幅が増大する）。レート偏差を計算するために２つの測定値が必要なので、レートおよびオフセット補正の場合、一般にクロックは、１サイクルの最後または２サイクルの最後に補正される。

すべてのシンク（同期）ノードが、自分の割当てスロットのうちの１つの中で、両チャネルＣ１、Ｃ２上で同時に同期フレームを送信する必要がある。したがって、すべてのノードは、同じ時間情報を受信し、１つのチャネルにのみ接続されるノードも同様である。上記に合致するシステムが、
Ｈｅｒｍａｎ Ｋｏｐｅｔｚ等の「Ｓｐｅｃｉｆｉｃａｔｉｏｎ ｏｆ ｔｈｅ ＴＴＰ／Ｃ ｐｒｏｔｏｃｏｌ」（ドラフト０．５）、ＴＴＴｅｃｈ Ｃｏｍｐｕｔｅｒｔｅｃｈｎｉｋ ＡＧ社、１９９９年７月（ｈｔｔｐ：／／ｗｗｗ．ｔｔｔｅｃｈ．ｃｏｍ／参照）、または
Ｒ．Ｂｅｌｓｃｈｎｅｒ等の「ＦｌｅｘＲａｙ−Ｒｅｑｕｉｒｅｍｅｎｔｓ Ｓｐｅｃｉｆｉｃａｔｉｏｎ」（バージョン２．０．２）、ＦｌｅｘＲａｙコンソーシアム、２００２年４月（ｈｔｔｐ：／／ｗｗｗ．ｆｌｅｘｒａｙ．ｃｏｍ／参照）
に開示されている。それに対応する先行技術文書ＷＯ ０３／０１０６１１ Ａ１は、ＦｌｅｘＲａｙプロトコルに関するものであり、特に、ノード・サブセット、メッセージ受信、時間およびクロック・レート偏差測定、オフセット補正値計算およびクロック・レート補正値計算、ならびにノード・クロック調整を有するＦｌｅｘＲａｙ（登録商標）自動車通信システムでの、分散システム中のクロック同期について、明らかにしている。

先行技術文書の欧州特許第１ ３５５ ４５９ Ａ２号は、少なくとも１つの通信媒体、およびその通信媒体に接続されたいくつかのノードを含む分散通信システム中のクロックを同期させる方法について言及している。ただし、それらのノードは、それらのクロックを含む。それらのノードのクロックを高精度で同期させ、それと同時に、クロック・レートにおける高偏差を許容することを可能にするために、クロックを同期させるのに、クロックのオフセット差およびクロックのレート差が補正されることが提案されている。

それ以外にも、先行技術文書の特開２００３−１９５９０３は、二重化通信モジュール装置を開示している。しかし、この先行技術文書は、二重化システムのフォールト・トレラント分散同期については言及していない。

前述のようなあらゆる努力にもかかわらず、デュアル・チャネル通信コントローラに障害が起きた場合、その接続チャネルへのアクセスがどちらも妨げられ、それによって、その通信コントローラのアプリケーション・ホストが通信から切り離されてしまう、という問題が残っている。単一の通信コントローラに両チャネルを扱わせることにより、いくつかの単一故障点が生じ、たとえばクロック同期は単に、１回だけ実施され使用される。

前述の欠点および短所を出発点とし、論じられた先行技術を考慮して、本発明の目的は、通信コントローラに接続されたチャネルのうちの少なくとも１つへの、アプリケーション・ホストのアクセスを、この通信コントローラが故障したり壊れたりした場合にも維持することである。

本発明の目的は、請求項１の特徴を含む方法および請求項５の特徴を含むノードによって実現される。本発明の有利な実施形態および好都合な改良形態が、それぞれの従属請求項に開示されている。

本発明の主旨は、フォールト・トレラント時間トリガ通信システムのために、デュアル・チャネル・クロック同期をシングル・チャネル・ベースのアーキテクチャと組み合わせる、という概念である。この文脈では、各チャネルの通信コントローラは好ましくは、オフセットとレートの両方に補正を適用する、何らかの種類の、相互間のフォールト・トレラント・クロック補正機構を使用する。

本発明によるシングル・チャネル・アーキテクチャ、すなわち、通信コントローラを２つの独立したエンティティに分離する手法は、各エンティティ（＝いわゆるシングル・チャネル通信コントローラ）が、片方が故障しても働き続けることができるという利点を有する。言い換えれば、少なくとも２つのシングル・チャネル通信コントローラが、一方のシングル・チャネル通信コントローラの故障が他方のシングル・チャネル通信コントローラのさらなる通信を妨げ得ないような仕方で、互いに通信する。

さらに、通信ノードが、他方の、場合によっては従来の通信コントローラと対話できるようにするために、根本的に異なる挙動がチャネル上で示されてはならない（一方、アプリケーションに対するインターフェースは異なってもよい）ことが、当業者には理解されよう。そのような解決策が使用されて、
２つの異なるチップを、すなわち各チャネルごとに１つの通信コントローラを提供することもでき、または、
２つのシングル・チャネル通信コントローラを単一のチップに統合して、より低いフォールト・トレランスしか必要としない通信システムに対するコストを低減させることもできる。

本発明の好ましい実施形態によれば、シングル・チャネル通信コントローラの２つの異なる機構が、すなわち起動およびクロック同期が通信する必要がある。

シングル・チャネル通信コントローラを２つの（ほとんど）独立したエンティティに分割することによって、２つの異なる故障領域がもたらされる。したがって、新規の通信コントローラのうちの一方が故障の場合、他方の通信コントローラは働き続ける。しかし、この機構は、２つのシングル・チャネル通信コントローラの組み合わされた挙動がデュアル・チャネル通信コントローラの挙動から過度に逸脱しない場合にのみ、従来のデュアル・チャネル通信コントローラとともに働くことができる。特に、両通信コントローラのクロックは、よく整合されるべきである（これは、デュアル・チャネル通信コントローラはいずれにしても１つのクロックしか含まないので、デュアル・チャネル通信コントローラでは実現される）。

本発明によって提案される機構は、既によく整合されたチャネルを、よく整合されたままに維持するが、一方、互いにずれたチャネルは、たとえば半サイクル長以上、互いにずれたチャネルは、必ずしも同期させない。それとともに、またはそれとは独立に、各チャネルの通信コントローラは好ましくは、何らかの種類の、相互間のフォールト・トレラント・クロック補正機構を使用する。

したがって、本発明は、チャネルを「必要なだけ同期した」ように維持する、すなわち各シングル・チャネル通信コントローラは、それ自体と、反対チャネルのその接続シングル・チャネル通信コントローラとのタイミング差によく追従する、という概念を実現する。

これを実現する第１の選択肢は、少なくとも１つの専用インターフェースによるものであり、それにより、２つのシングル・チャネル通信コントローラが、それぞれの自分の時間に対する、それぞれの他方のシングル・チャネル通信コントローラの時間を、相互に測定する。これは有利には、ローカルのサイクル開始を他方のシングル・チャネル通信コントローラに通知する、少なくとも１つの専用信号線によって使用され得る。

適用されるクロック同期アルゴリズムによっては、補正フェーズの直前の信号がより良い結果をもたらし得るが、他の時点も可能である。必要なことは、接続シングル・チャネル通信コントローラが、いつ信号を予期する必要があるかを知ることだけである。したがって、接続シングル・チャネル通信コントローラは、予期される信号と実際の信号の差から、クロック・オフセットを計算することができる。この信号によって、２つのシングル・チャネル通信コントローラのオフセット差およびレート差が計算されることができる。

別の選択肢は、ローカル・クロックおよびチャネルに関するより多くの情報を組み込んだ数値を、直接交換することである。

これで、２つの関連シングル・チャネル通信コントローラは、互いに自分の有するクロック差がわかる。すべてのシングル・チャネル通信コントローラが、自分のローカルの相手方に対するクロック差がわかる。それらはすべて、同一方法で、さらなる符号付きチャネル間補正を計算する。

本発明はさらに、少なくとも１つのコンピュータ上で、具体的には、少なくとも１つのマイクロプロセッサ上で実行することができ、かつ前述の方法を実行するためにプログラムされる、コンピュータ・プログラムに関する。

本発明の好ましい実施形態によれば、コンピュータ・プログラムは、少なくとも１つのＲＯＭ［読取り専用メモリ］、少なくとも１つのＲＡＭ［ランダム・アクセス・メモリ］、または少なくとも１つのフラッシュ・メモリに記憶されることができる。

本発明はさらに、前述のいくつかのノードをもつ分散通信システムに関し、その場合、前記通信システムは、フォールト・トレラントおよび／または時間トリガである。

本発明は最終的に、少なくともデュアル・チャネル環境内のクロックを同期させるための、前述の方法の、かつ／または前述の少なくとも１つのコンピュータ・プログラムの、かつ／または前述の少なくとも１つのノードの、かつ／または前述の通信システムの使用法であって、クロックのオフセット差およびクロックのレート差が補正されることのできる使用法に関する。

全体として、提示される機構により、シングル・チャネル通信ユニットに基づくスケーラブルなアーキテクチャ概念が可能になる。それにより、この概念によって、様々なレベルのフォールト・トレランスをもつシステム・アーキテクチャを構築することが可能になる。さらに、この概念は、製品の決定を完全に自由にする。

同じ機能ユニットは、シングル・チャネルＩＣ［集積回路］として実装されることもでき、あるいは何も機能変更せずに、冗長なデュアル・チャネルＩＣ［集積回路］に組み合わされることもできる。本発明による概念は、１チップの２つの通信コントローラを使用して互いに異なる通信クラスタに参加することを可能にする製品選択肢もサポートする。そのようなアプリケーションでは、チャネル間インターフェースは単に無効化される。各通信ユニットは、クラスタ内で単一のユニットとして独自に動作するのに十分なだけ機能する。

既に先に論じたように、本発明の教示を有利なように実施し改善する、いくつかの選択肢が存在する。この目的のために、請求項１、請求項３、および請求項５にそれぞれ従属する請求項が参照される。本発明のさらなる改良、特徴、および利点については、例として挙げられる３つの好ましい実施形態および添付の図面（図２Ａ〜図３Ｂ参照）に即して、以下により詳細に説明される。

同じ参照番号が、図２Ａ〜図３Ｂ中の対応する部分に使用される。

従来のアーキテクチャでは（図１参照）、コストを節約するために、各ノードＮごとに単にシングル通信コントローラＣＣが割り当てられて、冗長性の理由で必要な２本のチャネルＣ１、Ｃ２を扱う。それにもかかわらず、この手法は、通信コントローラＣＣ中の単一の誤りによってこのノードＮの両チャネルＣ１、Ｃ２に対するバス・アクセスが不能になるほど、誤りが生じやすい。

先行技術によるこれまでの通信コントローラＣＣは、単一のクロック同期セクションを有しており、したがってフォールト・トレラントではなかったのに対して（図１参照）、本発明では、各通信コントローラ３０、３２ごとの独立したクロック同期およびクロック補正を有する分散通信システムおよび方法について述べる（図２Ａ、図２Ｂ、および図２Ｃ参照、ただしそれぞれ、
ノード１００の第１の実施形態、
ノード１００’の第２の実施形態、および
ノード１００”の第３の実施形態
の概略図が示されている）。

先行技術によるデュアル・チャネル・ベースのアーキテクチャ（図参照１）と本発明によるシングル・チャネル・ベースのアーキテクチャ（図２Ａ、図２Ｂ、および図２Ｃ参照）におけるこの違いは、互いに異なるチャネル１０、２０のために働く通信コントローラ３０、３２のプロトコル・エンジン５０、５２が基本的に二重化され、それによって独立した装置へと構築され得るように、実装される。

この文脈では、本発明によるフォールト・トレラント時間トリガ・システムは、２本のチャネル１０、２０を含んでおり、それらにそれぞれノードが接続される。これらの各ノードは、それぞれのバス・ドライバ１２、２２、それぞれのプロトコル・エンジン５０、５２およびそれぞれのコントローラ・ホスト・インターフェース４０、４２をもつそれぞれの通信コントローラ３０、３２、オプションで各バス・ドライバ１２、２２ごとのそれぞれのバス・ガーディアン装置、ならびにアプリケーション・ホスト６０を含む。

それぞれのバス・ドライバ１２、２２は、それぞれの通信コントローラ３０、３２によって提供されるビットおよびバイトを、そのそれぞれの接続チャネル１０、２０上に送信し、今度はそれぞれのチャネル１０、２０上で受信されるそれぞれの情報を、それぞれの通信コントローラ３０、３２に提供する。

それぞれの通信コントローラ３０、３２は、そのそれぞれのバス・ドライバ１２、２２を介してそれぞれのチャネル１０、２０に接続され、該当データをホスト・アプリケーション６０に送達し、データをホスト・アプリケーション６０から受け取り、そのホスト・アプリケーションは、そのデータをフレームに組み立て、そのデータをそれぞれのバス・ドライバ１２、２２に送達する。

それぞれのバス・ドライバ１２、２２、（オプションの）バス・ガーディアン、およびホスト装置６０は、少なくとも一部、時間トリガされ、すなわち時間が、各サイクルがいくつかのセグメントを含む循環サイクルに、スライスされる。各ノードは、それ自体の組込みクロックに従って、新しいサイクルの開始を確定する。少なくとも１つのセグメントが、固定のスロット数に分割され、ここで各スロットには、最大でもせいぜい１つのそれぞれの通信コントローラ３０、３２が割り当てられ、その場合、それぞれの通信コントローラ３０、３２だけが、送信する権限を有する。そのサイクルの他のセグメントは、動的アービトレーション方式またはその他の目的に使用されることができる。

バス・ガーディアンとは、構成セットによって指定されるスロット中のみ、バス上の送信を可能にする、独立した１組の構成データをもつ装置である。

ホスト・アプリケーション６０は、データ・ソースおよびデータ・シンクを含み、一般にプロトコルのアクティビティには関わらない。それぞれの通信コントローラ３０、３２が単独で行えない判断だけが、ホスト・アプリケーション６０によって行われる。

図２Ａ〜３Ｂに示されている本発明に関して、先行技術によるデュアル・チャネル・ベースのアーキテクチャ（図１参照）でも、２本の準独立のチャネル１０、２０を扱う必要があるので、図２Ａ、２Ｂ、２Ｃのシングル・チャネル・ベースのアーキテクチャでのロジックにおける追加の労力はほとんど無視できるほどであり、すなわち一握りの機構が二重化される必要があるだけであることが、当業者には理解されよう。

より具体的には、冗長な通信チャネルは、２つの分離されたインスタンス３０、３２（図２Ｂ参照）、または単一ユニット内のオンチップ実装形態（図２Ｃ参照）を使用する、シングル・チャネル・アーキテクチャに基づくことができる。同様に、ローカル・チャネル内通信インターフェースはそれぞれ、チップ外部インターフェース５４（図２Ｂ参照）、またはオンチップ・インターフェース５６（図２Ｃ参照）である。

各ノードがサイクルの開始を独自に得、それによって、時間におけるすべてのセグメントおよびスロットの配置を得るので、ノードは、互いに同期される必要がある。各ノードは、その故障がシステム全体に障害を起こすことになる単一のマスタ・クロックに依存しないようにするために、自分のクロックを有する。同期ノード（またはシンク・ノード）と呼ばれる、それ自体のクロックとシステムのノードの何らかのサブセットのクロックとの差が、フォールト・トレラントな仕方でそれ自体のクロックを補正するために使用される。

２種類のクロック補正、すなわち、
純粋オフセット補正、および
オフセット補正とレート補正の組合せ
が可能である。

オフセット補正は単に、クロック・オフセットを補正し、一方、レート補正は、システム中のクロックの異なるレートを整合させようとも試み、それによって、クロックを互いにより近くに維持する（必要なオフセット補正量を低減させ、それによって、相互送信ギャップが小さくなるので、利用可能な帯域幅が増大する）。

レート偏差を計算するために２つの測定値が必要なので、レートおよびオフセット補正の場合、一般にクロックは、１サイクルの最後または２サイクルの最後に補正される。

すべてのシンク（同期）ノードが、自分の割当てスロットのうちの１つの中で、両チャネル１０、２０上で同時に同期フレームを送信する必要がある。したがって、すべてのノードは、同じ時間情報を受信し、１つのチャネルにのみ接続されるノードも同様である。

２つの通信コントローラ３０、３２間の同期を適用するために、各通信コントローラ３０、３２は、それ自体と、反対チャネルのその接続シングル・チャネル通信コントローラとのタイミング差によく追従する。具体的には、各シングル・チャネル通信コントローラ３０、３２は、それ自体の時間に対する時間を相互に測定し、２つの可能な方法によってオフセットおよびレート差を計算し、また、レートおよびオフセット補正のいずれにも提供される方法を使用して、たとえば、ローカル・クロックおよびチャネルに関するより多くの情報を組み込んだ数値の直接交換によって、フォールト・トレラント・パラメータが計算される。

このシステムに対する数学的命名に関しては、
ｚを１サイクルの長さとし、
Ｃをすべての通信コントローラ３０、３２のセットとし、
Ａをチャネル１０のすべての通信コントローラ３０のセットとし、
Ｂをチャネル２０のすべての通信コントローラ３２のセットとし、
Ａ_ｓをチャネル１０の同期フレームを送信するように構成されるすべての通信コントローラ３０のセットとし（Ａ_ｓ⊂Ａ）、かつ
Ｂ_ｓをチャネル２０の同期フレームを送信するように構成されるすべての通信コントローラ３２のセットとする（Ｂ_ｓ⊂Ｂ）。

図２Ａ、２Ｂ、２Ｃのシングル・チャネル・アーキテクチャでは、各通信コントローラｉ∈Ａ_ｓごとに一意の通信コントローラｊ∈Ｂ_ｓが存在し、それらはどちらも同じノードに属しているが、その逆も同様である。基本的に、これは、Ａ_ｓとＢ_ｓの間に全単射ｓが存在し、ただし、各ノードｉ∈Ａ_ｓに対して、ｓ（ｉ）∈Ｂ_ｓはｉと同じノード内のチャネル２０の通信コントローラである（また、各ノードｊ∈Ｂ_ｓに対して、ｓ^−１（ｊ）∈Ａ_ｓはｊと同じノード内のチャネル１０の通信コントローラである）ことを意味する。

ａ、ｂ∈Ｒ^＋を減衰係数とし、ａはチャネル内クロック補正用、ｂはチャネル間クロック補正用であり、ａおよびｂはオフセット補正およびレート補正のために別々に選ばれてもよい（簡略化のため、これは以下の式では反映されない）。

Ｔ_ｉ（ｔ）を通信コントローラｉ∈Ｃのサイクル時間ｔの実時間とする。それにより、Ｔ_ｉ（０）は、通信サイクル１が開始してよいとコントローラｉが考えるときの実時間になり、Ｔ_ｉ（ｚ）は、サイクル１が終了しサイクル２が開始すると通信コントローラｉが考えるときの実時間になる、などとなる。

最後に、τ_ｉをＴ_ｉ（ｔ）＝Ｔ_ｉ（０）＋τ_ｉｔとなるようなノードｉ∈Ｃのレートとする。

単純な交換に関して、まず、純粋オフセット補正用のアルゴリズムについて説明される。

各ノードは、それ自体のクロックとすべての観測可能なノードのクロックとの差を測定する。これは、ＦｌｅｘＲａｙでは、入力シンク（同期）フレームの到着時間を予想到着時間と比較することによって行われる。

ｉ∈Ａ_ｓとする。次に、各観測可能な通信コントローラｊ∈Ａ_ｓ、ｊ≠ｉに対して、通信コントローラｉは、各サイクルごとに、オフセット

を測定する。

すべてのノードｉ∈Ｂ_ｓも、同様に行う。

１サイクル内で、ある１対の通信コントローラ間のオフセット測定がいつ行われるかは、システム構成に依存し、したがってｘで表される。

Ｍ_ｉ，ｊは、測定誤差εによる誤りのある、通信コントローラｉのローカル時間で測定された最後の補正後のサイクル１内の、通信コントローラｉと通信コントローラｊのオフセット差である。

さらに、以下の測定

も行われる。

すべてのノードｉ∈Ｂ_ｓも、同様に行う。

これらは、同じノード内の他方の通信コントローラに対するオフセットである。

本発明によれば、次に、通信コントローラｉに対するオフセット補正項は、

で計算され、
ただし、ＦＴは、フォールト・トレラント・オフセット計算アルゴリズムである。そのようなアルゴリズムの例が、Ｆｒｅｄ Ｂ．Ｓｃｈｎｅｉｄｅｒの「Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｐｒｏｔｏｃｏｌｓ ｆｏｒ Ｂｙｚａｎｔｉｎｅ Ｃｌｏｃｋ Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ」、コーネル大学、ニューヨーク州Ｉｔｈａｃａ、１９８７年８月、に見つけられる。好ましい変形形態は、ＦＴＭ［フォールト・トレラント中点］アルゴリズムである。すべてのノードｉ∈Ｂ_ｓも、同様に行う。

１−１／ａ−２／ｂ≧０の場合、このアルゴリズムが機能し、両チャネル１０、２０のクロックが収束することが、証明されることができる。

ａおよびｂに対する良好な値が、

である。

特にａ＝２およびｂ＝４は、実装に極めて有利であり（除算用のＡＬＵ［演算論理装置］は必要とされず、単純なシフトで十分である）、好ましい選択である。

単純な交換に関して、次に、オフセット補正およびレート補正用のアルゴリズムについて説明される。

各ノードは、それ自体のクロックとすべての観測可能なノードのクロックとの差を測定する。これは、ＦｌｅｘＲａｙでは、入力シンク（同期）フレームの到着時間を予想到着時間と比較することによって行われる。

ｉ∈Ａ_ｓとする。次に、各観測可能な通信コントローラｊ∈Ａ_ｓ、ｊ≠ｉに対して、通信コントローラｉは、各サイクルごとに、オフセット

を測定する。

すべてのノードｉ∈Ｂ_ｓも、同様に行う。

１サイクル内で、ある１対の通信コントローラ間のオフセット測定がいつ行われるかは、システム構成に依存し、したがってｘ_ｉ，ｊで表される。

Ｍ^１ _ｉ，ｊは、測定誤差εによる誤りのある、通信コントローラｉのローカル時間で測定された最後の補正後のサイクル１内の、通信コントローラｉと通信コントローラｊのオフセット差である。Ｍ^２ _ｉ，ｊは、測定誤差εによる誤りのある、通信コントローラｉのローカル時間で測定された最後の補正後のサイクル２内の、通信コントローラｉと通信コントローラｊのオフセット差である。

さらに、以下の２つの測定

も行われる。

すべてのノードｉ∈Ｂ_ｓも、同様に行う。

これらは、同じノード内の他方の通信コントローラに対するオフセットである。

本発明によれば、次に、通信コントローラｉに対するオフセット補正項は、

で計算され、
ただし、ＦＴは、フォールト・トレラント・オフセット計算アルゴリズムである。そのようなアルゴリズムの例が、Ｆｒｅｄ Ｂ．Ｓｃｈｎｅｉｄｅｒの「Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｐｒｏｔｏｃｏｌｓ ｆｏｒ Ｂｙｚａｎｔｉｎｅ Ｃｌｏｃｋ Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ」、コーネル大学、ニューヨーク州Ｉｔｈａｃａ、１９８７年８月、に見つけられる。好ましい変形形態は、ＦＴＭ［フォールト・トレラント中点］アルゴリズムである。すべてのノードｉ∈Ｂ_ｓも、同様に行う。通信コントローラｉに対するレート補正項は、

で計算され、
ただし、ＦＴは、フォールト・トレラント・オフセット計算アルゴリズムである。そのようなアルゴリズムの例が、Ｆｒｅｄ Ｂ．Ｓｃｈｎｅｉｄｅｒの「Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｐｒｏｔｏｃｏｌｓ ｆｏｒ Ｂｙｚａｎｔｉｎｅ Ｃｌｏｃｋ Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ」、コーネル大学、ニューヨーク州Ｉｔｈａｃａ、１９８７年８月、に見つけられる。好ましい変形形態は、ＦＴＭ［フォールト・トレラント中点］アルゴリズムである。すべてのノードｉ∈Ｂ_ｓも、同様に行う。

１−１／ａ−２／ｂ≧０の場合、このアルゴリズムが機能し、両チャネル１０、２０のクロックが収束することが、証明されることができる。

ａおよびｂに対する良好な値が、

である。

特にａ＝２およびｂ＝４は、実装に極めて有利であり（除算用のＡＬＵ［演算論理装置］は必要とされず、単純なシフトで十分である）、好ましい選択である。

以下では、オフセット補正およびレート補正用のアルゴリズムの一例について提示される。

ＦＴをＦＴＭ［フォールト・トレラント中点］アルゴリズムとする。ＦＴＭは、２ｋ＋１個を超える測定値が得られた場合、最大ｋ個のＢｙｚａｎｔｉｎｅ故障を許容することができる。

ＦＴＭアルゴリズムは、許可された値をソートし、最下位ｋ個の値および最上位ｋ個の値を取り除く。ＦＴＭアルゴリズムは次に、残りの最大値および残りの最小値を選択し、両方の平均を計算する。

ノードｉのオフセット補正に関しては、上位値および下位値を取り除いた後は、
ノードＬ_ｉのオフセット差の測定値が最小値であり、かつ
ノードＨ_ｉのオフセット差の測定値が最大値である。

したがって、

ということになる。

ａ＝２およびｂ＝４では、その補正項の計算では、

ということになる。

レート補正およびＦＴＭでは、結果は同様である。

そうでない場合、図３Ａおよび図３Ｂが、２つの関連通信コントローラ３０、３２間の測定が、単純な仕方ではどのように行われるかの例を示している。

図３Ａは、第１のチャネル１０のシングル・チャネル通信コントローラ３０および第２のチャネル２０のシングル・チャネル通信コントローラ３２が、それらのクロック情報を、それぞれ１信号で、どのように交換することができるかについて示している。２つの通信コントローラ３０、３２は、それらのオフセットを測定し、それを補償するために、サイクルｃの長さを変更する（→サイクル境界ｂｏは補正なしで、それに対してサイクル境界ｂｗは補正ありであり、ｂｗとｂｏの差が正しいオフセットｃｏである）。この機構をフォールト・トレラントにするために、関数ｆが使用される。信号の伝播遅延が既知の場合、正確さを増すために補償されることができる。

図３Ｂは、第１のチャネル１０のシングル・チャネル通信コントローラ３０および第２のチャネル２０のシングル・チャネル通信コントローラ３２が、それらのクロック情報を、それぞれ１信号で、どのように交換することができるかを示している。２つの通信コントローラ３０、３２は、それらのオフセット差およびレート差を測定し、それをまたはそれらを補償するためにサイクルｃの長さを変更する（→サイクル境界ｂｏは補正なしで、それに対してサイクル境界ｂｗは補正ありであり、ｂｗとｂｏの差が正しいオフセット／正しいレートｃｏｒである）。この機構をフォールト・トレラントにするために、関数ｆおよびｇが使用される。信号の伝播遅延が既知の場合、正確さを増すために補償されることができる。

特性に関しては、前述のアルゴリズムは、迅速であり、２つの関連通信コントローラ３０、３２間に複雑な追加のインターフェースを必要としない。

１つの通信コントローラ３０（または３２）とその関連通信コントローラ３２（または３０）の時間差の測定が、通常の通信サイクルｃ中に行われることができるので、補正の計算が遅延される必要はない。しかし、実現可能な精度は、従来の手法に比べて著しく低下し得る。特に、異なるチャネル１０、２０の非シンク（同期）ノードが、潜在的に大きいクロック差の影響を受ける。

ａおよびｂは、最適な選択に固定されるのではなく、シングル・チャネル・システムとの互換性を得るために、構成可能なものとし、その場合、１の選択が最適である（第２のチャネル２０からの追加の項が組み込まれる必要はない）。

複雑な交換に関して、まず、純粋オフセット補正用のアルゴリズムについて説明される。

各ノードは、それ自体のクロックとすべての観測可能なノードのクロックとの差を測定する。これは、ＦｌｅｘＲａｙでは、入力シンク（同期）フレームの到着時間を予想到着時間と比較することによって行われる。

ｉ∈Ａ_ｓとする。次に、各観測可能な通信コントローラｊ∈Ａ_ｓ、ｊ≠ｉに対して、通信コントローラｉは、各サイクルごとに、オフセット

を測定する。

すべてのノードｉ∈Ｂ_ｓも、同様に行う。

１サイクル内で、ある１対の通信コントローラ間のオフセット測定がいつ行われるかは、システム構成に依存し、したがってｘ_ｉ，ｊで表される。

Ｍ_ｉ，ｊは、測定誤差εによる誤りのある、通信コントローラｉのローカル時間で測定された最後の補正後のサイクル１内の、通信コントローラｉと通信コントローラｊのオフセット差である。

本発明によれば、次に、各通信コントローラｉ∈Ａ_ｓに対して、次式によって以下の項

が計算され、
ただし、ＦＴは、フォールト・トレラント・オフセット計算アルゴリズムである。そのようなアルゴリズムの例が、Ｆｒｅｄ Ｂ．Ｓｃｈｎｅｉｄｅｒの「Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｐｒｏｔｏｃｏｌｓ ｆｏｒ Ｂｙｚａｎｔｉｎｅ Ｃｌｏｃｋ Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ」、コーネル大学、ニューヨーク州Ｉｔｈａｃａ、１９８７年８月、に見つけられる。好ましい変形形態は、ＦＴＭ［フォールト・トレラント中点］アルゴリズムである。すべての通信コントローラｉ∈Ｂ_ｓに対して、同じく、

が行われる。

各ノードｉ∈Ａ_ｓは次に、その補正項δ_ｉ ^{ｏｆｆｓｅｔ}をその関連通信コントローラｓ（ｉ）に送信し、今度はδ_ｓ（ｉ） ^{ｏｆｆｓｅｔ}をその関連通信コントローラｓ（ｉ）から受け取る。次に、通信コントローラｉは、そのオフセット補正項

を計算することができる。

すべてのノードｉ∈Ｂ_ｓも、同様に行う。

１−１／ａ−１／ｂ≧０かつａ＝ｂの場合、このアルゴリズムが機能し、両チャネル１０、２０のクロックが収束することが、証明されることができる。

ａおよびｂに対する良好な値が、

である。

特にａ＝２およびｂ＝２は、実装に極めて有利であり（除算用のＡＬＵ［演算論理装置］は必要とされず、単純なシフトで十分である）、好ましい選択である。

複雑な交換に関して、次に、オフセット補正およびレート補正用のアルゴリズムについて説明される。

各ノードは、それ自体のクロックとすべての観測可能なノードのクロックとの差を測定する。これは、ＦｌｅｘＲａｙでは、入力シンク（同期）フレームの到着時間を予想到着時間と比較することによって行われる。

ｉ∈Ａ_ｓとする。次に、各観測可能な通信コントローラｊ∈Ａ_ｓ、ｊ≠ｉに対して、通信コントローラｉは、各サイクルごとに、オフセット

を測定する。

すべてのノードｉ∈Ｂ_ｓも、同様に行う。

１サイクル内で、ある１対の通信コントローラ間のオフセット測定がいつ行われるかは、システム構成に依存し、したがってｘ_ｉ，ｊで表される。

Ｍ^１ _ｉ，ｊは、測定誤差εによる誤りのある、通信コントローラｉのローカル時間で測定された最後の補正後のサイクル１内の、通信コントローラｉと通信コントローラｊのオフセット差である。

Ｍ^２ _ｉ，ｊは、測定誤差εによる誤りのある、通信コントローラｉのローカル時間で測定された最後の補正後のサイクル２内の、通信コントローラｉと通信コントローラｊのオフセット差である。

本発明によれば、次に、各通信コントローラｉ∈Ａ_ｓに対して、次式によって以下の項

が計算され、
ただし、ＦＴは、フォールト・トレラント・オフセット計算アルゴリズムである。そのようなアルゴリズムの例が、Ｆｒｅｄ Ｂ．Ｓｃｈｎｅｉｄｅｒの「Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｐｒｏｔｏｃｏｌｓ ｆｏｒ Ｂｙｚａｎｔｉｎｅ Ｃｌｏｃｋ Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ」、コーネル大学、ニューヨーク州Ｉｔｈａｃａ、１９８７年８月、に見つけられる。好ましい変形形態は、ＦＴＭ［フォールト・トレラント中点］アルゴリズムである。すべての通信コントローラｉ∈Ｂ_ｓに対して、同じく、

が行われる。

各ノードｉ∈Ａ_ｓは次に、その補正項δ_ｉ ^{ｏｆｆｓｅｔ}およびδ_ｉ ^ｒａｔｅをその関連通信コントローラｓ（ｉ）に送信し、今度はδ_ｓ（ｉ） ^{ｏｆｆｓｅｔ}およびδ_ｓ（ｉ） ^ｒａｔｅをその関連通信コントローラｓ（ｉ）から受け取る。次に、通信コントローラｉは、そのオフセット補正項

およびそのレート補正項

を、計算することができる。

すべてのノードｉ∈Ｂ_ｓも、同様に行う。

１−１／ａ−１／ｂ≧０かつａ＝ｂの場合、このアルゴリズムが機能し、両チャネル１０、２０のクロックが収束することが、証明されることができる。

ａおよびｂに対する良好な値が、

である。

特にａ＝２およびｂ＝２は、実装に極めて有利であり（除算用のＡＬＵ［演算論理装置］は必要とされず、単純なシフトで十分である）、好ましい選択である。

以下では、オフセット補正およびレート補正用のアルゴリズムの一例について提示される。

ＦＴをＦＴＭ［フォールト・トレラント中点］アルゴリズムとする。ＦＴＭは、２ｋ＋１個を超える測定値が得られた場合、最大ｋ個のＢｙｚａｎｔｉｎｅ故障を許容することができる。

ＦＴＭアルゴリズムは、許可された値をソートし、最下位ｋ個の値および最上位ｋ個の値を取り除く。ＦＴＭアルゴリズムは次に、残りの最大値および残りの最小値を選択し、両方の平均を計算する。

ノードｉのオフセット補正に関しては、上位値および下位値を取り除いた後は、
ノードＬ_ｉのオフセット差の測定値が最小値であり、かつ
ノードＨ_ｉのオフセット差の測定値が最大値である。

したがって、

ということになる。

括弧内には、ｉ内で計算される必要のある項ではなく、実際に適用される項が提示されている。このアルゴリズムの挙動の分析には、この式が役に立つ。

ａ＝２およびｂ＝２では、その補正項の計算では、

ということになる。

レート補正およびＦＴＭでは、結果は同様である。

特性に関しては、前述のアルゴリズムは、かなり迅速であるが、δ値を交換するために、２つの関連通信コントローラ３０、３２間のインターフェースを必要とする。

１つの通信コントローラ３０（または３２）とその関連通信コントローラ３２（または３０）の時間差の測定が、通常の通信サイクル中に行われることができず、最初のＦＴ計算後に交換されるので、追加で必要なδ値の交換およびそれに続く追加の計算によって、補正項の計算が遅延される。

特に、その交換には、両通信コントローラ３０、３２がオフセットの影響を受けるので、いくらか時間がかかる。両通信コントローラ３０、３２は、それらの補正項の計算を、最も遅いものが終了したときに、ようやく完了することができる。これは、両通信コントローラ３０、３２が、システム起動によって保証される必要のある境界内でのみ異なる場合にだけ動作することができ、そうでない場合、クロック同期は「作動」できない。この条件が与えられた後では、クロック同期アルゴリズムは、関連コントローラ３０、３２をこれらの境界内に維持することができる。

前述のアルゴリズムは、実現可能な精度が従来のデュアル・チャネル・アーキテクチャの場合とほとんど同じである、という利点を有する。単に非シンク（同期）ノードが、わずかに高いクロック差の影響を受けるだけである。

ａおよびｂは、可能な最高の精度を実現するように、同一に選ばれる必要がある。したがって、ただ１つの構成パラメータだけが、両方に与えられるものとする。この構成パラメータは、２つの最適な選択ではなく、シングル・チャネル・システムとの互換性を得るために、さらに構成可能であるものとし、その場合、１の選択が最適である（第２のチャネル２０からの追加の項が組み込まれる必要はない）。

全体として、本発明は、異なるチャネル１０、２０上の、同じチップ上にある可能性が高い（図２Ｃ参照）が必ずしもその必要はない（図２Ｂ参照）、２つの独立したシングル・チャネル通信コントローラ３０、３２の動作を同期させて、２チャネルコントローラＣＣ（図１参照）の挙動を事実上エミュレートする新規の仕方を提案し、それにより、シングル・チャネル通信コントローラまたはデュアル・チャネル通信コントローラを生成するために使用されることのできる、費用対効果の高いＩＣ［集積回路］ブロックが作成されることが可能になる。

本発明では、通信コントローラ３０、３２が、最も重要である。バス・ドライバ１２、２２、バス・ガーディアン、およびホスト装置６０は、本発明がその文脈で使用されてもよい全技術概念を提供するために列挙されている。本発明は、それらの装置の有無によって限定または制限されない。

先行技術によるネットワーク・システムを示す概略図である。 本発明の方法に従って働く、本発明によるフォールト・トレラント時間トリガ・ネットワーク・システムの第１の実施形態を示す概略図である。 本発明の方法に従って働く、本発明によるフォールト・トレラント時間トリガ・ネットワーク・システムの第２の実施形態を示す概略図である。 本発明の方法に従って働く、本発明によるフォールト・トレラント時間トリガ・ネットワーク・システムの第３の実施形態を示す概略図である。 本発明による２つのシングル・チャネル通信コントローラ間のクロック情報交換を示す、それらのオフセットの測定およびサイクル長の変化が時間ｔの関数として示されている、概略図である。 本発明による２つのシングル・チャネル通信コントローラ間のクロック情報交換を示す、それらのオフセットおよびそれらのレート差の測定ならびにサイクル長の変化が時間ｔの関数として示されている、概略図である。

符号の説明

１００ ノード（本発明の第１の実施形態、図２Ａ参照）
１００’ ノード（本発明の第２の実施形態、図２Ｂ参照）
１００” ノード（第３の本発明の実施形態、図２Ｃ参照）
１０ 第１のチャネル
１２ 第１のチャネル１０のバス・ドライバ
２０ 第２のチャネル
２２ 第２のチャネル１２のバス・ドライバ
３０ 特に第１のチャネル１０に割り当てられた、通信コントローラ
３２ 特に第２のチャネル１２に割り当てられた、通信コントローラ
４０ 特に第１の通信コントローラ３０に割り当てられた、コントローラ・ホスト・インターフェース
４２ 特に第２の通信コントローラ３２に割り当てられた、コントローラ・ホスト・インターフェース
５０ 特に第１の通信コントローラ３０に割り当てられた、プロトコル・エンジン
５２ 特に第２の通信コントローラ３２に割り当てられた、プロトコル・エンジン
５４ ローカル・チャネル内通信外部インターフェース（本発明の第２の実施形態、図２Ｂ参照）
５６ ローカル・チャネル内通信オンチップ・インターフェース（本発明の第３の実施形態、図２Ｃ参照）
６０ アプリケーション・ホスト
Ｂ１ 第１のチャネルＣ１のバス・ドライバ（先行技術、図１参照）
Ｂ２ 第２のチャネルＣ２のバス・ドライバ（先行技術、図１参照）
Ｃ１ 第１のチャネル（先行技術、図１参照）
Ｃ２ 第２のチャネル（先行技術、図１参照）
ＣＣ 通信コントローラ（先行技術、図１参照）
ＣＩ 通信コントローラＣＣのコントローラ・ホスト・インターフェース（先行技術、図１参照）
Ｈ アプリケーション・ホスト（先行技術、図１参照）
Ｎ ノード（先行技術、図１参照）
Ｐ 通信コントローラＣＣのプロトコル・エンジン（先行技術、図１参照）
ｂｗ 補正ありのサイクル境界
ｂｏ 補正なしのサイクル境界
ｃ サイクル
ｃｏ 正しいオフセット
ｃｏｒ 正しいオフセット／正しいレート
ｆ 関数

Claims (10)

1. 複数のノードが少なくとも２本のチャネルを含む少なくとも１本の通信リンクによって相互接続される分散通信システムを動作させるための、特にそのような分散通信システム中のクロックを同期させるための方法であって、
   各チャネルがそれ自体の通信コントローラによって制御されることを特徴とする方法。
2. 前記クロックを同期させるために、前記クロックのオフセット差および前記クロックのレート差が補正されることを特徴とする、請求項１に記載の方法。
3. 少なくとも１つのコンピュータ上で、特に少なくとも１つのマイクロプロセッサ上で走ることのできるコンピュータ・プログラムであって、
   請求項１または２に記載の方法を実行するためにプログラムされることを特徴とするコンピュータ・プログラム。
4. 少なくとも１つのＲＯＭ［読取り専用メモリ］、少なくとも１つのＲＡＭ［ランダム・アクセス・メモリ］、または少なくとも１つのフラッシュ・メモリに記憶されることを特徴とする、請求項３に記載のコンピュータ・プログラム。
5. 複数のノードが少なくとも２本のチャネルを含む少なくとも１本の通信リンクによって相互接続される分散通信システムのノードであって、
   少なくとも１つの通信コントローラが各チャネルに割り当てられることを特徴とするノード。
6. 前記ノードのクロックを同期させるための手段を特徴とし、
   前記手段が、前記クロックのオフセット差および前記クロックのレート差を補正する、請求項５に記載のノード。
7. 前記通信コントローラの前記通信リンクへのアクセスを制御するための少なくとも１つのバス・ガーディアンを特徴とし、
   前記補正されたクロック信号が、前記バス・ガーディアンにとって利用可能にさせられ、前記バス・ガーディアンが、それに応じてそのクロックを適合させる、請求項５または６に記載のノード。
8. 請求項１または２に記載の前記方法、および／または
   請求項３または４に記載の前記コンピュータ・プログラム
   を実行するための手段を特徴とする、請求項５から７の少なくとも一項に記載のノード。
9. 前記通信システムが、フォールト・トレラントおよび／または時間トリガであることを特徴とする、請求項５から８の少なくとも一項に記載のいくつかのノードをもつ分散通信システム。
10. 少なくともデュアル・チャネル環境内のクロックを同期させるための、請求項１または２に記載の前記方法の、かつ／または請求項３または４に記載の少なくとも１つのコンピュータ・プログラムの、かつ／または請求項５から８の少なくとも一項に記載の少なくとも１つのノードの、かつ／または請求項９に記載の前記通信システムの使用法であって、
    前記クロックのオフセット差および前記クロックのレート差が補正されることのできる使用法。

Images