research-article

Traffic steering in software defined networks: planning and online routing

Authors:

Murali Kodialam,

T. V. LakshmanAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 44, Issue 4

https://doi.org/10.1145/2740070.2627574

Published: 18 August 2014 Publication History

Abstract

Middleboxes have become ubiquitous in data center as well as wide area networks. Simple routing of flows from ingress to egress along shortest paths has been replaced by policy aware paths that have to pass through the required set of middleboxes. The complex routing is one of the major impetus for the Software Defined Networking (SDN) paradigm. In this paper, we consider both offline planning and online routing problems in SDN framework. The offline planning problem is one where aggregate demands are specified and the objective is to determine whether there is enough capacity in the network to handle the demands. We develop a fast FPTAS for the problem based on segmentation and lazy dual update. In the online routing problem, flow requests are given one at a time and the objective is to steer the flows to maximize the total amount of traffic accepted over time. We develop a log-competitive algorithm based on time-dependent duals.

References

[1]

"Software-defined networking: the new norm for networks," Open Networking Foundation, 2012.

[2]

B. Anwer, T. Benson, N. Feamster, D. Levin, and J. Rexford, "A Slick control plane for network middleboxes," In Open Networking Summit, 2013.

Digital Library

[3]

N. Garg, and J. Konemann, "Faster and simpler algorithms for multicommodity flow and other fractional packing problems," SIAM Journal on Computing, 37(2):630--652, 2007.

Digital Library

[4]

S.K. Fayazbakhsh, V. Sekar, M. Yu, and J. Mogul, "FlowTags: enforcing network-wide policies in the presence of dynamic middlebox actions," In Proc. HotSDN, 2013.

Digital Library

[5]

A. Gember, R. Grandl, A. Anand, T. Benson, and A. Akella, "Stratos: virtual middleboxes as first-class entities," Technical Report TR1771, University of Wisconsin-Madison, 2012.

[6]

A. Gember, A. Krishnamurthy, S.S. John, R. Grandl, X. Gao, A. Anand, T. Benson, A. Akella, and V. Sekar, "Stratos: a network-aware orchestration layer for middleboxes in the cloud," arXiv:1305.0209v1, May, 2013.

[7]

N. Buchbinder, and J. Naor, "The design of competitive online algorithms via a primal-dual approach," Foundations and Trends in Theoretical Computer Science, 3(2--3):93--263, 2007.

Digital Library

[8]

Z. Qazi, C. Tu, L. Chiang, R. Miao, V. Sekar, and M. Yu, "SIMPLE-fying middlebox policy enforcement using SDN," In Proc. of ACM SIGCOMM, 2013.

Digital Library

[9]

Mininet, http://yuba.stanford.edu/foswiki/bin/view/OpenFlow/Mininet.

[10]

M. Casado, M. J. Freedman, J. Pettit, J. Luo, N. McKeown, and S. Shenker, "Ethane: taking control of the enterprise," In Proc. of ACM SIGCOMM, 37(4):1--12, 2007.

Digital Library

[11]

X. Meng, V. Pappas, and L. Zhang, "Improving the scalability of data center networkswith traffic-aware virtual machine placement," In Proc. of IEEE INFOCOM, 2010.

Digital Library

[12]

X. Jin, L. E. Li, L. Vanbever, and J. Rexford, "SoftCell: taking control of cellular core networks," In TR-950--13, Princeton University, 2013.

Digital Library

[13]

L. E. Li, V. Liaghat, H. Zhao, MT. Hajiaghayi, D. Li, G. Wilfong, Y.R. Yang, and C. Guo, "PACE: policy-aware application cloud embedding," In Proc. IEEE INFOCOM, 2013.

[14]

R. Soule, S. Basu, R. Kleinberg, E.G. Sirer, and N. Foster "Managing the network with Merlin," In Proc. HotNets-XII, 2013.

Digital Library

[15]

V. Sekar, N. Egi, S. Ratnasamy, M. K. Reiter, and G. Shi, "Design and implementation of a consolidated middlebox architecture," In Proc. NSDI, 2012.

Digital Library

[16]

J. Sherry, "Making Middleboxes Someone Else's Problem: Network Processing as a Cloud Service," In Proc. Sigcomm, 2012.

Digital Library

Cited By

Yuan CPeng TZhang KShu HWang W(2023)Dynamic Mapping Service Function Chains in a Logical Segmented LEO Constellation2023 IEEE 98th Vehicular Technology Conference (VTC2023-Fall)10.1109/VTC2023-Fall60731.2023.10333353(1-6)Online publication date: 10-Oct-2023
https://doi.org/10.1109/VTC2023-Fall60731.2023.10333353
Abbasi MRezaei HMenon VQi LKhosravi M(2021)Enhancing the Performance of Flow Classification in SDN-Based Intelligent Vehicular NetworksIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.301404422:7(4141-4150)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1109/TITS.2020.3014044
Paganelli FCappanera PCuffaro G(2021)Tenant-defined service function chaining in a multi-site network sliceFuture Generation Computer Systems10.1016/j.future.2021.03.002121(1-18)Online publication date: Aug-2021
https://doi.org/10.1016/j.future.2021.03.002
Show More Cited By

Index Terms

Traffic steering in software defined networks: planning and online routing
1. Networks
  1. Network types
    1. Packet-switching networks

Recommendations

