Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-09-24
2002-11-05
Yao, Kwang Bin (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06477173
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a system for switching high-capacity and variable length packets from plural input ports to plural output ports.
2. Related Art Statement
A common bus system is currently used in most major IP(internet protocol) routers and has been used in almost all commercially available IP routers.
FIG. 1
shows diagrammatically a packet switch of the common bus system. Each of plural input ports gets or acquires a right of using a common bus according to the round robin method and sends or broadcasts a packet on to the common bus. Each of plural outputs ports receives a broadcast packet addressed to the relevant output port. Therefore, in order to make a packet loss within the router to be zero, an operation speed of the common bus should be not lower than a value represented by (a transmission speed of each ports)×(the number of the ports).
The common bus system has advantages that variable-length packets can be exchanged and the number of circuit elements constituting the router can be reduced, but the transmission speed of the common bus must be increased in proportion to an increase in the number of the input and output ports. Therefore, due to physical limits of circuit elements, it is very difficult to realize a mass switching system having a bit rate more than one Tbps (terabit per second) by means of the common bus system.
FIG. 2
shows a Banyan network by means of which a mass switch can be realized by connecting unit switches in a multiple-stage mode. In the Banyan network, transmission paths exist between each of the input ports and all the output ports.
The Banyan network is suitable to realize the high-speed and high-capacity packet switching system, because all the unit switches within the Banyan network operate in parallel. However, as shown in
FIG. 3
, it has a drawback that when plural packets are inputted into the same input port, undesired internal blocking occurs. In
FIGS. 2 and 3
, the unit switch is formed by a 2×2 unit switch, but 4×4 unit switch, 8×8 unit switch, 16×16 unit switch and so on may be used to realize similar packet switching systems.
In order to reduce the internal blocking in the Banyan network, there has been proposed a tandem Banyan network. In this tandem Banyan network, plural Banyan networks are arranged in tandem as shown in FIG.
4
. In the tandem Banyan network, all the packets are inputted to a first stage Banyan network among the Banyan networks (in
FIG. 4
, the most left-hand side Banyan network), and when the internal blocking occurs in this first stage Banyan network, a misroute tag is set on the relevant packet and the packet is outputted to an empty output port which is not occupied by other packet. In this manner, after the packet has passed through the first stage Banyan network, the packet is inputted to a second stage Banyan network of the tandem Banyan network. On the other hand, a packet which has succeeded to be outputted to a desired or denoted output port of the first stage Banyan network is sent to an output buffer without passing through the remaining Banyan networks.
As explained above, in the tandem Banyan network, upon the occurrence of an internal blocking, a packet can be inputted to a succeeding one or more Banyan networks until the relevant packet arrives at a desired or destined output ports, and therefore almost all internal blockings can be avoided. In other words, in the tandem Banyan network, an internal blocking could not be avoided only when misroute tags are set at all the Banyan networks from the first stage to the last stage.
The tandem Banyan network is a valuable means for reducing the internal blocking in the Banyan network. However, in the tandem Banyan network, all packets are first inputted to the first stage Banyan network, and when an internal blocking might occur in the first stage Banyan network, the relevant packet is inputted to the second stage Banyan network and so on. Therefore, when an input traffic is large, a rate of occurrence of internal blocking in the first stage Banyan network becomes high and this results in an increase of a rate at which packets are inputting to Banyan networks after the second stage. This might cause an increase in a switching delay as well as an increase in a fluctuation of the switching delay. Furthermore, there might arise a problem that a rate of occurrence of a wrong order of packets is increased in accordance with the increase in a fluctuation of switching delay.
SUMMARY OF THE INVENTION
It is an object of the invention to provide a novel and useful system for switching high-capacity and variable length packets, in which the above mentioned problems in the known tandem Banyan network can be mitigated and a rate of occurrence of internal blocking can be reduced and the switching delay and the delay fluctuation can be decreased.
According to the present invention, a system for switching high-capacity and variable length packets comprises:
m (plural) input ports;
n (plural) output ports;
k (plural) Banyan networks connected into a ring by means of at least n parallel lines, each Banyan network having at least n inputs and at least n outputs;
m input modules each of which is connected to a respective one of said m input ports, said input modules being further connected to said inputs of said k Banyan networks;
m sets of misroute tag check parts, each set including at least n misroute tag check parts, respective misroute tag check parts in each set being connected to respective outputs of each Banyan networks; and
n output modules each having an output connected to a respective one of said output ports and inputs each connected to one of misroute tag check parts of each set;
wherein each of plural unit switches constituting a Banyan network is constructed such that when an input packet cannot be sent to a desired output, the relevant packet is outputted to a non-occupied output of the relevant Banyan network,
said misroute tag check part checks whether a misroute tag of an inputted packet is set or not, and when the misroute tag is set, the relevant packet is sent to a next stage Banyan network, but when the misroute check tag is not set, the relevant packet is outputted to an output module connected to a desired output; and
said input module is constructed to store a packet from the input port and a packet from a misroute tag check part and to send one of these packets selectively to a Banyan network of a next stage.
In the packet switching system according to the invention, as shown in
FIG. 5
, plural Banyan networks are connected in the form of a ring and plural input ports are connected to these Banyan networks in a dispersed manner. Thus, an input traffic is dispersed and an apparent input traffic of each Banyan networks can be reduced. For example, provided the number of the Banyan networks is N, in the known tandem Banyan network, a total amount of traffic is inputted into the Banyan network of the first stage, but in the packet switching system according to the invention, it is sufficient that each Banyan network receive 1/N of the total traffic amount. In this manner, the input traffic is dispersed among a plurality of Banyan networks connected into a ring. Due to this dispersing effect, an apparent input traffic to each of the Banyan networks is reduced, and thus a rate of occurrence of the internal blocking in Banyan networks is decreased as compared with the tandem Banyan network and a packet switching delay and a fluctuation of the packet switching delay can be decreased.
REFERENCES:
patent: 4866701 (1989-09-01), Giacopelli et al.
patent: 5287346 (1994-02-01), Bianchini et al.
patent: 5467211 (1995-11-01), Haney et al.
patent: 5940367 (1999-08-01), Antonov
patent: 6055233 (2000-04-01), Park
Aida Hitoshi
Aoki Terumasa
Saito Tadao
Frank Robert J.
Harper Kevin C.
Kaminski Jeffri A.
The University of Tokyo
Venable
LandOfFree
System for switching high-capacity and variable length packets does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for switching high-capacity and variable length packets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for switching high-capacity and variable length packets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2984008