Network Modelling Meeting - Mar. 14

[Yong Wang <ywangb@cs.sfu.ca>]

NETWORK MODELLING GROUP

Friday, March 14, 14:00, ASB 9705

Speaker:  Yong Wang
          School of Computing Science

Title:    Routing Algorithms for Ring Networks

Coffee and cookies will be provided.
____________________________________________________________________________ 

I'd like to practice my Master thesis defence this time. Since this is the
first version, there will be many problems. I hope to get feedbacks from
you. Any suggestion will be highly appreciated. 

Abstract:

In this thesis, we study the routing problems on the ring networks.
Because of its simplicity and self-healing properties, the ring is a
popular topology for communication networks and has attracted much
attention.

A communication application on a ring network can be described by a set of
connection requests, each request specifies a set of nodes in the ring 
network to be connected. To realize the communication request, a routing 
algorithm is required to find a path to connect all nodes in each
connection request. A most important optimization problem for the
communication on the ring networks is to find a routing algorithm such
that the max congestion (the maximum number of paths that use any single
link in the ring) is minimized. If exactly two nodes are involved for
every connection request, this problem can be modelled as Minimum
Congestion Graphs Embedding in a Cycle (MCGEC) problem. If more than two
nodes can be involved in one connection request, this problem can be
modelled as Minimum Congestion Hypergraphs Embedding in a Cycle (MCHEC)
problem. Also, if we allow different connection requests can have
different bandwidth requirements, then the problem is known
as Minimum Congestion Weighted Hypergraph/Graphs Embedding in a Cycle
problem. The MCGEC problem can be solved in polynomial time but the other
two problems are known NP-complete.

In this thesis, we develop routing algorithms for these NP-complete 
problems. For the MCHEC problem, we propose algorithms in three
categories. The first one is a 1.8-approximation algorithm which improves
the previous results of 2-approximation. The second one is an algorithm
which finds the optimal solution by enumerating all "good" embeddings. The
algorithm can be used for the problem instances with constant maximum
congestions and is more efficient in time complexity than the previous
enumeration algorithm. The third one is heuristic algorithms. The
experimental studies show these heuristics can achieve good performance in
practice.

In the future, we will extend our research to the Weighted Graphs 
Embedding in a Cycle problem where every connection request can ask
for different bandwidth. In addition, combining routing and path
coloring is another further reasearch direction.