Sam Austinon November 5, 202615 min read

Q-Routing Explained: Reinforcement Learning for Packet Routing in Networks

Q-Routing Explained: Reinforcement Learning for Packet Routing in Networks
Contents

Figure 1: Q-Routing Explained — each router learns delivery times through its neighbors, shifting traffic away from congested paths without a central controller

A packet enters your network at node A and needs to reach node F. Five routes exist, and congestion shifts every few seconds. Static routing tables do not notice, but a learning router can. Q-routing teaches each node to estimate delivery time through each neighbor and pick the fastest one, using nothing but local feedback.

I cannot claim I have run this on a production network, so treat this as a learning project. Q-routing is the cleanest way to see distributed reinforcement learning at work, because every router learns independently with no central controller. Ready to build?

What Is Q-Routing?

Boyan and Littman introduced Q-routing in 1993 as an application of Q-learning to packet routing. Each node keeps a table of estimates: "If I send a packet for destination d through neighbor y, how long will delivery take?" The node forwards each packet to the neighbor with the lowest estimate. Check the original paper for the exact formulation and experiments.

The key idea is that learning happens during normal traffic. Every forwarded packet produces feedback, so the tables improve without special probing. Congested paths get higher estimates, and traffic shifts away from them.

Why Classical Routing Struggles Under Load

Shortest-path protocols like OSPF and RIP compute routes from link costs, usually hop count or a configured weight. They react to topology changes, but they do not track queue delays at packet timescales. Three consequences follow:

  • Hot spots: every flow picks the same "shortest" path, and its queues grow
  • Slow reaction: load changes faster than route updates propagate
  • Static metrics: hop count ignores how long packets actually wait

Ever watched a navigation app send everyone down the same road? That is the problem Q-routing attacks.

How Q-Routing Works

The Q-Table

Each node x stores Q_x(d, y): its estimate of the total time to deliver a packet to destination d if it forwards through neighbor y. The estimate includes time spent in x's own queue, the transmission time, and the neighbor's remaining estimate.

The Update Rule

When node x sends a packet for destination d to neighbor y, node y replies with its own best estimate: t = min over z of Q_y(d, z). Node x then updates:

Q_x(d, y) ← Q_x(d, y) + α · (q + s + t − Q_x(d, y))

Here is what each symbol means:

  • α: the learning rate
  • q: time the packet waited in x's queue
  • s: transmission time on the link from x to y
  • t: y's estimate of the remaining time to the destination

This is ordinary Q-learning with time as the cost and a discount factor of one. The neighbor's reply carries the learning signal, so nodes need no global view.

Action Selection

Each node picks the neighbor with the lowest Q-value. Pure greedy choice can trap you, though, because a path that looked slow once never gets retried. Many implementations add a little epsilon-greedy exploration. Boyan and Littman's original version used greedy selection, and later work studied exploration and its side effects.

Setting Up

pip install numpy

This tutorial needs only NumPy. We will write the network simulator ourselves so you can read every line.

Building the Network Simulator

We will use a small grid. Each node has a FIFO queue, and each link takes one time step to traverse. Each node forwards one packet per step. Packets arrive at random sources with random destinations.

import numpy as np
from collections import deque

def make_grid(rows=4, cols=4):
    nodes = [(r, c) for r in range(rows) for c in range(cols)]
    nbrs = {}
    for r, c in nodes:
        nbrs[(r, c)] = [(r + dr, c + dc)
                        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]
                        if 0 <= r + dr < rows and 0 <= c + dc < cols]
    return nodes, nbrs

class Network:
    def __init__(self, nodes, nbrs, rng):
        self.nodes, self.nbrs, self.rng = nodes, nbrs, rng
        self.queues = {n: deque() for n in nodes}
        self.t = 0
        self.delivered = []                 # delivery times of finished packets

    def inject(self, src, dst):
        if src != dst:
            self.queues[src].append({"dst": dst, "born": self.t, "enq": self.t})

    def step(self, choose_next, on_feedback=None):
        moves = []
        for node in self.nodes:
            if not self.queues[node]:
                continue
            pkt = self.queues[node].popleft()
            nxt = choose_next(node, pkt["dst"])
            q_time = self.t - pkt["enq"]
            moves.append((node, nxt, pkt, q_time))

        self.t += 1                          # all moves arrive after one step
        for node, nxt, pkt, q_time in moves:
            if on_feedback:
                on_feedback(node, nxt, pkt["dst"], q_time)
            if nxt == pkt["dst"]:
                self.delivered.append(self.t - pkt["born"])
            else:
                pkt["enq"] = self.t
                self.queues[nxt].append(pkt)

    def backlog(self):
        return sum(len(q) for q in self.queues.values())

Packets reaching their destination leave the network immediately, and the delivery time is the age at arrival. The q_time value records how long the packet waited at the node before being sent, which is exactly the q term in the update rule.

Implementing Q-Routing

