Method for providing a precise network time service

[0002] This invention relates to providing timing information in communications networks and specifically to providing frequency and universal time information in communications networks.

[0003] Communications networks are required to deliver a variety of services over expansive geographic areas. With the increasing demand for multimedia services these networks are more and more required to deliver information that the networks were not initially designed for. Consequently new methods are constantly being developed to modify the network or enhance past network functions so that new services can be offered while meeting quality of service requirements. In some instances not only has the network proven inefficient in implementing new services but many strategies and concepts that were previously satisfactory have proven less useful as new services are conceived.

[0004] These new services deliver many different forms of information, including text, voice, and video to many different users; that information may be conveniently classified as either a time based stream or a non-time based stream. A time-based stream is a continuous flow of time sensitive information. That is, a time-based stream contains information wherein a timing component associated with each unit of information must be received or played back according to the timing component relative to the other units of information. For example, when either audio or video information is sent directly to a human interface, the time position of each unit of audio or video information is critical to the intelligible reception of the information. As a consequence, time based information places strict delay, bandwidth, and loss rate requirements on communications networks as the information must often be transported as a contiguous unit. In contrast, non-time based streams do not place the same constraints on the network. This is the case because non-time based information streams contain information that is for later consumption. Some examples of non-real time information include email messages or files. These forms of information may, for example, be held in queue until network bandwidth is available for transmittal.

[0005] Whether the information stream traversing the network is time-based or non-timed based, network timing information plays an important role in the operation of communications networks. In particular, as the information arrives at a Customer Premise Equipment (CPE), the CPE may have to recover precise frequency and universal time (i.e., time of day) information and make other time related measurements.

[0006] In order for transmitted data to be recovered at a receiver the transmitter and receiver must be synchronized. This typically requires the recovery of the frequency of the incoming data stream. The conventional approach to synchronization in the public switched telephone network (PSTN) has been to employ a hierarchical structure of progressively more accurate clocks. At the top of the hierarchy was the most accurate clock source. Signals from the clock source at the top of the hierarchy propagated downstream through the network to less accurate clocks and eventually to the network elements transporting the information. This approach to clock distribution worked quite well for the circuit switched PSTN because the PSTN essentially delivered information continuously in real time to its destination.

[0007] The PSTN hierarchical approach to timing distribution, however, has provided some complications for packet switched networks. In packet switched networks traffic patterns are often bursty, i.e., the information may not be transmitted continuously in real time to its destination. Therefore, a particular receiver is not always receiving information from a particular transmitter. When a packet is eventually received and timing information is recovered, the receiver clock may be skewed relative to the transmitter clock. Accordingly, departures from the hierarchical approach for synchronizing nodes in packet switched networks had to be made to reliably deliver information.

[0008] One such departure has been the use of universal time information. Universal time information is used to monitor the performance of cell based networks. For example, the time of day may be used to measure delay and throughput. In practice, a cell leaving its origination point may be stamped with the time of the day according to the originating CPE. When that cell arrives at its destination point, the time of day placed into the cell may be compared to the time of the day at the destination point. The difference between the time at the origination and destination points is a measure of the delay through the network.

[0009] Another departure from the approach to timing used in the PSTN is deployment of algorithms or protocols that are transmitted with and used to interpret the timing information communicated between a timing source and destination in a packet switch network. Different protocols have been developed throughout the communications industry to provide synchronization and universal time information in cell based networks. One such protocol is the Network Timing Protocol (NTP). NTP provides the mechanisms to synchronize and coordinate time distribution in a large, diverse internet operating at rates from a few kilobits/second to lightwave rates, e.g., gigabit/second. NTP uses a returnable-time design in which a distributed subnet of time servers operating in a self-organizing, hierarchical-master-slave configuration synchronizes local clocks within the subnet and to national time standards via wire or radio. The servers can also redistribute reference time via local routing algorithms and time daemons. NTP provides the protocol mechanisms to synchronize time in principle to precision on the order of nanoseconds while preserving a non-ambiguous date.

