The adversarial packet routing problem is defined as follows:
We are given a graph G = (V,E).
In each round t, an adversary gets to insert packets at nodes of G.
Each packet has a destination in V. An algorithm gets to move packets
along edges of the graph (only one packet may cross any one edge in
each time step) - when a packet reaches its destination, it is
absorbed (disappears). 
To give the algorithm a chance in the first place, the adversary can
only insert packets such that there is a multi-commodity flow between
the (source, sink) pairs for each round.
The kind of algorithms that we are interested in are
decentralized. The basic idea is that a node u only sends a packet
with destination t to a neighbor v if u has more packets with
destination t than v does. Thus, a "gradient" should develop into the
destinations. When multiple destinations have a gradient for edge
e=(u,v), then the packet is sent that maximizes the difference in
queue heights. 

The big goal is to prove that this algorithm is "stable", i.e. that
all queue sizes stay bounded by a constant, independent of the time t
(althogh probably depending on n).

Aiello, Kushilevitz, Ostrovsky, Rosen 
(available at http://citeseer.nj.nec.com/aiello98adaptive.html)
prove that this algorithm is stable if the adversary has rate
(1-epsilon), in the sense that there is a multi-commodity flow when
all edges have capacity (1-epsilon).

Awerbuch, Berenbrink, Brinkmann, Scheideler were the first to prove
stability at rate 1, but only when all packets have the same
destination. Their proof is quite technical, mostly because they
consider dynamic networks, in which edges appear and dissapear.

Elliot, Jon, and David (available at
http://www.cs.cornell.edu/people/eanshel/papers/stoc02-bal.ps) 
prove the same, but with a much simpler proof (Section 4).
Martin has suggested interpreting this proof as maintaining an
invariant over all integer solutions to the dual LP for
multi-commodity flow, and the proof goes through if we consider *all*
dual solutions instead. Maybe, that would help somewhere.

The big and interesting question is whether we can generalize the proof
technique somehow to multiple destinations of packets.
Suggested reading is the Aiello et al. paper (at least for definitions
etc.), and Section 4 of the EJD paper, as well as any sections
necessary to understand Section 4 well.