Why did I go to the presentation? That's because I talked to Michael about his research today morning and I found it interesting.
The topic was implementing an efficient DHT on an ad-hoc mobile network. Efficient DHTs for fixed-line, broadband Internet are already there, like Chord and Pastry, and everybody is using those knowingly or unknowingly. Michael's research is about how to make DHTs efficient on ad-hoc mobile networks, which is much harder than implementing DHTs on top of our everyday IP network. Some difficulties include:
1. Message routing. Mobile nodes do not and should not have fixed routes like our desktop computers. Although routing on the physical network can be partially solved by things like AODV, you still have to make sure the hops on the DHT's overlay network are efficient. e.g. assuming you've got perfect data routing in the physical network, it's still useless if one of the DHT hops goes to another country with a 12-hour timezone difference - your message will be hopping across many many many nodes in the physical network for just one DHT hop.
2. Bandwidth overhead. (??) I don't know how bad the problem is since I haven't seen the simulations myself. Probable causes I've heard are AODV-style flooding and Bloom filter inefficiencies. Gnutella-style implementations were mentioned for the audience to point and laugh at, I guess.
One of the related papers to M and J's work:
Now what's Michael and John's proposed solution... They proposed a DHT that's organized in a tree-like fashion, instead of the ring/skip list type seen in Chord or Pastry. The root node in the tree is called a "landmark", which should have a fixed location and has no extra hardware resource requirements when compared to other nodes. Their algorithm takes care of the physical routing as well so there's no need for AODV flooding or playing with Dijkstra's algorithm as in SrcRR. No AODV, no route request flooding, less bandwidth overhead. Bloom filters are used in narrowing/selecting paths in the tree, which is very intuitive and easy to understand (just a simple trick with bits, with the hard probability maths done for you 30 years ago), despite the seemingly cryptic name.
Prof. Gary Chan asked lots of questions during the presentation, he had a very sharp sense for things that seemed to be "strange" or inefficient. The object duplication algorithm (put in there to make p2p swarming possible) in John's presentation was one of the quirks Gary spotted, the algorithm seemed like a placeholder, I guessed it shouldn't be too hard to correct though.
So what I've got from the seminar... let's see
1. Revision of some old algorithms (Bloom filters... I almost forgot them completely, never used them once in the past few years), learned some new ones, and some new problems.
2. The 40 minutes presentation time I've got for my FYP is preciously short. Michael and John's presentation went for like 1.5 hours, and they were still missing on some details.
3. I need to keep my audience interested by doing demonstrations, with both WT Toolkit and WT Toolkit's competitors.