[0010] Architecturally, NTP requires a number of primary reference sources that are synchronized by wire or radio to national standards, e.g., the atomic clock in Boulder, Colo. These primary reference sources are operated as primary time servers and are usually connected to national standards by Global Positioning Systems (GPS). These primary time servers are connected to widely accessible resources such as backbone gateways. Subsets of these backbone gateways or local net hosts act as secondary time servers. By using NTP time keeping information is communicated from the primary time servers to other time servers over the internet. As such, the architecture over which NTP is deployed is similar to that implemented in the digital telephone system. The information communicated from these primary time servers is used to cross-check clocks and make up for errors due to equipment or propagation delay. The secondary servers run NTP along with one or more primary servers. In order to simplify the protocol the secondary servers distribute timing via NTP to the remaining local-net hosts.

[0011] In the end NTP is designed to produce three outputs: (1) clock offset, (2) roundtrip delay, and (3) dispersion. In simple terms, clients, e.g., workstations, transmit NTP messages requesting from the secondary time servers information that allow the clients to determine the server time with respect to the local client time and to adjust the local client clock.

[0012] NTP has some inherent limitations. While NTP can be used for monitoring delay and throughput, it achieves 1-50 millisecond accuracy. This translates to an accuracy of more than 17,000 cell periods on a 156 Mb/s link and more than 700,000 cell periods on a 622 Mb/s link. At such rates, transient congestion will be extremely difficult, if not impossible, to diagnose using the NTP protocol. Furthermore, in order to achieve millisecond accuracy NTP requires the use of complex and intricate algorithms.

[0013] Adaptations to NTP, such as Simple Network Timing Protocol (SNTP), have been implemented that allow delivery of time accurate to the order of microseconds without the complexity of the NTP. SNTP has some drawbacks. A SNTP client cannot be the source of timing for another SNTP or NTP client. Furthermore, SNTP servers must be synchronized by a stratum 1 source directly provided from a reliable radio or time service. Finally, SNTP is not as reliable as NTP and is usually not recommended for use in primary servers. As such, SNTP, while providing adequate accuracy, presents many limitations as to its use.

[0014] Accordingly, a method for providing precise frequency and universal time information and related time measurements at CPEs without the need for special or expensive components, such as GPS receivers, while having better than millisecond accuracy would be of utility.

[0015] My invention is a method for providing precise frequency and universal time information and related measurements at a CPE without the need for special and expensive components such as GPS hardware.

[0016] By my method after the CPE requests service activation, the minimum round trip time between a time server and the CPE is calculated. Based on the minimum round trip time the CPE and time server are synchronized. Once synchronized the time server and CPE then continually compensate for different transmit or receive delays based on the minimum round trip time. Based on these simple steps the time server and CPE maintain synchronization accurately without the complexity of the NTP.

[0017] An advantage of my invention is that several uni-directional cell/frame delay measurements may be obtained including end-to-end propagation delay, congestion, cell delay variation, cell transfer delay, and traffic throughput.

[0018] My invention is also advantageously approximately 100 times more accurate than NTP, providing accuracy of approximately 10 microseconds.

[0019] My invention also advantageously allows network traffic to be time stamped and correlated with any other network element supported by a time server anywhere in the world.

[0020] In addition, as previously mentioned, my invention allows for unidirectional and bidirectional delay measurements. This represents an improvement over prior art performance monitoring tools such as ping and traceroute which can measure delay but usually rely on roundtrip times. As such, these tools cannot distinguish the difference between delays in the forward and reverse directions. Because my invention does not depend on end-to-end loop back timing, I am able to accurately measure uni-directional delay which is a fundamental improvement over the prior art.

[0021] My invention is also able to accurately monitor one of the most common network problems, congestion. As those in the art are aware, the best method for monitoring congestion is to monitor the queue lengths of all the nodes used in a virtual connection. However, monitoring in this manner is rather complex. In contrast my invention offers a simple and accurate method for monitoring congestion.

[0022] My invention is also able to qualify point-to-multipoint, multipoint-to-point and n source to m destination connections. Prior art monitoring tools such as ping and traceroute cannot be used to qualify multipoint connections.

[0023] Finally, my invention may be used to identify and localize the source of network problems.

[0024] These and other advantages of my invention may be realized by reference to the drawings and detailed description described below.

[0025] FIG. 1 is an Asynchronous Transfer Mode (ATM) network time service utilizing my invention;

[0026] FIG. 2 is a state diagram illustrating the steps of a precise network time service in accordance with my invention;

[0027] FIG. 3 is an illustrative state diagram of the substeps executed during one of the steps of FIG. 2; and

