Top

Theory of Computing Systems

Published in:

23-04-2018

On-Line Path Computation and Function Placement in SDNs

Authors: Guy Even, Moti Medina, Boaz Patt-Shamir

Published in: Theory of Computing Systems | Issue 2/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider service requests that arrive in an online fashion in Software-Defined Networks (SDNs) with network function virtualization (NFV). Each request is a flow with a high-level specification of routing and processing (by network functions) requirements. Each network function can be performed by a specified subset of servers in the system. The algorithm needs to decide whether to reject the request, or accept it and with a specific routing and processing assignment, under given capacity constraints (solving the path computation and function placement problems). Each served request is assumed to “pay” a pre-specified benefit and the goal is to maximize the total benefit accrued. In this paper we first formalize the problem, and propose a new service model that allows us to cope with requests with unknown duration without preemption. The new service model augments the traditional accept/reject schemes with a new possible response of “stand by.” We also present a new expressive model to describe requests abstractly using a “plan” represented by a directed graph. Our algorithmic result is an online algorithm for path computation and function placement that guarantees, in each time step, throughput of at least a logarithmic fraction of a (very permissive) upper bound on the maximal possible benefit.

previous article Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision

next article Snap-Stabilizing Tasks in Anonymous Networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Typically, \(k\) is a small constant. In particular, the number of processing stages \((k)\) does not grow as a function of the size \((n)\) of the network.

Our pr-graphs are similar to Merlin’s regular expressions [16], but are more expressive and, in our humble opinion, are more natural to design.

The request model can be extended to deal with nonuniform demands. Namely, a possibly different amount of resource is consumed by the request \(r_{j}\) from each pr-graph element. Formally, \(d_{j}: X_{j}\cup Y_{j} \rightarrow {\mathbb {N}}\) specifies the demand of request \(r_{j}\) from each edge and node of the the pr-graph. This extension can capture varying bandwidth due to compression, asymmetric servers whose processing ability depends on the task at hand, etc.

In Merlin, the input may also contain a “policing” function of capping the maximal bandwidth of a connection. We focus on resource allocation only. Policing may be enforced by an orthogonal entity.

One could also allow for empty events \(\sigma _{j}\) to deal with the case that there is no new request and no active requests wishes to depart.

In case no departure event of a request has occurred, then the corresponding request stays forever.

The actual weight function that we use in our context is explained in Section 4, specifically in (2).

A shortest-path algorithm suffices for the implementation of Step 2, that is, if the shortest path is light enough then a single path is required (see Line 31 for the invocation of the oracle), otherwise, if it is not light enough then P_j = ∅.

We assume that \(b_{\max }\) is known in advance.

A fractional allocation may serve a request partially, split the assignment among multiple allocations, and change the allocation over time. Formally, a fractional allocation assigns to each request \(r_{j}\) in each time step \(t\) a non-negative linear combination of valid allocations \(\sum _{i}\alpha _{j,t,i} \cdot p_{j,i}\), where (for every \(j,t,i\)) \(\alpha _{j,t,i}\geq 0\), \(p_{j,i}\in {\varGamma }_{j}\), and \(\sum _{i} \alpha _{j,t,i} \leq 1\). Capacity constraints are satisfied in the sense that \(\sum _{j} \sum _{i: e\in p_{j,i}} d_{j}\cdot \alpha _{j,t,i} \leq c_{e}\). The benefit obtained by a fractional allocation is \(\sum _{t} \sum _{j} \sum _{i} b_{j}\cdot \alpha _{j,t,i}\).

This benefit is paid only once, if a request is accepted, as opposed to the benefit per time step paid by SDN requests.

In fact it is proven in [2, Lemmas 4.4, 4.5], for the case of (simple) routing (see first example after Definition 3), that if \(\frac {\max _{j} d_{j}}{\min _{z}c_{z}} \leq \frac {1}{\gamma }\), then the competitive ratio is \({\varOmega }(n^{1/\gamma })\).

Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM) 44(3), 486–504 (1997)MathSciNetCrossRefMATH

Awerbuch, B., Azar, Y., Plotkin, S.: Throughput-competitive on-line routing. In: Proc.34th IEEE Annual Symp. on Foundations of Computer Science, pp. 32–40 (1993)

Awerbuch, B., Azar, Y., Plotkin, S., Waarts, O.: Competitive routing of virtual circuits with unknown duration. J. Comput. Syst. Sci. 62(3), 385–397 (2001)MathSciNetCrossRefMATH

Buchbinder, N., Naor, J.S.: Improved bounds for online routing and packing via a primal-dual approach. In: 47th Ann. IEEE Symp.on Foundations of Computer Science, pp. 293–304 (2006)

Buchbinder, N., Naor, J.S.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270–286 (2009)MathSciNetCrossRefMATH

Cohen, R., Lewin-Eytan, L., Naor, J. S., Raz, D.: Near optimal placement of virtual network functions. In: 2015 IEEE Conference on Computer Communications (INFOCOM), pp. 1346–1354 (2015)

Even, G., Medina, M.: Online multi-commodity flow with high demands. In: Proc. 10th Int.Workshop on Approximation and Online Algorithms (WAOA), pp 16–29 (2012)

Even, G, Medina, M., Patt-Shamir, B.: On-line path computation and function placement in sdns. In: Bonakdarpour, B., Petit, F. (eds.) Stabilization, Safety, and Security of Distributed Systems - 18th International Symposium, SSS 2016, Lyon, France, November 7-10, 2016, Proceedings, volume 10083 of Lecture Notes in Computer Science, pp. 131–147 (2016)

Even, G., Medina, M., Schaffrath, G., Schmid, S.: Competitive and deterministic embeddings of virtual networks. Theor. Comput. Sci. 496(0), 184–194 (2013). Distributed Computing and Networking (ICDCN 2012)MathSciNetCrossRefMATH

10.

Even, G., Rost, M., Schmid, S.: An approximation algorithm for path computation and function placement in sdns. arXiv:1603.09158/ 2016 Appeared in SIROCCO (2016)

11.

Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation), 3rd edn. Pearson, Boston (2006)

12.

Kleinberg, J.M.: Approximation algorithms for disjoint paths problems. PhD thesis Massachusetts Institute of Technology (1996)

13.

Kreutz, D., Ramos, F., Esteves Verissimo, P., Esteve Rothenberg, C., Azodolmolky, S., Uhlig, S.: Software-defined networking: A comprehensive survey. Proc. IEEE 103(1), 14–76 (2015)CrossRef

14.

Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)MathSciNetCrossRef

15.

Soulé, R., Basu, S., Kleinberg, R., Sirer, E.G., Foster, N.: Managing the network with merlin. In: Proc. 12th ACM Workshop on Hot Topics in Networks. ACM, p. 24 (2013)

16.

Soulé, R., Basu, S., Marandi, P.J., Pedone, F., Kleinberg, R., Sirer, E.G., Foster, N.: Merlin: A language for provisioning network resources. In: Proc. 10th ACM Int. Conf. on emerging Networking Experiments and Technologies. ACM, pp. 213–226 (2014)

Title: On-Line Path Computation and Function Placement in SDNs
Authors: Guy Even
Moti Medina
Boaz Patt-Shamir
Publication date: 23-04-2018
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 2/2019
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9863-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2019

Packet Efficient Implementation of the Omega Failure Detector

Wait-free Solvability of Colorless Tasks in Anonymous Shared-memory Model

Self-Stabilizing Metric Graphs

Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision

Synchronous Gathering without Multiplicity Detection: a Certified Algorithm

Editor’s Note: Special Issue on Stabilization, Safety, and Security of Distributed Systems

Premium Partner