Jon Crowcroft on Opportunistic Networks and Human Mobility

Jon Crowcroft is a computer science researcher at the University of Cambridge. You can get a fairly good idea about his virtues and attitudes by reading through his webpage and papers, notably “Qos’s downfall: at the bottom, or not at all!” [1] and “Report from the Clean Slate Network Research post-SIGCOMM 2006 Workshop” [2]. Jon gave a talk last week at Imperial College, London, about a daring vision of a ubiquitous network formed by humans shown feasible by extensive, breath-taking experiments. In this article we will try to convey the key points of the talk.

All Together We Can Be One Big Mobile Ad-Hoc Wireless Network

The project Jon and his colleagues are working on concerns the delivery of data in a network with absolutely no infrastructure by making use of human mobility and local forwarding between wireless devices carried by people.

As Jon says:

[It’s about a] network that doesn’t have an end-to-end connectivity at any given moment, but you can construct a path by storing the data and then waiting a while, until things change and then forwarding them.

This can be also also expressed as a STORE – CARRY – FORWARD paradigm with the following meaning:

• “STORE” – in a portable devices we carry around (e.g a mobile phone)
• “CARRY” – carry the data in your device while you walk and travel around
• “FORWARD” – send data to another device on a short distance when appropriate using some wireless protocol (e.g. Bluetooth) and a forwarding protocol

Note that this idea falls into the area of “delay-tolerant networking” and “opportunistic communications”.

The rest of the talk aims at two fundamental questions:

• How does such network ever work?

and

• How to design a suitable forwarding protocol?

To answer the former question, we have to understand human mobility. Put simply – how many people we meet and what people they meet – parameters which allow us to estimate the chances that a message is delivered to its destination in a given time.

Adding Social Aspects to Human Mobility Modelling

As Jon notices, wireless networks have a dual nature – a physical one and a social one. Every person has multiple affiliations: few members of the family, colleagues at work, your friends who you meet occasionally, and, importantly, strangers who just happen to be in your proximity. It turns out that the social structures are vital to the feasibility of the network.

The iMote

(Picture is taken from “Pocket Switched Networks: Real-world mobility and its consequences for opportunistic forwarding” by Chaintreau, A., et al., available online at http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-617.html)

To obtain some confidence in how a network described above would perform, an amazing experiment has been carried out. (See [3] for details.) A large group of people were given a small Bluetooth-enabled device called iMote (in the picture above), which they carried around for several days. All the iMote does is it records contacts with other iMotes (time and ID). By processing the data from the iMotes at the end of the experiment, authors could map them to the personal data of the participants (with their informed consent) which included their affiliations, social connections, and other elements pertaining to their life style.

It is a little bit hard to describe the results of the experiments concisely. But one thing is for sure: we are all connected pretty well. It is perfectly realistic to expect that a message from any sender reaches any destination. The property to optimise is the delivery time. Note that these results are conservative (i.e. they are likely to be better in real world) as they stem from experiments with much smaller number of participants compared to the real world where every one carries a wireless device.

The reader may be interested in learning that the social structure of the network can be characterised using the concept of community-cliques and centrality, and that the parameter crucial to the functionality of the opportunistic network is the inter-contact time defined as the time interval between two consecutive contacts between a pair. The experiments show that the inter-contact probability distribution is heavy-tailed and similar to the approximate power law shape. Quoting [3], “This is contrary to the exponential decay of many mobility models put forward in the literature. As a result, opportunistic networking algorithms which have been designed around exponential models must be re-evaluated in the light of our observations.”

Having obtained a solid confidence in the feasibility of such network from iMote experiments, the problem to tackle now is the design of a suitable forwarding protocol.

Designing a Forwarding Protocol

Imagine you are standing in a crowd, your next generation phone storing some data to be sent. A forwarding protocol will decide which device in your proximity will be used to propagate your data further. Note that there isn’t any holy grail in the search for a forwarding protocol and author do not claim the proposed protocol is optimal.

When routing a packet in a wired network, we choose the next hop according to some parameter describing the next hop (e.g. its distance from the destination). What are the key parameters describing a node (a person) in terms of its suitability as the next hop?

• Node’s popularity — how many other nodes it encounters
• Node’s affiliations — what social groups it encounters

The forwarding protocol can be based on these characteristics in a number of ways. Jon takes us through simple protocols such as the RANK protocol which forwards data to highly centric nodes (the guy on the corner selling peanuts would be an absolutely brilliant forwarding node) or the LABEL protocol which uses nodes with the same affiliation as the destination node, showing the probabilities of successful delivery as a function of delivery time. The BUBBLE protocol uses popularity to “bubble up” through different social groups until it finds a node with a good connection to the target group. Then it travels between social groups using nodes’ affiliation labels.

In all this Jon emphasises the need for modeling of heterogeneity at multiple levels. For example, a postman is a highly central node in the sense that he meets a lot of people, but not any particular social group, whereas a conference chair may be an asocial loner with high centrality in geeky circles. The BUBBLE protocol reflects this.

Issues, Bits & Pieces and a Conclusion

User privacy is a major concern here. Even though the forwarding protocol does not need concrete information about your affiliations, the idea that others might know about your social structure is disturbing. Another open issue is the way people would be motivated to participate in the network. A highly popular node will surely drain its battery sooner for example, and needs to be compensated for this. How to include incentives in the network? And, naturally, how to deal with malicious use?

Issues aside, we saw this exciting proposal of an opportunistic network shown feasible by extensive emulations. Reading through the paper Network Architecture Research Considerations Or The Internet Conspiracy at the online edition of the Computer Communication Review , you can notice that this project goes well in line with the philosophy of no-network-architecture-at-all.

But most importantly, this work presents, in my opinion, a great example of a bold, visionary and yet pragmatic research. If you are after fresh research ideas in the post-Internet era, keep your eyes on Crowcroft.

The presentation slides for the talk are now available here.

References

[1] Jon Crowcroft, Steven Hand, Richard Mortier, Timothy Roscoe, and Andrew Warfield “Qos’s downfall: at the bottom, or not at all!” In RIPQoS ’03: Proceedings of the ACM SIGCOMM workshop on Revisiting IP QoS, pages 109–114, New York, NY, USA, 2003. ACM Press.

[2] Crowcroft, J. and Key, P. 2007. “Report from the clean slate network research post-sigcomm 2006 workshop” SIGCOMM Comput. Commun. Rev. 37, 1 (Jan. 2007), 75-78. DOI=http://doi.acm.org/10.1145/1198255.1198268

[3] Chaintreau, A., Hui, P., Crowcroft, J., Diot, Ch., Gass, R., Scott, J. “Pocket Switched Networks: Real-world mobility and its consequences for opportunistic forwarding”. Technical Report, Number 617. ISSN 1476-2986. University of Cambridge Computer Laboratory, February 2005. Available online at http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-617.html.

Advertisement