PaperlayerView exact revision on arXiv

Source-linked AI summary

SPFR: Semantic Potential Field Routing for the Distributed Internet of Agents

Yeguang Qin, Liangqi Peng, Fengxiao Tang, Ming Zhao

arXiv:2608.25396v1cs.NI

TL;DR

Distributed IoA routing must find capability-matched executors despite unknown destinations and bounded local service views. SPFR jointly discovers, reselects, and forwards toward executors using task-conditioned semantic potentials. Its analysis proves frozen-state routing guarantees, while simulations show competitive utility with lower forwarding and signaling overhead under dynamics.

  • Problem

    Distributed IoA routing must coordinate executor selection with network forwarding as candidate visibility changes across locations under bounded local service views.

  • Method

    SPFR represents visible eligible executors as task-conditioned semantic potential sources and recomputes executor selection and next-hop forwarding at each hop.

  • Results

    Across real-world topologies and dynamic conditions, SPFR approached distributed utility-greedy and global-discovery utility while reducing forwarding hops and request-triggered messages.

  • Takeaways & Limitations

    SPFR provides a distributed routing approach that balances executor utility with network overhead under bounded visibility and changing service or network states.

Abstract

from arXiv · show

In a distributed Internet of Agents (IoA) without centralized routing control, routing tasks to capability-matched executors is challenging because destinations are not predetermined and agents have bounded local service views. Discover-then-forward approaches, by contrast, select an executor before network forwarding and therefore do not directly support reselection when additional candidates become visible downstream. We introduce Semantic Potential Field Routing (SPFR), a distributed IoA routing algorithm that integrates executor discovery and reselection into hop-by-hop forwarding. SPFR represents each executor visible in a local semantic forwarding information base (FIB) as a task-conditioned semantic potential source, with utility setting its strength and hop distance inducing exponential attenuation. At each hop, the forwarding agent recomputes these potentials, reselects the dominant executor, and forwards the task one hop toward it. Under task-consistent frozen-FIB conditions, we prove loop freedom and finite-hop termination and derive an explicit additive error bound under bounded visibility relative to the full-visibility objective. Extensive simulations on real-world topologies show that SPFR approaches the realized utility of distributed utility-greedy routing and request-triggered global discovery while using fewer forwarding hops and substantially fewer request-triggered messages, and remains robust under network and service dynamics.

I. INTRODUCTION

Distributed IoA routing must jointly discover capability-matched executors and forward tasks when agents have only bounded, location-dependent service views. SPFR addresses this by recomputing task-conditioned semantic potentials and reselection during hop-by-hop forwarding.

  • I. INTRODUCTION: SPFR represents each visible eligible executor as a task-conditioned potential source whose strength reflects semantic fit, projected load, and execution price.Potential attraction decays exponentially with hop distance, and forwarding decisions use bounded semantic FIB information.
  • I. INTRODUCTION: Capability-driven IoA routing jointly selects an executor and request path under execution, return-route, deadline, and budget constraints.The resulting joint optimization problem is NP-hard, motivating tractable utility-only and hop-regularized reference objectives.
  • I. INTRODUCTION: SPFR integrates executor discovery and reselection with hop-by-hop forwarding, updating the executor and corresponding next hop using local information.This design addresses changing candidate visibility across locations rather than selecting an executor only before forwarding begins.
  • I. INTRODUCTION: Under stated frozen-FIB conditions, SPFR has loop freedom and finite-hop termination, with global optimality under full visibility and an additive error bound under bounded visibility.These guarantees apply to the analytical frozen snapshot and its stated FIB conditions.
  • I. INTRODUCTION: Across GEANT, UNINETT, and Deltacom, SPFR approached distributed utility-greedy and request-triggered global-discovery utility with fewer forwarding hops and less signaling.The simulations also evaluated robustness under network and service dynamics.
  • I. INTRODUCTION: SPFR models the IoA substrate as a finite, connected, undirected graph in which all agents may forward tasks but only some advertise execution services.Service capability is an agent attribute, while executor is the task-specific role assigned to a selected eligible agent.

