Optimal routing and flow control in networks with real-time traffic
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 784-791 vol.3
- https://doi.org/10.1109/infcom.1989.101527
Abstract
The authors address the problem of flow control and routing of real-time traffic in a network, where messages must arrive at their destination within given deadlines if they are not to be considered lost. Performance in this case is measured in terms of the probability of losing a message. For the case of n parallel links, the problem is formulated as one of optimal flow allocation and solved under general conditions. It is shown that for a FCFS (first-come first-served) service discipline an admission policy rejecting messages before link assignment is optimal when the load exceeds a critical value. Thus, the authors take advantage of the fact that if some messages will exceed their deadlines anyway, it is beneficial not to admit them in the first place. An efficient algorithm for explicitly solving the problem is presented and specific examples are analyzed. The authors also discuss the applicability of online algorithms for this problem when modeling assumptions cannot be made.Keywords
This publication has 9 references indexed in Scilit:
- Discrete event systems with real-time constraints: modeling and sensitivity analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On-line sensitivity analysis of Markov chainsIEEE Transactions on Automatic Control, 1989
- Applications of Perturbation Techniques to Optimal Resource Sharing in Discrete Event SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Load Sharing in Soft Real-Time Distributed Computer SystemsIEEE Transactions on Computers, 1987
- Optimal priority assignment with hard constraintIEEE Transactions on Automatic Control, 1986
- Adaptive load sharing in homogeneous distributed systemsIEEE Transactions on Software Engineering, 1986
- Sensitivity analysis via likelihood ratiosPublished by Association for Computing Machinery (ACM) ,1986
- Optimal static load balancing in distributed computer systemsJournal of the ACM, 1985
- The Markovian Queue with Bounded Waiting timeManagement Science, 1977