A COMPREHENSIVE STOCHASTIC MODEL FOR TCP LATENCY AND THROUGHPUT

D. Zheng∗ and G.Y. Lazarou∗∗

References

  1. [1] D. Zheng, G. Lazarou, & R. Hu, A stochastic model for short-lived TCP flows, Proc. IEEE International Conference on Communications (ICC), Anchorage, Alaska, 2003, 291–296.
  2. [2] D. Zheng, G. Lazarou, & R. Hu, A comprehensive TCP stochastic model, Proc. 2nd IASTED International Conference on Communications, Internet, and Information Technology (CIIT), Phoenix, Arizona, 2003, 291–296.
  3. [3] J. Padhye, V. Firoiu, D.F. Towsley, & J.F. Kurose, Modeling TCP Reno performance: A simple model and its empirical validation, IEEE/ACM Transactions on Networking, 8(2), 2000, 133–145.
  4. [4] N. Cardwell, S. Savage, & T. Anderson, Modeling TCP latency, Proc. IEEE INFOCOM, Tel Aviv, Israel, 2000, 1742–1751.
  5. [5] B. Sikdar, S. Kalyanaraman, & K.S. Vastola, An integrated model for the latency and steady-state throughput of TCP connections, Performance Evaluation, 46(2–3), 2001, 39–154.
  6. [6] K. Thompson, G.J. Miller, & R. Wilder, Wide-area internet traffic patterns and characteristics, IEEE Network, 11(6), 1997, 10–23.
  7. [7] K. Claffy, G. Miller, & K. Thompson, The nature of the beast: Recent traffic measurements from an internet backbone, Proc. International Networking Conference, 1998. Available online http://www.isoc.org/inet98/proceedings/6g/6g_3.htm
  8. [8] J. Heidemann, K. Obraczka, & J. Touch, Modeling the performance of HTTP over several transport protocols, IEEE/ACM Transactions on Networking, 5(5), 1997, 616–630. 118
  9. [9] S. Floyd & K. Fall, Promoting the use of end-to-end congestion control in the Internet, IEEE/ACM Transactions on Networking, 7(4), 1999, 458–472.
  10. [10] T.J. Ott, T.V. Lakshman, & L.H. Wong, Sred: Stabilized RED, Proc. IEEE INFOCOM, New York, NY, 1999, 1346–1355.
  11. [11] J. Blot & T. Turletti, Experience with rate control mechanisms for packet video in the Internet, ACM Computer Communications Review, 28(1), 1998, 4–15.
  12. [12] L. Vivisano, L. Rizzo, & J. Crowcroft, TCP-like congestion control for layered multicast data transfer, Proc. IEEE INFOCOM, San Francisco, CA, 1998, 1–8.
  13. [13] F. Kelly, Charging and rate control for elastic traffic, European Transactions on Telecommunications, 8(1), 1997, 33–37.
  14. [14] F.P. Kelly, A. Maulloo, & D.K.H. Tan, Rate control for communication networks: Shadow price, proportional fairness and stability, Journal of Operational Research Society, 49, 1998, 237–252.
  15. [15] F.P. Kelly, Fairness and stability of end-to-end congestion control, European Journal of Control, 9(27), 2003, 159–176.
  16. [16] S. Low & D. Lapsley, Optimization flow control–I: Basic algorithm and convergence, IEEE Transanctions on Networking, 7(6), 1999, 861–874.
  17. [17] S. Low, L. Peterson, & L. Wang, Understanding Vegas: A duality model, Journal of ACM, 49(2), 2002, 207–235.
  18. [18] J. Bolliger, T. Gross, & U. Hengartner, Bandwidth modeling for network-aware applications, Proc. IEEE INFOCOM, New York, NY, 1999, 1300–1309.
  19. [19] C. Partridge & T.J. Shepard, TCP/IP performance over satellite links, IEEE Network, 11(5), 1997, 44–49.
  20. [20] J. Mahdavi, TCP performance tuning, 1997. Available: online http://www.psc.edu/networking/tcptune/slides/
  21. [21] V. Paxson, Measurements and analysis of end-to-end internet dynamics, Doctoral Dissertation, University of California, Berkeley, CA, 1997.
  22. [22] M. Borella, D. Swider, S. Uludag, & G. Brewster, Internet packet loss: Measurement and implications for end-to-end QoS, International Conference on Parallel Processing, Minneapolis, MN, 1998, 3–15.
  23. [23] M. Borella, Measurement and interpretation of Internet packet loss, Journal of Communication and Networks, 2(2), 2000, 93–102.
  24. [24] C.R. Cunha, A. Bestavros, & M.E. Crovella, Characteristics of WWW client-based traces, Technical Report BU-CS-95-010, Boston University, Boston, MA, 1995.
  25. [25] M. Mellia, I. Stoica, & H. Zhang, TCP model for short lived flows, IEEE Communications Letters, 6(2), 2002, 85–87.
  26. [26] W.R. Stevens, TCP/IP illustrated: The protocols (Boston, MA: Addison-Wesley, 1994).
  27. [27] V. Jacobson, Congestion avoidance and control, Proc. ACM SIGCOMM, Stanford, CA, 1988, 314–329.
  28. [28] The network simulator ns-2. Available online http:// www.isi.edu/nsnam/ns/
  29. [29] M. Mitzenmacher & R. Rajaraman, Towards more complete models of TCP latency and throughput, Journal of Supercomputing, 20(2), 2001, 137–160.
  30. [30] T. Lakshman & U. Madhow, The performance of TCP/IP for networks with high bandwidth-delay products and random loss, IEEE/ACM Transactions on Networking, 5(3), 1997, 336–350.
  31. [31] A. Kumar, Comparative performance analysis of versions of TCP in a local network with a lossy link, IEEE/ACM Transactions on Networking, 6(4), 1998, 485–498.
  32. [32] J. Mahdavi & S. Flyod, TCP-friendly unicast rate-based flow control, Note sent to end2end-interest mailing list, 1997.
  33. [33] M. Mathis, J. Semske, J. Mahdavi, & T. Ott, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM Computer Communication Review, 27(3), 1997, 67–82.
  34. [34] C. Casetti & M. Meo, A new approach to model the stationary behavior of TCP connections, Proc. IEEE INFOCOM, Tel Aviv, Israel, 2000, 367–375.
  35. [35] H. Balakrishnan, V. Padmanabhan, S. Seshan, R.H. Katz, & M. Stemm, TCP behavior of a busy Internet server: Analysis and improvements, Proc. IEEE INFOCOM, San Francisco, CA, 1998, 252–262.
  36. [36] J.C. Hoe, Start-up dynamics of TCP’s congestion control and avoideance schemes, Master thesis, Massachusetts Institute of Technology, Cambridge, MA, 1995. Appendix 1 The Expectation of 1/W From Taylor formula, we know: f(W) = ∞i =0 fi (a) i! (W − a)i (56) Let f(W) and a be 1/W and E[W], respectively. We thus have: fn (W) = (−1)n n!W−(n+1) (57) Substituting fi (a) in (56) and making use of (57) and E[W], we get: 1 W = ∞i =0 (−1)i i!E[W]−(i+1) i! (W − E[W])i = ∞i =0 (−1)i (W − E[W])i E[W](i+1) (58) Taking expectation on both sides of (58), results in: E 1 W = E ∞ i =0 (−1)i (W − E[W])i E[W](i+1) = ∞i =0 E ( −1)i (W − E[W])i E[W](i+1) = ∞i =0 (−1)i E[(W − E[W])i ] E[W](i+1) = 1 E[W] + V ar(W) E[W]3 + ∞i =3 (−1)i E[(w − E[W])i ] E[W](i+1) ≈ 1 E[W] + V ar(W) E[W]3 = 1 E[W] 1 + V ar(W) E[W]2 ( 59) The approximation holds when E[W](i+1) E[(W − E[W])i ]. Appendix 2 The Variance of W TD Using similar assumptions as in the previous analysis, from (20), we know that V ar[α] = (1 − p)/p2 . Thus from (16) we get: V ar[Y ] = 1 − p p2 + V ar[WT D ] (60) 119 Using (18), we get the auto-correlation at the zero point:10 Rw(0) = Rw(0) 4 + Rx(0) b2 Rx(0) = 3b2 4 Rw(0) (61) And using (25), (26), and (27), we can compute the variance of β as follows: V ar[β] = Rβ(0) − E[β] 2 = E[β2 ] − E[β] 2 = E w−1k =0 k2 p(β = k)|w − E[β] 2 = E w−1k =0 k2 (1 − p)k p 1 − (1 − p)w |w − E[β] 2 ≈ 2(1 − p)2 p2 − (1 − p) 8 3bp − 1 2 (62) Using (19), we can also get: V ar[Y ] = V ar X i 2 WT D i−1 2 + WT D i − 1 + V ar[β] = E X i 2 2 E W T D i−1 2 + WT D i − 1 2− E X i 2 WT D i−1 2 + WT D i − 1 2 + V ar[β] = Rx(0) 4 5Rw(0) 4 − E X 2 2 × E WT D i−1 2 + WT D i − 1 2 + V ar[β] = 3b2 4 Rw(0) 4 5Rw(0) 4 − E[X] 2 4 3 2 E[WT D ] − 1 2 + V ar[β] = 15b2 64 [V ar[WT D ] + E[WT D ] 2 ] 2 − E[X] 2 4 3 2 E[WT D ] − 1 2 + V ar[β] ≈ 15b2 64 V ar[WT D ] + 8 3bp 2 − 1 4 b 2 8 3bp + b 2 × 3 2 8 3bp − 1 2 + 2(1 − p)2 p2 − (1 − p) 8 3bp − 1 2 (63) 10 This is equal to E[X2]. Combining (63) and (60), we obtain the final equation: 1 − p p2 + V ar[WT D ] = 15b2 64 V ar[WT D ] + 8 3bp 2 − 1 4 b 2 8 3bp + b 2 3 2 8 3bp − 1 2 + 2(1 − p)2 p2 − (1 − p) 8 3bp − 1 2 (64) Solving (64), we obtain the variance of WT D as follows: V ar[WT D ]p→0 ≈ 8( √ 3 − 1) 3bp (65)

Important Links:

Go Back