外文翻譯--基于哈希模式的負(fù)載均衡性能研究

1、<p><b>　　中文5790字</b></p><p><b>　　畢業(yè)設(shè)計(jì)外文翻譯</b></p><p>　　專 業(yè) 網(wǎng)絡(luò)工程 </p><p>　　班 級(jí) </p><p>

2、　　學(xué)生姓名 xx </p><p>　　學(xué) 號(hào) xx </p><p>　　指導(dǎo)教師 </p><p>　　

3、Performance of Hashing-Based Schemes for Internet Load Balancing</p><p>　　Zhiruo Cao ,Zheng Wang ,Ellen Zegura</p><p>　　College of Computing</p><p>　　Georgia Institute of Technology

4、</p><p>　　Atlanta, GA 30332-0280</p><p>　　Bell Labs </p><p>　　Lucent Technologies Holmdel , NJ 07733</p><p>　　Abstract—Load balancing is a key technique for improving I

5、nternet 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

6、 of packets within a ?ow. 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.</p><p>　　We evalu

7、ate 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

8、 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 ot

9、her schemes with poor to moderate performance.</p><p>　　Keywords—Load sharing, hashing.</p><p>　　I. INTRODUCTION</p><p>　　Load balancing (also known as load sharing) is a key techni

10、que for improving the performance and scalability of the Internet. For example, many large enterprise networks are connected to multiple Internet Service Providers (ISPs) to achieve redundant connectivity and to distribu

11、te traffic loading. Inside the Internet, the backbones are often engineered to have multiple parallel trunks between major Points of Presence to ensure high availability. Typically, these parallel trunks are con?gured as

12、 </p><p>　　The parallel trunks may become even more ubiquitous when the promising Dense Wavelength Division Multiplexing (DWDM) technology is deployed in the future Internet back-bone. DWDM expands the capac

13、ity of communication 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 b

14、est utilizing the multiple parallel channels.</p><p>　　Parallel architectures have been used for packet processing for coping with exponential growth in Internet traffic, Instead of one processing engine, pa

15、ckets 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 machine

16、s and the routers connected to them split the HTTP requests to different machines.</p><p>　　For all of these examples, effective use of load balancing requires good schemes for splitting traffic over multipl

17、e links. In addition, since the majority of the traffic on the Internet is TCP-based [1], traffic splitting schemes need to avoid packet misordering within a TCP ?ow, which can falsely trigger congestion control mechanis

18、ms and cause unnecessary throughput degradation [2], [3].</p><p>　　In this paper, we propose and evaluate a class of hashing based traffic splitting algorithms which preserve per-?ow packet ordering. We cons

19、ider five hash functions that are “direct,”meaning that the hash function produces a value in the range of 0...N-1, where N is the number of outgoing links. We also consider a table-based generalization that involves has

20、hing 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 </p><p>　　Our results are obtained by simulating the performance of

21、 a traf?c splitter, using packet traces taken from two trunks of a major Internet backbone provider. We ?nd that direct hashing with the destination IP address causes signi?cant imbalance across two links. Using the Inte

22、rnet 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 computationally complex 16-bit CRC of the ?ve

23、-tu</p><p>　　Table-based hashing has the additional advantage that it can distribute the load according to unequal weights. Further, an index-based version of this scheme can alter the weight distribution wi

24、th minimal disruption to existing ?ows . Our results con?rm that the index-based hashing can accurately achieve a weighted distribution when adaptation is also used.</p><p>　　The rest of this paper is organi

25、zed 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 t

26、he performance metrics that will be used to assess various hashing-based 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

27、 of the randomness inherent </p><p>　　II. RELATED WORK</p><p>　　Load balancing has been used in telecommunication networks in the form of inverse multiplexing [4]. Inverse multiplexing allows se

28、rvice providers to offer wideband channels by combining 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

29、], [7].</p><p>　　Our work differs from inverse multiplexing in two important dimensions. First, inverse multiplexing is designed for use over point-to-point links; its techniques are not typically applicable

30、 for network layer load balancing. Internet load balancing, however, makes use of the natural redundancy in the network topology. The paths for load balancing, for example, equal-cost multi-paths, are discovered dynamica

31、lly by routing protocols, such as OSPF [8], rather than through configuration. Second, in </p><p>　　Hashing has been widely used in indexing and searching [9].In the networking context, hashing-based algorit

32、hms for address lookup [10], ?ow identi?cation [11] and packet demultiplexing [12] have been proposed in the past. The use of hashing for network load balancing is not new. Some commercial router products have implemente

33、d simple hashing over the IP destination address to distribute traf?c [13]. In the OSPF Optimized Multipath protocol (OSPF-OMP) [14], a number of possible approaches for loa</p><p>　　A traf?c splitting schem

34、e using random numbers is proposed in [16]. It applies the name-based mappings approach to load balancing [17]. In this scheme, each next-hop is assigned with a weight based on a simple pseudo-random number function seed

35、ed with the ?ow identi?er and the next-hop identi?er. When a packet arrives, the weights are generated, and the next-hop receiving the highest weight is used for forwarding. The scheme is approximately times as expensive

36、 as a hashing-based scheme, where is</p><p>　　It is clear that although hashing-based schemes for traf?c splitting have been proposed in the past, and some simple schemes have even been implemented in commer

37、cial products, the performance of such schemes has not been adequately evaluated .This paper presents the ?rst comprehensive performance study on a wide range of hashing-based schemes, using real packet traces from backb

38、one networks.</p><p>　　III. FRAMEWORK</p><p>　　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 m

39、etrics for assessing various schemes.</p><p>　　A. Reference Model</p><p>　　A load balancing system typically comprises a traf?c splitter and multiple outgoing links as shown in Figure 1. In such

40、 a system, the traf?c splitter receives an incoming packet from a higher-speed link and forwards it to one of the lower-speed outgoing links. A good load balancing system should be able to split the traf?c to the multipl

41、e outgoing links evenly or by some pre-de?ned proportion.</p><p>　　In [7], it has been observed that there is a close relationship between fair queuing and load balancing. We now extend their observation to

42、a mathematical model to obtain the constraints for ideal traf?c splitting.</p><p>　　Let us ?rst look at an ideal ?uid model where the traf?c isin?nitely divisible. Suppose that there are out going links in t

43、he 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 sys

44、tem with a single outgoing link of capacity ∑ui . Therefore, the ideal system should satisfy the following for any period [T,t]:</p><p>　　The traf?c load is essentially split in proportion to the rates of th

45、e outgoing links. At any time instance, the traf?c load is perfectly balanced; all outgoing links are busy or idle at the same time. Such a system is work-conserving; there is no bandwidth lost because of load balancing.

46、 By work-conserving, we mean no one outgoing link is idle while there is data waiting to be forwarded.</p><p>　　Ideal load balancing is obviously impractical in a real network system. As the basic unit of fo

47、rwarding is at least a single approximately times as expensive as a hashing-based scheme packet, a packetized load balancing system is no longer work where is the number of outgoing links. Again , no performance conservi

48、ng. 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</p><p>　　In a packeti

49、zed 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 coming until the packet is served. Assume the packet is forwarde

50、d 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 shou

51、ld satisfy the following:</p><p>　　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 th

52、an the time to send a largest packet over the slower link.</p><p>　　B. Requirements</p><p>　　There are a number of basic requirements that traf?c splitting schemes should meet for Internet load

53、balancing:</p><p>　　Low Overhead . Traf?c splitting is executed for every packet in the packet forwarding path, thus the per-packet overhead it introduces is a major concern. Traf?c splitting algorithms shou

54、ld be very simple and preferably keep no or little state.</p><p>　　High Ef?ciency. Poor traf?c distribution will result in uneven link utilization and loss of bandwidth. A traf?c splitter should try to distr

55、ibute traf?c as close as possible to the reference model.</p><p>　　High Ef?ciency. Poor traf?c distribution will result in uneven link utilization and loss of bandwidth. A traf?c splitter should try to distr

56、ibute traf?c as close as possible to the reference model.</p><p>　　Per-Flow Ordering. Packet mis-ordering within a TCP ?ow can produce false congestion signals and cause unnecessary throughput degradation [2

57、], [3]. It is therefore an essential requirement that the traffic splitting algorithms maintain per-flow packet ordering. This has to be achieved without requiring a new protocol layer.</p><p>　　Let us now a

58、pply the above requirements to some of the possible traffic splitting approaches. Take packet-by-packet round robin or some form of fair queuing for example. The overheads are low and the performance is typically close t

59、o 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 man

60、y cases, only work over point-to-point links.</p><p>　　Hashing-based traf?c splitting algorithms are stateless and fairly easy to compute, particularly with hardware assistance. What is more, if the hash fun

61、ctions use any combination of the ?ve-tuple as input, per-flow ordering can be preserved 1. As we will show later in this paper, many of the hashing-based schemes perform well. Overall, hashing-based schemes meet the ab

62、ove requirements and offer the best tradeoff.</p><p>　　This is true because all packets within the same TCP ?ow have the same ?ve-tuple, thus the output of the hash function with the ?ve-tuple as input shoul

63、d always be the same.</p><p>　　C. Performance Metrics</p><p>　　We now discuss the basic performance metrics for evaluating traf?c splitting algorithms for Internet load balancing.</p><

64、;p>　　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

65、this section, in an ideal system, the traffic load should be distributed in proportion to the rates of the outgoing links.</p><p>　　Queue Length. In any practical system, the load distribution curve usually

66、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 ano

67、ther 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 </p><

68、;p>　　Non-Work-Conserving Idle Time. As we have discussed earlier, a packetized load balancing system is non-work- conserving. We de?ne the non-work-conserving idle time as the length of the period when at least one li

69、nk is idle while others are busy. The idle time metric captures the non-work-conserving inclination of the system: the larger the idle time metric is, the farther away the system skews from work-conserving, and hence the

70、 less efficient the load balancing is.</p><p>　　IV. HASHING-BASED APPROACHES</p><p>　　In this section, we describe the hashing-based schemes for load balancing that we will evaluate in the next

71、section.</p><p>　　A. Direct Hashing</p><p>　　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 ?ve-

72、tuple, 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.</p>&l

73、t;p>　　A.1 Hashing of Destination Address</p><p>　　The simplest scheme is to hash the IP destination address modulo the number of outgoing links N. It can be expressed as:</p><p>　　In this sch

74、eme, 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.</p><p>　　A.2 Hashing Using XOR Foldin

75、g of Destination Address</p><p>　　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 t

76、he destination IP address. This hash function can be expressed as:</p><p>　　Where is Di the ith octet of the destination IP address .This approach utilizes more bits of the destination address in selecting t

77、he link.</p><p>　　A.3 Hashing Using XOR Folding of Source and Destination Addresses</p><p>　　A simple modification to the previous hash function is to include the source address in the computati

78、on, i.e., XOR folding with both the destination IP address and the source IP address .This hash function can be expressed as:</p><p>　　where Si and are the ith octets of the source and destination IP address

79、es respectively.</p><p>　　A.4 Internet Checksum</p><p>　　The Internet Checksum algorithm proposed in RFC791 [18] is relatively simple to compute and is also a good hash function. In this paper,

80、we examine its performance for traffic splitting. We feed the ?ve-tuple as input to the 16-bit Internet checksum computation. The index of the outgoing link is calculated from the checksum result modulo by N. This hash f

81、unction can be expressed as:</p><p><b>　　A.5 CRC16</b></p><p>　　The 16-bit CRC (Cyclic Redundant Checksum) algorithm [19] has been proposed as a possible candidate for load balancing

82、. Although more complex compared with the other hash functions discussed above, CRC16 has been successfully implemented in high-speed systems. In the CRC16 scheme, the traffic splitter takes the ?ve-tuple, applies CRC16,

83、 and takes modulo by to obtain the outgoing link. The hash function can be expressed as:</p><p>　　B. Table-Based Hashing</p><p>　　Although direct hashing is simple, it also has some limitations.

84、</p><p>　　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 organization m

85、ay have two links to Internet backbones with one link twice the speed of the other. The organization may wish to distribute the traffic with a 2:1 ratio. Secondly, with direct hashing, it is almost impossible to tune the

