Switch algorithms and architectures for flow control of the available bit rate ATM service

Congestion and the need for congestion control in best-effort packet networks is an inviolate fact. The Available Bit Rate best-effort ATM service includes congestion control mechanisms. More recently, with continued growth of use of the best-effort Internet, adequacy of TCP congestion control has been investigated. Investigations have pointed to the need for inclusion of additional congestion management specific elements in host and router behavior. To support congestion control of best-effort service, the switches in the ATM (routers in IP) networks need to employ a switch algorithm. Ideally an algorithm must ensure a fair rate allocation, short queues, stability, low complexity of implementation and integrate into real switches. Most algorithms reported to date are found lacking in several regards. We have developed the algorithms SLAPLUS and LAPLUS. The critical path of per cell processing of SLAPLUS and LAPLUS comprises of a number of comparisons and additions, respectively, equal to 1 and the order of logarithm to a large base, e.g. 32, of range of rates. At the memory cost of 4 bits per flow they are free from the errors in measurement suffered by most other algorithms. They drain transient queue build-up and are proven to be locally stable with a large region of attraction and to be globally stable. The performance of the algorithms has been verified through extensive simulation. Supporting the ABR service in Input-Queued Switches presents additional considerations. We have developed solutions and designed the LAPLUS ABR controller for a 320 Gbps Input-Queued Bufferless Crossbar Switch.