論

ブロードバンドユビキタスネットワーク時代におけるインターネットアーキテクチャ論文特集

文

毎正秒パケット到着間隔（PAI）に基づいた時刻同期方式
町澤 朗彦† a)

岩間司†

鳥山 裕史†

Packet Arrival Interval (PAI) Based Time Synchronization
Akihiko MACHIZAWA†a) , Tsukasa IWAMA† , and Hiroshi TORIYAMA†

あらまし 近年，ネットワーク計測・分散制御分野では，マイクロ秒以下の同期精度が要求されている．高精度な時刻同期では，クロックレートが変動するスキューとパケット交換ネットワークにおけるキューイング遅延が問題となっている．そこで，本論文では，パケットの到着間隔による時刻同期方式（PAI：Packet Arrival
Interval based time synchronization）を提案する．本方式では，正確に一定間隔にブロードキャストされる同期パケットの到着間隔の平均がキューイング遅延の影響を受けにくいことを利用し，高精度にクロックレートを推定する．また，マスタから各クライアントへの片方向遅延は，LAN の構成要素に関する事前知識から高精度に算出可能である．なお，マスタを GPS に同期させれば，広域同期も可能である．実験の結果，回線利用度が80%程度のクロストラヒックの存在下でもマイクロ秒以下の同期精度が実現されることを確認した．しかも，本方式は，高い計算能力を必要としないため，センサネットワーク等の小さなノードでも利用可能である．
キーワード

高精度時刻同期，クロックレート，スキュー，パケット到着間隔，キューイング遅延

1. ま え が き動する（スキュー），(3) キューイング遅延の存在，な近年，ネットワーク計測・分散制御分野では，マイした時刻同期では，往路と復路の遅延時間が等しいとクロ秒精度の時刻同期が求められている [1], [2]．例え

仮定している方式が多いが，実際のネットワーク遅延ば，高精度な広域同期が必要な用途として，時分割多は非対称であり [6]，現在のインターネット技術では，

重方式を採用している携帯電話システムでは，屋外かネットワーク側から遅延時間情報は提供されてはいな

らの電波が届かない地下や大型ショッピングモールな

いため，一般のインターネットを介した場合，絶対的どが主な原因である．NTP など，ネットワークを介

どの屋内と，屋外との間を通話を継続しながら移動な同期精度は保証されない．一方，GPS が利用できる（ハンドオーバ）するためには，屋内と屋外の携帯電話環境では，マイクロ秒精度の時刻同期が可能であるが，の基地局が高精度に同期している必要があり，その要

GPS にはアンテナやコストの問題があるため，すべて求精度は，CDMA2000 で ±3 マイクロ秒，WCDMAの機器に GPS を用いることは現実的ではない．また，の時分割多重モードでは ±1.25 マイクロ秒 [3] である．

スレーブが 1 台であったとしても，GPS アンテナに用

しかも，屋内では電波の到達距離が短くなるため多数いられる同軸ケーブルを新たに敷設するよりも，既設の基地局を必要とする．

LAN を用いることができれば，費用や作業量だけでしかし，現在，インターネットでデファクトスタン

なく，構内光ファイバを用いた長距離伝送などメリッ

ダードとなっている NTP [4] ではミリ秒程度の精度しトが大きい．したがって，GPS に同期した stratum 1

か得られない [5]．これは，(1) ネットワーク遅延時間のマスタ時計が接続されている LAN において，低コが未知，(2) 時計の進み具合（クロックレート）が変ストで高精度な時刻同期方式が望まれている．
さて，前記 NTP の課題 (1)〜(3) は，インターネッ†

トだけではなく，LAN においても問題となる．まず，情報通信研究機構 小金井市
National Institute of Information and Communications

ネットワーク遅延時間は LAN でも，往路と復路でトラTechnology, 4–2–1 Nukui-Kitamachi, Koganei-shi, 184–8795

ヒックが異なるため非対称となるが，LAN では，ネッJapana) E-mail: machi@nict.go.jp

電子情報通信学会論文誌 B Vol. J89–B

トワークスイッチやケーブルなどの構成要素が既知でc （社）電子情報通信学会 2006
No. 10 pp. 1855–1866 

1855

電子情報通信学会論文誌 2006/10 Vol. J89–B No. 10あるため，遅延時間を事前知識から得ることが可能である．

2. 関 連 研 究

これまで，スキューに対しては，制御理論に基づい本章では，クロックレート推定に関連する研究をまたフィードバック系が多く用いられていたが [7], [8]，とめる．従来提案されてきた方式は，数学的には最小フィードバック係数が経験的に決定されており，最適二乗法と線形計画法に大別されることを示す．また，値を得ることが困難であった．一方，通信分野で，ディ各方式の計算量についても整理する．

ジタル PLL よりもフィードバック係数を最適化でき

2. 1 PLL とカルマンフィルタ

るカルマンフィルタが優れていることが示され [9]，最NTP で用いられている PLL/FLL は，フィードバッ

近，Bletsas はクロックレート推定にカルマンフィル

ク係数が経験的に決定されており，最適値を得ること

タを応用している [10]．しかし，カルマンフィルタでが困難であったが，Driessen は二次のディジタル PLL

は，計算能力を必要とする．

と等価なカルマンフィルタを構成し，フィードバック

また，ネットワーク遅延計測分野では，スキューを

係数を最適化できるカルマンフィルタが優れているこ補償するために，キューイング遅延が非負であることとを示し [9]，Bletsas はクロックレート推定にカルマを利用し，キューイング遅延の影響を除去する方式がンフィルタを応用した [10]．しかし，クロックレート

Paxson 及び Moon によって提案されている．Paxson
は区分的最小値を利用し [11]，Moon は線形計画法によって推定している [12]．しかし，高精度な時刻同期

は短期間では一定と考えられるが，推定値が一定とでは，キューイング遅延だけではなく，ネットワーク

がって，Bletsas の方法は，最小二乗法の近似解にす機器による処理遅延の変動の影響が顕在化する．

ぎない．一方，推定に用いるデータ点数を N とすれ

なお，キューイング遅延そのものを発生させない研究も進められているが，ルータやネットワークスイッチなどに変更が必要であったり [2], [13]，ネットワーク
を時分割で利用する方式 [14], [15] では，既存システムとの併用は不可能である．
そこで，本論文では，LAN における高精度時刻同なる場合は，カルマンフィルタは最小二乗法の逐次ア
ルゴリズムと一致することが知られている [16]．したば，共役分散行列を作り直すため，計算量は O(N 2 )の乗除算を必要とする．

2. 2 Paxson のアルゴリズム
Paxson は，キューイング遅延が非負であることを利用して，キューイング遅延の影響を除去した遅延時間の差の単位時間平均を用いている [11]．具体的には，√√期を目的として，毎正秒パケット到着間隔による時刻

まず，N 個のデータを， N ずつ

同期方式を提案する．本方式では，一定間隔にブロー分割し，各小区間の遅延時間の最小値を選び，任意のドキャストされた同期パケットの到着間隔がキューイ二つの最小値の差の単位時間平均を求める．すべてのング遅延の影響を受けにくいことを利用し，高精度な最小値の組合せから得られる平均値のメジアンをク

時刻同期を可能とする．なお，NTP のブロードキャ

ロックレートの推定値とする．ここで，次章で述べる

ストモードや IEEE1588 でも，同期パケットは一定のように，二つの遅延時間差の単位時間平均は，その期頻度で送出されるが，送出間隔に精度を要求しない点

間のクロックレートの最小二乗法の解となる．ただし，が提案方式と異なる．本方式では，マスタには同期パ

小区間の最小値を選択する際に，スキューを補償してケット送出間隔に高い精度を要求するが，スレーブはいないため，スキューよりも小さいキューイング遅延

整数の減算とビットシフト演算及びメジアンフィルタを排除することはできない．一方，計算量は O( N !)のみで実現されるため，センサネット等の計算能力のの除算を必要とする．

小さなスレーブにも実装可能である．実験の結果，回

2. 3 線形計画法

N 個の小区間に√線利用度が 80%程度のクロストラヒックの存在下でもMoon は線形計画法によって推定している [12]．す

マイクロ秒以下の同期精度が得られることを確認した．

べての遅延時間データが，クロックレート及び時刻オ

本論文では，2. でクロックレート推定に関する従来

フセットをパラメータとする直線より上方に存在する方式の関係を整理し，3. で毎正秒パケット到着間隔時

制約条件下において，データと直線との距離の総和を刻同期方式を提案する．4. では事前知識として必要と目的関数とする．しかし，高精度に遅延時間を計測す

なる，LAN の平均遅延時間について述べ，5. で提案る場合，キューイング遅延だけではなく，処理遅延の方式の性能について実データを用いて評価する．

変動も影響するため，同制約条件で得られる最適解

1856

論文／毎正秒パケット到着間隔（PAI）に基づいた時刻同期方式

は，実際のクロックレートとは異なる．一方，計算量
は O(N ) の乗除算を必要とする．

R=1+ρ

(2)

なお，温度補償されていない水晶では，周波数偏差は3. PAI 時刻同期方式の原理

10〜100 ppm 程度であるため，|ρ|  1 とする [11]．

本章では，パケット到着間隔（PAI：Packet Arrival

Interval）に基づいた時刻同期方式の原理について述べる．3.1 でネットワークを介した時刻比較をモデル化し，3.2 で比較時に問題となるネットワーク遅延をモデル化し，3.3 でキューイング遅延を除去してクロッ
クレートを推定する手法を提案し，3.4 でキューイン
グ遅延及び処理遅延の変動を除去して時刻オフセットを推定する手法を提案する．

3. 1 時刻比較モデル

ただし，|| は絶対値を表す．通常の温度補償されていない水晶によって駆動されている PC では，線形関係が保たれるのは数十秒以下である．
さて，マスタが毎正秒に時刻同期パケットをブロードキャストする場合を考える．時刻 ti にマスタから送出されたパケットは，遅延時間 di ( 1) 後にスレーブに到着する（図 2）．このとき，スレーブの時計の値

s(ti + di ) は，s(ti + di ) = R(ti + di ) + O

マスタの時刻とスレーブの時刻をネットワークを介= s(ti ) + Rdi

して比較した例を図 1 に示す．クロックレートが合っ= s(ti ) + diていないため，時間の経過に伴って，時刻差が広がっ(∵ ρdi  0)

(3)ている（時刻オフセットのドリフト）．また，比較開始となる．ここで，簡便のため，以下，スレーブの受信

後 70 秒付近より，正方向にキューイング遅延が見ら

時刻 s(ti + di ) を yi と記述する．

れる．時刻同期ではスキュー及びキューイング遅延に

3. 2 ネットワーク遅延モデル

よるノイズの除去が主要課題である．

本節では，式 (3) に示されるように，受信時刻に大まず，マスタの時刻 ti におけるスレーブ PC の示

きな影響を与える遅延時間をモデル化する．まず，遅す時刻 s(ti ) の間には，周波数源の種類に応じた短期

延時間 di を固定成分 ξ ，キューイング遅延成分 ηi そ間について，次式のような線形関係が存在する [17]．

してその他の変動成分 ψi に分解する．

s(ti ) = Rti + O(1)

di = ξ + ηi + ψi(4)

ここで，定数 R 及び O はそれぞれクロックレートとなお，図 2 では，ψi は省略している．次に，クロス

時刻オフセットである．さて，理想的に正確な時計でトラヒックが存在せず，ηi = 0 の場合の遅延時間平均

は，時計の進む速さはマスタに等しく，R = 1 であを ξ0 とする．

るが，現実の時計のクロックレートは周波数偏差 ρ を
含む．

1 
di
N
N

ξ0 =

(5)

i=1

ただし，N は標本数である．また，同様に，ηi = 0 の場合の変動成分 ψ0,i の平均と分散は以下のとおりで

図 1 ネットワークを介した二つの時計の比較
Fig. 1 Clock diﬀerence via network.

図 2 クロックモデル
Fig. 2 Clock model.

1857電子情報通信学会論文誌 2006/10 Vol. J89–B No. 10

3. 3 クロックレート推定

ある．

1
ψ¯0 =
N
2
σψ
=
0

N


N

ψ0,i =

i=1

N
1 

N

1 
(di − ξ0 ) = 0
N

ここで，パケット到着間隔に注目する．提案方式で

(6)

2
ψ0,i
=

i=1

N
1 

N

(di − ξ0 )2

は，毎正秒にパケットは送出されるため，送出間隔は常に正確に 1 秒となり，

i=1

(7)

i=1

ti − ti−1 = 1(13)

一方，図 2 では，時刻 ti に送出された時刻同期パ

なお，本論文では LAN を対象としており，ネットワー

ケットは，ネットワーク上の途中ノード（node）で ηiクを構成するスイッチの通過遅延の分布は平均値付近のキューイング遅延が生じている．このとき，先行時に集中しており，±3σψ0 の範囲にほとんど入っている

刻同期パケットとの間隔は ηi だけ伸びるが，逆に後（例えば，図 7）．また，これらのスイッチはハードウェ

続時刻同期パケットとの間隔は ηi だけ縮むことにな

アによって処理するため，通過遅延の平均も分散も負る．もし，前後の時刻同期パケットにはキューイング

荷の影響は小さく（図 8 参照），特に，負荷 80%以下

遅延が含まれていなければ（処理遅延は小さいので，

では，ほとんど一定であるため，遅延時間の固定成分

ここでは無視する），時刻同期パケットの到着間隔をとキューイング遅延以外の変動成分の統計的性質は一平均化すれば，キューイング遅延を除去することが可定と考える．

能となる．

ξ = ξ0(8)σψ = σψ 0

(9)

(10)

その大きさは σψ よりも大きい場合が多く，平均は σψ

が重畳している．

= R(ti − ti−1 ) + ηi − ηi−1 + ψi − ψi−1
= R + ηi − ηi−1 + ψi − ψi−1

(14)

ここで，δi の例を図 3 に示す．ただし，ダイナミック

よりも十分大きい（付録参照）．

η̄  σψ(13) より，次のようにクロックレートにノイズの差分

δi = yi − yi−1

一方，キューイング遅延は非負であり，

ηi ≥ 0

パケット到着間隔（PAI）を δi とすれば，式 (12)，レンジが狭いため，縦軸は 1 秒からの差分（PAI-1）(11)でプロットしている．なお，図 3 は，図 1 と同じデータを用いている．図 3 より，δi が一定値の上下にほぼ

式 (1)，(4) より，次式を得る．

均等に散らばっていることが分かる．この一定値が求

yi = Rti + O + ξ + ηi + ψi

(12)

したがって，時刻同期問題は，ノイズ成分 ηi 及び ψi

めるクロックレートである．そこで，最小二乗法に基づいてクロックレートを推定する．まず，δi の推定値の存在下で，毎正秒にブロードキャストされる同期パケットの到着時を観測値 yi として，スレーブのクロッ
クレート R 及び時刻オフセット O を推定する問題に帰着する．また，本方式は，LAN を対象としており，固定遅延成分 ξ は事前知識として 4. で示す推定法により与えられる．ただし，クロックレートを一定と考えられるのは，温度補償されていない水晶では数十秒程度であり，ネットワークトラヒックへの影響を考慮すると同期パケットは毎秒一つ程度となるため，統計処理に用いることのできるデータ数が少ない．なお，
ここでは，同期パケットが 1 秒間隔で送出される場合を示しているが，2 のべきで等間隔であれば，1 秒である必要はない．
1858

図 3 パケット到着間隔とクロックレート
Fig. 3 Packet arrival interval and clock rate.

論文／毎正秒パケット到着間隔（PAI）に基づいた時刻同期方式

を δ̂i とし，回帰直線を次式のように傾きが 0 の一定値とおく．

δ̂i = R(15)

次に，測定値 δi と推定値 δ̂i の予測残差の平方和を最小化する R を求める．クロックレートが一定と考えられるのは短時間であるため，近傍 N 点のデータに対する予測残差の平方和 Ji を最小化させる．



N−1

Ji =

(δi−k − δ̂i−k )2

(16)

k=0

図 4 時刻オフセット推定
Fig. 4 Time oﬀset estimation.

上式を R で偏微分し，正規方程式を得る．


∂Ji
= −2
(δi−k − R) = 0
∂R
N−1

(17)

k=0

1 

R̂ =
=

N

により与えられる．図 1 からスキューを補償した結果

1 

を図 4 に示す．最小値付近に集中しているデータとそ

N−1

δi−k =

k=0(21)

なお，遅延の固定成分 ξ は，次章で後述する事前知識

したがって，クロックレートの推定値 R̂ は，
N−1

yi − R̂i ti = O + ξ + ηi + ψiN(yi−k − yi−k−1 )k=01(yi − yi−N )N(18)で与えられる．これは，区間 [i − N : i] の両端でのれらの上方に離散しているデータに分離されている．
これは，キューイング遅延が非負であることによる．
さて，処理遅延は平均値付近に集中しており，±3σψの範囲にほとんど存在するが（図 7 参照），式 (11) より，同範囲に含まれるキューイング遅延の確率は非常

時計の差を，区間長 N で平均している．したがって，に小さい．なお，σψ も，次章で後述するように，事N を 2 のべきとすれば，二乗誤差最小化規範による推前知識により与えられる．したがって，最小値付近

定を，整数の減算とビットシフトのみによって実現可[min(yi − R̂i ti ), min(yi − R̂i ti ) + 6σψ ] のデータに対能である．

してメジアンフィルタを施すことにより，キューイン

ところで，式 (18) では，区間の両端の値 yi 及びグ遅延と接続機器の処理遅延ノイズを取り除き，時刻

yi−N のみから推定しているため，ノイズの影響を受

オフセットを推定する．ここでも前節と同様に算術平けやすい．そこで，次のように，同期パケット受信ご

均よりもロバストなメジアンフィルタを用いている．

とに，近傍 2 N 点のデータを用いて，N 個の推定値候補 R̂i [k](k = 0, ..., N − 1) を算出し，メジアンフィ

本章では遅延時間から，キューイング遅延や処理遅ルタを施す．

1(yi−k − yi−N−k )NR̂i = M EDIAN (R̂i [k])R̂i [k] =4. 遅延の固定成分
延の変動成分などを除いた固定成分について検討する．

(19)

経路に沿った固定成分の総和は，前章で導入したネッ(20)

トワーク無負荷時の平均遅延時間 ξ に相当する．まず，4.1 では，固定成分を構成要素に分解し，4.2 でなお，メジアンフィルタは算術平均よりもロバストでは，スイッチングハブの通過遅延について述べ，4.3

あることが知られている．

では，ケーブル遅延について述べる．最後に，4.4 で，

3. 4 時刻オフセット推定
まず，前節で得られたクロックレート推定値を用い

ξ 及び σψ を求める計算式について述べる．
4. 1 固定成分の構成要素て，式 (12) から導出される次式によって時刻オフセッ

マスタからクライアントまでの遅延時間を分解する

トのドリフトを補償した後，時刻オフセットを推定と，図 5 のようになる．マスタ内部で生成またはマスする．

タ外部より与えられる正秒信号（1 pls/s）を起点とし1859

電子情報通信学会論文誌 2006/10 Vol. J89–B No. 10
表 1 テストしたハブの遅延特性
Table 1 Latency of HUBs.
HUB(C)CG-SW05GTPV2(B)LSW-GT-5NS(N)GS105JP(G)GH-EHG5MRX(L)LB-GS05TP

Variance ofresiduals[ns2 ]
21
29
30
5000
7375

b

a

[ns]
736
759
737
1042
1013

[ns/bit]
1.000
1.000
1.000
1.000
1.001

図 5 遅延の構成要素
Fig. 5 Delay components.

て，以下のような成分により構成されている．

m outgoing ：マスタでの正秒とネットワークポートからフレーム先頭が出力されるまでの時間

network delay ：ケーブルの伝搬遅延と接続装置の通過遅延

図 6 スイッチングハブによる遅延時間特性の相違
Fig. 6 Latency of switching hubs.

buﬀering time ：スレーブでのネットワークポートにフレーム先頭が到着してから末尾までの時間

s incoming ：スレーブでのネットワークポートにフレーム末尾が到着してから割込みハンドラが呼出されるまでの時間

s interaction ：な項目は次のとおりである．

•
•
•
•

パケット長依存性•

負荷依存性

ポート依存性
方向依存性
ブロードキャスト/ユニキャスト依存性スレーブでの入出力命令発呼から実際の外界との入出力までの時間

表 1 に，現在入手可能な普及価格帯の主な 5 ポート

これらの固定成分が事前知識として与えられていれば，のギガビット対応ノンインテリジェントスイッチング

式 (12) によりオフセットを決定することができる．本

ハブについて，通過遅延時間を計測した結果を示す．

論文では，固定成分を実測するが，将来的には，構成

なお，伝搬時間の計測には PUTS [18] を用いた．一機器製造ベンダより提供されるべきである．

般に，通過遅延時間は，パケットサイズに比例するた

ただし，スレーブの buf f ering time はリンク速度

め，表 1 では，各ハブについて，パケットサイズと通とフレームサイズによって計算により求めることがで

過遅延時間に対する回帰直線の係数（a：傾き，b：y

き，buf f ering time = フレームサイズ [bit]/リンク切片）と分散を示している．また，パケットサイズを

速度 [bit/s] である．一方，スレーブ PC は外界との入パラメータとした通過遅延時間の例を図 6 に示す．ハ

出力（インタラクション）によってのみ，内部の状態

ブ (C) は通過遅延がパケットサイズに比例しているが，（時計）を知ることができる．したがって，入出力遅延

ハブ (L) はブロック状の分布を示している．なお，通の和 s incoming + s interaction として扱う．

過遅延の測定では，各ハブの 1 番ポートから入力し，以下の節で，network delay にかかわるスイッチン
グハブ及びケーブルについて詳細に検討する．

2 番ポートから出力させている．ここで，ハブ (C) 及びハブ (L) の通過遅延の分布を図 7 に示す．横軸は通4. 2 スイッチングハブ

過遅延時間，縦軸は頻度を表している．測定には，パスイッチングハブの通過遅延を推定するために必要

ケット長 1500 バイトの IPv4/UDP パケットを用い，1860

論文／毎正秒パケット到着間隔（PAI）に基づいた時刻同期方式

Fig. 7図 7 スイッチングハブ通過遅延分布
Latency distribution of switching hubs.

