Analysis of dynamic QoS routing algorithms for MPLS networks

Finding a path in the network for each traffic flow able to guarantee some quality parameters such as bandwidth and delay is the task of QoS routing algorithms developed for new IP networks based on label forwarding techniques as Multiprotocol Label Switching (MPLS). In this paper we focus on Dynamic QoS Routing, i.e. the routing of bandwidth guaranteed flows in a dynamic scenario where new connection requests arrive at the network edge nodes. When more than one path satisfying the bandwidth demand exists, the selection of the path aims at minimizing the blocking probability of future requests. We propose two novel mathematical programming models that assume the knowledge of arrival times and durations of connection requests, and provide theoretical bounds to the performance achievable by on-line routing algorithms. We compare to such bounds the performance of the Min-Hop (MH) algorithm, the Minimum Interference Routing Algorithm (MIRA) and the recently proposed Virtual Flow Deviation (VFD) algorithm. We show that the blocking probability of this new algorithm, in most scenarios, is quite close to the bound.