1On Routing Optimization in Networks with Embedded Computational Services Lifan Mei Jinrui Gou Jingrui Yang Yujin Cai and Yong Liu Fellow IEEE

2025-04-28 0 0 7.37MB 13 页 10玖币

侵权投诉

On Routing Optimization in Networks with

Embedded Computational Services

Lifan Mei∗, Jinrui Gou†, Jingrui Yang‡, Yujin Cai§, and Yong Liu Fellow, IEEE¶

Department of Electrical and Computer Engineering, New York University

Email: ∗lifan@nyu.edu, †jr6226@nyu.edu, ‡jy2823@nyu.edu, §yc4090@nyu.edu, ¶yongliu@nyu.edu

Abstract—Modern communication networks are increasingly

equipped with in-network computational capabilities and ser-

vices. Routing in such networks is signiﬁcantly more complicated

than the traditional routing. A legitimate route for a ﬂow not

only needs to have enough communication and computation

resources, but also has to conform to various application-speciﬁc

routing constraints. This paper presents a comprehensive study

on routing optimization problems in networks with embedded

computational services. We develop a set of routing optimization

models and derive low-complexity heuristic routing algorithms

for diverse computation scenarios. For dynamic demands, we

also develop an online routing algorithm with performance

guarantees. Through evaluations over emerging applications on

real topologies, we demonstrate that our models can be ﬂexibly

customized to meet the diverse routing requirements of different

computation applications. Our proposed heuristic algorithms

signiﬁcantly outperform baseline algorithms and can achieve

close-to-optimal performance in various scenarios.

Index Terms—Routing, Edge Computing, In-Network Compu-

tation, Network Function Virtualization

I. INTRODUCTION

Modern communication networks are increasingly equipped

with in-network computational capabilities and services.

Software-Deﬁned Networking (SDN) [1] [2] technology can

decouple data plane and control plane, and the routing decision

can be made in a centralized fashion rather than hop-by-hop,

utilizing more information for better routing decision. Trafﬁc

ﬂows traversing such networks are processed by different

types of middle-boxes in-ﬂight. For example, in a 5G [3]

core network, trafﬁc from/to mobile user devices must pass

through special network elements, including eNodeB, serving

gateways, and packet data network gateways. To improve

security and/or boost application performance, an applica-

tion ﬂow may also traverse other types of middle-boxes for

application-speciﬁc processing, e.g., intrusion detection and

prevention, content caching to reduce latency and network

trafﬁc, rendering of VR/AR objects to ofﬂoad user devices,

object detection from video/lidar camera data acquired by

autonomous vehicles, etc. In a cloud-native network, to im-

prove performance and resilience, middle-boxes are replicated

throughout the network, and can be elastically provisioned on

commodity servers through Network Function Virtualization

(NFV) [4] [5].

Routing is a critical component of networking. The main

goal of the traditional network routing is to forward user trafﬁc

to their destinations with the lowest possible delay, while

maintaining the network-wide load balance and resilience.

Routing in networks with embedded computational services

is signiﬁcantly more complicated. It has to ﬁnd a path for

each ﬂow that simultaneously has sufﬁcient bandwidth and

computation resources to meet the ﬂow’s trafﬁc and computa-

tion demands. Load balance and resilience have to be main-

tained on both communication links and computing nodes. To

further complicate matters, application-speciﬁc computational

services will introduce diverse additional routing requirements.

Some application ﬂows have to traverse multiple types of

middle-boxes in certain preset orders, and the routing path

may have to contain cycles. The trafﬁc volume of a ﬂow might

increase or decrease after processing, consequently, the ﬂow

conservation law no longer holds. Some applications require

the computation to be done on a single computation node,

while some applications can split their computation load to

multiple paths and multiple nodes to achieve the parallelization

gain. How trafﬁc and computation are split directly impacts the

load balance and resilience of the whole network. The existing

routing models cannot directly address these new challenges

and requirements. The goal of our study is to comprehensively

explore the design space of routing in networks with embedded

computational services. We develop a set of routing opti-

mization models and derive low-complexity heuristic routing

algorithms for diverse computation scenarios. Towards this

goal, we made the following contributions.

1) For routing with non-splittable ﬂows, we show that

the problem is NP-Hard, and develop a loop-friendly

mixed integer program (MIP) model to characterize

the interplay between trafﬁc routing, computation load

distribution, and network delay performance. We further

design a Metric-TSP type of heuristic algorithm to

achieve close-to-optimal performance.

2) When ﬂows can be arbitrarily split, we prove the equiv-

alence between the routing with computational services

problem and the regular routing problem using the

segment routing idea. We develop a Linear Program

(LP) routing optimization model by extending the classic

Multi-Commodity-Flow (MCF) model to work with

heterogeneous middle-boxes and trafﬁc scaling resulting

from the processing. The LP model can be further

extended to study the joint optimization of trafﬁc routing

and computation resource provisioning.

3) For come-and-go dynamic trafﬁc demands, we convert

the online routing problem into a ﬂow packing prob-

lem, and develop a primal-dual type of online routing

algorithm with performance guarantees.

4) We evaluate the developed models and algorithms us-

ing emerging computation applications over real net-

work topologies. Through extensive experiments, we

demonstrate that our models can be ﬂexibly customized

to meet the diverse routing requirements of different

arXiv:2210.03338v2 [cs.NI] 6 Jun 2023

computation applications. Our algorithms signiﬁcantly

outperform baseline routing algorithms, and can achieve

close-to-optimal performance in various scenarios.

II. RELATED WORK

For routing with in-network processing, there are existing

studies to address various application scenarios with different

assumptions. In the context of edge/fog computing, in [6],

besides the computation allocation, they also considered mo-

bility and privacy in the joint optimization problem. In [7],

authors focused on the service allocation problem for AR

ofﬂoading. Some papers, [8] [9] [10], focused on approxi-

mation algorithm. The authors of [8] [9] used randomized

rounding with linear programming relaxation as the key idea to

deal with the non-splittable ﬂows. Authors of [10] developed

a fully polynomial-time approximation scheme (FPTAS) for

an NP-Hard problem in IoT scenarios. In [11] [12], the

problem is studied without hard link capacity constraints. For

the middle-box traversal order, [13] focused on the case

where the traversal order is ﬁxed. In the [14], authors used

graph layering to conform to the order of traversal. Authors

of [15] studied the case with arbitrary traversal order. For

routing with cycles, one strategy is to calculate all paths

with a certain number of cycles in advance [15] [16] [17],

and then use the path-based routing formulation to ﬁnd the

optimal trafﬁc routing and demand allocation. The number of

candidate paths increases exponentially, and the pre-calculated

paths may miss some good paths. Among all these studies,

the one that is closest to ours is [15]. The main assumption of

their work is that ﬂows are inﬁnitely splittable. In real world

applications, it is equally important to study non-splittable

and ﬁnitely splittable ﬂows. For inﬁnitely splittable ﬂows,

their model assumes universal middle-boxes while our model

can handle heterogeneous middle-boxes. Our segment routing-

based formulation also makes it easy to study trafﬁc scaling

after processing and joint routing and provisioning. Table I

summarizes the main differences between our work and the

most related studies.

TABLE I

KEY DIFFERENCES FROM MOST RELATED WORKS

Trafﬁc Flow Non-Splittable Inﬁnitely-Splittable Scaling

Middle-box

Univ./Hetero. Univ. Hetero. Univ. Hetero.

Traversal Order

Fixed or Not n/a F N n/a F N

[15] "

[14] [13] " "

Our Paper " " " " " "

III. ROUTING WITH IN-NETWORK PROCESSING PROBLEM

We consider a generic network represented by a directed

graph G= (V,E), where Vdenotes a set of nodes, and E

denotes a set of directed links connecting the nodes. The graph

Gis assumed to be mesh-connected, having multiple paths

connecting each pair of nodes. Every link eis associated with

bandwidth capacity of Ce. The node set Vcontains standard

routers and special middle-boxes attached to routers. There

might be different types of middle-boxes. For a type-rmiddle-

box z, its processing capacity is Nr

z. A set of ﬂows are

to be routed and processed in the network. Each ﬂow dis

characterized by its source node sd, destination node td, trafﬁc

volume hd, and its demand for type-rprocessing Wr

d. The

Routing with In-Network Processing (RINP) problem is to

ﬁnd paths with sufﬁcient bandwidth and processing resources

for all ﬂows, subject to bandwidth/resource capacities on all

links/nodes.

There are different variations of RINP along different di-

