Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-98-20 November 1998

Abstract

We consider a routing problem which arises in the development of an algorithm which assigns routes in real-time 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 Okamura-Seymour 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 on-line 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 real-time.

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, LSE-CDAM-98-20, 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)-171-955 7732. Fax: +44(0)-171-955 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