US5179556A — Bandwidth management and congestion control schem…

Claim 1

Independent Claim 256 words

An ATM network comprised of a plurality of data links interconnecting a plurality of network switches, each of said data links having a maximum bandwidth, and a plurality of data terminals connected by associated data links to said network switches in said network, said network having means for selectively establishing a virtual circuit therethrough over which data bursts comprised of one of more cells may be routed from at least one data terminal to at least one other data terminal, each of said cells being encoded, each of said data links having a buffer means for receiving and storing cells in buffer slots prior to transmission over its associated data link, and a state machine associated with each virtual circuit, said state machine having means for monitoring the number of unallocated slots in said buffer, means for determining how many unallocated slots are required for transmitting one of said bursts, means for comparing said number of unallocated slots with said required number of unallocated slots, and means for allocating a plurality of unallocated buffer slots to a plurality of cells comprising a burst in response to said comparing means, said state machine having means for decoding each cell and determining at least partially in response to said cell encoding and said buffer slot comparing means whether it should be passed to said associated buffer for guaranteed transmission over its associated data link to thereby maximize the throughput of a matched plurality of encoded cells (burst) by minimizing the undesired truncating of a portion of said bursts.

Claim 2

Dependent Claim 256 words

An ATM network comprised of a plurality of data links interconnecting a plurality of network switches, each of said data links having a maximum bandwidth, and a plurality of data terminals connected by associated data links to said network switches in said network, said network having means for selectively establishing a virtual circuit therethrough over which data bursts comprised of one of more cells may be routed from at least one data terminal to at least one other data terminal, each of said cells being encoded, each of said data links having a buffer means for receiving and storing cells in buffer slots prior to transmission over its associated data link, and a state machine associated with each virtual circuit, said state machine having means for monitoring the number of unallocated slots in said buffer, means for determining how many unallocated slots are required for transmitting one of said bursts, means for comparing said number of unallocated slots with said required number of unallocated slots, and means for allocating a plurality of unallocated buffer slots to a plurality of cells comprising a burst in response to said comparing means, said state machine having means for decoding each cell and determining at least partially in response to said cell encoding and said buffer slot comparing means whether it should be passed to said associated buffer for guaranteed transmission over its associated data link to thereby maximize the throughput of a matched plurality of encoded cells (burst) by minimizing the undesired truncating of a portion of said bursts.

Claim 3

Dependent Claim 76 words

The network of claim 1 wherein said state machine is always in either a transmitting state or a blocking state, said transmitting state being characterized by the passing of cells to its associated buffer and said blocking state being characterized by the discarding of cells, and said state machine has means for changing from one of said states to the other of said states in response to said cell encoding and said buffer slot comparing means.

Claim 4

Dependent Claim 61 words

The network of claim 2 wherein said cell encoding corresponds to the start (s), middle (m), or end (e) or an acceptable sequence of a plurality of cells comprising a burst, or a loner cell which is a low priority single cell, and said state machine has means for changing state solely in response to said (s) or (e) encoded cells.

Claim 5

Dependent Claim 23 words

The network of claim 3 wherein said state machine further comprises means for limiting the time duration of each of said transmitting states.

Claim 6

Dependent Claim 105 words

The network of claim 4 wherein a plurality of data terminals are permitted to transmit over the same virtual circuit and wherein said cell encoding further comprises a begin (b) code which corresponds to an (s) encoded cell except that each of said data terminals is constrained to include only one (b) encoded cell for each burst, and each (b) encoded cell has a matched (e) encoded cell, and wherein said state machine further comprises means for remaining in a transmitting state upon receipt of an (e) encoded cell unless a like number of (b) encoded cells have been received during the same transmitting state.

Claim 7

Dependent Claim 44 words

The network of claim 1 wherein said virtual circuit establishing means comprises means for establishing a new virtual circuit in response to the probability that the demand for buffer slots exceeds the available supply being less than E, wherein E is a pre-selected value.

Claim 8

Dependent Claim 31 words

The network of claim 6 wherein said virtual circuit establishing means has means for calculating said probability as a function of each virtual circuit's peak data rate and average data rate.

Claim 9

Dependent Claim 31 words

