/

ISO/IEC 10164-20:1999 情報技術—オープンシステム相互接続—システム管理：時間管理機能—パート20： | ページ 8

※一部、英文及び仏文を自動翻訳した日本語訳を使用しています。

H.2 分散タイム サービス

H.2.1 時間値の取得

この節では、DTS クラークまたは DTS サーバーがリモート プロシージャ コールを実行して DTS サーバーから時間を取得する方法について説明します。図 H.4 は、クラークまたはサーバーのサーバーへのリモート プロシージャ コールを実装するメッセージの時空間図を表しています。

図 H.4 —遅延の構成要素

k = 1, 2, ...8 の時間t8は、正確に知ることのできない UTC の値に対応します。二重矢印はメッセージの送信を表し、単一の矢印はメッセージの受信を表します。

手順は、クライアントが要求を送信する準備としてクロックを読み取ることから始まります。この時点での UTC の値はt1であり、時計の読み取り値はTc ( t1 ) です。その直後に、クラークまたはクライアントとして機能するサーバーがその要求を送信します。ほとんどのシステムでは、オペレーティング システムがリクエストをネットワーク アダプタに転送し、アダプタが送信のためにキューに入れるため、リクエストの送信遅延S Cが発生します。 S Cの一部のコンポーネントは決定論的ですが (クライアントからネットワークに要求を転送する際に最小数の命令を実行する必要があります)、残りはランダムであり、その時点での他のシステムおよびネットワーク アクティビティに依存します。図 H.4 では、要求は実際には時刻t2に送信され、t csで示されるランダムな伝播遅延の後、時刻t3にサーバ オープン システムで受信されます。

サーバーが要求の到着時に行う最初のアクションは、時間を記録することです。送信と同様に、ランダムな受信遅延r Sが発生します。その結果、サーバーは、サーバーのクロックによってT C ( t4 ) として測定される時刻t4での要求の到着時刻を記録します。次に、サーバーは要求を処理し、時間t5で応答データグラムを送信します。クライアントは、時刻t8でこの応答を受け取り、タイムスタンプを押します。応答には、要求と同様の遅延、つまりS C 、t cs 、およびr Cが発生します。要求メッセージと応答メッセージの対応する遅延が等しいとは想定していません。つまり、一般的にS S ? scC t csとrc ? s ．

サーバーでの処理遅延は、図 H.4 で明示的に説明されています。遅延は小さいと予想されるかもしれませんが、そうではない場合があります。たとえば、負荷の高いサーバーでは、時間要求がすぐに処理されるのではなく、サービスのためにキューに入れられる場合があります。安全なシステムでは、サーバーは応答メッセージに署名するという時間のかかるタスクを引き受ける場合があります。

処理遅延は、/4, 75(/4) でのサーバーのクロックの値、およびその時点でのクロックの不正確さI s ( t4 ) と共に応答メッセージで返されます。これにより、サーバーが高度な適時性で要求に応答する必要がなくなります。代わりに、クライアントは、以下の計算に示すように、サーバーでの処理とスケジューリングの遅延を補うことができます。

t4でのサーバーのクロックの値は、その時点での自身のクロックの値を認識していないため、クライアントには役に立ちません。したがって、クライアントは、自身のクロックの値を知っている時点でサーバーのクロックの値を計算する必要があります。この瞬間をt1とします (ただし、 t8やその他の瞬間を選択することもできます)この計算の結果は、事実上、クライアントのクロックがT C ( t1 ) を読み取った瞬間のサーバーのクロックの読み取り値です。

サーバーに障害がないと仮定すると、クライアントは次のことを認識しています。

TS ( t4 ) - I S ( t 4 ) = t 4 = T S ( t4 ) + I S ( t 4 )

したがって、 t4の範囲は次のとおりです。

TS ( t4 ) - IS ( t4 ) - x = t1 = TS ( t4 ) + IS( t4 ) - x

(H.1)

ここで、図 H.4 からx = SC + tCS + r xは不明ですが、0 = x = t8 - t1 - w の範囲にありますt8 - t1は9)で与えられます。

t8 - t1 = ( T C ( t8 ) + r - T C ( t1 ))(1 +d C )

(H.2)

上記の式のクロック分解能 r は、クライアントのクロックの離散的な性質を説明し、係数 (1 +d C ) は期間 [ t1 、 t8 ] でのドリフトを説明します。その結果：

0 = x = ( T C ( t8 ) + r - T C ( t1 ))(1 +d C ) - w

(H.3)

式 (H.1) と (H.3) の不等式を組み合わせて、クライアントまたはクライアントとして機能するサーバーは、クロックがT C ( t1 ) を読み取ったときに、UTC が範囲内にあるとサーバーが信じていたことを確認します。

T Z ( t4 ) - I Z ( t4 ) - ( T C ( t8 ) + r - T C ( t1 ))(1 +d C ) + w = t1 = T Z ( t4 ) + S ( t4 )

(H.4)

このサーバーの時刻の推定値は、 10)の不正確な時刻として表すことができます。

サーバーの洗練された実装は、推定の不正確さを減らすために、( t1 ) に既知のすべての遅延コンポーネントを含めます。たとえば、 S Sおよびr Sの任意の既知のコンポーネントを含めることができます。ただし、 wに含まれるr Sの任意のコンポーネントでは、 tS)をその量だけ減らす必要があります。

同様に、クライアントとして機能する洗練された事務員またはサーバーは、SC, r C 、t C 、または t C Sの既知のコンポーネントを補償することによって ( t1 ) を減らすことができますC二重補償を防ぐために、サーバーは t S Cまたは t C Sの既知のコンポーネントを補償することを禁止されています。

H.2.2 正しい時刻の計算

この節では、クライアントとして機能するクラークまたはサーバーが、いくつかのサーバーまたはタイム プロバイダーから取得した時刻値から正しい時刻を計算する方法について説明します。説明は、時間値が他のサーバーから取得されたかのように表示されます。ただし、時間値が時間プロバイダー インターフェイスから取得される場合、手順は同じです。

