【文章內容簡介】 to the same outgoing link, and thus increase the loss of bandwidth. In a packetized system, consider the worst case that all out going links have been idle since time T when a packet of maximum size Pmax arrives and no more packets are ing until the packet is served. Assume the packet is forwarded onto link i. During the service period, Equation 1 no longer holds because , where C is a fraction of the packet that has been serviced during the period. Therefore, in a packetized system, the ideal load balancing should satisfy the following: over any interval [T,t] , where Pmax is the maximum size of packet. That is, the difference between the time link i is busy and the time link j is busy should be no more than the time to send a largest packet over the slower link. B. Requirements There are a number of basic requirements that traf?c splitting schemes should meet for Inter load balancing: Low Overhead . Traf?c splitting is executed for every packet in the packet forwarding path, thus the perpacket overhead it introduces is a major concern. Traf?c . . splitting algorithms should be very simple and preferably keep no or little state. High Ef?ciency. Poor traf?c distribution will result in uneven link utilization and loss of bandwidth. A traf?c splitter should try to distribute traf?c as close as possible to the reference model. High Ef?ciency. Poor traf?c distribution will result in uneven link utilization and loss of bandwidth. A traf?c splitter should try to distribute traf?c as close as possible to the reference model. PerFlow Ordering. Packet misordering within a TCP ?ow can produce false congestion signals and cause unnecessary throughput degradation [2], [3]. It is therefore an essential requirement that the traffic splitting algorithms maintain perflow packet ordering. This has to be achieved without requiring a new protocol layer. Let us now apply the above requirements to some of the possible traffic splitting approaches. Take packetbypacket round robin or some form of fair queuing for example. The overheads are low and the performance is typically close to optimal. However, per?ow ordering cannot be guaranteed unless additional mechanisms, such as sequence numbers or state keeping, are added. Such additional mechanisms would increase the overhead 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