CN101867431B - Network clock synchronization method - Google Patents

Abstract

The invention discloses a network clock synchronization method, which includes the following steps: step 1, obtain the delay measurement value according to the one-way transmission of the data packet with time stamp between the local host and the foreign host, and then use linear programming to obtain The clock rate ratio F of the local host and the foreign host; Step 2, then obtain the clock deviation offset according to the data packet with time stamp between the local host and the foreign host and the clock rate ratio F; Step 3, according to the clock Skew performs clock synchronization between the local host and the foreign host. The method of the invention has low cost and good robustness, only depends on the inherent host clock property, and simultaneously takes into account precision and burst resistance.

Description

A Network Clock Synchronization Method

technical field

The invention belongs to the field of network communication and relates to a network clock synchronization method.

Background technique

Network clock synchronization is a problem faced in network measurement. Clock asynchrony will affect the measurement accuracy related to time information such as delay and jitter. At the same time, in terms of network host collaboration, maintaining the clock synchronization of hosts in the network is to ensure its effectiveness. basis of work.

Existing clock synchronization methods are generally divided into two types: a hardware synchronization method and a software synchronization method.

There are two main technologies for hardware synchronization methods: GPS (Global Positioning Systems) and radio signals. GPS uses satellite signals to provide precise clock synchronization, and its highest resolution accuracy can reach 100ns. Although it will lose certain accuracy when converted into the clock pulse of the computer system core, its accuracy can still be controlled within microseconds. Its disadvantage is that each machine to be synchronized needs to be equipped with GPS, which is expensive.

The software synchronization method utilizes software completely, and the accuracy of this method is between 10 ^-4 s and 10 ^-3 s. Software synchronization methods mainly include the Network Time Protocol (NTP) (Network Time Protocol) proposed by Professor David L. Mills of the University of Delaware in 1985 and the improved Simple Network Time Protocol SNTP (Simple Network Time Protocol). Its disadvantage is that it does not consider the excessive clock rate or the change of clock offset during the synchronization process, so it is not robust enough to deal with network uncertainty and host uncertainty. Other synchronization algorithms, such as the Altair & Vega (A&V) method, not only need to know the clock rate ratio but also need to use the current clock deviation, that is, the host extrinsic property, so although it has good accuracy, it cannot cope with network bursts Changes, such as changes in the clock skew, require a lot of time to recalculate the new clock skew and clock rate ratio.

Contents of the invention

The technical problem to be solved by the present invention is to provide a robust network clock synchronization method with low cost, both accuracy and burst resistance.

In order to solve the above technical problems, the present invention adopts the following technical solutions.

A network clock synchronization method comprises the steps:

Step 1. Obtain the delay measurement value according to the one-way transmission of the time-stamped data packet between the local host and the foreign host, and then use linear programming to obtain the clock rate ratio F of the local host and the foreign host;

Step 2, then obtain the clock offset offset according to the interactive transmission of data packets with time stamps between the local host and the foreign host and the clock rate ratio F;

Step 3: Perform clock synchronization between the local host and the foreign host according to the clock deviation.

As a preferred solution of the present invention, the specific implementation method of said step 1 is:

The local host sends a large number of data packets with sending timestamps to the foreign host;

The foreign host obtains the delay measurement value d _i according to the sending time and receiving time of different data packets;

According to the sending time, receiving time and delay measurement value d _i , use linear programming to obtain the clock rate ratio F of the local host and the foreign host.

As another preferred solution of the present invention, the specific implementation method of said step 2 is:

The local host sends a request packet with sending timestamp t ₁ to the foreign host;

The foreign host records the receiving time _t2 after receiving the request packet;

The foreign host replies to the local host with a response packet with a receiving timestamp _t2 and a sending timestamp _t3 ;

The local host records the time t ₄ of receiving the response packet;

获得本地主机和外地主机的时钟偏差。According to the clock skew formula

Get the clock skew of the local host and the foreign host.

As another preferred solution of the present invention, the detailed steps of the network clock synchronization method are:

Step A, the local host A sends a large number of data packets with the sending time stamp T _i to the foreign host B;

Step B, the foreign host B receives the data packet, and obtains the delay measurement value d _i according to the sending time and receiving time;

Step C, according to the transmission time T _i and the measured delay value d _i , use linear programming

$\mathrm{<span\; class="notranslate">\; min</span>}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&beta;</span>}<span\; class="notranslate">\; \}</span>$

d _i -(F-1)T _i +β≥0, 1≤i≤N

Get the clock rate ratio F;

Step D, the local host A sends a request packet with a sending time stamp _t1 to the foreign host B;

Step E, the foreign host B records the time _t2 of receiving the request packet;

Step F, foreign host B writes t ₂ and the time t ₃ of sending the response packet in the response packet and replies to the local host A;

Step G, the local host A records the time _t4 of receiving the response packet;

得到两台主机的时钟偏差，从而完成时钟同步。Step H, local host A uses the formula according to time t ₁ , t ₂ , t ₃ , t ₄

Get the clock deviation of the two hosts to complete clock synchronization.

