Title :
QoS routing algorithms for pre-computed paths
Author :
Pornavalai, Chotipat ; Chakraborty, Goutam ; Shiratori, Norio
Author_Institution :
Res. Inst. of Electr. Commun., Tohoku Univ., Sendai, Japan
Abstract :
Routing with multiple QoS constraints is known to be a NP-complete problem. In our previous work (QoSRBF algorithm), we have shown that, for a number of specific QoS constraints, this problem can be solved in polynomial time, when a weighted fair queueing (WFQ) service discipline is employed. QoSRBF is an on-demand algorithm. We propose a number of QoS routing algorithms for pre-computed paths, when all or some of the flow specification parameters and the amount of bandwidth that has to be reserved are not known a priori. We also show that the size of the routing table could be reduced, as paths satisfying some conditions could be neglected
Keywords :
computational complexity; queueing theory; telecommunication network routing; NP-complete problem; QoS routing algorithms; QoSRBF on-demand algorithm; bandwidth; flow specification parameters; multiple QoS constraints; pre-computed paths; routing table size reduction; Arthritis; Bandwidth; Delay effects; Jitter; NP-complete problem; Polynomials; Routing; Telecommunication traffic; Time factors; Traffic control;
Conference_Titel :
Computer Communications and Networks, 1997. Proceedings., Sixth International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
0-8186-8186-1
DOI :
10.1109/ICCCN.1997.623320