mensions.

1) Universal vs. Heterogeneous middle-boxes: In the tra-

ditional networks, different types of middle-boxes are

designed for speciﬁc processing tasks. The new trend

is to implement middle-box functions on generic com-

puting servers using NFV. Each computing node can be

conﬁgured to process any demand. The capacity of a

middle-box can be measured by its universal computa-

tion power Nr, and the ﬂow processing demand can be

characterized by the total computation power needed.

2) Non-splittable vs. Inﬁnitesimal Flow/demand: When the

ﬂow granularity is small, e.g., one ﬂow for each user

application session, splitting the ﬂow to multiple net-

work paths and multiple middle-boxes will be inef-

ﬁcient/impractical. On the other hand, in a backbone

network, each ﬂow is indeed the aggregated user trafﬁc

from city A to city B. It is therefore more ﬂexible to split

the trafﬁc as well as the associated processing demand to

multiple paths, and if a path contains multiple middle-

boxes, the processing demand can be further split to

utilize all available resources.

3) Constant vs. Elastic Trafﬁc Volume: Certain types of in-

network processing will increase or decrease the trafﬁc

volume of the processed ﬂow. For example, after an

edge server rendered online game updates, the size

of the rendered video stream will typically be larger

than the game updates. On the other hand, after an

edge server processed the Lidar data captured by an

autonomous vehicle, it only needs to upload the learned

representations to the cloud server, which has a volume

much lower than the raw data.

4) Fixed vs. Reconﬁgurable Processing Capacity: The tra-

ditional middle-boxes have ﬁxed capacities, while the

software-based virtual middle-boxes can be reconﬁgured

on-demand to match the processing needs. The RINP

problem can be more efﬁciently solved by jointly routing

ﬂows and provisioning middle-boxes.

IV. RINP OPTIMIZATION MODELS

The optimization objective of RINP depends on the ac-

tual situation. Some popular objectives are to minimize the

link/node delay, minimize the maximum link/node utilization,

maximize the processed ﬂows, and certain combinations of

them. In this paper, we use minimizing network delay as

an example objective for static optimization and maximizing

the processed ﬂows for dynamic optimization. The developed

formulations can be easily customized for other objectives.

(a) Non-splittable (b) Inﬁnitely-splittable (c) Segment Routing

Fig. 1. Routing with In-Network Processing (RINP) Basic Examples

TABLE II

KEY PARAMETERS AND NOTATIONS

Symbol Description

Vset of all nodes

Pr⊂Vsubset of computing nodes with type-rresources

Eset of links in a graph

Dset of demand ﬂows

Ttime horizon

aev 1 if link eoriginates from node v; 0 otherwise

bev 1 if link eterminates at node v; 0 otherwise

sdsource node of ﬂow d

tdterminal node of ﬂow d

hdtrafﬁc volume of ﬂow d

dtrafﬁc volume of virtual sub-ﬂow of dprocessed by z

dtype-rresource demand of ﬂow d

Cebandwidth capacity on link e

fetotal trafﬁc rate on link e

xed trafﬁc of ﬂow dallocated on link e

xzs

ed trafﬁc of segment sof d’s subﬂow processed by z

allocated on link e

ued integer, number of times ﬂow dtraverses link e

εed binary, whether or not ﬂow dtraverses link e

ztype-rresource capacity on node z∈Pr

ρrupper bound of type-rresource utilization

Nzresource capacity on node zwith universal resources

zd type-rresource consumption of ﬂow don node z

ed unprocessed type-rdemand of ﬂow don link e

τd, τs

d, τf

dduration, start time, and ﬁnish time of d

βdτ binary, = 1 if τs

d≤τ≤τf

d,= 0 otherwise

Pdset of candidate paths for demand d

δedp non-negative constant, the fraction of trafﬁc of

candidate path prouted on link e

ydp binary variable, whether demand dis routed on

candidate path p∈Pd

D(e)variable, set of demands routed on link e

P(e)variable, set of selected paths (ydp = 1)

passing through link e

A. Non-splittable Flow

We start with the simple case that each ﬂow can only

take a single path, i.e., non-splittable. An example is shown

in Fig. 1(a), there are only two middle-boxes, each with a

capacity of 1, to complete the processing demand of 2, the ﬂow

has to take a path with cycles to pass through the two middle-

