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 forshort-lived TCP flows, Proc. IEEE International Conferenceon Communications (ICC), Anchorage, Alaska, 2003, 291–296.
  2. [2] D. Zheng, G. Lazarou, & R. Hu, A comprehensive TCPstochastic model, Proc. 2nd IASTED International Conferenceon Communications, Internet, and Information Technology(CIIT), Phoenix, Arizona, 2003, 291–296.
  3. [3] J. Padhye, V. Firoiu, D.F. Towsley, & J.F. Kurose, ModelingTCP Reno performance: A simple model and its empiricalvalidation, 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 integratedmodel for the latency and steady-state throughput of TCPconnections, Performance Evaluation, 46(2–3), 2001, 39–154.
  6. [6] K. Thompson, G.J. Miller, & R. Wilder, Wide-area internettraffic 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 onlinehttp://www.isoc.org/inet98/proceedings/6g/6g_3.htm
  8. [8] J. Heidemann, K. Obraczka, & J. Touch, Modeling the perfor-mance of HTTP over several transport protocols, IEEE/ACMTransactions on Networking, 5(5), 1997, 616–630.118
  9. [9] S. Floyd & K. Fall, Promoting the use of end-to-end con-gestion control in the Internet, IEEE/ACM Transactions onNetworking, 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 mechanismsfor packet video in the Internet, ACM Computer Communi-cations Review, 28(1), 1998, 4–15.
  12. [12] L. Vivisano, L. Rizzo, & J. Crowcroft, TCP-like congestioncontrol for layered multicast data transfer, Proc. IEEE INFO-COM, San Francisco, CA, 1998, 1–8.
  13. [13] F. Kelly, Charging and rate control for elastic traffic, EuropeanTransactions on Telecommunications, 8(1), 1997, 33–37.
  14. [14] F.P. Kelly, A. Maulloo, & D.K.H. Tan, Rate control forcommunication networks: Shadow price, proportional fairnessand stability, Journal of Operational Research Society, 49,1998, 237–252.
  15. [15] F.P. Kelly, Fairness and stability of end-to-end congestioncontrol, European Journal of Control, 9(27), 2003, 159–176.
  16. [16] S. Low & D. Lapsley, Optimization flow control–I: Basic algo-rithm and convergence, IEEE Transanctions on Networking,7(6), 1999, 861–874.
  17. [17] S. Low, L. Peterson, & L. Wang, Understanding Vegas: Aduality model, Journal of ACM, 49(2), 2002, 207–235.
  18. [18] J. Bolliger, T. Gross, & U. Hengartner, Bandwidth modelingfor network-aware applications, Proc. IEEE INFOCOM, NewYork, NY, 1999, 1300–1309.
  19. [19] C. Partridge & T.J. Shepard, TCP/IP performance over satel-lite links, IEEE Network, 11(5), 1997, 44–49.
  20. [20] J. Mahdavi, TCP performance tuning, 1997. Available: onlinehttp://www.psc.edu/networking/tcptune/slides/
  21. [21] V. Paxson, Measurements and analysis of end-to-end inter-net dynamics, Doctoral Dissertation, University of California,Berkeley, CA, 1997.
  22. [22] M. Borella, D. Swider, S. Uludag, & G. Brewster, Internetpacket 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 packetloss, Journal of Communication and Networks, 2(2), 2000,93–102.
  24. [24] C.R. Cunha, A. Bestavros, & M.E. Crovella, Characteristicsof 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 livedflows, 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. ACMSIGCOMM, 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 completemodels of TCP latency and throughput, Journal of Supercom-puting, 20(2), 2001, 137–160.
  30. [30] T. Lakshman & U. Madhow, The performance of TCP/IP fornetworks 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 ofTCP in a local network with a lossy link, IEEE/ACM Trans-actions on Networking, 6(4), 1998, 485–498.
  32. [32] J. Mahdavi & S. Flyod, TCP-friendly unicast rate-based flowcontrol, Note sent to end2end-interest mailing list, 1997.
  33. [33] M. Mathis, J. Semske, J. Mahdavi, & T. Ott, The macroscopicbehavior of the TCP congestion avoidance algorithm, ACMComputer Communication Review, 27(3), 1997, 67–82.
  34. [34] C. Casetti & M. Meo, A new approach to model the stationarybehavior of TCP connections, Proc. IEEE INFOCOM, TelAviv, Israel, 2000, 367–375.
  35. [35] H. Balakrishnan, V. Padmanabhan, S. Seshan, R.H. Katz, &M. Stemm, TCP behavior of a busy Internet server: Analysisand improvements, Proc. IEEE INFOCOM, San Francisco,CA, 1998, 252–262.
  36. [36] J.C. Hoe, Start-up dynamics of TCP’s congestion control andavoideance schemes, Master thesis, Massachusetts Institute ofTechnology, Cambridge, MA, 1995.Appendix 1The Expectation of 1/WFrom Taylor formula, we know:f(W) =∞i=0fi(a)i!(W − a)i(56)Let f(W) and a be 1/W and E[W], respectively. Wethus have:fn(W) = (−1)nn!W−(n+1)(57)Substituting fi(a) in (56) and making use of (57) andE[W], we get:1W=∞i=0(−1)ii!E[W]−(i+1)i!(W − E[W])i=∞i=0(−1)i(W − E[W])iE[W](i+1)(58)Taking expectation on both sides of (58), results in:E1W=E∞i=0(−1)i(W − E[W])iE[W](i+1)=∞i=0E(−1)i(W − E[W])iE[W](i+1)=∞i=0(−1)iE[(W − E[W])i]E[W](i+1)=1E[W]+V ar(W)E[W]3+∞i=3(−1)iE[(w − E[W])i]E[W](i+1)≈1E[W]+V ar(W)E[W]3=1E[W]1+V ar(W)E[W]2(59)The approximation holds when E[W](i+1)E[(W −E[W])i].Appendix 2The Variance of W TDUsing 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 − pp2+ V ar[WT D] (60)119Using (18), we get the auto-correlation at the zero point:10Rw(0) =Rw(0)4+Rx(0)b2Rx(0) =3b24Rw(0) (61)And using (25), (26), and (27), we can compute thevariance of β as follows:V ar[β] = Rβ(0) − E[β]2= E[β2] − E[β]2= Ew−1k=0k2p(β = k)|w−E[β]2= Ew−1k=0k2(1 − p)kp1 − (1 − p)w|w−E[β]2≈2(1 − p)2p2− (1 − p)83bp− 12(62)Using (19), we can also get:V ar[Y ] = V arXi2WT Di−12+ WT Di − 1+V ar[β]= EXi22 E WT Di−12+ WT Di − 12−E Xi2WT Di−12+ WT Di − 12+ V ar[β]=Rx(0)45Rw(0)4− EX22× EWT Di−12+ WT Di − 12+ V ar[β]=3b24 Rw(0)45Rw(0)4−E[X]2432E[WT D] − 12+ V ar[β]=15b264[V ar[WT D] + E[WT D]2]2−E[X]2432E[WT D] − 12+ V ar[β]≈15b264Var[WT D] +83bp2−14b283bp+ b2×3283bp− 12+2(1 − p)2p2− (1 − p)83bp− 12(63)10 This is equal to E[X2].Combining (63) and (60), we obtain the final equation:1 − pp2+ V ar[WT D] =15b264Var[WT D] +83bp2−14b283bp+ b23283bp− 12+2(1 − p)2p2− (1 − p)83bp− 12(64)Solving (64), we obtain the variance of WT Das follows:V ar[WT D]p→0 ≈8(√3 − 1)3bp(65)

Important Links:

Go Back