Speaker: Rachid Saad
Time:    Monday, October 27, 11:00-12:00
Place:   Room HP4351, Herzberg Building, Carleton University
Title:   The Forwarding Indices of Interconnection Networks

Abstract: Forwarding Index (FI) problems are purely graph-theoretic
problems arising in connection with the interconnection networks in
distributed systems. It is formulated in terms of "routings" and loads as
follows:
A routing R of a graph G of order n is a set of n(n-1) paths specified
for all ordered pairs of nodes in G.
Now, given a routing R of G and a node x, the load of x with respect to R
denoted by (G,R,x) is the number of routes of R containing x as an
internal node. The FI problem is to find a routing which minimizes the load of
 any node in G, that is: min_R max_x (G,R,x)
The motivation of the problem is quite clear in the context of
interconnection networks: the load of a vertex can be thought of as a
queue of messages, and the max load acts as a botteleneck to the system
to be kept as small as possible.
In this talk, I will present some upper bounds on the FI related to the
connectivity of G.