M 時間値を取得したクライアントとして機能する事務員またはサーバーを考えてみましょう。各サーバーS j 、j = 1, 2 . . . M, クライアントとして機能する事務員またはサーバーは、( t j ) および ( j j ) を計算しました。ここで、 t jは図 H.4 の瞬間t1に対応しますが、 S jに送信された要求についてです。

すべての時間値が同じ瞬間に持続する場合にのみ、正しい時間を計算できます。したがって、最初のタスクは、これらの値をt Sで示される 1 つの同期インスタントに対応するように変換することです。 t Sの任意の選択が適切であり、唯一の要件は、クライアントのクロックT C ( t S ) として機能するクラークまたはサーバーの値がわかっていることです。 tS が現在の時間に近い場合、不正確さは最小限に抑えられます。クラークまたはクライアントとして機能するサーバーが実行するすべての計算は、tS 自体が未知であるため、 T C ( t S ) に関するものです。 S j時間値をt Sに変換するには、次の式を使用します。

(H.6)

各時間値の不正確さは、期間 [ t j , t S ] にわたる店員の時計の最大可能ドリフトを補償するために増加することに注意してください。

ここで、計算の根拠について説明する。ここでは、すべてのサーバーが正しいと仮定します。したがって、すべてのM時間間隔には UTC が含まれます。クラークまたはクライアントとして機能するサーバーが計算できる最も狭い正確な時間は、単にこれらのM時間間隔の交点です。例を図 H.5 に示します。この交点は、クライアントとして機能する事務員またはサーバーが与えられた情報 ( M時間値) から計算できる UTC を含む最小の間隔であることを指摘します。

図 H.5 —最適な正確な時間の計算

しかし、一部のサーバーに障害が発生した場合はどうなりますか?交差がないか、さらに悪いことに、交差に UTC が含まれていない可能性があります。実際のアルゴリズムは、障害のあるサーバーの可能性に対応するために、単純な交差のアイデアを装飾しています。それは次の推論によって導き出されます。

クラークまたはクライアントとして機能するサーバーが計算できる最も狭い正確な時間は、すべての正確な時間間隔の交点です。すべての正しい時間値に含まれる実線上の任意のポイントは、事務員の時計がT C ( t S ) を読み取る瞬間の UTC の真の値である可能性があります。ただし、クライアントとして機能する事務員またはサーバーは、どのサーバーが正しく、(あるとしても) 障害があるかを知りません。

最大で f 台のサーバーに障害があると仮定しましょう。この場合、少なくともM - fの時間間隔に含まれる実線上の任意の点は、すべての正しい間隔の点である可能性があり、したがって UTC である可能性があります。これは、UTC を含むことが保証されているポイントの最小セットですが、図 H.5 の例で示されているように、必ずしも単一の間隔を構成するわけではありません。時間が複数の間隔であると考えるのではなく、クライアントとして機能する事務員またはサーバーは、少なくともM - fの間隔内のすべてのポイントを含む最小の単一の間隔になるように正しい時間をとります。

最も狭い正確な時間を計算する複雑さは、最初は高く見えるかもしれません。ただし、適切なデータ構造とアルゴリズムを使用すると、シンプルで高速です。この計算をアルゴリズム的に説明します。

  • 1) M 時間値の終点をリストに並べます。リストの長さは 2M で、値はリストに と の 2 つの要素を与えるたびに .
  • 2)各終点に印を付けて、それが最小終点か最大終点かを示します。
  • 3)エンドポイントの値に従ってリストを昇順に並べ替えます。 2 つ以上のエンドポイントが同じ値をとる場合、下限に対応するエンドポイントは、リスト内の上限に対応するエンドポイントよりも前になければなりません。つまり、次の場合です。

    その後、リストで先行する必要があります。
  • 4)fの初期値を設定します。
  • 5)リストを昇順にスキャンして、少なくともM - f間隔に含まれる最初のエンドポイントを見つけます。この点は、正しい時間間隔の最小値に対応します。
  • 6)そのようなポイントが見つからない場合は、障害のあるサーバーが f 個以上あります。 f を 1 増やして、手順 5) に戻ります。最小値が見つかった場合は、 fの現在の値で続行します。
  • 7)リストを降順にスキャンして、少なくともM - f間隔に含まれる最初のエンドポイントを見つけます。この点は、正しい時間間隔の最大値に対応します。

最も狭い正確な時間間隔の最小エンドポイントと最大エンドポイントを計算することは、atime と不正確さを計算することと同じです。この計算された時間と不正確さを、それぞれCT C ( t S ) とCI C ( t S ) で表します。

H.2.3 クロックの調整

クライアントまたはサーバーとして機能するクラークまたはサーバーは、正しい時刻CT C ( t S ) と不正確なCI C ( t S ) を計算すると、計算された時刻に従ってクロックを調整します。この節では、クロックが前後にジャンプしないように調整を行う方法について説明します。

同期点t Sで、クライアントの時計として機能する店員またはサーバーがT C ( t S ) を読み取ることを思い出してください。したがって、クライアントとして機能する事務員またはサーバーは、 C ( t S ) - T C ( t S ) だけクロックを調整する必要があります。

時間は常に進むので、時計も常に進む必要があります。つまり、単調に増加します。クラークまたはクライアントとして機能するサーバーは、高速クロックを調整するためにクロックを逆に設定しないでください。クロックが遅い場合、厳密に必要というわけではありませんが、クラークまたはクライアントとして機能するサーバーがクロックを徐々に調整して、ユーザーが突然の時間のジャンプを経験しないようにすることが望ましいですが、厳密には必要ではありません。これらの要件を満たすために、クライアントとして機能するクラークまたはサーバーは、UTC に追いつくように速度を落として高速クロックを調整し、UTC に追いつくように速度を上げて低速クロックを調整します。

段階的な単調な調整が行われる手順は、クロックを構成する基礎となるハードウェアとソフトウェアによって異なります。この手順は、多くのコンピューター システムに共通するクロックの 1 つの特定の実現について説明します。クロックの他の実現では、障害のないクロックが常にその間隔に UTC を含むことを保証する限り、異なる手順を使用できます。

