Routing and Call Control Algorithms for Ring Networks

A vast majority of communications in a network occurs between pairs of nodes, each such interaction is termed a call. The job of a call control algorithm is to decide which of a set of calls to accept in the network so as to maximize the number of accepted calls or the profit associated with the accepted calls. When a call is accepted it uses up some network resources, like bandwidth, along the path through which it is routed. The call control algorithm needs to make intelligent trade-offs between resource constraints and profits. We investigate two variants of call control problems on ring networks; in the first, the algorithm is allowed to determine the route connecting the end nodes of a call, while in the second, the route is specified as part of the input. For the first variant, we show an efficient algorithm that achieves the objective of routing and maximizing the number of accepted calls within an additive constant of at most 3 to an optimal algorithm. For the fixed path variant, we derive a 2-approximation for maximizing the profits (which could be arbitrary) of accepted calls. For several important special cases we show polynomial time optimal algorithms.