Random early demotion and promotion marker

• US 6,748,435 B1
• Filed: 04/28/2000
• Issued: 06/08/2004
• Est. Priority Date: 04/28/2000
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Mukherjee, Sarit, Bushmitch, Dennis, Wang, Fugui
• Primary Examiner(s): Wiley, David
• Assistant Examiner(s): AVELLINO, JOSEPH E
• Application Number:
  US09/560,323
• Time in Patent Office: 1,502 Days
• Field of Search: 709/240, 709/223-226, 709/229, 709/230, 370/229-240
• US Class Current: 709/225
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]

Abstract

Data packets are received by the REDP traffic conditioning marker from the upstream domain and each have a red, yellow, or green priority level. The traffic conditioning marker monitors the rate of green data packets flowing through the A random early demotion and promotion (REDP) traffic conditioning marker is located between an upstream domain and a downstream domain. If the rate exceeds a negotiated rate, the traffic conditioner randomly and fairly demotes green packets to yellow. If the rate is less than the negotiated rate, the traffic conditioner randomly and fairly promotes yellow packets to green. The traffic conditioner removes the phase effects that occur in conventional markers.

Claims

1. A traffic conditioner for a network system that routes a plurality of data packets, each having one of a first, a second and a third priority level, from an upstream domain to a downstream domain, comprising:

a rate generator that generates tokens at a token rate;

a token receiver connected to said token generator that contains n tokens where n is between 0 and N;

a token level indicator connected to said token receiver and having a plurality of states based upon the number of tokens n in said token receiver, wherein at least one of said states is a promotion state; and

a data packet remarker, connected to said token level indicator, that promotes at least one of said data packets having said second priority level to said first priority level when said token level indicator is in said promotion state,

wherein said second priority level is used exclusively for said data packets that previously had said first priority level and were demoted.

2. The traffic controller of claim 1 further comprising:

a token assignor, connected to said data packet remarker, that removes said tokens from said token receiver, assigns said tokens to said data packets having said first priority and forwards said data packets to said downstream domain.

3. The packet remarker of claim 2 wherein a number of tokens that said token assignor assigns to said data packets having said first priority is based upon a size of said data packets.

4. The traffic controller of claim 2 wherein said token level indicator is in said promotion state when said number of tokens n in said token receiver is between an upper threshold T_H and N.

5. The traffic controller of claim 4 wherein said token level indicator further includes a balanced state and wherein said token level indicator is in said balanced state when said number of tokens n is between a lower threshold T_L and said upper threshold T_H.

6. The traffic controller of claim 5 wherein said token level indicator includes a demotion state and wherein said token level indicator is in said demotion state when said number of tokens n is between 0 and said lower threshold T_L.

7. The traffic controller of claim 6 wherein said data packet remarker demotes said data packets having said first priority level to said second priority level when said token level indicator is in said demotion state.

8. A distributed network system that delivers a data stream including a plurality of data packets each having one of a first, a second and a third priority level, comprising:

an upstream domain;

a downstream domain; and

a router that connects said upstream domain and said downstream domain and includes a packet remarker that has a promotion state, a demotion state and a balanced state, that promotes at least one of said data packets having said second priority level to said first priority level when said packet remarker is in said promotion state and that demotes at least one of said data packets having said first state to said second state when said packet remarker is in said demotion state;

wherein said second priority level is used exclusively for said data packets that previously had said first priority level and were demoted.

9. The distributed network system of claim 8 wherein said router includes:

a rate generator that generates tokens at a token rate;

a token receiver that contains a number of tokens n from said rate generator, where n is between 0 to N; and

a token level indicator connected to said token receiver which determines whether said packet remarker is in said promotion state, said demotion state or said balanced state based on said number of tokens n in said token receiver.

10. The distributed network system of claim 9 wherein said packet remarker further includes:

a token assignor, connected to said token receiver, that removes said tokens from said token receiver and assigns said tokens to said data packets having said first priority.

11. The distributed network system of claim 10 wherein said packet remarker takes on said demotion state when said number of tokens n lies between 0 and a low threshold T_L.

12. The distributed network system of claim 11 wherein said packet remarker takes on said promotion state when said number of tokens n lies between a high threshold T_H and N.

13. The distributed network system of claim 12 wherein said packet remarker takes on said balanced state when said number of tokens n lies between said low threshold T_L and said high threshold T_H.

14. The distributed network system of claim 12 wherein said packet remarker has a maximum promotion rate Max_promo and promotes said data packets based on a promotion probability:

15. The distributed network system of claim 11 wherein said packet remarker has a maximum demotion rate Max_demo and demotes said data packets based on a demotion probability:

16. A distributed network system that delivers a data stream including a plurality of data packets each having one of a first, a second and a third priority level, comprising:

an upstream domain;

a downstream domain; and

a router that connects said upstream domain and said downstream domain and includes a packet remarker that randomly and fairly promotes said data packets having said second priority level to said first priority level and that randomly and fairly demotes said data packets having said first priority level to said second priority level,

wherein said second priority level is used exclusively for said data packets that previously had said first priority level and were demoted.

17. The distributed network system of claim 16 wherein said packet remarker has a promotion state, a demotion state and a balanced state and includes:

a rate generator that generates tokens at a token rate;

a token receiver that contains a number of said tokens n received from said rate generator, where n is between 0 to N; and

a token level indicator connected to said token receiver which determines whether said packet remarker is in said promotion state, said demotion state or said balanced state based on said number of said tokens n in said token receiver.