86、 load distribution. The table-based hashing approach we discuss below addresses bot</p><p>　　A table-based hashing scheme first splits a traffic stream into M bins. The M bins are then mapped to N outgoing l

87、inks 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 pre-defined ratio. One can also tune the performance of traffic splitting by

88、 adjusting the allocation table. The ratio of M and N determines the granularity of adjustment. Typically, M is one or two orders of magnitude larger than N, thus one</p><p>　　There are two basic approaches

89、for implementing a table- based scheme. One approach requires N-1 thresholds to be maintained, one for each outgoing link (see Figure 3). The thresholds are used to divide the M bins into N partitions. When a packet arri

90、ves, the traffic splitter computes the hashing and compares the hash value against the N-1 thresholds to determine the outgoing link. For example, suppose we want to split load over two outgoing links with a 2:1 ratio. W

91、e can simply set the threshol</p><p>　　A more flexible approach is to associate the outgoing link index with each of the M bins(see Figure4).This index-based approach requires more memory than the threshold-

92、based approach(M indexes versus N-1 thresholds).On the other hand ,the mapping from the hash value to the outgoing link is simpler with the index-based approach. It can be done with a direct table look up where as with t

93、he threshold-based approach , the hash value has to be compared with the N-1 thresholds.</p><p>　　The index-based approach is more flexible since each of the M bins can be assigned to N outgoing links indepe

94、ndently. This can be used to minimize disruption to the existing traffic when load splitting is adjusted, or new links are added or shutdown. In contrast, the threshold-based approach may cause a significant amount of fl

95、ows to change their outgoing links. For example suppose that a new link is added to the existing two load balance links. If the load is to be evenly distributed, 1/2 of th</p><p>　　基于哈希模式的負(fù)載均衡性能研究</p>

96、<p>　　亞特蘭大佐治亞理工學(xué)院計(jì)算機(jī)學(xué)院，GA30332-0280</p><p>　　貝爾實(shí)驗(yàn)室，朗訊科技，霍爾姆德爾，NJ 07733</p><p>　　摘要 負(fù)載均衡是一種提高互聯(lián)網(wǎng)性能的關(guān)鍵技術(shù)。有效利用負(fù)載均衡的需要良好的流量分配方案。我們研究分布在多個(gè)鏈路層幾個(gè)哈希方案的執(zhí)行情況，同時(shí)保留流量數(shù)據(jù)包的通信順序。雖然在過去已提出過基于哈希的負(fù)載均衡方案，但這是

97、首次使用實(shí)際流量記錄的結(jié)果的全面研究分析。</p><p>　　我們?cè)u(píng)估了五個(gè)直接哈希方法和一個(gè)基于表的哈希方法。我們發(fā)現(xiàn)使用五元組的CRC16哈希算法具有優(yōu)秀的負(fù)載均衡性能。此外，基于哈希表的負(fù)載自適應(yīng)使用源目IP地址使用異或位移的達(dá)到媲美CRC16的性能?；诒淼墓＿€可以根據(jù)不同權(quán)重分配流量負(fù)載。我們得出了其他四個(gè)方案性能在較差到中等的結(jié)論。</p><p>　　關(guān)鍵字 — — 負(fù)載

98、分享，哈希。</p><p><b>　　引言</b></p><p>　　負(fù)載均衡（也稱為負(fù)載分擔(dān)）是改善互聯(lián)網(wǎng)的性能和可擴(kuò)展性的關(guān)鍵技術(shù)。 例如，許多大型企業(yè)網(wǎng)絡(luò)連接到多個(gè)互聯(lián)網(wǎng)服務(wù)提供商（ISP），以實(shí)現(xiàn)冗余連接和分配流量負(fù)載。在互聯(lián)網(wǎng)內(nèi)部，內(nèi)部骨干往往設(shè)計(jì)有多個(gè)并行的主鏈路在于主要節(jié)點(diǎn)之間，以確保高效性。通常情況下，這些并行的主鏈路被配置為等價(jià)路徑負(fù)載均衡進(jìn)行