Department of Computer Science and Technology

Technical reports

Bubble Rap: Forwarding in small world DTNs in ever decreasing circles

Pan Hui, Jon Crowcroft

May 2007, 44 pages

DOI: 10.48456/tr-684


In this paper we seek to improve understanding of the structure of human mobility, and to use this in the design of forwarding algorithms for Delay Tolerant Networks for the dissemination of data amongst mobile users.

Cooperation binds but also divides human society into communities. Members of the same community interact with each other preferentially. There is structure in human society. Within society and its communities, individuals have varying popularity. Some people are more popular and interact with more people than others; we may call them hubs. Popularity ranking is one facet of the population. In many physical networks, some nodes are more highly connected to each other than to the rest of the network. The set of such nodes are usually called clusters, communities, cohesive groups or modules. There is structure to social networking. Different metrics can be used such as information flow, Freeman betweenness, closeness and inference power, but for all of them, each node in the network can be assigned a global centrality value.

What can be inferred about individual popularity, and the structure of human society from measurements within a network? How can the local and global characteristics of the network be used practically for information dissemination? We present and evaluate a sequence of designs for forwarding algorithms for Pocket Switched Networks, culminating in Bubble, which exploit increasing levels of information about mobility and interaction.

Full text

PDF (1.0 MB)

BibTeX record

  author =	 {Hui, Pan and Crowcroft, Jon},
  title = 	 {{Bubble Rap: Forwarding in small world DTNs in ever
         	   decreasing circles}},
  year = 	 2007,
  month = 	 may,
  url = 	 {},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-684},
  number = 	 {UCAM-CL-TR-684}