18. The distributed network system of claim 17 wherein said packet remarker takes on said demotion state when said number of tokens n lies between 0 and n and a low threshold T_L, takes on said promotion state when said number of tokens n lies between a high threshold T_H and N and takes on said balanced state when said number of tokens n lies between said low threshold T_L and said high threshold T_H.

19. The distributed network system of claim 18 wherein when said packet remarker is in said demotion state, said packet remarker has a maximum demotion rate Max_demo and demotes said data packets based on a demotion probability:

20. The distributed network system of claim 18 wherein said packet remarker has a maximum promotion rate Max_promo and promotes said data packets based on a promotion probability:

21. A distributed network system that delivers a data stream including a plurality of data packets each having one of a first, a second and a third priority level, comprising:

an upstream domain;

a downstream domain; and

a router that connects said upstream domain and said downstream domain and includes a packet remarker that has a promotion state, a demotion state and a balanced state, that promotes at least one of said data packets having said second priority level to said first priority level when said packet remarker is in said promotion state and that demotes at least one of said data packets having said first state to said second state when said packet remarker is in said demotion state,

wherein said second priority level is used for said data packets that previously had said first priority level and were demoted,

wherein said router includes;

(a) a rate generator that generates tokens at a token rate;

(b) a token receiver that contains a number of tokens n from said rate generator, where n is between 0 to N; and

(c) a token level indicator connected to said token receiver which determines whether said packet remarker is in said promotion state, said demotion state or said balanced state based on said number of tokens n in said token receiver;

wherein said packet remarker further includes a token assignor, connected to said token receiver, that removes said tokens from said token receiver and assigns said tokens to said data packets having said first priority;

wherein said packet remarker takes on said demotion state when said number of tokens n lies between 0 and a low threshold T_L, has a maximum demotion rate Max_demo and demotes said data packets based on a demotion probability;

22. A distributed network system that delivers a data stream including a plurality of data packets each having one of a first, a second and a third priority level, comprising:

an upstream domain;

a downstream domain; and

a router that connects said upstream domain and said downstream domain and includes a packet remarker that has a promotion state, a demotion state and a balanced state, that promotes at least one of said data packets having said second priority level to said first priority level when said packet remarker is in said promotion state and that demotes at least one of said data packets having said first state to said second state when said packet remarker is in said demotion state,

wherein said second priority level is used for said data packets that previously had said first priority level and were demoted,

wherein said router includes;

(a) a rate generator that generates tokens at a token rate;

(b) a token receiver that contains a number of tokens n from said rate generator, where n is between 0 to N; and

(c) a token level indicator connected to said token receiver which determines whether said packet remarker is in said promotion state, said demotion state or said balanced state based on said number of tokens n in said token receiver;

wherein said packet remarker further includes a token assignor, connected to said token receiver, that removes said tokens from said token receiver and assigns said tokens to said data packets having said first priority;

wherein said packet remarker takes on said demotion state when said number of tokens n lies between 0 and a low threshold T_L, takes on said promotion state when said number of tokens n lies between a high threshold T_H and N, has a maximum promotion rate Max_promo and promotes said data packets based on a promotion probability;

23. A distributed network system that delivers a data stream including a plurality of data packets each having one of a first, a second and a third priority level, comprising:

an upstream domain;

a downstream domain; and

a router that connects said upstream domain and said downstream domain and includes a packet remarker that randomly and fairly promotes said data packets having said second priority level to said first priority level and that randomly and fairly demotes said data packets having said first priority level to said second priority level,

wherein said second priority level is used for said data packets that previously had said first priority level and were demoted,

wherein said packet remarker has a promotion state, a demotion state and a balanced state and includes;

(a) a rate generator that generates tokens at a token rate;

(b) a token receiver that contains a number of said tokens n received from said rate generator, where n is between 0 to N; and

(c) a token level indicator connected to said token receiver which determines whether said packet remarker is in said promotion state, said demotion state or said balanced state based on said number of said tokens n in said token receiver,

wherein said packet remarker takes on said demotion state when said number of tokens n lies between 0 and n and a low threshold T_L, takes on said promotion state when said number of tokens n lies between a high threshold T_H and N and takes on said balanced state when said number of tokens n lies between said low threshold T_L and said high threshold T_H, and

wherein said packet remarker has a maximum demotion rate Max_demo and demotes said data packets based on a demotion probability;

24. A distributed network system that delivers a data stream including a plurality of data packets each having one of a first, a second and a third priority level, comprising:

an upstream domain;

a downstream domain; and

a router that connects said upstream domain and said downstream domain and includes a packet remarker that randomly and fairly promotes said data packets having said second priority level to said first priority level and that randomly and fairly demotes said data packets having said first priority level to said second priority level,

wherein said second priority level is used for said data packets that previously had said first priority level and were demoted,

wherein said packet remarker has a promotion state, a demotion state and a balanced state and includes;

(a) a rate generator that generates tokens at a token rate;

(b) a token receiver that contains a number of said tokens n received from said rate generator, where n is between 0 to N; and

(c) a token level indicator connected to said token receiver which determines whether said packet remarker is in said promotion state, said demotion state or said balanced state based on said number of said tokens n in said token receiver,

wherein said packet remarker takes on said demotion state when said number of tokens n lies between 0 and n and a low threshold T_L, takes on said promotion state when said number of tokens n lies between a high threshold T_H and N and takes on said balanced state when said number of tokens n lies between said low threshold T_L and said high threshold T_H, and

wherein said packet remarker has a maximum promotion rate Max_promo and promotes said data packets based on a promotion probability;