Toronto Networking Seminar


Organized by Department of Computer Science and
Department of Electrical and Computer Engineering, University of Toronto







A Memory-Efficient Per-Source Routing Scheme for Content-Based Networks





Antonio Carzaniga


Faculty of Informatics


University of Lugano




Date:  Friday, September  12,  11am

Location: BA 2165



Abstract:




Content-based networking is a message-oriented communication service in which a
message is delivered to all destinations that have declared a selection
predicate matching the content of that message.  A content-based network can be
seen as the implementation of, or the basis for a large-scale distributed
publish/subscribe system.  One of the crucial elements of the design of a
content-based network is its routing scheme.  In this talk, I will discuss two
aspects of the problem of routing in content-based networking.  First, I will
propose a general design framework, derived from that of a traditional
address-based network, where a routing scheme can be formally defined and
analyzed.  Within this framework, I will focus on the memory complexity of a
scheme--in simpler terms, the size of the forwarding tables--which is arguably
the most fundamental measure of scalability. Second, I will propose a concrete
routing scheme based on per-source trees.  In its most basic form, per-source
routing requires routers to store their local view of the spanning tree of each
source and annotate them with the predicates of all downstream destinations.
This leads to large forwarding tables that seriously limit the scalability of
the scheme.  The scheme I will present improves upon this basic idea by
allowing routers to group sources in equivalence classes, and also by grouping
destination selection predicates. Furthermore, I will show that a simple
variation of this scheme used in combination with a particular type of
forwarding algorithm achieves substantial reductions in forwarding table size,
making it effective in practical scenarios.




Bio:



Antonio Carzaniga is an Assistant Professor at the Faculty of Informatics of
the University of Lugano, Switzerland, since 2004.  From 2002 to 2007, he was
also an Assistant Research Professor at the Department of Computer Science at
the University of Colorado at Boulder. He received the Laurea degree in
Electronic Engineering and the Ph.D. degree in Computer Science from
Politecnico di Milano, Italy, in 1994 and 1999, respectively.  Antonio
Carzaniga has conducted research and published in the areas of software
process, mobile code, distributed configuration management, software
deployment, testing and validation of distributed systems, and distributed
publish/subscribe middleware and networking.  Currently, his primary research
interests are in the design and realization of advanced communication systems,
such as content-based networking, with a particular emphasis on both the
algorithmic aspects of routing protocols, and the engineering methods that make
those systems and protocols usable, scalable, robust, and secure.




Host of the talk



Hans-Arno Jacobsen (jacobsen@eecg.toronto.edu)