United States Patent (19)
`Brent et al.
`
`(73) Assignee:
`
`54 PACKET TRANSMISSION SYSTEM
`75 Inventors: Jason B. Brent, Newport Beach,
`Calif.; Edward Hatala, Devizes,
`England
`Cray Communications Limited,
`Surrey, United Kingdom
`21 Appl. No.: 64,270
`(22
`Filed:
`May 19, 1993
`30
`Foreign Application Priority Data
`May 19, 1992 GB United Kingdom ................. 9210646
`5ll int.C. ........................................... HO4, 12/56
`52 U.S. C. ...................................... 370/60; 370/94.1
`58) Field of Search .................. 370/108, 105.1, 100.1,
`370/94.1, 60, 13, 16, 60.1, 58.1-58.3, 94.2
`References Cited
`U.S. PATENT DOCUMENTS
`4,775,987 10/1988 Miller .................................. 370/108
`4,800,560 1/1989 Aoki et al. .......................... 370/108
`4,817,085 3/1989 De Prycker ........................ 370/108
`5,212,690 5/1993 Löw .................................... 370/108
`FOREIGN PATENT DOCUMENTS
`0016477 10/1980 European Pat. Off. .
`0130431 1/1985 European Pat. Off. .
`0234859 9/1987 European Pat. Off. .
`2261799 5/1993 United Kingdom.
`
`56
`
`US005381408A
`Patent Number:
`11
`45 Date of Patent;
`
`5,381,408
`Jan. 10, 1995
`
`WO84/00268 1/1984 WIPO .
`WO91/02419 2/1991 WIPO .
`Primary Examiner-Wellington Chin
`Assistant Examiner-Ajit Patel
`Attorney, Agent, or Firm-Young & Thompson
`57
`ABSTRACT
`A packet transmission system in which variable delays
`are compensated for by packetizing an input signal so as
`to produce packets at a predetermined packet frequency
`(3), allocating a sequence number to each packet (6),
`transmitting these packets over a network to an end
`point (7), and forming the packets into an output signal
`at the endpoint by reference to their sequence number
`(12) and by delaying each as necessary (9, 10) so that
`they are all delayed by substantially the same predeter
`mined delay time with reference to the packet fre
`quency. Preferably, the delay in the transmission of
`each packet through the network is measured by con
`parison of the time of arrival of the packet at the end
`point relative to a timing signal (11) synchronized with
`or running plesiochronously with the predetermined
`packet frequency. The endpoint delay is then set so that
`the sum of the measured delay and the endpoint delay is
`substantially equal to the predetermined delay time,
`which is assessed as the maximum delay for acceptable
`output signal quality.
`
`9 Claims, 2 Drawing Sheets
`
`PACKETIZER
`
`
`
`TRANSMITTER
`
`NTERVAL
`GENERATOR
`
`Page 1 of 5
`
`SAMSUNG EXHIBIT 1008
`
`

`

`U.S. Patent
`
`Jan. 10, 1995
`
`Sheet 1 of 2
`
`5,381,408
`
`PACKETZER
`
`
`
`TRANSMITTER
`
`
`
`INTERVAL
`GENERATOR
`
`SEQUENCE
`6 NUMBER
`GENERATOR
`FG 2
`
`CLOCK
`
`RECEIVER
`
`
`
`BUFFER
`
`DE-PACKETZER
`
`
`
`BUFFER
`CONTROLLER
`
`FG.3.
`
`Page 2 of 5
`
`

`

`U.S. Patent
`
`Jan. 10, 1995
`
`Sheet 2 of 2
`
`5,381,408
`
`
`
`TRANSMT
`
`NETWORK DELAYBUFFER DELAY
`FIG.A.
`
`NO OF
`PACKETS
`
`FIG.5.
`
`TIME
`
`Page 3 of 5
`
`

