Patent Publication Number: US-5428616-A

Title: Measuring packet transmission delays

Description:
TECHNICAL FIELD 
     This invention relates to a packet transmission system and a method of measuring the delays of packets in such a system. 
     It is known in a packet switching system to provide each packet with a time stamp field in which to record delays incurred as the packet traverses the system. In particular, it is known to measure the variable time taken by each packet to traverse each node of a packet switching network and to add this time to the time stamp field. Delays across the node are caused by queuing of the packets in storage means and are random in nature. The time stamp field therefore records an accumulated value of the variable delay in traversing the network, this being an especially important parameter when packets are used to transmit voiceband information, the received quality of which deteriorates unacceptably unless some form of variable delay compensation is provided. 
     In one known system, U.S. Pat. No. 4,506,358, two time stamp fields are employed, one for the accumulated delay and the other for the arrival time of the packet at a node input. These values are then used with the time that the packet is outputted from the node to update the accumulated delay stamp field. In another known system, disclosed in U.S. Pat. No. 4,894,823, only one time stamp field is employed and this is updated both at the input and output of the node by subtracting the current value in the time stamp field from the time of arrival at the input, and adding the time that the packet is outputted from the node. The use of just one time stamp field reduces the overhead for the packet, but only by introducing an additional time processing step at the node input which in turn adds complexity. 
     DISCLOSURE OF THE INVENTION 
     An object of the present invention is to provide a packet transmission system in which variable delays can be measured more simply than in the known systems. 
     This is achieved according to the invention by measuring the time which each packet spends in an output queue of each node and adding this time to a time stamp field of the packet. The invention assumes that the delay between the arrival of a packet at the input node and the arrival of the same packet in an output queue is substantially fixed, or at least varies by a negligible amount compared with the time spent in an output queue. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     The invention will now be described by way of example with reference to the accompanying drawings in which: 
     FIG. 1 is a schematic diagram of a packet switching network, 
     FIG. 2 is a schematic diagram of a packet switching node as used in the network of FIG. 1, 
     FIG. 3 is a diagram of marker signals used in the node of FIG. 2, and 
     FIG. 4 is a diagram showing the format of a packet within the node of FIG. 2. 
    
    
     MODE OF CARRYING OUT THE INVENTION 
     The packet switching network illustrated schematically in FIG. 1 comprises a plurality of interconnected packet switching nodes 1 some of which have input/output terminal devices 2 connected to them so that they can communicate with one another via the network. Data is transferred between the terminals 2 in the form of packets within a frame format known as frame relay. Each packet has a header including a logical address field by means of which it is routed through the network. Each node refers to the logical address field in order to select the appropriate output to which to route it. As shown in FIG. 2, each node includes a number of input buffers 3 to receive incoming packets and transfer these to appropriate output buffers 4 via a parallel bus 5 under the control of input and output controllers 6 and 7. 
     The bus 5 is 8 bits wide and packets are transmitted on it in 8 bit bytes within the slots of a time frame defined by a 4 kHz frame marker signal S FR  generated by a clock 8 and applied to a clock line 9 of the bus. Typically, each frame is divided into 6144 time slots, and all of the input and outputs to the bus are synchronised to this slotted frame format by reference to the frame marker signal S FM  as shown in FIG. 3. The input controller 6 controls the allocation of the time slots for the transmission of packets across the bus, and allocates pairs of consecutive slots, M and M+1 being a typical pair, for the transmission of each packet so that a multiple of 16 bits is transmitted per frame at a rate of 4 kHz. The output controller 7 shares the slot allocation information with the input controller 6, and controls the receipt of packets from the bus by the output buffers 4, 4&#39;, as described hereinafter. 
     Each incoming packet is processed in an input buffer 3, 3&#39; and, as applied to the bus 5, has a header H with a plurality of information fields shown in FIG. 4, including an address field AD, a priority field PR and a time stamp field TS. The address field AD contains a logical address LA derived from the incoming packet and a bus address BA which is added in the input buffer 3 under the control of the input controller 6 and corresponds to the address of one of the output buffers 4 or 4&#39; through which the packet is to be routed to the next node 1 or a terminal device 2. Every time a packet from an input buffer 3 or 3&#39; is applied to the bus 5, the input controller 6 applies a packet address marker S PA  to a control line 10 of the bus to coincide with the address field AD in the packet header. This control line 10 is connected to the output controller 7 which responds to the packet address marker S PA  by causing all of the output buffers 4, 4&#39; to read the address field of the associated packet. That output buffer 4 or 4&#39; which recognises the bus address BA as its own, is triggered to receive the whole of that packet, which it then passes to a corresponding output packet store 11 or 11&#39; after removing the bus address from the address field. 
     Each output packet store 11, 11&#39; comprises a buffer which stores the packets it receives in a plurality of FIFO queues each corresponding to a different priority level of the packets. This priority level is identified for each packet by reference to the priority field PR in the packet header which has been added in the input buffer 3 or 3&#39; under the control of the input controller 6 and is deleted once the packet has been directed to a queue. A packet controller 12 controls the order in which the queues are accessed to transfer packets to the output of the store for transmission onwards via a respective line controller 13, 13&#39;. The frequency with which each queue is accessed depends on the priority level of that queue, although any particular queue can be given absolute priority over all others if required, so that this queue is emptied before any of the other queues are accessed. 
     Considering time delays in the transmission of any packet across the node, there is a minimal variable time delay in the transmission of the packet between the input of the input buffer 3 and input of the output packet store 11. The input buffer 3 only has a limited capacity sufficient to buffer the incoming packet data to adapt it for application to the bus, and this delay is fixed. The bus 5 involves a transmission delay corresponding to a possible timing difference between the arrival of a packet and the occurrence of the next allocated pair of time slots. At maximum, this delay equals the period between successive pairs of time slots, which for a 4 kHz frame marker signal S FR  has a maximum value of 250 microseconds. The output buffer 4 operates to receive a complete packet before this is transferred to the output packet store 11, and this incurs a delay corresponding to the packet size. Thus, for any packet switch connection, there is a maximum variable delay time for the transmission of a packet through the node to the output packet store. 
     The delay incurred in the output packet store 11 is variable and depends upon the priority level of each packet and the length of the corresponding queue to which it is allocated. Under normal operating conditions, this delay is long compared with all other possible variable delays. 
     The time stamp field TS in the header of each packet is used to provide an accumulative value of the variable transmission delays incurred by storage of a packet in the output packet stores 11, 11&#39; of the network. The packet controller 12 includes a timing function represented as 14 in FIG. 2 which serves to measure the time each packet spends in a queue of each output packet store 11, 11&#39;, and adds this time to that recorded in the time stamp field TS of the packet header before the packet is outputted from the store. This can be achieved by the timing function 14 subtracting the current time from the time stamp field TS of each packet as it arrives in an output packet store 11,11&#39;, and adding the current time to the time stamp field TS of each packet as it leaves an output packet store 11,11&#39;.