[0028] FIG. 4 is a state diagram illustrating the steps for compensating for different transmit or receive delay times as indicated in FIG. 2.

[0029] Turning to FIG. 1 there is depicted an Asynchronous Transfer Mode (ATM) network time service utilizing my invention. Two timing networks, i.e., network 100 and network 160, are illustrated in FIG. 1. In network 100, a Global Positioning System (GPS) 105 provides timing 110 to a first network provider time server 120. The time server 120 in turn supplies frequency and universal time information 121 through 129 to customer premise equipment (CPE) 131 through 139, respectively. CPEs 131 through 139 transmit and receive information or data over paths or links 141 through 149 to CPEs 161 through 169, respectively, in timing network 160. CPEs 161 through 169 derive timing information along paths 171 through 179, respectively, from a second network provider time server 180. Time server 180 in turn uses GPS 191 as a source of timing 190. GPS 191 may be the same GPS as GPS 105 or an entirely different GPS. In accordance with my invention timing paths 121 through 129 and 171 through 179 are each a low bandwidth virtual connection of less than 16 kilobits/second (kb/s) that should have no affect on active user applications and specifically may advantageously be approximately 10 kHz.

[0030] Although FIG.1 depicts two timing domains, i.e., network 100 and network 160, my invention, as described below, can be implemented in any number of domains. In fact, as data flows back and forth between CPEs 161 and 131, for example, the data will traverse many timing domains each possibly being timed by a different time server. Furthermore, although FIG. 1 illustratively depicts only nine CPEs being supported within each domain, each time server is expected to support thousands of CPEs simultaneously.

[0031] Turning now to FIG. 2 there is depicted the method steps 200 for implementing a precise network time service on a timing network, such as timing network 100 of FIG. 1, in accordance with my invention. Initially, a user or CPE 131 initiates the process by requesting precise network timing service as illustrated by step 201. Step 201 can actually be done at any time the user establishes a network connection or when the CPE is powered up.

[0032] Responsive to the request for service, step 201, the time server 120 calculates the minimum reasonable delay (e.g., lowest 5 percentile) defined as a Minimum Round Trip Time (MRTT) between the time server 120 and the CPE 131, step 202. In calculating the MRTT, step 202, the time server 120 sends priority Operation, Alarm, and Maintenance (OAM) cells to CPE 131 via path 121 over the course of a few minutes at a rate of approximately 10 kHz, step 203. The CPE 131 then loops back the received OAM cells to the time server 120, step 204. Based on steps 203 and 204 the time server 120 is able to calculate the MRTT. It should be noted that in calculating the MRTT in accordance with my invention, step 202 should work well even if the CPE 131 is sending or receiving user traffic along data path 141 because it is assumed that a majority of the OAM cells may have experienced some queuing delays. Therefore, by taking the lowest 5 percentile the effects of queuing delays are ignored. Note, however, MRTT may be improperly calculated in accordance with my invention if: (1) CPE 131 or a competing CPE is sending or receiving Continuous Bit Rate (CBR) traffic on the link 121 that is used to connect the time server 120 to CPE 131; or (2) all the OAM cells are delayed through a source shaping/pacing mechanism or a User Network Interface/Network Network Interface (UNI/NNI) shaping mechanism. Step 202 may be continually repeated and filtered over the life of the connection to ensure that the MRTT value is accurate.

[0033] The time server 120 and CPE 131 are then synchronized, step 210. The synchronization process, step 210, once initialized is repeated for the duration of the connection. The substeps for achieving synchronization are shown in FIG. 3. As FIG. 3 shows, the process is initiated by time server 120 sending a primary timing cell to the CPE 131, step 301. The primary timing cell sent by the time server 120 includes the time the primary timing cell was sent by the time server 120. The CPE 131 immediately loops back or returns the primary timing cell upon receiving it to the time server 120, while at the same inserting the time the CPE 131 sent the timing cell back to the server 120, step 304. The loopback performed as part of step 304 does not involve the host processor and operates similarly to ABR RM cells at the destination. If the calculated round trip time of the returned primary timing cell (at the server 120) is outside the MRTT, the returned primary cell is ignored and step 301 is repeated. On the other hand, if the time server 120 receives the returned primary timing cell within (less than or equal to) the MRTT, then it immediately sends a secondary timing cell to the CPE 131, step 307. If the CPE receives the secondary timing cell within the MRTT, then the secondary timing cell is considered a valid timing cell and is used to immediately synchronize the CPE timer. Of course, if the CPE-calculated round trip time is not within the MRTT then the process returns to step 301. Note however, that even where the CPE timer is synchronized according to steps 301, 304, and 307, the process is continually repeated. The CPE timer is synchronized to the time server using conventional filtering and phase locked loop methods.

