[翻译原文] Optimizing Cost and Performance for Multihoming.pdf

Optimizing Cost and Performance for Multihoming David K Goldenberg Lili Qiu Haiyong Xie Yang Richard Yang Yin Zhang AT users cost which is another major incentive to use multihoming is not considered In addition previous studies focus on the potential performance benefi ts not on the design of al gorithms it remains an open question how such potential benefi ts can be achieved in practice In this paper we attempt to realize some of the benefi ts of smart routing by developing a series of novel algorithms for optimizing both cost and performance for multihomed users We fi rst demon strate that optimizing network performance alone can signifi cantly increase the cost of a user thus rendering smart routing less at tractive To address this issue we propose novel offl ine and on line routing algorithms to minimize a user s cost under common usage based charging models Using realistic pricing data and traf fi c demand traces from universities and enterprises we show that despite fl uctuations in traffi c our online algorithm can signifi cantly reduce a user s cost compared with using dedicated links or apply ing round robin or equal split algorithms to burstable links We also design online and offl ine algorithms to optimize the network performance of a smart routing user under cost constraints Using realistic pricing data traffi c demand traces and latency traces we show that our online algorithm achieves performance within 10 20 of the optimal offl ine algorithm In this paper we assume that the user is already multihomed to a set of ISPs Thus we focus on how to dynamically assign traffi c among them to optimize cost and performance The business deci sions of whether to use multihoming and which ISPs to choose are by themselves very complicated and may involve many technical and non technical factors which we do not attempt to address in this paper We also assume that cost and performance are the main factors of interest to the user For many real Internet services such as Virtual Private Networks VPNs however optimizing cost and performance alone may not be enough Other factors such as ease of management ease of trouble shooting security and Quality of Service QoS also play critical roles in users business decisions So our techniques are not directly applicable in such contexts Nev ertheless we believe that in order to better understand the potential role of smart routing in the future Internet it is important to go beyond previous performance centric studies by placing both cost and performance in a common optimization framework Besides developing techniques for optimizing cost and perfor mance we also evaluatethe global effectsof suchoptimization We note that smart routing becomesa selfi sh routingscheme wheneach individual smart routing user adaptively changes its routes to opti mize its own metrics without considering its effects on the network Such adaptation changes network performance and may cause self interference or interference with other smart routing or regular i e single homed traffi c It remains to be seen whether smart routing can retain its performance benefi ts in the presence of such forms of interference We use extensive simulations to study the global effects of smart routing We fi rst examine the equilibrium performance of smart routing in the presence of self interference i e when the rout ing decisions made by the smart routing user change the network performance which in turn interferes with the decisions involved in smart routing Our results suggest that even in the presence of self interference our algorithms still achieve good equilibrium performance We then evaluate how smart routing traffi c interacts with other smart routing traffi c as well as with single homed traffi c Ourevaluationsarebasedonaninter domainnetworktopologyand user demands from real traffi c traces Our results show that smart routing improves performance without degrading the performance of other traffi c Our key contributions can be summarized as follows We design offl ine and online algorithms to minimize cost based on realistic usage based charging models We design offl ine and online algorithms to optimize network performance under cost constraints We use both analysis and simulations based on realistic traf fi c and performance data to demonstrate that our algorithms yield good performance and low cost We evaluate the performance of smart routing when multiple users selfi shly optimize their own cost and performance We fi nd that under this setting smart routing traffi c interacts well with other traffi c under traffi c equilibria The rest of this paper is organized as follows In Section 2 we review related work In Section 3 we discuss our network and charging models In Section 4 we motivate the importance of opti mizing cost and present novel cost optimization algorithms In Sec tion 5 we optimize network latency under given cost constraints We present the methodology and results of our evaluations in Sec tion 6 In Section 7 we study the global effects of smart routing and evaluate its interactions with other traffi c We conclude and discuss future work in Section 8 2 RELATED WORK Several recent studies have shown that Internet routing often yields sub optimal user performance e g 4 27 32 33 There are a number of contributing factors including routing hierarchy policy routing and slow reaction if any to transient network con gestion or failures BGP routing instabilities can further exacerbate the problem These observations have generated considerable re search interest in offering end users more control in route selection For instance the authors in 4 27 propose using overlay routing to improve user performance Achieving a large scale deployment with this approach is challenging as cooperation among multiple organizations is not easy to arrange in practice Multihoming is an alternative way to enable users to control routes Many large enterprises stub ISPs and even small businesses already use multihoming as a way to connect to the Internet Much of the previous work on multihoming focuses on how to design protocols to implement multihoming e g 5 7 11 30 For example the authors of 5 7 12 24 30 use BGP peering as an implementation technique Another technique is through DNS or NAT which is used in 9 21 Our work differs from the above in that we do not focus on the implementations but instead on de signing algorithms to determine when and how much traffi c a user should assign to different ISPs to optimize both performance and cost Consequently our work is complementary to the above There are several papers that evaluate the benefi ts of smart rout ing including 8 28 29 More recently Akella et al 1 quantify the potential performance benefi ts of multihoming using real Inter net traces Their results show that smart routing has the potential to achieve an average performance improvement of 25 or more for a 2 multihomed user in most cases and that most of the benefi t can be achieved using 4 providers Motivated by these results we seek to develop routing schemes to achieve such benefi ts in practice In addition we study the effects of un coordinated route optimization by multiple mutually interfering smart routing users Finally there are a few research studies on designing algorithms forsmartrouting e g 1 15 17 Forexample OrdaandRom 17 investigate where to place multihomed users and show that the problem is NP hard Cao et al 6 propose using hash functions to achieve load balancing among multiple links In 11 the au thors compare several route selection schemes in a local area net work and show that hashing can achieve performance comparable to load sensitive route selection Our work differs from these stud ies in that we use both cost and network performance as metrics of interest We also study the interactions between multiple smart routing users and between smart routing and single homed users 3 NETWORK AND CHARGING MODELS In this section we describe our network model ISP charging models and the performance metric we use 3 1Network Model ISP K WAN user ISP 2 ISP 1 Figure 1 An illustration of a user with K service providers A multihomed user has multiple links to the Internet for sending and receiving traffi c as shown in Figure 1 The implementation techniques of distributing traffi c to the links are different for outgo ing and incoming traffi c For outgoing traffi c a border router inside the user s network can actively control how traffi c is distributed For incoming traffi c a user can use NAT or DNS to control the routes For more detailed discussions about the implementations we refer the readers to 1 5 7 11 30 Note that the implementations of multihoming are complemen tary to our study as our focus is on determining when and how much traffi c should be assigned to each link Consequently our algorithms can be applied to a wide variety of multihoming im plementations and work for both out going and incoming traffi c Since our traffi c traces as described below consist of only out going traffi c we evaluate traffi c assignment only in the out bound direction in this paper 3 2Charging Models Users pay ISPs for using their service The cost incurred is usu ally based on the amount of traffi c a user generates i e cost c x where x is a variable determined by a user s traffi c which we will term the charging volume and c is a non decreasing func tion that maps x to cost Various charging models differ from one another in their choices of charging volume x and cost function c Usually thecostfunctioncisapiece wiselinear non decreasing function which we will use for our design and evaluation There are several ways in which the charging volume x can be deter mined Percentile based charging and total volume based charging are both in common use Percentile basedcharging Thisisatypicalusage basedcharg ing scheme currently in use by ISPs 26 Under this scheme an ISP records the traffi c volume a user generates during every 5 minute interval At the end of a complete charg ing period the q th percentile of all 5 minute traffi c volumes is used as the charging volume x for q percentile charging More specifi cally the ISP sorts the 5 minute traffi c volumes collected during the charging period in ascending order and then computes the charging volume x as the q I th vol ume where I is the number of intervals in a charging period For example if 95th percentile charging is in use and the charging period is 30 days then the cost is based on the traf fi c volume sent during the 8208 th 95 30 24 60 5 8208 sorted interval Total volumebasedcharging Thisisastraightforwardcharg ing model where the charging volume x is the total volume of traffi c a user generates during the entire charging period In this paper we focus primarily on percentile based charging We describe how to deal with total volume based charging in Ap pendix C In our evaluations we use two sets of pricing functions The fi rst set of functions are simple pricing functions if the charg ing volume is 0 the price is 0 otherwise the price is a constant value We pick the values from the entries in Table 1 which is pub lished in 25 1In this table a burstable link is a link whose price is determined by the percentile based charging model a full rate link is also called a dedicated link and has a fi xed price indepen dent of usage To evaluate the sensitivity of our algorithms to cost functions we also use another set of functions shown in Figure 2 These functions are the more complex step functions The prices at 24 Mbps for DS3 and at 100 Mbps for OC3 match those in Table 1 The overall trend of the pricing curves refl ects the general pricing practice of decreasing unit cost as bandwidth increases it is also consistent with the pricing curves we are aware of e g 3 18 3 3Network Performance Metric There are several ways to measure network performance In our evaluations we use end to end latency as the metric As shown in 24 latency not only refl ects network response time but also serves as a measure of availability as users often consider large 1Prices are based on a February 2002 Blind RFP All prices listed are discounted based on a two year 240 000 annual commitment with installation in a San Jose CA facility Prices do not include recurring and non recurring local access fees Given a set of ded icated links available the cost of using dedicated links is the min imum cost of links such that their total capacity exceeds the max imum traffi c load Note that the price of ISP5 is corrected from 23 750 in the original publication to 28 750 ISPBurstableFull rateBurstableFull rate DS3DS3OC3OC3 24 Mbps 45 Mbps 100 Mbps 155 Mbps ISP1 12 131 13 000 32 500 43 245 ISP2 11 160 18 652 29 900 46 930 ISP3 9 870 12 690 37 088 45 989 ISP4 7 600 10 500 19 600 29 000 ISP5 6 300 9 000 24 700 28 750 Table 1 The pricing data 0 5000 10000 15000 20000 0 5 10 15 20 25 30 35 40 45 Monthly Charge Mbps a DS3 pricing functions 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 0 20 40 60 80 100 120 140 160 Monthly Charge Mbps b OC3 pricing functions Figure 2 The more complex pricing functions delay or rapidly increasing latency as a sign of a potential avail ability problem Our algorithms can be easily extended to work with alternative metrics e g a combination of latency and loss rate latency w log 1 1 lossRate where w is the relative weight of loss rate 4 MINIMIZING TOTAL COST Since the previous studies focus on improving network perfor mance without considering cost we fi rst motivate the need to opti mize cost We showthat by optimizing networkperformance alone users may incur high cost Since the percentile based charging model is in common use we illustrate our point below using a sim ple example under this model Our performance results in Section 6 will further support this point using real data Consider a user with K identical links to K ISPs Suppose the user has one unit of traffi c to send at each interval and the latency of each link at each interval is drawn uniformly from a common range In each interval to minimize latency the user sends all of its traffi c through the link with the lowest latency while the other links receive no traffi c Since the latency through different links are iden tically distributed each link receives traffi c for approximately 1 K of the intervals Therefore when K is less than 20 e g K 4 the 95th percentile of each link is one This implies that by optimizing performance the user pays K times the cost of using a single link This K fold increase in cost is clearly unacceptable to most users Given this potential of a large cost increase in this section we study how to design effective smart routing algorithms to optimize cost As mentioned in Section 3 we focus on the percentile based charging model We present an algorithm for dealing with the total volume based charging model in Appendix C 4 1 Problem Specifi cation We fi rst introduce the following notation KThe number of ISPs We use k as the index ckThe cost function of ISP k Without loss of generality we assume that ckis a piece wise linear non decreasing function IThe number of time intervals in a charging period We use i as the index F The number of fl ows We use f as the index v i f The traffi c volume of fl ow f during interval i v i The total traffi c volume during interval i i e v i P fv i f Let time series V v i 1 i I t i k The volume of traffi c distributed to ISP k during interval i Let time series Tk t i k 1 i I Note that V P kTk with vector summation qkThe charging percentile of ISP k e g qk 0 95 if an ISP charges at 95th percentile qt X q The dq X e th value in Xsorted or 0 if q 0 where Xsortedis X sorted in non decreasing order and X is the number of elements in X pkThe charging volume of ISP k i e pk qt Tk qk For example if ISP k charges at 95th percentile then pk is the 95th percentile of the traffi c assigned to ISP k We now formally specify the fl ow assignment problem Given cost functions ck the fl ow assignment problem is to fi nd t i k that minimizes the total cost PK k 1ck pk We consider two cases fractional fl ow assignment and integral fl ow assignment Under fractional fl ow assignment fl ows are in fi nitely splittable In contrast integral fl ow assignment assumes that during each interval each fl ow is assigned to only one ISP In the latter case fl ows can be naturally defi ned using destination pre fi xes when BGP is used to implement smart routing The traffi c assignment problem be it fractional or integral can be further classifi ed into two categories offl ine or online The of fl ine version assumes that v i f are given in advance whereas the online version needs to predict v i f and deals with prediction er rors The online integral algorithms are more practical and have lower control overhead The offl ine fractional algorithms are also important because they provide a lower bound on cost and further serve as a basis for designing our online algorithms 4 2 Offl ine Fractional Flow Assignment We begin by solving the offl ine fractional fl ow assignment prob lem We fi rst present an effi cient algorithm to compute an optimal traffi c assignment when ISPs do not have capacity constraints We then extend the algorithm to deal with capacity constraints 4 2 1An Optimal Algorithm for Percentile based Charging Without Capacity Constraints A key to optimizing cost is to determine the charging volumes For example when ISPs use the 95th percentile charging model we need to determine the 95th percentile traffi c volume for each ISP Once we know the charging volume for each ISP we can as sign traffi c by ensuring that the number of intervals in which ISP k serves more than its charging volume of traffi c does not exceed 1 qk I e g 5 I for 95th percentile charging Based on the above observation we develop an effi cient algo rithm that computes an optimal traffi c assignment in two steps i compute the charging volume for each ISP and ii assign traff