Apparatus and method for packet forwarding with quality of service and rate control

• US 20060203721A1
• Filed: 03/11/2005
• Published: 09/14/2006
• Est. Priority Date: 03/11/2005
• Status: Active Grant

• Current Assignee: Reti Corp.
• Original Assignee: Reti Corp.
• Inventors: Wu, Chiu-tien, Wang, Lan-feng, Hsieh, Kuen-Rong
• Granted Patent: US 7,440,405 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 61/251 between different IP versions
• CPC Class Codes: H04L 61/2596 Translation of addresses of the same type other than IP, e.g. translation from MAC to MAC addresses
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/80 Responding to QoS

Abstract

A system and method for forwarding data packets with quality of service and rate control. A plurality of data packets are received from a plurality of sources. The header information of each data packet is extracted and compared against a plurality of tables, and then new header information is assembled based upon the comparison results. The data packets have their headers replaced by the new header information on the fly before being sent to their destinations, or the new header information may be dropped if certain conditions are met.

Claims

1. An apparatus for processing data packets received from a data network and forwarding the data packets to their destination according to a predefined transfer rate, the apparatus comprising:

at least one lower layer processing unit for receiving data packets from an external source and storing the data packets into an external memory buffer;

a header extracting unit in communication with the at least one lower layer processing unit, the header extracting unit capable of extracting header information from each received data packet;

a plurality of tables, each table having a plurality of entries of table information;

a search engine arbiter for receiving the extracted header information from the header extracting unit and comparing the extracted header information against the plurality of tables, the search engine creating a new header information for each received data packet based on comparison results, the search engine further being capable of discarding the extracted header information based on the comparison results;

a plurality of output queues, each output queue having an output rate and an availability indicator of queuing additional data;

a random early drop module for receiving the extracted header information from the search engine arbiter and distributing the extracted header information among the plurality of output queues, the random early drop module monitoring the availability indicator in each output queue and being capable of discarding the extracted header information; and

a plurality of transfer rate control modules for receiving the extracted header information from the plurality of output queues, each transfer rate control module being in communication with an output queue and controlling the output rate for the output queue,

wherein the at least one lower layer processing unit receives the extracted header information and retrieves the data packet identified by the extracted header information and transmits the data packet to the destination identified in the new header information.

2. The apparatus of claim 1, further comprising a packet handling unit for processing the header information that needs special processing.

3. The apparatus of claim 1, wherein the new header information is stored in along with the data packet for which the new header information is created.

4. The apparatus of claim 1, wherein the at least one lower layer processing unit inserts the new header information in each data packet before transmitting the data packet to its destination.

5. The apparatus of claim 1, further comprising a plurality of rules that determine whether service should be denied to a data packet.

6. The apparatus of claim 1, wherein the plurality of tables further comprising a layer-2 table, a flow table, and a packet classifier and filter table.

7. The apparatus of claim 1, further comprising:

a scheduling module in communication with the plurality of transfer rate control modules, the scheduling module scheduling transfer of the header identifier according to a predefined algorithm; and

an aggregated transfer control module in communication with the scheduling module, the aggregated transfer control module receiving the header identifier from the scheduling module and controlling a transfer rate of the header identifier over an output link.

8. The apparatus of claim 1, wherein the apparatus is an integrated circuit.

9. A method for processing at a device receiving data packets from a data network and forwarding the data packets to a destination according to a predefined transfer rate, comprising the steps of:

receiving a plurality of data packets from a plurality of sources at the device;

extracting a header information from each of the plurality of data packets;

comparing the extracted header information with at least one table;

if the extracted header information matches one entry in the at least one table, creating a new header information for each of the plurality of data packets;

if the extracted header information does not match any entry in the at least one table, discarding the extracted header information;

transmitting the extracted header information to a random early drop module in the device;

distributing the extracted header information among a plurality of queues;

discarding the extracted header information from a queue if the output rate of the queue exceeds a predefined criterion;

inserting the new header information in the data packet; and

transmitting the data packet to the destination listed in the new header information.

10. The method of claim 9, further comprising the step of storing the plurality of data packets into a memory device.

11. The method of claim 10, further comprising the step of retrieving the data packet identified by the extracted header information from the memory device.

12. The method of claim 9, further comprising the step of controlling an output rate for each of the plurality of queues according to a predefined criterion.

13. The method of claim 9, further comprising the step of storing the new header information into a memory device.

14. The method of claim 9, further comprising the step of removing a data packet from the memory device if a corresponding extracted header information is discarded.

15. The method of claim 9, further comprising the step of comparing the extracted header information against a set of denial of service rules.

16. The method of claim 9, further comprising the step of transmitting the extracted header information to a central processing unit (CPU) for processing if the extracted header information does not match any entry in the at least one table.

17. A gateway for processing data packets received from a plurality of data network and forwarding the data packets to their destination according to a predefined transfer rate, the gateway comprising:

a plurality of lower layer processing units, each lower layer processing unit connecting to at least one data link and receiving data packets from the at least one data link;

a header extracting unit in communication with the plurality of lower layer processing units, the header extracting unit being capable of extracting header information from the data packets received by the plurality of lower layer processing unit;

at least one table having a plurality of entries of traffic information;

a search engine arbiter unit for comparing the extracted header information received from the header extracting unit with the at least one table, the search engine arbiter being capable of generating a new header related information based on comparison results;

a flow control unit for receiving the extracted header information from the search engine arbiter unit and discarding the data packet associated with the extracted header information according to a predefined criterion; and

a plurality of output control units for receiving the extracted header information from the flow control unit and distributing the extracted header information to the lower layer processing unit, wherein the lower layer processing unit transmits a data packet associated with the extracted header information to a destination after inserting the new header related information in the data packet.

18. The gateway of claim 17, wherein each of the output control unit further comprising:

an output queue for receiving the extracted header information from the flow control unit;

a transfer rate control unit for controlling a transfer rate for the output queue; and

a scheduling unit for scheduling the extracted header information from each output queue to a lower layer processing unit specified by the new header related information.

19. The gateway of claim 18, wherein the scheduling unit is capable of scheduling data packets for transmission according to an algorithm of combined strict and weighted priorities.

20. The gateway of claim 17, wherein the search engine arbiter unit is capable of storing the new header related information into an external memory.