Electrical computers and digital processing systems: multicomput – Computer-to-computer session/connection establishing
Reexamination Certificate
1999-02-01
2002-01-22
Lim, Krisna (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer session/connection establishing
C709S228000, C709S239000, C370S235000, C370S355000, C370S278000, C370S360000
Reexamination Certificate
active
06341313
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a flow controlling method and apparatus for use for transfer of a packet in a network between processors including a plurality of switches, and more particularly to a flow controlling method and apparatus for use for transfer of a packet between switches and between a processor and a switch connected to a network of switches.
2. Description of the Relates Art
A switch of the cross point buffer type which includes a number of FIFO (First In First Out) memories equal to the square of the “port number” on the input port side allows writing a packet into a FIFO memory at any time only if the FIFO memory is empty since, upon writing a packet into a FIFO memory, contention with writing from another port does not occur. However, as a number of FIFO memories equal to the square of the “port number” are required, it is inevitable from the limitation of the number of gates of a chip that the capacity of FIFO memories which can be mounted in a switch is small.
In a switch of the virtual cut-through type, a packet begins to be sent to the reception side only after reception side FIFO memories of a capacity sufficient to accept the entire one packet become empty. Therefore, a link between switches is occupied by a packet only for a time necessary to transfer the packet. Consequently, a switch of the virtual cut-through type is advantageous in that a high throughput of the entire network is achieved.
If it is intended to make a switch which employs a combination of the two types described above, the capacity of FIFO memories still matters. Since the number of required FIFO memories is as great as the square of the “port number”, it is inevitable that the capacity of one FIFO memory is small. However, in order to implement the virtual cut-through, one FIFO memory is required to have a capacity sufficient to store at least one packet therein.
Meanwhile, since one packet is composed of a header part in which control information such as a destination of the packet is held and a part of data to be sent actually, as the length of one packet increases, the ratio of the packet header decreases, and this allows data to be sent with a higher degree of efficiency.
In summary, since the cross point buffer system is employed, the capacity of each FIFO memory becomes small, but since the virtual cut-through system is adopted, each FIFO memory must be able to store at least one packet therein, and when the efficiency in transfer of data with one packet is taken into consideration, the packet length must be as large as possible.
When the requirements described above are taken into consideration, it is required that the maximum length of one packet should be set to a size a little smaller than the capacity of one FIFO memory.
Since the virtual cut-through system is employed, it becomes possible to output a write-enable signal for reporting to a switch in the preceding stage that the FIFO memory is in a write-enabled state at a point of time when it becomes possible to receive one packet.
In a FIFO memory of a conventional system, an empty signal indicating that the FIFO memory has no data therein and no data can be read out from the FIFO memory and a full signal indicating that the FIFO memory is full of data and does not allow writing of any further data are used to perform flow control.
Further, taking the time required for flow control into consideration, some FIFO memories utilize an almost empty signal indicating a state wherein the FIFO memory will become empty if several more words are read out from it and/or an almost full signal indicating a state wherein the FIFO will become full if several more words are written into it. Each of the signals represents the respective condition with its level.
If it is tried to use FIFO memories of the conventional system for switches of the cross point buffer type and the virtual cut-through type, then since the maximum length of a packet is a little smaller than the capacity of the FIFO memories, in order to allow discrimination of whether writing into a FIFO memory in the next stage is possible, it is inevitable to use an empty or almost empty flag from the FIFO memory. This is because, in the virtual cut-through system, since, once writing of a packet is started, it is written into a FIFO memory to the finish, flow control cannot be performed with a full flag or an almost full flag which changes over to ON intermediately on writing.
Flow control where an empty flag is used proceeds in the following manner.
1. When the empty flag is ON, since the FIFO memory is in an empty state, a packet which is smaller than the capacity of the FIFO memory can be written into the FIFO memory to the finish, and consequently, it is discriminated that the FIFO memory allows writing and writing of the packet is started.
2. When the empty flag is OFF, although a packet may possibly be written into the FIFO memory to the end, depending upon the length of the packet, since the packet may not be written to the last end, writing of the packet is not started.
After one packet is written into a FIFO memory of the switch in the next stage, it becomes possible to write a next packet at a point of time when the preceding packet is read out fully from the FIFO memory and the empty flag changes over to ON. In short, unless the FIFO memory in the next stage is not read completely, writing of a next packet is not allowed.
In this manner, in a switch of the cross point buffer type and the virtual cut-through type, since the size of FIFO memories is proximate to the maximum size of one packet, for flow control for FIFO memories of the conventional type, flow control which employs an empty flag is used, and this results in a large overhead.
The first problem resides in that, since writing of a next packet is not permitted until a packet in a FIFO memory of the switch in the next stage is transferred and the FIFO memory of the switch in the next stage becomes empty, writing of a next packet in the switch in the preceding stage is made to wait.
One of the reasons is that whether or not the FIFO memory in the next stage allows writing can be reported only by an empty flag or an almost empty flag of the FIFO memory. Further, since the switch also employs the virtual cut-through system, even if the FIFO memory overflows, transfer of the packet cannot be stopped. Consequently, the other reason is that a full flag or an almost full flag of the FIFO memory cannot be used.
The second problem resides in that an empty flag and a full flag of the FIFO memory are not suitable for packet transfer of the virtual cut-through type which employs FIFO memories which have a capacity for only one packet.
The reason is that the empty flag and the full flag are originally used for flow control only with reference to the number of words in the FIFO memory and cannot be used for flow control in units of a packet.
Further, in the virtual cut-through system wherein the capacity of a FIFO memory corresponds to only one packet, once a packet in the FIFO memory begins to be processed, the packet will be read out entirely and the FIFO memory will become empty in the near future. However, the empty flag and the full flag are each a signal representing a state at present, and neither of them can transmit whether or not a packet is going to be processed. Also this is a reason for the second problem described above.
The third problem resides in that time is required for transmission of information that a FIFO memory does not allow writing.
The reason is that critical information is transmitted after a delay of time to the switch in the preceding stage because all flow control information is produced on the FIFO memory side into which writing is to be performed.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a flow control system by which, when transfer of the virtual cut-through type is performed with switches of the cross point buffer type, efficient transfer can be achieved even if the capacity of FIFO memories is small.
Lim Krisna
Sughrue & Mion, PLLC
LandOfFree
Flow controlling method and apparatus for network between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flow controlling method and apparatus for network between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flow controlling method and apparatus for network between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2822517