** **

**Gordon Wilfong, Distinguished Member of Technical Staff**

**Mathematics of Network Systems group, Bell Labs**

**Modeling Routing Problems as Graph Orienting Problems**

**Wednesday, October 23, 4:00 PM **

**Packard Lab room 208**

**Reception in Packard Lab 216 prior to seminar**

**Abstract: **We consider a number of applications in network routing that lead to problems involving orienting the edges of an undirected graph. In particular, we consider a problem concerned with minimizing the maximum table size in an interval routing network and show that this is equivalent to finding an orientation that minimizes the maximum indegree in a strongly connected digraph. Another application has to do with avoiding routing deadlocks due to full buffers and this leads to the problem of orienting a graph to make the indegrees as uniform as possible in an acyclic digraph. Finally we look at the problem of assigning responsibility for route recovery to source or sink node for each route so as to not burden any node too much. We model this as the problem of orienting a graph so that indegrees of the nodes are as equal as possible without any further constraints on the resulting digraph.

This is joint work with G. Borradaile (OSU), J. Iglesias (CMU), T. Migler (OSU), A. Ochoa (OSU) and L. Zhang (Bell Labs)

**Bio: **Gordon Wilfong is a Distinguished Member of Technical Staff in the Mathematics of Network Systems group at Bell Labs. He received his B.Sc., First Class Honours, in mathematics from Carleton University in 1980 and his M.S. and Ph.D. in computer science from Cornell University in 1983 and 1984 respectively. In 2010 he was received the ACM SIGCOMM Test of Time Award for his work on the analysis of the routing protocol BGP.