# US 2006/0067225 A1 · Hierarchical flow control for router ATM interfaces

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0067225 A1
- Document ID: US20060067225A1
- Status: Published application
- Kind: A1
- Application number: 10/949,916
- Filed: 2004-09-24
- Published: 2006-03-30
- Earliest claimed: 2004-09-24
- Assignees: Cisco Technology, Inc.
- Inventors: Guy Fedorkow; Kenneth Potter; Mark Gustlin; Christopher Kappler; Robert Olsen
- Web page: https://patentgrep.com/patent/US20060067225A1

## CPC

- H04L 12/5601: {Transfer mode dependent, e.g. ATM}
- H04L 47/266: {Stopping or restarting the source, e.g. X-on or X-off}
- H04L 47/43: Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
- H04L 2012/562: {Routing}
- H04L 2012/5679: {Arbitration or scheduling}
- H04L 2012/5681: {Buffer or queue management}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Presently disclosed is an apparatus and method for returning control of bandwidth allocation and packet scheduling to the routing engine in a network communications device containing an ATM interface. Virtual circuit (VC) flow control is augmented by the addition of a second flow control feedback signal from each virtual path (VP). VP flow control is used to suspend scheduling of all VCs on a given VP when traffic has accumulated on enough VCs to keep the VP busy. A new packet segmenter is employed to segment traffic while preserving the first in, first out (FIFO) order in which packet traffic was received. Embodiments of the invention may be implemented using a two-level (per-VC and per-VP) scheduling hierarchy or may use as many levels of flow control feedback-derived scheduling as may be necessitated by multilevel scheduling hierarchies.

## Claims

### Claim 1

A method of flow control in a network communications device, said network communications device receiving packets, comprising:
enqueuing said packets in one or more packet queue structures;
scheduling said packets for dequeuing from said one or more packet queue structures according to a packet hierarchy;
dequeuing said packets;
segmenting each said dequeued packet into one or more ATM cells;
enqueuing said ATM cells into one or more cell queue structures;
scheduling said ATM cells for dequeuing from said one or more cell queue structures according to said packet hierarchy; and
transmitting said ATM cells through an ATM interface;
wherein said dequeuing said packets is controlled by the presence or absence of one or more feedback signals from said cell queue structures and wherein said scheduling said ATM cells for dequeuing from said one or more cell queue structures employs a first in, first-out buffer.

### Claim 2 (depends on 1)

The method of claim 1, wherein said network communications device is a router.

### Claim 3 (depends on 1)

The method of claim 1, wherein said network communications device is a switch.

### Claim 4 (depends on 1)

The method of claim 1, wherein said packet hierarchy is determined at least in part by a virtual circuit characteristic and a virtual path characteristic of each said packet.

### Claim 5 (depends on 4)

The method of claim 4, wherein said packet hierarchy is determined at least in part by an interface characteristic of each said packet.

### Claim 6 (depends on 1)

The method of claim 1, wherein at least one of said feedback signals is generated with an incremental algorithm.

### Claim 7

An apparatus for flow control in a network communications device, said network communications device receiving a plurality of packets, comprising:
a packet queue structure disposed to receive said plurality of packets and comprising a plurality of packet buffers;
a packet scheduler, operably connected to said packet queue structure, configured to dequeue each packet in said plurality of packets from said packet queue structure based on a packet hierarchy;
a packet segmenter disposed to receive said dequeued packets and configured to segment each said dequeued packet into ATM cells;
a cell queue structure operably connected to and receiving said ATM cells from said packet segmenter comprising a plurality of cell buffers, said cell buffers having a fill level characteristic;
a cell scheduler, operably connected to said cell queue structure, configured to dequeue said ATM cells from said cell queue structure based on said packet hierarchy, said cell scheduler comprising a first in, first-out (FIFO) module configured to schedule cells belonging to each said packet for dequeuing, preferentially in the order in which said cells were received; and
a feedback circuit disposed between and operably connected to said cell scheduler and said packet queue structure and configured to provide one or more feedback signals corresponding to said packet hierarchy to said packet queue structure;
wherein:
said feedback circuit is controlled at least in part by said fill level characteristic of said cell buffers; and
said one or more feedback signals are based on said virtual circuit characteristics and said virtual path characteristics of said plurality of packets.

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein said network communications device is a router.

### Claim 9 (depends on 7)

The apparatus of claim 7, wherein said network communications device is a switch.

### Claim 10 (depends on 7)

The apparatus of claim 7, wherein said packet hierarchy is determined at least in part by a virtual circuit characteristic and a virtual path characteristic of each said packet.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein said packet hierarchy is determined at least in part by an interface characteristic of each said packet.

### Claim 12 (depends on 7)

The apparatus of claim 7, wherein said feedback circuit employs an incremental algorithm to generate one or more feedback signals.

### Claim 13

An apparatus for flow control in a network communications device, said network communications device receiving packets, comprising:
means for enqueuing said packets in one or more packet queue structures;
means for scheduling said packets for dequeuing from said one or more packet queue structures according to a packet hierarchy;
means for dequeuing said packets;
means for segmenting each said dequeued packet into one or more ATM cells;
means for enqueuing said ATM cells into one or more cell queue structures;
means for scheduling said ATM cells for dequeuing from said one or more cell queue structures according to said packet hierarchy; and
means for transmitting said ATM cells through an ATM interface;
wherein said means for dequeuing said packets is controlled by the presence or absence of one or more feedback signals from said cell queue structures and wherein said means for scheduling said ATM cells for dequeuing from said one or more cell queue structures employs a first in, first-out buffer.

### Claim 14 (depends on 13)

The apparatus of claim 13, wherein said packet hierarchy is determined at least in part by a virtual circuit characteristic and a virtual path characteristic of each said packet.

### Claim 15 (depends on 13)

The apparatus of claim 13, wherein at least one of said feedback signals is generated with an incremental algorithm.

### Claim 16

A computer system for use in flow control in a network communications device, said network communications device receiving packets, comprising computer instructions for:
enqueuing said packets in one or more packet queue structures;
scheduling said packets for dequeuing from said one or more packet queue structures according to a packet hierarchy;
dequeuing said packets;
segmenting each said dequeued packet into one or more ATM cells;
enqueuing said ATM cells into one or more cell queue structures;
scheduling said ATM cells for dequeuing from said one or more cell queue structures according to said packet hierarchy; and
transmitting said ATM cells through an ATM interface;
wherein said computer instructions for dequeuing said packets is controlled by the presence or absence of one or more feedback signals from said cell queue structures and wherein said scheduling said ATM cells for dequeuing from said one or more cell queue structures employs a first in, first-out buffer.

### Claim 17 (depends on 16)

The computer system of claim 16, wherein said packet hierarchy is determined at least in part by a virtual circuit characteristic and a virtual path characteristic of each said packet.

### Claim 18 (depends on 16)

The computer system of claim 16, wherein at least one of said feedback signals is generated with an incremental algorithm.

### Claim 19

A computer-readable medium storing a computer program executable by a network communications device, the computer program comprising computer instructions for:
enqueuing said packets in one or more packet queue structures;
scheduling said packets for dequeuing from said one or more packet queue structures according to a packet hierarchy;
dequeuing said packets;
segmenting each said dequeued packet into one or more ATM cells;
enqueuing said ATM cells into one or more cell queue structures;
scheduling said ATM cells for dequeuing from said one or more cell queue structures according to said packet hierarchy; and
transmitting said ATM cells through an ATM interface;
wherein said dequeuing said packets is controlled by the presence or absence of one or more feedback signals from said cell queue structures and wherein said scheduling said ATM cells for dequeuing from said one or more cell queue structures employs a first in, first-out buffer.

### Claim 20 (depends on 19)

The computer-readable medium of claim 19, wherein said packet hierarchy is determined at least in part by a virtual circuit characteristic and a virtual path characteristic of each said packet.

### Claim 21 (depends on 19)

The computer-readable medium of claim 19, wherein at least one of said feedback signals is generated with an incremental algorithm.

### Claim 22

A computer data signal embodied in a carrier wave, comprising computer instructions for:
enqueuing said packets in one or more packet queue structures;
scheduling said packets for dequeuing from said one or more packet queue structures according to a packet hierarchy;
dequeuing said packets;
segmenting each said dequeued packet into one or more ATM cells;
enqueuing said ATM cells into one or more cell queue structures;
scheduling said ATM cells for dequeuing from said one or more cell queue structures according to said packet hierarchy; and
transmitting said ATM cells through an ATM interface;
wherein said dequeuing said packets is controlled by the presence or absence of one or more feedback signals from said cell queue structures and wherein said scheduling said ATM cells for dequeuing from said one or more cell queue structures employs a first in, first-out buffer.

### Claim 23 (depends on 22)

The computer data signal of claim 22, wherein said packet hierarchy is determined at least in part by a virtual circuit characteristic and a virtual path characteristic of each said packet.

### Claim 24 (depends on 22)

The computer data signal of claim 22, wherein at least one of said feedback signals is generated with an incremental algorithm.