Traffic steering in software defined networks: planning and online routing
DCC '14: Proceedings of the 2014 ACM SIGCOMM workshop on Distributed cloud computing

Middleboxes have become ubiquitous in data center as well as wide area networks. Simple routing of flows from ingress to egress along shortest paths has been replaced by policy aware paths that have to pass through the required set of middleboxes. The ...
An Analytic-Deterministic Model for Traffic Prioritization in Software Defined Networks with Network Calculus
SBRC '15: Proceedings of the 2015 XXXIII Brazilian Symposium on Computer Networks and Distributed Systems

Different classes of packets traffic require specific performance of network resources in terms of Quality of Service metrics. The models proposed to ensure end-to-end QoS have not been well implemented due to their complexity and lack of scalability. ...
Jointly optimized QoS-aware virtualization and routing in software defined networks

Software Defined Networks (SDNs) have been recognized as the next-generation networking paradigm that decouples the network control plane from the data forwarding plane. A logically centralized controller is responsible for all the control decisions and ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 44, Issue 4

SIGCOMM'14

October 2014

672 pages

ISSN:0146-4833

DOI:10.1145/2740070

Editors:
Konstantina Papagiannaki
Telefonica Research, Barcelona, Spain
,
Katerina Argyraki
EPFL, Switzerland
,
Hitesh Ballani
Microsoft Research Cambridge, UK
,
Fabián Bustamante
Northwestern University, USA
,
Joseph Camp
SMU, USA
,
Augustin Chaintreau
Columbia University, USA
,
Phillipa Gill
Stony Brook University, USA
,
Marco Mellia
Politecnico di Torino, Italy
,
Bhaskaran Raman
IIT Bombay, India
,
Joel Sommers
Colgate University, USA
,
Aline Carneiro Viana
INRIA, France

Issue’s Table of Contents

DCC '14: Proceedings of the 2014 ACM SIGCOMM workshop on Distributed cloud computing
August 2014
92 pages
ISBN:9781450329927
DOI:10.1145/2627566
Program Chairs:
Stefan Schmid
T-Labs & TU Berlin, Germany
,
James Kempf
Ericsson, USA
,
Rick McGeer
SAP & US Ignite, USA
,
Yvonne Coady
University of Victoria, Canada

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 August 2014

Published in SIGCOMM-CCR Volume 44, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

78
Total Citations
View Citations
1,596
Total Downloads

Downloads (Last 12 months)117
Downloads (Last 6 weeks)12

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yuan CPeng TZhang KShu HWang W(2023)Dynamic Mapping Service Function Chains in a Logical Segmented LEO Constellation2023 IEEE 98th Vehicular Technology Conference (VTC2023-Fall)10.1109/VTC2023-Fall60731.2023.10333353(1-6)Online publication date: 10-Oct-2023
https://doi.org/10.1109/VTC2023-Fall60731.2023.10333353
Abbasi MRezaei HMenon VQi LKhosravi M(2021)Enhancing the Performance of Flow Classification in SDN-Based Intelligent Vehicular NetworksIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.301404422:7(4141-4150)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1109/TITS.2020.3014044
Paganelli FCappanera PCuffaro G(2021)Tenant-defined service function chaining in a multi-site network sliceFuture Generation Computer Systems10.1016/j.future.2021.03.002121(1-18)Online publication date: Aug-2021
https://doi.org/10.1016/j.future.2021.03.002
Poularakis KIosifidis GSmaragdakis GTassiulas L(2019)Optimizing Gradual SDN Upgrades in ISP NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2018.289024827:1(288-301)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TNET.2018.2890248
Sahay RMeng WJensen C(2019)The application of Software Defined Networking on securing computer networksJournal of Network and Computer Applications10.1016/j.jnca.2019.01.019131:C(89-108)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1016/j.jnca.2019.01.019
Liu XZhao SWang XZhou C(2024)LPulse: An efficient algorithm for service function chain placement and routing with delay guaranteeComputer Networks10.1016/j.comnet.2024.110728253(110728)Online publication date: Nov-2024
https://doi.org/10.1016/j.comnet.2024.110728
Khemili WSaidi MHajlaoui JOmri MChen K(2024)Parallel bi-state deep reinforcement learning approach for SFC placements and deploymentsNeural Computing and Applications10.1007/s00521-024-10486-7Online publication date: 5-Dec-2024
https://doi.org/10.1007/s00521-024-10486-7
Tran Huy HTam NBinh HVinh L(2024)Two-stage metaheuristic for reliable and balanced network function virtualization-enabled networksSoft Computing10.1007/s00500-024-09630-128:13-14(8259-8277)Online publication date: 4-Jul-2024
https://doi.org/10.1007/s00500-024-09630-1
Yuan CPeng TZhang KShu HWang W(2023)Dynamic Mapping Service Function Chains in a Logical Segmented LEO Constellation2023 IEEE 98th Vehicular Technology Conference (VTC2023-Fall)10.1109/VTC2023-Fall60731.2023.10333353(1-6)Online publication date: 10-Oct-2023
https://doi.org/10.1109/VTC2023-Fall60731.2023.10333353
Nguyen DLien YLiu BChu SNguyen T(2023)Virtual Network Function Placement for Serving Weighted Services in NFV-Enabled NetworksIEEE Systems Journal10.1109/JSYST.2023.325777617:4(5648-5659)Online publication date: Dec-2023
https://doi.org/10.1109/JSYST.2023.3257776
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents