隨機路徑延遲下的網路同步

Abstract

封包延遲變異(packet delay variation)通常是利用交換帶有時間資訊的封包之網路同步方式最主要的估計誤差來源。沿著主從路徑(master-to-slave route)，在交換式集線器的佇列緩衝區之封包轉接延遲變異乃是網路(時鐘)同步系統最主要的不確定性來源。一個常被用來減少封包延遲變異的方法為利用最小取樣濾波器(sample-minimum filter)去選擇一個有著最小時間差異的封包。易言之，在所有收到的封包裡，我們選擇一個有著最小的主從時間戳差(timestamp difference)的封包，假設其傳遞過程並無轉接延遲，而去計算時鐘偏差(clock offset)。然而，上述假設未必成立，亦即封包延遲變異並不能用最小取樣值來描述。在擁擠的網路，平均取樣濾波器(sample-mean filter)或最大取樣濾波器(sample-maximum filter)可能會有更好的性能。 在這篇論文當中，我們考慮兩種廣義的參數封包延遲模型。第一個模型假設封包延遲遵循著含有未知的階層參數(order parameter)與流量速率參數(traffic rate parameter)之爾朗分佈(Erlang distribution)；第二個模型則運用了混合式爾朗分佈(mixed-Erlang distribution)來描述封包延遲的統計分布。對於第一個模型，我們利用廣義最大似然估計(GMLE)去同時估算時鐘偏差與模型參數。至於第二個模型，我們則使用動差匹配(moment matching)的概念先去估計混合係數，接著利用三階動差的最小平方誤差找出時鐘偏差的解。當部分混和係數變得非常小而讓混合式爾朗分佈退化時，這個方法可能無法得到可靠的估計值。為了解決這個缺點，我們增加了一個模型選擇步驟，將混和係數組合劃分成了七種模型。模型選擇標準是基於採樣的延遲分佈與量化模型分佈之間的KL散度(Kullback-Leibler divergence)。根據電腦模擬的結果，我們發現除了在第一種模型的流量速率參數非常小的特殊情況下，我們的估計法是無偏(unbiased)的，而且能大幅度的改善最小取樣濾波器的平均估計值與均方誤差(root mean squared error)效能。

The packet delay variation (PDV) is usually a major error source in a packet-based synchronization system. The PDV at the queue buffer in each switching hub along the master-to-slave route presents a considerable uncertainty in the clock recovery system. A popular method to mitigate PDVs is to apply the minimum filter that uses only the packet with the least delay, i.e., we select, among the arriving packets, the packet with the minimum master and slave timestamp difference to compute the clock offset and discards all other packets. However, PDV does not always follow a distribution that is amenable to (sample-)minimum filtering. It has been shown that for congested networks, the sample-mean filter or the sample-maximum filter may yield better performance. We consider two general parametric packet delay (PD) models. The first model assumes that the PD follows an Erlang distribution with unknown order parameter and traffic rate parameter, and the second model describes the PD by a mixed-Erlang distribution. For the first traffic model, we derive the generalized maximum likelihood estimator (GMLE) to jointly estimate the clock offset and model parameters. To estimate the clock offset with the second model, we invoke the concept of moment matching to estimate the mixing coefficients first and then find the solution with the least squared third moment error. This approach may fail to give an accurate estimate when a subset of the mixing coefficients become very small. To deal with this shortcoming, we add a model selection step by classing the mixing parameter combinations into seven cases (models). The model selection criterion is based on the Kullback-Leibler divergence (distance) between the sampled delay distribution and the quantized model distribution. Simulated numerical behaviors of the proposed synchronizers are presented. We find that, except for the special case when traffic rate parameter of the first model is very small, our estimators are unbiased and offer much improved mean performance than that of the minimum filter.