【正文】 ) technology is deployed in the future Inter backbone. DWDM expands the capacity of munication trunks by allowing a greater number of channels to be carried on a single optical fiber. With potentially tens or even hundreds of DWDM channels between major points, load balancing is essential in best utilizing the multiple parallel channels. Parallel architectures have been used for packet processing for coping with exponential growth in Inter traffic, Instead of one processing engine, packets are dispatched to multiple parallel engines inside a router to increase the overall processing throughput. The same technique is also used in scaling web servers. Popular web servers often operate a farm of machines and the routers connected to them split the HTTP requests to different machines. For all of these examples, effective use of load balancing requires good schemes for splitting traffic over multiple links. In addition, since the majority of the traffic on the Inter is TCPbased [1], traffic splitting schemes need to avoid packet misordering within a TCP ?ow, which can falsely trigger congestion control mechanisms and cause unnecessary throughput degradation [2], [3]. In this paper, we propose and evaluate a class of hashing based traffic splitting algorithms which preserve per?ow packet ordering. We consider five hash functions that are “direct,”meaning that the hash function produces a value in the range of 0...N1, where N is the number of outgoing links. We also consider a tablebased generalization that involves hashing to M bins, then assigning the M bins to the N outgoing links. Table based hashing requires more state than direct hashing, but has the flexibility to support unequal load distribution and dynamic adaptation. Our results are obtained by simulating the performance of a traf?c splitter, using packet traces taken from two trunks of a major Inter backbone provider. We ?nd that direct hashing with the destination IP address causes signi?cant imbalance across two links. Using the Inter checksum or the exclusive OR of both the source IP address and destination IP address improves the performance considerably, though moderate imbalance persists. The more putationally plex 16bit CRC of the ?vetuple (source address, destination address, source port,destination port and . . protocol id) gives excellent load balancing performance, keeping the load and queue lengths very similar on two links. Equally good load balancing can be achieved using tablebased hashing with adaptation, which requires less putation than the CRC but necessitates monitoring the link loads and storing (and adjusting) the mapping from table bins to links. Tablebased hashing has the additional advantage that it can distribute the load according to unequal weights. Further, an indexbased version of this scheme can alter the weight distribution with minimal disruption to existing ?ows . Our results con?rm that the indexbased hashing can accurately achieve a weighted distribution when adaptation is also used. The rest of this paper is anized as follows. In Section II we discuss related work in traf?c splitting and load balancing. Section III describes the behavior of an ideal traf?c splitter, explains the requirements for a practical system, and de?nes the performance metrics that will be used to assess various hashingbased schemes. The set of schemes that we consider are described in Section IV. The results of our study are described in Section V, and include analysis of the randomness inherent in the trace data (Section VA). We conclude and mention areas for future work in Section VI. II. RELATED WORK Load balancing has been used in telemunication works in the form of inverse multiplexing [4]. Inverse multiplexing allows service providers to offer wideband channels by bining multiple narrowband 56 kbps and 64 kbps trunks [5]. The load balancing in inverse multiplexing is typically based on round robin distribution of packets or bytes [6], [7]. Our work differs from inverse multiplexing in two important dimensions. First, inverse multiplexing is designed for use over pointtopoint links。 its techniques are not typically applicable for work layer load balancing. Inter load balancing, however, makes use of the natural redundancy in the work topology. The paths for load balancing, for example, equalcost multipaths, are discovered dynamically by routing protocols, such as OSPF [8], rather than through configuration. Second, in order to maintain synchronization and perflow FIFO packet ordering in inverse . . multiplexing, it is necessary to add extra packet headers with sequence numbers or to keep state at both ends of the channel. But, implementing these additional mechanisms for work load balancing requires a new work protocol. In parison, the hashingbased schemes can maintain perflow packet ordering and can be implemented without requiring any additional protocol support. Hashing has been widely used in indexing and searching [9].In the working context, hashingbased algorithms for address lookup [10], ?ow identi?cation [11] and packet demultiplexing [12] have been proposed in the past. The use of hashing for work load balancing is not new. Some mercial router products have implemented simple hashing over the IP destination address to distribute traf?c [13]. In the OSPF Optimized Multipath protocol (OSPFOMP) [14], a number of possible approaches for load balancing over multiple paths are mentioned , including perpacket round robin, dividing destination pre?xes among available next hops in the forwarding table, and dividing traf?c according to a hash function applied to the source and destination pair. However, the proposed schemes are not evaluated with simulation or real work measurement. In the study of load balancing with O