Method and apparatus for input rate regulation associated with a packet processing pipeline

• US 6,882,642 B1
• Filed: 10/14/1999
• Issued: 04/19/2005
• Est. Priority Date: 10/14/1999
• Status: Expired due to Fees

• Current Assignee: Nokia Solutions and Networks US LLC (Nokia Corporation)
• Original Assignee: Nokia, Inc. (Nokia Corporation)
• Inventors: Ho, Chi Fai, Kejriwal, Prabhas
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): JONES, PRENELL P
• Application Number:
  US09/419,728
• Time in Patent Office: 2,014 Days
• Field of Search: 370/388, 370/235, 370/218, 370385-395, 370/372, 370/357, 370/380, 370/383, 370/412, 712/23, 712/41, 712/52, 712/217, 712/218, 712/213, 712/240, 236230-235, 233/468, 233/396, 233/402, 233/229, 233/408, 714/738, 714/38, 714/25, 714763-775, 709226-229, 709/104, 709/243, 709/219, 709/252, 709230-236, 375/240, 715/15, 715/22, 345/506
• US Class Current: 370/388
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• 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/41 by acting on aggregated flows or links

Abstract

A method is described that involves presenting packet header information from a packet and packet size information for the packet to a pipeline that comprises multiple stages. One of the stages identifies, with the packet header information, where input flow information for the packet is located. The input flow information is then fetched. The input flow information identifies where input capacity information for the packet is located and the input capacity information is then fetched. Another of the stages compares an input capacity for the packet with the packet'"'"'s size and indicates whether the packet is conforming or non-conforming based upon the comparison. The input capacity is calculated from the input capacity information.

Claims

1. An apparatus, comprising:

a pipeline having a series of stages, one of said pipeline stages having a content addressable memory interface for coupling to a content addressable memory that stores a pointer to input flow information for a packet, said pointer to said input flow information obtainable from said content addressable memory with information from said packet'"'"'s header, another of said pipeline stages having a first interface that receives information indicative of said packet'"'"'s size and a second interface that receives said input flow information, said input flow information comprising a pointer to information describing an input bucket for said packet, said other pipeline stage further comprising a register to store said input bucket information and policing logic coupled to both said first interface and said register.

2. The apparatus of claim 1 wherein said input capacity information is stored within an input flow table that is stored within a second memory.

3. The apparatus of claim 1 wherein said input flow information further comprises priority information.

4. The apparatus of claim 1 wherein said input flow information further comprises a tagging policy.

5. The apparatus of claim 1 further comprising a discard tag output coupled to said comparison logic, said discard tag output to indicate whether or not said packet conforms to a user input rate, said input capacity based upon said user input rate.

6. A method comprising:

a) presenting packet header information from a packet and packet size information for said packet to a pipeline that comprises multiple stages;

b) identifying at one of said stages, with said packet header information, where input flow information for said packet is located;

c) fetching said input flow information, said input flow information identifying where input capacity information for said packet is located;

d) fetching said input capacity information;

e) comparing, within another of said stages, an input capacity for said packet with said packet'"'"'s size and indicating whether said packet is conforming or non-conforming based upon said comparison, said input capacity calculated from said input capacity information.

7. The method of claim 6 wherein said identifying further comprises looking up said input flow information from a content addressable memory with said packet header information.

8. The method of claim 6 wherein said user input flow information further comprises priority information.

9. The method of claim 8 further comprising placing said priority information into a control label that is made accessible to other stages within said pipeline.

10. The method of claim 6 further comprising, if said packet is non-conforming, indicating whether said packet must be discarded.

11. An apparatus for regulating traffic offered to a network by a first user of said network and a second user of said network, said apparatus comprising:

a) a first pipeline stage that operates to retrieve, in response to a first packet being sent from said first user to said network, a first input flow identifier that points to a first memory location where a first input flow is located, said first input flow allocated to said first user, said first input flow having a first input rate; and

,

b) a second pipeline stage that;

i) operates to retrieve

one or more parameters that describe said first input rate so that it can be determined if said sending of said first packet conforms to said first input rate

ii) while

said first pipeline stage operates to retrieve a second input flow identifier that points to a second memory location where a second input flow is located, said second input flow allocated to said second user, said second input flow having a second input rate, said retrieving of a second input flow identifier in response to a second packet being sent from said second user to said network.

12. The apparatus of claim 11 further comprising a memory for storing said input flow identifier, said memory coupled to said first pipeline stage.

13. The apparatus of claim 12 wherein said memory further comprises a content addressable memory (CAM).

14. The apparatus of claim 13 wherein said first packet further comprises a header and said CAM is configured as a lookup table that provides said first input flow identifier in response to said first pipeline stage providing, as an input to said CAM lookup table, at least a portion of information found within said header.

