paper a day : last encounter routing with EASE

Locating Mobile Nodes with EASE : Learning Efficient Routes from Encounter Histories Alone
M. Grossglauser and M. Vetterli
IEEE/ACM Transactions on Networking, 14(3), p. 457- 469

This paper deals with last encounter routing (LER), a kind of protocol in which location information for nodes is essentially computed “on the fly” and there is no need to disseminate a location table and update it. They consider a grid toplogy (a torus, actually) on which nodes do a simple random walk. The walk time is much slower than the transmission time, so at any moment the topology is frozen with respect to a single packet transmission. Every node i maintains a table of pairs (Pij, Aij) for each other node j where P is its last known position and A is the age of that information. In the Exponential Age SEarch protocol (EASE) and GReedy EASE (GREASE), a packet keeps in its header an estimate of the position of its destination, and rewrites that information when it meets a node with a closer and more recent estimate. Because the location information and mobility processes are local, these schemes performs order-optimally (but with worse constants) to routing with location information, and with no overhead in the cost.

In particular, EASE computes a sequence of anchors for the packet, each one of has an exponentially closer estimate of the destination in both time and space. For example, each anchor could halve the distance to the destination as well as the age of that location estimate. This is similar in spirit to Kleinberg’s small world graphs paper, in which routing in a small world graph halves the distance, leading to a log(n) routing time, which comes from long hops counting the same as local hops. Here long hops cost more, so you still need n1/2 hops. The paper comes with extensive simulation results to back up the analysis, which is nice.

What is nicer is the intuition given at the end:

Intuitively, mobility diffusion exploits three salient features of the node mobility processes: locality, mixing, and homogeneity…
Locality ensure[s] that aged information is still useful… Mixing of node trajectories ensures that position information diffuses around this destination node… Homogeneity ensure[s] that the location information spreads at least as fast as the destination moves.

The upshot is that location information is essentially free in an order sense, since the mobility process has enough memory to guarantee that suboptimal greedy decisions are not too suboptimal.


Reads 2007 No. 1

I used to write a lot about each book I read but of course I don’t have the time. And besides, I haven’t been reading as quickly as I used to. Unfortunately my dream of more theory/nonfiction hasn’t come to fruition. So besides The New Yorker and Harpers I’ve delved into some more reads:

The Thursday Next Novels : The Eyre Affair, Lost In a Good Book, The Well of Lost Plots, Something Rotten (Jasper Fforde) — a bit of brain candy, these, but a lovely bit of literary comedy. It’s like Terry Pratchett with an ear for the classics (which I haven’t really read, truth be told). The books follow a Special Operations agent named Thursday Next, who lives in a world in which the line between fiction and reality is permeable, and in which there is a special division for literary crimes. What fun! Actually, the best part about it is that it actually makes me want to go back and read Great Expectations and the like. Even Jane Austen seems like it could be fun after these books, despite my falling asleep the last time I tried to read her. Maybe I have become more sensitive over time…

The Big Over-Easy (Jasper Fforde) — A spin-off series from the above, with a similar sensibility. Who wouldn’t like a murder mystery set in a world in which nursery rhyme characters populate the town? It’s more like Who Framed Roger Rabbit? than The Thin Man, so noir fans beware.

Speaking of Siva (AK Ramanujan)) — This was a slim volume of Bhakti-movement poems (vacanas, or utterances) from the Virasaiva community and were translated from the original Kannada. The poems themselves are quite beautiful — like most Bhakti poems, they get at the heart of what love and God and the self are in a relatively un-self-conscious way. One of the poems, by Allama Prabhu, is used in A Flowering Tree, the new John Adams opera that I am singing as part of a semi-staged SF Symphony concert at the beginning of next month. As one of the few, if only, South Asian singers in that concert, I feel a particular need to educate myself about the textual underpinnings. The poem was translated into Spanish before being set into music, and I’m not sure the music is appropriate to the relgious/philosophical outlook of the poem. Adams is free to set the poem as he likes, and he isn’t trying to don some mantle of authenticity, so I find his musical choices interesting, but I think the text serves his end, rather than the reverse. Perhaps I will write more on that later.

I’m currently working on a number of books in parallel. More when I actually finish some of them.