Asynchronous transfer mode networks with multiple service classes and parallel links

The problem that we are studying is how to route messages having different delay sensitivities over an ATM based fiber optic network with parallel links. The capacities of the communication links, the topology of the network and the cost structure are known and it is assumed that the messages belong to different priority classes to account for the difference in delay requirements. Decisions need to be made about how to distribute the load over the parallel links when predetermined delay guarantees for the different service classes are to be met. We also address the issue of how to decide what price to charge from the users who are requesting delivery of messages belonging to different priority classes under certain quality of service (in terms of delay) constraints. We model the ATM network as a network of M/D/c queues. The parallel links are viewed as \u27c\u27 servers and the messages as customers. The routing and pricing problem is formulated as a nonlinear mixed integer program. This problem being an NP-Hard problem, the method of Lagrangean Relaxation is used for obtaining lower bounds to the optimal solution. Subgradient optimization is used to obtain estimates of the \u27best\u27 Lagrange multipliers and these multipliers give the \u27shadow priority prices\u27 for the different service classes. Efficient heuristics are suggested for generating feasible solutions that provide a guarantee about the quality of the solution generated by the Lagrangean procedure. The model is run for an example network and a mechanism is devised that trades off the various costs involved in the process of network design. In our research, there is fundamental contribution from queuing theory perspective. Calculation of mean waiting time for multi-server priority queues is known to be a complex problem. As part of our research we have obtained analytical expressions for mean waiting time of different priority classes with exponential arrival and fixed service time. The analytical model that we proposed is a close approximation of current backbone networks and hence the results of our research would be of great significance to network service providers, network designers and also network users