クロックは、UTC の現在の測定値を含むメモリと、定期的にプロセッサに割り込むハードウェア タイマーで構成されます。通常、これらのティック割り込みを処理するルーチンは、クロックのメモリを解像度 r だけインクリメントし、メモリの内容を (ほぼ) UTC と同じレートで増加させます。

クロックを調整するために、クライアントとして機能するクラークまたはサーバーは、 CCでSが増加する量をSします。それ以外の場合は、それを減らします。公称ティック増分 ? の量を示します。によって調整されます。クライアントとして機能する事務員またはサーバーがティックの増分を ? + e ティックの数、例えば n. e が正の場合、時計は ne 秒進みますが、負の場合、時計はその量を失います。したがって、 CT C ( t S ) - T C ( t S ) を得るために、クライアントとして機能するクラークまたはサーバーは、次のようにティックの増分を e だけ変更します。

N = ( CT C ( t S ) - T C ( t S ))/ e

(H.7)

ティック( CT C ( t S ) - T C ( t S ) < 0 の場合、e は負であり、クロックは増加するのではなく失われます。)

e の値は、実装では定数です。ただし、仕様には 2 つの制限があります。クロックが単調であることを保証するには、e は -? 以上でなければなりません。また、調整によってドリフトが補正されるため、調整率はドリフトよりも大きくなければなりません。 e | > ?すなわちさらに、| e | ? に比べて小さい場合、ユーザーは調整を認識したとしてもほとんど認識しません。

H.2.4 最大誤差の決定

時計の認識は、時間のように不正確さを自動的に測定するわけではありません。代わりに、店員またはサーバーは、時計が読み取られるたびに不正確さを計算します。この節では、その計算を行うための式を示します。

時計の不正確さは、次の 4 つの要素で構成されます。

ベースの不正確さで与えられる同期点 tS での不正確さ
I C ( t S ) = CI C ( t S ) + | CT C ( t S ) - T C ( t S ) |.
ドリフト増加これは、ドリフトによって増加したベースの不正確さの最大値です。時刻 t でのドリフト
増加は ( T C ( t ) - T C ( t S )) d Cです。
調整減額クロックを調整することによって不正確さが減少する量。すべてのための
クロックが e によって調整される目盛り、不正確さは | によって減少します。 e |。予測
調整は同期点t Sで開始され、調整の減少は | (( T C ( t ) -
T C ( t S )) e)/ (? + e) || | の合計を超えないN |。
クロック分解能解像度 r は、UTC の量を反映するために不正確さに含まれています。
およびクロックは、2 つの連続するティックの間で発散します。ドリフトを考慮してスケーリングされます。

これらの 4 つのコンポーネントを組み合わせると、 t S後の任意の時点での不正確さを計算する式が次のように得られます。

I C ( t ) = CI C ( t S ) + | CT C ( t S ) - T C ( t S ) | + ( C ( t ) - C ( S )) C - 最小{( C ( t ) - C ( S ))/ (? + e), N} | e | + (1 + d C )?

(H.8)

ここで、 Nは式 H.7 で与えられます。実装によって解像度の寄与を 0.5(1 = d C ) に減らすことができることに注意してください。クロックによって報告された時間が 0.5 (1 = d C ) 増加すると?実際の値を超えています。

前のリストの調整減少の式で要求されるように、調整の開始を正確にtにスケジュールすることはできない場合があることに注意してください。この場合、不正確さを計算する式では、同期の瞬間と調整が実際に始まる瞬間との間のティック数を考慮する必要があります。ここで、これを行う 1 つの方法を示します。

調整が始まる瞬間を基準時間t bと呼びます。時計はこの時点でT ( t b ) を読み取ります。 t bでの不正確さ (ベースの不正確さと呼びます) は、 tでの不正確さであり、時間ttot bへのドリフトを説明するために増加されます。それで：

I C ( t b ) = CI C ( t S ) + | CT C ( S ) - TC ( ts ) | + ( T C ( t b ) - T C ( t S )) d C

(この式では、高次の項は無視されます。) ベースの不正確性にはt Stot bへのドリフトが含まれているため、ドリフトの増加にはそれ以降のドリフトを含めるだけで済みます。したがって、時間tでは、( T C ( t ) - T C ( t b )) d Cで与えられます。

調整の減少は、 t bで調整が開始されている限り、調整が開始されてから経過したティック数を測定することによって計算されます。したがって、それは | で与えられます。 ( T C ( t ) - T C ( t b )) e)/(?+ e) |しかし、それでも | の合計以下です。 N e |.したがって、式 H.8 は、次のように、より一般的な用語で表すことができます。

I C ( t ) = CI C ( t S ) + | CT C ( t S ) − T C ( t S ) | + ( C ( t b ) - C ( t S )) d C + ( C ( t ) - C ( t b )) d C - 最小{( C ( t ) - C ( t b ))/ (? + e）、 N} |え | + (1 + d C )?

H.2.5 ローカル障害

定期的な同期にもかかわらず、システムのエラー (一時的または永続的) により、そのシステムのクロックが故障する可能性があります。クロックの間隔を計算された間隔と比較することにより、同期時に異常なクロックを検出できます。交差しない場合は、ローカル クロックに障害があります。

クロックを調整して不正確さを計算するための通常のメカニズムは、障害のあるクロックを修正します。ただし、クロックの誤差が大きい場合 (たとえば、数日)、クロックを徐々に調整して誤差を修正することは望ましくない場合があります。代わりに、クロックを計算された時間に設定する方が望ましい場合があります。

これを容易にするために、障害のあるクロックを正しい時刻に設定するか、単調に調整するかを制御する管理属性があります。このパラメーターはerrorToleranceと呼ばれます。その間隔と計算された間隔の間の分離がerror Toleranceよりも大きい場合、単調に調整されるのではなく、障害のあるクロックが設定されます。これを定量的に表すと次のようになります。

| | CT C ( t S ) − T C ( t S ) | - CI C ( t S ) - I C ( t S )) = errorTolerance

