Sébastien Henri
ABSTRACT
In all networks, link or route capacities fluctuate for multiple reasons, e.g., fading and multi-path effects on wireless channels, interference and contending users on a shared medium, varying loads in WAN routers, impedance changes on power-line channels. These fluctuations severely impact packet delays. In this paper, we study delays in time-varying networks. Intuitively, we expect that for a given average service rate, an increased service rate variability yields larger delays. We find that this is not always the case. Using a queuing model that includes time-varying service rates, we show that for certain arrival rates, a queue with larger service rate variance offers smaller average delays than a queue with the same average service rate and lower service rate variance. We also verify these findings on a wireless testbed. We then study the conditions under which using simultaneously two independent paths helps in terms of delays, for example, in hybrid networks where the two paths use different physical layer technologies. We show that using two paths is not always better, in particular for low arrival rates. We also show that the optimal traffic splitting between the two paths depends on the arrival rate.
- https://multipath-tcp.org/pmwiki.php/Users/OpenWRT.Google Scholar
- https://wiki.openwrt.org/doc/networking/praxis.Google Scholar
- IEEE 1905.1-2013 Standard for Heterogeneous Technologies. 2013.Google Scholar
- IMT-Vision - Framework and overall objectives of the future development of IMT for 2020 and beyond. Recommendation ITU-R, 2015.Google Scholar
- I. J.-B. F. Adan and V. G. Kulkarni. Single-Server Queue with Markov-Dependent Inter-Arrival and Service Times. Queueing Systems, 2003. Google ScholarDigital Library
- O. T. Akgun, R. Righter, and R. Wolff. Multiple-server System with Flexible Arrivals. Advances in Applied Probability, 2011.Google Scholar
- C.-S. Chang, X. Chao, and M. Pinedo. A Note on Queues with Bernoulli Routing. In IEEE CDC, 1990.Google ScholarCross Ref
- Y.-C. Chen, Y.-s. Lim, R.J. Gibbens, E. M. Nahum, R. Khalili, and D. Towsley. A Measurement-based Study of Multipath TCP Performance over Wireless Networks. In ACM IMC, 2013. Google ScholarDigital Library
- Y.-C. Chen and D. Towsley. On Bufferbloat and Delay Analysis of Multipath TCP in Wireless Networks. In IFIP Networking, 2014.Google ScholarCross Ref
- A. B. Clarke. A Waiting Line Process of Markov Type. The Annals of Mathematical Statistics, 1956.Google ScholarCross Ref
- A. Frömmgen, T. Erbshäußer, Buchmann, T. Zimmermann, and K. Wehrle. ReMP TCP: Low Latency Multipath TCP. In IEEE ICC, 2016.Google ScholarCross Ref
- K. Gardner, M. Harchol-Balter, A. Scheller-Wolf, M. Velednitsky, and S. Zbarsky. Redundancy-d: The Power of d Choices for Redundancy. Operations Research, 2017.Google Scholar
- V. Gupta, M. Harchol-Balter, A. Wolf, and U. Yechiali. Fundamental Characteristics of Queues with Fluctuating Load. In ACM Sigmetrics, 2006. Google ScholarDigital Library
- F. A. Haight. Two Queues in Parallel. Biometrika, 1958.Google Scholar
- P. G. Harrison and H. Zatschler. Sojourn time distributions in modulated g-queues with batch processing. In IEEE QEST, 2004. Google ScholarDigital Library
- D. Heyman. On Ross's Conjectures about Queues with Non-stationary Poisson Arrivals. Journal of Applied Probability, 1982.Google Scholar
- E. Hyytiä. Optimal Routing of Fixed Size Jobs to Two Parallel Servers. INFOR: Information Systems and Operational Research, 2013.Google Scholar
- A. Izagirre and A. M. Makowski. Light traffic performance under the power of two load balancing strategy: The case of server heterogeneity. ACM Sigmetrics Performance Evaluation Review, 2014. Google ScholarDigital Library
- E. Kohler, R. Morris, B. Chen, J. Jannotti, and M. F. Kaashoek. The Click Modular Router. ACM TOCS, 2000. Google ScholarDigital Library
- J. F. Kurose and K. W. Ross. Computer Networking: A Top-down Approach. 2009. Google ScholarDigital Library
- J. Lambert, B. Van Houdt, and C. Blondia. Queues with Correlated Service and Inter-Arrival Times and Their Application to Optical Buffers. Stochastic Models, 2006.Google Scholar
- R. L. Larsen. Control of Multiple Exponential Servers with Application to Computer Systems. PhD thesis, University of Maryland, 1981. Google ScholarDigital Library
- L. Liyanage and J. Shanthikumar. Second-order Properties of Single-stage Queueing Systems. Oxford Statistical Science Series, 1992.Google Scholar
- S. R. Mahabhashyam and N. Gautam. On Queues with Markov Modulated Service Rates. Queueing Systems, 2005. Google ScholarDigital Library
- C. Mitchell, A. Paulson, and C. Beswick. The Effect of Correlated Exponential Service Times on Single Server Tandem Queues. Naval Research Logistics, 1977.Google ScholarCross Ref
- M. F. Neuts. The M/M/1 Queue with Randomly Varying Arrival and Service Rates. PhD thesis, Delaware University, 1977.Google Scholar
- C. Raiciu, C. Paasch, S. Barre, A. Ford, M. Honda, F. Duchene, O. Bonaventure, and M. Handley. How Hard Can It Be? Designing and Implementing a Deployable Multipath TCP. In USENIX NSDI, 2012. Google ScholarDigital Library
- T. Rolski. Queues with Non-stationary Input Stream: Ross's Conjecture. Advances in Applied Probability, 1981.Google Scholar
- S. M. Ross. Average Delay in Queues with Non-stationary Poisson Arrivals. Journal of Applied Probability, 1978.Google Scholar
- C. Vlachou, S. Henri, and P. Thiran. Electri-Fi Your Data: Measuring and Combining PLC with WiFi. In ACM IMC, 2015. Google ScholarDigital Library
- W. Winston. Optimality of the Shortest Line Discipline. Journal of Applied Probability, 1977.Google Scholar
- U. Yechiali and P. Naor. Queuing Problems with Heterogeneous Arrivals and Service. Operations Research, 1971. Google ScholarDigital Library
- K. Yedugundla, S. Ferlin, T. Dreibholz, Ö. Alay, N. Kuhn, P. Hurtig, and A. Brunstrom. Is Multi-path Transport Suitable for Latency Sensitive Traffic? Computer Networks, 2016. Google ScholarDigital Library
Index Terms
- On the Delays in Time-Varying Networks: Does Larger Service-Rate Variance Imply Larger Delays?
Recommendations
Delays for Customers from Different Arrival Streams to a Queue
In a queue with several different arrival streams, in general, the expected delay for customers from one stream is not equal to the expected delay for customers from the other streams. Two approximations are presented here for the expected delay for ...
Queue-Length, Waiting-Time and Service Batch Size Analysis for the Discrete-Time GI/D-MSP Queueing System
AbstractThis paper analyzes an infinite-buffer single-server bulk-service queueing system in which customers arrive according to a discrete-time renewal process. The customers are served under the discrete-time Markovian service process according to the ...
On the analytic assessment of the impact of traffic correlation on queues in continuous time domain
Given only the traffic correlations of counts and intervals, a Batch Renewal Arrival Process (BRAP) is completely determined, as the least biased choice and thus, it provides the analytic means to construct suitable traffic models for the study of ...
Comments