[0034] Once the time server 120 and the CPE 131 are synchronized, the minimum cell transfer delay is calculated at both the time server 120 and CPE 131 so different transmit/receive delays may be compensated for. In particular, and as shown in FIG. 4, the CPE 131 will send to the time server 120 an OAM timing cell that includes a transmit time stamp in the payload, step 401. The time server then uses the received OAM cell to compute the one way transfer delay by subtracting the transmit time of the cell from the actual time the OAM cell was received, step 404. Step 404 is repeated over a period of time to develop a set or plurality of one way transfer delays. The time server 120 then uses the results of repeating step 404 to calculate the minimum reasonable delay, which I have defined as the minimum cell transfer delay (MCTD), from the CPE 131 to the time server 120. Specifically, the minimum reasonable delay or MCTD is the lowest 5 percentile of the one way transfer delays from time server 120 to CPE 131. If the MCTD is one half of the MRTT, then the transmit/receive delays are the same.

[0035] The MCTD is also calculated in a similar manner from the time server 120 to CPE 131. Specifically, the time server 120 sends an OAM timing cell having a transmit time stamped in the payload to the CPE 131, step 405. Upon receiving this OAM cell the CPE 131 subtracts the transmit time from the actual received time, step 406, to compute a one transfer delay from the time server 120 to the CPE 131. As OAM cells having a time server 120 transmit time stamp are received at CPE 131, a plurality of time server 120 one way transfer delays are accumulated. The CPE 131 repeats the subtraction using the accumulated delays thereby computing the MCTD from the time server 120 to the CPE 131.

[0036] The sum of the MCTD in both directions should add up to the MRTT. In addition the process may be continually repeated and filtered to ensure accurate time server to CPE MRTT and vice versa.

[0037] The MCTD values computed are continually used by the host processor and the CPE timer to maintain the accuracy of the timing information. Specifically, the time server to CPE MCTD is always subtracted from the CPE timer whenever it is read by the host processor. As is known in the art, each incoming cell or frame includes a unique cell/frame identifier such as Virtual Path (VP)Nirtual Circuit (VC) identifier. Accordingly, the incoming time (adjusted for time server to CPE MCTD) can be logged in an on-board frame table. The frame table is accessed by the Virtual Path (VP)Nirtual Circuit (VC) and frame identifier and therefore a host processor can later access the frame table to determine the exact time any given frame was received. Likewise the time server to CPE MCTD value is always subtracted from the CPE timer before embedding a time stamp into outgoing traffic.

[0038] The end product of my invention may be used to improve network performance. For example, the timing information stored along with the table entries may be used to implement policies for deleting table entries. For example, a table entry may be deleted based on its age or via some least recently used algorithm.

[0039] In addition, my method allows for unidirectional and bidirectional delay measurements. Because my invention does not depend on end-to-end loop back timing, I am able to accurately measure unidirectional delay which is a fundamental improvement over the prior art. This represents an improvement over arrangements which can measure delay but usually rely on roundtrip times. As previously mentioned, prior art performance monitoring tools such as ping and traceroute cannot distinguish the difference between delays in the forward and reverse directions.

[0040] My invention is also able to accurately monitor one of the most common network problems, congestion. As was discussed above, the minimum end-to-end delay is one of the measurements automatically made by my invention. This value is a measure of the propagation and transmission delay, which is nearly constant for SONET/ATM networks. This value may also be associated with an uncongested end-to-end connection (i.e., no additional queuing delays). Accordingly, values above the minimum value are usually suggestive of queuing delays or congestion assuming that the traffic is not being shaped/paced at the source or user network interface. As such, my invention offers a simple and accurate method for monitoring congestion in lieu of monitoring the queue lengths of all the nodes used in a virtual connection.

[0041] The above description is exemplary of my invention. Numerous modifications and variations may be made by those skilled in the art without departing from the scope and spirit of my invention.