Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM9820November 1998 
A. Frank, F.B. Shepherd, V. Tandon, and Z. Vegh
Abstract
We consider a routing problem which arises in the development of an algorithm which assigns routes in realtime to incoming path requests (calls) between pairs of nodes in a passive optical local network. For the application addressed, this led to an integral multicommodity flow problem on a ring. In the version of this problem where capacities are on the edges, a characterization for the existence of a solution followed from work of OkamuraSeymour and Frank. The application discussed here, however, leads to capacities being on the nodes of the ring. We give necessary and sufficient cut conditions for this fractional flow problem in the case where there are capacities on the nodes (and/or edges). This yields a polynomial time algorithm to determine whether such a flow exists. We also see that if we increase the capacity of each link by one, then we may always find an integral routing. Finally, we give simulation results for an online routing algorithm which was suggested by the preceding results. These showed that blocking in a network can be delayed by departing from a strict shortest path routing regime, even in the case of wavelength routing. This suggests that linear programming cut conditions could be used as measure for how not to route calls in realtime.
A compressed (gzip) PostScript file (64 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you like a free hard copy of this report, please send the number of this report, LSECDAM9820, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)171955 7732. Fax: +44(0)171955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html