Abstract
This paper presents a new path computation algorithm for the batch bandwidth constrained routing problem, aiming to reduce the end-to-end running time of a routing algorithm while maintaining the quality of the solution set. The batch bandwidth constrained routing problem arises along with the emergence of the Software Defined Networking (SDN) framework. A network is a bidirectional graph and most bandwidth constrained routing algorithms use Constrained Shortest Path First (CSPF) algorithm to compute a path meeting a certain bandwidth demand. However, available CSPF algorithms’ time complexities have a super-linear relation with the graph size. In fact, we think the entire graph is unnecessary for bandwidth constrained routing algorithms in that a comparatively small subgraph can be enough to cover a feasible path. Based on this thought, we present an algorithm to figure out different subgraphs for different requests of a batch with the help of a graph partitioning process in advance. We achieve an end-to-end time saving of up to a proportion of 69% in our experiments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Apostolopoulos, G., Kama, S., Williams, D., Guerin, R., Orda, A., Przygienda, T.: QoS routing mechanisms and OSPF extensions. RFC 2676, RFC Editor, August 1999
Berde, P., et al.: ONOS: towards an open, distributed SDN OS. In: Proceedings of the Third Workshop on Hot Topics in Software Defined Networking, pp. 1–6. ACM (2014)
Boutaba, R., Szeto, W., Iraqi, Y.: DORA: efficient routing for MPLS traffic engineering. J. Netw. Syst. Manag. 10(3), 309–325 (2002)
Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering. LNCS, vol. 9220, pp. 117–158. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49487-6_4
Hassas Yeganeh, S., Ganjali, Y.: Kandoo: a framework for efficient and scalable offloading of control applications. In: Proceedings of the First Workshop on Hot Topics in Software Defined Networks, pp. 19–24. ACM (2012)
Kar, K., Kodialam, M., Lakshman, T.V.: Minimum interference routing of bandwidth guaranteed tunnels with mpls traffic engineering applications. IEEE J. Sel. Areas Commun. 18(12), 2566–2579 (2000)
Koponen, T., et al.: Onix: a distributed control platform for large-scale production networks. In: OSDI, vol. 10, pp. 1–6 (2010)
Kreutz, D., Ramos, F.M., Verissimo, P.E., Rothenberg, C.E., Azodolmolky, S., Uhlig, S.: Software-defined networking: a comprehensive survey. Proc. IEEE 103(1), 14–76 (2015)
Ma, Q., Steenkiste, P., Zhang, H.: Routing high-bandwidth traffic in max-min fair share networks. In: ACM SIGCOMM Computer Communication Review, vol. 26, pp. 206–217. ACM (1996)
Medina, A., Lakhina, A., Matta, I., Byers, J.: BRITE: an approach to universal topology generation. In: Proceedings of the Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 346–353. IEEE (2001)
Medved, J., Varga, R., Tkacik, A., Gray, K.: OpenDaylight: towards a model-driven SDN controller architecture. In: 2014 IEEE 15th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), pp. 1–6. IEEE (2014)
Nippon Telegraph and Telephone Corporation: RYU Network Operating System (2012). http://osrg.github.com/ryu/. Accessed 11 Apr 2018
Project Floodlight: Floodlight (2012). http://www.projectfloodlight.org/floodlight/. Accessed 11 Apr 2018
Sanders, P., Schulz, C.: Think locally, act globally: highly balanced graph partitioning. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 164–175. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38527-8_16
Tootoonchian, A., Ganjali, Y.: HyperFlow: a distributed control plane for OpenFlow. In: Proceedings of the 2010 Internet Network Management Conference on Research on Enterprise Networking, p. 3 (2010)
Wang, Y., Wang, Z.: Explicit routing algorithms for internet traffic engineering. In: International Conference on Computer Communications and Networks, pp. 582–588. IEEE (1999)
Waxman, B.M.: Routing of multipoint connections. IEEE J. Sel. Areas Commun. 6(9), 1617–1622 (1988)
Acknowledgements
This work was supported by the Ministry of Science and Technology of China (2017YFC0804003), Shenzhen Peacock Plan (Grant No. KQTD2016112514355531), the Natural Science Foundation of China (61672478), the Science and Technology Innovation Committee Foundation of Shenzhen (ZDSYS201703031748284), and the Royal Society Newton Advanced Fellowship (NA150123).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Qian, D., Yang, P., Tang, K. (2018). A Fast Heuristic Path Computation Algorithm for the Batch Bandwidth Constrained Routing Problem in SDN. In: Geng, X., Kang, BH. (eds) PRICAI 2018: Trends in Artificial Intelligence. PRICAI 2018. Lecture Notes in Computer Science(), vol 11012. Springer, Cham. https://doi.org/10.1007/978-3-319-97304-3_38
Download citation
DOI: https://doi.org/10.1007/978-3-319-97304-3_38
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-97303-6
Online ISBN: 978-3-319-97304-3
eBook Packages: Computer ScienceComputer Science (R0)