Abstract:
A method ( 60; 70 ) for processing data packets allows the same hardware that is used in a traffic-forwarding path to add timestamps to the data, which allow accurate measurements to be taken. By adding this function in the forwarding equipment itself, the measurements can be taken in a true operational network, i.e., under actual usage conditions. Moreover, if multiple systems in the traffic path support this functionality, the value of the measurements is enhanced to enable end-to-end path guarantees. One exemplary embodiment ( 10 ) of the present invention uses synchronized clocks to provide timestamps for use in performance monitoring within an operational system. Synchronized clock signals can be used to accurately time stamp incoming and outgoing packets to provide performance measurement of traffic through the system under actual operating conditions.

Description:
RELATED APPLICATIONS 
   This application claims the benefit of U.S. Provisional Application No. 60/421,183, filed Oct. 25, 2002 by the same inventors, entitled “Use of Synchronized Clocks to Provide Input and Output Time Stamps for Performance Measurement of Traffic within a Communications System.” This application is also related to U.S. Provisional Application No. 60/421,303 entitled “IP Measurement Protocol” and filed on Oct. 25, 2002 by one of the same inventors. 

   FIELD OF THE INVENTION 
   The present invention is directed generally to methods and apparatuses for transmitting data packets over computer networks, and more particularly to a method and apparatus for transmitting data packets over a public computer network via switches and routers for which quality of service is significant. 
   BACKGROUND 
   Packet based data communications (e.g., IP traffic) is evolving from a best effort delivery system to a system for supporting applications that require a defined quality of service, at least in terms of latency and jitter. Currently, it is not possible to measure latency and jitter for actual user traffic in an operational packet forwarder, such as an IP switch or router. 
   Existing switches and routers do not support such measurements by injecting measurement information, such as timestamps. Test equipment vendors can provide accurate timestamps only by connecting test equipment to the interfaces under test and injecting test traffic. This requires expensive external equipment, is invasive in nature and is not an operational measurement as interfaces must be disconnected from the network and connected to the test equipment. Moreover, such a test configuration can only test the equipment under test—not a path through a network. 
   The present invention is therefore directed to the problem of developing a method and apparatus for enabling performance testing and measurement of individual network equipment, as well as a network path, in a true operational fashion. 
   SUMMARY OF THE INVENTION 
   The present invention solves these and other problems by providing inter alia a method for processing data packets that allows the same hardware that is used in a traffic-forwarding path to add timestamps to the data, which allow accurate measurements to be taken. By adding this function in the forwarding equipment itself, the measurements can be taken in a true operational network, i.e., under actual usage conditions. Moreover, if multiple systems in the traffic path support this functionality, the value of the measurements is enhanced to enable end-to-end path guarantees. 
   According to another aspect of the present invention, an exemplary embodiment of a method for processing data packets inserts time stamps upon receipt and also upon transmission. Moreover, by employing a single clock source from which both the input and output time stamps are derived, an exemplary embodiment of the present invention removes clock uncertainty from the timestamps, thereby enabling an accurate measurement of latency and other aspects of a network device processing the data packets. 
   According to another aspect of the present invention, one exemplary embodiment of the present invention uses synchronized clocks to provide timestamps for use in performance monitoring within an operational system. For example, the synchronized clock signals in the Motorola Broadband Service Router (BSR) 64000 can be used to accurately time stamp incoming and outgoing packets to provide performance measurement of traffic through the system under actual operating conditions. 
   According to one aspect of the present invention, an accurate clock reference is derived from either an internal hardware clock or an external clock source, such as a“BITS” (Building Integrated Timing Supply) clock, a synchronous interface, such as SONET, or a GPS receiver. The clock signal is converted to a convenient frequency for internal use (e.g., low enough to be delivered to all interface cards with sufficient integrity, but high enough to provide the required accuracy). The signal is distributed to interface cards via hardware (e.g., using dedicated traces in a mid-plane or back-plane PCB). The timing signal is delivered to the forwarding subsystem of each line card. If transmitting is done in hardware, such as an FPGA or ASIC, the timing signals are provided to the transmitting hardware itself. If firmware or software transmission is used (e.g., a network processor or CPU) the timing signals are converted into a form which can be read by the forwarding software (e.g., placed in a register). 
   According to another aspect of the present invention, during packet transmission each packet is inspected for the presence of a field in the packet header, which field indicates timestamps should be added (e.g., IPMP). If time stamping is indicated, the current value of the clock is inserted. Note that for maximum value the input time stamp should be inserted as soon as possible after packet reception and the output time stamp as late as possible before transmission. 
   According to another aspect of the present invention, the above process can be used to provide latency statistics through an Internet device, by double stamping and recording the difference between the two stamps. This can also be done in a compliant manner by comparing the first stamp to the real time clock to get the difference and then overwriting the stamp, or just leaving the first stamp in place. By combining synchronized clocks used for RF synchronization in the BSR64000 with the Internet Measurement Protocol, the present invention provides a powerful technique for establishing the performance of an Internet device. 
   Other aspects of the present invention will be apparent to those reviewing the following drawings in light of the specification. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  depicts a block diagram of an exemplary embodiment of a System Timing and Clock Distribution Subsystem according to one aspect of the present invention. 
       FIG. 2  depicts a table of Stratum  3  Timing Module Operational Modes according to another aspect of the present invention. 
       FIG. 3  depicts a block diagram of an exemplary embodiment of a BITS Clock Interface according to still another aspect of the present invention. 
       FIG. 4  depicts a block diagram of an exemplary embodiment of a BITS Clock Redundancy system according to yet another aspect of the present invention. 
       FIG. 5  depicts a block diagram of an exemplary embodiment of a SONET Clock Extraction system according to yet another aspect of the present invention. 
       FIG. 6  depicts a flow chart of an exemplary embodiment of a method for processing packets in a network according to still another aspect of the present invention. 
       FIG. 7  depicts a flow chart of another exemplary embodiment of a method for processing packets in a network according to still another aspect of the present invention. 
       FIG. 8  depicts an exemplary embodiment of a network operating according to another aspect of the present invention. 
   

   DETAILED DESCRIPTION 
   It is worthy to note that any reference herein to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment. 
   One application of the present invention enables the testing of a device for compliance with the Expedited Forwarding Per-Hop Behavior, as described in IETF RFC 3246 (which is hereby incorporated by reference as if repeated herein in its entirety). This is accomplished by inserting a timestamp in the packet both when it is received and when it is transmitted. By comparing the timestamps of when packets were received and when they were transmitted it can be determined if the device transmitted the packets in a manner which conformed to the requirements of RFC 3246. In general any test which attempts to determine if a given packet or packets were transmitted in the correct order, or at the correct time, based on the time that they were received, either individually or as a group may be performed by using this double time stamping approach. The present invention does not require that IPMP packets be used in which to place the timestamps, rather, any packet containing sufficient room to hold the timestamps may be employed for the purposes herein. 
   Nevertheless, some of the embodiments of the present invention employ an Internet Protocol Measurement Protocol (IPMP) as set forth in the above mentioned U.S. Provisional Patent Application, which U.S. Provisional Application No. 60/421,303 is hereby incorporated by reference as if repeated herein in its entirety, including the drawings. 
   The following sets forth the electrical architecture and functional behavior of the synchronous clocking support for the BSR64000 system. Similar designs and functions can be implemented in any packet forwarding or Internet device. 
   The clocking subsystem is composed of the following components:
         BITS clock source   SONET clock Source   System Timing and Clock Distribution       

   The BITS and SONET clock sources provide alternate sources for an external reference clock to be used. The system timing and clock distribution module allows selection of the clock source to be used and distribution of the derived clock signals through the system. 
   System Timing and Clock Distribution 
   A System Timing and Clock Distribution subsystem is provided for management of multiple synchronization-input references, and to provide flexible synchronization distribution throughout the system.  FIG. 1  shows a block diagram of the System Timing and Clock Distribution subsystem  10 , which consists of the following functional blocks:
         Input Reference  11     Stratum  3  Timing Module  12     Clock Distribution  13 
 