Each node keeps a table keyed by destination and neighbor. We initialize estimates with a rough hop-distance guess, which gives the agent a sensible start without handing it the answer.

class QRouter:
    def __init__(self, nodes, nbrs, alpha=0.5, eps=0.0, rng=None):
        self.nbrs, self.alpha, self.eps = nbrs, alpha, eps
        self.rng = rng or np.random.default_rng(0)
        self.Q = {}
        for x in nodes:
            for d in nodes:
                if d == x:
                    continue
                for y in nbrs[x]:
                    hops = abs(y[0] - d[0]) + abs(y[1] - d[1]) + 1
                    self.Q[(x, d, y)] = float(hops)

    def best(self, x, d):
        return min(self.Q[(x, d, y)] for y in self.nbrs[x])

    def choose(self, x, d):
        options = self.nbrs[x]
        if self.rng.random() < self.eps:
            return options[self.rng.integers(len(options))]
        return min(options, key=lambda y: self.Q[(x, d, y)])

    def feedback(self, x, y, d, q_time):
        t = 0.0 if y == d else self.best(y, d)   # delivered: no time remaining
        s = 1.0                                   # link transmission time
        key = (x, d, y)
        self.Q[key] += self.alpha * (q_time + s + t - self.Q[key])

Notice the line t = 0.0 if y == d. When the next hop is the destination, no further delay remains, so the estimate collapses to the final link time. Without that rule, estimates never anchor to reality.

Building the Baseline

Q-routing needs a comparison. We will use static shortest-path routing, which picks the neighbor that minimizes Manhattan distance to the destination and breaks ties by a fixed order.

def make_shortest_path(nbrs):
    def choose(x, d):
        return min(nbrs[x], key=lambda y: (abs(y[0] - d[0]) + abs(y[1] - d[1]), y))
    return choose

On a grid, this baseline funnels many flows through the same rows and columns because of the fixed tie-breaking. That is the congestion pattern Q-routing should learn to avoid.

Running the Experiment

We will create a deliberate hot spot: most packets go from the left column to the right column, so the center links carry heavy load.

def run(policy_name, load=0.8, steps=6000, seed=0):
    rng = np.random.default_rng(seed)
    nodes, nbrs = make_grid()
    net = Network(nodes, nbrs, rng)
    rows, cols = 4, 4

    if policy_name == "qrouting":
        qr = QRouter(nodes, nbrs, alpha=0.5, eps=0.02, rng=rng)
        choose, fb = qr.choose, qr.feedback
    else:
        choose, fb = make_shortest_path(nbrs), None

    window = []
    for t in range(steps):
        # Poisson arrivals, mostly left-to-right traffic
        for _ in range(rng.poisson(load * 4)):
            src = (int(rng.integers(rows)), 0)
            dst = (int(rng.integers(rows)), cols - 1)
            net.inject(src, dst)
        net.step(choose, fb)
        if t % 500 == 499:
            recent = net.delivered[-500:]
            window.append((t + 1, np.mean(recent) if recent else float("nan"),
                           net.backlog()))
    return window

for name in ["shortest", "qrouting"]:
    print(name)
    for t, avg, backlog in run(name):
        print(f"  step {t:5d} | avg delivery time {avg:6.1f} | backlog {backlog}")

Watch the backlog column as well as delivery time. A policy that looks fast on delivered packets can hide a growing pile of stuck ones, so you need both numbers. Ever celebrated an average that ignored the failures?

What Results Should You Expect?

I cannot promise numbers, because they depend on your load, topology, and seed. In setups like this, the usual pattern looks like this:

  • At low load, both policies perform similarly, because queues stay short and the shortest path is also the fastest
  • At high load, static routing builds queues on the busy links while neighboring links sit underused
  • Q-routing spreads traffic and holds delivery times lower once its tables have learned
  • Early in training, Q-routing can lag, since its estimates start out as rough hop counts

This matches the qualitative finding in the original Q-routing paper: adaptive routing helps most under heavy load. Check that paper for the original experimental setup rather than treating my toy results as a replication.

Known Weaknesses of Q-Routing

Q-routing has real limitations, and honest tutorials should say so:

  1. Hysteresis: after a congestion spike passes, a node keeps avoiding the once-slow path, because greedy selection never retests it. The estimate stays stale and high.
  2. Slow adaptation to recovery: low-load periods give weak feedback, so tables update slowly.
  3. Exploration overhead: extra exploration fixes stale tables but sends some packets down bad paths.
  4. Routing loops: while estimates are still wrong, packets can bounce between nodes.
  5. Scaling: tables grow with destinations times neighbors at every node.

Researchers proposed fixes, including dual reinforcement Q-routing, which adds backward learning from the packet's path, and confidence-based variants that track how fresh each estimate is. Look up those papers for the details before relying on my summary.

How to Improve Your Implementation

