US6091709A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Quality of service management for packet switched networks
Assignee: International Business Machines Corp
•
Filing: 1997-11-25
•
Granted: 2000-07-18
•
Expires: 2017-11-25
Abstract
Abstract A packet router for a data packet transmission network, wherein routers offer priority services of the type required for isochronous handling of data representing real-time voice, includes a Quality of Service (QoS) management system for ensuring that guarantees associated with such priority service can be met with a high degree of certainty. This management system provides prioritized queues including a highest priority queue supporting reservations for the priority service suited to isochronous handling. The highest priority queue and other queues are closely monitored by a QoS manager element for states of near congestion and critical congestion. While neither state exists, filler packet flows are promoted from lower priority queues to the highest priority queue, in order to keep the latter queue optimally utilized. If all lower priority queues are empty at such times, dummy packets are inserted as filler flows. Dummy packets have a form causing routers and other stations receiving them to immediately discard them. The volume of dummy traffic allowed for each queue of the system is a predetermined fraction of the queue's estimated peak traffic load, and that volume is displaceable to allow forwarding of additional traffic through the queue when conditions require it. While a state of near congestion exists, the QoS manager demotes filler flow units from the highest priority queues to lower priority queues, in order to lessen the potential forwarding delays presented to real traffic occupying the highest priority queue. When a state of critical congestion exists in the highest priority queue, admission of new incoming traffic flows to that queue is suspended and forwarding of filler flows from that queue out to the network is also suspended.
Inventors
- 👤 Colin George Harrison
- 👤 Edith Helen Stern
- 👤 Barry Edward Willner
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 12:51
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/70; H04L47/80; H04L47/805; H04L47/72; H04L47/724; H04L47/74; H04L47/745; H04L47/801; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5638; H04L2012/5646; H04L2012/5649; H04L2012/5651; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
334 words
For a data transmission network having packet routers offering guaranteed priority services consistent with isochronous handling of data flows representing real time voice data, a packet router control system for ensuring that guarantees associated with said services can be consistently met with a high degree of certainty even when forwarding queues in the controlled router become congested due to conditions external to that router, said control system comprising: first and second packet forwarding queues having respective first and second forwarding priorities, the first priority greater than the second priority; a prioritizer element for transferring incoming packets that are parts of units of packet flow directly into said first and second queues, packets in each said unit of flow having common origin and destination; said prioritizer element transferring incoming packets that are part of a packet flow having a reservation for said guaranteed priority service into said first queue and other packets directly into said second queue; a monitoring element for monitoring said first queue to detect first and second states of respective imminent and critical congestion in said first queue; and a flow regulating element interacting with said monitoring and prioritizer elements for regulating the flow of packets into and out of said first queue when necessary to compensate for conditions in said network causing said first and second states; said flow regulating element acting, while said first queue is in neither of said first and second states, to promotionally transfer units of filler packet flow from said second queue to said first queue; said regulating element acting, while said first queue is in said first state, to demotionally transfer said promotionally transferred units of filler packet flow from said first queue to said second queue; and said regulating element acting, while said first queue is in said second state, to block admission of new packet flows to said first queue and also to block forwarding transfers, from said first queue to said network, of any filler packet flows currently occupying said first queue.
Claim 2
Dependent Claim
334 words
For a data transmission network having packet routers offering guaranteed priority services consistent with isochronous handling of data flows representing real time voice data, a packet router control system for ensuring that guarantees associated with said services can be consistently met with a high degree of certainty even when forwarding queues in the controlled router become congested due to conditions external to that router, said control system comprising: first and second packet forwarding queues having respective first and second forwarding priorities, the first priority greater than the second priority; a prioritizer element for transferring incoming packets that are parts of units of packet flow directly into said first and second queues, packets in each said unit of flow having common origin and destination; said prioritizer element transferring incoming packets that are part of a packet flow having a reservation for said guaranteed priority service into said first queue and other packets directly into said second queue; a monitoring element for monitoring said first queue to detect first and second states of respective imminent and critical congestion in said first queue; and a flow regulating element interacting with said monitoring and prioritizer elements for regulating the flow of packets into and out of said first queue when necessary to compensate for conditions in said network causing said first and second states; said flow regulating element acting, while said first queue is in neither of said first and second states, to promotionally transfer units of filler packet flow from said second queue to said first queue; said regulating element acting, while said first queue is in said first state, to demotionally transfer said promotionally transferred units of filler packet flow from said first queue to said second queue; and said regulating element acting, while said first queue is in said second state, to block admission of new packet flows to said first queue and also to block forwarding transfers, from said first queue to said network, of any filler packet flows currently occupying said first queue.
Claim 3
Dependent Claim
99 words
The system of claim 1 wherein said flow regulating element further includes means to insert dummy packets of predetermined form into said first queue while said first queue is in neither of said first and second states and said second queue is empty; said dummy packets having a form causing them to be immediately discarded at network stations to which they are sent; the rate of insertion of said dummy packets being restricted to keep the peak dummy packet traffic through said first queue at a predetermined fraction of the expected peak rate of real traffic through that queue.
Claim 4
Dependent Claim
81 words
The system of claim 1 wherein said network is a public network such as the Internet, said packets are in the TCP/IP format used in the Internet, said format having a control header including a Time to Live field, and said dummy packets exclusively having their Time to Live fields set to 0, that setting causing the dummy packets to be discarded at routers and network stations to which they are sent when they are forwarded out of said controlled router.
Claim 5
Dependent Claim
67 words
The system of claim 1 wherein said monitoring element includes means for periodically sampling time stamps applied to data entering said first queue, means using the sampled times to calculate a latest average packet forwarding delay for said first queue, and means for comparing said latest average forwarding delay to predetermined first and second thresholds associated respectively with transitions to said first and second states of congestion.
Claim 6
Dependent Claim
45 words
The system of claim 4 wherein said first and second thresholds used by said comparing means are derived from predetermined first and second positions in the bend of a hockey-stick curve defrning the relationship in said first queue between traffic loads and average forwarding delays.
Claim 7
Dependent Claim
229 words
For a data transmission network having packet routers offering guaranteed priority service in respect to data needing isochronous handling, a method of regulating traffic flow within said routers so as to ensure that guarantees associated with said service can be consistently met with a high degree of certainty even when forwarding queues in the router become congested due to conditions external to the router, said method comprising: transferring incoming packets that are parts of units of packet flow directly into first and second queues having different priorities, said first queue having a higher priority than said second queue; said first queue being used to support forwarding of traffic subscribed to said priority service requiring isochronous handling; monitoring said first queue to detect first, second and third states of occupancy in said first queue; said first state being present when said the average forwarding delay in said first queue is below a first threshold associated with imminent congestion, said second state being present when said average forwarding delay is greater than said first threshold but less than a second threshold associated with onset of critical congestion, and said third state being present when said average forwarding delay is above said second threshold; and regulating flow of packet traffic into and out of said first queue to keep said queue operating efficiently while counteracting said states of imminent and critical congestion.
Claim 8
Dependent Claim
229 words
For a data transmission network having packet routers offering guaranteed priority service in respect to data needing isochronous handling, a method of regulating traffic flow within said routers so as to ensure that guarantees associated with said service can be consistently met with a high degree of certainty even when forwarding queues in the router become congested due to conditions external to the router, said method comprising: transferring incoming packets that are parts of units of packet flow directly into first and second queues having different priorities, said first queue having a higher priority than said second queue; said first queue being used to support forwarding of traffic subscribed to said priority service requiring isochronous handling; monitoring said first queue to detect first, second and third states of occupancy in said first queue; said first state being present when said the average forwarding delay in said first queue is below a first threshold associated with imminent congestion, said second state being present when said average forwarding delay is greater than said first threshold but less than a second threshold associated with onset of critical congestion, and said third state being present when said average forwarding delay is above said second threshold; and regulating flow of packet traffic into and out of said first queue to keep said queue operating efficiently while counteracting said states of imminent and critical congestion.
Claim 9
Dependent Claim
100 words
The method of claim 6 wherein said flow regulating steps include: promotionally transferring filler packet flows from said second queue to said first queue while said first queue is in said first state of neither imminent nor critical congestion; demotionally transferring filler flows from said first queue to said second queue while said first queue is in said second state of imminent congestion; and blocking admission of new packet flows to said first queue, as well as forwarding transfers of filler packet flows out of said first queue, while said first queue is in said third state of critical congestion.
Claim 10
Dependent Claim
86 words
The method of claim 7 wherein said flow regulating step further includes: inserting dummy filler packets of predetermined form into said first queue while said first queue is in said first state and said second queue is empty; said dummy packets having a form causing them to be immediately discarded at stations of said network receiving them; said dummy packets being entered into said first queue at a restricted rate suitable for not unduly interfering with admission of new real packet flows into said first queue.
Claim 11
Dependent Claim
70 words
The method of claim 8 wherein said network is a public network such as the Internet, said packets are in the TCP/IP format used in the Internet, said format having a control header including a Time to Live field, and said dummy packets exclusively having their said Time to Live fields set to 0, that value causing the dummy packets to be discarded at routers to which they are sent.
Claim 12
Dependent Claim
65 words
The method of claim 6 wherein said monitoring step includes: periodically sampling time stamps applied to data entering said first queue, calculating a latest average forwarding delay for said first queue from said sampled time stamps, and comparing said latest average forwarding delay to predetermined first and second thresholds associated respectively with transitions to said second and third states of respective imminent and critical congestion.
Claim 13
Dependent Claim
47 words
The method of claim 10 wherein said first and second thresholds used in said comparing step are derived from predetermined first and second positions in the bend of a hockey-stick curve defining the relationship in said first queue between instant packet traffic loads and average forwarding delays.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-18 | 2004-01-17 | 2004-07-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-18 | 2008-01-17 | 2008-07-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-18 | 2012-01-17 | 2012-07-18 | $7700.00 | Window Closed / Lapsed |