Method and apparatus for output rate regulation and control associated with a packet pipeline

• US 6,757,249 B1
• Filed: 10/14/1999
• Issued: 06/29/2004
• 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): WAXMAN, ANDREW
• Application Number:
  US09/418,683
• Time in Patent Office: 1,720 Days
• Field of Search: 370/389, 370/392, 370/394, 370/395.31, 370/395.4, 370/395.65, 370/412, 370/413, 370/230, 370/235, 370/236, 370/414, 370/398, 370/399, 370/401-404
• US Class Current: 370/235.1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

An apparatus having a pipeline having a series of stages. At least one of the pipeline stages has a first interface for coupling to a memory that stores output capacity information for a packet. The output capacity information is obtainable from the packet'"'"'s packet header information or internal information where the internal information is used within a service provider'"'"'s network. At least one of the pipeline stages has a second interface that receives packet size information; a third interface that receives the output capacity information; and comparison logic coupled to the second and third interfaces.

A method that involves presenting packet header information and packet size information to one or more pipeline stages where the packet header information and the packet size information correspond to a packet. Then, determining within a stage associated with the pipeline, with the packet header information, output capacity for the packet. Then, comparing within a stage associated with the pipeline, the output capacity with the packet size to determine appropriate delay for the packet.

Claims

1. An apparatus, comprising:

a pipeline having a series of stages, where, a first of said pipeline stages has a first interface for coupling to a memory that stores a pointer to output flow information for a packet, said pointer obtainable from said memory via a TOS value found within said packet'"'"'s header information or assigned by a second pipeline stage that precedes said first pipeline stage, and where, another of said pipeline stages has;

(i) a second interface to receive packet size information of said packet, (ii) a third interface to receive token bucket information for said output flow, (iii) shaping logic coupled to said second and third interfaces, and (iv) an output from said shaping logic, said output to provide a delay for said packet that is consistent with said output flow, where said second pipeline stage follows said first pipeline stage.

2. The apparatus of claim 1 wherein said output flow information further comprises a tagging policy.

3. The apparatus of claim 1 wherein said output flow information further comprises a marking policy.

4. The apparatus of claim 3 wherein said output flow information further comprises a second TOS value to be placed into said packet'"'"'s header, said marking policy to indicate said second TOS value is to be placed into said packet'"'"'s header.

5. The apparatus of claim 1 wherein said token bucket information further comprises a token number parameter and a token rate parameter.

6. A method, comprising:

presenting packet header information from a second packet to a first pipeline stage and presenting packet size information and other information from which delay can be calculated for a first packet to a second pipeline stage;

retrieving a pointer to output flow information for said second packet with said first pipeline stage and calculating an appropriate output delay for said first packet with said second pipeline stage;

presenting packet size information and other information from which delay can be calculated for said second packet to said second pipeline stage and queuing a packet identifier into an output packet organizer at a location that corresponds to said delay for said first packet with a third pipeline stage, where, said packet identifier identifies where said first packet can be found in a packet buffer.

7. The method of claim 6 further comprising looking up said other information for said second packet with information found in said output flow information for said second packet.

8. The method of claim 6 herein said retrieving further comprises looking up, with a TOS value found in said second packet header information, from a memory containing said pointer.

9. The method of claim 6 wherein said output flow information for said second packet further comprises a marking policy for said second packet.

10. The method of claim 9 further comprising selecting an output TOS value found in said output flow information for said second packet based upon said marking policy.

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

a) a first pipeline stage having a data bus to receive a first output flow identifier, where, said first output flow identifier points to a first memory location where parameters for a first output flow are located, where said first output flow is for a first packet that is to be sent from a packet buffer to said first user, and where, said first output flow is characterized at least by a first output rate; and

b) a second pipeline stage having shaping logic circuitry coupled to register storage space, said register storage space to provide to said shaping logic circuitry at least one characteristic of said first output rate, said second pipeline stage to;

(i) determine a delay for said first packet that conforms to said first output rate,

(ii) during a same pipeline cycle in which;

said first pipeline stage receives upon said data bus a second output flow identifier that points to a second memory location where parameters for a second output flow are located, where, said second output flow is for a second packet that is to be sent from said packet buffer to said second user, and where, said second output flow is characterized at least by a second output rate.

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

13. The apparatus of claim 12 wherein said memory is to correlate said first output flow to a first TOS lookup value and is to correlate said second output flow to a second TOS lookup value.

