Tolerant CIR monitoring and policing

• US 6,370,116 B1
• Filed: 05/26/1998
• Issued: 04/09/2002
• Est. Priority Date: 05/26/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Inventors: Liu, Bo, Rezaki, Ali, Paquette, Andre, Giroux, Natalie
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Duong, Frank
• Application Number:
  US09/084,119
• Time in Patent Office: 1,414 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/235, 370/252, 370/389, 370/391, 370/394, 370/465, 370/437, 370/253
• US Class Current: 370/232
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5637 Leaky Buckets
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/21 using leaky-bucket
• 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 modification to the “leaky bucket” algorithm provides fair treatment of Frame Relay packets of varying length. The previously known leaky bucket scheme requires that there be sufficient credits in either the committed burst (Bc) bucket or excess burst (Be) bucket to accommodate the entire frame at an access point for the frame to be accepted. The “elastic leaky bucket” algorithm of the present invention permits acceptance of frames if there are any credits at all in the relevant buckets. This provides for fair treatment of long frames.

Claims

1. A method of enforcing rate parameters respecting variable length data packets at an access point in a packet switching network wherein a committed information rate (CIR) is assigned to data packets having a committed delivery status and an excess information rate (EIR) is assigned to data packets having a rate in excess of CIR, the network having configured rate limits for CIR and EIR, the method comprising:

examining each data packet at said access point, and determining whether said data packet has been assigned a CIR or EIR delivery status; and

accepting each data packet having a CIR delivery status if there is room within said CIR rate limit for at least a portion of said data packet, otherwise marking said packet discard eligible and determining whether there is room within said EIR rate limit for at least a portion of said data packet and if room exists accept said packet, otherwise discard.

2. A method as defined in claim 1 wherein if said packet is assigned EIR status and if there is capacity within said EIR limit for at least a portion of said packet accept said packet, otherwise discard.

3. A method as defined in claim 2 wherein said packet is a frame relay packet.

4. A method as defined in claim 3 wherein, if there is no room for at least a portion of said packet within either CIR or EIR rate limits check said data packet for discard eligible status and if said packet is not marked discard eligible discard said packet.

5. A method as defined in claim 4 wherein if said packet is marked discard eligible check for available space within CIR rate limit and if space exists for at least a portion of said packet accept said packet, otherwise discard.

6. A method as defined in claim 1 comprising an elastic, dual leaky bucket algorithm.

7. A system for enforcing rate information parameters in a packet switching network for routing variable length packets of information therethrough, said information having either a committed information rate (CIR) delivery class or an excess information rate (EIR) delivery class and wherein said network has defined rate limits for each class of information, said system comprising:

means to dynamically determine the network status for each class of information and determine whether there is space within said defined rate limits to accept at least a portion of an incoming packet;

monitoring means at an access point to said network to determine to which class of information an arriving packet of information has been assigned;

means to accept a packet of committed class of information if space remains for at least a portion of said packet, otherwise mark said packet discard eligible means to accept said packet marked discard eligible if space exists for at least a portion of said packet within said excess rate information class rate limit, otherwise discard said packet marked discard eligible.

8. A system as defined in claim 7 wherein said means to dynamically determine the network status includes means to determine whether said packed is marked discard eligible.

9. In a packet switched communications network wherein variable length data packets are introduced to access means at a switching node, an elastic, dual leaky bucket method for enforcing rate control on said input data packets wherein elastic dual leaky buckets are employed, said leaky buckets comprising an excess burst bucket for data packets having an information rate in excess of an agreed rate, said packets being marked discard eligible (DE), and a committed burst bucket for data packets having an information rate in compliance with an agreed rate, said method comprising:

checking said packets for discard eligible marking;

checking said committed burst bucket for space for at least a portion of one of said packets and if space exists accept said one of said packets without discard eligible marking, if packets are marked DE check excess burst bucket for space for at least a portion of one of said packets and if space exists accept said one of said packets otherwise discard, and if said one of said packets has discard eligible marking, check excess burst bucket for space for at least a portion of one of said packets and if space exists accept said one of said packets marked DE otherwise discard.