Input Reference
       

   The Input Reference block  11  consists of Low Voltage Differential Signaling (LVDS) receivers  11   a  and dual 16:1 Multiplexers  11   b ,  11   c . The input reference block  11  receives 8 kHz clocks from two different sources. One source is the BITS clock that is derived from an external E1/T1 network (not shown), and the other is derived from SONET Trunking modules in the system (not shown). 
   Two 16:1 MUXes  11   b ,  11   c  each accept sixteen input reference clocks, two TTL level 8 kHz clocks from the Ti transceivers, and fourteen LVDS differential 8 kHz clock, one from each SONET module (not shown) in the system. System software can control the source selected by each 16:1 MUX through the SFB FPGA Clock Distribution and Control interface (not shown). The output of each MUX  11   b ,  11   c  supplies the primary and secondary reference inputs to the Stratum  3  module  12 . 
   Stratum  3  Timing Module 
   The Stratum  3  Timing Module  12  is used as the system timing reference. It is synchronized to a primary and secondary 8 kHz input reference signals and generates two output reference clocks signals, 19.44 MHz and 10 kHz. The 19.44 MHz and 10 kHz clocks feed the clock distribution interface  13 , which distributes the clock signals to each resource module slot on the system midplane  14 . Two programmable inputs allow system software controls of the operating modes in the timing module  12  through the SFB Clock Distribution and Control interface. Six output signals provide status and notify the supervisor CPU when an alarm condition has occurred in the module. 
   Table 1 shown in  FIG. 2  details the Stratum  3  timing module operational modes and associated status and alarm states. 
   Clock Distribution 
   The clock distribution block  13  receives 19.44 MHz and 10 kHz clocks from the Stratum  3  timing module  12 . LVDS clock repeaters  13   a ,  13   b  supply the 19.44 MHz and 10 kHz clocks differentially to each resource module slot on the system midplane  14 . The clock repeaters  13   a ,  13   b  supplying the 19.44 MHz and 10 kHz clock groups to each midplane slot  14  share a common control signal which allows system software to enable either 19.44 MHz or 10 kHz to the slot based on the type of resource module plugged in. 
   The Trunk Interface Module (not shown) synchronizes to 19.44 MHz, and the CMTS module synchronizes to 10 kHz. 
   BITS Clock Interface 
   The SRM7410 (control card for BSR 64000) provides two E1/T1 interfaces that are used primarily to receive synchronization timing from a Building Integrated Timing Supply (BITS). BITS timing information received over the E1 or T1 network is used for timing synchronization in the BSR 64000 system. 
   As shown in  FIG. 3 , the E1/T1 subsystem  20  is implemented using PMC Sierra PM4351 Combined E1/T1 transceiver/Framer (COMET) devices  21   a ,  21   b , Stratum  3  Timing module  22  and the MPC8260 (element  23 ). The E1 (2.048 Mbit/s) or T1 (1.544 Mbit/s) frames flow from the BITS network through the SRM7410 I/O module  24  to COMET devices ( 21   a ,  21   b ) on the SRM7410 via the system midplane  25 . 
   All COMET framing, alarms, and operating modes are software configurable through an 8-bit processor interface controlled by the Supervisor CPU (MPC8260). The COMET recovers 8 kHz clocks from E1/T1 frames sourced by the BITS; these clocks are selected via a selector to be used as an input reference to the Stratum  3  Timing module  22 . The Stratum  3  Timing module  22  performs clock regeneration. 
   BITS Clock Redundancy 
   The SRM7410 I/O module  24  provides E1/T1 BITS clock access ports to both SRM7410 modules in the system. The block diagram  30  in  FIG. 4  shows the redundant BITS clock connections from I/O access ports  33  to SRM7410s (elements  31   a ,  31   b ). 
   SONET Clock 
   A reference clock source can be derived from the SONET network interface and delivered to the system timing module(s) via the BSR midplane  32 . 
   This function is implemented in the SONET Trunk Interface Module and provides two 8 KHz reference signals to redundant timing modules located on the SRMs  31   a ,  31   b . This enables the system to synchronize off of any SONET port within any Trunk Interface Module. This task is accomplished using the RX-FRAME-OUT pin of the S1201 (CONGO) devices. This output provides an 8 KHz signal based on received frames. Since there are as many as four ports in a Trunk Interface Module, a multiplexer is used to select the desired recovered receive 8 KHz signal for delivery to the SRM modules. 
     FIG. 5  shows a block diagram of an exemplary embodiment  40  of a circuit used, which includes a selector  41  and a TTL to LVDS fanout buffer  42 . 
   Turning to  FIG. 6 , shown therein is an exemplary embodiment  60  of a method for processing one or more packets in a network. In step  61 , a first time stamp is inserted upon receipt of the packet by a network device. In step  62 , a second time stamp is inserted upon transmitting of the packet by the network device, wherein the first time stamp and the second time stamp are either both derived from a single clock source or from different clock sources operating synchronously with respect to each other. In step  63 , a header of the packet is inspected upon receipt of the packet and the first time stamp and the second time stamp are inserted if the header indicates a time stamp should be inserted. Alternatively, this step  63  could occur by inspecting a header of the packet upon receipt of the packet and not inserting the first time stamp or the second time stamp unless the header indicates a time stamp should be inserted. 
   Turning to  FIG. 7 , shown therein is another exemplary embodiment  70  of a method for processing packets in a network according to another aspect of the present invention. In step  71 , a first time stamp is inserted in a received packet upon receipt and a second time stamp is inserted in the received packet just prior to transmitting the received packet, if upon receipt inspection of the header indicates that a time stamp should be inserted. In step  72 , the first time stamp to the second time stamp are compared to obtain a difference between the first and second time stamps. In step  73 , either the first or second time stamp is overwritten with the difference and/or the difference is recorded elsewhere in the received packet. 
     FIG. 8  shows an exemplary embodiment of a computer network  80 , which includes several network devices  81 ,  83 ,  86  to receive and forward a plurality of packets. These network devices are coupled to one another over one or more networks  82 ,  84  and possibly via one or more firewalls  85 . Each network device  81 ,  83 ,  86  includes an input/output module or processor  81   a  to insert a first time stamp upon receipt of each of the plurality of packets and to insert a second time stamp prior to transmission of each of the plurality of packets. Each of the network devices also includes a clock source  81   b  coupled to the input/output module, said clock source to generate a clock signal from which the first time stamp and the second time stamp are derived. The input/output module  81   a  inspects a header of the packet upon receipt and inserts the first time stamp and the second time stamp if the header indicates a time stamp should be inserted. 
   Other hardware implementations will be apparent to those of skill in this art upon review of the above. 
   Where the insertion of the timestamp may be desired, it may also be performed by associating the timestamp with the packet as well as any information that would be needed to decide to insert the timestamp, such as the incoming interface number. The actual insertion of the timestamp may then be performed at a later point or subsequent point in the processing of the packet, but the effect would be as if the timestamp was inserted at the earlier time or point in the packet processing. The same can also apply to insertion of the second time stamp. The act of deciding to insert the timestamp can be performed early in the packet processing and the result of the decision can be then associated with the packet, such as inserting a flag, and the actual timestamp can then be inserted later or subsequently in accordance with the earlier decision. 
   As used herein, network device can also refer to a module within a network device so that performance can be measured on a module basis or across one or more modules in a series within a network device. In general, a network device as used herein is simply a device that processes packets in network. 
   Although various embodiments are specifically illustrated and described herein, it will be appreciated that modifications and variations of the invention are covered by the above teachings and are within the purview of the appended claims without departing from the spirit and intended scope of the invention. For example, certain versions of Internet Protocol are used in the above descriptions, but subsequent versions may also be applicable. In addition, the above description relates to the Motorola BSR 64000, but the inventions herein could be implemented in any packet forwarding or Internet device. Furthermore, these examples should not be interpreted to limit the modifications and variations of the invention covered by the claims but are merely illustrative of possible variations.