Marking mechanism for controlling consecutive packet loss in ATM networks

• US 5,790,521 A
• Filed: 03/27/1996
• Issued: 08/04/1998
• Est. Priority Date: 08/01/1994
• Status: Expired due to Fees

• Current Assignee: Iowa University of Research Foundation Incorporated
• Original Assignee: University of Iowa Research Foundation
• Inventors: Andersland, Mark S., Lee, Chaewoo W.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Jung, Min
• Application Number:
  US08/624,897
• Time in Patent Office: 860 Days
• Field of Search: 370/230, 370/231, 370/232, 370/234, 370/235, 370/253, 395/200.13
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 12/64 Hybrid switching systems
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An apparatus and method for optimal packet marking to control consecutive packet loss (also called "average packet gap") in a packet buffer. The apparatus and method can be used in a packet switched system having either a single or multiple packet class, as well as at any entry point of the packet switched system, e.g. source buffers, and switching node buffers. It is shown that variations of the disclosed packet marking method are optimal for either minimizing or maximizing the average packet gap.

Claims

1. A method for controlling the average cell gap of traffic transported in asynchronous transfer mode on a network, comprising the steps of:

receiving a series of cells of said traffic at a first buffer;

marking, prior to transmitting said series of cells, certain ones of said series of cells with a first token type according to a predetermined scheme depending on whether the cells violate negotiated admission rate and burst length constraints; and

outputting said series of cells including said cells having said first token type to the network, whereby cells other than said cells with the first token type should not be dropped and said cells having said first token type may be dropped when said series of cells encounter congestion.

2. The method as claimed in claim 1, wherein said receiving step comprises receiving a series of cells of real-time type traffic and said marking step comprises marking certain ones of said series of cells according to a predetermined scheme so as to minimize the average cell gap should said cells be dropped due to congestion.

3. The method as claimed in claim 2, wherein said marking step comprises marking approximately every other cell of said series of cells, whenever an impending admission rate or burst length violation is detected.

4. The method as claimed in claim 2, wherein said receiving step comprises receiving a series of cells carrying voice data.

5. The method as claimed in claim 4, wherein said marking step comprises marking approximately every other cell of said series of cells, whenever an impending admission rate or burst length violation is detected.

6. The method as claimed in claim 1, wherein said receiving step comprises receiving a series of cells of nonreal-time type traffic and said marking step comprises marking certain ones of said series of cells according to a predetermined scheme when said series violates specific burst or admission rate constraints so as to maximize the average cell gap created should said series of cells encounter congestion and said cells having said first token type be dropped due to congestion.

7. The method as claimed in claim 1, wherein said receiving step comprises receiving a series of cells of data type traffic and said marking step comprises marking certain ones of said series of cells according to a predetermined scheme when said series violates specific burst or admission rate constraints so as to maximize the average cell gap created should said series of cells encounter congestion and said cells having said first token type be dropped due to congestion.

8. The method as claimed in claim 1, wherein said marking step comprises certain ones of said series of cells according to a predetermined scheme when said series violates specific burst or admission rate constraints so as to maximize the average cell gap should said certain ones of said series of cells are dropped when said series of cells encounter congestion.

9. The method as claimed in claim 1, wherein said receiving step comprises receiving a series of cells of data type traffic.

10. The method as claimed in claim 1, wherein said marking step comprises marking certain ones of said series of cells with a first token type from a token generator, wherein said token generator has a finite number of said first token type and is periodically replenished with said first token types.

11. The method as claimed in claim 1, wherein said marking step comprises marking as many cells as possible after a first of said certain cells are marked until no further of said cells can be marked or no impending admission rate or burst length violation is detected.

12. A method for controlling the average cell gap of traffic transported in asynchronous transfer mode on a network, comprising the steps of:

receiving a series of cells of said traffic at a first buffer;

marking, prior to transmitting said series of cells, certain ones of said series of cells with a first token type according to a predetermined scheme which depends on the type of traffic to be transmitted on the network; and

outputting said series of cells including said cells having said first token type to the network, whereby cells other than said cells with the first token type should not be dropped and said cells having said first token type may be dropped when said series of cells encounter congestion.

13. The method as claimed in claim 12, wherein said marking step comprises marking, prior to transmitting said series of cells certain ones of said series of cells with a first token type according to a predetermined scheme depending on whether the cells violate negotiated admission rate or burst length constraints.

14. A system for controlling the average cell gap of traffic transported in asynchronous transfer mode on a network, comprising:

a packet buffer for receiving and storing a series of cells;

a delay and cell marker coupled to said packet buffer for receiving said series of cells and for delaying and marking certain ones of said series of cells in accordance with cell marking control signals and transmission delay control signals;

a decision logic unit coupled to said packet buffer and said delay and cell marker for receiving buffer state signals from said packet buffer and outputting first and second token control signals;

first and second token pool unit coupled to said decision logic unit, wherein said decision logic outputs cell marking control signals and transmission delay control signals which cause said delay and cell marker unit to mark certain ones of said cells with said first and second tokens in a manner such that if certain cells marked with said first tokens encounter congestion, said certain cells can be dropped and results in either maximizing or minimizing average packet gap of said series of cells.