COMPUTER
`NETWORKS
`
`and
`ISDN SYSTEMS
`
`The International Journal of Computer
`and Telecommunications Networking
`
`Theme issue
`
`ITC 14 Special Sessions Presentations
`
`Guest Editor:
`
`J‘W- Robe“
`
`3:‘:
`
`;~‘;*%
`
`mum’ F. wenm LIBRARY
`cowaoe or smameenmc
`
`APR 0 4 %
`
`uw-meisew». N! serves
`
`ELSEVIER Amsterdam — Lausanne — New York — Oxford - Shannon — Tokyo
`RPX Exhibit 1231
` RPX Exhibit 1231
`RPX v. DAE
`
`RPX V. DAE
`
`

`
`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`

`
`730
`
`BJ. Dernpsey at o:‘./ Computer Networks and ISDN Sy.r.'etn.t 28 (I996) 719-736
`
`The distribution of continuous media across a packet—switching network requires consideration of encoding
`schemes. end-to-end network delays, network delay variations, and packet loss, all of which significantly affect
`the playback quality at the receiving site:
`‘
`o In recent years, considerable progress has been made in the design of efficient digital encoding techniques
`for analog audiovisual data [II}. The selection of an encoding scheme represents a trade-off between
`consumption of bandwidth in the network and playback quality at
`the receiving site since low-bit-rate
`encoding schemes result in a less precise reconstruction of the original analog signal.
`0 In an interactive continuous media session, human perception factors produce a requirement for bounded
`roundtrip delays. If roundtrip delays are too long, the interactive nature of the session is degraded.
`0 Statistical multiplexing introduces variations in the network delay experienced by individual packets. These
`variations are referred to as delay jitter. Delay jitter can lead to interruptions in the continuous playback
`of the continuous media stream at the receiver.
`though its
`o Unlike data transmission, most continuous media data does not require reliable delivery,
`tolerance for packet loss is low. Techniques for robust signal processing in the presence of packet
`loss
`can significantly improve loss tolerances, but even the loss of a single packet may noticeably degrade
`playback quality at the receiver.
`In this paper we study error control for voice transmission in packet-switching networks. We selected interac-
`tive packet voice for our work since it has very stringent delay and error requirements. While our investigation
`focuses on voice transmission, most of our concepts apply to other forms of continuous media traffic, e.g..
`|ow—handwidth video. We examine the feasibility of retransmission-based error recovery for continuous media
`traffic. In order to be effective, retransmissions of lost packets must be completed within the delay constraints
`of the packet stream. However, if timely retransmission can be achieved with a high probability of success,
`a retransmission-based approach to error control
`is attractive because it imposes little overhead on network
`resources. Note that retransmission-based error recovery can be used in conjunction with extant preventive error
`control schemes such as forward error correction or channel coding.
`We employ analytical modeling techniques to investigate the effectiveness of retransmission for different
`network scenarios. To explore the relationship between our theoretical results and the dynamic behavior oi‘
`voice transmission over existing networks, we present measurements of the actual delays experienced by voice
`transmission running over a campus backbone network. Our results indicate that retransmission-based error
`recovery can be effective for many end—to-end transmission scenarios in current networks.
`The remainder of this paper is structured as follows. In Section 2 we review issues that must be addressed
`by protocols for voice distribution in packet-switching networks. In Section 3 we develop an analytic model for
`the end-to-end transmission of packet voice and derive a performance metric for timely retransmission in the
`presence of errors. We present examples where we apply the performance metric under variations of network
`parameters. In Section 4 we provide measurements of voice packets on a multiple-segment local area network
`and compare the empirically obtained data with our theoretical findings. In Section 5 we present the conclusions
`of the paper.
`
`2. Protocol issues
`
`Continuous media protocols must have mechanisms to address all factors that may degrade the quality of
`remote playback. In this section we briefly discuss important issues for maintaining high quality voice trans-
`mission. and discuss how these issues are resolved in extant packet voice protocols. An important consideration
`in the design of packet voice protocols is that speech is actually an alternating series of activity periods. or
`ralf<spnrt.r. followed by silence periods with the activity periods constituting only around 40% of the total time
`l4l-
`
`

