TY - JOUR

T1 - Optimum Transmission Delay for Function Computation in NFV-Based Networks

T2 - The Role of Network Coding and Redundant Computing

AU - Tahmasebi, Behrooz

AU - Maddah-Ali, Mohammad Ali

AU - Parsaeefard, Saeedeh

AU - Khalaj, Babak Hossein

N1 - Publisher Copyright:
© 2018 IEEE.

PY - 2018/10

Y1 - 2018/10

N2 - In this paper, we study the problem of delay minimization in network function virtualization-based networks. In such systems, the ultimate goal of any request is to compute a sequence of functions in the network, where each function can be computed at only a specific subset of network nodes. In conventional approaches, for each function, we choose one node from the corresponding subset of the nodes to compute that function. In contrast, in this paper, we allow each function to be computed in more than one node, redundantly in parallel, to respond to a given request. We argue that such redundancy in computation not only improves the reliability of the network but also, perhaps surprisingly, reduces the overall transmission delay. In particular, we establish that by judiciously choosing the subset of nodes which compute each function, in conjunction with a linear network coding scheme to deliver the result of each computation, we can characterize and achieve the optimal end-to-end transmission delay. In addition, we show that using such technique, it is possible to significantly reduce the transmission delay as compared to the conventional approaches. In fact, in some scenarios, such reduction can even scale with the size of the network, where by increasing the number of nodes that can compute the given function in parallel by a multiplicative factor, the end-to-end delay will also decrease by the same factor. Moreover, we show that while finding the subset of nodes for each computation, in general, is a complex integer program, approximation algorithms can be proposed to reduce the computational complexity. In fact, for the case where the number of computing nodes for a given function is upper bounded by a constant, a dynamic programming scheme can be proposed to find the optimum subsets in polynomial times. Our numerical simulations confirm the achieved gain in performance in comparison with conventional approaches.

AB - In this paper, we study the problem of delay minimization in network function virtualization-based networks. In such systems, the ultimate goal of any request is to compute a sequence of functions in the network, where each function can be computed at only a specific subset of network nodes. In conventional approaches, for each function, we choose one node from the corresponding subset of the nodes to compute that function. In contrast, in this paper, we allow each function to be computed in more than one node, redundantly in parallel, to respond to a given request. We argue that such redundancy in computation not only improves the reliability of the network but also, perhaps surprisingly, reduces the overall transmission delay. In particular, we establish that by judiciously choosing the subset of nodes which compute each function, in conjunction with a linear network coding scheme to deliver the result of each computation, we can characterize and achieve the optimal end-to-end transmission delay. In addition, we show that using such technique, it is possible to significantly reduce the transmission delay as compared to the conventional approaches. In fact, in some scenarios, such reduction can even scale with the size of the network, where by increasing the number of nodes that can compute the given function in parallel by a multiplicative factor, the end-to-end delay will also decrease by the same factor. Moreover, we show that while finding the subset of nodes for each computation, in general, is a complex integer program, approximation algorithms can be proposed to reduce the computational complexity. In fact, for the case where the number of computing nodes for a given function is upper bounded by a constant, a dynamic programming scheme can be proposed to find the optimum subsets in polynomial times. Our numerical simulations confirm the achieved gain in performance in comparison with conventional approaches.

KW - Delay-computation trade-off

KW - network coding

KW - network function virtualization (NFV)

KW - network optimization

KW - redundancy

KW - reliability

UR - http://www.scopus.com/inward/record.url?scp=85053341720&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85053341720&partnerID=8YFLogxK

U2 - 10.1109/JSAC.2018.2869952

DO - 10.1109/JSAC.2018.2869952

M3 - Article

AN - SCOPUS:85053341720

SN - 0733-8716

VL - 36

SP - 2233

EP - 2245

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

IS - 10

M1 - 8463556

ER -