Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
2001-10-09
2004-12-07
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S388000, C370S389000, C340S002600, C257S499000, C257S661000, C257S930000
Reexamination Certificate
active
06829237
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to data switches and, more specifically, to a high speed multi-stage switching network formed from stacked switching layers for use in routers and the like.
2. Description of the Related Art
This invention relates to switches. A switch, in the most general sense relevant here, is a communications device that controls the routing of a signal path. Switches are generally categorized as packet switches or as circuit switches. Packet switches, also sometimes called datagram switches, switch packets containing both data and meta-data (control information). Some well-known packet switching devices are IP routers and asynchronous transfer mode (ATM) switches. As stated in RFC 1812, “An IP router can be distinguished from other sorts of packet switching devices in that a router examines the IP protocol header as part of the switching process. It generally removes the Link Layer header a message was received with, modifies the IP header, and replaces the Link Layer header for retransmission.”
Circuit switches are devices that establish a dedicated channel for the duration of the transmission, thereby allowing data that is not accompanied by meta-data to be transmitted in real time. The public switched telephone network (PSTN) is a circuit-switched network. A telephone switch that is part of the PSTN is a prototypical circuit switch. This patent application will focus on packet switching devices, but a switch made in accordance with this invention is applicable to a circuit switching device as well.
In a data communications network that uses packet switching technology, data to be sent from one network interface to another is broken up into small chunks for transmission over the network. The individual data chunks are typically combined with suitable control information to form transmission units called “packets.” The packets are usually self-contained in the sense that the packet itself carries the information needed for routing the packet to its intended destination. The destination information is part of the packet's control information.
Each packet generally has a header containing its source and destination, a block of data content sometimes called a payload, and an error-checking code. All the data packets related to a message may or may not take the same route to get to their destination; they may pass through different packet switches on the way to their final destination and they are all reassembled once they have arrived.
Some packet-switching protocols refer to the transmission units as “datagrams” or “frames” or “messages” or “cells”. This application, however, will generically refer to all such transmission units as packets without regard to the actual format or specific name used by any particular protocol.
In the context of a packet switch, therefore, a switch is a networking device which can send packets directly to a port associated with a given network address, or destination address, contained in the packet.
FIG. 1
is a simplified block diagram of a switch
10
that forwards data arriving at one of its inputs
11
to one of its outputs
13
. The core of a data switch, as shown by
FIG. 1
, is a so-called “switch fabric”
12
that routes data from an input port to an output port.
A “router” is a device that finds the best path for a data packet to be sent from one network to another. A router stores and forwards electronic messages between networks. A router generally picks the most expedient route to the destination address from among all possible paths based on the traffic load and the number of hops.
A router commonly incorporates a data switch and combines such switch with other complexities such as input buffers, output buffers, port mappers, schedulers for generating “switch commands”, sorters and so on.
FIG. 2
shows a simplified block diagram of a router
20
consisting of (1) a plurality of “line cards”
21
that each have one ore more network interfaces
22
to the attached networks, (2) an internal interconnection unit or data switch
10
that contains a “switch fabric”
12
as discussed above, and (3) a processing module
23
.
The most common switch fabric technologies in use today are buses, shared memories, and crossbars.
Buses and Shared Memories
The simplest switch fabric
12
is a shared bus that operates in a time-division manner. In such case, multiple interface cards are connected to the bus and a microprocessor executes suitable software for performing the routing function. The microprocessor reads data from an input port connected to the bus, determines a “next hop” address by reading the packet's destination address and performing a look up operation in a routing table that is updated pursuant to suitable protocols, and then writes the data to the appropriate output port based on the next hop determination. The data is usually buffered in a common memory connected to the bus such that it must cross the bus twice in going from an input port to an output port.
While this simple bus-based, software controlled architecture is useful for a router with 10 megabits per second (Mbps) ports, and perhaps for a router with relatively few 100 Mbps ports, its capacity is limited in terms of data rate and port count. It is difficult to achieve wire-speed routing at higher data rates with this architecture because of bottlenecks associated with the shared bus, the memory's data transfer bandwidth, and the processor's clock speed. According to one author, “it is almost impossible to build a bus arbitration scheme fast enough to provide nonblocking performance at multigigabit speeds.” Aweya, James,
IP Router Architectures: An Overview
, Nortel Networks, p.30.
There are, of course, more efficient ways of operating with a bus-based switch fabric
12
. For example, some designers have put “satellite” processors, route caches, and memory on the interface cards themselves to allow the cards to process packets locally and make their own routing decisions whenever possible.
Other bus-based architectures used multiple parallel “forwarding engines” that operate only on the destination header, the packet data being forwarded directly from an input interface card to an output interface card under the control of so-called forwarding engines. The packet's data payloads, in other words, is directly transferred from interface card to interface card.
Crossbars
A more advanced generation of routers was designed with a parallel connection switch fabric that operated in a space-division manner rather than a time-division manner. Such switch fabrics allowed data throughput to be increased by several orders of magnitude. A popular switch fabric of parallel connection construction is known as a crossbar switch.
FIG. 3
is a simplified block diagram of an N×N crossbar switch
112
implemented in crosspoint arrangement with switching elements located at each node or crosspoint
113
. Data arriving on at inputs row is placed on an output column if the corresponding crosspoint
113
is active.
FIG. 4
is a simplified block diagram of an N×N crossbar switch
212
that uses multiple N-to-1 demultiplexers
213
, one for each of the N outputs. A full crossbar switch is desirable because every input port has a path to every output port such that there is no blocking at any input ports or inside of the switch. Blocking will only occur when two packets compete for the same output port.
Crossbar switches are conceptually desirable, but they have generally been regarded as physically impractical for large switches.
Crossbars usually have very low blocking probabilities, but they have a key defect: they require a lot of circuitry (proportional to n
2
or worse) in each output port. Because costs grow quadratically with the number of ports, crossbar designs are generally suitable only for comparatively small switches.
Partridge, Craig.
Gigabit Networking
, Massachusetts: Addison-Wesley Publishing Company, 1994. Page 100.
In other words, prior art approaches to crossbar sw
Carson John C.
Ozguz Volkan H.
Andras Joseph C.
Elallam Ahmed
Irvine Sensors Corporation
Kizou Hassan
Myers Dawes Andras & Sherman LLP
LandOfFree
High speed multi-stage switching network formed from stacked... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed multi-stage switching network formed from stacked..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed multi-stage switching network formed from stacked... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3327820