The beneficial effect of the present invention is: the present invention does not need special equipment such as GPS, has very low cost; Considers the clock rate ratio and the clock deviation change that influences synchronous accuracy, has very good robustness; Utilizes the master clock Inherent properties, so it has good burst resistance while ensuring accuracy.

Description of drawings

Figure 1 is a diagram of the calculation clock rate ratio model.

Fig. 2 is a flow chart of the network clock synchronization method of the present invention.

Fig. 3 is the experimental comparison result (1) of the method of the present invention and the NTP method in a simulated environment.

Fig. 4 is the experimental comparison result (2) of the method of the present invention and the NTP method in a simulated environment.

Fig. 5 is the result of the method of the present invention and the NTP method after the synchronization of the simulated network.

Detailed ways

The specific implementation manners of the present invention will be described in further detail below in conjunction with the accompanying drawings.

Embodiment one

This embodiment provides a network clock synchronization method, the method is:

First, host A sends a large number of data packets with sending time stamp T _i to another host B, and then host B calculates the delay measurement value d _i according to the receiving time, and finally combines d _i and T _i , using linear The planning method obtains the clock rate ratio F of the two hosts.

得到两台主机的时钟偏差，从而完成同步。Then, the two hosts obtain the information required for clock synchronization by exchanging timestamp information, sending request packets and response packets, and then use the formula

Get the clock deviation of the two hosts to complete synchronization.

As shown in Figures 1 and 2, the network clock synchronization method described in the embodiment specifically includes the following steps:

Step A, host A sends a large number of data packets with sending timestamp T _i to host B;

Step B, host B receives the data packet, and obtains the delay measurement value d _i according to the sending time and receiving time; the delay measurement value d _i here is a one-way delay value, and there is an error of clock deviation, that is, the measured one-way delay value ;

Step C, according to the transmission time Ti and the measured delay value d _i , use the linear programming formula

$\mathrm{<span\; class="notranslate">\; min</span>}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&beta;</span>}<span\; class="notranslate">\; \}</span>$

d _i -(F-1)T _i +β≥0, 1≤i≤N

The clock rate ratio F is obtained; the clock rate ratio F is the time scale of clock changes per second. Because the transmission time T _i and the delay measurement value d _i are values obtained through measurement, that is, they are known. The formula d _i -(F-1)T _i +β≥0 is a constraint condition, that is, when the condition d _i -(F-1)T _i +β≥0 is satisfied, the formula F and β with the smallest value of 1≤i≤N, where β is a value similar to offset, here there is no need to consider the variable β, if β is considered, the algorithm described in this embodiment cannot cope with suddenness, this variable Related to, but not identical to, the current clock skew.

Step D, host A sends a request packet with sending timestamp _t1 to host B;

Step E, the host B records the time _t2 when the request packet is received;

Step F, host B writes _t2 and the time _t3 of sending the response packet into the response packet and replies to host A;

Step G, host A records the time _t4 of receiving the response packet;

得到两台主机的时钟偏差，从而进行时钟同步。Step H, host A uses the formula according to time t ₁ , t ₂ , t ₃ , t ₄

Get the clock deviation of the two hosts, so as to synchronize the clocks.

此公式是考虑了时钟速率比存在和时钟同步过程中时钟偏差变化而得到，具有很好的健壮性。Among them, when host A sends a large number of data packets to calculate the clock rate ratio, in order to ensure that the sending time is not affected by system process switching, we send a data packet every T (T ≥ 1) seconds, which can ensure that the statistical calculation clock The accuracy of the rate ratio; the time information in the formula is relative to the host that obtains the time information, such as t ₁ is relative to host A, t ₂ is relative to host B, and the delay measurement value is relative to host A’s t ₁ minus relative at t ₂ of host B; finally calculate the clock skew of the two hosts

This formula is obtained by taking into account the existence of the clock rate ratio and the change of the clock deviation during the clock synchronization process, and has good robustness.

First of all, it does not require other special equipment, such as GPS, etc., so it has a very low cost; in the formula, the factors that generate clock asynchrony, that is, the clock rate ratio and the clock bias change that affects the synchronization accuracy are taken into account, so that this method can be obtained The offset formula for calculating the clock deviation ensures that the clock synchronization has good robustness; finally, because this method uses the inherent properties of the host clock, it has good burst resistance while ensuring accuracy.

Embodiment two

In this embodiment, the performance of this method and NTP in dealing with network uncertainty and host uncertainty is observed by simulating the processing time of two hosts A, B and host B, and by changing the clock rate ratio or host processing time.

Figure 3 is a LAN simulation with a delay of 1000us and a deviation of 100, which reflects the experimental results that the processing time remains unchanged and the frequency increases. Find in the experiment, under the same situation of server processing time, two kinds of methods except the error produced because of the difference of round-trip delay, along with the increase of frequency ratio, the error of NTP obviously increases, and the method of the present invention then only has The reason for the increase of small fluctuations is that the method of the present invention considers the impact of different clock rates on clock synchronization, thus having better robustness.

