Reducing Dense Virtual Networks for Fast Embedding

Toru MANO
Takeru INOUE
Kimihiro MIZUTANI
Osamu AKASHI

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: 
Keyword: 
network virtualization,  virtual network embedding,  heuristics,  

Full Text: FreePDF(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|2)) based on a traffic matrix, the time complexity is actually O(|E|3=|V|6). If we were allowed to reduce this dense network to a sparse one before embedding, the time complexity could be decreased to O(|V|3); 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.