Pre-Congestion Notification (PCN) has been proposed at IETF as a framework for scalable measurement-based admission control (MBAC) for a DiffServ-capable network domain. PCN encompasses two functions: admission control of new flows and termination of admitted flows when the available capacity is unexpectedly reduced after a network failure. While there has been extensive research on MBAC, our goal is to understand practical limitations of the specific admission algorithms proposed for PCN and to understand the properties of the termination algorithms of which little is known from prior research.

Current intra-domain Traffic Engineering (TE) relies on offline methods, which use long term average traffic demands. It cannot react to realtime traffic changes caused by BGP reroutes, diurnal traffic variations, attacks, or flash crowds. Further, current TE deals with network failures by pre-computing alternative routings for a limited set of failures. It may fail to prevent congestion when unanticipated or combination failures occur, even though the network has enough capacity to handle the failure.This paper presents TeXCP, an online distributed TE protocol that balances load in realtime, responding to actual traffic demands and failures. TeXCP uses multiple paths to deliver demands from an ingress to an egress router, adaptively moving traffic from over-utilized to under-utilized paths. These adaptations are carefully designed such that, though done independently by each edge router based on local information, they balance load in the whole network without oscillations. We model TeXCP, prove the stability of the model, and show that it is easy to implement. Our extensive simulations show that, for the same traffic demands, a network using TeXCP supports the same utilization and failure resilience as a network that uses traditional offline TE, but with half or third the capacity.

Packet scale rate guarantee (PSRG) is a generic node model which underlies the definition of expedited forwarding (EF) proposed in the context of Internet differentiated services. For the case of first-in-first-out (FIFO) nodes, PSRG is equivalent to the well-understood concept of adaptive service curve. However, in practice, many devices do not necessarily preserve the FIFO property, and therefore, known FIFO results do not hold. This paper analyzes the properties of PSRG in the absence of FIFO assumption. Our analysis is based on a novel characterization of PSRG which avoids the use of virtual finish times and is obtained by min-max algebra. We use it to show that delay bounds previously obtained for the FIFO case are still valid; in contrast, we find that this is not true for the characterization of the concatenation of two nodes.

Packet scale rate guarantee (PSRG) is a generic node model which underlies the definition of expedited forwarding (EF) proposed in the context of Internet differentiated services (DiffServ). For the case of FIFO nodes, PSRG is equivalent to the well-understood concept of adaptive service curve. However, in practice, many devices do not necessarily preserve the FIFO property, and therefore known FIFO results do not hold. This paper analyzes the properties of PSRG in the absence of FIFO assumptions. Our analysis is based on a novel characterization of PSRG which avoids the use of virtual finish times; it is obtained by min-max algebra. We use it to show that delay bounds previously obtained for the FIFO case are still valid; in contrast, we find that this is not true for the characterization of the concatenation of two nodes.

We consider the definition of the expedited forwarding per-hop behavior (EF PHB) as given in RFC 2598 and its impact on worst case end-to-end delay jitter. On the one hand, the definition in RFC 2598 can be used to predict extremely low end-to-end delay jitter, independent of the network scale. On the other hand, the worst case delay jitter can be made arbitrarily large, while each flow traverses at most a specified number of hops, if we allow networks to become arbitrarily large; this is in contradiction with the previous statement. We analyze where the contradiction originates and find the explanation. It resides in the fact that the definition in RFC 2598 is not easily implementable in known schedulers, mainly because it is not formal enough and also because it does not contain an error term. We propose a new definition for the EF PHB, called "packet scale rate guarantee" (PSRG) that preserves the spirit of RFC 2598 while allowing a number of reasonable implementations and has very useful properties for per-node and end-to-end network engineering. We show that this definition implies a rate-latency service curve property. We also show that it is equivalent, in some sense, to the stronger concept of "adaptive service guarantee". Then we propose some proven bounds on delay jitter for networks implementing this new definition in cases without loss and with loss.

We consider the definition of the expedited forwarding per-hop behaviour (EF PHB) as given in RFC 2598 (Jacobsen et al. 1999), and its impact on worst case end-to-end delay jitter. On one hand, the definition in RFC 2598 can be used to predict extremely low end-to-end delay jitter, independent of the network scale. On the other hand, we find that the worst case delay jitter can be made arbitrarily large, while each flow traverses at most a specified number of hops, if we allow networks to become arbitrarily large; this is in contradiction with the previous statement. We analyze where the contradiction originates, and find the explanation. It resides in the fact that the definition in RFC 2598 is not easily implementable in schedulers we know of, mainly because it is not formal enough, and also because it does not contain an error term. We propose a new definition for the EF PHB, called "packet scale rate guarantee", which preserves the spirit of RFC 2598, while allowing a number of reasonable implementations, and has very useful properties for per-node and end-to-end network engineering. We show that this definition implies the rate-latency service curve guarantee. Then we propose some proven bounds on delay jitter for networks implementing this new definition, both in cases without loss and with loss.

This paper describes the architecture for a work-conserving server using a combined I/O-buffered crossbar switch. The switch employs a novel algorithm based on output occupancy, the lowest occupancy output first algorithm (LOOFA), and a speedup of only two. A work-conserving switch provides the same throughput performance as an output-buffered switch. The work-conserving property of the switch is independent of the switch size and input traffic pattern. We also present a suite of algorithms that can be used in combination with LOOFA. These algorithms determine the fairness and delay properties of the switch. We also describe a mechanism to provide delay bounds for real-time traffic using LOOFA. These delay bounds are achievable without requiring output-buffered switch emulation.

Rate based congestion management for computer communication networks has been the focus of considerable research. We examine some of the fundamental properties of such end-to-end rate based algorithms. The first is the requirement for a policy to ensure the feasibility of the transmission rates by the sources. The feasibility implies that the capacity of any of the resources is not exceeded at any time. We show that a source policy which defers increases in the explicit rate for a period of time, while allowing decreases to take effect immediately maintains the requirement of feasibility. We also examine the convergence properties of the end-to-end rate based schemes in general, and give an upper bound on the convergence time of the scheme presented.

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.