Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-07
2004-06-29
Pham, Chi (Department: 2667)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06757284
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to pipeline sorting of ordered streams of data items, which may be used to sort timestamps of data items within a packet switching system, and to providing jitter buffers at various switching stages of a packet switch.
BACKGROUND OF THE INVENTION
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ systems having greater speed and capacity (i.e., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Packet technology typically allows a plurality of information types to be transmitted over the same transmission lines and using the same packet switching systems and devices.
As used herein, the term “packet” is used to indicate generically addressable information packets of all types, including fixed length cells and variable length packets. Moreover, the information contained in such packets could represent one or more of an unlimited type of information, including voice, data, video, and audio information. Furthermore, the term “system” is used generically herein to describe one or more systems, networks, computer or communication devices or mechanisms, or combinations thereof.
Consumers and designers of these systems typically desire increased performance at a reasonable price. A commonly used technique for helping to achieve this goal is for these systems to provide multiple paths between a source and a destination. Packets of information are then dynamically routed and distributed among these multiple paths. It is typically more cost-effective to provide multiple slower rate links or switching paths, than to provide a single higher rate path. Such designs also achieve other desired performance characteristics.
An artifact of using dynamic routing is the need to resequence each of the streams of packets dynamically routed through a packet switch to an output port respectively back into their original order. Moreover, improved methods and systems for sequencing and resequencing of data items in this and other communications and computing environments are needed. Some packet switches manipulate an actual packet of information (including payload), while other packet switches manipulate a data item representing a packet rather than the whole packet for certain operations. The invention covers these and other variants of packet switch implementations.
Merge sorting, illustrated in
FIG. 1
, is a known technique for producing a single sorted list from multiple ordered lists whose values are known a priori. For example, two lists
920
and
922
of known elements sorted in ascending order can be combined into a single sorted list
924
by repeatedly taking the smaller value from the top of lists
920
and
922
and appending the smaller value to the end of list
924
. This example can be extended to a set of known n values, which can be sorted by first dividing the set into n lists containing a single value each, then combining pairs of lists to produce n/2 lists with two values each. Pairs of these lists are then merged, producing n/4 lists with four values each. Continuing in this fashion eventually yields a single sorted list containing the original values, but in sorted order, as shown in FIG.
1
. Merge sorting can also be implemented using three-way merging (that is, merging three sorted lists into a single sorted list in one step) for three lists of known items, rather than by using two-way merging. More generally, d-way merging is possible for any integer d>1 for sorting d sorted lists of known values.
However, known sorting techniques are not candidates for resequencing streams of packets in a packet switching environment. In such a dynamic environment, lists of known values are not available. In dynamic resequencing systems, a complete set of packets to be resequenced is routinely not available at the time resequencing decisions must be made. Furthermore, the resequencing process is additionally complicated because the streams of packets to be resequenced can be temporarily empty.
New methods, apparatus, and systems for sequencing and resequencing information in a dynamic environment are needed, including those which perform resequencing dynamically routed packets in a packet switch.
Additionally, because of congestion within a packet switch dynamically routing packets, the time required for a packet to traverse the packet switch will vary substantially, which is sometime referred to as packet “burstiness” within the packet switch. When packets of an ordered packet stream arrive at an output interface before previous packets of the stream, these early arriving packets must be held in buffers until the previous packets arrive. Typically, a significant number of buffers must be placed in the output interfaces of a packet switch to hold these packets. Needed are new methods, apparatus, and systems for reducing the burstiness of packet traffic within a packet switch.
SUMMARY OF THE INVENTION
A method is disclosed for producing a single ordered stream of data items. An embodiment partitions the ordered streams of data items into a plurality of groups. Then, the processes of determining a first group data item for each of the plurality of groups to produce a plurality of first group data items, and determining a first system data item from the plurality of the first group data items are repetitively performed to produce the single ordered stream of data items.
REFERENCES:
patent: 4491945 (1985-01-01), Turner
patent: 4494230 (1985-01-01), Turner
patent: 4630260 (1986-12-01), Toy et al.
patent: 4734907 (1988-03-01), Turner
patent: 4748620 (1988-05-01), Adelmann et al.
patent: 4829227 (1989-05-01), Turner
patent: 4849968 (1989-07-01), Turner
patent: 4893304 (1990-01-01), Giacopelli et al.
patent: 4894823 (1990-01-01), Adelmann et al.
patent: 4899335 (1990-02-01), Johnson et al.
patent: 4901309 (1990-02-01), Turner
patent: 5127000 (1992-06-01), Henrion
patent: 5173897 (1992-12-01), Schrodi et al.
patent: 5179551 (1993-01-01), Turner
patent: 5179556 (1993-01-01), Turner
patent: 5216420 (1993-06-01), Munter
patent: 5220664 (1993-06-01), Lee
patent: 5229991 (1993-07-01), Turner
patent: 5253251 (1993-10-01), Aramaki
patent: 5260935 (1993-11-01), Turner
patent: 5274642 (1993-12-01), Widjaja et al.
patent: 5319360 (1994-06-01), Schrodi et al.
patent: 5337308 (1994-08-01), Fan
patent: 5339311 (1994-08-01), Turner
patent: 5402415 (1995-03-01), Turner
patent: 5402417 (1995-03-01), Aramaki
patent: 5406556 (1995-04-01), Widjaja et al.
patent: 5414705 (1995-05-01), Therasse et al.
patent: 5461614 (1995-10-01), Lindholm
patent: 5491728 (1996-02-01), Verhille et al.
patent: 5570348 (1996-10-01), Holden
patent: 5721820 (1998-02-01), Abali et al.
patent: 5822317 (1998-10-01), Shibata
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5875190 (1999-02-01), Law
patent: 6055246 (2000-04-01), Jones
patent: 6246684 (2001-06-01), Chapman et al.
patent: 6252891 (2001-06-01), Perches
patent: 6330559 (2001-12-01), Azuma
patent: 6434148 (2002-08-01), Park
Jonathan S. Turner, “An Optimal Nonblocking Multicast Virtual Circuit Switch,” Jun. 1994, Proceedings of Infocom, 8 pages.
Chaney et al., “Design of a Gigabit ATM Switch,” Feb. 5, 1996, WUCS-96-07, Washington University, St. Louis, MO, 20 pages.
Turner et al., “System Architecture Document for Gigabit Switching Technology,” Aug. 27, 1998, Ver. 3.5, ARL-94-11, Washington University, St. Louis, MO, 110 pages.
Cisco Technology Inc.
Ly Anh-Vu H
Pham Chi
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for pipeline sorting of ordered streams... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for pipeline sorting of ordered streams..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for pipeline sorting of ordered streams... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3350199