Node-Capacitated Multicommodity Routing for a Ring

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 pair 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 ring routing algorithm which was suggested by the preceding results.