Method and apparatus for selectively discarding packets

• US 6,219,339 B1
• Filed: 02/20/1998
• Issued: 04/17/2001
• Est. Priority Date: 02/20/1998
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Wang, Yung-Terng, Sriram, Kotikalapudi, Doshi, Bharat Tarachand
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Pham, Brenda H.
• Application Number:
  US09/026,830
• Time in Patent Office: 1,152 Days
• Field of Search: 370/235, 370/230, 370/395, 370/394, 370/355, 370/412, 370/429, 370/473, 370/474, 370/389, 370/393, 370/397, 370/414, 370/418, 370/428, 370/471, 370/479
• US Class Current: 370/235
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

In a packet voice system, discarding of a packet is performed as a function of previously discarded packets. In one embodiment, a packet voice system includes an ATM Adaptation Layer Type 2 (AAL2) and Service Specific Convergence Sublayer (SSCS) System. In this system, a transmission buffer stores AAL2 voice packets for transmission, each AAL2 voice packet comprising a sequence number, the values of which range from 0 to n−1, and a source identifier, k. When traffic congestion is detected, the transmitter portion of the SSCS System selectively discards one packet from a source k at the output of the transmission buffer if no packet from source k was dropped in either the last n−1 packets or over a predefined prior interval of time. Another embodiment of the invention discards packets at the input of the transmission buffer.

Claims

1. A method for discarding packets, the method comprising the steps of:

storing a number of packets for transmission in a buffer;

detecting when the number of stored packets reaches a predefined level; and

responsive to the detecting step,

retrieving a channel identifier from a packet;

checking if prior packets associated with the channel identifier were discarded over a previous time interval;

if at least one of the prior packets was previously discarded, forwarding the packet for transmission; and

discarding the packet otherwise.

2. The method of claim 1 wherein the discarded packet is dropped from the buffer.

3. The method of claim 1 wherein the discarded packet is dropped from an output end of the buffer.

4. The method of claim 1 wherein the discarded packet is dropped before storage in the buffer.

5. The method of claim 1 wherein the checking step checks if any of n−

1 prior packets associated with the channel identifier were discarded.

6. The method of claim 1 wherein the retrieving step also retrieves a sequence number value of the packet, where the sequence number value is less than or equal to n.

7. A method for discarding packets, the method comprising the steps of:

(a) retrieving a channel identifier from a packet stored in a buffer;

(b) retrieving a fill value of the buffer;

(c) if the fill value of the buffer is less than a predefined level, forwarding the packet for transmission;

(d) if the fill value is not less than a predefined level, checking if prior packets associated with the channel identifier were previously discarded;

if at least one of the prior packets was previously discarded, forwarding the packet for transmission; and

discarding the packet otherwise.

8. The method of claim 7 further comprising the step of updating a record of the prior discarded packets subsequent to step (d).

9. The method of claim 8 further comprising the step of advancing packets in the buffer.

10. The method of claim 7 wherein the checking step checks if any of n−

1 prior packets were discarded.

11. The method of claim 10 wherein step (a) also retrieves a sequence number value of the packet, where the sequence number value is less than or equal to n.

12. The method of claim 7 wherein the checking step checks if any prior packets were discarded over a previous time interval.

13. The method of claim 7 wherein the checking step checks if any of n−

1 prior packets were discarded or if any prior packets were discarded over a previous time interval.

14. A method for discarding packets, the method comprising the steps of:

(a) retrieving a channel identifier from a packet;

(b) retrieving a fill value of a buffer;

(c) if the fill value of the buffer is less than a predefined level, storing the packet in the buffer;

(d) if the fill value is not less than a predefined level, checking if prior packets associated with the channel identifier were previously discarded; and

if at least one of the prior packets was previously discarded, storing the packet in the buffer;

discarding the packet otherwise.

15. The method of claim 14 further comprising the step of updating a record of the prior discarded packets subsequent to step (d).

16. The method of claim 14 wherein the checking step checks if any of n−

1 prior packets were discarded.

17. The method of claim 16 wherein step (a) also retrieves a sequence number value of the packet, where the sequence number value is less than or equal to n.

18. The method of claim 14 wherein the checking step checks if any prior packets were discarded over a previous time interval.

19. The method of claim 14 wherein the checking step checks if any of n−

1 prior packets were discarded or if any prior packets were discarded over a previous time interval.

20. A method for discarding packets, the method comprising the steps of:

(a) retrieving a channel identifier from a packet;

(b) retrieving a fill value of a buffer;

(c) if the fill value of the buffer is less than a predefined level, storing the packet in the buffer;

(d) if the fill value is not less than a predefined level, checking if prior packets associated with the channel identifier were previously discarded;

(i) if at least one of the prior packets was previously discarded, checking the buffer for any stored packets that have not had a prior packet discarded;

(ii) if a stored packet is found that has not had a prior packet discarded,

discarding this stored packet;

adding the packet to the buffer; and

(iii) if a stored packet is not found that has not had a prior packet discarded;

discarding the packet.

21. The method of claim 20 further comprising the step of updating a record of the prior discarded packets subsequent to step (d).

22. The method of claim 20 wherein the checking steps (d) and (i) check if any of n−

1 prior packets were discarded.

23. The method of claim 22 wherein steps (a) and (i) also retrieve a sequence number value of the packet, where the sequence number value is less than or equal to n.

24. The method of claim 20 wherein the checking steps (d) and (i) check if any prior packets were discarded over a previous time interval.

25. The method of claim 20 wherein the checking steps (d) and (i) check if any of n−

1 prior packets were discarded or if any prior packets were discarded over a previous time interval.

26. The method of claim 20 wherein the predefined level is set to a capacity of the buffer.

27. Apparatus for discarding packets, the apparatus comprising:

a buffer for storing a number of packets for transmission; and

a processor for detecting when the number of stored packets reaches a predefined level, and, responsive to the detection, (a) retrieving a channel identifier from a packet, (b) checking if prior packets associated with the channel identifier were previously discarded, and (c) if at least one of the prior packets was previously discarded, forwarding the packet for transmission, and discarding the packet otherwise.

28. The apparatus claim 27 wherein the discarded packet is dropped from the buffer.

29. The apparatus of claim 27 wherein the discarded packet is dropped from an output end of the buffer.

30. The apparatus of claim 27 wherein the discarded packet is dropped before storage in the buffer.

31. The apparatus of claim 27 wherein the processor checks if any of n−

1 prior packets associated with the channel identifier were discarded.

32. The apparatus of claim 27 wherein the processor also retrieves a sequence number value of the packet, where the sequence number value is less than or equal to n.

33. The apparatus of claim 27 wherein the processor checks if any prior packets associated with the channel identifier were discarded over a previous time interval.

34. Apparatus for discarding packets, the apparatus comprising:

a first processing element for forming packets, each packet having a channel identifier;

a buffer for storing the formed packets; and

a second processor for (a) detecting when the number of stored packets reaches a predefined level as a precondition to discarding ones of the formed packets, (b) retrieving a channel identifier from ones of the formed packets, (c) checking if prior packets associated with the channel identifier were previously discarded, and (d) if at least one of the prior packets was previously discarded, forwarding the packet for transmission, and discarding the packet otherwise.

35. The apparatus claim 34 wherein the second processor discards ones of the formed packets from the buffer.

36. The apparatus of claim 34 wherein second processor discards ones of the formed packets from an output end of the buffer.

37. The apparatus of claim 34 wherein the second processor discards ones of the formed packets before storage in the buffer.

38. The apparatus of claim 34 wherein the second processor checks if any of n−

1 prior packets associated with the channel identifier were discarded.

39. The apparatus of claim 34 wherein the second processor also retrieves a sequence number value of the packet, where the sequence number value is less than or equal to n.

40. The apparatus of claim 34 wherein the processor checks if any prior packet associated with the channel identifier were discarded over a previous time interval.

41. The apparatus of claim 34 wherein the packet is an ATM Adaptation Layer packet.

42. The apparatus of claim 34 wherein the packet is an ATM Adaptation Layer 2 packet.

43. The apparatus of claim 34 wherein the packet is an Internet Protocol (IP) packet.