`

`1.
`
`PACKET TRANSMISSION SYSTEM
`
`TECHNICAL FIELD
`This invention relates to a packet transmission system
`and a method of, and means for compensating for 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 queu
`15
`ing of the packets in storage means and are random in
`nature. The time stamp field therefore records an accu
`mulated value of the variable delay in traversing the
`network, this being an especially important parameter
`when packets are used to transmit voiceband informa
`20
`tion, the received quality of which deteriorates unac
`ceptably unless some form of variable delay compensa
`tion is provided. However, the use of a time stamp field
`in this manner increases the overhead for the packets
`and involves additional processing capacity at each
`25
`node in the network.
`DISCLOSURE OF THE INVENTION
`An object of the present invention is to provide a
`packet transmission system in which variable delays can
`30
`be compensated for more simply than in the known
`systems.
`This is achieved according to the present invention
`by packetizing an input signal so as to produce packets
`at a predetermined packet frequency and allocating a
`35
`sequence number to each packet, transmitting these
`packets over a network to an endpoint, and forming the
`packets into an output signal at the endpoint by refer
`ence to their sequence number and by delaying each as
`necessary so that they are all delayed by substantially
`the same predetermined delay time with reference to
`said packet frequency.
`Preferably, the delay in the transmission of each
`packet through the network is measured by comparison
`of the time of arrival of the packet at the endpoint rela
`45
`tive to a timing signal synchronised with or running
`plesiochronously with said predetermined packet fre
`quency. The endpoint delay is then set so that the sum
`of the measured delay and the endpoint delay is substan
`tially equal to said predetermined delay time, which is
`SO
`assessed as the maximum delay for acceptable output
`signal quality. Thus, variable transmission delays are
`accommodated within a predetermined maximum ac
`ceptable delay time which is preferably adaptively ad
`justed by reference to the measured delay times of suc
`55
`cessive packets so that it is reduced to a minimum.
`The invention therefore avoids the need for time
`stamping at each node of a network, and instead by
`continuously producing sequenced packets at a prede
`termined frequency, the packet transmission delays can
`be readily measured at the endpoint with reference to
`this packet frequency and compensated for within said
`predetermined maximum acceptable delay time.
`DESCRIPTION OF THE DRAWINGS
`65
`The invention will now be described by way of exam
`ple with reference to the accompanying drawings in
`which:
`
`10
`
`5,381,408
`2
`FIG. 1 is a schematic diagram of a packet transmis
`sion system,
`FIG. 2 is a schematic diagram of the originating end
`point of packets in the system of FIG. 1,
`FIG. 3 is a schematic diagram of the terminating
`endpoint of packets in the system of FIG. 1,
`FIG. 4 is a diagram showing the timing sequence of
`packets within the system of FIG. 1, and
`FIG. 5 is a diagram illustrating the distribution of
`measured variable delay times in the system of FIG. 1.
`MODE OF CARRYING OUT THE INVENTION
`The packet transmission system illustrated schemati
`cally in FIG. 1 comprises a network of interconnected
`packet switching nodes 1 with endpoint devices 2 con
`nected to them so that they can communicate with one
`another via the network. Data is transferred between
`the endpoints 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.
`Each endpoint device 2 is capable of acting as an
`originating endpoint device which produces and trans
`mits packets, or a terminating endpoint device which
`receives packets. FIG. 2 shows an endpoint device 2
`when operating as an originating endpoint. In these
`circumstances, a synchronous voiceband signal (e.g.
`digital voice, facsimile or video data) is received at a
`packetizer device 3 and formed into packets in a contin
`uous manner. The packets are produced at a predeter
`mined timing interval as determined by a clock 4 and a
`packetization interval generator 5. A sequence number
`generator 6 is driven from the interval generator 5 and
`allocates a sequence number to each interval, which
`sequence number is inserted in the header of the associ
`ated packet. A transmitter 7 receives the packets from
`the packetizer and transmits these to the network for
`delivery via the nodes 1 to a terminating endpoint de
`vice 2, such as shown in FIG. 3.
`At the terminating endpoint, the packets are received
`by a receiver 8 which reads the sequence number from
`the header of each and writes this to a buffer controller
`9 before passing the packet onto a buffer 10. The buffer
`controller 9 operates in synchronism with the packeti
`zation interval through a clock 11 synchronised with
`the clock 4 driving the packetization interval generator
`5. The function of the buffer controller is to release
`packets from the buffer 10 at the correct timing so that
`each arrives at a de-packetizer 12 a predetermined time
`delay after the corresponding synchronisation signal,
`this time delay being sufficient to accommodate vari
`able delays in the network.
`The manner in which the buffer controller 9 operates
`can be better understood with reference to the timing
`diagram of FIG. 4 which shows an example of a packet
`interval of 20 m.sec. and a predetermined delay time of
`30 msec. A packet sequence number 1 arrives at the
`receiver 8 after suffering a delay in the network of 8
`msec. The buffer controller 9 measures this delay from
`the arrival time of the packet and the timing signal from
`clock 11, and calculates that an additional delay time of
`22 msec. is required to give a total delay time of 30
`msec. The packet is therefore delayed in the buffer 10
`for a further 22 msec. before it is released to the de
`packerizer 12.
`
`Page 4 of 5
`
`

`

`5,381,408
`3
`4.
`Similarly, the time of arrival of the packet sequence
`tween said transmitting means and said packet process
`number 2 at the receiver 8 is monitored and the network
`ing means, analyzing means connected to the timing
`delay time of 14 msec. calculated. This packet is then
`means to analyze the times of arrival of said packets at
`delayed in the buffer 10 for a further 16 msec. It will be
`the endpoint so as to determine a distribution character
`noted that this second packet is passed to the de-packe
`istic for them, and adapting means connected to the
`tizer 1220 m.sec. after the first packet so that the packet
`analyzing means and the delaying means to adapt said
`interval is maintained at the terminating endpoint.
`predetermined time delay in accordance with variations
`The buffer controller 9 analyses the measured delay
`of said distribution characteristic so as to control the
`times in the network and produces a distribution count
`quality of said output signal.
`as shown in FIG. 5 which it uses to determine the opti
`5. A packet transmission system as claimed in claim 4
`10
`Inum predetermined delay time so that it can vary this in
`in which the timing means comprises clock means that
`an adaptive manner to suit the operating conditions of
`generates a timing signal synchronized with or running
`the system.
`plesiochronously with said predetermined packet fre
`We claim:
`quency, and delay measuring means connected to the
`1. A method of compensating for delays in a packet
`packet processing means and said clock means to mea
`transmission system comprising packetizing an input
`sure the transmission delay of each packet by reference
`signal so as to produce packets at a predetermined
`to the time of arrival of the packet at the endpoint and
`packet frequency, allocating a sequence number to each
`the timing signal.
`of said packets, transmitting said packets in sequence
`6. A packet transmission system as claimed in claim 4
`over a network to an endpoint, processing said packets
`20
`in which said adaption means sets said predetermined
`to form an output signal at said endpoint by reference to
`time delay at a minimum acceptable value in accor
`the sequence numbers allocated to them, recording the
`dance with a predetermined quality for said output
`time of arrival of said packets at the endpoint, delaying
`signal.
`said packets at the endpoint by a variable delay so that
`7. A packet transmission delay compensating system
`each packet is delayed by a predetermined time delay
`comprising packet processing means to receive packets
`between transmitting said packets and processing said
`from said network and to produce a corresponding
`packets at said endpoint, analyzing the times of arrival
`output signal by reference to transmission sequence
`of said packets at the endpoint so as to determine a
`numbers allocated to the packets during transmission,
`distribution characteristic for them, and adapting said
`timing means connected to the packet processing means
`predetermined time delay in accordance with variations
`for timing the arrival of said received packets, delaying
`of said distribution characteristic so as to control the
`means connected to the packet processing means for
`quality of said output signal.
`delaying the packets by a variable delay so that each
`2. A method as claimed in claim 1 in which the time
`packet is delayed by a predetermined time delay be
`of arrival of each packet at the endpoint is recorded
`tween transmission and processing by said packet pro
`relative to a timing signal synchronized with or running
`35
`plesiochronously with said predetermined packet fre
`cessing means, analyzing means connected to the timing
`means to analyze the times of arrival of said packets at
`quency and used to measure the transmission delay.
`the endpoint so as to determine a distribution character
`3. A method as claimed in claim 1 in which said pre
`determined time delay is set at a minimum acceptable
`istic for them, and adapting means connected to the
`value in accordance with a predetermined quality for
`analyzing means and the delaying means to adapt said
`said output signal.
`predetermined time delay in accordance with variations
`4. A packet transmission system comprising packetiz
`of said distribution characteristic so as to control the
`quality of said output signal.
`ing means to transform an input signal into packets at a
`predetermined packet frequency, packet numbering
`8. A packet transmission delay compensating system
`means connected to said packetizing means to allocate a
`as claimed in claim 7 in which the timing means com
`45
`sequence member to each of said packets in sequence,
`prises clock means that generates a timing signal syn
`transmitting means connected to said packet numbering
`chronized with or running plesiochronously with the
`means to transmit said packets in sequence over a net
`frequency of transmission of said packets, and delay
`work to an endpoint, packet processing means to re
`measuring means which measures the transmission
`ceive packets from said network at said endpoint and
`delay of each packet by reference to the time of arrival
`50
`produce a corresponding output signal by reference to
`of the packet and the timing signal.
`the sequence numbers allocated to them, timing means
`9. A packet transmission delay compensating system
`connected to the packet processing means for timing the
`as claimed in claim 7 in which said adaption means sets
`arrival of packets at the endpoint, delaying means con
`said predetermined time delay at a minimum acceptable
`nected to the packet processing means for delaying said
`value in accordance with a predetermined quality for
`55
`packets at the endpoint by a variable delay so that each
`said output signal.
`packet is delayed by a predetermined time delay be
`
`25
`
`15
`
`30
`
`65
`
`2k
`
`Et
`
`Ek
`
`2k
`
`Page 5 of 5
`
`