On the performance of dynamic online QoS routing schemes

Several dynamic QoS routing techniques have been recently proposed for new IP networks based on label forwarding. However, noextensive performance evaluation and comparison is available in the literature.In this paper, after a short review of the major dynamic QoS routing schemes, we analyze and compare their performance referringto several networks scenarios. In order to set an absolute evaluation ofthe performance quality we have obtained the ideal performance of anyrouting scheme using a novel and flexible mathematical programmingmodel that assumes the knowledge of arrival times and duration of theconnections offered to the network. This model is based on an extensionof the maximum multi-commodity flow problem. Being an integer linearprogramming model, its complexity is quite high and its evaluation isconstrained to networks of limited size. To overcome the computationalcomplexity we have defined an approximate model, based on the multiclass Erlang formula and the minimum multi-commodity cut problem,that provides an upper bound to the routing scheme performance. Theperformance presented in the paper has been obtained by simulation. From the comparison of the schemes considered it turns out that the Virtual Flow Deviation routing algorithm performs best and it almostreaches, in several scenarios, the ideal performance showing that no much gain is left for alternate new schemes.