Congestion Minimization for Service Chain Routing Problems With Path Length Considerations

Network function virtualization (NFV), with its perceived potential to accelerate service deployment and to introduce flexibility in service provisioning, has drawn a growing interest from industry and academia alike over the past few years. One of the key challenges in realizing NFV is the service...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2020-12, Vol.28 (6), p.2643-2656
Main Authors: Gao, Lingnan, Rouskas, George N.
Format: Article
Language:English
Subjects:
Algorithms
Chains
Heuristic algorithms
IEEE transactions
Minimization
Network function virtualization
Network topologies
NFV orchestration
Noise measurement
online algorithm
Optimization
Provisioning
resource allocation
Resource management
Routing
virtual network functions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Network function virtualization (NFV), with its perceived potential to accelerate service deployment and to introduce flexibility in service provisioning, has drawn a growing interest from industry and academia alike over the past few years. One of the key challenges in realizing NFV is the service chain routing problem, whereby traffic must be routed so as to traverse the various components of a network service that have been mapped onto the underlying network. In this work, we consider the online service chain routing problem. We route the service chain with the goal of jointly minimizing the maximum network congestion and the number of hops from the source to the destination. To this end, we present a simple yet effective online algorithm in which the routing decision is irrevocably made without prior knowledge of future requests. We prove that our algorithm is O(\log m) -competitive in terms of congestion minimization, where m is the number of edges of the underlying network topology, and we show that this ratio is asymptotically optimal.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2020.3017792