Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-01-20
2001-09-11
Ton, Dang (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S406000, C370S407000, C370S408000, C370S400000
Reexamination Certificate
active
06289021
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to interconnection structures for computing and communication systems. More specifically, the present invention relates to a scaleable low-latency switch for usage in a multiple level interconnection structure.
2. Description of the Related Art
A persistent significant unsolved problem in the field of computer science has been the lack of a scalable, low-latency interconnect that sustains high throughput (high cross-sectional bandwidth) under fully loaded conditions. Existing interconnect designs, such as the banyon, omega and fat-tree networks, multi-level grids, torus and hypercube networks all fail, in various degrees, to scale without limit, support low latency and high throughput when loaded with traffic. The geometries of these networks were developed by Nineteenth Century mathematicians, and even earlier geometricians, and were never intended to support a message-routing method.
What is needed is an interconnect structure and a suitable switch for use in forming interconnections in the structure that are scalable virtually without limit, and that support low latency and high throughput.
An interconnect structure and switch with these advantageous characteristics is useful in many electronic design environment application categories including supercomputer networks and network switch fabric environments such as local area network (LAN)/Internet switch fabrics and telephone switch fabrics.
Objectives of the various electronic design environments are very different. For example, a primary objective in the design of a supercomputer is very low latency. In contrast, the main objective in the design of a LAN/Internet switch fabric is scalability, rather than latency. An objective of telephony central office switching is very high scalability and low cost, while latency and bandwidth are of smaller concern.
Switches for supercomputer designs are fabricated using expensive silicon fabrication technologies. Design parameters are particularly defined and invariant throughout a supercomputer system. Specifically word size, addressing schemes, size, and capacity are generally invariant throughout a supercomputer system. A single compiler philosophy and design, and operating system definition and requirement set is typically used for a supercomputer system. Similarly, a supercomputer system includes a single definition of operating speed and voltages. A supercomputer utilizes compatible components, memory, processors, power supplies and the like.
A supercomputer design generally has a smaller maximum size than a LAN/Internet network, although the size of a network is highly variable. A supercomputer design typically has a size in the range from hundreds to a few thousand ports while a network has a size in the range from hundreds to many thousands of ports or higher. A supercomputer system uses a switch design with a high degree of parallelism through usage of multiple identical stacked integrated circuits. Typically nodes in a supercomputer network are implemented on a single integrated circuit chip with only a few nodes fabricated on one circuit board. The interconnection of nodes is made by multiple, expensive high-speed cables. The supercomputer design parallelism extends to addressing and control issues, as well as packaging to achieve a reduction in latency and an increase in bandwidth per port.
In contrast to supercomputer switch implementations, switches for a network design, such as a LAN/Internet network design, typically utilize multiple integrated circuits possibly having different design parameters. Generally, design parameters for small networks are substantially different from design parameters for large networks. For example, large networks sometimes use a “twisted cube” or two-dimensional design. Very large networks having on the order of hundreds of thousands of ports commonly use three-dimensional or four-dimensional topologies that are formed by interconnecting or cascading multiple switch circuits into a meta-topology for super-large switches. Different implementations of switch circuits are needed to efficiently construct LAN/Internet networks having differing meta-topologies, especially to supply suitable input and output signal timing. Network bit rates are commonly slower than the bit rates of a supercomputer and are widely variable. For example, Ethernet uses a 10 Mbit/s rate. A token ring has a 12 Mbit/s rate. A fast Ethernet attains a 100 Mbit/s rate and ATM attains a 25 Mbit/s to 622 Mbit/s rate.
Conventional switch technologies have many deficiencies in the support of interconnect structure technologies. First, no existing switching fabric or technology can support more than about 12 to 24 ports at a reasonable cost. For example, an eight-port token ring switch costs approximately $10,000. An eight to sixteen-port 10 Mbit/s Ethernet switch ranges in cost from $4,000 to $10,000.
A second deficiency of interconnect switch technologies is that a single switch design does not support multiple different communication protocols. Pin-limited designs are easily supported only for communication protocols having a small packet length, such as ATM. Different packet sizes directly affect integrated circuit chip design so that wide variability in packet sizes leads to large differences in design switch specifications. For example, a switch buffers the entire length of the maximum packet size at least once for every port on an integrated circuit switch. Thus, the defined ATM packet size is 53 bytes so that the small payload of an ATM design yields an efficient usage of the gates in an integrated circuit. The Ethernet packet size is variable and ranges up to about 2 Kbytes, requiring a large number of gates for buffering a message. Similarly, token ring packets range up to 4 Kbytes and fiber channel sizes are virtually unlimited, using a large circuit area for message buffering.
What is needed is a generic switch circuit for local area network usage. What is further needed is a generic switch circuit for constructing a network that implements IEEE network specifications
SUMMARY OF THE INVENTION
A highly advantageous interconnect structure is useful for computers of all types, networks and communication systems utilizing a data flow technique that is based on timing and positioning of messages communicating through the interconnect structure. Switching control is distributed throughout multiple nodes in the structure so that a supervisory controller providing a global control function and complex logic structures are avoided. The interconnect structure operates as a “deflection” or “hot potato” system in which processing and storage overhead at each node is minimized. Elimination of a global controller and buffering at the nodes greatly reduces the amount of control and logic structures in the interconnect structure, simplifying overall control components and network interconnect components and improving speed performance of message communication.
A scalable low-latency switch, extends the usefulness and advantages of the interconnect structure and includes a novel set of structures that accompany a novel message-routing method to avoid limitations of previously existing networks. The throughput of a simple embodiment of the interconnect structure using the scalable low-latency switch is better than 20 percent as the interconnect size goes to infinity. Time-of-flight (latency) is typically no greater than twice the time elapsed for the header to enter the network, even when the interconnect structure is fully loaded. Another embodiment of the interconnect structure, called a “Flat Latency Interconnecf”, using the scalable low-latency switch has two or more downward paths per node and improves throughput to better than forty percent as the size goes to infinity.
In accordance with an aspect of the present invention, a scaleable low-latency switch design satisfies highly aggressive objectives in multiple interconnect design categories. The scaleable low-latency switch satisfies many diff
Interactic Holdings, LLC
Koestner Ken J.
Skjerven Morrill & MacPherson LLP
Ton Anthnoy
Ton Dang
LandOfFree
Scaleable low-latency switch for usage in an interconnect... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scaleable low-latency switch for usage in an interconnect..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaleable low-latency switch for usage in an interconnect... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2470864