Dynamic fair queuing to support best effort traffic in an ATM network

• US 5,629,928 A
• Filed: 12/12/1995
• Issued: 05/13/1997
• Est. Priority Date: 12/13/1994
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Orsatti, Daniel, Verplanken, Fabrice, Calvignac, Jean
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Nguyen, Chau T.
• Application Number:
  US08/570,840
• Time in Patent Office: 518 Days
• Field of Search: 370/13, 370/17, 370/60, 370/61, 370/60.1, 370/94.2, 370/85.6, 370/85.7, 370/84, 370/94.1, 340/825.5, 340/825.51, 395/650, 395/849
• US Class Current: 370/237
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5635 Backpressure, e.g. for ABR
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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;

7. 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.

8. 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.