As communications networks grow in both speed and scale, there is a need to switch packets at higher speeds. One approach is to use fast switches that operate at the datalink layer (layer 2) to build a high-performance "cloud" for interconnecting network layer routers. The use of ATM for the layer 2 network provides a number of advantages when the network is shared among multiple services and when additional capabilities that are supported well at layer 2, such as fine-grained per-flow QoS, are needed. This paper describes a robust and efficient solution to the problem of supporting IP over a large non-broadcast multiple-access (NBMA) network, such as ATM. The solution, known as SUBMARINE, calculates loop-free shortcut routes across the NBMA network. SUBMARINE builds on existing IP routing protocols, is designed to scale to multiple areas within a single autonomous system, and makes minimal changes to the IP forwarding process.

The performance of timer algorithms is crucial to many network protocol implementations that use timers for failure recovery and rate control. Conventional algorithms to implement an operating system timer module take O(n) time to start or maintain a timer, where n is the number of outstanding timers: this is expensive for large n. This paper shows that by using a circular buffer or timing wheel, it takes O(1) time to start, stop, and maintain timers within the range of the wheel. Two extensions for larger values of the interval are described. In the first, the timer interval is hashed into a slot on the timing wheel. In the second, a hierarchy of timing wheels with different granularities is used to span a greater range of intervals. The performance of these two schemes and various implementation tradeoffs are discussed. We have used one of our schemes to replace the current BSD UNIX callout and timer facilities. Our new implementation can support thousands of outstanding timers without much overhead. Our timer schemes have also been implemented in other operating systems and network protocol packages.

One of the challenges for rate based congestion management for computer communication networks is that of scalability. This is true especially in the context of ATM, when reducing the amount of state maintained and the computation performed can have significant advantages in making switches fast as well as low-cost. We explore ways of achieving better scalability of explicit rate algorithms for maxmin fair rate allocation in the presence of a large number of flows/virtual connections. We seek ways to reduce the complexity in both the amount of state that individual switches have to maintain, and the computation performed, by introducing the idea of discrete source rates. We develop algorithms with O(k) complexity of the calculation of fair allocation at the switch, where k is the number of distinct rates. We reduce the amount of state information to one bit per flow without performance degradation. We suggest a further approximation requiring only O(k) state information which performs quite well in our simulations, although it is shown to be vulnerable to certain conditions which may lead to somewhat lower link utilization.

End-to-end rate based congestion management has been extensively studied for control of computer communication networks. We examine some of the properties of end-to-end rate based algorithms for congestion management using explicit rate feedback, to achieve maxmin fair rate allocation in the network. We formulate a requirement on a switch's local rate allocation computation sufficient to ensure convergence of the distributed algorithm to the global maxmin fair rate allocation. We provide an upper bound on the convergence time when the switch algorithm satisfies this requirement. We propose a requirement of feasibility of the transmission rates, maintaining which results in oscillation-free operation of the algorithm while maintaining small queues at the switches. Feasibility implies that the capacity of any of the resources is not exceeded at any time. We suggest a source policy to ensure feasibility of transmission rates, the essence of which is to delay a rate increase by a certain time, while decreasing the transmission rate immediately upon receiving the appropriate feedback. Finally, we seek ways of improving scalability of the computation of maxmin fair rates in the presence of a large number of flows. We suggest using a discrete set of rates, which as we show, reduces the computational complexity and the state requirement at the switches.

Conventional algorithms to implement an Operating System timer module take Ο(n) time to start or maintain a timer, where n is the number of outstanding timers: this is expensive for large n. This paper begins by exploring the relationship between timer algorithms, time flow mechanisms used in discrete event simulations, and sorting techniques. Next a timer algorithm for small timer intervals is presented that is similar to the timing wheel technique used in logic simulators. By using a circular buffer or timing wheel, it takes Ο(1) time to start, stop, and maintain timers within the range of the wheel.