B. Task Semantics and Executor Utility

The paper models tasks through semantic requirements, workload, payloads, and policy constraints, then computes executor eligibility and utility from capability matching, load, and price. Feasibility additionally requires request–return paths satisfying delay and budget limits.

  • B. Task Semantics and Executor Utility: Each task contains semantic requirements, computational workload, payload sizes, and a task-policy descriptor.The policy descriptor includes request-related task parameters, while payload and deadline fields support later feasibility checks.
  • B. Task Semantics and Executor Utility: Eligibility requires a distinct capability assignment covering every task requirement with similarity above θT.The maximum average matched similarity is computed over feasible assignments, solvable in polynomial time using the Hungarian method.
  • B. Task Semantics and Executor Utility: Executor utility combines semantic similarity, normalized projected workload, and normalized execution price using shared weights that sum to one.All agents derive identical executor-side quantities from the same task and descriptor snapshot.
  • B. Task Semantics and Executor Utility: Projected execution delay is based on queued workload plus task workload divided by service rate, with normalized load used in utility.The load normalization uses a system-wide reference constant.
  • B. Task Semantics and Executor Utility: An executor–path combination is feasible only when request and return paths exist and total completion delay and cost satisfy the SLA limits.Total delay includes request transmission, execution, and return delay; total cost includes request communication, execution price, and return communication.

C. Local Semantic FIB and Reply Interface

The local semantic FIB stores bounded-radius service descriptors and request-forwarding state, while a separate reply interface checks return-route feasibility and aggregate path metrics. Semantic visibility, structural reachability, and return-route availability remain distinct.

  • C. Local Semantic FIB and Reply Interface: The control horizon Hctrl bounds how far service descriptors are disseminated, limiting local semantic information without limiting the complete request path.The resulting bounded semantic view is denoted with superscript H.
  • C. Local Semantic FIB and Reply Interface: A converged FIB entry stores a service descriptor, hop distance, request next hop, and timestamp for each visible service.The stored next hop lies on a shortest-hop path under convergence, and service-capable agents maintain self-entries.
  • C. Local Semantic FIB and Reply Interface: Every valid remote FIB entry satisfies hi(j) ≤ Hctrl, while TTL completeness is an analytical condition rather than a prerequisite for local forwarding.This separates the bounded dissemination model from the ability to make an immediate forwarding decision.
  • C. Local Semantic FIB and Reply Interface: The FIB stores no task-specific match, utility, or candidate set; these quantities are computed after task arrival.It supplies request next hops, while the underlay supplies return-route feasibility and aggregate metrics through ReplyLookup.
  • C. Local Semantic FIB and Reply Interface: ReplyLookup checks return-route availability, cost, and delay without revealing remote service descriptors or enlarging semantic visibility.Structural reachability, return-route availability, and semantic visibility are therefore separate properties.

D. Task-Specific Executor Eligibility

Executor eligibility is evaluated locally from stored descriptors, task parameters, and return-route information. The resulting screens are necessary path-independent conditions, while end-to-end feasibility still depends on request-path delay and cost.

  • D. Task-Specific Executor Eligibility: A complete one-to-one capability matching above θT is required, so no additional threshold on average similarity S(j,T) is needed.The matching condition itself ensures every selected capability–requirement pair meets the threshold.
  • D. Task-Specific Executor Eligibility: The projected-load condition ρTj < 1 excludes agents whose workload fills the service-admission horizon, while unsaturated load differences remain represented in utility.These conditions omit request-path delay and cost, making them necessary screens rather than sufficient end-to-end feasibility conditions.
  • D. Task-Specific Executor Eligibility: During runtime, each agent evaluates eligibility using its current FIB descriptor, task parameters, and return-route lookup, then gates the locally stored utility.The locally gated utility is the evaluated executor utility multiplied by the eligibility indicator.
  • D. Task-Specific Executor Eligibility: The frozen analysis equates locally evaluated utility with task utility for every visible executor under a task-consistent snapshot.This identity supports the theoretical treatment of locally visible candidates.
  • D. Task-Specific Executor Eligibility: The analytical eligibility reference set combines executor-side and return-side necessary conditions but does not certify an end-to-end request path.The implementation does not construct or enumerate this global reference set.