15. The apparatus of claim 11 further comprising a register that stores a control label, said register coupled to said first and second pipeline stages, said first packet having a header, said control label having information found within said header.

16. The apparatus of claim 15 wherein said header information further comprises a Source Port (SP) associated with an Internet Protocol (IP) header.

17. The apparatus of claim 15 wherein said header information further comprises a Destination Port (DP) associated with an Internet Protocol (IP) header.

18. The apparatus of claim 15 wherein said header information further comprises a Source Address (SA) associated with an Internet Protocol (IP) header.

19. The apparatus of claim 15 wherein said header information further comprises a Destination Address (DA) associated with an Internet Protocol (IP) header.

20. The apparatus of claim 17 wherein said header information further comprises a Next Hop Address (NHA) associated with an Internet Protocol (IP) header.

21. The apparatus of claim 15 wherein said header information further comprises Layer 2 information.

22. The apparatus of claim 21 wherein said header information further comprises a Data Link Connection ID (DLCI) associated with a Frame Relay packet.

23. The apparatus of claim 15 wherein said control label further comprises control information formatted by a packet aggregation layer.

24. The apparatus of claim 23 wherein said control information further comprises a packet identifier that identifies where said first packet may be found within a packet buffer.

25. The apparatus of claim 23 wherein said control information further comprises a length indicator that indicates the size of said first packet.

26. The apparatus of claim 11 wherein said one or more parameters that describe said first input rate further comprise a token number and a token rate, wherein said token number corresponds to an amount of data, wherein said token rate corresponds to a number of tokens that are to be added to said token number per unit of time.

27. The apparatus of claim 11 wherein said first input flow further comprises a priority parameter that describes the priority of said first packet within said network.

28. The apparatus of claim 27 wherein said priority parameter further comprises a Type of Service (TOS) value to be placed into a header of said first packet prior to entry of said first packet into said network.

29. The apparatus of claim 11 wherein said first input flow further comprises a memory pointer that points to a third memory location where said one or more parameters that describe said first input rate are located.

30. A method for regulating traffic offered to a network by a first user of said network and a second user of said network, said method comprising:

a) using a first pipeline stage to retrieve, in response to a first packet being sent from said first user to said network, a first input flow identifier that points to a first memory location where a first input flow is located, said first input flow allocated to said first user, said first input flow having a first input rate; and

b) using a second pipeline stage to retrieve

one or more parameters that describe said first input rate so that it can be determined if said sending of said first packet conforms to said first input rate

while using said first pipeline state to retrieve

a second input flow identifier that points to a second memory location where a second input flow is located, said second input flow allocated to said second user, said second input flow having a second input rate, said retrieving of a second input flow identifier in response to a second packet being sent from said second user to said network.

31. The method of claim 30 wherein said first input flow comprises a pointer to a third memory location where said one or more parameters that describe said first input rate are located.

32. The method of claim 31 further comprising retrieving said first input flow with said first input flow identifier and using said pointer to said retrieve said one or more parameters that describe said first input rate.

33. The method of claim 30 wherein said one or more parameters that describe said first input rate further comprise a token number and a token rate, wherein said token number corresponds to an amount of data, wherein said token rate corresponds to a number of tokens that are to be added to said token number per unit of time.

34. The method of claim 33 further comprising multiplying said token rate by an elapsed time between said sending of said first packet and a sending of a third packet from said first user, said third packet sent immediately prior to said first packet in a sequence of packets sent by said first user.

35. The method of claim 34 further comprising adding said token number to said multiple of said token rate and said elapsed time in order to determine a number of tokens that corresponds to an amount of data that conforms to said first input rate.

36. The method of claim 30 further comprising, in order to said determine if said sending of said first packet conforms to said first input rate, comparing a first value with a second value, said first value representing an amount of data that can be carried by said first packet yet still conform to said first input rate, said second value representing the amount of data said packet carries.

37. The method of claim 36 further comprising tagging said first packet as conforming if said first value is greater than said second value.

38. The method of claim 36 further comprising tagging said first packet as non-conforming if said first value is less than said second value.

39. The method of claim 30 wherein said first input flow further comprises a priority parameter that describes the priority of said first packet within said network.

40. The method of claim 39 wherein said priority parameter further comprises a Type of Service (TOS) value to be placed into a header of said first packet prior to entry of said first packet into said network.

41. An apparatus for regulating traffic offered to a network by a first user of said network and a second user of said network, said apparatus comprising:

a) a first pipeline stage coupled to a first memory, said first memory to provide to said first pipeline stage;

(i) during a first pipeline cycle;

a first input flow identifier;

(ii) during a second pipeline cycle;

a second input flow identifier; and