このように障害のあるクロックの許容誤差を指定することで、境界条件に簡単に対応できます。つまり、障害のあるクロックをリセットしない ( errorTolerance = ∞) か、障害のあるクロックをすぐにリセットする ( errorTolerance = 0)

H.2.6 構成

事務員が各同期中に時間を要求するサーバーの数は、minServers と呼ばれる管理属性によって決定されます。すべての店員のニーズを満たすのに十分な数のサーバーが存在するように、タイム サービスを構成する必要があります。さらに、サーバーは、時間を提供する店員の近くに配置することが望ましいです。これにより、不正確さの原因となる通信遅延が最小限に抑えられます。

スモール セルは、すべてのクラークにサービスを提供する 1 セットのサーバーでこれらの基準を満たすことができますが、ラージ セルは、1 つのクラークに必要な数よりも多くのサーバーで構成する必要があります。その結果、アーキテクチャはサーバーをセットに分割し、各セットは事務員のサブセットにサービスを提供します。

管理パーティショニングを簡素化するために、ほとんどのシステムが LAN に接続されているという前提を利用しています。各 LAN には、ローカル セットと呼ばれる (場合によっては空の) サーバーのセットが含まれています。通常、ローカル セットには、そのセットの LAN 上のすべての事務員のニーズを満たすのに十分な数のサーバーがあります。この場合、クラークはそれぞれのローカル セット内のサーバーから時刻を取得します。これらのサーバーは、C.3.2 で説明されているアルゴリズムを使用して、RPC サービス プロファイルを通じて検出されます。

このアルゴリズムにより、タイム サービス ローカル セットの自動構成が可能になります。

この配置はローカル セットの構成に適していますが、次の 2 つの欠点があります。

  • 1)ローカル セット内のどのサーバーにもタイム プロバイダーがない場合、オペレータはこのセット内の fservers で定期的に時刻をリセットする必要があります。
  • 2)ローカル セットに含まれるサーバーが不十分なクラークには、追加のサーバーを検出するメカニズムがありません。

これらの欠点を克服するために、セル全体で使用できる追加のサーバー セットを提供します。このセットをグローバル セットと呼び、このセットのサーバーをグローバル サーバーと呼びます。グローバル サーバーは通常、何らかのローカル セットのメンバーですが、これは必須ではありません。

クラークは、同期に必要な数よりもローカル セット内のサーバーが少ない場合にのみ、グローバル サーバーにアクセスします。タイム プロバイダがなく、次の 2 つの条件のいずれかが当てはまる場合、サーバーはグローバル サーバーにアクセスします。

  • 1)ローカル セット内のサーバーの数が、同期に必要な数よりも少ない。
  • 2)サーバーは宅配業者です。

クーリエは、グローバル セットからローカル セットに時間をインポートするサーバーです。これは、ローカル セット内のどのサーバーにもタイム プロバイダーがなく、グローバル セット内の一部のサーバーにタイム プロバイダーがある場合に役立ちます。 C.3.4 で説明されているように、サーバーが宅配便になるメカニズム。

グローバル サーバーは明示的に相互に同期しないことに注意してください。グローバル サーバーが別のグローバル サーバーと同期するのは、2 つのグローバル サーバーが異なるローカル セットにあり、最初のグローバル サーバーにタイム プロバイダーがない場合のみです。

H.2.7 クーリエ

一部のローカル セットは、タイム プロバイダーを持つサーバーなしで構成される可能性があります。この構成では、オペレータは定期的にタイム プロバイダを模倣して、そのようなローカル セットの不正確さが過度に大きくなるのを防ぐ必要があります。

ただし、ローカル セット内のサーバーが正確な時刻を取得できるタイム プロバイダーに近接しているセル内に、いくつかのグローバル サーバーが存在する場合があります。このアーキテクチャは、グローバル サーバーにかかる負荷を制限し、フォールト トレランスの低下を犠牲にして管理を容易にする設計により、このためのメカニズムを提供します。このメカニズムでは、タイム プロバイダーのないすべてのサーバーではなく、クーリエとして指定されたサーバーのみがグローバル サーバーと同期します。

サーバーは、選択メカニズムと、courier, non-courier, または backup-courier の 3 つの値のいずれかを取る courierRole と呼ばれる属性の組み合わせによってクーリエになります。 courierRole が non-courier に設定されたサーバーは決してクーリエにはなりません。 courierRole が courier に設定されているものは常にクーリエです。 courierRole が backupcourier に設定されたサーバーは、一般にクーリエではありませんが、次の場合はクーリエになります。

  • 1) courierRole が courier に設定されたローカル セットにサーバーがありません。
  • 2)セキュリティ UUID (サーバーのセキュリティ プリンシパルに関連付けられた UUID) が他のサーバーより優先され、courierRole が backup-courier に設定されているサーバーです。

サーバーは、タイム リクエスト RPC でクーリエ ロールの値を交換します。 courierRole が backup-courier に設定されているサーバーは、ローカルサーバーのリストにエントリを追加または削除するたびに、クーリエであるかどうかを判断する必要があります。

H.2.8 次の同期の決定

事務員は、不正確さを制限しようとすることで、クロックを同期するタイミングを決定します。不正確さの望ましい境界は、管理属性 maxInacc によって指定されます。計算された時間と不正確さCT C ( t S ) およびCI C ( t S ) から、事務員はその不正確さが maxInacc の値に達する時間を計算できます。これは次の式で与えられます。

T = CT C ( t S ) + (maxInacc - CI C ( t S ))/ d C

I C ( t ) < maxInacc を維持するために、クラークは、クロックがこの時刻を読み取る前に同期する必要があります。

タイム サービスは、 CI C ( t S ) の境界を保証しないことに注意してください。したがって、maxInacc CI C ( t S ) が小さいか、負の値でさえある可能性があります。クラークが継続的に同期するのを防ぐために、同期間の時間が、管理属性 syncHold で指定された最小値よりも大きい必要があります。

残念ながら、前の段落で説明したアプローチを使用すると、すべてのクラークが同期する同じ瞬間を選択し、ネットワークとサーバーにバースト負荷が発生する可能性があります。これらを回避するために、クラークが同期する時間にランダム性が導入されます。