The network of claim 1 wherein each data terminal further comprises means for limiting the average data rate of data sought to be transmitted through said network by each data terminal.

Claim 10

Dependent Claim 80 words

The network of claim 8 wherein said average data rate limiting means comprises a state dependent token pool mechanism (SDTPM), said SDTPM having means for generating tokens into a token pool at a pre-selected average data rate when active or idle, means for subtracting tokens from said token pool at a pre-selected peak rate when active, and means for passing or discarding data cells at least partially in response to the presence or absence of tokens in said token pool.

Claim 11

Dependent Claim 23 words

The network of claim 9, wherein said data cell passing or discarding means is at least partially responsive to a pre-determined time delay.

Claim 12

Dependent Claim 34 words

The network of claim 10 wherein said SDTPM has means for changing a data cell encoding to (e) if upon receipt thereof the number of tokens in said token pool is zero or less.

Claim 13

Dependent Claim 68 words

The network of claim 11 wherein said SDTPM is always in either a transmitting state or a blocking state, said transmitting state being characterized by the passing of cells to its associated buffer and said blocking state being characterized by the discarding of cells, and said SDTPM has means for changing from one of said states to the other of said states in response to said cell encoding.

Claim 14

Dependent Claim 91 words

In an ATM network comprised of a plurality of data links interconnecting a plurality of network switches, and a plurality of data terminals connected by associated data links to said network switches in said network, each of said data links having a plurality of buffer slots, the improvement comprising means for selectively establishing a new virtual circuit therethrough in response to the computed probability that the instantaneous demand for the buffer slots associated with the data links comprising the new virtual circuit exceeds the supply is less than a pre-determined value.

Claim 15

Dependent Claim 91 words

In an ATM network comprised of a plurality of data links interconnecting a plurality of network switches, and a plurality of data terminals connected by associated data links to said network switches in said network, each of said data links having a plurality of buffer slots, the improvement comprising means for selectively establishing a new virtual circuit therethrough in response to the computed probability that the instantaneous demand for the buffer slots associated with the data links comprising the new virtual circuit exceeds the supply is less than a pre-determined value.

Claim 16

Dependent Claim 82 words

The device of claim 13 wherein said virtual circuit establishing means comprises means for establishing a new virtual circuit through each network switch, each of said data links and network switches having a buffer with a plurality of slots into which all data must be stored prior to transmission over said data link or switch, and wherein said virtual circuit establishing means includes means for computing the probability distribution of buffer load to be experienced after establishment of said new virtual circuit.

Claim 17

Dependent Claim 41 words

The device of claim 14 wherein said virtual circuit establishing means includes means for computing the probability distribution of buffer load in terms of its peak data rate and average data rate, and without regard to the length of data bursts.

Claim 18

Dependent Claim 166 words

In an ATM network comprised of a plurality of data links interconnecting a plurality of network switches, each of said data links and network switches having an associated buffer through which data must pass prior to entering said associated data link or network switch, and a plurality of data terminals connected by associated data links to said network switches in said network for transmission and reception of data over said network, the improvement comprising means for limiting the average data rate of data sought to be transmitted through each of said buffers by each of said data terminals comprising a state dependent token pool mechanism (SDTPM), said SDTPM having means for generating tokens into a token pool at a preselected average data rate when active or idle, means for substracting tokens from said token pool at a preselected peak rate when active, and means for passing or discarding data cells at least partially in response to the presence or absence of tokens in said token pool.

Claim 19

Dependent Claim 166 words

In an ATM network comprised of a plurality of data links interconnecting a plurality of network switches, each of said data links and network switches having an associated buffer through which data must pass prior to entering said associated data link or network switch, and a plurality of data terminals connected by associated data links to said network switches in said network for transmission and reception of data over said network, the improvement comprising means for limiting the average data rate of data sought to be transmitted through each of said buffers by each of said data terminals comprising a state dependent token pool mechanism (SDTPM), said SDTPM having means for generating tokens into a token pool at a preselected average data rate when active or idle, means for substracting tokens from said token pool at a preselected peak rate when active, and means for passing or discarding data cells at least partially in response to the presence or absence of tokens in said token pool.