`
`B.J'. Dempsey et at’. I Computer Net‘wrJrk.r and ISDN Systerns 28 f I 996) 7.’ 9- 736
`
`72 l
`
`2.}. Encoding and packetization
`
`The packet voice source continuously collects and buffers digitized voice samples. After a fixed period
`of time, the so-called packetization interval, voice samples collected by the audio hardware are placed into a
`network packet, and the packet is submitted to the network. Typical packetization intervals range from 10-50 ms
`[ I9].
`Given a fixed packetization interval, the encoding scheme determines the actual number of bits per packet.
`The ubiquitous pulse code modulation (PCM) encoding scheme for voice [6] samples every 125 pzs with 8
`bits per sample to yield a 64 Kbitfs channel. Bandwidth reduction can be achieved through the use of fewer
`hits per sample, less frequent sampling, suppression of transmission during silence periods, and compression of
`the digitized data. Adaptive differential pulse code modulation (ADPCM) [7], for example, encodes only the
`difference between consecutive samples, reducing the number of bits per sample to 25 bits. Coding techniques
`with even lower bit rates, e.g., Linear Predictive Coding (LPC), exist, though speech fidelity is frequently poor
`|
`I
`I |.
`
`2. 2. Rotmdrrip delay
`
`Behavioral studies [5,l3] have shown that roundtrip delays above a certain threshold degrade the interactive
`nature of the conversation. Quantifying this factor is difficult since individual human users have different
`tolerances for delay and these tolerances vary with the application. High-quality voice applications require less
`than 200 ms roundtrip delays, but delays of up to 600 ms have been shown to be acceptable [13].
`Since current packet-switching networks do not provide a bounded delay service, voice protocols must provide
`mechanisms that can cope with highly variable end-to-end delays. Adjustments of the packetization interval and
`buffering of voice packets at the receiver are widely used to compensate for unpredictable delays [ 15,19].
`
`2.3. Dela)’ jitter
`
`If the network delay of voice packets is not constant, e.g., due to statistical multiplexing, discontinuity of
`the voice playback at
`the receiver can occur. We refer to these discontinuities as gaps. Gaps are commonly
`addressed through buffering at
`the receiving site. The first packet in a talkspurt is artificially delayed at the
`receiver for a period of time known as the control time. The control time builds up a buffer of arriving packets
`sufficient to provide continuous playback in the presence of delay jitter. Note however, that the control time
`cannot be arbitrarily large due to constraints on the roundtrip delay.
`The use of a control time to compensate for delay jitter requires mechanisms to identify the beginning of
`talkspurts and to determine the control time. The latter is difficult since it requires knowledge of the network
`delay distribution. Numerous methods have been proposed for estimating the control time of a talkspttrt. based
`on network delay measurements [ 15], on stochastic assumptions about the network delay { L2], or both [ 16].
`
`2.4. Error control
`
`The impact of packet loss on voice quality varies since interpolation can mitigate the effects of lost samples
`and not all samples contain equally important information. In any case, the tolerance to packet loss is low and
`even the loss of even a single packet may be perceptible during playback.
`Packet-level error control for packet voice streams must be designed so as to provide the best possible quality
`for the stream. Conventional error control techniques are unacceptable since they do not consider the delay
`sensitivity of voice data. Hence, researchers have dismissed a retransmission—based approach to error control.
`focusing instead on open-loop techniques that recover or limit the effects of losses.
`
`
`
`

