デバイス時刻の推定

ExecAt や GpioOut::SysTimeEq などでは, デバイスの時刻を指定する必要がある. ホストは PTP に参加していないので, デバイスの時刻を直接知ることはできない. そのため, DeviceClock は, ホストの送信/受信時刻とデバイスの送信/受信時刻を記録して, それらの情報から, ホスト時刻に対応するデバイス時刻を推定する.

デバイスの時刻 (ETHSW のタイマ) は, open 時に GM (ID 0 のデバイス) が SetTime で指定した値 ( 0 ) から GM のクロックでカウントする. slave は PTP で GM に追従するので, GM の時刻だけを推定すればいい.

ホスト時刻とデバイス時刻

時刻にはホストの時計で測ったもの (ホスト時刻) と, デバイスの時計で測ったもの (デバイス時刻) の 2 種類がある. 以下, ある出来事をホストの時計で測った時刻をと表し, 同じ出来事をデバイスの時計で測った時刻をのようにを付けて表す.

ホスト時刻を基準にして, 両者の差を offset とおくと,

となる. 任意のホスト時刻に対して, デバイス時刻を得るために, を推定する必要がある.

デバイスの時計はホストの時計とは独立しており, 水晶振動子の誤差等により微妙にクロック周波数は指定値とは異なる. そのためは一定ではなく, 時間が経つと徐々に変化していく. 周波数差は温度などでもゆっくり変わるが, 短い区間窓 (直近 10 s) の中では一定とみなし, を直線

で近似する. はでの offset, はクロック周波数の相対差である (例えば, デバイスの時計がホストより 1 ppm 速ければ ).

1 往復から得られる上下限

GM へ送った Frame / Heartbeat の 1 往復に関して, 以下の 4 つの時刻を記録する.

: ホストが要求を送る直前のホスト時刻
: GM が要求を受信したデバイス時刻
: GM が返信を組んだデバイス時刻
: ホストが返信を受信したホスト時刻

GM が要求を受信した時, および, 返信を組んだ時のホスト時刻を直接観測することはできない. ここで, 往路 (ホスト → GM) の遅れを , 復路 (GM → ホスト) の遅れをとおくと, どちらもホスト時刻で

となる. ただし, も直接観測することはできない.

往路について, 観測されるは

となる. なので,

が成り立つ. ここで, のはずなのでとなり, はホスト時刻における offset の上限になる.

復路も同様に,

となり, はホスト時刻における offset の下限になる.

そこで 1 往復から 2 種類のサンプル (ホスト時刻, offset の限界) を作る.

上限:
下限:

以下, 上限のサンプルを , 下限のサンプルをとおく.

上の議論から, 全てのサンプルで

である.

offset の推定

真の直線は, 区間窓の中の全ての下限の上側, 全ての上限の下側を通るはずである. 傾きをに固定すると, そのような直線の切片が取れる範囲は

となる.

ここで,

とすし, 真の傾きでがほぼ最大になることを示す.

真の値をとすると, 各サンプルは

と書ける. よりとすると,

である.

傾きをとおくと,

したがって,

となり,

である.

ここで, 遅れは経路で決まる一定の遅れに, 混雑や処理待ちなどによる余分な遅れが加わったものと考え,

とおく. はサンプルによらない定数, はサンプルごとに異なる誤差である. これらを代入すると,

となる. の場合は, より

である.

のとき, となる上限のサンプルと下限のサンプルを 1 つずつ選ぶと,

となる.

のときは, 逆にとなる , を選ぶと, 同様に

となる.

どちらの場合も, 選んだ , の誤差が小さいほどは以下に近づく. サンプルがたくさん取れれば, が十分小さいものが選べるはずなので,

となり, 真の傾きではほぼ最大になる.

また, を最大にする傾きはを満たす. したがって,

となる. 誤差の小さいサンプル同士が窓の中で離れているほど傾きの推定は正確になる.

切片は, 傾きでのの範囲の中央, つまり帯の中央を取って

