【正文】 head drastically, and in many cases, only work over pointtopoint links. Hashingbased traf?c splitting algorithms are stateless and fairly easy to pute, particularly with hardware assistance. What is more, if the hash functions use any bination of the ?vetuple as input, perflow ordering can be preserved 1. As we will show later in this paper, many of the hashingbased schemes perform well. Overall, hashingbased schemes meet the above requirements and offer the best tradeoff. This is true because all packets within the same TCP ?ow have the same ?vetuple, thus the output of the hash function with the ?vetuple as input should always be the same. C. Performance Metrics We now discuss the basic performance metrics for evaluating traf?c splitting algorithms for Inter load balancing. . . Load Distribution. From the perspective of load balancing, the most important performance metric is the distribution of bytes over time among the multiple outgoing links. As we have discussed at the beginning of this section, in an ideal system, the traffic load should be distributed in proportion to the rates of the outgoing links. Queue Length. In any practical system, the load distribution curve usually fluctuate over the time. This fluctuation of load is absolved through buffering, thus the queue length of outgoing links reflects the cumulative effects of load balancing. In our analysis, the queue length is used as another performance metric. The queue length metric takes into Account the fact that load distribution discrepancy during A lightly loaded period has far less real effect than a heavily loaded period .A good traffic splitting algorithm may Not necessarily have perfect load distribution at all time instances, but it should be able to keep the queues small and balanced. NonWorkConserving Idle Time. As we have discussed earlier, a packetized load balancing system is nonwork conserving. We de?ne the nonworkconserving idle time as the length of the period when at least one link is idle while others are busy. The idle time metric captures the nonworkconserving inclination of the system: the larger the idle time metric is, the farther away the system skews from workconserving, and hence the less efficient the load balancing is. IV. HASHINGBASED APPROACHES In this section, we describe the hashingbased schemes for load balancing that we will evaluate in the next section. A. Direct Hashing Direct hashing is a simple form of traffic splitting. With direct hashing, the traffic splitter applies a hash function to a set of fieds of the ?vetuple, and uses the hash value to select the outgoing link. It is very simple to implement and requires no extra state to be maintained. In this paper, we consider the following five direct hashing schemes. Hashing of Destination Address The simplest scheme is to hash the IP destination address modulo the number of outgoing links N. It can be expressed as: . . In this scheme, if N=2k , we effectively use the last k bits of the destination address as an index of the outgoing link. This hash function has been implemented by router vendors. Hashing Using XOR Folding of Destination Address XOR folding has been used in many hash functions, and has been shown to provide good performance in other applications [10]. We propose a hash function with XOR folding of the destination IP address. This hash function can be expressed as: Where is Di the ith octet of the destination IP address .This approach utilizes more bits of the destination address in selecting the link. Hashing Using XOR Folding of Source and Destination Addresses A simple modification to the previous hash function is to include the source address in the putation, ., XOR folding with both the destination IP address and the source IP address .This hash function can be expressed as: where Si and are the ith octets of the source and destination IP addresses respectively. Inter Checksum The Inter Checksum algorithm proposed in RFC791 [18] is relatively simple to pute and is also a good hash function. In this paper, we examine its performance for traffic splitting. We feed the ?vetuple as input to the 16bit Inter checksum putation. The index of the outgoing link is calculated from the checksum result modulo by N. This hash function can be expressed as: CRC16 The 16bit CRC (Cyclic Redundant Checksum) algorithm [19] has been . . proposed as a possible candidate for load balancing. Although more plex pared with the other hash functions discussed above, CRC16 has been successfully implemented in highspeed systems. In the CRC16 scheme, the traffic splitter takes the ?vetuple, applies CRC16, and takes modulo by to obtain the outgoing link. The hash function can be expressed as: B. TableBased Hashing Although direct hashing is simple, it also has some limitations. First, direct hashing can only split traffic into equal amounts to multiple outgoing paths. However, it is not always desirable to distribute the traffic load evenly. For example, an anization may have two links to Inter backbones with one link twice the speed of the other. The anization may wish to distribute the traffic with a 2:1 ratio. Secondly, with direct hashing, it is almost impossible to tune the load distribution. The tablebased hashing approach we discuss below addresses both issues by separating traffic splitting and load allocation. A tablebased hashing scheme first splits a traffic stream into M bins. The M bins are then mapped to N outgoing links based on an allocation table (see Figure 2). By changing the allocation of the bins to the outgoing links, one can distribute traffic in a predefined ratio. One can also tune the performance of traffic splitting by adjusting the allocation table. The ratio of M and N determines th