Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1998-05-26
2002-01-01
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S389000
Reexamination Certificate
active
06335930
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a packet switching network, and more particularly a multi-stage interconnection network having several switching stages.
BACKGROUND OF THE INVENTION
High speed packet switching is a key technology for Broad-band Integrated Services Digital Network (B-ISDN). Currently, Asynchronous Transfer Mode (ATM) is receiving tremendous attention for the next generation of communication technology. The ATM was defined by the CCITT (currently ITU-T) which is the United Nations (U.N) body which defines future telecommunication standards. The basic Protocol Data Unit (PDU) of ATM, which is called a cell, has a fixed length of 53 bytes. ATM switching can be classified as part of the larger category packet switching.
The high speed packet switch is a key technology for B-ISDN technology. There are many requirements for the architecture of a high speed packet switch, such as a modularity and high fault-tolerance, which contribute to easy implementation and good quality of service. Such technology is disclosed in “ATM Technology for Corporate Networks”, IEEE Communications Magazine, pages 90-101, April, 1992.
A packet switch is a system that is connected to multiple transmission links and does the central processing for the activity of a packet switching network where the network consists of switches, transmission links and terminals. The transmission links are connected to network equipment, such as multiplexers (MUX) and demultiplexers (DMUX). A terminal can be connected to the MUX/DMUX or it can be connected to the packet switch system. Generally, the packet switch consists of input and output transmission link controllers and the switching network. The input and output link controllers perform the protocol termination traffic management and system administration related to transmission jobs and packet transmission. These controllers also process the packets to help assist in the control of the internal switching of the switching network.
The switching network of the packet switch performs space-division switching which switches each packet from its source link to its destination link. There are many known architectures for switching networks. The important characteristics for a switching network are self-routing for high speed switching, short transmission delays, low delay variance, good fault tolerance for high quality service, and high reliability for easy maintenance. Generally, the switching networks are composed of several switching stages with a web of interconnections between adjacent stages. These network are called Multi-stage Interconnection Networks (MIN). Each stage consists of several basic switching elements where the switching elements perform the switching operation on individual packets for self-routing of the packets.
Self-routing enables each packet to be processed by the distributed switching elements without a central control scheme, and thus high speed switching can be done.
The architecture of packet switching networks can be classified by the buffering scheme employed in the network for various queues. For example, input queuing, output queuing, input/output queuing, crosspoint queuing, central queuing, internal queuing and the like.
Input queuing suffers from what is called the “head of line” problem (e.g., head of line:HOL). The head of line problem occurs when a packet at the head of line, or first-in position, in a first-in-first-out (FIFO) input buffer is blocked by an output collision with another packet in the network. While the HOL packet is blocked, the other packets in the FIFO buffer are also blocked as they await their turn for the head of line position in the FIFO input buffer while their output destinations are not occupied by other routing requests.
Output queuing is better than input queuing because it does not suffer from the HOL problem, but the buffer size for each output port must be increased as the number of input ports increases. Internal queuing and crosspoint queuing also increase the hardware complexities as the number of ports increases. Central queuing has a bottleneck caused by the speed of memory accesses within the central queue which increases with the number of ports.
Switching networks can also be classified as time division switches in addition to space division. There are many proposed architectures for each division method, as disclosed in “ATM Technology for Corporate Networks”, IEEE Communications Magazine, pages 90-101, April, 1992.
The time division switching technique is not adequate for large scale switching systems. Under the space division switching technique, a single path network has some problems such as low maximum throughput and hardware complexity. However, the matrix for the time division technique combined with the fully interconnected architecture of space division technique has good performance and can be adapted to the design of the basic elements, as disclosed in “Integrated Services Packet Network Using Bus Matrix Switch”, IEEE Journal on Selected Areas in Communications Magazine, 22(4): 24-31, April, 1994.
Among multiple path switching networks, a recirculating scheme causes an increase in the number of inlets due to the recirculated lines, so that it is not adequate for a large scale switching system. This technology is disclosed in “STARLITE: A Wideband Digital Switch”, GLOBECOM, pages 121-125, November 1984.
On the other hand, tandem banyan networks (discussed in “Architecture, Performance, and Implementation of the Tandem Banyan Fast Packet Switch”, IEEE Journal on Selected Areas in Communications, 9(8):1173-1193, October 1991; U.S. Pat. No. 5,541,914), parallel banyan networks (discussed in “Analysis of Out-of-Sequence Problem and Preventative Schemes in Parallel Switch Architecture for High-speed ATM Network”, IEEE-Proceeding-Communications, 141(1):29-38, February 1994), load sharing networks (discussed in “Performance of Unbuffered Shuffle-exchange Networks”, IEEE Transactions on Computers, c-35(6): 573-577, June 1986), dilated networks (discussed in “Broadband Packet Switches Based on Dieted Interconnection Network”, IEEE Transactions on Communications, 42(2.3.4): 732-744, 1994) and close networks (discussed in “A Modular Architecture for Very Large Packet Switches”, IEEE Transactions on Communications, 38(7): 1097-1106, 1990) are each good candidates for the architecture of a large scale ATM switching system.
In multiple path switching networks, the number of paths from a given input port to a given output port can be one measure of the performance. A banyan network is a network which has one and only one path from each input port to each output port. A tandem banyan network serially connects each banyan network so that multiple routing trials can be taken. A parallel banyan network is one in which several networks are connected in parallel with one another. A rerouting network is one in which respective banyan networks are overlapped, so that a packet which has failed in one routing trial can restart its routing path at the next stage of the network. Among the different types of networks, the rerouting network has the largest number of routing paths for a given level of hardware complexity.
Lawrie has reported on an omega network for data access and alignment using an array processor in order to access multiple data at the same time in “Access and Alignment of Data in an Array Processor”, IEEE Transactions on Computers, C-24(12):1145-1155, December 1975. The omega network consists of n switching stages (where n=log
s
N stages with N being the number of input ports and the number of input ports, i.e. the number of input and output ports being the same is a “square size” network). Each of the n switching stages is composed of N/2 basic switching elements and each switching element performs 2×2 switching.
FIG. 1
shows an embodiment of an omega network having a two port perfect shuffle interconnection scheme. The omega network supports bi-directional routing and the number of perfect shuffle connections is the same as the number of sw
Chin Wellington
Marger & Johnson & McCollom, P.C.
Pham Brenda H.
Samsung Electronics Co,. Ltd.
LandOfFree
Multi-stage interconnection network for high speed packet... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-stage interconnection network for high speed packet..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-stage interconnection network for high speed packet... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2873818