TU Berlin

Internet Network ArchitecturesStefan Schmid's Publications

Page Content

to Navigation

Stefan Schmid's Publications

Competitive and Deterministic Embeddings of Virtual Networks
Citation key EMSS-CDEVN-11
Author Even, Guy and Medina, Moti and Schaffrath, Gregor and Schmid, Stefan
Year 2011
Month January
Note ID arXiv:1101.5221 [cs.NI]
Institution arXiv
Abstract Network virtualization is a paradigm that allows for flexible and efficient allocation of the resources among multiple virtual networks (VNets). In this paper we deal with the problem of embedding dynamically arriving VNet requests. We describe a generic algorithm for the online VNet embedding problem and analyze its competitive ratio. This means that we compare the benefit accumulated by the algorithm with the benefit of an optimal offline algorithm. We prove that the competitive ratio of our online algorithm is, loosely speaking, logarithmic in the sum of the resources. Our algorithm is generic in the sense that it supports multiple traffic models, multiple routing models, and allows for nonuniform benefits and durations of VNet requests. Concretely, the routing models considered in this paper include: multipaths, single paths, and tree routing. For modeling traffic, we study the customer-pipe model, the hose model, and a new traffic model, called aggregate ingress model, that is well suited for modeling multicasts and multi-party video conferences.
Bibtex Type of Publication Technical Report
Link to publication Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe