An Integrated Source Coding and Congestion Control Framework for
`Video Streaming in the Internet
`Kang-Won Lee* Rohit Purit Tae-eun Kim* Kannan Ramchandrant Vaduvur Bharghavan*
`* Coordinated Science Laboratory, University of Illinois at Urbana-Champaign
`t Electrical Engineering and Computer Science, University of California at Berkeley
`{ kwlee, tkim, bharghav} @ timely.crhc.uiuc.edu {rpuri, kannan} @eecs.berkeley.edu
`
`match between the end-to-end requirements of the video source
`Abstract-We describe a framework for video transmission over the In-
`ternet that features the coordinated operation of an application-layer video
`coding algorithms and the capabilities of the network as it is
`source coding algorithm and a transport-layer rate control mechanism. The
`deployed today.
`proposed video coding scheme operates on a progressively encoded video
`This underlines the need for an efficient transcoding mech-
`stream and provides graceful resilience to network packet drops. The ro-
`bustness is enabled through a generalized Multiple Description 0) cod-
`anism that. converts the MR-based prioritized bitstream into a
`ing strategy, architected as an adaptive array of packet-erasure correction
`non-prioritized packet stream while ensuring graceful quality
`codes. The video coding algorithm is matched to an efficient and reactive
`degradation when there is a packet loss. In this paper, we pro-
`rate control mechanism that minimizes the fluctuation of rate and uses the
`pose a transcoding mechanism based on Multiple Description
`profile of past losses to adjust the rate in a TCP-friendly manner.
`While the two constituent algorithms identified above are interesting in
`(MI))’ robust source coding principles, anchored on Forward
`their own right, a key feature of this work is the integration of these al.
`Error Correction (FEC) channel codes.
`gorithms in a simple framework that seeks to maximize the expected deliv-
`From the end user’s viewpoint, a medium but constant quality
`ered video quality at the receiver through coordinated adaptation of the two
`components. We present simple simulation results to illustrate the utility of
`is more desirable than a high and jittery one. For a smooth video
`our approach.
`reception, we want the variation of the sender’s transmission rate
`to be as small as possible. However, the conventional linear in-
`crease multiplicative decreased (L1MD)-based congestion con-
`trol causes large fluctuations in the transmission rate even in the
`absence of congestion. In this paper, we propose an augmen-
`tation to LIMD congestion control that achieves low rate fluc-
`tuations (hence is more suited to streaming applications) when
`the connection capacity is invariant without compromising the
`responsiveness to the onset of congestion.
`While the source transcoding algorithm and the rate control
`algorithm are useful contributions in their own right, a key as-
`pect of our approach is the coordination of the source coding and
`rate control algorithm in an integrated architecture. In the pro-
`posed system, the source transcoding module and the congestion
`control module exchange connection state in a very simple yet
`efficient manner.
`To summarize, the following are the three contributions of the
`paper.
`1. In the source transcoding layer, we propose a simple and fast
`method of transforming an MR bitstream into an MD packet
`stream using efficient erasure codes [7], which is optimal in
`the sense that the delivered quality at the receiver is maximized
`when the channel condition is described accurately.
`2. In the transport layer, we propose a TCP-friendly rate control
`algorithm that reduces rate fluctuation when the connection ca-
`pacity is invariant and at the same time quickly reacts to changes
`in the connection capacity.
`3. The ‘glue’ that holds the source layer and the transport layer
`together is the interaction layer, which packages the connection
`state in a way that can be used effectively by the source layer.
`In the proposed system, the transcoder requires the trunsrnzssiori
`profile of the connection, and the rate budget. This information
`is inferred by the interaction layer by monitoring the progress
`of the connection in the kernel space, and efficiently (without
`context switches) passed up to the user space.
`
`I. INTRODUCTION
`In the current deployment of the Internet, routers in the net-
`work are oblivious to the structure or content of the packets that
`traverse through them. Typically, tail-drop routers discard in-
`coming packets when output queues are full, and random-drop
`routers discard packets at random as the output queues start to
`fill up. The sender estimates the available connection capac-
`ity by probing the network, i.e. periodically incrementing the
`transmission rate till some router drops a packet due to queue
`overflow. Upon detecting this loss via end-to-end feedback from
`the receiver, the sender throttles the transmission rate by a large
`multiplicative factor (typically 0.5) [ 11, (21,131.
`This network design is inappropriate for video packet flows
`because of two reasons. First, typical video-encoded bitstreams
`are highly structured, e.g., characterized by a hierarchy of im-
`portance layers’. The design of multiresolution (MR)-based
`scalable/layered/progressive encoders is becoming increasingly
`popular in the source coding community for both still images
`and motion video [4], [5], [6]. However, routers may drop newly
`arriving higher priority packets in favor of already-queued lower
`priority packets, and may deliver more partial frames rather
`than fewer complete frames. Second, most current conges-
`tion control algorithms follow the “probe-lose-throttle” princi-
`ple and hence experience significant variations in instantaneous
`rate even if the network resources available for the connection
`remain invariant. This can lead to a potentially high variance
`in the delivered video quality unless the sender accurately esti-
`mates the average sending rate, which is difficult to accomplish
`in dynamic network conditions. In su”zry,
`the current de-
`sigil of the Internet is best suited for transporting non-prioritized
`packet frows that are inserisitive to rate frUCtUQtiOI2s mtd to the
`relative position ofpacket fosses. There is thus an inherent mis-
`
`‘Examples of imporfurif video signal descriptors include anchor-frame data
`(e.g. MPEG I-frames), course information such as DC and low-frequency AC
`transform data, and that of fess important information include high-frequency
`AC transform data and perceptually-insignlfimt textured areas in the picture,
`etc.
`
`2MD coding refers to the generation of multiple independent and unprior-
`itized representations of the same source stream having the property that the
`reconstruction quality is proportional to the number of representations available
`at the decoder.
`
`0-7803-5880-5/00/$10.00 (c) 2000 IEEE
`
`747
`
`IEEE INFOCOM 2000
`
`VIMEO/IAC EXHIBIT 1014
`VIMEO ET AL., v. BT, IPR2019-00833
`
`

`

`The goal of our work is to exploit the power of shared infor-
`mation between the transport layer and the source coding layer
`- this approach has also been explored in several recent works,
`e.g. using different constituent components in [8] and using a
`layered coding framework in [9]. Figure 1 describes a simple
`block diagram of the system, and the components proposed in
`this paper.
`The remainder of this paper is organized as follows: Section I1
`describes the transcoding scheme. Section I11 presents the con-
`gestion control algorithm. Section IV integrates the two com-
`ponents via the interaction layer. Section V evaluates the per-
`formance of our system via simulation. Section VI places our
`work in the context of related work, and Section VI1 concludes
`the paper and offers directions for future work.
`
`11. FORWARD ERROR CORRECTION
`(FEC)-BASED
`MULTIPLE DESCRIPTION CODING
`In this section, we first describe the transcoding mechanism
`that converts the prioritized multiresolution (MR)3 bitstream
`into an unprioritized multiple description (MD)4 stream using
`efficient erasure channel codes. The quality profile, i.e.
`the
`quality experienced at the receiver as a function of the num-
`ber of packet losses of the generated stream has the property of
`graceful quality degradation with respect to packet losses at the
`receiver.
`We then describe an algorithm that optimizes the quality pro-
`file in the following sense: given a multiresolution bitstream, a
`rate budget (the maximum number N of packets of a length L
`that can be injected into the network) and a transmission pro-
`file (the probability of successfully delivering i packets out of
`N , V i), the algorithm outputs a quality profile that attains the
`maximum expected average quality. Since we are dealing with
`encoding a video source having a fidelity criterion, we invoke a
`rate-distortion (R-D) f r a m e ~ o r k . ~
`
`A. Transcoding Mechanism
`The quality profile reflects the target quality (or equivalently
`distortion d) when any k out of N descriptions are received. We
`use the notation ( k , d(lc)) to denote quality profile, where d(k)
`is the distortion vector with dimension m 5 N whose entries
`reflect the distortion profile. We will refer to the dimension m
`as order of the quality profile, i.e. the number of quality levels
`in the profile.
`
`Fig. 2. Progressive bistream from the source coder partitioned into m layers
`
`3Multiresolution or progressive bitstreams can be embedded bitstreams [lo],
`wherein the reconstruction quality is potentially successively refined by every
`succeeding bit or scalable bitstreams where new blocks of data successively
`refine the previous blocks of data as in progressive JPEG.
`4Briefly, MD coding is concerned with the task of encoding a source into N
`descriptions in such a manner as to optimize the delivered source fidelity if any
`k out of the N descriptions are received for all k 5 N [ll], [121, [13]. The
`word description is synonymous with packet in this paper.
`'The R-D curve for a source bitstream is a plot of the quality (equivalently
`distortion, i.e. lower distortion implies higher quality and vice versa) and the
`number of bits used to describe the source. As intuitively expected, the R-D
`curve is monotonically decreasing.
`0-7803-5880-5/00/$10.00 (c) 2000 IEEE
`
`Secrionl
`
`Section?
`
`I
`
`n-m+l
`
`n-m+l
`
`' '
`
`. . .
`
`. . .
`
`Seclion i
`
`1
`
`n-m+l
`
`. ' '
`. . .
`
`. . .
`
`Section m
`
`1
`
`Descriprion I
`
`n-m+l
`
`Descriplionn-m+l
`
`FEC
`
`FEC
`
`. . .
`
`FEC
`
`. . .
`
`n
`
`Descriprionn
`
`Given N and d(k), and a progressive bitstream, the bitstream
`is marked at m different positions (see Figure 2) which corre-
`spond to the attainment of the distortion levels d(k), and is thus
`partitioned into m sections or resolution layers. The ith layer is
`decodable when the number of erasures does not exceed m - i.
`We can achieve this by using the family of Reed-Solomon
`erasure-correction block codes [ 161, which are characterized by
`the optimal code parameters ( N , k , N - k + 1),6 which can cor-
`rect any (N - k ) erasures out of N descriptions.
`We split the ith quality layer into ( N - m + i) equal parts'
`and apply the ( N , k , N - k + 1) Reed-Solomon code to get
`the contribution from the ith layer to each of the N descrip-
`tions. The contributions from each of the m quality levels are
`concatenated to form the N descriptions (see Figure 3). Thus,
`every description contains all m layers, and all N descriptions
`are equal in information content as intended. The combination
`of the progressively encoded bitstream and the family of Reed-
`Solomon codes enables us to attain quality level i provided that
`the number of erasures does not exceed m - i, which results in
`the graceful degradation profile that we are after.
`Now the question is how to optimally partition the resolution
`layers in Figure 2 and 3. In the next section, we will describe an
`algorithm that achieves this goal.
`
`B. Optimal Allocation Algorithm
`In this section, we propose a fast algorithm for choosing the
`quality profile d(k), that is optimal in the sense of maximizing
`the expected quality delivered at the receiver. We assume that
`our model is characterized by the transmission profile, qi ( N ) ,
`where i = -1, . . . , N - 1 denoting the probability that i + 1 out
`of N packets are delivered to the destination.
`In this section we prove some key results for the case of a con-
`tinuous R-D curve that can also be applied for the case of prac-
`tical discrete R-D characteristics and would hold up to a convex
`hull approximation, but we do not present the extension due to
`lack of space. Since the quality is a one-to-one function ( D ( r ) )
`of the rate r , ascertaining the quality profile d(k) of order N
`corresponds to finding the rate partition (R = Ro, . . . , R N - ~ )
`of the bitstream (see Figure 2). Note that Ri 5 Rj for i < j
`from the embedding requirement of the source.
`
`6An ( n , k , d ) hlock code is defined by a length n code with k user symbols
`and a minimum distance of d, i.e. it can correct (d - 1) erasures.
`7For practical source streams that are bit granular, such divisibility might not
`be possible always. Such issues are not addressed in this submission for sim-
`plicity. But the results proved here are can be extended to accommodate these
`issues.
`748
`
`IEEE INFOCOM 2000
`
`

`

`raw video stream
`
`prioritized
`video stream
`
`- v y -
`
`Transcoder
`
`channel state 1
`
`MD video stream
`
`display
`
`A
`
`video sources
`
`Transport
`Rotocol
`
`feedback
`feedback
`Fig. 1. Block diagram of the video transmission system:components discussed in this paper are highlighted.
`
`Define the expected distortion ED:
`
`N - 1
`
`qj . D ( R j ) ,
`
`E D = 9-1 ' E +
`j = O
`where E equals the source variance, the distortion encoun-
`tered when the source is represented by zero bits. When the
`codes as outlined in the above section are used, the total rate
`used Rt equals :
`(RI -mN+,..+
`( R N - ~ - RN--2)
`Ro
`Rt=-N+----
`N
`N
`1
`or equivalently,
`
`(1)
`
`(2)
`
`2
`
`N - 1
`Rt =
`j = O
`
`a j R j
`
`(3)
`
`Problem Statement Given the number of packets N , each
`packet of size L (i.e. a total rate budget R* = N . L), an embed-
`ded bitstream with rate-distortion curve D ( T ) , and the transmis-
`sion profile qi; Find R that minimizes E D subject to Rt 5 R*
`(the resource constraint) and
`
`We note that the R-D curve for any source, is theoretically a
`convex curve with the property that X(Ri) > X(Rj) f o r i < j
`where X(R) denotes the absolute value of the slope at point
`( R , D(R)). We observe that if constraint (5) were not present,
`the problem stated above would default to a standard bit alloca-
`tion problem [ 171, generalized to include the notion of weights
`in the form of ai and qi. The optimal solution subject only to the
`resource constraint is easily found using the theory of Lagrange
`Multipliers and we briefly illustrate the procedure. Introducing
`the Lagrangian [ 181 for this problem, we get :
`
`N - 1
`
`N - 1
`
`Merge all points in the rising and the flat
`section to equivalent a and q
`
`Fig. 4. The monotonizing algorithm that gives theform of the optimal solution.
`
`over the channel state information qi. Hence, in general the con-
`straints of (5) cannot be ignored.
`We now prove a key result that sheds insight into the nature or
`form of the optimal solution to the original problem that does not
`ignore (5) yet enables us to apply the method described above.
`
`Fact vz 2 z,
`
`then in the optimal solution, R, = R,+I.
`
`Proof Assume that there exists an optimal solution such that
`Rn
`Then take away AR bits from Rn+l and give
`( Y A R ) bits to R, (so that the resource constraint and the
`rate constraints (5) are satisfied). Now, the net decrease in the
`E D cost which is the difference between the decrease in cost in
`the nth term and the increase for n + lth term is:
`
`Decrease = ARCX,+~[*A(R,)
`
`f f n
`
`- *X(Rn+l)] ffn+1
`
`(8)
`
`Since E 5 % and A(&) > X(R,+1), the decrease
`is positive, which is a contradiction because if a solution with
`R, < R,+1 were optimal, we could still improve on the solu-
`tion by successively decreasing Rn+l and increasing R, while
`satisfying the rate constraints. Hence, R, = Rn+l in the opti-
`mal solution. Q.E.D.
`observations from the above result. Firstly, if 2 5 z,
`solution based on the nature of the 2 profile. We make two key
`The above result serves to characterize the form of the optimal
`the
`optimal solution to the original problem is the same as that to
`a reduced problem where R, = Rn+l is replaced by RL so
`that cy: = cy, + a,+1 and q: =;' qn + q,+l. Also we see
`that if 2 5 3.S then 2 5 2 = (Y,+(Yn+l < w. In
`qn+qn+l - P n + l
`P n + l
`to a monotonically increasing or flat section in the 2 profile,
`other words, the above observation can be successively applied
`and all the corresponding rate variables are equal in the optimal
`solution thus reducing the dimensionality of the problem.
`Based on the above observations, we propose an O ( N ) al-
`IEEE INFOCOM 2000
`
`(6)
`At optimality, the partial derivative of the Lagrangian func-
`tion with respect to Ri, i = 0 , . . . , N - 1 and A equals zero.
`This yields :
`Qi d D ( R i )
`i = O ,..., N - 1 .
`(7)
`+ A Z O .
`dRi
`In other wokds, at optimality the respective slopes are in the
`proportion s. Since Q .
`is a constant at optimality, it
`qi
`ai
`is clear that for monotonically decreasing 3 , the absolute value
`Q;
`has to be a monotonically decreasing sequence in i.
`of
`Since the rate distortion curve is strictly convex, it follows that
`for this case, (5) is satisfied automatically. However, monotonic-
`ity of 2 cannot be guaranteed in general as we have no control
`749
`
`(Y.
`
`0-7803-5880-5/00/$10.00 (c) 2000 IEEE
`
`

`

`(d)
`
`(e)
`
`(0
`
`I
`
`I
`
`Q2
`
`Fig. 5 . The optimal allocation algorithm example: (a) 2 = s, 3 =
`w, % = 0.03 % -
`-
`92
`0.1 % - 0.03 a4 - 0.01
`o.25 (b) After applying the algorithm. we get
`,
`w, 2 =
`o . 2 5 , q4
`o , 5 , q3
`in terms of new variables: 9 =
`( c ) Expressing in terms of the original variables: 2 =
`0 . 2 5 ' q j - 0 . 2 5 '
`91
`0.075 Qg - 0.03 a4 = D.01
`o,5 , qs
`o,15 (d) Unknown rate variables. (e) Solu-
`o . 2 5 , ql
`tion to the monotonized problem in terms of new variables. (f) Solution in
`terms of the original variables.
`
`sively to all packet losses, which is appropriate behavior for
`losses caused by persistent congestion (i.e. when there is a
`reduction in the "fair share" of the network bandwidth for the
`connection) but inappropriate behavior for losses due to non-
`persistent congestion (e.g. losses induced by the sender probing
`for additional bandwidth, or random channel loss in wireless
`networks). As we mentioned above, LIMD throttles the sending
`rate by a multiplicative factor p, which is typically set to 0.5. 0
`must be set to a large enough value that the sender will throttle
`its rate aggressively in response to persistent congestion. On the
`other hand, this causes a large fluctuation in the instantaneous
`rate even in steady state, when losses are only induced by the
`linear probing mechanism of LIMD. Large rate fluctuations are
`undesirable for several reasons: (a) the sender must estimate the
`average sending rate accurately, which can be difficult in dy-
`namic operating conditions, (b) the sender must buffer packets
`when application sending rate exceeds the instantaneous send-
`ing rate, potentially increasing end-to-end delay and buffer re-
`quirements, and (c) most important to our source coder design,
`it makes computing the transmission profile very difficult.
`We present a congestion control algorithm called LIMD/H
`(LIMD with history) that augments the basic LIMD algo-
`rithm with an additional mechanism to differentiate the cause
`of packet losses and take adaptive action accordingly. The
`LIMD/H congestion control algorithm has the following two
`key features:
`1. LIMD/H uses the history of packet losses in order to distin-
`guish between persistent congestion and non-persistent conges-
`tion.
`2. LIMD/H reacts gently to non-persistent congestion in order
`to keep the sending rate variation to a minimum in steady state,
`but reacts aggressively to the onset of the persistent congestion
`in order to prevent congestion collapse.
`We present the LIMD/H algorithm in three parts. We first
`describe the framework for end-to-end congestion control, then
`describe the LIMDM algorithm, and finally discuss some of its
`properties.
`
`A. Framework for Congestion Control
`In our framework, the evolution of the transmission rate oc-
`curs over discrete time periods called epochs. The sender as-
`signs a monotonically increasing sequence number for each
`packet transmission. At the end of each epoch, the receiver com-
`putes the fraction of received packets over the range of packet
`sequence number during the epoch. The receiver then sends a
`congestion feedback to the sender containing the loss fraction
`0 5 f 5 1. Upon receiving the loss feedback, the sender ex-
`ecutes the LIMD/H congestion control algorithm to adjust its
`sending rate.
`
`B. LIMD/H Congestion Control
`Before describing the LIMD/H algorithm, we revisit the
`vanilla LIMD algorithm for reference. Let T denote the send-
`ing rate, f denote the loss fraction, Q denote the linear increase
`constant, and p denote the multiplicative decrease constant. Us-
`ing LIMD:
`i f f = O , r t r + a .
`
`.
`iff > O , T + T X ( ~ - ~ )
`Ideally, losses that are not induced by persistent congestion
`(such as probe losses) should trigger a gentle throttling of the
`sending rate while losses that are induced by persistent conges-
`tion should trigger an aggressive throttling of the sending rate.
`
`gorithm (Figure 4) which transforms the problem at iteration i
`to a reduced problem at iteration i + 1 such that the optimal
`solution to both problems is identical. We note that, when the
`algorithm terminates, the final will be a monotonic decreas-
`ing curve for which we already have the standard Lagrangian
`solution. Having obtained this solution, in terms of the reduced
`or merged variables, we can unmerge the solution to get the so-
`lution in terms of the original variables. Figure 5 illustrates an
`example of this procedure.
`In general, the complexity for such a problem based on brute
`force methods is 0(2N) [18]. In [15], a similar problem has
`been tackled and the proposed solution is based on a suboptimal,
`greedy, iterative descent algorithm. In contrast, we have a low
`complexity algorithm ( O ( N ) per value of A) that is provably
`optimal. In order to use this scheme for robust video streaming,
`a progressive video encoder is needed. For our experiments,
`we use the 3D-SPMT video encoder [19]. However, standards
`compatible encoding schemes such as h4PEG -2 can also be used
`within our framework.
`
`111. CONGESTION CONTROL
`For the target application, we need the variation in the instan-
`taneous rate to be smooth and small when the connection capac-
`ity is invariant, and we need to generate an accurate transmission
`profile that can be used by the source coder. At the same time,
`we need the congestion control algorithm to be TCP-friendly
`[20], robust, and react quickly to the onset of congestion.
`Congestion control algorithms that are-deployed in the cur-
`rent Internet typically use the linear increase multiplicative de-
`crease (LIMD) paradigm for both window-based [ l] and rate-
`based congestion control [ 2 ] , [3]. In this paper, we are interested
`in rate-based congestion control because this is better suited to
`multimedia applications. Briefly, LIMD periodically adapts the
`sending rate of a connection by gently increasing the rate by an
`additive constant LY upon observing no packet losses (in order
`to probe for additional bandwidth), and aggressively decreasing
`the sending rate by a multiplicative constant p upon observing
`packet losses (in order to alleviate congestion).
`The trade-offs of LIMD are quite well-known: LIMD has
`been shown to be robust, and asymptotically converges to fair-
`ness [21]; on the other hand, it reacts identically and aggres-
`
`0-7803-5880-5/00/$10.00 ( c ) 2000 IEEE
`
`750
`
`IEEE INFOCOM 2000
`
`

`

`I
`
`ow,
`
`Fig. 6. Congestion control example of LIMD and LIMD/H when the available
`bandwidth of the connection has suddenly decreased.
`
`The fundamental problem is therefore to relate the rate throttling
`factor p to the cause of packet loss. An intuitive and highly sim-
`plistic heuristic to predict persistent congestion is the follow-
`ing: if the packet losses observed during an epoch are caused by
`a persistent congestion but the sender does not throttle aggres-
`sively enough, then the loss will continue; on the other hand, if
`the packet loss is a probe loss, then so long as the sender throt-
`tles enough to account for the loss, there will be no loss in the
`next epoch.
`Taking these factors into account, we propose the LIMD/H
`algorithm that keeps track of a very simple history parameter,
`h. The h variable is initially set to 1, is doubled if there is a
`packet loss in an epoch, and reset to 1 if there is not. Thus, the
`h variable is a very simple mechanism to capture the history of
`packet loss in the previous epochs. Based on the value of the
`h variable, LIMD/H exercises a graded multiplicative decrease
`upon packet loss:
`I f f = O , r t r + a , a n d h t l .
`I f f > O , r + - r x ( l - p x h ) ,
`a n d h t 2 h i .
`In case of LIMD/H, we typically set the multiplicative de-
`crease constant ,l3 to be a small value (between 0.1 and 0.2),
`in order to achieve smooth variations of sending rate when the
`available bandwidth is invariant. LIMD/H thus throttles its
`transmission rate gently when there was no packet loss in the
`previous epoch, and progressively more aggressively when pre-
`vious epochs have also experienced packet loss (see Figure 6).
`Of course, the impact of this approach is that if a is maintained
`at the same value as in LIMD, then the channel probe is as ag-
`gressive as before but the rate throttling on loss is less aggres-
`sive, thereby inducing more packet drops. In order to reduce the
`packet drops and in order to design the algorithm to be TCP-
`friendly, we need to adjust the Q: as shown below. In effect, our
`approach is to trade-off the aggressiveness in the increase phase
`for gentle throttling in the decrease phase, while still allowing
`for an exponential increase in the throttling factor in order to ac-
`count for sudden congestion and to prevent congestion collapse.
`It turns out that the above approach is very simplistic and
`can be further significantly improved by maintaining a history
`of the “envelope” of the peaks of the transmission rate (i.e. the
`rates when losses occur), and conditioning p on whether the loss
`occurs within an acceptable band of the envelope of the peaks
`(predicted as non-persistent congestion) or not (predicted as per-
`sistent congestion). Due to space constraints, we do not present
`the enhanced algorithm, which is reported in [223. Nevertheless,
`the basic idea of our approach is to throttle the rate gently upon
`initially observing loss, and then throttling the rate more aggres-
`sively by exponentially increasing the throttling factor when we
`predict persistent congestion. It turns out that because of the re-
`sulting low rate fluctuations in steady state, we can improve both
`the estimate of the sending rate and the transmission profile.
`
`+dw,
`
`C. Properties of LIMD/H
`Property I : If a connection experiences a packet loss proba-
`bility of p , then the average rate in LIMDM is upper bounded
`where a is the increase constant, ,f3 is the de-
`by
`crease constant in LIMD/H, and T is the epoch time (this re-
`sult follows from a simple extension of the standard TCP rate
`computation [20]). The expected variation of rate is between
`J&.
`P--P)+ J&and+
`Property 2: From the above result, LIMD/H is TCP-friendly if
`This yields [a,P] pairs of [0.15, 0.11, [0.33, 0.21,
`a =
`[0.53,0.3], [l, 0.51, etc.
`
`s.
`
`The trade-off is between the aggressive channel probing and
`gentle throttling. Note that simply choosing low values of Q: and
`/3 in the standard LIMD algorithm is insufficient, because that
`causes very slow response to persistent congestion and leads to
`congestion collapse in highly dynamic environments. LIMDM
`provides the fallback to aggressive throttling on persistent con-
`gestion while fluctuating around the average rate value at steady
`state.
`We now briefly revisit the interaction between the transcoder
`and the congestion control modules. These two algorithms are
`very well matched: LIMD/H is able to provide a fairly accurate
`estimate of the connection capacity, and an aggregation of the
`transmission rate samples from the LIMD/H algorithms can be
`used to generate an accurate transmission profile.
`Iv. COORDINATION OF TRANSCODER A N D CONGESTION
`CONTROL
`In this section, we discuss the mechanism employed by the
`transport layer for the transmission profile calculation and its
`actual implementation. Figure 7 shows the interaction of the
`components presented in this paper, i.e. the source transcoder,
`LIMD/H congestion control algorithm, and the interaction layer
`between the two, in the end-to-end architecture of the system.
`Among the input data to the MD-FEC block, Rate-Distortion
`characteristic D ( r ) and the MR stream are user-level inputs, the
`transmission profile q; and the rate budget R’ are connection
`level inputs. Thus, the remaining issues are:
`1. How should the transmission profile and rate budget be com-
`puted ?
`2. How should the interaction between the transcoder and the
`transport be architected ?
`From the network’s point of view, it is easy to compute a set
`of [pi, ri] pairs based on the transmission rate history from the
`congestion control algorithm, where pi is the probability of the
`achieving an effective transmission rate of ri. Given this profile
`and the maximum allowable rate budget R*, we can generate
`exactly how many packets can be transmitted in an epoch, and
`convert rate-based probabilities pi to packet probabilities qi re-
`quired by the transcoder.
`We first describe the interaction of the transport layer and
`source coder in 4 steps, and then detail the transmission profile
`generator algorithm:
`1. When an application opens a socket, it notifies the kernel
`using the setsockopt option.
`2. The congestion control module in the kernel queues the ef-
`fective transmission rate into the kerneldq message queue.
`This message queue is a special queue that is accessible to both
`the kernel and the kerneld daemon.
`
`0-7803-5880-5/00/$10.00 (c) 2000 IEEE
`
`751
`
`IEEE INFOCOM 2000
`
`

`

`, . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`rowre IIreu"
`[-.~econ.wucled
`
`Transport Layer
`
`Fig. 7. End-to-end Architecture of the Proposed System
`
`3. When the kerneld gets scheduled periodically, it dequeues
`the messages from the kerne ldq message queue, and signals
`the appropriate process.
`4. The runtime library then uses the effective transmission rate
`samples in order to update its transmission profile.
`Note that the kernel need not switch context or make an up-
`call to notify the application about the new transmission rate
`samples.
`We maintain a weighted running average of the frequency
`fi(t) of occurrence of each rate sample 7-i, and generate the
`transmission profile by normalizing the frequencies.
`fi(t) + ?fi(t - 1) + (1 - ? b i ( t ) , P i ( t ) = fi(t)/
`
`fi(t).
`
`where y = 0.875 in order to maintain the long term history,
`and ni(t) is the number of instances of 7-i in the kerneldq
`during the tth invocation of the transmission profile generator.
`Additionally, we estimate the rate budget R* in the following
`way. First, we choose R* to be the smallest rate value at which
`the aggregate probability of exceeding the rate is under 5%, i.e.
`
`352 x 240 pixels and each GOP comprises of 16 frames. The
`transmission speed chosen was 1 GOP per epoch, where each
`epoch has a duration equal to 650 msec, which corresponds to
`approximately 26.7 frames per second.
`The reference scheme for our congestion control mechanism
`is LIMD. The reference systems for robust video encoding rep-
`resent a gradual evolution from the dumb MR scheme to the
`proposed MD-FEC scheme. They are:
`1. Multiresolution (MR) Source Encoder
`2. Constant FEC or Equal Error Protection (EEP) and
`3. Fixed Unequal Error Protection (FUEP).
`M R source encoder corresponds to no robustness against packet
`loss