Bandwidth management and congestion control scheme for multicast ATM networks
First Claim
1. 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.
2 Assignments
0 Petitions
Accused Products
Abstract
A bandwidth management and congestion control scheme for a multi-cast ATM network which includes a buffer reservation mechanism comprised of a state machine for association with each virtual circuit set up through the network, the state machine being adapted to monitor the number of available buffer slots at a data link and reading an encoding scheme for cells comprising a burst of data in order to control its switching from an active to an idle state to thereby control the flow of data through the virtual circuit. A state dependent token pool mechanism is associated with each virtual circuit and generates tokens at varying rates which are "used" by transmitted data in order to monitor and control the average data rate passing through a data link over a virtual circuit. By thus monitoring and controlling the peak data rate and average data rate, the bandwidth for each data link is efficiently managed to maximize data throughput and minimize loss of data cells from data bursts. A novel means for determining the availability of capacity on a data link for establishing a virtual circuit is also disclosed which depends on a probability calculation expressed in terms of the average data rate and peak data rate through a network link. This information is available through the buffer reservation mechanism and the token pool mechanism to facilitate the fast calculation required to establish a virtual circuit "on the fly". Various implementation details are also provided.
311 Citations
24 Claims
- 1. 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.
- 13. 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.
- 16. 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.
- 20. 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.
Specification