Optimizing Network Latency with Fast Path Assignment for Incoming Flows

Authors: Qing Lyu, Hang Zhu

Abstract:

Various flows in the network require to go through different types of middlebox. The improper placement of network middlebox and path assignment for flows could greatly increase the network latency and also decrease the performance of network. Minimizing the total end to end latency of all the ows requires to assign path for the incoming flows. In this paper, the flow path assignment problem in regard to the placement of various kinds of middlebox is studied. The flow path assignment problem is formulated to a linear programming problem, which is very time consuming. On the other hand, a naive greedy algorithm is studied. Which is very fast but causes much more latency than the linear programming algorithm. At last, the paper presents a heuristic algorithm named FPA, which takes bottleneck link information and estimated bandwidth occupancy into consideration, and achieves near optimal latency in much less time. Evaluation results validate the effectiveness of the proposed algorithm.

Keywords: Latency, Fast path assignment, Bottleneck link.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.3455737

References:

[1] O. N. Fundation, “Software-defined networking: The new norm for networks,” ONF White Paper, vol. 2, pp. 2–6, 2012.
[2] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: enabling innovation in campus networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 69–74, 2008.
[3] B. Han, V. Gopalakrishnan, L. Ji, and S. Lee, “Network function virtualization: Challenges and opportunities for innovations,” IEEE Communications Magazine, vol. 53, no. 2, pp. 90–97, 2015.
[4] Y. Zhang, N. Beheshti, L. Beliveau, G. Lefebvre, R. Manghirmalani, R. Mishra, R. Patneyt, M. Shirazipour, R. Subrahmaniam, C. Truchan, et al., “Steering: A software-defined networking for inline service chaining,” in Network Protocols (ICNP), 2013 21st IEEE International Conference on, pp. 1–10, IEEE, 2013.
[5] A. Gushchin, A. Walid, and A. Tang, “Scalable routing in sdn-enabled networks with consolidated middleboxes,” in Proceedings of the 2015 ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization, pp. 55–60, ACM, 2015.
[6] A. Hari, T. Lakshman, and G. Wilfong, “Path switching: reduced-state flow handling in sdn using path information,” in Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies, p. 36, ACM, 2015.
[7] A. Gember, P. Prabhu, Z. Ghadiyali, and A. Akella, “Toward software-defined middlebox networking,” in Proceedings of the 11th ACM Workshop on Hot Topics in Networks, pp. 7–12, ACM, 2012.
[8] A. Abujoda and P. Papadimitriou, “Midas: Middlebox discovery and selection for on-path flow processing,” in Communication Systems and Networks (COMSNETS), 2015 7th International Conference on, pp. 1–8, IEEE, 2015.
[9] Z. Liu, X. Wang, W. Pan, B. Yang, X. Hu, and J. Li, “Towards efficient load distribution in big data cloud,” in Computing, Networking and Communications (ICNC), 2015 International Conference on, pp. 117–122, IEEE, 2015.
[10] Z. A. Qazi, C.-C. Tu, L. Chiang, R. Miao, V. Sekar, and M. Yu, “Simple-fying middlebox policy enforcement using sdn,” in ACM SIGCOMM computer communication review, vol. 43, pp. 27–38, ACM, 2013.
[11] W. Ma, J. Beltran, Z. Pan, D. Pan, and N. Pissinou, “Sdn-based traffic aware placement of nfv middleboxes,” IEEE Transactions on Network and Service Management, vol. 14, no. 3, pp. 528–542, 2017.
[12] J. Liu, Y. Li, Y. Zhang, L. Su, and D. Jin, “Improve service chaining performance with optimized middlebox placement,” IEEE Transactions on Services Computing, vol. 10, no. 4, pp. 560–573, 2017.
[13] Y. Kanizo, D. Hay, and I. Keslassy, “Palette: Distributing tables in software-defined networks,” in INFOCOM, 2013 Proceedings IEEE, pp. 545–549, IEEE, 2013.
[14] N. Kang, Z. Liu, J. Rexford, and D. Walker, “Optimizing the one big switch abstraction in software-defined networks,” in Proceedings of the ninth ACM conference on Emerging networking experiments and technologies, pp. 13–24, ACM, 2013.
[15] X. Wang, W. Shi, Y. Xiang, and J. Li, “Efficient network security policy enforcement with policy space analysis,” IEEE/ACM Transactions on Networking, vol. 24, no. 5, pp. 2926–2938, 2016.
[16] S. K. Fayazbakhsh, L. Chiang, V. Sekar, M. Yu, and J. C. Mogul, “Enforcing network-wide policies in the presence of dynamic middlebox actions using flowtags.,” in NSDI, vol. 14, pp. 543–546, 2014.
[17] J. Liu, Y. Li, H. Wang, D. Jin, L. Su, L. Zeng, and T. Vasilakos, “Leveraging software-defined networking for security policy enforcement,” Information Sciences, vol. 327, pp. 288–299, 2016.
[18] Z. Qazi, C.-C. Tu, R. Miao, L. Chiang, V. Sekar, and M. Yu, “Practical and incremental convergence between sdn and middleboxes,” Open Network Summit, Santa Clara, CA, 2013.
[19] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms. MIT press, 2009.
[20] J. McCauley, Z. Liu, A. Panda, T. Koponen, B. Raghavan, J. Rexford, and S. Shenker, “Recursive sdn for carrier networks,” ACM SIGCOMM Computer Communication Review, vol. 46, no. 4, pp. 1–7, 2016.
[21] S. Mitchell, M. OSullivan, and I. Dunning, “Pulp: a linear programming toolkit for python,” The University of Auckland, Auckland, New Zealand, http://www. optimization-online. org/DB FILE/2011/09/3178. pdf, 2011.
[22] A. J. Mason, “Opensolver-an open source add-in to solve linear and integer progammes in excel,” in Operations research proceedings 2011, pp. 401–406, Springer, 2012.
[23] A. Makhorin, “Glpk (gnu linear programming kit),” http://www. gnu. org/s/glpk/glpk. html, 2008.