Figure 4 is a LAN simulation, the clock rate ratio is 1.001, the delay is 1000us, and the deviation is 500, which reflects the experimental results that the frequency is constant and the processing time is increased. From the experimental results, it can be seen that the frequency ratio of the two machines is constant. Next, in addition to the error caused by the difference in the round-trip delay of the two methods, i.e. the slight fluctuation of the curve, the longer the server processing time, the greater the error produced by the NTP method, and the method of the present invention is due to consideration of the server processing time. unaffected, resulting in better robustness.

Embodiment three

In this embodiment, an experiment of a robust network clock synchronization method is carried out based on the NIST simulation platform, please refer to FIG. 1 and FIG. 2 . In this embodiment, "network" is replaced by a NIST simulation platform, which is used to control the network situation, by giving exact different network delay values, observing and utilizing the method of the present invention and the NTP method after clock synchronization, comparing the delay measurement value and The relationship between the values set by NIST shows that this method also has good robustness in actual synchronization. Figure 5 shows the one-way delay measurement values measured after synchronization by the two methods respectively. At this time, the delay measurement value set by NIST is 105ms.

The client initiates a clock synchronization request, the server receives the request and waits for 10s, which is used to simulate that the server is busy, then sends a response packet, uses NTP and the method of the present invention to perform clock synchronization on the client side, and then continues to send delay measurement packets to On the server side, by observing the change of the measured delay value after synchronization over a period of time, it can be concluded that it still increases according to the trend of the clock rate ratio F obtained by using linear programming. Simultaneously the data that the method of the present invention obtains is above the data that NTP obtains, and here it is said that NTP fluctuates around a certain value, and the method of the present invention is caused by fluctuations around zero; on the other hand the present invention The first delay measurement value of the method, that is, the value just after synchronization is also closer to 105ms, which also illustrates that the method of the present invention is facing a lot or synchronization due to the frequency ratio (F=S/C) being greater than 1. When the process time is too long and the offset changes greatly, the clock synchronization can be performed better, and it has good robustness. Among them, S refers to the clock rate of the foreign host, and C refers to the clock rate of the local host.

In short, clock synchronization is within the scope of the claims of the present invention by obtaining a large amount of time stamp information, using various mathematical methods to obtain the clock rate ratio, and then using the formula in this method to calculate the clock deviation to complete clock synchronization.

The description and application of the invention herein is illustrative and is not intended to limit the scope of the invention to the above-described embodiments. Variations and changes to the embodiments disclosed herein are possible, and substitutions and equivalents for various components of the embodiments are known to those of ordinary skill in the art. It should be clear to those skilled in the art that the present invention can be realized in other forms, structures, arrangements, proportions, and with other elements, materials and components without departing from the spirit or essential characteristics of the present invention.

Claims (3)

1. a network clock synchronization method, is characterized in that, described method comprises the steps: Step 1. Obtain the delay measurement value according to the one-way transmission of the time-stamped data packet between the local host and the foreign host, and then use linear programming to obtain the clock rate ratio F of the local host and the foreign host; Step 2, then obtain the clock offset offset according to the interactive transmission of data packets with time stamps between the local host and the foreign host and the clock rate ratio F; Step 3, performing clock synchronization between the local host and the foreign host according to the clock deviation; The detailed steps of the network clock synchronization method are: Step A, the local host A sends a large number of data packets with the sending time stamp T _i to the foreign host B; Step B, the foreign host B receives the data packet, and obtains the delay measurement value d _i according to the sending time and receiving time; Step C, according to the transmission time T _i and the measured delay value d _i , use linear programming $\mathrm{<span\; class="notranslate">\; min</span>}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&beta;</span>}<span\; class="notranslate">\; \}</span>$ d _i -(F-1)T _i +β≥0,1≤i≤N Get the clock rate ratio F; β is related to the current clock deviation; Step D, the local host A sends a request packet with a sending time stamp _t1 to the foreign host B; Step E, the foreign host B records the time _t2 of receiving the request packet; Step F, foreign host B writes t ₂ and the time t ₃ of sending the response packet in the response packet and replies to the local host A; Step G, the local host A records the time _t4 of receiving the response packet; Step H, local host A uses the formula according to time t ₁ , t ₂ , t ₃ , t ₄

Get the clock deviation of the two hosts to complete clock synchronization. 2. The network clock synchronization method according to claim 1, wherein the specific implementation method of said step 1 is: The local host sends a large number of data packets with sending timestamps to the foreign host; The foreign host obtains the delay measurement value d _i according to the sending time and receiving time of different data packets; According to the sending time, receiving time and delay measurement value d _i , use linear programming to obtain the clock rate ratio F of the local host and the foreign host. 3. network clock synchronization method according to claim 2, is characterized in that, the specific implementation method of described step 2 is: The local host sends a request packet with sending timestamp t ₁ to the foreign host; The foreign host records the receiving time _t2 after receiving the request packet; The foreign host replies to the local host with a response packet with a receiving timestamp _t2 and a sending timestamp _t3 ; The local host records the time t ₄ of receiving the response packet; According to the clock skew formula

Get the clock skew of the local host and the foreign host.

Images