Title:  On the Algorithmic aspects of Computation-Enabled Networks

Speakers: Danny Raz, Technion, Israel

Abstract:

In the recent years, a number of approaches have proposed either to add 
computational power into the network nodes (e.g. Active Networks) or to 
perform networking tasks in an overlay application layer (e.g. Application 
Layer multicast).  The result in both cases in a computation-enabled 
network.  This talks deals with the algorithmic power of networks whose 
internal nodes are capable of performing complex tasks.  We present 
a new model that captures both the ability to perform complex computations 
in elements, and the hop-by-hop forwarding mechanism.

Using this model, we present and analyze distributed algorithms for basic
problems that arise in the control and management of IP networks.  These 
problems include: route discovery, message dissemination, topology discovery, 
and general information collection.  In addition we use the model to 
analyze the optimality of different multicast trees. 

Our results prove that, although adding computation power to the internal 
nodes increases the message delay, it shortens the completion time for 
many tasks.  The suggested model can be used to evaluate the contribution of 
added features to a router, and allows the formal comparison of different 
proposed architectures.

The talk is based on joint papers with Yuval Shavitt and Evgeny Panman.