Fig. 8図 8 スイッチングハブ通過遅延負荷特性
Load characteristics of switching hub latency.

表 2 テストしたハブ (C) のポート遅延特性
Table 2 Latency of the port of HUB (C).
1

Input Port

1
2
3
4
5

737
741
742
761

Output Port
2
3
4
736
743
739
740
742
743
738
734
739
753
749
751

表 3 ケーブル遅延特性
Table 3 Latency of cable.
5
755
752
761
764

Length [m]
20
40
60
80
100

Outward [ns]
100
208
316
416
520

homeward [ns]
104
211
305
419
519

更に，ハブ (C) 及びハブ (L) の，負荷依存性を図 8

1 万パケットの通過遅延からヒストグラムを作成した．

に示す．横軸は通過するデータ量，縦軸は通過遅延時

ジッタの小さなハブ (C) ではヒストグラムのビン幅を間，エラーバーは通過遅延時間の標準偏差を示してい4 ns とし（図 7 (a)），ハブ (L) ではヒストグラムのビ
ン幅を 8 ns としている（図 7 (b)）．また，図中，水平方向の矢印は平均から ±3σψ の範囲を示している．通過遅延の分布は平均値付近に集中しており，±3σψ のる．ハブを介して 2 台の PC を接続し，片方の PC か

範囲にほとんど入っていることが分かる．

り，通過遅延の平均も分散も負荷の影響は小さく，特次に，ポート依存性について実験した．ここでは，

らパケットサイズ 1500 バイトの IPv4/UDP パケットを一定間隔で送出している．パケット送出間隔を短くすると，単位時間当りのデータ量が増加する．図 8 よに，負荷 80%以下では，ほとんど一定である．

ついてのみ報告する．ハブ (C) は五つのポートを有

4. 3 ケ ー ブ ル
CAT6 ケーブルの伝搬遅延時間は，100 m の長さにしており，各ポート間での通過遅延について，回帰分

対し 538 ns 以下と規定されている．例として，DTI-

通過遅延が最小であるスイッチングハブ (C) の結果に析した結果を表 2 に示す．1 番〜4 番ポートでは特性

C6X（沖電線製）について実測した．表 3 に，ケーブに相違は見られず，5 番ポートを利用した場合のみ，

ル長を変化させて，伝搬遅延を実測したデータを示す．

10〜20 ns ほどの遅延時間の増大が見られた．しかし，分散及びパケットサイズに対する係数 a に差異は認め

更に，この測定データから，回帰分析によって 1 m 当りの伝搬遅延を推定したとろ，5.2 [ns/m] となった．

られなかったため，表には示していない．また，同じ次に，理論的に伝搬遅延を求める．まず，UTP ケー

二つのポートの組合せでは，方向による差異は見られブルにおける電気信号の伝搬速度の理論値は，被覆絶なかった．

縁材料の比誘電率を % とすれば，次式で与えられる．

また，ユニキャスト及びブロードキャストフレーム
での遅延時間も計測したが，両者に差は見られなかっ√v = c/ %(22)

た．しかも，リンクアップしているポートの個数のブ

ここで，c は光速．UTP ケーブルに用いられている

ロードキャストパケットフレームの遅延時間への影響

FEP の比誘電率は，約 2.1 である．また，芯線の長も見られなかった．

さはよりの強さに影響されるが，信号の干渉を防ぐ
1861

電子情報通信学会論文誌 2006/10 Vol. J89–B No. 10

ために芯線ペアごとによりの強さが異なるため，1 本のケーブルでも，芯線の長さは異なっている．1 m のDTI-C6X の芯線を抜き取って，長さを測ってみたと
ころ，次のようになっていた．
橙 107\,cm 橙/白 105\,cm
緑 105\,cm 緑/白 104\,cm
青 111\,cm 青/白 111\,cm
茶 110\,cm 茶/白 109\,cm
したがって，1 m の UTP の信号伝達遅延の理論値は，最短ペアで 5.02 ns/m，最長ペアで 5.36 ns/m である．
結局，5.2 ns/m が妥当と考えられる．

4. 4 固定成分の推定値
本章のこれまでの議論により，遅延の固定成分の推図 9 性能評価システム構成図
Fig. 9 Performance evaluation system.

定値 ξˆ は以下の計算式によって求められる．
形計画法と比較する．更に，5.3 で初期特性についてξ̂ = m outgoing + network delay

NTP と比較する．5.4 で最後に，遅延の固定成分の+ buf f ering time + s incoming+ s interaction(23)

buf f ering time = S/L(24)

network delay =H(ak S + bk ) +

k=1

H


5.2li

イズ遅延特 性 ak 及び bk ，また，m outgoing 及び（s incoming + s interaction）は，機器のデータシー
トなどにより与えられる．また，S は時刻同期パケッ
トのフレーム長，L はスレーブのリンク速度，H はス
イッチングハブの段数，そして，lk は，k 段目と k + 1
段目のスイッチングハブを接続しているケーブル長である．
また，処理遅延の標準偏差は，k 段目のスイッチン
2
グハブの処理遅延の分散を σψ
とすれば，分散の加法k性を用いて次式で与えられる．
2σψk

スタは外部の原子時計からの 1 pls/s(M) で駆動し，2い，スレーブからのパルス出力 1 pls/s(S) と時刻源の

1 pls/s(M) をインタバルカウンタにて時刻差を計測

k=0

た だ し ，k 段 目 の ス イッチ ン グ ハ ブ の フ レ ー ム サH

5. 1 耐キューイング精度
図 9 に示す構成で提案方式の性能を評価した．マ
台のスイッチングハブを介してスレーブの同期を行

(25)

2
σψ
=

影響について考察する．

した．スレーブは，自時計の毎正秒にパルスを出力することにより，マスタとスレーブの時刻差を計測することが可能となる．一方，クロストラヒックは，iperf（注 1）（Ver. 1.1.1）の UDP モードを用いて，1500 バイ

ト長の IPv4/UDP パケットを所定レートで発生させ，ハブ (1) で，キューイングが生じる．
なお ，本論文 では，マスタと して PUTS を用 いている．PUTS は，通過型タイムスタンプとして開発されているが，付加機能として，任意のビットパ
ターンのイーサネットフレームを外部 1 pls/s 信号に同期して送出することが可能であり，PUTS では

m outgoing = 260 ns 一定である．また，本論文では，拡張ディジタル出力ボード（インタフェース社

(26)

k=1

5. 性能評価及び考察

PCI-2703）によってパルス出力を行い，実測した結果，s incoming + s interaction = 5025 ns を得た．
また，スレーブは，ソフトウェアタイムスタンプの精度を高めるために，割込みハンドラでプロセッササイ
クルカウンタを取得している [19]．スレーブの諸元を本章では，提案方式の性能について評価する．まず，

5.1 で耐キューイング性能について調べ，次に，5.2でクロックレートの推定精度について，提案方式と線
1862

表 4 に示す．また，ハブ (1) 及びハブ (2) は，ともに（注 1）：http://dast.nlanr.net/projects/Iperf/論文／毎正秒パケット到着間隔（PAI）に基づいた時刻同期方式
表 4 測定に用いた PC の諸元
Table 4 Speciﬁcation of the PC.
Mother board
CPU
Network controller
OS

Supermicro P4DPR-iG2Intel Xeon 2.4 GHz
ADMtek AN983(B) drv tulip-0.9.14
linux 2.4.18

図 11 クロックレート推定性能の比較
Fig. 11 Comparison of clock rate estimation.

で与えられる．p < 1 のとき，yi−k と yi−N−k の両パ
ケットともキューイングされていないペアはほとんど存在せず，クロックレートの推定は困難となる．この図 10 クロストラヒックによる同期精度の低下
Fig. 10 Synchronization accuracy deteriorated bycross traﬃc.

表 1 で，最も通過遅延の小さいスイッチングハブ (C)を用いている．
クロストラヒックの量を変化させて，同期精度を計測した結果を図 10 に示す．図 10 の横軸はクロスト
ラヒックのデータ量を回線使用率で表している．また，縦軸は，スレーブの毎正秒パルス出力と規準となる原
子時計の毎正秒パルスとの時間差（時刻オフセットに相当）の平均を示している．更に，ジッタの標準偏差をグラフ中にエラーバーで示した．クロストラヒックの回線使用率 80%以下ではマイクロ秒以下で同期していることが確認された．しかも，クロストラヒックの回線使用率 50%以下では 0.1 マイクロ秒以下で同期している．一方，ネットワークの回線使用率が 80%を超えると，急激に同期精度が劣化してしまう．
回線使用率が 80%を超えると，急激に同期精度が劣化してしまう理由は，クロックレート推定の誤差が大きくなるために，最終的な時刻オフセットの推定値の精度が劣化すると考えられる．提案方式では，式 (20)のように，N 個の標本ペアが用いられるが，パケッ
トがキューイングされずにハブを通過する確率は，回線の空き確率であるので，回線使用率を θ とすれば，yi−k と yi−N−k の両パケットともキューイングされていないペアの個数の平均 p は，

p = N (1 − θ)

2

ような回線使用率 θ1 は標本数 N の関数となる．

√
θ1 > (1 − 1/ N )(28)

ここで，N = 32 とすると，θ1 > 82.3% となる．一方，図 10 では，正に，82%付近から急激に精度が劣化している．更に，クロックレート推定の誤差が大きくなると，式 (21) による時刻オフセットのドリフトを十分に補償することができず，最終的な時刻オフセッ
トの推定の精度が劣化すると考えられる．
また，クロストラヒックがバースト的である場合，回線使用率が瞬間的に 80%を超える場合もあるが，影響は小さいと考えられる．これは，上で述べたように，本方式の精度がキューイングされずに通過した同期パ
ケットの割合に依存していると考えられるが，クロス
トラヒックと時刻同期パケットの到着は独立過程であり，時刻同期パケットがキューイングされずにハブを通過する確率は，瞬間的なキュー長ではなく，平均的な回線使用率に依存すると考えられるためである．

5. 2 クロックレート推定性能
従来方式の中では，最もクロックレート推定性能が高いと考えれらている線形計画法（LP）と提案方式（PAI）によるクロックレート推定値を比較した結果を図 11 に示す．参照データ点数は，線形計画法で 64
点の窓とし，1 秒ずつ窓をずらした．同様に，提案方式では N = 32 とし，参照データ点数をそろえている．なお，評価には図 1 と同じデータを用いており，
右縦軸は時刻同期をしない場合の，マスタとスレー(27)

ブの時計をネットワークを介して比較した差（clock1863電子情報通信学会論文誌 2006/10 Vol. J89–B No. 10

diﬀerence）を示している．実験システムの構成は前節と同じく，図 9 に示す構成を用いて，クロストラ
ヒックのない状態で十分同期してから計測を開始し，70 秒経過後から，クロストラヒックとして iperf により，1500 バイト長の IPv4/UDP パケットを，回線使用率 50%の一定レートで流している．また，線形計画
法は GNU 線形計画法キット（注 2）のシンプレックス法を利用した．
図 11 より，提案方式の推定値の方が安定していることが分かる．これは，高精度時刻同期では，処理遅延の変動が無視できなくなるため，線形計画法で仮定している “ノイズは非負” が成り立たないためと考え

Fig. 12

図 12 同期初期特性
Initial character of synchronization.

