Efficient Tree-Based Content-Based Routing Schemes

Decanato - Facoltà di scienze informatiche

Data: 5 Febbraio 2018 / 15:30 - 17:00

USI Lugano Campus, room SI-003, Informatics building (Via G. Buffi 13)

You are cordially invited to attend the PhD Dissertation Defense of Koorosh KHAZAEI on Monday, February 5th 2018 at 15h30 in room SI-003 (Informatics building)



This thesis is about routing and forwarding for inherently multicast communication such as the communication typical of information-centric networks.

The notion of Information-Centric Networking (ICN) is an evolution of the Internet from the current host-centric architecture to a new architecture in which communication is based on “named information”'. The ambitious goal of ICN is to effectively support the exchange and use of information in an ever more connected world, with billions of devices, many of which are mobile, producing and consuming large amounts of data. ICN is intended to support scalable content distribution, mobility, and security, for such applications as video on demand and networks of sensors or the so-called Internet of Things.

Many ICN architectures have emerged in the past decade, and the ICN community has made significant progress in terms of infrastructure, test-bed deployments, and application case studies. And yet, despite the impressive research effort, the fundamental problems of routing and forwarding remain open. In particular, none of the proposed architectures has developed truly scalable name-based routing schemes and efficient name-based forwarding algorithms.

This is not surprising, since the problem of routing based on names, in its most general formulation, is known to be fundamentally difficult. In general, one would want to support application-defined names (as opposed to network-defined addresses) with a compact routing scheme (small routing tables) that uses optimal paths and minimizes congestion, and that admits to a fast forwarding algorithm. Furthermore, one would want to construct this routing scheme with a decentralized and incremental protocol for administrative autonomy and efficient dynamic updates. However, there are clear theoretical limits that simply make it impossible to achieve all these goals.

In this thesis we explore the design space of routing and forwarding in an information-centric network. Our purpose is to develop routing schemes and forwarding algorithms that combine many desirable properties. We consider two forms of addressing, one tied to network locations, and one based on more expressive content descriptors. We then consider trees as basic routing structures, and with those we develop routing schemes that are intended to minimize path lengths and congestion, separately or together.  For one of these schemes based on expressive content descriptors, we also develop a fast forwarding algorithm specialized for massively parallel architectures such as GPUs.

In summary, this thesis presents two efficient and scalable routing algorithms for two different types of networks, plus one scalable forwarding algorithm.


Dissertation Committee:

  • Prof. Antonio Carzaniga, Università della Svizzera italiana, Switzerland (Research Advisor)
  • Prof. Patrick Eugster, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Fernando Pedone, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Pascal Felber, Université de Neuchâtel, Switzerland (External Member)
  • Prof. Fabian Kuhn, University of Freiburg, Germany (External Member)