14. The apparatus of claim 13 further comprising another pipeline stage that precedes said first pipeline stage and assigns said first TOS lookup value if said pipeline processes said first packet as it travels through both an input edge and an output edge of said network.

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 information further comprises a Source Port (SP) associated with an Internet Protocol (IP) header.

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

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

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

20. The apparatus of claim 15 wherein said information further comprises a Type of Service (TOS) associated with an Internet Protocol (IP) header.

21. The apparatus of claim 11 wherein said first packet can be higher in priority than said second packet.

22. The apparatus of claim 21 wherein said first packet can be a control packet that carries maintenance information for said network and said second packet can be a real time packet.

23. The apparatus of claim 22 wherein said second packet can carry voice information if said second packet is a real time packet.

24. The apparatus of claim 22 wherein said second packet can carry video conference information if said packet is a real time packet.

25. The apparatus of claim 11 wherein said parameters for a first output flow at least include a marking policy for said first packet, said marking policy identifying which of a plurality of TOS values should be added to said first packet'"'"'s header information.

26. The apparatus of claim 11 wherein said parameters for a first output flow at least include a TOS value to be added to said first packet'"'"'s header information.

27. The apparatus of claim 11 wherein said parameters for a first output flow at least include a location type parameter that indicates whether or not said packet is destined for a queue that is not oversubscribed.

28. The apparatus of claim 11 wherein said parameters for a first output flow at least include a tagging policy that indicates how said first packet should be treated if said first packet does not conform to said first output flow.

29. The apparatus of claim 11 wherein said first output flow can be a quantitative output flow.

30. The apparatus of claim 29 wherein said first output rate is described by 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, said register storage space to store said token number and said token rate.

31. The apparatus of claim 11 wherein said first output flow can be a qualitative output flow.

32. The apparatus of claim 11 wherein said parameters for a first output flow at least include a pointer to a third memory location where one or more parameters that describe said first input rate said at least one characteristic of said first output rate are located.

33. The apparatus of claim 11 further comprising a third pipeline stage that:

(i) places;

a first packet identifier into a location within an output packet organizer, said output packet organizer having different locations that correspond to different waiting times for said first packet within said packet buffer, said location within said output packet organizer corresponding to said delay, said first packet identifier identifying where said first packet can be found within said buffer memory

(ii) during a same pipeline cycle in which;

said second pipeline stage determines a delay for said second packet that conforms to said second output rate.

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

a. retrieving

in response to a first packet that is to be sent from a packet buffer to said first user, a first output flow identifier that points to a first memory location where a first output flow is located, said first output flow having a first output rate and a first priority; and

,

b. determining

a location within an output packet organizer, said output packet organizer having different locations that correspond to different waiting times for said first packet within said packet buffer, said determined location within said output packet organizer corresponding to a waiting time for said first packet that conforms to said first output rate and said first priority,

during a same pipeline cycle in which;

a second output flow identifier that points to a second memory location where a second output flow is located is retrieved, said second output flow having a second output rate and a second priority, said retrieving of said second output flow in response to a second packet that is to be sent from said packet buffer to said second user.

35. The method of claim 34 wherein said first output flow further comprises a pointer to a third memory location where one or more parameters that describe said first output rate are located.

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

37. The method of claim 34 wherein said first priority is higher than said second priority.

38. The method of claim 37 wherein said first packet is a control packet that carries maintenance information for said network and said second packet is a real time packet.

39. The method of claim 38 wherein said second packet carries voice information.

40. The method of claim 38 wherein said second packet carries video conference information.

41. The method of claim 37 wherein said first packet is a real time packet and said second packet is a data packet.

42. The method of claim 41 wherein said first packet carries voice information.

43. The method of claim 41 wherein said first packet carries video conference information.

44. The method of claim 41 wherein said second packet carries at least a portion of an email message.

45. The method of claim 41 wherein said first output rate is described by 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.

46. The method of claim 34 further comprising 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 output rate, said second value representing the amount of data said packet carries.

47. The method of claim 46 further comprising discarding said first packet if said second value is greater than said first value.

48. The method of claim 47 wherein said first packet is a real time packet.

49. The method of claim 46 wherein said determined location within said output packet organizer corresponds to a lowest waiting time of said different waiting times if said second value is less than said first value.

50. The method of claim 46 wherein said determined location within said output packet organizer corresponds to a longer waiting time than a lowest waiting time, of said different waiting times, if said second value is greater than said first value.