`
`722
`
`BJ. Dem_n.re_\' er al. /Computer Networks and ISDN S_t'.rrems 28 (I 996) 7 i‘ 9- 736
`
`Forward error correction (FEC) [3, 17] provides robustness in the presence of packet loss by adding redundant
`information to the Original samples. If only a smail number of packets is lost, the added redundancy enables a
`reconstruction of the original voice data at the receiver. Theability to recover lost information strongly depends
`on the degree of redundancy. In addition to considerable processing overhead, FEC-based error control results
`in increased network bandwidth consumption. Thus. FEC contributes to network congestion. and, since losses
`in the network are most often due to congestion, may even be the cause of packet loss. '
`Channel coding refers to a class of approaches that separate the voice signal into multiple data streams with
`different priorities. The priorities are used by network switches to selectively discard low priority packets which
`carry information that is less crucial in reconstructing the voice signal. Channel coding techniques have been
`shown to provide a graceful degradation of playback quality in a variety of loss scenarios [l0.2f},23]. For
`PCM-encoded voice, packet loss rates of over 5% on the channel carrying the least significant information have
`been reported as tolerable when using small (32-byte) packets [21 l. A drawback to channel coding. however.
`is that the network is required to support selective discarding of packets during periods of congestion.
`
`3. An analytical model for retransmission of packet voice data
`
`In this section we present an analytical retransmission model for error control of a voice packet stream in
`a packet-switching network. Through analysis of the model we are able to quantify the gain achieved by the
`retransmission of packets lost in the network. Given an encoding scheme, voice quality depends primarily on
`maintaining the continuity of the playback of each talkspurt at the receiver. The loss of voice quality results
`from discontinuities due to delay jitter or packet loss. Since they both cause gaps. delay jitter and packet loss
`cannot be considered separately. Timely retransmission is of little value if discontinuities due to delay jitter
`degrade the quality of the playback. For this reason we define the performance metric for measuring transmission
`quality as the probability of continuous playback. i.e., a playback without gaps, of an entire talkspurt. Under a
`given packet loss scenario, this metric accounts for the quality degradation due to delay jitter and to untimely
`retransmission. The quality degradation due to delay jitter alone is found by computing the metric under the
`assumption of error-free transmission.
`Our model considers all protocol issues reviewed in the previous section. Since packets in different talkspurts
`rarely interfere with each other. we model the transmission of a single talkspurt within a packet voice stream.
`The sender introduces packets into the network with a deterministic spacing as given by the packetization
`interval. It is assumed that the network preserves the transmission order of the packets in the voice stream.
`Since connection-oriented networks, such as ATM networks, guarantee in-order delivery. and,
`in practice. most
`connectionless networks rarely reorder the packets in a stream communication, 2
`the assumption of in-sequence
`delivery is widely applicable.
`In Section 3.1 we give a detailed description of an end-to-end retransmission model. In Section 3.2 we
`develop analytic expressions for the effectiveness of retransmission of lost voice data. In Section 3.3 we present
`numerical examples of our results.
`
`' Note that retransmission-based error control also consumes network bandwidth and increases network congestion. Unlike retransmission.
`however. forward error correction always imposes additional overhead on the network and thus may induce congestion—based losses in the
`network where none would otherwise occur.
`ln LANs and
`3 ln connectionless networks a traffic stream such as a voice transmission often passes over the same set of routers.
`MANs,
`it
`is often the case that only a single physical path exists between a pair of communicating enclsystems. Even if there are multiple
`network paths between the sender and the receiver. current routing algorithms modify their routing tables relatively infrequently. resulting
`in infrequent more changes. One study on wide—area lnternet traffic. for example. reports packet reorderings to have occurred for less than
`0.05 % of the packets transmitted in its experiments I l8|.
`
`

