Dynamic data packet flow control for packet switching node

A data packet switching node that temporarily stores data packets received from at least one source network adapter and transmits them to at least one destination network adapter comprises a data packet flow control system to control the data packet flow. The data packet flow control system comprises identifier to determine the at least one destination adapter of each received data packet. Then, flow control logic coupled to the storage allow computing a data packet flow value representing the traffic for the at least one destination adapter. The data packet flow value is transmitted simultaneously to the at least one source network adapter and to the at least one destination network adapter each time a data packet for the at least one destination network adapter is stored into the storage.

TECHNICAL FIELD

The present invention relates to the flow control of data packets transmitted between Local Area Networks (LAN) interconnected by a switch engine.

BACKGROUND ART

Local Area Networks (LAN) such as Ethernet or token-ring networks, are generally interconnected through hubs. The hub is a system made of LAN adapters that communicate together through a switch card. The switch card is mainly composed of input ports, output ports and a shared memory switch engine.

The data packets received by the input ports are stored into the shared memory at address locations determined by queues containing the packet destination addresses. The packets are de-queued to be transmitted to the destination output ports.

The shared memory having a limited size, a flow control mechanism is generally implemented to control the data packet transfer between each adapter card and the switch engine. Flow control mechanisms are often based on thresholds. The shared memory has a maximum threshold and a minimum threshold. When the number of data packets stored into the shared memory reaches the max. threshold, the switch engine asks the adapter card to stop sending data packets. When the number of data packets stored into the shared memory reaches the min threshold, the switch engine asks the adapter card to resume the transmission of data packets. Drawback of such mechanism is that it is a binary control which operates as ‘do transmit’ or ‘do not transmit’, thereby leading to interrupt and resume the data flow.

Therefore, there is a need to have a flow control system wherein the transmission from the adapter cards is never stopped. The present invention offers such solution.

SUMMARY OF THE INVENTION

Accordingly, it is an object of the invention to provide a smooth flow control mechanism between adapter cards and a switch engine.

It is another object to provide a flow control system having less latency between the adapter cards and the switch engine.

It is yet another object of the invention to offer an optimal use of the shared memory of the switch engine.

In a preferred embodiment, the invention relates to a data transmission system comprising a plurality of Local Area Networks (LANs) interconnected by several hubs. Each hub contains a Control Point card, a plurality of adapter cards connected to the Local Area Networks and a switching system made of two switch cards, one being active and the other being backup.

Each data packet transmitted by any adapter card to the switch engine includes a header containing at least the address of the adapter card to which the data packet is forwarded.

The system of the invention operates both in the switch engine and the adapter cards. It comprises a flow control circuitry associated to the shared memory where the data packets are stored. The flow control circuitry operates between each adapter card and the active switch card.

In a preferred embodiment, a data packet switching node that temporarily stores data packets received from at least one source network adapter and transmits them to at least one destination network adapter comprises a data packet flow control system to control the data packet flow. The data packet flow control system is characterized in that it comprises:

identifier means to determine the at least one destination adapter of each received data packet;

means coupled to the storing means for computing a data packet flow value representing the traffic for the at least one destination adapter; and

means coupled to the identifier means and to the computing means for transmitting the computed data packet flow value simultaneously to the at least one source network adapter and to the at least one destination network adapter each time a data packet for the at least one destination network adapter is stored into the storing means.

DETAILED DESCRIPTION OF THE INVENTION

The invention is preferably implemented in a data transmission environment as illustrated onFIG. 1. For sake of simplicity, the environment is made of four Local Area Networks (LAN)10_1,10_2,10_3, and10_4but it could be extended to a plurality of LANs and as such a LAN is also denoted10_i in the description. LANs10-i are interconnected together by a hub12, and may be of the type ATM, Ethernet, or token-ring. Each LAN is connected to a switching system14within the hub12by means of a respective adapter card16_1for LAN10_1, adapter card16_2for LAN10_2, adapter card16_3for LAN10_3and adapter card16_4for LAN10_4. Each adapter card (also denoted16_i) sends data packets by means of a data bus-in (bus-in13_1to bus-in13_4) connected to input ports of the switching system14. Each adapter card receives data packets by means of a data bus-out (bus-out15_1to bus-out15_4) connected to output ports of the switching system14. Then, a data bus-in13_i carries data packets from the respective adapter card16_i to switching system14and data bus-out (15_i) carries data packets from switching system14to the adapter card16_i. Each adapter card also receives flow control information from the switching system14by means of a serial interface17. Then, a serial signal17carries flow control information from the switching system14to the respective adapter card16_i. The switching system14is made of two distinct switch cards, an active switch card14_1and a backup switch card14_2. The invention is located within each switch card but for the ease of description, let's only describe the active switch card14_1.

Referring now toFIG. 2, the invention is described as part of the switch card14_1. For the ease of comprehension, let's describe the transmission of a data packet from adapter card16_1on data bus-in13_1to adapter card16_2on data bus-out15_2. It is to be easily understood that adapter cards16_1and16_2are only taken as example. In the preferred embodiment, the switch card is mainly composed of:a Shared Memory250;a Header Detection and Packet Validation block100_1;a Memory Write entity made of:an En-queue Register block380_1,a Lease Address Selector block350,a Memory Write Controller block150;a Memory Read entity made of:a De-queue Destination FIFO block310_2,a Release Address Selector block300,a Memory Read Controller block200,a Destination Output Buffer block280_2;a Free Buffer Queue block400;a Flow Control block450.

The structure and operation of the different blocks are now described.

Shared Memory (250):

The Shared Memory receives data packets from adapter card16_1on data bus-in13_1and transmits them to adapter card16_2on data bus-out15_2through the Destination Output Buffer block280_2. The write operation is controlled by bus160and the read operation by bus210.

Header Detection and Packet Validation (100_1):

Generally, a data packet is made of a header and a payload. The header contains information such as a destination address, a priority level, and the payload contains the data.

The Header Detection and Packet Validation block100_1receives data packets from adapter card16_1through data bus-in13_1. When a valid data packet is detected the destination address is extracted and generated on bus140_1. In addition, a write enable signal130_1is activated.

Memory Write Entity:

The Memory Write Entity is made of an En-queue Register block380_1, a Lease Address Selector block350and a Memory Write Controller block150.

To detail more each task:The En-queue Priority Register block380_1contains the address where to store an incoming data packet. The address comes from the Free Buffer Queue block400through bus410. The output bus370_1is connected to the Lease Address Selector block350.The Lease Address Selector block350for destination adapter16_2is illustrated inFIG. 3. Its function is to transfer the address stored into En-queue Register block380_1onto bus360through the buffer block351. The destination address of the incoming data packet is received on bus140by the Destination Decoder block330which decodes and activates the corresponding destination chip select signal360_2. This chip select signal is carried out to Flow Control block450and to the De-queue Destination write FIFO input.The Memory Write Controller block150controls the Shared Memory block250through bus160. The write address comes from bus360and the write command comes from signal130_1.
Memory Read Entity:

The Memory Read Entity is made of a De-queue FIFO block310_2, a Release Address Selector block300and a Memory Read Controller block200.

To detail more each task:The De-queue Destination FIFO block310_2contains the addresses of incoming data packets that have been stored for a transmission to adapter16_2. The input interface is made of an input FIFO data bus connected to the address bus360and an input FIFO write signal connected to the destination chip select signal360_2. The output interface is made of an output FIFO data bus320and an input FIFO read signal320_2, both being connected to the Release Address Selector block300.The Release Address Selector block300for destination adapter16_2is illustrated inFIG. 4. Its function is to de-queue and release memory read addresses. A State Machine301controls the address de-queue in a round-robin fashion from adapter16_1to adapter16_4. For sake of simplicity, only destination adapter16_2is described. A Comparator block330_2and a Buffer block340_2are connected to the output FIFO data bus320. The output bus of the buffer is connected to the Memory Read Controller block200through bus220. The State Machine301receives the output control signal of Comparator block330_2on signal301_2and generates a De-queue Destination read FIFO signal320_2and a memory read signal270_2. The read signal is connected to the Memory Read Controller block200, the Destination Output Buffer block280_2and the Flow Control block450. The State Machine301is clocked by the outgoing data packet clock received on signal301_5. The Release Address Selector block300performs the following tasks:reads the De-queue Destination FIFO of adapter16_2by activating signal320_2,compares its content to zero which is the default value when the FIFO is empty,if the control signal301_2is activated, performs a memory read operation and release the address into the Free Buffer Queue block400; if the control signal301_2is not activated reads the De-queue Destination FIFO of next adapter.The Memory Read Controller block200controls the Shared Memory block250through bus210. The read address comes from bus220and the read command comes from signal270_2. The data packet is transmitted from the memory to adapter16_2through the Destination Output Buffer block280_2on bus15_2.
Free Buffer Queue block (400):

The Free Buffer Queue block400contains memory addresses ready to be used. Its output bus410provides addresses to the En-queue Register for memory write operations. Its input bus220receives addresses from the Release Address Selector block300when a memory read operation has been completed.

Referring now toFIG. 5, the Flow Control block450for destination adapter16_2is mainly composed of:a Microprocessor Interface block25;a flow control logic per adapter made of:a Threshold Register block31_2,a Counter/De counter block41_2,a Substract Logic block51_2an ID register block61_2;a Serializer block70.

The structure and operation of the different blocks are now described.

The microprocessor interface block25is connected to the Control Point card21through bus20. The interface allows the user to access the Threshold register block31_2in order to predefined a threshold value.

Flow Control Logic:

It is made of a Threshold register block31_2, a Counter/De counter block41_2, a Substract logic block51_2and an ID register block61_2.

To detail more each task:

a. The Threshold register is programmed through the microprocessor interface by the user which access the Control Point card. Its output bus32_2is connected to a first port ‘A’ of the Substract logic block51_2.b. The Counter block is incremented each time a data packet is stored into the shared memory250and is decremented each time a data packet is read from the shared memory. An increment input signal is connected to the Lease Address Selector block350through signal360_2. A decrement input signal is connected to the Release Address Selector block300through signal270_2. The Counter/De counter data bus42_2is connected to a second port ‘B’ of the Substract logic block51_2.c. The Substract combinatorial logic block51_2always computes on the fly the difference between the two input ports ‘A-B’. The result is only transmitted to serializer70onto bus71when signal270_2is activated which means each time a data packet for adapter16_2is stored into shared memory250. The result represents the flow control information to be transmitted to the adapter cards. When the result is close to the predefined threshold value, this means that the traffic to the respective adapter is very low; when the result is close to zero, this means that the traffic to the respective adapter is heavy. The result is sent to all the adapters connected to the switch and when the flow control information is received by each adapter, each one may take appropriate action to adapt its traffic. As an example let's assume that there is no traffic at all in the switch and therefore the shared memory block250stores and transmits the data packets only to adapter16_2. In this case the counter/de counter is equal to zero and each adapter receives the threshold value as the flow control information for adapter16_2. This means that adapter16_2is receiving data packets without any congestion. Now, let's assume that there is a high priority traffic going on in the switch with adapter16_3. The counter block41_2is incremented each time a data packet is stored for adapter16_2but will not be decremented until the traffic for adapter16_3reduces. Therefore each adapter receives from the Substract logic a flow control information going to zero. This means that adapter16_2is not receiving data packets already sent. Therefore all adapters that want to transmit data packets to adapter16_2should reduce their traffic until the flow control information reaches again the threshold value. To recall, the present system allows a dynamic picture of the use of the shared memory of the switch engine and provides a real time information to the whole adapter cards communicating with the switch engine.
ID Register (61_2):

The ID Register block61_2provides the address of the destination adapter. In a preferred embodiment, this address is hardwired on the board on 2 bits. As an alternative, the address should be programmed from the Control Point through the microprocessor interface.

The serializer block70receives a parallel bus71made of 10 bits,8flow control bits which come from the substract logic block51_2and2ID bits which come from the ID Register block61_2. Each read access to the shared memory block250for adapter16_2activates the control signal270_2which then starts the serializer. The transmission begins with the ID bits followed by the flow control bits. This information is received by each adapter card in the hub through the serial link17.

The principle of operation of the system is now detailed as previously explained with adapter16_1transmitting a data packet to adapter16_2. Adapter16_1first builds in a conventional manner a data packet and sends it to the switch card14onto data bus-in13_1. Next, the data packet is routed by the switch card using the routing index information contained in its header. Then the data packet is transmitted to the destination adapter16_2on data bus-out15_2. In parallel with the transmission of the data packet, the flow control information is sent to all the adapters16_i through corresponding serial links17.

The incoming data packet is analyzed by the Header Detection and Packet Validation block100_1which performs the following tasks:sending the data packet destination address (port #2 in the description) to the Lease Address Selector block350through bus140;informing the Write Memory Controller block150through signal130_1to perform a write operation.

Next the Lease Address Selector block350performs the following tasks:decoding the data packet destination address and activating the corresponding chip select signal360_2;enabling the buffer block351to transmit the address stored into the En-queue Register block380_1to the Write Memory Controller block150. This address was previously taken from the Free Buffer Queue block400;storing this address into De-queue Destination FIFO block310_2;transferring the active chip select signal360_2to the Flow Control block450to increment counter block41_2.

Finally the Write Memory Controller block150stores the data packet into the Shared Memory block250.

As a background task, the Release Address Selector block300performs the following operations:reading the De-queue Destination FIFO of adapter16_2by activating signal320_2;comparing its content to zero which is the default value when the FIFO is empty;if the control signal301_2is not activated, reading the De-queue Destination FIFO of next adapter;if the control signal301_2is activated, performing a memory read operation and releasing the address into the Free Buffer Queue block400for further use.

The Read Memory Controller block200controls the Shared Memory block250through bus210. The read address comes from bus220and the read command comes from signal270_2. The data packet is transmitted from the memory to adapter16_2through the Destination Output Buffer block280_2on bus15_2.

While the data packet is transmitted to adapter16_2the Flow Control block450transmits the flow control information to all adapters on serial link17.

The counter is incremented when a data packet is stored into the shared memory250and decremeted when a data packet is read. The content of the counter/de counter is subtracted from the threshold value defined by the user at the initialization time. The result represents the flow control information: when the value is close to the threshold value the traffic to the adapter16_2is very low, when the value is close to zero the traffic to the adapter16_2is heavy. This value along with the destination adapter address is serialized by Serializer block70and sends to each adapter card in the hub.