boxes before reaching its destination. We will ﬁrst show that

the non-splittable RINP problem is NP-Hard by reducing the

well-known Metric Traveling Salesman Problem (TSP) to non-

splittable RINP. We then develop a Mixed-Integer Program

(MIP) to study the interplay between trafﬁc routing, demand

processing, and network delay optimization.

Theorem 1: Non-splittable RINP with constant link delays

is NP-Hard. □

Proof: Given a set of nodes and the distances between them,

the Traveling Salesman Problem (TSP) is to ﬁnd an optimal

order of traversing all the nodes with the shortest total distance.

Metric-TSP (M-TSP) is a special case of TSP where the

distances between nodes form a metric to satisfy the triangle

inequality: d(v1, v2)≤d(v1, v3)+d(v3, v2). For a given graph

G= (V, E)and the distance metric d(·), we construct a

special instance of non-splittable RINP on Gby: 1) placing

one unit of computing capacity on each node, 2) setting the

propagation delay on link (v1, v2)to d(v1, v2), 3) creating one

ﬂow with the same source and destination node, 4) setting the

ﬂow’s trafﬁc volume to ϵ << Ceso that the congestion delay

is negligible, and setting the ﬂow’s processing demand to |V|.

Obviously, to satisfy the ﬂow’s processing demand, the ﬂow

has to visit all nodes in the graph, and to minimize the total

delay RINP has to ﬁnd the path with the shortest distance. The

only potential discrepancy between RINP solution and the M-

TSP solution is that M-TSP solution can only visit each node

once while in principle RINP solution may have to visit a

node multiple times, as illustrated in the example in Fig. 1(a).

However, due to the metric distance, we can easily show that

the RINP solution for the specially constructed network can be

guaranteed to be cycle-free. Suppose the RINP solution visits

some nodes more than once, without loss of generality, let kbe

the ﬁrst node that is visited twice, iand jare the nodes visited

before and after the second visit to k. By removing the second

visit of k, i.e., replacing the path segment i→k→jwith

i→j, the total path length can potentially be reduced due

to the triangle inequality. Using this process, we can remove

all the duplicate visits to get a cycle-free RINP path that has

either the same length or a shorter length than the original

path. This path is a cycle-free solution for M-TSP. ■

For more generic non-splittable RINP, we develop a MIP

model to analytically investigate how trafﬁc routing and de-

mand splitting impact network-wide performance. The nota-

tions are deﬁned in Table II.

MIP-RINP: min

{ued,yr

ed,wr

zd }X

e∈E

Ce−fe

(1a)

subject to

|D|

d=1

xed =fe≤Ce,

|D|

d=1

zd ≤ρrNr

z,(1b)

e∈E

aevued −X

e∈E

bevued =





1if v =sd

0if v ̸=sd, td

−1if v =td

(1c)

xed =uedhd(1d)

εed ≤ued, ued ≤Bεed, yr

ed ≤Bεed (1e)

e∈E

aevyr

ed −X

e∈E

bevyr

ed =





dif v =sd

vd if v ̸=sd, td

0if v =td

(1f)

ued ≥0integer;εed binary;(1g)

vd ≥0, wr

vd = 0,∀v /∈Pr, yr

ed ≥0,(1h)

where (1a) is the total network delay modeled using the M/M/1

formula. (1b) describes the total trafﬁc rate on a link can not

exceed its bandwidth capacity, and the total type-rresources

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

1OnRoutingOptimizationinNetworkswithEmbeddedComputationalServicesLifanMei∗,JinruiGou†,JingruiYang‡,YujinCai§,andYongLiuFellow,IEEE¶DepartmentofElectricalandComputerEngineering,NewYorkUniversityEmail:∗lifan@nyu.edu,†jr6226@nyu.edu,‡jy2823@nyu.edu,§yc4090@nyu.edu,¶yongliu@nyu.eduAbstract—Moderncommuni...

展开>> 收起<<

1On Routing Optimization in Networks with Embedded Computational Services Lifan Mei Jinrui Gou Jingrui Yang Yujin Cai and Yong Liu Fellow IEEE.pdf

共13页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

1On Routing Optimization in Networks with Embedded Computational Services Lifan Mei Jinrui Gou Jingrui Yang Yujin Cai and Yong Liu Fellow IEEE

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: