Over the last several years there has been considerable interest in multimedia communications over the Internet. This paper investigates one of the key technical issues in supporting per-flow queueing-flow identification. We present several hashing-based flow identification approaches and examine their performance and scalability limits with a quantitative analysis and a simulation study with backbone traffic traces. Of the hashing schemes we studied, 32-bit CRC and XOR-folding of the five-tuple demonstrate excellent performance, both on the memory requirement for a collision rate target, and on the number of collided flows on average and in the worst-case. Our findings show that, with hashing-based schemes, it is feasible to implement flow identification at high speeds to support hundreds of thousands of flows with resource reservation.

Load balancing is a key technique for improving Internet performance. Effective use of load balancing requires good traffic distribution schemes. We study the performance of several hashing schemes for distributing traffic over multiple links while preserving the order of packets within a flow. Although hashing-based load balancing schemes have been proposed in the past, this is the first comprehensive study of their performance using real traffic traces. We evaluate five direct hashing methods and one table-based hashing method. We find that hashing using a 16-bit CRC over the five-tuple gives excellent load balancing performance. Further, load-adaptive table-based hashing using the exclusive OR of the source and destination IP addresses achieves comparable performance to the 16-bit CRC. Table-based hashing can also distribute traffic load according to unequal weights. We also report on four other schemes with poor to moderate performance.

Fair bandwidth sharing at routers has several advantages, including protection of well-behaved flows and possible simplification of end-to-end congestion control mechanisms. Traditional mechanisms to achieve fair sharing (e.g., weighted fair queueing, flow random early discard) require per-flow state to determine which packets to drop under congestion, and therefore are complex to implement at the interior of a high-speed network. In recent work, Stoica et al., (1998), have proposed core-stateless fair queueing (CSFQ), a scheme to approximate fair bandwidth sharing without per-flow state in the interior routers. In this paper, we also achieve approximate fair sharing without per-flow state, however our mechanism differs from CSFQ. Specifically, we divide each flow into a set of layers, based on rate. The packets in a flow are marked at an edge router with a layer label (or "color"). A core router maintains a color threshold and drops layers whose color exceeds the threshold. Using simulations, we show that the performance of our rainbow fair queueing (RFQ) scheme is comparable to CSFQ when the application data does not contain any preferential structure. RFQ outperforms CSFQ in goodput when the application takes advantage of the coloring to encode preferences.

We consider the use of an application-layer performance measure-the utility-in the context of bandwidth allocation for an available bit rate service. This bandwidth allocation scheme can be viewed as a generalization of traditional available bit rate service; the scheme is equivalent to bandwidth max-min allocation when the utility of all applications are equal. The goal of the allocation scheme is to provide a good application-layer service to a wide diversity of applications sharing available bandwidth. We achieve this goal while also supporting changes in utility over time, tolerating some inaccuracy in utility function specification, and addressing the issue of circumvention through pricing.

An available bit rate (ABR) service allows applications to access a time-varying network capacity. In a basic ABR service the available network capacity is divided "fairly" amongst active connections, without regard to the utility that each application derives from the bandwidth allocation. The goal of this paper is to improve both the global and individual utility obtained by applications using ABR, as compared to standard max-min bandwidth allocation. The key to our novel ABR algorithm is to relax the requirement for short-term fair bandwidth allocation, allowing an allocation that trades bandwidth between applications to increase the overall utility. To increase the utility of each individual application, we also re-allocate the bandwidth on the usual ABR time interval. This re-allocation increases the long-term average utility obtained by each individual application; it also ensures that the longer term average bandwidth allocated to each application is equal to the max-min allocation.