Minimizing the flow completion time (FCT) is widely considered as an important optimization goal in designing data center networks. However, existing schemes either rely on the precondition that the size and deadline of each flow is known in advance, or require modifying the switch hardware, which is hard to implement in practice. In this paper, we present a flexible and dynamic flow scheduling strategy, namely, Maximal Completion Probability First (MCPF), to reduce the FCT. This strategy is based on the estimated probabilities of each flow to finish the transmission in a period time, and these flows which have higher completion probabilities are assigned with higher priority. Meanwhile, switches perform flow scheduling according to these priorities. We employ a queueing theory based mathematical model to analyze the average FCT of MCPF, and compare it with other two flow scheduling strategies. We also introduce the challenges and the solutions to implement MCPF in realistic networks. Finally, we evaluate the performance of MCPF in Mininet. The analysis and experimental results show that MCPF could effectively reduce the FCT.
D.Abts and B.Felderman, A guided tour of data-center networking, Commun. ACM6 (2012), 44–51. doi:10.1145/2184319.2184335.
2.
M.Al-Fares, S.Radhakrishnan, B.Raghavan, N.Huang and A.Vahdat, Hedera: Dynamic flow scheduling for data center networks, in: USENIX NSDI, San Jose, California, USA, 2010.
3.
M.Alizadeh, A.Greenberg, D.A.Maltz, J.Padhye, P.Patel, B.Prabhakaret al., Data center TCP (DCTCP), in: ACM SIGCOMM, New Delhi, India, 2010, pp. 63–74.
4.
M.Alizadeh, A.Kabbani, T.Edsall, B.Prabhakar, A.Vahdat and M.Yasuda, Less is more: Trading a little bandwidth for ultra-low latency in the data center, in: USENIX NSDI, San Jose, CA, USA, 2012, pp. 19–30.
5.
M.Alizadeh, S.Yang, M.Sharif, S.Katti, N.Mckeown, B.Prabhakar and S.Shenker, pFabric: Minimal near-optimal datacenter transport, in: ACM SIGCOMM, Hong Kong, China, 2013, pp. 435–446.
6.
W.Bai, L.Chen, K.Chen, D.Han, C.Tian and H.Wang, Information-agnostic flow scheduling for commodity data centers, in: USENIX NSDI, Oakland, CA, USA, 2015, pp. 455–468.
7.
N.Bansal and M.Harchol-Balter, Analysis of srpt scheduling: Investigating unfairness, in: ACM SIGMETRICS, Cambridge, Massachusetts, USA, 2001, pp. 279–290.
8.
T.Benson, A.Akella and D.Maltz, Network traffic characteristics of data centers in the wild, in: IMC, Melbourne, Australia, 2010, pp. 267–280.
9.
M.Chowdhury and I.Stoica, Efficient coflow scheduling without prior knowledge, in: ACM SIGCOMM, London, United Kingdom, 2015, pp. 393–406.
10.
R.O.Duda and P.E.Hart, Pattern Classification and Scene Analysis, John Wiley & Sons, 1973.
11.
N.Dukkipati, M.Kobayashi, R.Zhang-Shen and N.McKeown, Processor sharing flows in the Internet, in: IWQoS, Passau, Germany, 2005, pp. 267–281.
12.
A.Greenberg, J.R.Hamilton, N.Jain, S.Kandula, C.Kim, P.Lahiriet al., VL2: A scalable and flexible data center network, in: ACM SIGCOMM, Barcelona, Spain, 2009, pp. 51–62. doi:10.1145/1592568.1592576.
13.
D.Gross, J.F.Shortle, J.M.Thompson and C.M.Harris, Fundamentals of Queueing Theory, Wiley-Interscience, 2008.
14.
I.R.S.Ha and L.Xu, Cubic: A new TCP-friendly high-speed TCP variant, ACM SIGOPS Operating Systems Review – Research and developments in the Linux kernel5 (2008), 64–74. doi:10.1145/1400097.1400105.
15.
N.Handigol, B.Heller, V.Jeyakumar, B.Lantz and N.McKeown, Reproducible network experiments using container-based emulation, in: ACM CoNEXT, Nice, France, 2012, pp. 253–264.
16.
T.Henderson, S.Floyd, A.Gurtov and Y.Nishida, The NewReno modification to TCP’s fast recovery algorithm, RFC 6582, 2012.
17.
C.-Y.Hong, M.Caesar and P.B.Godfrey, Finishing flows quickly with preemptive scheduling, in: ACM SIGCOMM, Helsinki, Finland, 2012, pp. 127–138.
18.
C.Hu, B.Liu, C.Xing, Z.Yue, L.Song and M.Chen, Queueing model based analysis on flow scheduling in information-agnostic datacenter networks, in: IEEE ICC, Kuala Lumpur, Malaysia, 2016.
19.
Iperf, https://iperf.fr/.
20.
C.Jin, D.X.Wei and S.Low, FAST TCP: Motivation, architecture, algorithms, performance, IEEE/ACM Transactions on Networking6 (2006), 1246–1259. doi:10.1109/TNET.2006.886335.
21.
S.Kandula, S.Sengupta, A.Greenberg, P.Patel and R.Chaiken, The nature of datacenter traffic: Measurements and analysis, in: IMC, Chicago, Illinois, USA, 2009, pp. 202–208. doi:10.1145/1644893.1644918.
22.
C.Lu, Queueing Theory, Beijing University of Post and Telecommunication Press, 1993.
23.
A.Munir, I.A.Qazi, Z.A.Uzmi, A.Mushtaq, S.N.Ismail, M.S.Iqbal and B.Khan, Minimizing flow completion times in data centers, in: IEEE INFOCOM, Turin, Italy, 2013.
24.
I.A.Rai, G.Urvoy-Keller and E.W.Biersack, Analysis of las scheduling for job size distributions with high variance, in: ACM SIGMETRICS, San Diego, CA, USA, 2003, pp. 218–228.
25.
C.Raiciu, S.Barre, C.Pluntke, A.Greenhalgh, D.Wischik and M.Handley, Improving datacenter performance and robustness with multipath tcp, in: ACM SIGCOMM, Toronto, Ontario, Canada, 2011, pp. 266–277.
26.
K.Ramakrishnan, S.Floyd and D.Black, The addition of explicit congestion notification (ECN) to IP, RFC 3168, 2001.
27.
B.Vamanan, J.Hasan and T.Vijaykumar, Deadline-aware datacenter TCP (D2TCP), in: ACM SIGCOMM, Helsinki, Finland, 2012, pp. 115–126.
28.
C.Wilson, H.Ballani, T.Karagiannis and A.Rowstron, Better never than late: Meeting deadlines in datacenter networks, in: ACM SIGCOMM, Toronto, Ontario, Canada, 2011, pp. 50–61.
29.
H.Wu, Z.Feng, C.Guo and Y.Zhang, Ictcp: Incast congestion control for tcp in data center networks, in: IEEE/ACM Transactions on Networking, Vol. 2, 2013, pp. 345–358.
30.
B.Xu, C.Hu, B.Liu, C.Xing and D.Li, Queue demotion threshold configuration for minimizing flow completion in information-agnostic datacenters, in: IEEE ICC, Paris, France, 2017.
31.
H.Xu and B.Li, RepFlow: Minimizing flow completion times with replicated flows in data centers, in: IEEE INFOCOM, Toronto, Canada, 2014.
32.
S.Yang and G.De Veciana, Enhancing both network and user performance for networks supporting best effort traffic, IEEE/ACM Trans. on Networking2 (2004), 349–360. doi:10.1109/TNET.2004.826280.
33.
D.Zats, T.Das, P.Mohan, D.Borthakur and R.Katz, DeTail: Reducing the flow completion time tail in datacenter networks, in: ACM SIGCOMM, Helsinki, Finland, 2012, pp. 139–150.
