Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-07
2004-09-07
Vu, Huy D. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S357000, C370S412000, C370S415000, C370S416000
Reexamination Certificate
active
06788689
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to packet switching systems; and more particularly, the invention relates to the scheduling and routing of packets corresponding to multiple streams of packets through a packet switching system.
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 multiple 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 generically addressable 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 switches, networks, computer and/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.
However, this approach can lead to network congestion, especially for certain types of traffic. Packet switching systems route all kinds of traffic, including point-to-point or circuit switched traffic. This traffic includes isochronous traffic that arrives at an input port and is routed to one or more output ports of the packet switching system. For example, a Synchronous Optical Network (SONET) OC-192 link might be terminated on an input port with numerous OC-3 and OC-1 streams of data being routed through the packet switching system. The uncoordinated routing of such traffic, and especially when multiple streams arriving at multiple inputs of a packet switch, can lead to some unbounded network congestion conditions. Needed are new methods and systems for routing such traffic to achieve bounded delay in the packet switching system.
SUMMARY OF THE INVENTION
Packet switches, systems apparatus and methods are disclosed for scheduling and routing packets through a packet switching system. In one embodiment, a packet switch has an input interface, an output interface and an interconnection network coupled to the first input and output interfaces. The input interface includes a packet route scheduler which schedules the forwarding of packets over a multiplicity of different paths in such a way as to limit contention for internal links in the interconnection network so as to ensure that packets pass through the interconnection network with bounded delay.
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: 4785446 (1988-11-01), Dias et al.
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: 5130975 (1992-07-01), Akata
patent: 5164939 (1992-11-01), Shobatake
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: 5241536 (1993-08-01), Grimble et al.
patent: 5253251 (1993-10-01), Aramaki
patent: 5260935 (1993-11-01), Turner
patent: 5309430 (1994-05-01), Verhille et al.
patent: 5339311 (1994-08-01), Turner
patent: 5355372 (1994-10-01), Sengupta et al.
patent: 5357506 (1994-10-01), Sugawara
patent: 5402415 (1995-03-01), Turner
patent: 5572521 (1996-11-01), Pauwels et al.
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5987028 (1999-11-01), Yang et al.
patent: 6125112 (2000-09-01), Koning et al.
patent: 6335930 (2002-01-01), Lee
Jonathan S. Turner, “Almost all k-Colorable Graphs are Easy to Color,” Journal of Algorithms, Mar. 1988, 24 pages.
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.
Dirkx et al., “Performance Evaluation of High Performance Switches on Parallel and Distributed Computers,” Aug. 1997, Proceedings of the High-Performance Computing on the Information Superhighway, HPC-Asia '97, pp. 236-241.
Galles Michael B.
Turner Jonathan S.
Cisco Technology Inc.
The Law Offices of Kirk D. Williams
Volper Thomas E.
Vu Huy D.
LandOfFree
Route scheduling of packet streams to achieve bounded delay... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Route scheduling of packet streams to achieve bounded delay..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route scheduling of packet streams to achieve bounded delay... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3257145