US5629928A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic fair queuing to support best effort traffic in an ATM network
Assignee: Cisco Technology Inc
•
Filing: 1995-12-12
•
Granted: 1997-05-13
•
Expires: 2015-12-12
Abstract
Abstract A flow control apparatus implemented in a virtual path ATM communication system comprising a plurality of nodes interconnected by physical links which comprise virtual paths including a plurality of virtual channels. A connection between two nodes is defined as the combination of a physical link, a virtual path, and a virtual channel. Connections are shared between a reserved bandwidth service and a best effort service. ATM data cells conveyed on said best effort service are routed from node to node by analyzing their virtual connection identifier. Queues, allocated as needed from a pool of free queues, are used to store all incoming ATM data cells having the same virtual channel identifier.
Inventors
- 👤 Jean Calvignac
- 👤 Daniel Orsatti
- 👤 Fabrice Verplanken
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 21:42
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L47/00; H04L47/10; H04L49/00; H04L49/30; H04L49/3081; H04L2012/5619; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5635; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
237 words
In a data communication network having a plurality of nodes interconnected by links, each of said links being identified by a link identifier and supporting a plurality of virtual paths, each of the virtual paths being identified by a virtual path identifier VPi and further supporting a plurality of virtual channels, each of said channels being identified by a virtual channel identifier VCi, the combination of said link, virtual path and virtual channel identifiers defining a virtual connection over which data cells can be conveyed between nodes, each of said data cells including a virtual path identifier CVPi and a virtual channel identifier CVCi, a flow control apparatus located at a node in the network and comprising: a pool of free queues for storing incoming data cells; identifying means for reading the CVPi and CVCi identifiers for each incoming data cell; means for performing a look up operation based on the CVPi and CVCi identifiers to determine whether a queue already exists for the virtual connection identified by said CVPi and CVCi identifiers; means responsive to a determination that no queue exists for said virtual connection for allocating a queue from said pool of free queues and for storing cells received on said virtual connection in said allocated queue; and means responsive to a determination that a queue already exists for said virtual connection to store cells received on said virtual connection in the already existing queue.
Claim 2
Dependent Claim
237 words
In a data communication network having a plurality of nodes interconnected by links, each of said links being identified by a link identifier and supporting a plurality of virtual paths, each of the virtual paths being identified by a virtual path identifier VPi and further supporting a plurality of virtual channels, each of said channels being identified by a virtual channel identifier VCi, the combination of said link, virtual path and virtual channel identifiers defining a virtual connection over which data cells can be conveyed between nodes, each of said data cells including a virtual path identifier CVPi and a virtual channel identifier CVCi, a flow control apparatus located at a node in the network and comprising: a pool of free queues for storing incoming data cells; identifying means for reading the CVPi and CVCi identifiers for each incoming data cell; means for performing a look up operation based on the CVPi and CVCi identifiers to determine whether a queue already exists for the virtual connection identified by said CVPi and CVCi identifiers; means responsive to a determination that no queue exists for said virtual connection for allocating a queue from said pool of free queues and for storing cells received on said virtual connection in said allocated queue; and means responsive to a determination that a queue already exists for said virtual connection to store cells received on said virtual connection in the already existing queue.
Claim 3
Dependent Claim
40 words
Flow control apparatus according to claim 1 further including: a round robin scheduler for servicing all allocated queues; inserting means for inserting a queue in said round robin scheduler, and deallocating means for removing queues from said round robin scheduler.
Claim 4
Dependent Claim
45 words
Flow control apparatus according to claim 2 further including: dequeuing means for transmitting a cell from a scheduled queue upon service by said round robin scheduler, and means for releasing an allocated queue to said pool of free queues if said allocated queue becomes empty.
Claim 5
Dependent Claim
34 words
Flow control apparatus according to claim 3 further including means for stopping further transfer of data cells conveyed by a particular virtual connection in response to a first stop request from a downstream node.
Claim 6
Dependent Claim
85 words
Flow control apparatus according to claim 4 further including: means responsive to a stop request and to a determination that a queue associated with the virtual connection does exist to remove that queue from the round robin scheduler, preventing further servicing of the queue; and means responsive to a stop request and to a determination that no queue is associated with the virtual connection to allocate a queue from the pool of free queues while keeping the allocated queue isolated from the round robin scheduler.
Claim 7
Dependent Claim
55 words
Flow control apparatus according to any of claims 1 through 5 further including: means for maintaining a count QC of the current number of queues allocated in said node, and means for comparing the current count QC to a high threshold and to a low threshold, said high threshold being greater than said low threshold;
Claim 8
Dependent Claim
43 words
Flow control apparatus according to claim 6 further including means responsive to a determination that the current count QC has exceeded the high threshold to generate and send a stop signal to an upstream node provided such signal has not previously been sent.
Claim 9
Dependent Claim
39 words
Flow control apparatus according to claim 7 further including means responsive to a determination that the current count QC has fallen below the low threshold generate and send a restart signal provided such a signal was not previously generated.
References Cited (Backward Citations)
EP0272939A2
Cited
EP0430570A2
Cited
US5231633A
Cited
US5150358A
Cited
US5268900A
Cited
US5436891A
Cited
US5499238A
Cited
US5515363A
Cited
US5533020A
Cited
US5533009A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-12 | 2000-11-11 | 2001-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-12 | 2004-11-11 | 2005-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-12 | 2008-11-11 | 2009-05-13 | $7700.00 | Window Closed / Lapsed |