Method and apparatus for controlling the flow of variable-length packets through a multiport switch

• US 6,046,979 A
• Filed: 05/04/1998
• Issued: 04/04/2000
• Est. Priority Date: 05/04/1998
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Bauman, James A.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US09/072,148
• Time in Patent Office: 701 Days
• Field of Search: 370/229, 370/230, 370/232, 370/233, 370/234, 370/235, 370/236, 370/252, 370/389, 370/397, 370/399, 370/409, 370/412, 370/413, 370/468, 370/253, 370/414
• US Class Current: 370/229
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A method and apparatus for controlling the flow of variable-length packets to a multiport switch involve accessing forwarding information in a memory based at least partially on layer 4 information from a packet and then forwarding the packet only if the packet is within a bandwidth consumption limit that is specified in the forwarding information. In a preferred embodiment, a credit bucket algorithm is used to ensure that packet flows are within specified bandwidth consumption limits. The preferred method for implementing the credit bucket algorithm to control flows of packets involves first receiving a particular packet from a flow and then stripping the layer 2 header information from the packet. The layer 3 and layer 4 information from the packet is then used to look-up flow-specific forwarding and flow control information in a memory that stores a linked list of table entries that includes the fields necessary to implement the credit bucket algorithm. The credit bucket algorithm is implemented in embedded devices within an application-specific integrated circuit, allowing the control of packet flows based on the application of the flow.

Claims

1. A method of controlling the flow of variable-length packets on data links connected to a multiport switch comprising steps of:

receiving a packet that includes packet-specific header information at said multiport switch;

accessing a memory that contains forwarding information, said forwarding information including bandwidth management information;

searching said memory based on transmission control protocol, TCP, or user datagram protocol, UDP, information, and internet protocol, IP, or internet packet exchange, IPX, information found within said packet-specific header information of said packet;

locating, in said memory, forwarding information that is related to said packet;

extracting bandwidth management information from said forwarding information that is related to said packet, wherein said bandwidth management information includes a bandwidth consumption limit that is relevant to forwarding said packet;

comparing said extracted bandwidth management information to said packet;

forwarding said packet within said multiport switch when said comparison indicates that forwarding said packet will not exceed said bandwidth consumption limit; and

dropping said packet from said multiport switch or tagging said packet with an adjusted priority before forwarding of said packet within said multiport switch when said comparison indicates that forwarding said packet will exceed said bandwidth consumption limit.

2. The method of claim 1 wherein said bandwidth management information is based at least partially on an identification of an application protocol within said TCP or UDP information.

3. The method of claim 2 wherein the step of comparing includes steps of:

determining if a pre-established time interval has expired by comparing the time said packet was received by said multiport switch to a last time that said forwarding information related to said packet was accessed;

refreshing a credit bucket included within said bandwidth management information if said pre-established time interval has expired;

comparing said credit bucket, whether refreshed or not, to said packet; and

forwarding said packet through said multiport switch if said credit bucket contains a number of credits that represents at least the quantity of data in said packet.

4. The method of claim 3 further including the step of adjusting one of said pre-established time interval and the size of said credit bucket included within said bandwidth management information to change a characteristic of a flow of variable-length packets.

5. An apparatus for controlling a flow of variable-length packets through a multiport switch comprising:

means for receiving a packet that is part of said flow of variable-length packets wherein said packet includes packet-specific header information related to layer 3 and layer 4 protocols;

memory having searchable registers that store flow-specific packet forwarding information including application protocol information contained in said layer 4 protocol;

means for locating, within said memory, flow-specific packet forwarding information specific to said flow of variable-length packets that said received packet is part of, based at least partially on said application protocol information;

means, formed in circuitry that is specific to packet flow control, for comparing the time said received packet arrived in said switch to the time that said flow-specific packet forwarding information specific to said flow was previously accessed by another packet to determine if a pre-established time interval has expired;

means, formed in circuitry that is specific to packet flow control, for comparing a credit bucket value that indicates a maximum size packet to the size of said received packet and for forwarding said received packet when the size of said received packet is less than or equal to said credit bucket value that indicates said maximum size packet, and for dropping or limiting said forwarding of said received packet when said received packet is larger than said credit bucket value that indicates said maximum size packet; and

means for decrementing said credit bucket value each time a packet from said flow of variable-length packets is forwarded and for refreshing said credit bucket value back to a pre-established credit bucket value each time it is determined that said pre-established time interval has expired.

