Optimum Transmission Delay for Function Computation in NFV-based Networks: the role of Network Coding and Redundant Computing

Behrooz Tahmasebi, Mohammad Ali Maddah-Ali, Saeedeh Parsaeefard, Babak Hossein Khalaj

Introduction

In the quest for lower latency in modern data networks, researchers often look for ways to streamline processes and eliminate waste. However, a recent study explores a counter-intuitive approach: speeding up networks by doing the same work multiple times. By combining redundant computing with network coding, the authors demonstrate a significant reduction in end-to-end transmission delay within Network Function Virtualization (NFV) environments.

The Bottleneck in Service Function Chains

Modern 5G and cloud infrastructures rely heavily on Network Function Virtualization (NFV). Instead of dedicated hardware, Virtual Network Functions (VNFs)—like firewalls or load balancers—run as software on general-purpose servers.

User requests typically traverse a Service Function Chain (SFC), a sequence of functions (e.g., $f_1 \to f_2 \to f_3$) that must be processed in order. The traditional approach is to assign a single optimal node to each function in the chain. This creates a performance bottleneck: the entire chain's speed is constrained by the single best path between these specific nodes. If a chosen node resides in a congested network segment, transmission delay—the time taken to move data between nodes—increases dramatically.

General model of a Service Function Chain (SFC) across multiple rounds of computation and transmission.

Methodology: Redundancy and Coding

To overcome these limitations, the authors propose moving away from the "one node per function" paradigm. Their framework rests on two pillars:

  1. Redundant Computing: For each step in the SFC, multiple nodes are tasked with computing the same function simultaneously.
  2. Network Coding: Rather than simple routing, the network employs linear network coding. This allows results from redundant nodes to be combined and delivered to the next stage of the chain more efficiently, effectively utilizing more of the network's available capacity.

The problem of selecting the optimal set of nodes is formulated as a min-cut/max-flow optimization. Since finding the absolute best subset is computationally intensive (an integer programming problem), the authors developed two practical algorithms:

  • Greedy Algorithm: An iterative approach that starts with one node per function and adds the "best" additional nodes until delay gains plateau.
  • $\alpha$-optimal Algorithm: A dynamic programming solution that finds the mathematically optimal configuration given a fixed limit ($\alpha$) on the number of redundant nodes per function.

Key Insights: The "More is Faster" Paradox

The study reveals several surprising insights. Most notably, adding redundant computation tasks—which usually increases network load—actually speeds up delivery. This is because redundancy unlocks more paths through the network graph, allowing data to flow through multiple segments simultaneously. In certain topologies, increasing the redundancy factor by $\alpha$ can decrease transmission delay by that same factor.

Furthermore, this approach provides inherent reliability. The redundant nature of the computation makes the network more resilient to individual node failures or "stragglers." The authors emphasize that traditional routing alone cannot achieve these gains; network coding is essential to fully exploit the capacity provided by redundant nodes.

Results and Future Directions

Simulations on a 100-node network showed that the redundant method could reduce normalized delay from approximately 12 units to under 4 units with a redundancy factor of 10. The Greedy algorithm proved highly effective, performing nearly as well as the more complex optimal solution. These gains remained robust even in sparse or heterogeneous networks.

While promising, the model currently assumes synchronized servers and identical processing times. Future research will need to address "straggler" nodes, multi-commodity flow analysis for simultaneous requests, and the joint optimization of energy costs versus delay gains, as redundant computing naturally increases CPU and power consumption.

Summary updated

Abstract

In this paper, we study the problem of delay minimization in NFV-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 work, 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 would also, perhaps surprisingly, reduce 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, we can significantly reduce the transmission delay as compared to the conventional approach. In some scenarios, such reduction can even scale with the size of the network. More precisely, 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.
BibTeX
@article{tahmasebi2018optimum,
  author = {Behrooz Tahmasebi and Mohammad Ali Maddah-Ali and Saeedeh Parsaeefard and Babak Hossein Khalaj},
  title = {{Optimum Transmission Delay for Function Computation in NFV-based Networks: the role of Network Coding and Redundant Computing}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2018},
  doi = {10.1109/jsac.2018.2869952},
}
Figure