次の手順では、計算された時間と maxInacc および syncHold の 2 つのパラメーターに基づいて、次の同期をスケジュールする方法について説明します。

  • 1)不正確さが maxInacc に達するまでの時間を計算します。これは次の式で与えられます。

    D = (maxInacc - CI C ( t S ))/ d C

  • 2) D がsyncHoldの場合は、手順 4) に進みます。そうでない場合は、次のステップに進みます。
  • 3) [ D/2, D ] に一様に分布する乱数 R を描画します。手順 5) に進みます。
  • 4) [(3 syncHold )/4, (5 syncHold )]/4] に均一に分布する乱数 R を描画します。
  • 5)クロックがCT C ( t S ) + Rを読み取る前に完了できるように、次の同期をスケジュールします。

H.2.9 サーバーリストの維持

新しいローカル サーバーを知るために、担当者はローカル セットの RPC インポートを定期的に実行する必要があります。新しいグローバル サーバーを知るために、グローバル サーバーを使用している事務員は、グローバル セットの RPC インポートを定期的に実行する必要があります。

クラークがこれらのインポートを強制的に実行するメカニズムは、グローバル サーバーとローカル サーバーのリスト全体を定期的にフラッシュするためです。 C.4.2 の同期手順からわかるように、これによりクラークはローカル セットをインポートし、必要に応じて次回の同期時にグローバル セットをインポートします。

フラッシングは定期的に行われます。フラッシュの間隔は、管理属性 cacheRefresh によって指定されます。

サーバーがタイム プロバイダーと同期している場合、サーバーはタイム プロバイダーによって指定された時刻に次の同期をスケジュールします。 (Time Provider インターフェイスの ContactProvider 関数の呼び出しによって返される TPctlMsg の nextPoll フィールド。)

サーバーが他のサーバーと同期した場合、またはサーバーが少なすぎるために同期を中止した場合は、C.4.3 で指定されているようにクラークが行うのと同じ方法で次の同期を決定します。

H.2.10 障害のあるサーバーのチェック

障害のあるサーバーをタイムリーに検出して報告するには、サーバーはローカル セット内の他のすべてのサーバーから定期的に時間を取得し、それらの間隔が交差していることを確認する必要があります。

この手順は、C.5.3.2 で説明されているように、他のサーバーとの同期に使用されるものですが、次の変更があります。

  • グローバル サーバーは照会されません。
  • minServers -1 未満のクエリが実行された場合、手順は中止されません。
  • 時刻を合わせる（または設定する）手順は実行されません。
  • 次の同期をスケジュールする手順は実行されません。

障害のあるサーバーのチェックは、管理属性 checklnt で指定された平均期間の定期タイマーによって開始されます。初期化後、チェック手順の完了後、[(3checkInt)/4, (5checkInt)/4] の範囲で乱数を描画することによってタイマーが設定されます。

注 —サーバーが他のサーバーと同期するときにもチェックが行われるため、タイマーは [(3 checkInt )/4, (5 checkInt )/4] の範囲の乱数の値で再起動されます。

H.2 Distributed Time service

H.2.1 Obtaining a time value

This subclause describes how a DTS clerk or DTS server obtains time from some DTS server by performing a remote procedure call. Figure H.4 represents a time-space diagram of the messages that implement the clerk or server's remote procedure call to the server.

Figure H.4—Components of Delay

The times t8 where k = 1, 2, ...8, correspond to values of UTC, which can never be known exactly. A double arrow denotes a message transmission and a single arrow denotes a message reception.

The procedure begins with the client reading its clock in preparation for sending the request. The value of UTC at this instant is t1 and the clock reads Tc(t1). Immediately thereafter, the clerk or server acting as client sends its request. In most systems, the request incurs some sending delay SC as the operating system transfers it to the network adapter and as the adapter queues it for transmission. Although some component of SC is deterministic (some minimum number of instructions must be executed in transferring the request from the client to the network), the remainder is random, depending on other system and network activities at that time. In Figure H.4, the request is actually transmitted at time t2 and received at the server open system at time t3 after a random propagation delay denoted by tcs.

The first action the server takes upon the arrival of a request is to note the time. As with sending, some random receiving delay rS is incurred. Consequently, the server notes the arrival time of the request at time t4, which is measured as TC (t4) by the server's clock. The server then processes the request and sends a response datagram at time t5. The client receives and time stamps this response at time t8. The response incurs similar delays to those of the request, namely SC , t cs , and rC . We do not assume that the corresponding delays of the request and response messages are equal. That is, in general, SS ? tSC t sc , ? t cs and rc ? rs .

The processing delay at the server is explicitly accounted for in Figure H.4. Although you might expect the delay to be small, this may not be the case. For example, at a highly loaded server, a time request may be queued for service rather than processed immediately; in a secure system, a server may undertake the time-consuming task of signing the response message.

The processing delay is returned in the response message together with the value of the server's clock at/4, 75(/4), and the clock's inaccuracy at that instant, Is (t4). This eliminates any need for servers to respond to requests with a high degree of timeliness. Instead, the client can compensate for processing and scheduling delays at the server as shown in the arithmetic below.

The value of the server's clock at t4 is not useful to the client as it does not know the value of its own clock at that instant. So, the client must calculate the value of the server's clock at an instant for which it does know the value of its own clock. Let this instant be t1 (however, we could equally have chosen t8 or any other instant). The result of this calculation is effectively the reading of the server's clock at the instant when the client's clock read TC (t1).

Assuming the server is non-faulty, the client knows that:

TS (t4) - IS (t4) = t4 = TS (t4) + IS (t4)

Therefore, t4 is in the range:

TS (t4) - IS (t4) - x = t1 = TS (t4) + IS(t4) - x

(H.1)

where, from Figure H.4 x = SC + tCS + rS. Although x is unknown, it is in the range 0 = x = t8 - t1 - w. Now, t8 - t1 isgiven by 9):

t8 - t1 = (TC (t8) + r - TC (t1))(1 +d C )