とし, ホスト時刻に対するデバイス時刻をと推定する.

とすると, 前の式から

なので,

となる. したがって, 切片の真の値とのずれは程度であり, 往路と復路の一定の遅れが等しければずれない.

アルゴリズム

ここでは, を最大にする傾きを求めるアルゴリズムを述べる.

まず, は, 上限のサンプル群の下側凸包と下限のサンプル群の上側凸包を構成するサンプルのみが寄与することを示す.

まず, 上限側のについて, どのサンプルが効くのかを考える. は, 平面で点を通る傾きの直線の切片である. したがって, これを最小にするような点は, 必ず上限のサンプル群の下側凸包の頂点である.

サンプルを 1 つ固定すると, は傾きのの 1 次関数である. は, これらの直線のうち各で一番下にあるものなので, 直線をつないだ上に凸な折れ線になる. また, この折れ線の折れ目は, 2 本の直線の交点であり,

となる. この右辺は平面で点とを結ぶ線分の傾きである. したがって, 折れ目は下側凸包の辺の傾きにある.

よって, は下側凸包の頂点のみによって決まり, の候補は, 下側凸包の辺の傾きになる.

下限に関しても同様の議論が成り立ち, 下限のサンプルのなかで, 上側凸包の頂点のみによってが決まる.

したがって, を最大にするの候補は, 上限の下側凸包の辺の傾きと, 下限の上側凸包の辺の傾きのみになる.

以上の議論に従って, 以下のアルゴリズムでを最大にする傾きを求める.

下限・上限の列がどちらも 1 s 以上にわたり, かつ

を満たすとする. これが満たされない場合は2に進む

1-1. 下限の列から上側凸包, 上限の列から下側凸包を Andrew’s Monotone Chain Algorithm で作る

1-2. 2 つの凸包の各辺の傾きを候補とする

1-3. 各候補について, 天井と床を

で求める ( は凸包の頂点だけ走査する)

1-4. が最大の候補を選び, , とする.
1 の条件を満たさず, 最新の下限と最新の上限のホスト時刻の差が 1 s 未満のとき, 傾きを 0 としてとする (open 直後など, サンプルがまだ少ない間).
どちらでもなければ, 推定しない.

実装

サンプルの収集

GM 宛てにフレームを送るたびに, その msg_id と送信直前のホスト時刻を記録する
GM の返信を受け取るたびに,
- 返信時刻が載っていれば, 下限のサンプルを加える.
- 要求の受信時刻が載っていて, 同じ msg_id のが記録されていれば, 上限のサンプルを加える.
open 時の SetTime では, デバイス時刻が送信直前のホスト時刻と応答受信時のホスト時刻の間に 0 になるので, 上限と下限を加える.
ホスト時刻は, 最初に記録した時刻 (最初の送信または最初の返信) からの経過時間 [ns] とする.

間引きと区間窓

後々の走査の計算量を減らすため, サンプルは間引きと区間窓で整理する.

ホスト時刻を 100 ms ごとの区間に区切り, 各区間でサンプルを 1 つだけ残す. 下限はが最大のもの, 上限はが最小のものを残す. 直前の区間より古い区間のサンプルが届いたら捨てる.
下限・上限のどちらかで最新のサンプルから 10 s より古いサンプルを, 両方の列から捨てる.

これにより各列のサンプルは高々 101 個で, ホスト時刻順に並ぶ.

凸包の頂点は高々 101 個なので, 候補は高々 200 個, 1 回の推定は高々 4 万回程度の積和で済む. 推定は DeviceClock::now のたびに行い, 凸包も毎回作り直す. なお, 上限の下側凸包は, 符号を反転させて下限の上側凸包と同じアルゴリズムで作る.

整数演算

候補の傾きは, 凸包の辺の両端の差

のまま, 整数の組で持つ.

また, 最後にとを別々に割り算しなくて済むよう, 推定したいホスト時刻に対して,

を用いる. は共通なので, 幅は変わらない.

この時,

となる.

最後に, 選んだ候補について,

でを求める.