End-to-end delay margin balancing approach for routing in multi-class networks

This paper presents Quality of Service (QoS) based routing and priority class assignment algorithms. It introduces an end-to-end delay margin balancing approach to routing, and uses it to formulate a nonlinear optimization problem. In a single-class network, the formulation is shown to be convex; however in a multi-class priority network, it is only convex within specific regions, and is infeasible otherwise. A centralized off-line computation technique is proposed to calculate both the route configuration and end-to-end priority assignment. A gradient-based solution in the convex region and a heuristic to overcome the multi-class discontinuity are derived. An approximation of the optimization problem is developed for on-line distributed processing is then presented. Using the approximation, arriving traffic flows can use vector routing tables to search for routes. Compared with minimum-hop, minimum-delay, and min-interference routing algorithms, the proposed approach enables the single-class network to accommodate more users of different end-to-end delay requirements. In a multi-class priority network, results show that using the objective function to combine route and priority class assignment further increases the supportable network traffic volume. Mohamed Ashour received his B.Sc. (1991) and M.Sc. (1997) in Electrical Engineering from Ain Shams University, Cairo, Egypt. He worked for Hughes and General Dynamics as a Telecommunications Engineer. Currently, he is a Ph.D. Candidate in the Department of Electrical and Computer Engineering of McGill University, Montreal, Quebec, Canada. His current area of research is focused on traffic engineering, routing, and QoS provisioning in DiffServ and MPLS Networks. He is also interested in multi-class queuing analysis of long-range traffic, and QoS provisioning in ad hoc networks and satellite communications. Tho Le-Ngoc obtained his B. Eng. (with Distinction) in Electrical Engineering in 1976, his M.Eng. in Microprocessor Applications in 1978 from McGill University, Montreal, and his Ph.D. in Digital Communications 1983 from the University of Ottawa, Canada. During 1977–1982, he was with Spar Aerospace Limited as a Design Engineer and then a Senior Design Engineer, involved in the development and design of the microprocessor-based controller of Canadarm (of the Space Shuttle), and SCPC/FM, SCPC/PSK, TDMA satellite communications systems. During 1982–1985, he was an Engineering Manager of the Radio Group in the Department of Development Engineering of SRTelecom Inc., developed the new point-to-multipoint DA-TDMA/TDM Subscriber Radio System SR500. He was the System Architect of this first digital point-to-multipoint wireless TDMA system. During 1985–2000, he was a Professor the Department of Electrical and Computer Engineering of Concordia University. Since 2000, he has been with the Department of Electrical and Computer Engineering of McGill University. His research interest is in the area of broadband digital communications with a special emphasis on Modulation, Coding, and Multiple-Access Techniques. He is a Senior Member of the Ordre des Ingénieur du Quebec, a Fellow of the Institute of Electrical and Electronics Engineers (IEEE), a Fellow of the Engineering Institute of Canada (EIC), and a Fellow of the Canadian Academy of Engineering (CAE). He is the recipient of the 2004 Canadian Award in Telecommunications Research, and recipient of the IEEE Canada Fessenden Award 2005.