Online network slicing in a multi-domain environment requires considering trust constraints and latency simultaneously. The analysis shows how the Path–Link model reduces computation time without critical quality loss.
The problem arises at the intersection of two constraints: multi-domain orchestration and trust between operators. In classical VNF placement, the system optimizes the placement of functions and routing but assumes a single administrative domain. In reality, the slice passes through multiple operators, and not all of them trust each other. This introduces strict limitations on acceptable traffic paths and VNF placement, which directly affects blocking probability and latency. Additionally, the online nature complicates the task: decisions are made without knowledge of future requests.
The basic model is formalized as a Node–Link (NL) integer linear program. It simultaneously addresses two tasks: where to place VNFs and how to route traffic considering the order (service function chain). The model includes constraints on capacity, end-to-end latency, and trust constraints between operators. However, the NL approach explores too large a solution space. This makes it impractical for online network slicing, where the solution must fit within seconds.
An alternative is the Path–Link (PL) formulation. Instead of exhaustive search, it pre-generates acceptable candidate paths in an expanded graph. This graph encodes both the order of VNFs and possible placement points. Additionally, only those paths that satisfy trust constraints are filtered. For non-transitive trust, the enumeration of maximum cliques (Bron–Kerbosch) is used to identify acceptable “coalitions” of operators. As a result, the problem reduces to selecting one path from a limited set, which radically decreases complexity.
The key engineering compromise is the loss of strict optimality for the sake of response time. Simulations show that PL approaches NL with a slight gap under low load and a moderate gap under high load. The time gain is 3–6×, remaining within a few seconds even as load increases. This is critical for online scenarios. Additionally, dynamic resource pricing is introduced through the Kleinrock function, where costs increase with load. This mechanism redistributes traffic, reducing congestion and decreasing blocking in resource scarcity.
The practical takeaway for architects: the PL approach is a pragmatic compromise for real-time orchestration. It shifts complexity to preprocessing (path generation), maintaining fast runtime. Dynamic pricing acts as a local feedback loop, reducing the need for global re-optimization. However, the quality of the solution depends on the completeness of the candidate paths set: overly aggressive restrictions will lead to degraded placement. In systems with strict trust constraints, this becomes a key factor for resilience.
Information source
arXiv is the largest open preprint repository (since 1991, under the auspices of Cornell), where researchers quickly post working versions of papers; the materials are publicly accessible but do not undergo full peer review, so results should be considered preliminary and, where possible, checked against updated versions or peer‑reviewed journals. arxiv.org