【正文】 SPFOMP, perfect hashing is assumed[15]. A traf?c splitting scheme using random numbers is proposed in [16]. It applies the namebased mappings approach to load balancing [17]. In this scheme, each nexthop is assigned with a weight based on a simple pseudorandom number function seeded with the ?ow identi?er and the nexthop identi?er. When a packet arrives, the weights are generated, and the nexthop receiving the highest weight is used for forwarding. The scheme is approximately times as expensive as a hashingbased scheme, where is the number of outgoing links. Again, no performance study on the proposed scheme is presented. It is clear that although hashingbased schemes for traf?c splitting have been proposed in the past, and some simple schemes have even been implemented in mercial products, the performance of such schemes has not been adequately evaluated .This paper presents the ?rst prehensive performance study on a wide range of hashingbased schemes, using real packet traces from backbone works. III. FRAMEWORK . . In this section, we describe the behavior of an ideal traf?c splitter, explain the requirements for a practical system, and de?ne the performance metrics for assessing various schemes. A. Reference Model A load balancing system typically prises a traf?c splitter and multiple outgoing links as shown in Figure 1. In such a system, the traf?c splitter receives an ining packet from a higherspeed link and forwards it to one of the lowerspeed outgoing links. A good load balancing system should be able to split the traf?c to the multiple outgoing links evenly or by some prede?ned proportion. In [7], it has been observed that there is a close relationship between fair queuing and load balancing. We now extend their observation to a mathematical model to obtain the constraints for ideal traf?c splitting. Let us ?rst look at an ideal ?uid model where the traf?c isin?nitely divisible. Suppose that there are out going links in the load balancing system, and the capacity of link I is ui . Let Si(T,t) be the amount of traf?c forwarded to link I during the period[T,t]. The ideal load balancing system should perform as well as the corresponding system with a single outgoing link of capacity ∑ui . Therefore, the ideal system should satisfy the following for any period [T,t]: The traf?c load is essentially split in proportion to the rates of the outgoing links. At any time instance, the traf?c load is perfectly balanced。 there is no bandwidth lost because of load balancing. By workconserving, we mean no one outgoing link is idle while there is data waiting to be forwarded. Ideal load balancing is obviously impractical in a real work system. As the basic unit of forwarding is at least a single approximately times as expensive as a hashingbased scheme packet, a packetized load balancing system is no longer work where is the number of outgoing links. Again , no performance conserving. For example, suppose that a load balancing systems has two outgoing links of the same capacity. Assume that the system is initially idle, then a single packet arrives. The packet is forwarded to one of the two outgoing link. Note that the packet is serviced with half of the total bandwidth available, thus it will take twice the amount of time to transmit pared with an ideal system. During this period, one of two outgoing links is busy servicing the packet while the other link remains idle. In a practical system, the traf?c splitter may send several packets in a row 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 over