Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-07
2004-06-08
Pham, Chi (Department: 2667)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06747972
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to communications systems and networks; and more particularly, the invention relates to reducing the required size of sequence numbers used in resequencing packets. This invention is especially useful in the design and operation of packet switches, but is not limited to this environment.
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 (e.g., 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 many 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” refers to packets of all types, including fixed length cells and variable length packets. Moreover, these packets may contain one or more types of information, including, but not limited to, voice, data, video, and audio information. Furthermore, the term “system” is used generically herein to describe any number of components, packet switch elements, packet switches, networks, computer and/or communication devices or mechanisms, or combinations thereof.
Consumers and designers of these systems typically desire high reliability and 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 back into their original order. One known technique for dynamically routing and resequencing streams of packets is to add a sequence number to each packet and then to place packets in sequential order based on these added sequence numbers. Separate sequence numbers are required for each switch input-output pairing. For example, each input interface of the packet switch must keep a separate sequence number counter for each output of the packet switch; and each output interface of the packet switch must keep a separate counter for each input of the packet switch. This technique is simple, but it requires a substantial amount of resources for lengthy buffers and sequence number counters. The resources required for these buffers and counters must be sufficient to distinguish the order of the packets even when worst cast delay differentials between paths occur. The size of these counters and the number and size of the buffers required for this resequencing technique are large, and it is difficult to place a bound on the resources required to implement such a system. Desired are improved methods and systems for dynamically routing and resequencing packets in a packet switch, especially those methods and systems which place a bound on the size requirements of sequence numbers.
Controlling the distribution of packets across the multiple paths between input and output pairs can be used to optimize the resequencing function and to improve performance. Two commonly used techniques of distributing traffic among the multiple paths between a source and destination are a pure round robin distribution and a pure random distribution. Both of these techniques fail to consider the destination or a downstream point in the network when distributing the traffic. The pure round robin technique repetitively sequences through each of the multiple paths in the same order for traffic without regard to a packet's destination. The pure random distribution technique randomly selects one of the multiple paths without regard to a packet's destination. However, such techniques are deficient in their resultant throughput. Desired are improved methods and systems for achieving greater throughput.
SUMMARY OF THE INVENTION
A packet switch has multiple in-order delivery interconnection elements. Coupled to the multiple in-order delivery interconnection elements are multiple packet switch input interfaces and multiple packet switch output interfaces. Each packet switch interface may include a packet distributor to distribute packets in accordance with a distribution scheme across the multiple in-order delivery interconnection elements and a packet switch sequencer to add a sequence number within a sequence number range to packets to be sent across the plurality of in-order delivery interconnection elements, the range of the sequence numbers being dependent on the packet distribution scheme. Each packet switch output interface may included a packet switch resequencer.
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: 4829227 (1989-05-01), Turner
patent: 4849968 (1989-07-01), Turner
patent: 4893304 (1990-01-01), Giacopelli 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: 5229991 (1993-07-01), Turner
patent: 5253251 (1993-10-01), Aramaki
patent: 5260935 (1993-11-01), Turner
patent: 5278828 (1994-01-01), Chao
patent: 5319360 (1994-06-01), Schrodi et al.
patent: 5339311 (1994-08-01), Turner
patent: 5402415 (1995-03-01), Turner
patent: 5617561 (1997-04-01), Blaauw et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 6252876 (2001-06-01), Brueckheimer et al.
patent: 6314100 (2001-11-01), Roach et al.
patent: 6317430 (2001-11-01), Knisely et al.
patent: 6351454 (2002-02-01), Crocker et al.
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.
Dittia Zubin D.
Eatherton William N.
Fingerhut John Andrew
Lenoski Daniel E.
Cisco Technology Inc.
Ly Anh-Vu
Pham Chi
The Law Office of Kirk D. Williams
LandOfFree
Method and apparatus for reducing the required size of... 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 reducing the required size of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing the required size of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3359118