Event based rate policing with a jumping window

• US 6,233,240 B1
• Filed: 10/26/1999
• Issued: 05/15/2001
• Est. Priority Date: 10/27/1998
• Status: Expired due to Fees

• Current Assignee: Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Original Assignee: Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Inventors: Homberg, Michael J., Barbas, Steve N.
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/426,600
• Time in Patent Office: 567 Days
• Field of Search: 370/253, 370/234, 370/235, 370/232, 370/233, 370/397, 370/230, 370/231, 370/236, 370/389, 370/392, 370/394, 370/395
• US Class Current: 370/395.62
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 2012/5687 Security aspects
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 41/5019 Ensuring fulfilment of SLA
• CPC Class Codes: H04L 41/5022 by giving priorities, e.g. assigning classes of service
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/225 Determination of shaping rate, e.g. using a moving window
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/245 using preemption
• CPC Class Codes: H04L 47/27 : Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/29 : using a combination of thresholds
• 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/32 : by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/39 : Credit based
• CPC Class Codes: H04L 47/50 : Queue scheduling
• CPC Class Codes: H04L 47/6215 : Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 : Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 61/00 : Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 65/1101 : Session protocols
• CPC Class Codes: H04L 65/80 : Responding to QoS

Abstract

A system and method for performing event-based rate policing using varying window start times. Rate policing overhead, including counter and timer monitoring and resetting, is performed only as needed and in response to actual received traffic on each connection. As the last bit of a data unit is received from an external network, an “event time stamp” is generated and associated with the data unit, for example as part of an internal header or trailer attached to the data unit. To determine if a rate policing window was active when the frame was received, the event time stamp is compared with a sum of a window start time and a window period value stored in association with the connection on which the data unit was received. If the associated event time stamp indicates a time prior to the sum of the associated window start time and window period, then a rate policing window is determined to have been active when the frame was received. In that case, rate policing is performed on the received frame with respect to the active rate policing window. If a rate policing window was not active when the frame was received, then a new rate policing window is started, and the frame is rate policed in a new rate policing window, which is started at a time equal to the event time stamp associated with the received frame.

Claims

1. A method of determining an event-based rate policing window, comprising:

receiving a data unit;

generating an event time stamp reflecting a time at which said data unit was received;

associating said event time stamp with said data unit;

generating a rate policing window end time by adding a rate policing window start time to a rate policing window duration;

comparing said event time stamp with said rate policing window end time;

starting, in the event that said event time stamp indicates a time subsequent to said rate policing window end time, a new rate policing window;

wherein said data unit is received on a virtual connection, and wherein said rate policing window start time, said rate policing window end time, said rate policing window duration, and said new rate policing window are associated with said virtual connection; and

wherein said rate policing window start time defines a time at which a current rate policing window started, wherein said rate policing window duration defines a length of said current rate policing window, wherein said rate policing window end time defines an end of said current rate policing window, and wherein said current rate policing window defines a time interval during which a predetermined amount of bandwidth is reserved as guaranteed bandwidth for use by data units received on said virtual connection during said current rate policing window.

2. The method of claim 1, further comprising:

performing, in the event said event time stamp does not indicate a time subsequent to said rate policing window end time, rate policing on said data unit, said rate policing including determining whether said data unit is to be considered part of said guaranteed bandwidth of said virtual connection.

3. The method of claim 2, further comprising:

writing, in the event that said data unit is not to be considered part of said guaranteed bandwidth of said virtual connection, a discard enabled indicator associated with said data unit.

4. The method of claim 3, wherein said discard enabled indicator is a discard enabled bit within said data unit.

5. The method of claim 3, wherein said discard enabled indicator is a flag in a descriptor data structure associated with at least one memory buffer storing said data unit.

6. The method of claim 1, wherein said starting said new rate policing window includes setting said rate policing window start time associated with said virtual connection equal to said event time stamp.

7. The method of claim 1, wherein said starting said new rate policing window includes setting a field associated with said virtual connection to a predetermined value.

8. The method of claim 7, wherein said predetermined value represents the maximum amount of data which may be received using said guaranteed bandwidth over said connection during said rate policing window duration.

9. The method of claim 7, wherein said predetermined value is zero.

10. A system for determining an event-based rate policing window, comprising:

receiver logic operable to receive a data unit, generate an event time stamp reflecting a time at which said data was received, and associate said event time stamp with said data unit;

rate policing logic operable to

generate a rate policing window end time by adding a rate policing window start time to a rate policing window duration,

compare said event time stamp with rate policing window end time, and

start, in the event that said event time stamp indicates a time subsequent to said rate policing window end time, a new rate policing window;

wherein said data unit is received on a virtual connection, and wherein said rate policing window start time, said rate policing window end time, said rate policing window duration, and said new rate policing window are associated with said virtual connection; and

wherein said rate policing window start time defines a time at which a current rate policing window started, wherein said rate policing window duration defines a length of said current rate policing window, wherein said rate policing window end time defines an end of said current rate policing window, and wherein said current rate policing window defines a time interval during which a predetermined amount of bandwidth is reserved as guaranteed bandwidth for use by data units received on said virtual connection during said current rate policing window.

11. The system of claim 10, wherein said rate policing logic is further operable to perform, in the event said event time stamp does not indicate a time subsequent to said rate policing window end time, rate policing on said data unit, said rate policing including determining whether said data unit is to be considered part of said guaranteed bandwidth of said virtual connection.

12. The system of claim 11, wherein said rate policing logic is further operable to write, in the event that said data unit is not to be considered part of said guaranteed bandwidth of said virtual connection, a discard enabled indicator associated with said data unit.

13. The system of claim 12, wherein said discard enabled indicator is a discard enabled bit within said data unit.

14. The system of claim 12, wherein said discard enabled indicator is a flag in a descriptor data structure associated with at least one memory buffer storing said data unit.

15. The system of claim 10, wherein said rate policing logic is further operable to set said rate policing window start time associated with said virtual connection equal to said event time stamp when starting said new rate policing window.

16. The system of claim 10, wherein said rate policing logic is further operable to set a byte count field associated with said virtual connection to a predetermined value when starting said new rate policing window.

17. The system of claim 16, wherein said predetermined value represents the maximum amount of data which may be received using said guaranteed bandwidth over said connection during said rate policing window duration.

18. The system of claim 16, wherein said predetermined value is zero.

19. A system for determining an event-based rate policing window, comprising:

means for receiving a data unit;

means for generating an event time stamp reflecting a time at which said data was received;

means for associating said event time stamp with said data unit;

means for generating a rate policing window end time by adding a rate policing window start time to a rate policing window duration;

means for comparing said event time stamp with rate policing window end time;

means for starting, in the event that said event time stamp indicates a time subsequent to said rate policing window end time, a new rate policing window;

wherein said data unit is received on a virtual connection, and wherein said rate policing window start time, said rate policing window end time, said rate policing window duration, and said new rate policing window are associated with said virtual connection; and

wherein said rate policing window start time defines a time at which a current rate policing window started, wherein said rate policing window duration defines a length of said current rate policing window, wherein said rate policing window end time defines an end of said current rate policing window, and wherein said current rate policing window defines a time interval during which a predetermined amount of bandwidth is reserved as guaranteed bandwidth for use by data units received on said virtual connection during said current rate policing window.