【正文】 . . 中文 5790 字 畢業(yè)設(shè)計(jì) 外文翻譯 專 業(yè) 網(wǎng) 絡(luò) 工 程 班 級 學(xué) 生姓名 xx 學(xué) 號 xx 指 導(dǎo)教師 . . Performance of HashingBased Schemes for Inter Load Balancing Zhiruo Cao ,Zheng Wang ,Ellen Zegura College of Computing Geia Institute of Technology Atlanta, GA 303320280 Bell Labs Lucent Technologies Holmdel , NJ 07733 Abstract—Load balancing is a key technique for improving Inter 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 of packets within a ?ow. Although hashingbased load balancing schemes have been proposed in the past, this is the first prehensive study of their performance using real traffic traces. We evaluate five direct hashing methods and one tablebased hashing method. We find that hashing using a 16bit CRC over the Five tuple gives excellent load balancing performance. Further, loadadaptive tablebased hashing using the exclusive OR of the source and destination IP addresses achieves parable performance to the 16bit CRC. Tablebased hashing can also distribute traffic load according to unequal weights. We also report on four other schemes with poor to moderate performance. Keywords—Load sharing, hashing. I. INTRODUCTION Load balancing (also known as load sharing) is a key technique for improving the performance and scalability of the Inter. For example, many large enterprise works are connected to multiple Inter Service Providers (ISPs) to achieve redundant connectivity and to distribute traffic loading. Inside the Inter, 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 equalcost paths and allow load balancing over them. . . The parallel trunks may bee even more ubiquitous when the promising Dense Wavelength Division Multiplexing (DWDM) 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