b) a second pipeline stage that follows said first pipeline stage, said second pipeline stage comprising;

1) a data bus to receive from a second memory;

(i) during said second pipeline cycle and from a location of said second memory pointed to by a first output flow identifier;

parameters belonging to said first input flow;

(ii) during a third pipeline cycle and from a location of said second memory pointed to by said second output flow identifier;

parameters belonging to said second input flow;

2) register space in which to store;

(iii) during said second pipeline cycle;

parameters from which a first amount of data can be calculated, said first packet being in conformance with said first input flow'"'"'s input rate if said first packet'"'"'s size is not greater than said first amount of data;

(iv) during said third pipeline cycle;

parameters from which a second amount of data can be calculated, said second packet being in conformance with said second input flow'"'"'s input rate if said second packet'"'"'s size is not greater than said second amount of data;

3) logic circuitry to determine;

(v) during said second pipeline cycle;

if said first packet is in conformance with said first input flow'"'"'s input rate;

(vi) during said third pipeline cycle;

if said first packet is in conformance with said first input flow'"'"'s input rate.

42. The apparatus of claim 41 further comprising a third pipeline stage that follows said second pipeline stage, said third pipeline stage coupled to a content addressable memory capable of providing:

(i) during said third pipeline cycle;

a first output connection identifier for said first packet;

(ii) during a fourth pipeline cycle;

a second output connection identifier for said second packet.

43. The apparatus of claim 42 further comprising fourth and fifth pipeline stages that respectively follow said third pipeline stage, said fourth and fifth pipeline stages capable of regulating traffic offered by said network to a third user of said network and a fourth user of said network, where:

said fourth pipeline stage further comprises a memory interface capable of receiving;

(i) during said first pipeline cycle;

a first output flow identifier;

(ii) during said second pipeline cycle;

a second output flow identifier; and

said fifth pipeline stage further comprises;

1) a second data bus capable of receiving;

(i) during said second pipeline cycle and from a memory location pointed to by said first output flow identifier;

a first TOS parameter for a first output packet, said first output packet destined for said third user;

(ii) during said third pipeline cycle and from a memory location pointed to by said second output flow identifier;

a second TOS parameter for a second output packet, said second output packet destined for said fourth user;

2) register space in which to store;

(iii) during said second pipeline cycle;

a first parameter from which a first delay for said first packet that is consistent with said first output flow can be calculated;

(iv) during said third pipeline cycle;

a second parameter from which a second delay for said second packet that is consistent with said second output flow can be calculated;

3) logic circuitry to calculate;

(v) during said second pipeline cycle;

said first delay;

(vi) during said third pipeline cycle;

said second delay.

44. A method, comprising:

a) during a first pipeline cycle;

with a first pipeline stage;

identifying a memory location where input flow information for a packett can be found, said packet sent from a user of a network to said network;

with a second pipeline stage that follows said first pipeline stage;

identifying a memory location where output flow information for a second packet can be found, said second packet to exit said network so that it can be received by a second user of said network;

b) during a second pipeline cycle that follows said first pipeline cycle;

with a third pipeline stage that follows said first pipeline stage but precedes said second pipeline stage;

fetching said input flow information and determining if said first packet conforms to said input flow'"'"'s input rate;

with a fourth pipeline stage that follows said second pipeline stage;

fetching said output flow information and calculating a delay for said second packet that conforms to said output flow'"'"'s output rate.

45. The method of claim 44 further comprising:

c) during a third pipeline cycle that follows said second pipeline cycle;

with a fourth pipeline stage that follows said third pipeline stage but precedes said second pipeline stage;

looking up an output port for said first packet.

46. A machine readable medium containing a description of a semiconductor circuit design for regulating traffic offered to a network by a first user of said network and a second user of said network, said description comprising a description of:

a) a first pipeline stage to lookup a first input flow identifier, where, said first input flow identifier points to a first memory location where parameters for a first input flow are located, where said first input flow is for a first packet that is sent from said first user and stored into a packet buffer, and where, said first input flow is characterized at least by a first input rate; and

,

b) a second pipeline stage having policing logic circuitry coupled to register storage space, said register storage space to provide to said policing logic circuitry a characteristic of said first input rate, said second pipeline stage to;

(i) determine

whether said first packet conforms to said first output rate,

(ii) during a same pipeline cycle in which

said first pipeline stage looks up a second input flow identifier that points to a second memory location where parameters for a second input flow are located, where, said second input flow is for a second packet that is sent from said second user and stored into said packet buffer, and where, said second input flow is characterized at least by a second output rate.

47. The machine readable medium of claim 46 wherein said description is a GDS-II description.

48. The machine readable medium of claim 46 wherein said description is an RTL level description.