られる．また，線形計画法の解は制約条件の張る凸多面体の頂点を移動するため，推定値は離散値となり，
図 11 のようにステップ状となる．更に，評価データ
は，途中からキューイング遅延を含んでおり，提案方式の推定精度は若干低下しているが，線形計画法の変動よりは小さい．

5. 3 初 期 特 性（注 3）
NTP の初期特性と比較する．ntpd（Ver. 4.2.0）を用いて，図 9 と同様の構成を用いた．ただし，クロストラヒックのない状態で計測した．また，NTPのポーリング間隔を 16 秒固定とし，ntp サーバにはPUTS を用いた．PUTS の SNTP サーバ精度は 8 ナノ秒である [20]．実験結果を図 12 に示す．横軸は同期開始からの経過時間を示しており，縦軸は，スレーブの毎正秒パルス出力と規準となる原子時計の毎正秒
パルスとの時間差を示している．

NTP では，PLL/FLL のフィードバック係数が小さいため，初期化に 1 時間ほど要する（図 12）．一方，提案方式は，プログラム起動後，数秒でマイクロ秒以下の精度に達する．

5. 4 固定成分の影響
遅延の固定成分 ξ の及ぼす影響について考える．
式 (21) で，固定成分 ξ を独立して扱わず，オフセッ
トと固定遅延成分の和 O + ξ を一体化して，仮想的なオフセットとみなした場合，ξ 相当分の誤差を含
むことになる．イーサネットの最小フレーム長は 84
バイトであるため，リンク速度が 1 Gbit/s の場合，
表 1 で測定したスイッチングハブでは 1 段で最低，84 [byte] × 8 [bit] × a [ns/bit] + b [ns] = 1408 [ns] の遅延が生じ，ケーブル遅延も 100 m で 520 ns 生じる．
したがって，少なくとも 2 µs 程度の誤差を含むことになり，本論文で対象とするマイクロ秒以下の高精度同1864

期では ξ をオフセットと一体化して考えることはできない．しかし，もし，必要とする精度が数 µs 程度な
らギガビットイーサネットで，数十 µs 精度程度ならファストイーサネットでも，ξ を考慮せずに簡便にオフセットを推定することが可能である．

6. む す び
LAN 上での高精度時刻同期方式を開発した．正確に一定間隔でブロードキャストされる時刻同期パケットの到着間隔を利用することにより，パケット交換ネッ
トワークで生じるキューイング遅延の影響を除去し，高精度に同期できることが確認された．回線使用率80%程度のクロストラヒックが存在する場合でも，マイクロ秒以下の精度で同期可能である．また，本方式
では，スレーブは整数の減算とビットシフト演算及びメジアンフィルタのみで実現され，初期同期時間も短
いため，センサネット等の計算能力の小さなスレーブにも実装可能である．しかも，本方式は，ネットワー
ク全体の同期システムを置き換える必要はなく，NTPなどの他システムとの混在が可能である．本方式では，マスタを GPS に同期させることにより，同期系全体
を広域同期を得ることができる．
今後は，ユビキタス環境に向けて，無線 LAN での高精度時刻同期に展開する予定であるが，チャネル競合及び電波干渉などが問題となる．また，単独の GPS
では大気のシンチレーションによって，100 ナノ秒以下の精度での時刻同期は困難であるため，光ファイバを用いた広域高精度時刻同期の研究も進める予定で（注 2）：http://www.gnu.org/software/glpk/glpk.html（注 3）：http://www.ntp.org/

論文／毎正秒パケット到着間隔（PAI）に基づいた時刻同期方式

ある．

no.10, pp.2002–2011, Oct. 2005.

文
[1]

[19]

献

S. Johannessen, “Time synchronization in a local area
network,” IEEE Control Syst. Mag., vol.24, no.4,
pp.61–69, 2004.

[2]“IEEE1588:

IEEE standard for a precision clock

synchronization protocol for networked measurement
and control systems,” IEEE Standard, 1588, 2002.
[3]

S.

RodriguesandA.

Pietilainen,

町澤朗彦，北口善明，“割込みハンドラと高精度 PC によるソフトウェアタイムタンプの精度改善，” 信学論（B），
vol.J87-B, no.10, pp.1678–1685, Oct. 2004.

[20]

鳥山裕史，町澤朗彦，岩間 司，金子明弘，“ハードウェ[21]

ア SNTP サーバの開発，” 信学技報，CQ2005-12，2005.
C. Williamson, “Internet traﬃc measurement,” IEEE
Internet Computing, vol.5, no.7, pp.70–74, 2001.

“IEEE-1588

付

telecommunications applications,” Proc. of the 2005
IEEE 1588 Conference, Zurich, 2005.
[4]

D.L. Mills, “Network time protocol (version 3),” RFC
1305, IETF, 1992.

[5]

[6]

[7]

network clocks,” ACM Comput. Commun. Rev.,ら推定する．インターネットを流れているトラヒック

vol.24, no.2, pp.28–43, 1994.

のパケット長は，長短に偏在していることが知られてK.C. Claﬀy, G.C. Polyzos, and H.-W. Braun, “Measurement considerations for assessing unidirectional

おり [21]，これは，データパケットの多くが MTU サ

latencies,” Internetworking: Research and Experi-

イズとなる一方，コントロールパケットの多くが TCP

ence, vol.4, no.3, pp.121–132, 1993.

ヘッダのみであり，その割合は，長いパケットが約半

D.L. Mills, “Adaptive hybrid clock discipline algoTrans. Netw., vol.6, no.5, pp.505–514, 1998.
J. Levine, “Time synchronization over the inter-

ネットではなく，LAN を対象としているが，パケッ

