Q-routing
Algorithms AIMech:QRouting DRAFT
A distributed adaptive packet-routing algorithm that learns destination-specific delivery-time estimates by combining observed local queue and transmission delays with a neighboring node’s estimate of remaining delivery time.
Identity Notes & Concept Scope
This record denotes Boyan and Littman’s original tabular Q-routing method. It minimizes predicted delivery time using local bootstrapped information, unlike AntNet’s measured complete forward-trip feedback and probabilistic routing-table reinforcement. The exploratory full-echo scheme is a distinct variant, not an unmentioned mandatory part of the baseline. A neural approximation was explored but is not the defining original representation. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 298 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 20 and 20 lines respectively. All 17 unique hit contents were inspected: prior TD(lambda) and Q-routing leads, GAE and AntNet boundary statements, and their saved reports/reviews. These were references to methods rather than existing candidate records. Six exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and six native neighboring mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
At node x, maintain Q_x(d,y), the estimated time to deliver a packet to destination d through neighbor y, including waiting in x’s queue. Route using the neighbor with the smallest current estimate. Upon sending the packet to y, obtain its estimate t=min_z Q_y(d,z). With observed waiting time q at x and link-transmission time s from x to y, update the used table entry by Q_x(d,y)_new=Q_x(d,y)+eta*(q+s+t−Q_x(d,y)). This is an asynchronous local cost backup; it uses a minimum because delivery times are costs and the displayed target has no discount factor. The baseline only updates the selected neighbor entry. The full-echo extension separately queries all neighbors and updates their estimates, under a simulation assumption that the extra queries do not themselves congest the network.
⚠️ Curated Limitations & Negative Results
- The greedy baseline has no deliberate exploration once its initial policy is established. Overestimated unused alternatives can remain stale, impeding rediscovery of shortcuts when load decreases; the source explicitly reports this weakness. Full echo changes the information and update scheme and may introduce oscillation under heavy traffic.
- Queue-dependent delays, other adaptive routers and changing traffic make the environment nonstationary relative to a destination/neighbor table. The record imports no stationary tabular Q-learning convergence theorem, optimality certificate, loop-freedom guarantee or universal routing superiority.
- The displayed interior-node update needs declared destination-boundary, initialization, tie-breaking, disconnected-network and message-delay conventions in an executable implementation. The method text does not fully specify all these cases, and a simulator or complete protocol is not supplied by this conceptual record.
- Results come from a simplified discrete-event network simulation; the paper explicitly says it is not fully realistic. The neural-network experiments were inconclusive. No empirical performance claim or deployment validation is curated.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ReinforcementLearning
Reinforcement Learning
|
related_match | The primary method embeds local reinforcement-learning updates in packet routers. The AIO target is the task category, not the same algorithm, a network model, or a theorem guaranteeing adaptive network convergence. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Justin A. Boyan, Michael L. Littman
|
primary paper
full_text
|
ID: https://papers.nips.cc/paper_files/paper/1993/hash/4ea06fbc83cdd0a06020c35d50e1e89a-Abstract.html
sha256:d85e5660aa4e…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T14:02:32Z
Updated: 2026-10-11T14:02:32Z
Source File:
data/curated/QRouting.yaml