« Axis and caching | Main | Shark jumping Google revisited »

Optimal routing policies

Underway in Ireland

From personal experience, mostly gleaned by peering over the shoulder of Liam Noonan's bandwidth throttling research, I know that adding more interconnections to a network doesn't improve service. As the Columbia paper shows, you might run into something called Braess' paradox, which says that if you introduce more interconnections so that messages can hop from one path to another partway along, this actually makes the trip longer for everyone -- pretty much like changing lanes in a traffic jam.

Exactly. Now if you could get the people charged with uneviable task of determining the UK and Ireland's transport policies to take some lessons from networking, queing theory and logistics I'd have some more faith in the future of transport infrastracture for both countries.

Solutions in routing could be achieved using reinforcing pheromone trails (as ants do). These are interesting because the paths dissipate quickly after going unused. Eric Bonneabeau among others has interesting results in this area. A technology worth looking at for routing policies is Reinforcment Learning (using a Markov decision process or Q-learning). I'm pretty sure the future of cache management, heap sizing and object/thread pooling lies with reinforcement learning - eventually the penny drops that you can get the computer to figure out what to do instead of having to confugure it by hand. To close the Irish angle, there's a chap at DCU Mark Humphries, who has extended Q-learning in his PhD.

February 17, 2003 10:50 PM


Trackback Pings

TrackBack URL for this entry: