Optimizing Network Latency with Fast Path Assignment for Incoming Flows

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.

Authors:

• Qing Lyu
• Hang Zhu

Keywords:

• Latency
• Fast path assignment
• Bottleneck link.

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.