Try these in order:

  1. Add a TTL. Drop packets that exceed a hop limit, so loops cannot stall the network.
  2. Tune alpha. Compare 0.1, 0.5, and 0.9. High values react fast but add noise.
  3. Tune epsilon. Test 0, 0.02, and 0.1, and watch recovery after a load spike.
  4. Change the load mid-run. Switch the hot spot halfway and measure how fast each policy adapts.
  5. Add link failures. Remove a link and see whether the tables reroute.
  6. Try a larger topology. Move from 4x4 to 8x8 and watch table size and learning time.

From Toy to Real Networks

Real networks add problems this simulator ignores:

  • Variable packet sizes and link speeds change the transmission term
  • Priority classes and QoS may forbid sending sensitive traffic down unpredictable paths
  • Control-plane constraints: production routers rely on standard protocols, and replacing them with learned policies requires careful safety work
  • Wireless and ad hoc networks face mobility and noisy links, which is where much follow-up research on Q-routing variants landed
  • Software-defined networking (SDN) offers a more realistic home for learned routing, since a controller can host the policy

For serious experiments, explore network simulators like ns-3, and check current surveys on deep RL for routing before choosing a direction. Verify tool details against current documentation.

Common Pitfalls

  1. Forgetting the delivered case. Without t = 0 at the destination, estimates never anchor.
  2. Measuring delivery time only. Track backlog too, or you will miss starvation.
  3. Comparing at one load level. Sweep the load, because Q-routing's advantage appears at high load.
  4. Skipping exploration entirely. Pure greedy routing locks in stale estimates.
  5. Weak baselines. Compare against shortest-path, and consider a load-aware baseline too.

Did you notice that most of these mistakes involve measurement, not the algorithm?

Best Book to Read

CoverBookDescriptionGet it
Cover of “Network Routing: Algorithms, Protocols, and Architectures” Network Routing: Algorithms, Protocols, and Architecturesby Deep Medhi and Karthikeyan Ramasamy the standard networking text covering OSPF, BGP, MPLS, and the QoS routing foundations that adaptive methods like Q-routing extend. View on Amazon

As an Amazon Associate I earn from qualifying purchases. Links on this page are affiliate links, and I may earn a commission at no extra cost to you.

Read it after you have run the code once. It makes the difference between "my Q-table spreads traffic on a 4x4 grid" and "this policy would survive a real AS" impossible to confuse.

Wrapping Up

Q-routing shows how simple a distributed learner can be: a table, a feedback message, and one update rule. It adapts to congestion with no central planner, though it carries real weaknesses like hysteresis and routing loops. Modern work extends the idea with deep networks and better exploration.

So run the script this week, then change one thing: the load, alpha, or the topology. If Q-routing beats shortest-path under heavy load, celebrate. If it does not, check your feedback rule first, then welcome the reminder that distributed systems enjoy humbling their builders.

Frequently Asked Questions

How does Q-routing differ from traditional routing protocols like OSPF?

OSPF computes routes from static link costs (usually hop count or configured weights) and reacts to topology changes. Q-routing learns delivery times from live traffic feedback, so it adapts to queue delays at packet timescales without a central controller.

Why does Q-routing need the 't = 0' rule when the next hop is the destination?

Without anchoring estimates to zero at the destination, Q-values have no ground truth to propagate back. The delivered packet provides the only absolute timing signal; all other updates are relative to that anchor.

What is hysteresis in Q-routing?

After congestion clears, a node keeps avoiding the once-slow path because pure greedy selection never retests it. The stale high estimate persists, so traffic stays detoured even when the path has recovered.

Can Q-routing create routing loops?

Yes. While estimates are still converging, packets can bounce between nodes that both think the other is the better next hop. Adding a TTL (time-to-live) hop limit prevents infinite loops.

How does this scale to real networks?

Tables grow with destinations times neighbors at every node. Real deployments use SDN controllers or hierarchical aggregation. Production routers also require safety guarantees that learned policies struggle to provide, so Q-routing remains mostly a research tool for adaptive routing.

Sources

  • [1] J. A. Boyan and M. L. Littman, Packet Routing in Dynamically Changing Networks: A Reinforcement Learning Approach (1993) — the original Q-routing paper with grid experiments and comparison to shortest-path: dl.acm.org/doi/10.5555/1866802.1866820
  • [2] Deep Medhi and Karthikeyan Ramasamy, Network Routing: Algorithms, Protocols, and Architectures — OSPF, BGP, MPLS, and QoS routing foundations: Amazon search
  • [3] S. Srivastava et al., Reinforcement Learning for Routing: A Survey — covers Q-routing variants, dual reinforcement, and deep RL approaches: arxiv.org/abs/2102.07152
  • [4] ns-3 documentation — the discrete-event network simulator with routing, Wi-Fi, and LTE modules: nsnam.org/documentation
  • [5] M. E. W. Erraji et al., Dual Reinforcement Q-Routing for Communication Networks — backward learning from packet paths to accelerate convergence: ieeexplore.ieee.org/document/6656727

What are You Looking For?

esc