Network seminar - Friday,

[Joseph Peters <peters@cs.sfu.ca>]

NETWORK MODELLING GROUP

Friday, November 1, 13:30, ASB 10820

Speaker:  Yong Wang

Title:    Demand Routing and Slotting on Ring Networks

Coffee and cookies will be provided.
____________________________________________________________________________

Abstract:

Demand Routing and Slotting Problem (DRSP) arises from constructing SONET
ring to minimize cost. The problem is desribed as follows:

Given a set of demands (connection requests) D on an n-node
ring, and every demand d in D is represented by a triple (s_{d}, t_{d},
k_{d}) where s_{d}, t_{d} and k_{d} are respectively the source node,
destination node and size of demand d. The k_{d} units of demand d can't 
be split and they must be routed together either clockwise or 
counterclockwise. In addition, the route for every unit of one demand
should be assigned a slot on the ring such that no two routes that 
overlap have an assigned slot in common. The objective is to minimize
the number of used slots.

It has been proved that the DRSP on Rings is NP-complete. In my talk I
will present two known 2-approximation algorithms for solving this
problem. Also I will give a brief introduction for some other variants 
of DRSP on Rings.