Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-05-08
2004-08-10
Ho, Duc (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000, C370S413000
Reexamination Certificate
active
06775286
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The field of the invention is that of information technology, and more specifically, routers.
2. Description of Related Art
In a computer system, a network makes it possible to link together various data terminal equipment units for the purpose of exchanging information by means of data packets which they transmit.
A router is a device for switching data packets through the network in order to send them to the destination data terminal equipment. Each data packet generally includes in a header the means for recognizing a destination address, which allows the router to switch the packet to another router or directly to the destination data terminal equipment.
Certain routers are actual computers connected to the network. Such routers analyze the packet headers, possibly storing the packets before retransmitting all or some of them through the network, depending on network availability. Intermediate processing by these types of routers sometimes introduces less-than-desirable latencies into the transfer of packets through the network.
To reduce the latency of transfers in the network, some routers have been designed in the form of integrated circuits that constitute autoswitches with a minimum of intermediate storage.
When the data terminal equipment units are computers and peripherals, the transit times of the data packets between data terminal equipment units imposed by the physical links are relatively long compared to the processing capacities of the current machines. When the data terminal equipment units in a computer system are microprocessors, storage units and input-output units, overly long transit times of the data packets between data terminal equipment units will harm the performance of the system.
A router of the autoswitch type generally comprises a number n of inputs and a number n of outputs, for routing data packets from the inputs to the outputs. In order to constitute a network, inputs and outputs of the router are respectively connected to outputs and inputs of data terminal equipment or of other routers. Such a router comprises a minimum amount of memory in the form of buffers for temporarily accumulating data packets when the outputs cannot immediately absorb the load of the packets arriving through the inputs. This is the case, for example, when data packets arriving through several inputs are to be routed to the same output.
A buffer constituted by one or more cells, each cell specifically assigned to a respective input, constitutes an input queue. The drawback of an input queue is that when the output to which a data packet in question is to be routed is not available, the packet in question blocks the routing of subsequent packets that arrive through the same input. Even if there is an output available for a subsequent packet, this subsequent packet will remain unduly blocked by the packet in question until it is routed to an available output. This phenomenon harms the performance of the router.
A buffer constituted by one or more cells, specifically assigned to each output, constitutes an output queue. When an output to which a data packet in question is to be routed is not available, the data packet in question is accumulated in the output buffer, and waits for release. Thus, the packet in question does not block subsequent packets that arrive through the same input but are intended for another output. There is still a problem when several of the packets in question arrive through several inputs in order to be simultaneously routed to the same output. According to the prior art, the output queue then creates a bottleneck in the routing of the packets in question.
One solution, which consists of also installing an input buffer in order to make each packet in question wait while the other packets in question are routed to the output buffer, still has the drawback of the input queue phenomenon.
A solution that consists of multiplying, by the number n of inputs, the processing frequency of the router relative to the arrival frequency of the data through the inputs, runs the risk of being limited by the physical structure of the router. For example, it is difficult to obtain cycle times of less than one nanosecond in 0.5-micron CMOS technology for complex logical circuits. This limits the arrival frequency of data through the inputs to an order of magnitude of one GHz.
A solution that consists of equipping the router with a bus with a data path width equal to n times the data path width in one input requires complex control of this bus.
SUMMARY OF THE INVENTION
The subject of the invention is a router comprising a number n of inputs and a number n of outputs, for routing data packets from the inputs to the outputs. To eliminate the drawbacks mentioned above, the router according to the invention comprises:
a reticular routing switch constituted by a number n of first incoming lines, by a number n of second incoming lines, by a number n of first outgoing lines, and by a number n of second outgoing lines, each of the first incoming lines being respectively connected to an input and each of the first outgoing lines being respectively connected to an output;
an accumulator memory comprising a number n of write inputs, each connected to one of the second outgoing lines, a number n of read outputs, each connected to one of the second incoming lines, and a number n of groups of n cells;
each read line configured to allow an extraction of a packet contained in a group of n cells; and
each write line configured to allow an insertion of a packet into one of the cells of each group of n cells.
The n second outgoing lines of the reticular switch make it possible to route a data packet in question through one of these n second outgoing lines if the one of the n first outgoing lines connected to the output to which the data packet is to be routed is not available. There is always at least one outgoing line available for each input because there are as many second outgoing lines as first incoming lines. The accumulator memory makes it possible to save the data packet until the outgoing line again becomes available, to the extent that its capacity allows. The n second incoming lines of the reticular switch make it possible to route the packet in question to the output as soon as the outgoing line again becomes available. There is always at least one incoming line available for each output because there are as many second incoming lines as first outgoing lines. The capability to extract the packets from a group of cells through a read line connected to one of the second incoming lines gives the group of cells the advantages of an output queue. The possibility of inserting a packet into the group of cells through each write line connected to a second outgoing line considerably reduces the bottleneck that exists for the prior known output queues.
REFERENCES:
patent: 4403321 (1983-09-01), Kruger
patent: 5151996 (1992-09-01), Hillis
patent: 6381247 (2002-04-01), Munter et al.
patent: 0 492 026 (1992-07-01), None
patent: 0 504 710 (1992-09-01), None
Bull S.A.
Ho Duc
Kondracki Edward J.
Miles & Stockbridge P.C.
LandOfFree
Data packet router does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data packet router, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data packet router will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3353027