Claim 20

Dependent Claim 23 words

The device of claim 16 wherein said data cell passing or discarding means is at least partially responsive to a pre-determined time delay.

Claim 21

Dependent Claim 34 words

The device of claim 17 wherein said SDTPM has means for truncating the transmission of related data cells if upon receipt thereof the number of tokens in said token pool is zero or less.

Claim 22

Dependent Claim 94 words

The device of claim 18 wherein said SDTPM is always in either a transmitting state or a blocking state, said transmitting state being characterized by the passing of cells to its associated buffer and said blocking state being characterized by the discarding of cells, and said SDTPM has means for changing from one of said states to the other of said states in response to an encoding present in said cells, said cell encoding corresponding to the relative position of each of said cells in a data burst comprised of a plurality of cells.

Claim 23

Dependent Claim 153 words

In an ATM network comprised of a plurality of data links interconnecting a plurality of network switches, and a plurality of data terminals connected by associated data links to said network switches in said network for transmitting or receiving data over said network, and means for establishing virtual circuits interconnecting said data terminals over said network through which said data is transmitted and received, the improvement comprising means associated with each data link for monitoring and controlling the peak data rate and average data rate through each virtual circuit to thereby manage the bandwidth over each data link, said data link monitoring and control means comprising a buffer reservation mechanism and a token pool mechanism, said buffer reservation mechanism having means for controlling the peak data rate transmitted through an associated virtual circuit, and said token pool mechanism having means for monitoring and controlling the average data rate through an associated virtual circuit.

Claim 24

Dependent Claim 153 words

In an ATM network comprised of a plurality of data links interconnecting a plurality of network switches, and a plurality of data terminals connected by associated data links to said network switches in said network for transmitting or receiving data over said network, and means for establishing virtual circuits interconnecting said data terminals over said network through which said data is transmitted and received, the improvement comprising means associated with each data link for monitoring and controlling the peak data rate and average data rate through each virtual circuit to thereby manage the bandwidth over each data link, said data link monitoring and control means comprising a buffer reservation mechanism and a token pool mechanism, said buffer reservation mechanism having means for controlling the peak data rate transmitted through an associated virtual circuit, and said token pool mechanism having means for monitoring and controlling the average data rate through an associated virtual circuit.

Claim 25

Dependent Claim 53 words

The device of claim 20 wherein said virtual circuit establishing means comprises means for establishing a new virtual circuit over said network in response to the computed probability that said load resulting from said new virtual circuits would not exceed said network capacity, said computed probability being less than an acceptable level E.

Claim 26

Dependent Claim 32 words

The device of claim 21 wherein said virtual circuit establishing means has means for computing said probability in terms of the peak data rate and average data rate for said virtual circuit.

Claim 27

Dependent Claim 152 words

The device of claim 22 wherein a buffer is assigned for each data link comprising a virtual circuit, said buffer having a plurality of slots for receiving the one or more data cells comprising data bursts for transmission therethrough, and wherein said cells are encoded with regard to their relative position within the burst, and wherein each buffer has one of said buffer reservation mechanisms associated therewith for monitoring the number of unallocated slots in its associated buffer, and determining how many unallocated slots are required for transmitting a data burst, means for comparing said number of unallocated slots with said required number of unallocated slots, and means for allocating a plurality of unallocated buffer slots to a plurality of cells comprising a burst in response to said comparing means, and means for switching between an idle state and an active state in response to said cell encoding and said comparing means.

Claim 28

Dependent Claim 84 words

The device of claim 23 wherein said means for monitoring and controlling the average data rate comprises a state dependent token pool mechanism (SDTPM), said SDTPM having means for generating tokens into a token pool at a pre-selected average data rate when active or idle, means for substracting tokens from said token pool at a pre-selected peak rate when active, and means for passing or discarding data cells at least partially in response to the presence or absence of tokens in said token pool.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1996-01-12	1996-07-13	1997-01-12	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2000-01-12	2000-07-13	2001-01-12	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2004-01-12	2004-07-13	2005-01-12	$7700.00	Window Closed / Lapsed

Bandwidth management and congestion control scheme for multicast ATM networks

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag