![[INET 2000]](/web/20160103035804im_/http://www.isoc.org/inet2000/cdproceedings/inet00sm.gif)
![[ Up ]](/web/20160103035804im_/http://www.isoc.org/inet2000/cdproceedings/up.gif)
![[Prev]](/web/20160103035804im_/http://www.isoc.org/inet2000/cdproceedings/prev.gif)
![[Next]](/web/20160103035804im_/http://www.isoc.org/inet2000/cdproceedings/next.gif)
The Internet is distributedly managed by various organizations, and this fact makes it difficult to solve problems without the cooperation of these organizations. Recently, the Internet has begun to be used in business, and in these situations, the users request high network performance for the delay and the throughput, for example, in the usage of the server and client environments. But, in the Internet it is impossible to guarantee network performance because the Internet is made of many sub-networks, which are distributedly managed by their own policies. Now, when the administrator of the server or the Internet provider gets a complaint of network service trouble from the user, a system that can specify the trouble point between the server and the client without the collaboration of the other providers is very helpful. As a candidate to solve this problem, we propose NTP (network time protocol) to measure delay and jitter between them. In this paper, we also describe the method of applying the system in real environments to decide whether the trouble comes from our network or the other one.
We installed a precise time synchronization system using ISDN (integrated services digital network). This system is incorporated into the packet-monitoring system described in the next section to deliver precise time-stamp. By adding time-stamp to a packet at a large number of points, we can observe the one-way delay between these points. Details of the system components are described below.
NTP [1] is a standard protocol for time synchronization in the Internet. In this protocol, a client requests the server to report its time, and the client sets its own clock (fig 1) according to the time reported from the server. Thus the precision of the client time relies on the server. From our experiences, in the local area network (LAN), if the server and the client belong to the same Ethernet segment, the propagation delay between them is a few hundred microseconds (fig 2). Ethernet congestion incurs a millisecond delay. In NTP, the client knows the current time from the server and estimates the packet one-way delay. This client assumes that the packet one-way delay is equal to half of the packet's round-trip time. On the other hand, congestion occurs only in one way: it causes a time error of a few microseconds in the estimation of the one-way delay, because congestion delay is larger than packet propagation delay. For example, a 500 microsec in the clock means 3000 bit error on 6Mbps leased line. This bit error also corresponds to one packet time error when the packet length is about 300 bytes. In fact, it is usual that there are no NTP servers on the same segment, and an NTP server belonging to the different segment is used. Then, we must count the possibility of an even larger error.
Figure 1: NTP server and client
| Remote | Delay | Offset | Dispersion |
|---|---|---|---|
| WAN | 241.8 | 4.06 | 1.16 |
| ISDN dialup | 57.1 | 1.12 | 0.63 |
| LAN | 1.2 | -0.00 | 0.05 |
In NTP, time dispersion of network delay causes instability of the clock in network probes. Figure 3 and 4 are graphs of RTT (Round Trip Time) and clock difference on y-axis and the elapsed time in seconds after the midnight on x-axis between NTP servers. Figure 3 and 4 indicate stable and unstable states of the network, respectively. In these graphs, clock difference is calculated by subtracting incoming delay from outgoing delay. When outgoing delay is larger than incoming delay, clock difference has positive value. From these graphs, we can observe that there are no relationships between incoming delay and outgoing delay. This fact shows that we cannot assume that one-way packet delay is a half of the packet round trip time, and we need a special network for time synchronization.
Figure 3: NTP delay in stable network
Figure 4: NTP delay in unstable network
In order to avoid the errors described above, network stability is indispensable for realizing a time synchronization system. The conditions for network stability are as follows:
We chose the system ISDN clock server and client system [2] for the purpose. This system uses an ISDN network for the server and the client connection to prevent packet congestion, and it is a stable network. The ISDN line clock delivered by the telephone carrier is very precise, so we can ensure precision by using this clock as our standard.
Global positioning system (GPS) is an alternative candidate for obtaining precise time as a source. But if there is no router near the roof then we need to work hard to install the GPS antenna. In this system, if there is an ISDN line near the router, we can get the time easily. This system has the advantage in this point.
The clock server system (fig 5) installed for this experiment contains a GPS clock system, which can obtain the correct time by means of the GPS satellite. The clock server uses a 1-pps (pulse per second) and 10-MHz clock delivered from the GPS clock system, and a clock client is connected to a clock server using an ISDN line.
The GPS clock system receives the time from the GPS satellite. The clock device in this system uses the time received from the satellite and generates a 1-pps pulse and 10-MHz signal. The clock server uses an ISDN board on a Sun workstation as the clock device. This clock is deemed to be error-free because this system uses an ISDN line clock, and it distributes precise time via the ISDN line to the clock client. The clock client is also a workstation that has an ISDN board with a clock device. It is very precise because it also uses the ISDN line clock.
Figure 5: Clock system
The clock server and the client have an NTP server to distribute time information through the Internet. The NTP client accesses the NTP server using a UDP (user datagram protocol) packet in order to get time. The NTP client obtains the time using the packet and the estimated packet propagation delay. It also has the internal clock. The server replies to the time request from the client systems. This system is set up such that both the clock server and the client behave as NTP servers.
We are now trying to transfer the time between one clock server and three clock clients. To compare the clock server system with the traditional Internet NTP system, clock server is arranged by switch to refer to both its board and the Internet NTP server. The cumulative distribution of the observed dispersion is shown in figure 6. Fifty microsecond errors mean a 300-bit error on a 6-Mbps leased line.
Figure 6: ISDN clock server vs. NTP
Figure 7: Traffic measurement environment
NTP is known as one of the time synchronization methods in the Internet. To detect the time difference between our side and the other side, NTP assumes that incoming delay is the same as outgoing delay. But actually, when congestion occurs, incoming delay is not the same as outgoing delay; then we use some clocks to reduce errors.
NTP packets are exchanged between clients and servers with the time interval ranging from one to twelve minutes in order to measure time difference. These packets tell us incoming and outgoing delay if these clocks are completely synchronized. But when only one pair of NTP server and client is available and the pair is not proved to be time synchronized, we cannot measure incoming and outgoing delay correctly. To keep clock precision, we need to prepare as many pairs as possible.
In this case, the route between X and Y is overlapped by the route from X to A and X to B (fig 7). The delay from X to A is the sum of the delay from X to Y and the delay from Y to A. We can also divide the path from X to B into the path from X to Y and the path from Y to B. When the delay from X to Y is changed by some reason it influences the delay both from X to A and from X to B. On the other hand, when the delay from Y to A is changed, the delay of X to A is changed, while the delay from X to B is not. So we can separate the delay from X to Y from the delay from Y to A.
When the delay movement from X to A is similar to the one from X to B, we can regard the delay movement as coming from the one from X to Y. When not, we can regard the delay movement as coming from the intrinsic delay movement from Y to A and from Y to B, respectively. We evaluate the performance of this algorithm below.
We installed the clock server with GPS antenna on the roof of our office to gather time information. We also installed the clock client near the server for NTP reference server to the Internet. We observe network statistics whole Internet using this NTP server. The NTP servers observe the other Internet NTP servers. So we make it a collector of one-way delay. And we use it to observe the delay per part of the Internet from delay information on NTP servers.
We try to detect the collision using the delay information classify the NTP server to the Y and the Y to NTP client.
Based on the above idea, we formalized the method below. At first the time
when the delay is observed is denoted by t. The start time is denoted by S, the
end by E. So S < t < E. We denote one-way delay by 
, one-way delay from P to Q as 
We estimate the one-way delay between P and Q by the apparent time
difference of the NTP servers and the round-trip delay between them. For
example one-way delay from P to Q denoted by 
can be
obtained by the sum of a half of round trip delay and the apparent time
difference of the NTP server. Because the round-trip delay and the time
difference from packet observation is 
, 
.
We pay attention to the one-way delay of either outgoing or incoming
packets. In our framework, one-way delay , is
divided into two components. 
which varies with time,
and 
which doesn't vary with time. These values
satisfy
Based on this framework, we formalize how to estimate the delay from X to Y
using the delay data from X to A and from X to B. We denote one-way delay from
X to A, and from X to B, as 
,
, their time-variable components 
,
, and the time-constant components 
,
, respectively. Then, if difference
between and is little,
we know is similar to
.
We assume the minimum value of the time-constant component of and well approximates the
time-constant component of 
. We furthermore assume
the time-variable component of and have similar characteristics when the difference of the time
variable components is small. This means and have similar values on 
and
.
We assume the similar value can well approximate the time-variable component
of the 
element. Then we use the average of
time-variable element of and as time-variable component of the delay of 
. When the difference between and is small, we can show the following equation about the
delay between X and Y approximately holds.
In this case, we know the delay from X to Y using the delay data from X to
A, and from X to B. But if there is a great difference between and , this method cannot be used. When
there is a great difference, we can estimate that the values of the components
of 
and 
are much larger
than the value of element in and . So, in this case, we cannot
calculate delay with precision. For this case, we
need to prepare C, D ... instead of A, B, and to measure the delay with
precision of , 
or 
and 
.
When there is a great difference between and
, we assume delay can
be approximated by 
.
Figure 8 shows an example of evaluation results of the proposed algorithm for estimating delays in network segments. Three graphs for bottom to top show the delay from X to A, the delay from X to B, and the estimated delay from X to Y, respectively. These graphs indicate that the proposed algorithm well estimate the delay from X to Y in the area where the difference between the delay from X to A and the delay from X to B is small. On the other hand, the algorithm cannot well separate the delay from X to Y in the area where the difference between the delay from X to A and the delay from X to B is great. Furthermore when the delay occurs in the segment from X to Y, the delay pattern occurred in the segment from X to A is sometimes different from the pattern occurred in the segment from X to B. For this case, the algorithm cannot well estimate the delay from X to Y, and the algorithm should be improved by analyzing the reason why the delay pattern from X to A is different from the one from X to B.
Figure 8: The delay from X to A, X to B, X to Y
We implemented the one-way delay observation system based on the NTP protocol by incorporating the GPS and ISDN clock delivery mechanism. We also proposed an algorithm that can separate the delay into portions occurred in the network segments by using the overlapping information of the path segments in the routes from the NTP client to servers. The algorithm well estimated the delay that occurred in the overlapped segment when two delay patterns that occurred in the routes including the overlapped segment rather resemble each other. We will improve the algorithm for separating the delay well even when the delay patterns are rather different from each other by combining the delay data for more than three NTP servers.
[1] David L. Mills, "Network Time Protocol (Version 3) Specification, Implementation." RFC 1305, March 1992.