Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-07-11
2004-03-16
Pham, Chi (Department: 2667)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S347000, C370S444000, C370S528000
Reexamination Certificate
active
06707821
ABSTRACT:
FIELD OF THE INVENTION
This present invention relates generally to voice-over-packet-network and similar time-critical packet transmission, and more particularly to systems and methods for interleaving time-critical packets with lower-priority packets on a common data link without inducing significant jitter and/or delay in the time-critical packets.
BACKGROUND OF THE INVENTION
Packet-switched networks route data from a source to a destination in packets. A packet is a relatively small sequence of digital symbols (e.g., several tens of binary octets up to several thousands of binary octets) that contains a payload and one or more headers. The payload is the information which the source wishes to send to the destination. The headers contain information about the nature of the payload and its delivery. For instance, headers can contain a source address, a destination address, data length and data format information, data sequencing or timing information, flow control information, and error correction information.
A packet's payload can consist of just about anything that can be conveyed as digital information. Some examples are e-mail, computer text, graphic, and program files, web browser commands and pages, and communication control and signaling packets. Other examples are streaming audio and video packets, including real-time bidirectional audio and/or video conferencing. In Internet Protocol (IP) networks, a two-way (or multipoint) audio conference that uses packet delivery of audio is usually referred to as Voice over IP, or VoIP.
The urgency with which a given packet should be delivered depends to a great extent on the type of payload. E-mail and background file transfers are among the least urgent, as delays of minutes can usually easily be tolerated. On the other end of the spectrum, VoIP packets typically must be delivered within a few hundred milliseconds of their creation, or VoIP call quality begins to degrade noticeably. Other relatively high-priority packets can include data link flow control packets and network node status packets.
Since high-priority packets and low-priority packets must share the packet network, various schemes have been proposed to provide fair allocation of network resources between the two. For instance,
FIG. 1
illustrates a portion of a device
20
, e.g., implemented on a computer, that multiplexes VoIP packets and other data packets onto a common data link using a priority queuing mechanism. The VoIP packets are created by digitally encoding a voice capture channel (e.g., from a microphone or headset) using an AID (analog-to-digital) converter
22
and a voice encoder
26
. Data packets are received from other applications running on the computer, e.g., a web-browser, e-mail application, or networked file system application.
Device
20
uses two packet queues. A time-critical-packet queue
28
queues VoIP packets as they are created. A data packet queue
36
queues lower-priority packets. Note that in
FIG. 1
, data packets pass through an optional data packet fragmenter
34
, which segments large data packets into sequences of smaller data packets before submission to queue
36
. Note also that signal packets from controller
24
are submitted to data packet queue
36
. The signal packets provide overall coordination of VoIP call setup and termination, among other things, and may optionally be placed in queue
28
.
Packet scheduler
30
multiplexes packets from queues
28
and
36
to data link interface
32
. Under one prior art method of operation, scheduler
30
selects time-critical packets from queue
28
until queue
28
is emptied. When queue
28
is empty, scheduler
30
then selects packets from data packet queue
36
. When queue
28
receives one or more additional time-critical packets, scheduler
30
switches back to queue
28
until that queue is once again empty.
The priority operation of scheduler
30
can be better understood with reference to the timing diagrams of
FIGS. 2
,
3
, and
4
. Referring first to
FIG. 2
, a single talkspurt on the voice capture channel is represented. The overall duration of the talkspurt is tTS
1
.
Voice encoder
26
groups voice samples from A/D converter
22
into voice sample blocks
1
-
1
,
1
-
2
, . . . ,
1
-
8
. Each sample block represents the same fixed number of voice samples, e.g., 80 samples, 240 samples, etc. Because the number of samples is fixed, block
1
-
8
extends past the end of the talkspurt in order to take in the appropriate number of samples.
Voice encoder
26
encodes each sample block into a voice packet. Simple encoders may do no more than place the entire sample block in a packet payload and attach addressing headers. More sophisticated encoders may compress the sample block using a variety of known coding techniques. In either case, the encoder cannot place a voice packet in packet queue
28
until sometime after the entire sample block is received at encoder
26
—if sophisticated coding must also take place, additional delay may occur while the data is compressed.
FIG. 2
illustrates the packet formation delay, tPF, as the time between when the first sample of a sample block is generated and when the packet corresponding to that sample block is queued.
When the time-critical packets do not have to compete for data link bandwidth (and the bandwidth of the channel is large compared to packet size), total packet transmission delay is not much greater than packet formation delay. Packet transmission delay, tTX, is the time between when the first sample of a sample block is generated and when transmission of the packet corresponding to that sample block has completed.
It is believed to have been heretofore unrecognized that time-critical packet transmission can be negatively affected, even with priority queuing.
FIG. 3
shows packet transmission delay when two data packets are placed in data queue
28
shortly after voice packet VP
1
.
1
is placed in queue
26
. Once VP
1
.
1
has been placed on the data link, queue
26
is empty. Scheduler
30
thus checks queue
36
, finds data packet DP
1
waiting, and selects that data packet for transmission. While the data packet is transmitting, voice packets VP
1
.
2
, VP
1
.
3
, and VP
1
.
4
arrive at queue
26
. Thus, a four-packet delayed “burst” of voice packets occurs at the end of data packet DP
1
transmission. With queue
26
once again empty, data packet DP
2
from queue
36
is selected for transmission, causing another four-packet burst of voice packets to occur. In addition to the voice sample “bursting” phenomenon, data packet transmission has caused the transmission delay tTX for voice sample block
1
-
2
, for example, to be substantially longer than the comparable delay in FIG.
2
.
FIG. 4
shows the same scenario as
FIG. 3
, but using data packet fragmenter
34
to segment the two data packets of
FIG. 3
into eight smaller data packets. Although this tends to improve the regularity of voice packet transmission and lessen the average voice packet transmission delay, the problem is not completely cured.
SUMMARY OF THE INVENTION
The disclosed embodiments address the interleaving of time-critical packets, such as VoIP packets, with lower-priority packets on a common data link. It has now been recognized that priority queuing can cause the time-critical packet jitter and absolute latency problems shown in FIG.
3
—particularly on low-speed data links where the transmit time for a maximum transmission unit (MTU) data packet is on the order of (or larger than) the time spacing between consecutive voice packets. Furthermore, is has also now been recognized that an approach different from data packet fragmentation is also desirable. Not only does fragmentation not completely diminish the negative effects of priority queuing, but data packet fragmentation is generally undesirable, often difficult, and sometimes impossible to achieve.
In general, the disclosed embodiments determine when lower-priority packets can be sent with a low probability of introducing jitter or latency in a time-sensitive packet d
Khouri Joseph F.
Knappe Michael E.
Shaffer Shmuel
Cisco Technology Inc.
Hoang Thai
Marger Johnson & McCollom
Pham Chi
LandOfFree
Time-sensitive-packet jitter and latency minimization on a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Time-sensitive-packet jitter and latency minimization on a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time-sensitive-packet jitter and latency minimization on a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3292231