(H.2)

The clock resolution r, in the formula above, accounts for the discrete nature of the client?s clock and the factor (1 +d C )accounts for its drift over the period [t1, t8]. Consequently:

0 = x = (TC (t8) + r - TC (t1))(1 +d C ) - w

(H.3)

Combining the inequalities of equations (H.1) and (H.3), the client or server acting as client ascertains that, when itsclock read TC (t1), the server believed that UTC was in the range:

TZ (t4) - IZ (t4) - (TC (t8) + r -TC (t1))(1 +d C ) + w = t1 = TZ (t4) + IS (t4)

(H.4)

This estimate of the server?s clock at time can be represented as a time with inaccuracy by 10):

A sophisticated implementation of a server would include all known components of delay in (t1) so as to reduce theestimated inaccuracy. For example, it could include any known components of SS and rS ; but any component of rS included in w requires that TS (t4) be decremented by that amount.

Similarly, a sophisticated clerk or server acting as client could reduce (t1) by compensating for known componentsof SC , rC , tSC , or tCS . To prevent double compensation, servers are prohibited from compensating for knowncomponents of tSC or tCS .

H.2.2 Computing a correct time

This subclause describes how a clerk or server acting as client computes a correct time from time values obtained from several servers or from the time provider, even if some are faulty. The description is presented as if the time values were obtained from other servers. However, the procedure is the same if the time values are obtained from the time provider interface.

Consider a clerk or server acting as client which has obtained M time values. For each server Sj with j = 1, 2 . . . M, theclerk or server acting as client has computed (tj ) and (tj ) where tj corresponds to the instant t1 in Figure H.4but for the request sent to Sj .

Calculating a correct time is feasible only if all the time values pertain to the same instant. So the first task is to translatethese values to correspond to one synchronization instant, which is denoted by tS . Any choice of tS is adequate, the onlyrequirement being that the value of the clerk or server acting as client?s clock TC (tS ) is known. Least inaccuracy isachieved if tS is close to the current time. All calculations that the clerk or server acting as client performs are in terms ofTC (tS ) since tS itself is never known. Translating the Sj time value to tS is achieved by the following equations:

(H.6)

Note that the inaccuracy of each time value increases to compensate for the maximum possible drift of the clerk?s clockover the period [tj , tS ].

The basis of the calculation is now described. Assume for now that all servers are correct. Therefore, all the M timeintervals contain UTC. The narrowest correct time that the clerk or server acting as client can compute is simply theintersection of these M time intervals. An example is shown in Figure H.5. We point out that this intersection is thesmallest interval containing UTC that the clerk or server acting as client could possibly compute from the giveninformation (the M time values).

Figure H.5—Computing the best correct time

But what if some servers are faulty? There may be no intersection or, even worse, the intersection may not contain UTC.The actual algorithm embellishes the idea of a simple intersection to accommodate the possibility of faulty servers. It isarrived at by the following reasoning.

The narrowest correct time that the clerk or server acting as client could possibly compute is the intersection of all thecorrect time intervals; any point on the real line contained in all the correct time values could potentially be the truevalue of UTC at the instant when the clerk?s clock reads TC (tS ). However, the clerk or server acting as client does notknow which servers are correct and which (if any) are faulty.

Let us assume that at most f servers are faulty. In this case, any point on the real line contained in at least M - f of thetime intervals could be a point in all the correct intervals, and hence could be UTC. While this is the smallest set ofpoints guaranteed to contain UTC, it does not necessarily constitute a single interval as shown by the example inFigure H.5. Rather than considering the time to be multiple intervals, the clerk or server acting as client takes the correcttime to be the smallest single interval containing all points in at least M - f of the intervals.

The complexity of computing the narrowest correct time may at first appear to be high. However, it is simple and fastwith a suitable data structure and algorithm. We now describe this computation algorithmically:

  • 1) Arrange the endpoints of the M time values into a list. The list is of length 2M as each time valuecontributes two elements to the list: and .
  • 2) Mark each end point to indicate if it is a minimum or maximum endpoint.
  • 3) Sort the list according to the values of the endpoints in ascending order. In the case where two or moreendpoints take on the same value, those corresponding to lower bounds must precede those correspondingto upper bounds in the list; that is, if:

    then must precede in the list.
  • 4) Set the initial value of f.
  • 5) Scan the list in ascending order to find the first endpoint that is contained in at least M - f intervals. Thispoint corresponds to the minimum value of the correct time interval.
  • 6) If no such point is found, then there are more than f faulty servers. Increase f by one and go back tostep 5). If a minimum value has been found, then continue with the current value of f.
  • 7) Scan the list in descending order to find the first endpoint that is contained in at least M - f intervals. Thispoint corresponds to the maximum value of the correct time interval.

Computing the minimum and maximum endpoints of the narrowest correct time interval is equivalent to computing atime and inaccuracy. We denote this computed time and inaccuracy by CTC (tS ) and CIC (tS ), respectively.

H.2.3 Adjusting the clock

Once a clerk or server acting as client or server has computed a correct time CTC (tS ) and inaccuracy CIC (tS ), it adjustsits clock in accordance with the computed time. This subclause describes how that adjustment is made so that the clocknever jumps forward or backward.

Recall that, at the synchronization point tS , the clerk or server acting as client?s clock reads TC (tS ). Consequently, theclerk or server acting as client must adjust the clock by CTC (tS ) - TC (tS ).

Since time always advances, the clock too must always advance; that is, increase monotonically. A clerk or server actingas client should not set its clock backward to adjust a fast clock. When the clock is slow, it is desirable, but not strictlynecessary, for the clerk or server acting as client to adjust the clock gradually so that users do not experience a suddenforward jump in the time. To satisfy these requirements, a clerk or server acting as client adjusts a fast clock by slowingit down so that UTC catches up, and a slow clock by speeding it up so that it catches up to UTC.

The procedure by which gradual monotonic adjustments are made depends on the underlying hardware and softwareconstituting the clock. We describe this procedure for one particular realization of a clock, one common to manycomputer systems. Other realizations of clocks may use different procedures as long as they guarantee that a non-faultyclock always contains UTC in its interval.

