IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL 28,NO.11.NOVEMBER 2017 3157 Efficient Data Center Flow Scheduling Without Starvation Using Expansion Ratio Sheng Zhang,Member,IEEE,Zhuzhong Qian,Member,IEEE,Hao Wu,and Sanglu Lu,Member,IEEE Abstract-Existing data center transport protocols are usually based on the Processor Sharing(PS)policy and/or the Shortest Remaining Processing Time(SRPT)policy.PS divides link bandwidth equally between competing flows,thus it fails to achieve optimal average flow completion time(FCT).SRPT prioritizes flows that have the shortest remaining processing time and provides near-optimal average FCT,but it may cause long flows to suffer unfair delays,or even starve them.In fact,these two types of policies represent two directions in the design space:PS prefers fairness (in terms of starvation freedom)while SRPT favors efficiency (in terms of average FCT).In this paper,we propose a novel metric,expansion ratio,which enables us to strike a balance between SRPT and PS.We design MERP that achieves efficient flow scheduling without starvation.MERP takes care of both average and tail FCTs by minimizing the expansion ratio of competing flows in a lexicographically manner.MERP controls the sending rate of competing flows via synchronized virtual deadlines and routes flows in a downstream-aware manner that reacts quickly to link failures.We evaluate MERP using extensive NS2-based simulations.Results show that,under various traffic loads,MERP reduces the tail FCT significantly with a negligible increase of average FCT compared with pFabric,and MERP reduces the average FCT notably compared with ECMP and CONGA when link failures occur. Index Terms-Data center,flow completion time,efficiency,starvation freedom,expansion ratio 1 INTRODUCTION ODAY's data centers usually organize online interactive partition-aggregate-based online services.This is because, L services with the partition-aggregate pattern.The comple- in such kind of services,there are flows with various sizes, tion time of a large task largely depends on the flow comple- and the overall response time is often dominated by the tion times (FCT)of the flows generated in this process.In "lagger".In this sense,some online service may have better current data centers,the FCTs of these flows fluctuate dramati- performance with short tail FCT rather than short average cally [1]-they may experience 2x more mean FCT than its the- FCT.The second concern with SRPT is that,an malicious oretical minimum [2],[3].This is unacceptable,since the service could preempt bandwidth resources by simply split- response to user requests for those interactive services must be ting large flows into many small ones.If all services split quick enough:even fractions of a second could have an impor- their large flows into small ones,none of them can achieve tant influence on user experiences,which in turn impairs the better performance than no split. business revenue of cloud service providers [41,[5]. PS-based policies [8],[9],[10]reduce the queueing length To achieve low latency,many transport protocols have at switch ports through novel congestion detection and rate been proposed in recent years,among which two main tech- control mechanisms.These approaches usually divide link niques are Shortest Remaining Processing Time(SRPT)and bandwidth equally among competing flows,and thus short Processor Sharing(PS). flows are often blocked by long flows even though they can SRPT-based policies [2],[6]focus on minimizing the finish earlier.Therefore,the average FCT of PS-based poli- average FCT by prioritizing flows that have the shortest cies is larger than that of SRPT-based policies [2],which remaining processing time and have near-optimal average implicitly implies that,we cannot simultaneously achieve FCT.However,applying SRPT-based policies has several the minimum average and the minimum tail FCTs. problems.First,long flows are completely ignored by SRPT- We observe that,these two types of policies represent two based protocols [7].When short flows contribute the major- extremes in the design space:SRPT favors efficiency (in terms ity of the overall traffic,SRPT could even unfairly "starve" of average FCT)while PS prefers fairness (in terms of starva- long flows,which probably increases the response time of tion freedom).To strike a balance between them,in this paper, we propose a novel metric,i.e.,expansion ratio,which is the ratio of the actual FCT of a flow to the optimal FCT.Under The authors are with the State Key Laboratory for Novel Software Technol- this definition,if two flows are delayed on the same link by ogy,Nanjing University,Nanjing Shi 210008,China.E-mail:(sheng,qzz, sanglul@nju.edu.cn,wuhao@dislab.nju.edu.cn. the same amount of time,then the expansion ratio of the Manuscript received 4 Apr.2016;revised 8 Apr.2017;accepted 15 May 2017. shorter flow is larger than that of the other one;and the expan- Date of publication 19 May 2017;date of currenf version 11 Oct.2017. sion ratio of a flow increases as its waiting time increases. (Corresponding author:Sheng Zhang.) These properties enable us to design MERP,a distributed pro- Recommended for acceptance by H.Jin tocol that takes care of both average and tail FCTs. For information on obtaining reprints of this article,please send e-mail to: reprints@ieee.org,and reference the Digital Object Identifier below. The rate control in MERP decides the transmitting order Digital Object Identifier no.10.1109/TPDS.2017.2706290 of concurrent flows through minimizing the maximumEfficient Data Center Flow Scheduling Without Starvation Using Expansion Ratio Sheng Zhang , Member, IEEE, Zhuzhong Qian, Member, IEEE, Hao Wu, and Sanglu Lu, Member, IEEE Abstract—Existing data center transport protocols are usually based on the Processor Sharing (PS) policy and/or the Shortest Remaining Processing Time (SRPT) policy. PS divides link bandwidth equally between competing flows, thus it fails to achieve optimal average flow completion time (FCT). SRPT prioritizes flows that have the shortest remaining processing time and provides near-optimal average FCT, but it may cause long flows to suffer unfair delays, or even starve them. In fact, these two types of policies represent two directions in the design space: PS prefers fairness (in terms of starvation freedom) while SRPT favors efficiency (in terms of average FCT). In this paper, we propose a novel metric, expansion ratio, which enables us to strike a balance between SRPT and PS. We design MERP that achieves efficient flow scheduling without starvation. MERP takes care of both average and tail FCTs by minimizing the expansion ratio of competing flows in a lexicographically manner. MERP controls the sending rate of competing flows via synchronized virtual deadlines and routes flows in a downstream-aware manner that reacts quickly to link failures. We evaluate MERP using extensive NS2-based simulations. Results show that, under various traffic loads, MERP reduces the tail FCT significantly with a negligible increase of average FCT compared with pFabric, and MERP reduces the average FCT notably compared with ECMP and CONGA when link failures occur. Index Terms—Data center, flow completion time, efficiency, starvation freedom, expansion ratio Ç 1 INTRODUCTION TODAY’S data centers usually organize online interactive services with the partition-aggregate pattern. The comple￾tion time of a large task largely depends on the flow comple￾tion times (FCT) of the flows generated in this process. In current data centers, the FCTs of these flows fluctuate dramati￾cally [1]—they may experience 2x more mean FCT than its the￾oretical minimum [2], [3]. This is unacceptable, since the response to user requests for those interactive services must be quick enough: even fractions of a second could have an impor￾tant influence on user experiences, which in turn impairs the business revenue of cloud service providers [4], [5]. To achieve low latency, many transport protocols have been proposed in recent years, among which two main tech￾niques are Shortest Remaining Processing Time (SRPT) and Processor Sharing (PS). SRPT-based policies [2], [6] focus on minimizing the average FCT by prioritizing flows that have the shortest remaining processing time and have near-optimal average FCT. However, applying SRPT-based policies has several problems. First, long flows are completely ignored by SRPT￾based protocols [7]. When short flows contribute the major￾ity of the overall traffic, SRPT could even unfairly “starve” long flows, which probably increases the response time of partition-aggregate-based online services. This is because, in such kind of services, there are flows with various sizes, and the overall response time is often dominated by the “lagger”. In this sense, some online service may have better performance with short tail FCT rather than short average FCT. The second concern with SRPT is that, an malicious service could preempt bandwidth resources by simply split￾ting large flows into many small ones. If all services split their large flows into small ones, none of them can achieve better performance than no split. PS-based policies [8], [9], [10] reduce the queueing length at switch ports through novel congestion detection and rate control mechanisms. These approaches usually divide link bandwidth equally among competing flows, and thus short flows are often blocked by long flows even though they can finish earlier. Therefore, the average FCT of PS-based poli￾cies is larger than that of SRPT-based policies [2], which implicitly implies that, we cannot simultaneously achieve the minimum average and the minimum tail FCTs. We observe that, these two types of policies represent two extremes in the design space: SRPT favors efficiency (in terms of average FCT) while PS prefers fairness (in terms of starva￾tion freedom). To strike a balance between them, in this paper, we propose a novel metric, i.e., expansion ratio, which is the ratio of the actual FCT of a flow to the optimal FCT. Under this definition, if two flows are delayed on the same link by the same amount of time, then the expansion ratio of the shorter flow is larger than that of the other one; and the expan￾sion ratio of a flow increases as its waiting time increases. These properties enable us to design MERP, a distributed pro￾tocol that takes care of both average and tail FCTs. The rate control in MERP decides the transmitting order of concurrent flows through minimizing the maximum
The authors are with the State Key Laboratory for Novel Software Technol￾ogy, Nanjing University, Nanjing Shi 210008, China. E-mail: {sheng, qzz, sanglu}@nju.edu.cn, wuhao@dislab.nju.edu.cn. Manuscript received 4 Apr. 2016; revised 8 Apr. 2017; accepted 15 May 2017. Date of publication 19 May 2017; date of current version 11 Oct. 2017. (Corresponding author: Sheng Zhang.) Recommended for acceptance by H. Jin. For information on obtaining reprints of this article, please send e-mail to: reprints@ieee.org, and reference the Digital Object Identifier below. Digital Object Identifier no. 10.1109/TPDS.2017.2706290 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 28, NO. 11, NOVEMBER 2017 3157
2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information