net using an adaptive frequency-locked loop,” IEEEト長の分布を同様と仮定する．さて，ここでは，平均の変動よりも十分大きいことを示せばよいため，更にacquisition using adaptive kalman ﬁltering tech-

モデルを簡略化し，ランダムな長さのパケットを無視

niques,” IEEE Trans. Commun. Technol., vol.42,

し，長短パケットの割合を 50%/50%とする．この場

A. Bletsas, “Evaluation of kalman ﬁltering for net-

キューイング時間は短くなる．また，キュー長も最長

electr. Freq. Control, vol.52, no.9, pp.1452–1460,

1 と仮定する．キューに複数のパケットがたまってい2005.

る場合よりも，やはり，推定される平均キューイング

V. Paxson, “On calibrating measurements of packet
pp.11–21, 1998.
S.B. Moon, P. Skelly, and D.F. Towsley, “Estimaion
and removal of clock skew from network measurements,” Proc. IEEE INFOCOM ’99, pp.227–234,
New York, 1999.

[13]

北口善明，町澤朗彦，鶴 正人，尾家祐二，箱崎勝也，“パケット自己消滅法によるネットワーク時刻同期精度の向上，” 情処学論，vol.46, no.4, pp.1017–1024, 2005.

[14]

合，短パケットの割合が増えるため，推定される平均

work time keeping,” IEEE Trans. Ultrason. Ferro-transit times,” Proc. ACM SIGMETRICS 1998,[12]

キューイング時間がスイッチングハブなどの処理遅延

P.F. Driessen, “DPLL bit synchronizer with rapid

no.9, pp.2673–2675, 1994.

[11]

数，短いパケットが約 40%となり，残りの 10%ほどはランダムなパケット長である．本論文では，インターno.4, pp.888–896, 1999.

[10]

まず，1 段のスイッチングハブで生じる平均キューD.L. Mills, “Precision synchronization of computer

Trans. Ultrason., Ferroelectr. Freq. Control, vol.46,[9]

式 (11) の根拠
イング時間を，クロストラヒックのパケット長分布か

rithm for the network time protocol,” IEEE/ACM[8]録

H. Kopetz and G. Bauer, “The time-triggered archi-

時間は短くなる．
さて，時刻同期パケットがキューイングされたときに，回線を占有しているパケットが長パケットである
確率は，Pl = Ll /(Ll + Ls ) である．ここで，Ll , Ls
は，それぞれ，長パケット及び短パケットのフレーム長である．イーサネットのプリアンブルや FCS（Frame
Check Sum）などのオーバヘッドを考慮すると，長パケットのフレーム長 (Ll ) は Ll = 1538 バイトであり，tecture,” Proc. IEEE, vol.91, no.1, pp.112–126, 2003.

リンク速度を 1 Gbit/s とすれば，ポート占有時間 (Tl )[15]

福富 実，“時刻同期方式，” 特許 2705665, 1995.

は Tl = 12304 ns である．また，短パケットのフレー[16]

添田 喬，中溝高好，大松 繁，信号処理の基礎と応用，
日新出版，1979.

ム長及びポート占有時間は，それぞれ，Ls = 84 バイ[17]

北口善明，町澤朗彦，中川普一，西村道明，日迫 彰，箱崎勝也，“PC における時刻精度の精密計測とその評価，”
信学技報，NS2003-160，2003.

[18]

町澤朗彦，鳥山裕史，岩間 司，金子明弘，“通過型高精度
UDP タイムスタンパの開発，” 信学論（B），vol.J88-B,

ト及び Ts = 672 ns である．これらの値を代入すれば，Pl = Ll /(Ll + Ls ) = 94.8%(A·1)

である．同様に，短パケットが回線を占有している確1865

電子情報通信学会論文誌 2006/10 Vol. J89–B No. 10

鳥山

率は次のようになる．

Ps = Ls /(Ll + Ls ) = 5.2%

(A·2)

一定長パケットによるキューイング時間の分布は一裕史 （正員）昭 56 名工大・情報卒．昭 58 名大大学
院情報工学専攻博士課程前期課程了．同年
郵政省電波研究所（現情報通信研究機構）

様分布となり，その平均は（ポート占有時間/2）であ入所．平 2〜5 ATR 通信システム研究所．
平 5〜6 ドイツテレコム研究所客員研究員．

る [18]．したがって，平均キューイング時間 η̄ は少な

画像符号化，情報通信などの研究に従事．

くとも，η̄ = Pl ∗ Tl /2 + Ps ∗ Ts /2 = 5.85 us(A·3)と推定される．
一方，表 1 より，個々のスイッチングハブの処理遅延の標準偏差は 100 ns 以下であるため，η̄  σψ(A·4)と考えることができる．この関係は，スイッチングハ
ブの段数が増えても維持される．なんとなれば，平均
キューイング時間は加算的であるが，標準偏差は 2 乗で加算的（分散の加法性による）であることによる．
（平成 18 年 1 月 18 日受付，5 月 17 日再受付）

町澤朗彦 （正員）昭 59 上智大・理工・電気電子卒．同年郵政省電波研究所（現情報通信研究機構）入所．平 6 科学技術庁に出向し，IMnet 立上げに参与．平 8〜11 Univ. Canterbury
客員研究員．平 15 JGN2 立上げに参与．
画像の高能率符号化，視覚情報処理，計算機ネットワーク，時刻同期の研究に従事．

岩間

司 （正員）

昭 58 山梨大・工・電子卒．昭 60 東工大
大学院修士課程了．同年郵政省電波研究所（現情報通信研究機構）入所．以来，電波伝搬特性解析，移動通信のセル構成，標準時，時刻認証基盤技術の研究に従事．現在，
電磁波計測部門タイムアプリケーショング
ループ主任研究員．平 2 本会篠原記念学術奨励賞受賞．IEEE
会員．

1866