IV. PROBLEM FORMULATION

The paper formulates task routing as jointly selecting an eligible executor and a feasible request path under utility, deadline, budget, and return-route constraints. It separates this difficult joint problem from utility-only reference objectives.

  • IV. PROBLEM FORMULATION: The formulation uses one control-plane snapshot for Problems P1, P1′, and P2, with later updates affecting subsequent tasks rather than the analyzed decision.
  • IV. PROBLEM FORMULATION: The model distinguishes path-independent executor eligibility and utility from end-to-end request-path feasibility.
  • A. P1: Global Joint Executor–Path Optimization: The ideal problem jointly selects executor j and request path P to maximize task utility under execution, request-path, return-route, deadline, and budget constraints.
  • A. P1: Global Joint Executor–Path Optimization: P1-FEAS is NP-complete, so the joint executor–path optimization problem is NP-hard.
  • A. P1: Global Joint Executor–Path Optimization: Feasibility certificates consist of an executor and a simple request path whose matching, validity, deadline, and budget constraints can be checked in polynomial time.
  • A. P1: Global Joint Executor–Path Optimization: The NP-hardness reduction constructs a chain of diamond subgraphs whose branch choices encode a PARTITION instance through request costs and delays.
  • A. P1: Global Joint Executor–Path Optimization: The constructed instance is feasible exactly when the encoded branch costs satisfy X = S/2, establishing the reduction.

B. P1′: Utility-Only Upper Benchmark

P1′ ranks eligible executors by utility without constrained-path search, while P2 adds hop attenuation to regularize utility with locality for distributed routing analysis.

  • B. P1′: Utility-Only Upper Benchmark: P1′ isolates executor ranking from constrained-path search and uses path-independent eligibility.
  • B. P1′: Utility-Only Upper Benchmark: The utility-only optimum is a polynomial-time global upper benchmark obtained through capability matching and candidate scanning.
  • C. P2: Hop-Regularized Semantic Routing Objective: P2 maximizes source-side utility multiplied by exponential hop attenuation, with ωh controlling the utility–locality trade-off.
  • C. P2: Hop-Regularized Semantic Routing Objective: A breadth-first search plus candidate scan solves the global P2 reference objective in O(|V| + |E|) time once eligibility and utility are available.
  • C. P2: Hop-Regularized Semantic Routing Objective: SPFR evaluates a local P2 counterpart whose candidate set and distance origin can change between hops, with exact full-visibility realization and bounded-view error established theoretically.
  • C. P2: Hop-Regularized Semantic Routing Objective: P2 omits accumulated request-path cost and delay, so SPFR is not claimed to approximate P1 in polynomial time.
  • C. P2: Hop-Regularized Semantic Routing Objective: Exponential attenuation follows segment composability: concatenated path attenuation equals the product of segment attenuations.
  • C. P2: Hop-Regularized Semantic Routing Objective: The effective ranking distance is a task-dependent transformation, not a physical underlay distance or graph metric.

V. SPFR DESIGN

SPFR performs local, hop-by-hop executor reselection by recomputing task-conditioned potentials from each forwarding agent’s semantic FIB and forwarding toward the dominant executor.

  • B. Hop-by-Hop Forwarding and Complexity: SPFR evaluates visible executors using local semantic FIB state and can discover a stronger downstream executor while updating both executor and next hop.
  • B. Hop-by-Hop Forwarding and Complexity: Each visible executor induces a locally estimated task-conditioned potential, with ties broken deterministically by executor identifier.
  • B. Hop-by-Hop Forwarding and Complexity: Under a frozen task-consistent snapshot, runtime estimates equal analytical utility and potential values used in the proofs.
  • B. Hop-by-Hop Forwarding and Complexity: At each hop, the current agent executes if it is the selected executor; otherwise, it forwards to that executor’s stored next hop for another local decision.
  • B. Hop-by-Hop Forwarding and Complexity: Missing or inactive next hops, forwarding failure, and exhausted hop budgets produce NO_SEMANTIC_ROUTE.
  • B. Hop-by-Hop Forwarding and Complexity: When no positive-potential candidate exists, SPFR returns NO_SEMANTIC_ROUTE without semantic frontier exploration.
  • B. Hop-by-Hop Forwarding and Complexity: The forwarding rule operates on valid local FIB entries, while formal guarantees require separate consistency and completeness conditions.
  • B. Hop-by-Hop Forwarding and Complexity: Per-hop computation is dominated by capability matching, while bounded dissemination limits state and computation to an Hctrl-hop neighborhood whose size may grow with local density.

VI. THEORETICAL ANALYSIS

The analysis assumes a task-consistent frozen snapshot with complete bounded-radius visibility, correct next-hop closure, and a positive source-side attractor. Under these conditions, candidate inheritance yields loop freedom and finite termination.

  • VI. THEORETICAL ANALYSIS: Candidate inheritance produces strict dominant-potential ascent, establishing loop freedom and finite-hop termination.
  • VI. THEORETICAL ANALYSIS: The frozen-snapshot analysis keeps the attenuation parameter ωh > 0 fixed throughout.
  • VI. THEORETICAL ANALYSIS: The task-consistent snapshot fixes the graph, descriptors, utility inputs, matching results, reply descriptors, hop counts, and next hops during analysis.
  • VI. THEORETICAL ANALYSIS: TTL completeness requires every advertised service descriptor within Hctrl hops and its correct shortest-hop distance to be present in each semantic FIB.
  • VI. THEORETICAL ANALYSIS: Next-hop closure requires a selected nonlocal executor to be one hop closer from the next forwarding agent.
  • VI. THEORETICAL ANALYSIS: The source must observe at least one eligible executor with positive utility for the stated analysis.

B. Candidate Inheritance and Potential Ascent

Under task-consistent frozen-FIB conditions, visible positive-potential candidates persist downstream, while dominant potential strictly increases at every nonterminal hop. These properties establish loop freedom, finite termination, full-visibility optimality, and a bounded-visibility additive error guarantee.

  • Candidate Inheritance: Candidate inheritance preserves executor eligibility, task utility, reply descriptors, and positive gated utility at the next hop.Next-hop closure reduces the remaining hop count by one while preserving a valid forwarding entry.
  • Potential Ascent: Strict dominant-potential ascent gives ΦH_k(T) ≥ exp(ωh)ΦH_i(T) for every nonterminal step i → k.The inequality is strict because ωh > 0 and the current dominant potential is positive.
  • Termination: SPFR is loop-free and terminates at an eligible executor after at most |V|−1 nonterminal forwarding steps.Revisiting an agent would reproduce its frozen local state and contradict strict potential ascent.
  • Full Visibility: Under full semantic visibility, SPFR terminates at an executor maximizing the full-visibility P2 objective.The terminal source-side potential is both feasible for P2 and bounded above by its optimum.
  • Bounded Visibility: Under bounded visibility, the additive P2 gap satisfies 0 ≤ P2Gap_T ≤ Umax exp[−ωh(Hctrl + 1)].The bound follows because source-invisible executors lie at least Hctrl + 1 hops away.
  • Scope of Guarantees: The guarantees require frozen task-consistent state and do not bound executor utility or Problem P1 approximation under changing FIBs.If no eligible positive-utility executor is visible at the source, SPFR returns NO_SEMANTIC_ROUTE.

A. Setup

The evaluation uses dynamic distributed-task simulations across three real-world topologies, with heterogeneous agents, capability requirements, paired baselines, and task-level outcome accounting. Figure 2 separately examines in-path reselection on UNINETT.

  • Simulation Environment: The simulator evaluates distributed task forwarding on GEANT, UNINETT, and Deltacom with one agent hosted at each topology node.The catalog contains 24 atomic capabilities grouped into eight semantic domains, with heterogeneous agent tiers and regional or cross-region placement.
  • Workload: Light, standard, and complex tasks require 2, 2–3, and 3–4 capabilities, respectively, with independently sampled sources and requirements.Requirement–capability matching uses the Hungarian algorithm and excludes pairs below the 0.55 relevance threshold.
  • Experimental Protocol: The main experiment uses dynamic queues, service changes, link perturbations, background traffic, stale control-plane state, 10 paired seeds, and 200 tasks per seed.Cross-topology contrasts average topologies within each seed and use two-sided 95% Student-t confidence intervals across seeds.
  • Baselines: SPFR is compared with RAND, D-SEM, D-GREEDY, and request-triggered full-discovery GLOBAL† under shared bounded local FIBs for the distributed methods.The methods differ in executor selection: source-fixed random, semantic, utility-greedy, semantic-potential, or full-view potential.
  • Metrics: Realized Utility counts successful execution, result return, and semantic, deadline, and budget satisfaction; failed and NO_SEMANTIC_ROUTE tasks contribute zero.Request-triggered messages are normalized over all tasks, while several performance metrics are conditioned on successful tasks.
  • Reselection Experiment: Figure 2 compares utility and completed-task network expenditure for source-sufficient and moving-view-required tasks, with expenditure normalized to SRC-FIX.The separate UNINETT experiment isolates in-path reselection using paired Local and Discovery tasks.

B. Main Results

Across topologies and runtime regimes, SPFR preserved competitive utility while reducing forwarding and request-path overhead, with stronger relative advantages under high joint stress. Sensitivity, ablation, and audit results identify practical operating points, component roles, bounded-state costs, and the scope of the guarantees.

  • Cross-topology performance: 34.34% fewer forward hops and 27.24% fewer request-triggered messages than D-GREEDY accompanied SPFR’s competitive utility across three topologies.SPFR had 1.43% lower Utility but 1.10 percentage points higher Success than D-GREEDY; relative to GLOBAL†, it retained 97.63% Utility with 81.24× fewer request-triggered messages.
  • Reselection: 18.19% higher utility on Discovery tasks demonstrates SPFR’s in-path reselection benefit when superior executors become visible downstream.On Local tasks, SPFR and SRC-FIX achieved nearly identical utility; D-GREEDY gained 1.18% utility over SPFR but incurred 13.66% more hops and 13.00% more request messages.
  • Runtime regimes: Under high joint stress, SPFR improved Utility by 3.21% and Success by 4.40 percentage points while reducing network costs by 14.04–35.25%.Under nominal dynamics, it sacrificed 1.37% Utility relative to D-GREEDY while improving Success by 1.20 percentage points; compared with GLOBAL, it retained at least 97.92% utility with at least 73.46× fewer request messages.
  • Sensitivity: Hctrl = 2 and ωh = 0.08 were selected near the observed utility–overhead elbow rather than as universally optimal settings.Increasing Hctrl from 2 to 3 yielded only a 1.64% utility gain while increasing FIB state 2.08× and beacon traffic 2.60×; increasing ωh from 0.04 to 0.08 reduced hops 14.1% and communication cost 16.0% with a 0.50% utility loss.
  • Ablations: Removing hop attenuation increased Utility by 1.69% but increased hops by 56.0% and messages by 39.2%, while removing reselection reduced Utility by 1.10%.Linear attenuation closely matched exponential attenuation, changing Utility, hops, and messages by only −0.21%, −1.7%, and −1.2%, respectively.
  • Component and scaling audits: Semantic similarity had the largest observed component-specific Utility effect, while bounded dissemination constrained per-agent state but left aggregate beacon traffic as the principal scaling cost.Removing semantic similarity reduced Utility 6.13%; across measured topologies, mean FIB size stayed within 12.44–21.55 entries per agent while aggregate beacon rate increased 7.15× from GEANT to KDL.
Loading 2608.25396v1…