Scholarlink

<p>With the rapid advancement in computing technologies, an increasing number of networked applications require processing within the network while data is transmitted from source to destination. This has led to the emergence of computing-aware networks (CANs), which integrate network routing and in-network computation to efficiently serve latency- and compute-sensitive applications. However, jointly optimizing routing and compute node selection in CANs remains a fundamental challenge due to the inherent coupling between data delivery and computation decisions. Existing methods either suffer from high computational complexity or rely on heuristics without optimality guarantees. To address this, we propose the CAN-expanded graph (CANEG), a novel three-layer graph model that provides a complete and lossless representation of all feasible routing and computing options in CANs. Leveraging this structure, we transform the original integer linear programming (ILP) problem into a polynomial-time shortest path problem, solvable optimally using classic algorithms. Numerical experiments demonstrate that our CANEG-based method achieves optimal solutions while significantly reducing computation time by up to 8.1 times compared to ILP-based solvers and up to 3.8 times compared to heuristic approaches.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

CANEG: a polynomial-time graph model for optimal routing in computing-aware networks

  • 期刊论文

  • 发表日期：

    2026年6月18日

查看全文
  • Fei Liu,
  • Xiushe Zhang,
  • Peng Wang,
  • Hongyan Li,
  • Zonghuan Guo

摘要

With the rapid advancement in computing technologies, an increasing number of networked applications require processing within the network while data is transmitted from source to destination. This has led to the emergence of computing-aware networks (CANs), which integrate network routing and in-network computation to efficiently serve latency- and compute-sensitive applications. However, jointly optimizing routing and compute node selection in CANs remains a fundamental challenge due to the inherent coupling between data delivery and computation decisions. Existing methods either suffer from high computational complexity or rely on heuristics without optimality guarantees. To address this, we propose the CAN-expanded graph (CANEG), a novel three-layer graph model that provides a complete and lossless representation of all feasible routing and computing options in CANs. Leveraging this structure, we transform the original integer linear programming (ILP) problem into a polynomial-time shortest path problem, solvable optimally using classic algorithms. Numerical experiments demonstrate that our CANEG-based method achieves optimal solutions while significantly reducing computation time by up to 8.1 times compared to ILP-based solvers and up to 3.8 times compared to heuristic approaches.