`
`SJ. Demp.rey at at. /Computer Networks and ISDN Systems 28 (1996) 7! 9- 736
`
`T23
`
`2
`
`3
`
`I
`Y
`
`5
`
`-I
`Y
`
`_____________________________________ __
`
`
`
`E
`:
`
`E E
`
`Network
`E Delay
`
`Unnormalizecl
`Network
`
`Delay
`
`Packet
`Stlbniission
`
`Times
`
`Arrival
`Times
`
`l’l:l)-'l3:1(.'l<
`Times
`
`
`
`
`Sequencing
`Delay
`
`i
`
`“me
`
`2
`
`s5.
`T,;
`
`_-
`T3
`
`s
`T3
`
`s
`T4
`
`E
`g
`
`
`
`Fig.
`
`I. Transmission model of a talkspun.
`
`.1’. I. End—ro—end model for packet voice transmission
`
`Starting at time I = O, the sender generates voice packets after packetization intervals of fixed length I. A
`laikspurt is assumed to consist of a fixed number of N packets. The transmission times of packets are assumed
`to be negligible compared to the packetization interval. Thus, 3? represents the distance between packets at the
`entrance of the network.
`
`the packet would
`is the sum of two components. One is the delay that
`The network delay of a packet
`experience if transmitted in isolation; the other is the sequencing delay due to in-order delivery of packets. The
`first component is called the unnorntalized network delay of the packet and the second is called its sequencing
`delay. The unnonnalized network delay is assumed to follow an arbitrary but fixed distribution. FU. and U_,-
`is
`used to denote the unnormalized network delay of the jth packet in a talkspurt. Unnorrnalized network delays
`
`the additional delay due to ordered delivery,
`are assumed to be independent. However,
`delay. captures the dependence among packet delays due to sequencing.
`When the first packet of a talkspurt arrives to the receiver, playback of the talkspurt is delayed for the duration
`of :1 so—called control time. denoted by V (V 2 0). Thus, playback of the talkspurt is started at I = U. + V.
`The playback duration of each packet is identical to the packetization interval Y.
`The end-to-end transmission mode]
`is summarized in Fig.
`1
`for a talkspurt consisting of N = 6 packets.
`
`the sequencing
`
`i.e.,
`
`In the top of the figure we show the transmission of packets with a distance of 3? time units. Each packet
`experiences an independent unnorrnalized network delay with U; denoting the unnormalized network delay of
`the jth packet in the talkspurt. Due to the additional delay required for proper sequencing, the arrival time of
`the jth packet at the receiver, denoted by Tf,
`is given by
`
`J
`Ti'=:i‘l1]aXJ{U;+ (s— 1):}.
`
`‘
`
`t 1)
`
`
`
`

`
`T24
`
`BJ. Demp.t'£.’_t' at (If. / Crmipttr£'r' Nenvrirks and ISDN .S'y.rr€rri.r 23 ( I996) 7.-'9— 736
`
`Assuming that no playback discontinuities have occurred before the arrival of the jth packet, the scheduled
`playback time for the jth packet, denoted by T2‘.
`is fully determined once the first packet has arrived at the
`receiver. As shown on the bottom timeline in Fig. 1, TI.‘ is given by
`
`T_;'=U,+v+(j—t)r.
`
`(2)
`
`l, the fourth packet arrives after its playback time, that is, T4‘ < T5’. causing a discontinuity, or gap.
`In Fig.
`in the playback of the talkspurt. Once a gap occurs in the playback of a talkspurt, playback synchronization is
`lost. and all subsequent packets in the talkspurt, e.g., the fifth and sixth packets in Fig. I, begin playback after
`their scheduled playback times.
`We assume that during the transmission of a talkspurt there is an arbitrary period, the so-called error period,
`during which zero or more packets are dropped by the network. We assume only one error period per talkspurt,
`but allow multiple consecutive packets to be dropped in an error period. The beginning of the error period is
`uniformly distributed over the length of a talkspurt. Since packets of a talkspurt arrive at the receiver in the
`order in which they are transmitted. the receiver detects losses as soon as a packet arrives out-of-sequence.
`After detecting a loss, a retransmission procedure is initiated. From the viewpoint of the receiver, the time to
`recover lost packets via retransmission is fully determined by a roundtrip network delay. That is, processing
`times for retransmissions at the receiver or the sender are assumed to be small and not considered in our model.
`
`Also. we assume that the sequence of lost packets in an error period can be retransmitted in a single packet.
`This assumption is realistic for network or transport layer protocols since the maximum packet size is much
`larger than the typical voice packet. Thus, the retransmission time. denoted by R. is taken to be the sum of the
`network delays for two packets, the packet from the receiver carrying the retransmission request to the sender
`and the single-packet retransmission from the sender to the receiver. The distribution function of R is given by
`FR = FU -® FU where Q3) is the convolution operator.
`
`3.2. Aaa!_\'sis of end-to-end model
`
`In this subsection we develop an exact analytic expression for the probability of continuous playback of
`a talkspurt. First, we derive the desired probability assuming an error—free scenario. Then, we extend our
`expression to consider error periods.
`
`Probabi!i’r_v of continuous playback without‘ errors
`3.2. I.
`We are concerned with the occurrence of a gap in the playback of a talkspurt. We thus define random
`variables G; (1 3 i’ 5 N) that indicate the presence of a discontinuity in the playback. By setting
`
`V
`
`if E = 1.
`
`(}',-:=
`
`0
`max -[0, T,-" —~ T,-"}
`
`il'G;_}=0, £551.
`otherwise
`
`(3)
`
`we obtain G, = 0 if a packet with index i or less arrives after its playback time. Since the arrival of the first
`packet sets the playback schedule and cannot cause a gap, that is, Ti‘ — Tf’ = V, we set G1 = V. For a talkspurt
`with N packets, GN > 0 indicates that no discontinuity has occurred during playback of the entire talkspurt.
`Note that in Eq. (3), G; = 0 for the itb packet is feasible in two scenarios. Either no gap has occurred
`before packet i and packet E arrives after its playback time, or a gap has occurred before the arrival of packet
`1'. Therefore, by denoting P{G,- = 0} as the probability of G; = 0. we obtain for 2 g i 3 N:
`
`P{G,- =0} =P{G,-_; = 0}+P{G,'_1> 0 and T: <
`
`(4)
`
`The second term on the right side of Eq. (4) is the probability that the ith packet causes the first gap in the
`playback of the talkspurt. in this case, all packets with index less than i have arrived before their respective
`
`

