For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Reducing Dense Virtual Networks for Fast Embedding
Toru MANO Takeru INOUE Kimihiro MIZUTANI Osamu AKASHI
IEICE TRANSACTIONS on Communications
Publication Date: 2020/04/01
Online ISSN: 1745-1345
Type of Manuscript: Special Section PAPER (Special Section on Network Resource Control and Management Technologies for Sustainable Social Information Infrastructure)
network virtualization, virtual network embedding, heuristics,
Full Text: PDF(1.9MB)>>
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.