SED navigation bar go to SED home page go to SED publications page go to NIST home page SED Home Page SED Contacts SED Projects SED Products and Publications Search SED Pages


contents     previous     next


3.1.1 Modeling Roundtrip Delay

Charles Hagwoood
Statistical Engineering Division, ITL

Hsin Fang
High Performance Systems and Services Division, ITL

On the Internet, a packet's round-trip delay is the sum of delays on each subnet link traversed by the packet. Each link (or hop) delay consists of four components, processing delay, queuing delay, transmission delay and propagation delay. Once the packet length and route are fixed, the packet round-trip delay only changes with the queue delay, which in the Internet changes with the fluctuation of the Internet traffic. Suppose such a scenerio holds. The purpose of this theoretical and experimental study is to determine how long range dependence and heavy tailedness, inherent properties of the interarrival times of Internet traffic processes, are inherited by the related roundtrip delay process. That is, suppose one monitors or probes the Internet e.g. by pinging a site at times $t_1,t_2,\ldots,t_n$, and recording the corresponding delays $R(t_1),\ldots,R(t_n)$. Then, how does one characterize this delay process?

The experimental verification is based on performance data collected through the past year from several of the Cross Industry Working Team (XIWT) sites. These sites are shown in the figure, they include Stanford University, HP, Intel, NIST, Bell South, Hughes, West Group, DEC, SBC, and CAIDA.

Suppose in its roundtrip, an outgoing packet started at hop 1 passes through s hops, where hop s=hop 1. At each hop the packet is queued and then routed to the next hop. Let R(n,i) denote the queuing delay of the nth packet at the ith hop. The roundtrip queuing delay of the nth packet sent from hop 1 is given by

T(n)=R(n1,1)+R(n2,2)+...+R(ns,s)

where it is assumed that when the nth packet from hop 1 arrives at hop i, it is the nith packet at that hop.

We first solve the problem for the simplified model: Assume that R(ni,i), i=1,...,s are independent, and that each R(n,i) satisfies Lindley's queuing theory equation

\begin{displaymath}R(n,i)=max\{R(n-1,i)+u_n-v_n,0\}
\end{displaymath}

where for that hop, un denotes the service time of the nth packet and vn denotes the interarrival time between the nth and (n-1)st packets. It is assumed the un's are independent, exponentially distributed with known parameter, $\lambda$ and they are independent of the vn's.

Traffic Property I: (Heavy-Tailed Interarrival Times) The interarrival times are assumed to have a heavy right tail i.e.

\begin{displaymath}1-F(x)=P[v_n > x]=x^{-\alpha}L(x) ~~ x \geq 0
\end{displaymath}

where L(x) is a slowly varying function.

Traffic Property II. (Long Range Dependence) Suppose that the ith hop has interarrival times v1,v2,... that are stationary, dependent with autocorrelation given by

\begin{displaymath}r(k)= Cov[v_i,v_{k+i}]/\sqrt{Var[v_i]Var[v_{k+i}]}=k^{-D}L(k)
\end{displaymath}

where 0< D<1 and where L(x) is a slowly varying function. Such a correlation structure can arise from fractional Brownian motion (Taqqu and Teverovsky), i.e from a mean zero, stationary increments, Gaussian process, X(t), with covariance $E[X(t)X(s)]=\frac{1}{2}\sigma^2[\mid t \mid ^{2H}+\mid s \mid ^{2H}-\mid t-s \mid ^{2H}]$ . The increments $v(k)=X(k)-X(k-1), k=1,2,\ldots$ will have autocorrelation function $r(k)=\frac{1}{2}\sigma^2[(k+1)^{2H}-2k^{2H}+\mid k-1 \mid^{2H}]$, therefore $r(k) \sim H(2H-1)k^D$ where D=2H-2. For 1/2< H<1 the increments display long range dependence.




\begin{figure}
\epsfig{file=/proj/sedshare/panelbk/2000/data/projects/it/roundtrip.EPS,width=6.0in} \end{figure}

Figure 1: XIWT sites



contents     previous     next

Date created: 7/20/2001
Last updated: 7/20/2001
Please email comments on this WWW page to sedwww@nist.gov.