An Evaluation Methodology for Virtual Network Embedding
- The increasing scale and complexity of computer networks imposes a need for highly flexible management mechanisms. The concept of network virtualization promises to provide this flexibility. Multiple arbitrary virtual networks can be constructed on top of a single substrate network. This allows network operators and service providers to tailor their network topologies to the specific needs of any offered service. However, the assignment of resources proves to be a problem. Each newly defined virtual network must be realized by assigning appropriate physical resources. For a given set of virtual networks, two questions arise: Can all virtual networks be accommodated in the given substrate network? And how should the respective resources be assigned? The underlying problem is commonly known as the Virtual Network Embedding problem. A multitude of algorithms has already been proposed, aiming to provide solutions to that problem under various constraints. For the evaluation of these algorithms typically an empirical approach isThe increasing scale and complexity of computer networks imposes a need for highly flexible management mechanisms. The concept of network virtualization promises to provide this flexibility. Multiple arbitrary virtual networks can be constructed on top of a single substrate network. This allows network operators and service providers to tailor their network topologies to the specific needs of any offered service. However, the assignment of resources proves to be a problem. Each newly defined virtual network must be realized by assigning appropriate physical resources. For a given set of virtual networks, two questions arise: Can all virtual networks be accommodated in the given substrate network? And how should the respective resources be assigned? The underlying problem is commonly known as the Virtual Network Embedding problem. A multitude of algorithms has already been proposed, aiming to provide solutions to that problem under various constraints. For the evaluation of these algorithms typically an empirical approach is adopted, using artificially created random problem instances. However, due to complex effects of random problem generation the obtained results can be hard to interpret correctly. A structured evaluation methodology that can avoid these effects is currently missing. This thesis aims to fill that gap. Based on a thorough understanding of the problem itself, the effects of random problem generation are highlighted. A new simulation architecture is defined, increasing the flexibility for experimentation with embedding algorithms. A novel way of generating embedding problems is presented which migitates the effects of conventional problem generation approaches. An evaluation using these newly defined concepts demonstrates how new insights on algorithm behavior can be gained. The proposed concepts support experimenters in obtaining more precise and tangible evaluation data for embedding algorithms.…
Author: | Andreas Fischer |
---|---|
URN: | urn:nbn:de:bvb:739-opus4-4793 |
Advisor: | Hermann de Meer, Wolfgang Kellerer |
Document Type: | Doctoral Thesis |
Language: | English |
Year of Completion: | 2017 |
Date of Publication (online): | 2017/06/01 |
Date of first Publication: | 2017/06/01 |
Publishing Institution: | Universität Passau |
Granting Institution: | Universität Passau, Fakultät für Informatik und Mathematik |
Date of final exam: | 2017/05/29 |
Release Date: | 2017/06/01 |
Tag: | Algorithmus; Kombinatorische Einbettung; Virtualisierung; Virtuelles Netz Empirical Evaluation; Experimental Algorithmics; Network Virtualization; Virtual Network Embedding |
GND Keyword: | Virtuelles Netz |
Page Number: | XVII, 179 S. |
Institutes: | Fakultät für Informatik und Mathematik |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
open_access (DINI-Set): | open_access |
Licence (German): | CC by: Creative Commons - Namensnennung |