Reducing Dense Virtual Networks for Fast Embedding

Toru MANO; Takeru INOUE; Kimihiro MIZUTANI; Osamu AKASHI

doi:10.1587/transcom.2019NRP0004

Open Access
Reducing Dense Virtual Networks for Fast Embedding

Toru MANO, Takeru INOUE, Kimihiro MIZUTANI, Osamu AKASHI

Full Text Views

127

Share
Cite this

Free PDF (1.9MB)

Summary :

Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E|=O(|V|²)) based on a traffic matrix, the time complexity is actually O(|E|³=|V|⁶). If we were allowed to reduce this dense network to a sparse one before embedding, the time complexity could be decreased to O(|V|³); the time saving would be of the order of a million times for |V|=100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction operations and analyze them with several interesting theorems. The analysis indicates that an exponential drop in embedding time can be achieved with a linear increase in embedding cost. A rigorous numerical evaluation justifies the desirability of the trade-off.

Publication: IEICE TRANSACTIONS on Communications Vol.E103-B No.4 pp.347-362

Publication Date: 2020/04/01

Publicized: 2019/10/25

Online ISSN: 1745-1345

DOI: 10.1587/transcom.2019NRP0004

Type of Manuscript: Special Section PAPER (Special Section on Network Resource Control and Management Technologies for Sustainable Social Information Infrastructure)

Category

Authors

Toru MANO
  NTT Network Innovation Laboratories
Takeru INOUE
  NTT Network Innovation Laboratories
Kimihiro MIZUTANI
  Kindai University
Osamu AKASHI
  National Institute of Informatics

Keyword

network virtualization, virtual network embedding, heuristics

Cite this

Copy

Toru MANO, Takeru INOUE, Kimihiro MIZUTANI, Osamu AKASHI, "Reducing Dense Virtual Networks for Fast Embedding" in IEICE TRANSACTIONS on Communications, vol. E103-B, no. 4, pp. 347-362, April 2020, doi: 10.1587/transcom.2019NRP0004.
Abstract: Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E|=O(|V|²)) based on a traffic matrix, the time complexity is actually O(|E|³=|V|⁶). If we were allowed to reduce this dense network to a sparse one before embedding, the time complexity could be decreased to O(|V|³); the time saving would be of the order of a million times for |V|=100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction operations and analyze them with several interesting theorems. The analysis indicates that an exponential drop in embedding time can be achieved with a linear increase in embedding cost. A rigorous numerical evaluation justifies the desirability of the trade-off.
URL: https://globals.ieice.org/en_transactions/communications/10.1587/transcom.2019NRP0004/_p

Copy

@ARTICLE{e103-b_4_347,
author={Toru MANO, Takeru INOUE, Kimihiro MIZUTANI, Osamu AKASHI, },
journal={IEICE TRANSACTIONS on Communications},
title={Reducing Dense Virtual Networks for Fast Embedding},
year={2020},
volume={E103-B},
number={4},
pages={347-362},
abstract={Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E|=O(|V|²)) based on a traffic matrix, the time complexity is actually O(|E|³=|V|⁶). If we were allowed to reduce this dense network to a sparse one before embedding, the time complexity could be decreased to O(|V|³); the time saving would be of the order of a million times for |V|=100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction operations and analyze them with several interesting theorems. The analysis indicates that an exponential drop in embedding time can be achieved with a linear increase in embedding cost. A rigorous numerical evaluation justifies the desirability of the trade-off.},
keywords={},
doi={10.1587/transcom.2019NRP0004},
ISSN={1745-1345},
month={April},}

Copy

TY - JOUR
TI - Reducing Dense Virtual Networks for Fast Embedding
T2 - IEICE TRANSACTIONS on Communications
SP - 347
EP - 362
AU - Toru MANO
AU - Takeru INOUE
AU - Kimihiro MIZUTANI
AU - Osamu AKASHI
PY - 2020
DO - 10.1587/transcom.2019NRP0004
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E103-B
IS - 4
JA - IEICE TRANSACTIONS on Communications
Y1 - April 2020
AB - Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E|=O(|V|²)) based on a traffic matrix, the time complexity is actually O(|E|³=|V|⁶). If we were allowed to reduce this dense network to a sparse one before embedding, the time complexity could be decreased to O(|V|³); the time saving would be of the order of a million times for |V|=100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction operations and analyze them with several interesting theorems. The analysis indicates that an exponential drop in embedding time can be achieved with a linear increase in embedding cost. A rigorous numerical evaluation justifies the desirability of the trade-off.
ER -