A clock consists of memory containing its current measure of UTC and a hardware timer that periodically interrupts theprocessor. Normally, the routine servicing these tick interrupts increments the clock?s memory by the resolution r,causing the contents of the memory to increase at (approximately) the same rate as UTC.

To adjust the clock, the clerk or server acting as client changes the amount by which the clock increments at each tick,increasing the amount if CTC (tS ) = TC (tS ); otherwise, decreasing it. We denote the amount by which the nominal tickincrement ? is adjusted by e. Suppose that the clerk or server acting as client increases the tick increment to ? + e forsome number of ticks, say n. If e is positive, the clock gains ne seconds, while if it is negative, the clock loses thatamount. So to gain CTC (tS ) - TC (tS ), the clerk or server acting as client modifies the tick increment by e for:

N = (CTC (tS ) -TC (tS ))/ e

(H.7)

ticks. (If CTC (tS ) - TC (tS ) < 0, then e is negative and the clock loses rather than gains.)

The value of e is an implementation constant. However, the specification imposes two restrictions: to ensure that theclock is monotonic, e must be greater than or equal to -?; and, because the adjustment compensates for drift, theadjustment rate must be greater than the drift, or | e | > ? d. If, in addition, | e | is small compared with ?, users will barelyperceive the adjustment, if at all.

H.2.4 Determining the maximum error

Our realization of the clock does not automatically measure inaccuracy as it does time. Instead, the clerk or servercalculates the inaccuracy whenever the clock is read. This subclause presents the formula for making that calculation.

The inaccuracy of a clock consists of four components:

Base inaccuracyThe inaccuracy at the synchronization point tS, which is given by
IC (tS ) = CIC (tS ) + | CTC (tS ) - TC (tS ) |.
Drift increaseThis is the most the base inaccuracy has increased due to drift. At time t, the drift
increase is (TC (t) - TC (tS )) d C .
Adjustment decreaseThe amount by which the inaccuracy is decreased by adjusting the clock. For every
tick for which the clock is adjusted by e, inaccuracy is decreased by | e |. Assuming
adjustment begins at synchronization point tS , the adjustment decrease is | ((TC (t) -
TC (tS )) e)/ (? + e) | but no more than the total of | Ne |.
Clock resolutionThe resolution r is included in the inaccuracy to reflect the amount by which UTC
and the clock diverge between two consecutive ticks. It is scaled to account for drift.

Combining these four components gives the formula for calculating the inaccuracy at any time after tS as:

IC (t) = CIC (tS ) + | CTC (tS ) - TC (tS ) | + (TC (t) - TC (tS )) d C - min{(TC (t) - TC (tS ))/ (? + e), N} | e | + (1 + dC)?

(H.8)

where N is given by equation H.7. Note that implementations can reduce the contribution of resolution to0.5(1 = d C )? if the time reported by the clock is increased by 0.5(1 = d C )? over its actual value.

We note that it may not be possible to schedule the beginning of the adjustment at precisely t as required by the formulafor adjustment decrease in the preceding list. If this is the case, the formula for calculating the inaccuracy must take intoaccount the number of ticks between the synchronization instant and the instant at which adjustment actually begins. Wenow show one way to do this.

Call the instant at which adjustment begins the base time tb . The clock reads T(tb ) at this instant. The inaccuracy at tb ,which we call the base inaccuracy, is the inaccuracy at t, increased to account for the drift over the time ttotb . So:

IC (tb ) = CIC (tS ) + | CTC (tS ) - TC (ts) | + (TC (tb ) - TC (tS )) d C

(Higher-order terms are ignored in this equation.) As the base inaccuracy now includes drift from tStotb , the driftincrease need only include drift thereafter. So at time t, it is given by (TC (t) - TC (tb )) d C .

The adjustment decrease is calculated by measuring the number of ticks that have elapsed since adjustment began aslong as adjustment began at tb . So, it is given by | (TC (t) - TC (tb )) e)/(?+ e) | but still no more than the total of | N e |.Thus, equation H.8 can be expressed in more general terms by:

IC (t) = CIC (tS ) + | CTC (tS ) - TC (tS ) | + (TC (tb ) - TC (tS )) d C + (TC (t) - TC (tb )) d C - min{(TC (t) - TC (tb ))/ (? + e), N} | e | + (1 + d C )?

H.2.5 Local faults

Despite periodic synchronization, an error (either transient or permanent) on a system can cause the clock on that systemto become faulty. A faulty clock can be detected at synchronization by comparing the interval of the clock to thecomputed interval. If they do not intersect, the local clock is faulty.

The usual mechanism for adjusting the clock and computing the inaccuracy will correct a faulty clock. However, if theamount by which the clock is in error is large (say, several days), it may be undesirable to adjust the clock gradually tocorrect the error; instead, it may be preferable to set the clock to the computed time.

To facilitate this, there is a management attribute to control whether a faulty clock is set to the correct time or adjustedmonotonically. This parameter is called errorTolerance. A faulty clock is set rather than monotonically adjusted if theseparation between its interval and the computed interval is greater than errorTolerance. This is expressed quantitativelyby the following:

| CTC (tS ) - TC (tS ) | -CIC (tS ) - IC (tS )) = errorTolerance

By specifying the error tolerance of a faulty clock in this way, it is easy to accommodate the boundary conditions;namely, to never reset a faulty clock (errorTolerance = ∞) or, to immediately reset a faulty clock (errorTolerance = 0).

H.2.6 Configuration

The number of servers from which a clerk requests the time during each synchronization is determined by a managementattribute called minServers. The Time Service must be configured so that there are enough servers to satisfy the needs ofevery clerk. In addition, it is desirable for servers to be located close to the clerks to which they provide the time. Thisminimizes communication delay that contributes to inaccuracy.

While small cells can satisfy these criteria with a single set of servers serving all clerks, large cells must be configuredwith many more servers than required for any one clerk. Consequently, the architecture partitions servers into sets witheach set serving a subset of clerks.

To simplify management partitioning, we exploit the assumption that most systems are connected to LANs. Each LANcontains a (possibly empty) set of servers called the local set. Normally, there are sufficient servers in a local set tosatisfy the needs of all clerks on the LAN of that set. If this is the case, clerks obtain the time from servers in theirrespective local sets. They discover these servers through RPC service profiles using the algorithm described in C.3.2.

This algorithm makes it possible to autoconfigure the Time Service local sets.

While this arrangement is well suited for configuring local sets, it suffers two shortcomings:

  • 1) If none of the servers in a local set have a time provider, an operator must periodically reset the time at fservers in this set.
  • 2) Clerks whose local sets contain insufficient servers have no mechanism to discover additional servers.

To overcome these shortcomings, we provide an additional set of servers that are available throughout the cell. We callthis set the global set and the servers of this set we call global servers. A global server is usually a member of some localset, but this is not required.

A clerk accesses global servers only if there are fewer servers in its local set than the number it requires forsynchronization. A server accesses global servers if it does not have a time provider and either of the following twoconditions holds:

  • 1) There are fewer servers in the local set than the number it requires for synchronization.
  • 2) The server is a courier.

Couriers are servers that import time from the global set into the local set. This is useful when none of the servers in thelocal set have time providers but some servers in the global set do. The mechanism by which a server becomes a courieris described in C.3.4.

Note that global servers do not synchronize with each other explicitly. A global server synchronizes with another globalserver only if the two are in different local sets and the first does not have a time provider.

H.2.7 Couriers

It is likely that some local sets will be configured without any servers that have time providers. With this configuration,an operator must periodically mimic a time provider to prevent inaccuracies in such a local set from becomingexcessively large.

However, there may be some global servers in the cell with close proximity to time providers from which the servers in alocal set could obtain accurate time. The architecture provides a mechanism for this with a design that limits the loadplaced on global servers and is easy to manage at the expense of reduced fault tolerance. With this mechanism, onlythose servers designated as couriers synchronize with global servers rather than all servers without time providers.

A server becomes a courier by a combination of an election mechanism and an attribute called courierRole which takesone of the three values: courier, non-courier, or backup-courier. A server with courierRole set to non-courier neverbecomes a courier; one with courierRole set to courier is always a courier; a server with courierRole set to backupcourieris, in general, not a courier but becomes one if:

  • 1) There are no servers in the local set with courierRole set to courier .
  • 2) It is the server whose security UUID (the UUID associated with the server?s security principal) precedesall others with courierRole set to backup-courier.

Servers exchange their courierRole values in time request RPCs. Servers with courierRole set to backup-courier mustredetermine whether or not they are couriers whenever they add an entry to, or remove one from, their lists of localservers.

H.2.8 Determining the next synchronization

A clerk determines when to synchronize its clock by attempting to bound its inaccuracy. The desired bound on theinaccuracy is specified by the management attribute maxInacc.From the computed time and inaccuracyCTC (tS ) and CIC (tS ), the clerk can calculate the time at which its inaccuracywill reach the value of maxInacc. This is given by:

T =CTC (tS ) + (maxInacc -CIC (tS ))/d C

To keep IC (t) < maxInacc, the clerk must synchronize before its clock reads this time.

Note that the Time Service does not guarantee any bound on CIC (tS ). Consequently, it is possible that maxInacc CIC (tS )is small or even negative. To prevent a clerk from synchronizing continuously, we require that the time betweensynchronizations be more than a minimum value which is specified by the management attribute syncHold.

Unfortunately there are likely conditions where, using the approach described in the previous paragraph, all clerks willchoose the same instant at which to synchronize, causing bursty loads on the network and servers. To avoid these, somerandomness is introduced into the times at which clerks synchronize.

The following steps describe how to schedule the next synchronization based on the computed time and the twoparameters maxInacc and syncHold:

  • 1) Compute the time for the inaccuracy to grow to maxInacc. This is given by the following:

    D = (maxInacc - CIC (tS ))/d C

  • 2) If D s syncHold, go to step 4). Otherwise, continue with the next step.
  • 3) Draw a random number, R, uniformly distributed over [D/2, D]. Go to step 5).
  • 4) Draw a random number, R, uniformly distributed over [(3syncHold)/4, (5syncHold)]/4]
  • 5) Schedule the next synchronization so that it can complete before the clock readsCTC (tS ) + R.

H.2.9 Maintaining the server lists

To learn of new local servers, clerks must periodically perform an RPC import of the local set. To learn of new globalservers, those clerks using global servers must periodically perform RPC imports of the global set.

The mechanism by which a clerk is forced to perform these imports is for it to periodically flush its entire lists of globaland local servers. As can be seen from the synchronization procedure in C.4.2, this causes the clerk to import the localset and, if necessary, the global set the next time it synchronizes.

Flushing is done periodically. The period between flushes is specified by the management attribute cacheRefresh.

If the server synchronized with the time provider, it schedules the next synchronization for the time specified by the timeprovider. (The nextPoll field of the TPctlMsg returned by a call to the ContactProvider function of the Time Providerinterface.)

If the server synchronized with other servers, or if it aborted the synchronization because there were too few servers, itdetermines the next synchronization in the same way that clerks do as specified in C.4.3.

H.2.10 Checking for faulty servers

To detect and report faulty servers in a timely fashion, servers must periodically obtain time from all other servers in the local set and check that their intervals intersect.

The procedure is the one used for synchronizing with other servers, as described in C.5.3.2, with the following changes:

  • No global servers are queried.
  • The procedure is not aborted if less than minServers -1 are queried.
  • The step to adjust (or set) the clock is not carried out.
  • The step to schedule the next synchronization is not carried out.

Checking for faulty servers is initiated by a periodic timer whose average period is specified by the management attribute checklnt. After initialization and after completing the checking procedure, the timer is set by drawing a random number in the range [(3checkInt)/4, (5checkInt)/4],

NOTE — Since checking is also done when a server synchronizes with other servers, the timer is restarted with a value that is a random number in the range [(3checkInt)/4, (5checkInt)/4].

ISO PDF プレビュー