51. The method of claim 50 wherein said determined location within said output packet organizer corresponds to a waiting time that is a function of the difference between said first value and said second value.

52. The method of claim 46 wherein said first output flow is a quantitative output flow.

53. The method of claim 46 wherein said first output flow is a qualitative output flow.

54. The method of claim 34 wherein said first priority further comprises a Type of Service (TOS) parameter.

55. The method of claim 34 further comprising:

(i) placing;

a first packet identifier into said determined location within said output packet organizer, said first packet identifier identifying where said first packet can be found within said buffer memory

(ii) during a same pipeline cycle in which;

a second location within said output packet organizer is determined, said second location corresponding to a waiting time for said second packet that conforms to said second output rate and said second priority.

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

a) a first pipeline stage comprising;

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

(i) during a first pipeline cycle;

a first output flow identifier;

(ii) during a second pipeline cycle;

a second output flow identifier; and

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

1) a second 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 said first output flow identifier;

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

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

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

2) register space in which to store;

(i) 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;

(ii) 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;

(i) during said second pipeline cycle;

said first delay;

(ii) during said third pipeline cycle;

said second delay.

57. The apparatus of claim 56 wherein said first memory correlates said first output flow identifier to a lookup TOS parameter.

58. The apparatus of claim 57 wherein another pipeline stage precedes said first pipeline stage and where said lookup TOS parameter is assigned by said another stage if said pipeline is located at both an input edge and an output edge of said network relative to the travels of said first output packet.

59. The apparatus of claim 57 wherein said lookup TOS parameter was embedded in said first output packet'"'"'s header within said network if said pipeline is located only at an output edge of said network relative to the travels of said first output packet.

60. The apparatus of claim 56 where, said second data bus is also to receive a marking policy from said second memory from said location pointed to by said first output flow identifier, said marking policy to confirm that said first TOS parameter is to be located within said first output packet'"'"'s header while said first output packet exits said network en route to said first user.

61. The apparatus of claim 56 wherein said second data bus is also to receive a tagging policy from said second memory from said location pointed to by said first output flow identifier, said tagging policy to indicate how said first output packet is to be treated if said first output packet is deemed non conforming to said first output flow.

62. The apparatus of claim 56 wherein said second data bus is also to receive a location type parameter from said second memory from said location pointed to by said first output flow identifier, said location type parameter to indicate that said first output flow is a quantitative or qualitative output flow.

63. The apparatus of claim 56 wherein said first parameter further comprises a Current Token # parameter, said Current Token # parameter to indicate how many tokens existed in said first output flow after the last time it was used.

64. The apparatus of claim 56 wherein said first parameter further comprises a Token Rate parameter, said Token Rate parameter to define how many tokens per unit time said first output flow receives per unit time.

65. The apparatus of claim 56 wherein said first parameter further comprises a Burst parameter, said Burst parameter to indicate the maximum number of tokens for said first output flow that can be consumed during a single cycle of said pipeline.

66. The apparatus of claim 56 wherein said first parameter further comprises a Max Depth parameter, said Max Depth parameter to indicate the maximum number of tokens that a bucket for said first output flow can hold.

67. The apparatus of claim 56 wherein said second pipeline stage first parameter further comprises a Bucket Timestamp parameter, said Bucket Timestamp parameter to indicate the last time the number of tokens available for said first output flow was updated.

68. The apparatus of claim 56 wherein said first output flow can be either a qualitative flow or a quantitative flow.

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

a) a first pipeline stage having a data bus to receive a first output flow identifier, where, said first output flow identifier points to a first memory location where parameters for a first output flow are located, where said first output flow is for a first packet that is to be sent from a packet buffer to said first user, and where, said first output flow is characterized at least by a first output rate; and

b) a second pipeline stage having shaping logic circuitry coupled to register storage space, said register storage space to provide to said shaping logic circuitry at least one characteristic of said first output rate, said second pipeline stage to;

(i) determine

a delay for said first packet that conforms to said first output rate,

(ii) during a same pipeline cycle in which

said first pipeline stage receives upon said data bus a second output flow identifier that points to a second memory location where parameters for a second output flow are located, where, said second output flow is for a second packet that is to be sent from said packet buffer to said second user, and where, said second output flow is characterized at least by a second output rate.

70. The machine readable medium of claim 69 wherein said description is a VHDL description.

71. The machine readable medium of claim 69 wherein said description is an RTL level description.