US6147970A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Quality of service management for aggregated flows in a network system
Assignee: Verizon Corporate Services Group Inc
•
Filing: 1997-09-30
•
Granted: 2000-11-14
•
Expires: 2017-09-30
Abstract
Abstract A system and method for optimizing data flow through a node in a network system, where messages forwarded to the node have one of at least two priorities, a normal priority and a high priority. A novel token bucket approach allows maintaining Quality of Service (Qos) while maximizing throughput. Token buckets include normal and high-priority levels, which reserve capacity for high priority bursts of data. Messages for which not enough tokens are present are marked as not protected against loss, and dropped or sent on depending on a mode. Two-stage policing using two levels of token buckets is also presented. Each flow into a node or router has an associated token bucket, with normal and high priority levels. A second aggregate token bucket then re-tests all messages which were considered protected against loss from the first stage. Messages can be marked not protected against loss and sent out appropriately (for example, marked CLP-1 in an ATM VBR-tagged system), or dropped. Also, messages which were marked not protected against loss at the first stage can be marked protected against loss based on a headroom threshold, which allows excess token bucket capacity to be used passing messages which would normally be dropped.
Inventors
- 👤 Gregory D. Troxel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 03:54
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L12/00; H04L12/02; H04L12/16; H04L12/18; H04L12/1881; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L45/00; H04L45/02; H04L45/10; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5629; H04L2012/5631; H04L2012/5636; H04L2012/5638; H04L2012/5646; H04L2012/5647; H04L2012/5651
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
220 words
A system for optimizing data flow through a node in a network system, wherein messages forwarded to said node have one of at least two priorities, a normal priority and a high priority, said system comprising: a first stage, including for each flow into said node: a token counter associated with each flow into said node, each token counter for holding a numeric value representing a number of tokens, said token counter being incremented at a predetermined rate of tokens per second, and said token counter being decremented by a number of tokens as required for passing an arriving message in that flow through said node, said number of tokens required for passing said arriving message being determined by attributes of said arriving message, said token counter further including a maximum limit value; a normal priority threshold value associated with each token counter; wherein if a message with a high priority arrives at said node, said message is marked not protected against loss if said token counter is below said number of tokens required for passing said message; and wherein if a message with a normal priority arrives at said node, said message is marked not protected against loss if said token counter is below said number of tokens required for passing said message plus said normal priority threshold value.
Claim 2
Independent Claim
220 words
A system for optimizing data flow through a node in a network system, wherein messages forwarded to said node have one of at least two priorities, a normal priority and a high priority, said system comprising: a first stage, including for each flow into said node: a token counter associated with each flow into said node, each token counter for holding a numeric value representing a number of tokens, said token counter being incremented at a predetermined rate of tokens per second, and said token counter being decremented by a number of tokens as required for passing an arriving message in that flow through said node, said number of tokens required for passing said arriving message being determined by attributes of said arriving message, said token counter further including a maximum limit value; a normal priority threshold value associated with each token counter; wherein if a message with a high priority arrives at said node, said message is marked not protected against loss if said token counter is below said number of tokens required for passing said message; and wherein if a message with a normal priority arrives at said node, said message is marked not protected against loss if said token counter is below said number of tokens required for passing said message plus said normal priority threshold value.
Claim 3
Dependent Claim
114 words
The system of claim 1, further including: a second stage, receiving messages from one or more first stages including an aggregate token counter, said aggregate token counter for holding a numeric value representing a number of tokens, said aggregate token counter being incremented at a predetermined rate of tokens per second, and said aggregate token counter being decremented by a number of tokens as required for passing said arriving message through said node, said number of tokens required for passing said arriving message being determined by attributes of said arriving message, said aggregate token counter further including a maximum limit value; and an aggregate normal priority threshold value associated with said aggregate token counter.
Claim 4
Dependent Claim
52 words
The system of claim 2 wherein if a message with a high priority was not marked not protected against loss in said first stage, said message is marked not protected against loss in said second stage if said aggregate token counter is below said number of tokens required for passing said message.
Claim 5
Dependent Claim
58 words
The system of claim 3 wherein if a message with a low priority was not marked not protected against loss in said first stage, said message is marked not protected against loss in said second stage if said aggregate token counter is below said number of tokens required for passing said message plus said normal priority threshold value.
Claim 6
Dependent Claim
77 words
The system of claim 2 further including: an aggregate headroom threshold value associated with said aggregate token counter, said aggregate headroom threshold value being greater than said aggregate normal priority threshold value and if a message was marked not protected against loss in said first stage, said message is marked protected against loss if said aggregate token counter is at or above said number of tokens required for passing said message plus said aggregate headroom threshold value.
Claim 7
Dependent Claim
23 words
The system of claim 1 wherein said number of tokens required for passing a message is proportional to the size of the message.
Claim 8
Dependent Claim
18 words
The system of claim 6 wherein one token is required for each byte of data in said message.
Claim 9
Dependent Claim
29 words
The system of claim 1 wherein said number of tokens required for passing a message is related to the cost of sending said message out over a particular network.
Claim 10
Dependent Claim
37 words
The system of claim 1 wherein said network includes an ATM network, and messages marked as not protected against loss are sent out as CLP-1, and messages marked as protected against loss are sent out as CLP-0.
Claim 11
Dependent Claim
40 words
The system of claim 1 wherein messages are outputted over an IP network, wherein: messages marked as not protected against loss are sent out as routine precedence, and messages marked as protected against loss are sent out as elevated precedence.
Claim 12
Independent Claim
202 words
A method for optimizing data flow through a node in a network system, wherein messages arriving on flows to said node have one of at least two priorities, a normal priority and a high priority, said method comprising: for each data flow into said node: providing a token counter associated with each data flow, each token counter for holding a numeric value representing a number of tokens, said token counter further including a maximum limit value; incrementing said token counter at a predetermined rate of tokens per second; decrementing said token counter by a number of tokens as required for passing an arriving message in that data flow through said node, said number of tokens required for passing said arriving message being determined by attributes of said arriving message; providing a normal priority threshold value associated with each token counter; and marking a message with a high priority as not protected against loss if said token counter is below said number of tokens required for passing said message; and marking a message with a normal priority as not protected against loss if said token counter is below said number of tokens required for passing said messages plus said normal priority threshold value.
Claim 13
Independent Claim
202 words
A method for optimizing data flow through a node in a network system, wherein messages arriving on flows to said node have one of at least two priorities, a normal priority and a high priority, said method comprising: for each data flow into said node: providing a token counter associated with each data flow, each token counter for holding a numeric value representing a number of tokens, said token counter further including a maximum limit value; incrementing said token counter at a predetermined rate of tokens per second; decrementing said token counter by a number of tokens as required for passing an arriving message in that data flow through said node, said number of tokens required for passing said arriving message being determined by attributes of said arriving message; providing a normal priority threshold value associated with each token counter; and marking a message with a high priority as not protected against loss if said token counter is below said number of tokens required for passing said message; and marking a message with a normal priority as not protected against loss if said token counter is below said number of tokens required for passing said messages plus said normal priority threshold value.
Claim 14
Dependent Claim
97 words
The method of claim 11 further including: providing an aggregate token counter for holding a numeric value representing a number of tokens, said aggregate token counter further including a maximum limit value; incrementing said aggregate token counter at a predetermined rate of tokens per second; decrementing said aggregate token counter by a number of tokens as required for passing said arriving message through said node, said number of tokens required for passing said arriving message being determined by attributes of said arriving message; and providing an aggregate normal priority threshold value associated with said aggregate token counter.
Claim 15
Dependent Claim
44 words
The method of claim 12 further including: if a message with a high priority was not marked not protected against loss, marking said message not protected against loss if said aggregate token counter is below said number of tokens required for passing said message.
Claim 16
Dependent Claim
50 words
The method of claim 13 further including: if a message with a low priority was not marked not protected against loss, marking said message not protected against loss if said aggregate token counter is below said number of tokens required for passing said message plus said normal priority threshold value.
Claim 17
Dependent Claim
74 words
The method of claim 11 further including: providing an aggregate headroom threshold value associated with said aggregate token counter, said aggregate headroom threshold value being greater than said aggregate normal priority threshold value; and if a message was marked not protected against loss, marking said message as protected against loss if said aggregate token counter is at or above said number of tokens required for passing said message plus said aggregate headroom threshold value.
References Cited (Backward Citations)
US5390176A
Cited
US5555264A
Cited
US5511168A
Cited
US5539747A
Cited
WO1995013838A1
Cited
US5519704A
Cited
US5455826A
Cited
US5530703A
Cited
US5726987A
Cited
US5914936A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-14 | 2004-05-15 | 2004-11-14 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-14 | 2008-05-15 | 2008-11-14 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-14 | 2012-05-15 | 2012-11-14 | $7700.00 | Window Closed / Lapsed |