6. The apparatus of claim, 5 wherein said means for locating, said means for comparing the time, said means for comparing said credit bucket value, and said means for decrementing are formed within the physical boundaries of a single application-specific integrated circuit.

7. The apparatus of claim, 6 further including a direct data connection between said memory and said single application-specific integrated circuit.

8. The apparatus of claim, 5 further including a means for selecting bits from a system counter that are representative of said pre-established time interval.

9. A method of controlling the flow of variable-length packets through a transmission control protocol, TCP, and internet protocols, IP, compatible multiport switch wherein said variable-length packets include layer 2, layer 3, and layer 4 header information comprising the steps of:

receiving a packet of a particular length within said multiport switch;

stripping layer 2 header information from said packet;

accessing a memory that contains flow-specific information;

utilizing layer 3 and layer 4 header information from said received particular length packet to look-up flow-specific information in said accessed memory;

comparing said flow-specific information to the length of said particular length packet and to a clock value that is representative of the time that said packet was received by said multiport switch; and

forwarding said particular length packet through said multiport switch if the length of said particular length packet does not exceed a maximum packet length as determined by a credit bucket indicator included within said flow-specific information.

10. The method of claim 9 further including the step of adjusting said maximum packet length to a preselected length represented by a credit refresh indicator included within said flow-specific information when said clock value indicates that a preselected time interval represented by a time select indicator included within said flow-specific information has expired.

11. The method of claim 10 further including the step of adjusting said preselected time interval or said maximum packet length to change a characteristic of the flow of variable-length packets through said multiport switch.

12. The method of claim 9 further including the step of adding a preselected credit value to said credit bucket indicator each time a preselected time interval has expired.

13. A method of controlling the flow of variable-length packets on data links connected to a multiport switch comprising steps of:

receiving a packet that includes packet-specific header information at said multiport switch;

accessing a memory that contains forwarding information, said forwarding information including bandwidth management information;

searching said memory based on said packet-specific header information of said packet;

locating, in said memory, forwarding information that is related to said packet;

extracting bandwidth management information from said forwarding information that is related to said packet, and isolating a time select vector that indicates significant bits of a system counter and determines a pre-established time interval, wherein said bandwidth management information includes a bandwidth consumption limit that is relevant to forwarding said packet;

comparing said extracted bandwidth management information to said packet;

forwarding said packet within said multiport switch when said comparison indicates that forwarding said packet will not exceed said bandwidth consumption limit; and

dropping said packet from said multiport switch or tagging said packet with an adjusted priority before forwarding of said packet within said multiport switch when said comparison indicates that forwarding said packet will exceed said bandwidth consumption limit.

14. The method of claim 13 wherein said step of extracting bandwidth management information includes a step of isolating a time stamp vector that indicates when said forwarding information was last accessed.

15. The method of claim 14 wherein said step of extracting bandwidth management information includes a step of isolating a credit_-- bucket vector that represents a maximum amount of data that can be forwarded in a remaining portion of a current time interval, wherein said current time interval is initially equal to said pre-established time interval.

16. The method of claim 15 wherein said step of extracting bandwidth management information includes a step of isolating a credit_-- refresh vector that represents a maximum amount of data that can be forwarded in said pre-established time interval.

17. The method of claim 16 wherein said step of comparing said bandwidth management information includes steps of:

utilizing said time select vector that indicates significant bits of a system counter to obtain a clock vector that represents an arrival time of said packet;

comparing said clock vector to said time stamp vector that indicates when said forwarding information was last accessed to determine if said pre-established time interval has expired;

if said pre-established time interval has not expired, comparing said credit bucket vector to said packet and forwarding said packet if said packet is within said maximum amount of data that can be forwarded; and

if said pre-established time interval has expired, updating said bandwidth consumption limit according to said credit_-- refresh vector and comparing said updated bandwidth consumption limit to said packet to determine if said packet is within said updated bandwidth consumption limit and forwarding said packet if said packet is within said updated bandwidth consumption limit.

18. The method of claim 17 further including a step of updating said credit bucket vector when said packet is forwarded within said switch and if said pre-established time interval has not expired.

19. The method of claim 17 further including the step of updating said credit bucket vector with said credit_-- refresh vector when said pre-established time interval has expired.