Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-07-28
2004-12-28
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S357000
Reexamination Certificate
active
06836479
ABSTRACT:
FIELD OF THE INVENTION
This invention is related to a router which switches a variable length packet.
BACKGROUND OF THE INVENTION
By the Internet's popularization, the data traffic rapidly increases recently. In order to deal with the increase, enlargement of capacity of a communication channel, speedup and enlargement of capacity of a communication device, such as an exchange node, is important.
A conventional variable length packet communication device has structure that interfaces and a microprocessor are connected to a bus. When a packet arrives at one of the interfaces, the interface transmits the packet to the microprocessor and the microprocessor analyzes the packet and transmits the packet to the desirable route. However, the bus and microprocessor are the bottleneck to perform a processing at high speed.
It is also used a switching device that performs the switching in packet units, like a frame relay. The device assigns and releases switch resources in variable length packet units. In the device, however, it is necessary to monitor the packet transmission completion in byte units, and to control the assignment in byte units. Therefore, since the control processing is a bottleneck, it is hard to construct a large capacity packet switch.
It also appeared a relatively high speed packet communication device that used as the switch core, a switch like what it is disclosed in “The Tiny Tera: A Packet Switch Core,” IEEE Micro, Vol.17, No.1, 1997,pp. 26-33 (Reference (1)). Reference (1) disclose that the input interface divides the packet into fixed length cells and transmits the cells to the core switch. The core switch transmits the cells to a desirable route, and the output interface for output reassembles the cells into the packets.
Japanese Unexamined Patent Publication Disclosure 5(1993)-227211 (Reference (2)) discloses a technique for dividing the variable length packet into a plurality of small packets, adding the internal header for indicating the destination to each of the small packets and after that transmitting the small packets to the switch. The switch performs ATM (asynchronous transfer mode) switching to the small packets based on the internal header. After that, in output side, the small packets are assembled into the variable length packet. A path is set up between the source channel and the destination channel through the switch. While a packet is transmitted through the path, the path is fixed and transmission from another channel holds being waited.
Japanese Unexamined Patent Publication Disclosure 8(1996)-65307(Reference (3)) discloses a technique for generating switching information from destination information included in packets and sending them to the switch. The switch performs switching based on the switching information. The packet assembling part converts sent information to packets, attribute information indicating the lead packet and destination information in the case of the first packet, but attribute information indicating the packets other than the first packet in the case of following packets.
SUMMARY OF THE INVENTION
In the technique disclosed in Reference (1), the switch is occupied in cell units, and cells arrive at an output interface in such a manner as to be interleaved from a plurality of input interfaces. Therefore, the output interface has to have a plurality of queues corresponding to the number of input interfaces, store cells from their respective input interfaces into their respective queues, and reassemble the cells into the packet in respective queue like CLAD of ATM exchange. Accordingly, the amount of hardware increases.
On the other hand, in the technique for Reference (2), at output side, buffers corresponding to input interfaces are not necessary.
In the technique, however, each of the small packets has a field for indicating its destination. There is more overhead because the field occupies relatively large part of the small packet. This decreases the throughput of the switch.
The technique for Reference (3) is related to an application of ATM switching. Moreover, Reference (3) does not mention the way that does not create the state that packets arrive at the packet disassembling part in such a manner as to be interleaved from a plurality of packet assembling parts.
An object of this invention is providing a router that the throughput of the switch is high and the amount of hardware is small.
And in order to deal with increasing Internet traffic, a router with large capacity is necessary at the backbone. Although that router has to have a switch with large capacity therein, in order to make that switch, parallel processing in the switch is effective. Generally, since throughput of a switch depends on internal clock frequency of the switch times the number of bits to be processed in parallel, increasing the number of bits to be processed in parallel can realize the switch with large capacity. This requires increasing the number of bits of processing unit in the switch. However, even if a packet is divided into plurality of cells and the switch performs switching process cell by cell, the number of parallel processing bits is under restriction caused by the cell size.
Another object of this invention is providing a router that can perform parallel processing in switch effectively.
In the present invention, an input interface segments a variable length packet into plurality of fixed length cells and generates a cell (switch control cell) indicating the output path based on the head information of the variable length packet. That is, the cell has switching establishment information. The input interface transmits the switch control cell as the head cell to a switch and, after that, transmits the cells as the following cells of the switch control cell to the switch. The switch performs switching processing to the succeeding cells based on switching establishment information of the head cell. Therefore, the switching establishment information is not added to the cells.
In the present invention, switch is reserved in packet units. That is, when an input interface starts to transmit cells generated from a packet to its destination output interface through the switch, the switch is reserved until all the cells arrive at the output interfaces. In other words, the output interface does not receive any cell from another input interfaces until all the cells arrive at the output. However, the switch may transmit a packet to be transmitted to an output interface different from the output interface. In such way, the variable length communication device reassembles the cells into the packet by queuing the cells in arrival order at the output interface. And, in the present invention, due to adding the field for indicating the output route to only the head cell, there is less overhead in switch and less the amount of hardware in transmitting interface side. Moreover, in this invention, since a switch on/off operation itself is performed cell by cell, there is less load of scheduler of the switch.
In the another present invention, a packet container containing a packet/packets is provided. An input interface has a plurality of queues, each of which corresponds to each of the output interfaces respectively. The input interface stores packets into the their respective queues and stuffs a packet/packets to be transmitted to the same output interface into the same container in such a manner as a packet does not extend over two containers. The switch performs switching by the containers. The output interface takes the packet/the packets from the container and transmits the packet to the transmission path. This facilitates reassembling a packet at the output interface. Moreover, using the container facilitates large capacity of the switch, since unit of switching and the number of parallel processing bits increase.
Moreover, in the another present invention, a fixed length container is provided. An input interface permits a packet to extend over a plurality of containers. An input interface has a plurality of queues, each of which corres
Aimoto Takeshi
Endo Noboru
Matsuyama Nobuhito
Moriwaki Norihiko
Sakamoto Ken'ichi
Chin Wellington
Hitachi , Ltd.
Jain Raj
Mattingly Stanger & Malur, P.C.
LandOfFree
Variable length packet communication device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Variable length packet communication device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable length packet communication device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3303088