Unstable Network Routing

Dynamic Topology:

Links fail & Recover

On each input & Dynamic topology:

Throughput is Competitive with offline algorithm.

Main idea:

Packets moved by “Local gravity”

Distributed Online Algorithm: Packet delivery from source to sink.