`
`BJ. Denipsey et at’. I Computer Nenvorkx and ISDN 5'_1'.rtem.r 28 (I996) 7.’9—736
`
`7'25
`
`playback times. It follows that packet 1' could not have arrived earlier than any packet with a smaller index. that
`is.
`
`ll
`
`T,"
`
`_n*|iax_{U,;+(j—1)3f}=U.-+(i—[)3
`_j'-— .....l'
`
`Substituting Eq. (5) into Eq. (4) and using Eq. (2) yields
`
`P{G,'=0}=P{G,'_| =0}-l-P{G,'_: >0 and V-l-U1< U,-}.
`
`(5)
`
`Fixing the delay of the first packet, i.e. U1 =1‘, in Eq. (6) gives an expression for the conditional probability
`
`P{G.-=O|U; =r}=P{G,~_,=0|Ut =:}+P{G;_1 >0|U1 =r}P{U,->V+z|U. =r}.
`
`We then recursively compute the probability for continuous playback, i.e., GN > 0, as follows:
`OC-
`
`P{GN>0}=I—/P{GN=0|U.=r}dFU(r).
`
`0
`
`(7)
`
`(3)
`
`3.2.2. Probabiiiry of continuous playback in the presence of errors
`In the presence of errors, gaps in the playback of a talkspurt may result from delay jitter or from a failure of
`the retransmission procedure to recover lost packets before their playback times. In this subsection we calculate,
`P{(n,k)—gap}. the probability of a gap in the playback of a talkspurt, given that the network loses k consecutive
`packets with index n — k.n — k + l. .
`. .,n — 1. We exclude the loss of the first packets in a talkspurt,
`i.e.,
`n > it + 1. Note that in a talkspurt containing an error period. the arrival time of the jth packet is obtained by
`calculating the latest packet arrival with index less than j that is not lost in the network. Thus we obtain for
`Tf’ that
`
`T;* =
`-
`
`max_{U;+(l'-IJT}
`_
`“L-""
`_{U,- + (J — l)x}
`max
`I--1.....n—k—I.n.n+l.....;
`
`ifj§n—k—l,
`.
`otherwise.
`
`(9)
`
`For calculating the probability of discontinuous playback in the presence of errors. we must consider two
`cases that can result in gaps. First, a gap may be due to an untimeiy retransmission of the lost packets. We refer
`to this case as an error gap or E-gap. Second. a gap may result from excessive delay variations, independent
`of the loss of packets. This case is referred to as ajitter gap or J-gap. Under the assumption that the network
`loses k consecutive packets with index n — k.. .
`.
`, n — 1, we denote an error gap by E:-gap and a jitter gap by
`Jfi-gap. Given this assumption then, P{(n.,k)-gap}. the probability of a gap in the playback of a talkspurt.
`is
`given by
`
`P{{n_.k)-gap} = P{E:—gap} + P{no IE‘:-gap}P{J:-gap [ no E:-gap}.
`
`(10)
`
`The calculation of P{(n.I:)-gap} is performed in three steps. We first calculate the probability of an Eflgap.
`Next. using an approach similar to that of the previous subsection, we define random variables G; that indicate
`the occurrence of a J,'f—gap at or before the arrival of packet i. We then calculate PU:-gap | no }E‘f,~gop}, which
`is the probability of a Jf,‘-gap in the talkspurt under the condition that the lost packets are retransmitted in a
`timely fashion. Note that a jitter gap can occur before or after the lost packets are due for playback. In the
`latter case. the discontinuity occurs independent of the retransmission procedure.
`First we consider the probability of gaps due to untimely retransmission. Recall that the arrival of the nth
`packet. that is, the first packet after the sequence of lost packets, invokes the retransmission procedure. Recall
`also that the time necessary for retransmission is denoted by R with FR = Fy ® Fu since R is the sum of two
`
`
`
`

`
`726
`
`8.}. Demp.re_v er al./Corripurer Nenvr;-rks and ISDN Sy.t.'em.r 28 (1' 996) 71 9- 736
`
`network delays. one for the control packet issued by the receiver and the other for the retransmission from the
`sender. For retransmission to be untimely, the difference between the playback time of the (H — Ir — l)st packet,
`i.c..
`the first
`lost packet, and the arrival time of the nth packet must be less than R, the time necessary for
`I
`retransmission. Thus, the probability of an E,‘-gap is
`
`P{Efi-sap} = P{T.f_i - Ti’ < R}
`
`=p{_|ma;i1{Uy+(;—1)x}>v+U.+(n—kw1):—R}.
`
`l;= ._...l'I— ‘— .1:
`
`U”
`
`Using fixed values for the retransmission time, R = r. and the delay of the first packet, U. =1, we obtain from
`equation { l l ) that
`
`P{J_:j tr:ax_1”{r,U;+(j—l)JT}>(1/+r+(n—k—l)E—r)[U.=t‘,R=r}=
`
`(I2)
`
`n—k—l
`
`=[— P{V+(n—k—l)?>r}Fg(l/+r—k.Y—r) H FU(V+!+(n—k—j)E—r)
`1:2
`
`In Eq. (I2), we have used the independence of network delays. Now we tincondition the expression in Eq.
`( 12) by integrating over the retransmission delay and the delay of the first packet in the talkspurt. That is,
`P«[Efi-gap}=]/l — P {V+(n—k— l)JT>r}Fy(V+t‘—kf—r)
`
`n—k—|
`
`HFU(v+:+(n—k—,i),r—r)
`j:2
`
`dFR(r)dFu(r)
`
`(13)
`
`v+(n—.'.-—Ir
`
`= I —]
`
`r
`
`f
`
`i=0
`
`Fg(V+t—k:'c—r) H FU(V+r+(n—k—j)I—r)dF,q(r)dFU(r).
`
`n_k_I
`
`3:2
`
`In the following we assume that retransmission is timely, that is, an E,"—gap has not occurred. We compute
`P{J:—gap|n0 Efi-gap}, the probability that ajitter gap occurs in the playback of a talkspurt under the assumption
`of timely retransmission. Similarly to Eq. (3), we define random variables G,-, such that G, = 0 ifa packet with
`index i’ or less arrives after its playback time. With our assumption that packets in — k,n — k + l.. .
`.
`, n — I are
`lost and do not arrive at the receiver we obtain for 1 3 i 5 n — k — I or it 3 i g N
`
`V
`
`ifi'=l.
`
`0"‘
`
`0
`max {0, Tf - T,“}
`
`ifs,-_.=0.t'¢1,iaen,
`otherwise.
`
`(1)
`
`With this definition, P{GN = O} is the desired probability that, assuming timely retransmission, a jitter gap
`occurs in the playback of a talkspurt. Since the definition of G; is recursive, we must compute P{G; = 0} for
`all values of t’. From the definition in Eq. (I4), P{G. = 0} = 0. That is.
`the first packet sets the playback
`schedule and cannot cause a jitter gap. Also, the nth packet cannot cause a jitter gap since its arrival
`invokes
`the retransmission procedure, which could not be timely if the nth packet arrived after its playback time. Hence
`P{G,, = 0} is defined to be the probability that a jitter gap occurs before the nth packet,
`i.e., P{G,, = 0} =
`P{G,,_j._. = 0}. Two cases remain to be considered: 2 3 t' 3 n — k — l and n 3 1' 5 N.
`
`

`
`BJ. Demp.9e_v er m‘./Crmrpmer Ne.-‘wrmlzt and ISDN 5,vsrem.r 28 (£996) 7 ."9— 736
`
`727
`
`We first calculate the probability of a Jf—gap at or before the ith packet where 2 g :7 _<_ n — k — 1. In this case
`the ith packet arrives early enough to ensure successful retransmission of the lost packets, but the ith packet
`can cause a jitter gap by arriving after its playback time. That is, the conditions for the ith packet resulting in
`
`a jitter gap are
`
`7"F’>T}"'
`
`and Tf'ST:‘<7",';'_;,—R
`
`for2§t'§n—k—l.
`
`Hence. for 2 3 i 3 n — k — l,
`
`P{G,- =0}=P{G,-_. =0} +P{G;_. > O and T,-"' 3 7}" § ,f_k — R}.
`
`(15)
`
`(lo)
`
`The last term in Eq. ([6) is the probability that the first jitter gap in the playback occurs upon the arrival of
`the ith packet. By using a similar argument as for the derivation of Eq. (5), the arrival time of the ith packet
`is U; + (E — IF, and Eq. (16) can be rewritten as
`
`P{G,-=0]-=P{G,'_| =0}"l' P{G,'_| >0and l/+013 U,’ g l/‘l‘U| +(.PI—tlC—f)T—R}.
`
`(17)
`
`Equation ( 1?) is equivalent to
`
`P{Gj=0}=ffP{Gf_1=0lU]=f,R= .?'}dFR(t") dFy(f)
`
`+[jP{G,~_1>0|U.=r,R=r}(Fu(V+t‘+(n—-k—i)T—r)—FU(V+r))dFR(r)dFU(r).
`
`(I8)
`
`We have shown how to compute P{G,- = 0} for E g n — k — l. Next we consider P{G; = 0} for i > 11. Since
`packets with index greater than 1'! cannot affect the retransmission procedure. we obtain with the definition in
`Eq.
`( I4):
`
`P{G,-=0}=P{G,-_|=0}+P{G;_1>0 and T,-“ST,-fl}
`
`forn+l§i§N.
`
`(19)
`
`Note that the second term on the right side of Eq. (19) is the probability that the ith packet causes the first
`gap in the playback of the talkspurt. In this case, all packets with index less than E have arrived before their
`respective playback times. It follows that packet i could not have arrived earlier than any packet with a smaller
`index. that is.
`
`T-"=
`I
`
`_{UJ-+(j—l)T}=U,-+(r'—1)f
`max
`,i=l .....n—k—l .H.!1+l.....I
`
`forn+l§£§N.
`
`(20)
`
`Then. Eq. (19) yields, for in + I g i 3 N,
`
`P{G;=0}=fP{G;_1=0|U| =f}-l-P{G,'_| > OI U] =l‘}P{l/‘iris U,'}ClFgy(1‘).
`
`r
`
`At this point we can compute from Eq. (10) P{(n,k)-gap}, the probability of a gap in the playback of a
`talkspurt given that the network loses 1: consecutive packets of index n — k. . .,n — I. To compute Eq. (10),
`we have P{Ef‘,—gap} in Eq. (13) and P{J:-gap | no E:-gap} by recursively evaluating Eqs. (I8) and (21).
`
`3.3. Numerical examples
`
`We present numerical examples that apply our analysis for determining the effectiveness of retransmission
`without disrupting the continuous playback of voice packets for various network and protocol parameters. We
`present three examples, where in each example the‘ effectiveness of retransmission is expressed in terms of the
`probability of maintaining playback continuity during a talkspurt. as derived in the previous subsection.
`
`
`
`

`
`728
`Table I
`
`Network parameters
`
`8.J. Derrtpsey er til. I Cmnpurer Nenvnrlcr and ISDN Systems 28 (I 996) 7! 9-736
`
`Example
`
`I
`2
`3
`
`Packetization
`interval (3)
`20 ms
`20 ms
`20 ms
`
`Packets in
`talkspurt (N)
`20
`20
`20
`
`Average network
`delay
`'
`15 ms
`I5 ms
`2.10.20.30.40 ms
`
`Network delay
`distribution (PU)
`E;
`El. E3. El,
`E;
`
`0 Example l shows the sensitivity of the probability of continuous playback in the presence of errors to
`different control time values.
`
`o Example 2 shows the degree to which the unnormalized network delay distribution influences retransmis
`sion—based error recovery.
`0 Example 3 shows the effects of the average unnormalized network delay on retransmission—based error
`recovery.
`
`For the unnormalized network delay, we consider delay distributions with different variance, namely Erlang
`distributions with k exponential phases, denoted by Erlang~t'c or E;,., for k 2 1. Networks with large delay
`variations are modeled by E., that
`is, an exponential distribution; for moderate and low delay variations we
`use. respectively. E3 and E6. In accordance with our empirical delay measurements (see Section 4) and studies
`on wide-area connections (e.g.. [18]). we select E; as the default unnormalized network delay distribution.
`The selection reflects that delay variations over short periods of times, such as the duration of a talkspurt. are
`generally modest.
`The parameters for our examples are presented in Table I. The default average unnormalized network delay
`is set to l5 ms. The default packetization interval is fixed at Y = 20 ms, a value commonly used in extant voice
`protocols [19], and the default number of packets in a talkspurt is N = 20. Thus. each talkspurt has a duration
`of 400 ms. at value motivated by our empirical measurements of packet voice traffic in Section 4.
`
`3.3.}. Exanrple 1: effects of the control time on retransntissiort
`Recall
`that in our end-to-end model we specify a single error period during the transmission of a talkspurt.
`The beginning of the error period is uniformly distributed over the transmission time for the talkspurt. Multiple
`consecutive packets can he lost during an error period. Here. we consider error periods in which zero, one. two.
`or three packets are lost. An error period in which E packets are lost is referred to as an i-error scenario.
`Figure 2 shows the probability of continuous playback of the talkspurt under variation of the control time. The
`figure depicts four curves representing the respective error scenarios. The 0-error scenario is included in order
`to consider the effects of delay jitter on the playback continuity of talkspurts whose end-to-end transmission is
`error-free. From the 0-error curve we see that a control time of roughly V = 60 ms is required to compensate
`for the delay jitter in the network. The .'-error curve gives the probability that playback is continuous for a
`talkspurt during whose transmission exactly one packet is lost in the network and subsequently retransmitted.
`With V = 60 ms.
`the I-error curve shows that approximately 70% of single—packet losses are successfully
`recovered through retransmission. As the control time is lengthened, successful retransmission is more likely,
`and at V = 100 ms, successful retransmission in both the }-error and 2-error scenarios occurs in over 90% of
`the cases.
`
`Recall that the feasible range of control time values is determined by the end-to-end delay restriction. In our
`example. the sum of the packetization interval and the network delay on the average account for only 35 ms
`of the total end-to-end delay. I-Ience control times on the order of V = l00 ms are feasible for all but the most
`stringent delay requirements.
`The packetization interval plays an important role in the retransmission algorithm. In a k-error scenario. the
`average amount of time that elapses between the occurrence of packet loss and its discovery at the receiver is £1?
`since the receiver discovers packet loss when the first out-of-sequence packet arrives. Hence the probability 0|‘
`successful retransmission in a k-error scenario will be low when V<. k}. This can he observed in Fig. 2 where
`
`

`
`BJ. Dempsey at at./Crrrnpttrer Netv.-'ork.9 and ISDN S_v.rrems 28 ( I996) 719-736
`
`729
`
`Playback]
`Prob[Continuous
`
`0
`
`10
`
`20
`
`30
`
`40
`
`50
`
`60
`
`TU
`
`80
`
`90
`
`100 H0
`
`120
`
`Fig. 2. Retransmission effectiveness for an E3 (Erlang—2) unnormalized network delay distribution.
`
`Control Time (ms)
`
`the recovery rate for control times of less than k? is roughly 5%. e.g.. for the 3-error scenario at a control
`time of V = 60 ms. 6% of retransmission attempts are successfu