  Modern communication networks are increasingly equipped with in-network
computational capabilities and services. Routing in such networks is
significantly more complicated than the traditional routing. A legitimate route
for a flow not only needs to have enough communication and computation
resources, but also has to conform to various application-specific 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 flexibly customized to meet the diverse routing requirements
of different computation applications. Our proposed heuristic algorithms
significantly outperform baseline algorithms and can achieve close-to-optimal
performance in various scenarios.

Networking and Internet Architecture