Subject: Re: Which service class for a scalable flow ?

From: [email-masked] (Don Hoffman)
Date: Tue, 2 Jul 1996 21:27:27 -0700

>From: Prakash Jayaraman <[email-masked]>
>
>	I think a proposal to support layered encoding within RSVP was
>given by someone in the last IETF at Montreal. According to the proposal,
>the layer information (number of layers and the Tspec parameter for each
>layer) will be carried by the Path message. The receivers also make
>separate reservations for each layer. In this proposal, there is an
>ordering of the layers. If a receiver wants to reserve layer i, then all
>layers from 1 to i-1 should have been reserved. Someone else argued that
>the ordering may not be appropriate depending on what is carried by the
>layer. (if audio is in layer 1 and video in layers 2- 5, and I don't want
>audio.. what do I do?)  Things will become clear after the minutes are
>out.
>	Prakash
>
>

The RSVP session group proposal was presented by Madhu Sudan at SRI and
reflected some joint work we are doing with them.  It is based on a proposal
for groups in an earlier version of the RSVP spec (BTW, who of the RSVP spec
authors proposed the orginal version of session groups?), but with a few
enhancements. The approach we propose is not quite like described above.
Although the layers are considered to be ordered, the receiver can provide an
ordered bitmap specifying which layers are required by that receiver.  In
your example, the bit for layer 1 would be left cleared, and the bits for
layers 2-5 set to 1.

We seemed to have missed the ID train somehow, but you can find the
draft at:

	ftp://ftp.csl.sri.com/pub/hmc/rsvp/draft-madhu-session-groups-00.txt

This approach allows the receiver to pick and choose the layers, but requires
that the ordering remain the same.  I would like to hear of some plausible
scenarios (based on real coding schemes) where the ordering requirement can't
be made to work (even if it is a bit overconstraining).  It was our opinion
that the complexity of the schemes goes way up if you allow heterogenous
ordering on a per-receiver basis, and we didn't want to open that can of
worms unless there were real reasons to do so.  We did get rightfully trashed
for not allowing the sessions in the group to have differing reservation
styles (e.g., WF, FF or SE), and are going back and re-evaluting our original
requirement that they be the same style.

For a more general discussion of one way to use RSVP and layered codings see
the draft of a paper Michael Speer and I have submitted in:
	
	ftp://playground.sun.com/pub/hoffman/papers/icip-paper.ps.gz

We propose to use success/failure of RSVP reservations to gate membership
in multicast/layer groups. Even have some working prototypes.

Also, Mark Garrett suggested the core layer could go as guaranteed, and
enhancment layers as controlled-load.  I would expect the loss rate in a
properly implemented router to be very similar for both classes of service
(in that neither would be allowed to get appreciably high).  Their main
difference would probably be in the delay bounds.  In most layered coding
schemes, this would require the receiver to set the playout buffer for the
layer with the worst case delay, wasting whatever you spent to get the better
service for the core layer.  >But<, if we did have services with differing
(and well specified at least in terms of ordering) loss rates, but similar
delay characteristics, then I could see this working. (Modulo all the usual
diclaimers about cost models).

Andrew Cambell mentions some work he did with Geoff Coulson with layered
video in a native ATM environment.  I would also point folks to some work
done by Nachum Shacham on "temporally-layered" motion JPEG over native ATM
(IEEE Infocomm '92).  Also, the ST-2 folks have proposed something like
session groups to do something similar (Delgroossi et al, ACM Multimedia'93).

Another tricky thing brought up by someone in an earlier message (maybe in a
different group) is the (implicit?) assumption made in most service models of
flow independence.  The flows of a scalable video stream are unlikely to be
independent (but could have either a positive or negative correlation,
depending on the type of scalablity used).  We are examining an approach
where we specify an aggregate/equivalent flow spec for the entire session
group for the purposes of admission control.  It is assumed in this approach
that the application might have some idea how the layers combine (although
easier said than done).

--
Don Hoffman
Sun Microsystems, Inc.
email - [email-masked], phone - +1 503 297 1580, fax - +1 503 297 2880

---

From: Amit Gupta <[email-masked]>
Date: Wed, 03 Jul 1996 10:24:12 -0700

Hi Don

 :Andrew Cambell mentions some work he did with Geoff Coulson with layered
 :video in a native ATM environment.  I would also point folks to some work
 :done by Nachum Shacham on "temporally-layered" motion JPEG over native ATM
 :(IEEE Infocomm '92).  Also, the ST-2 folks have proposed something like
 :session groups to do something similar (Delgroossi et al, ACM Multimedia'93).

 :Another tricky thing brought up by someone in an earlier message (maybe in a
 :different group) is the (implicit?) assumption made in most service models of
 :flow independence.  The flows of a scalable video stream are unlikely to be
 :independent (but could have either a positive or negative correlation,
 :depending on the type of scalablity used).  We are examining an approach
 :where we specify an aggregate/equivalent flow spec for the entire session
 :group for the purposes of admission control.  It is assumed in this approach
 :that the application might have some idea how the layers combine (although
 :easier said than done).
 
 I am not sure if it is very proper to refer to one's own work, but we did something along the same lines; the Tenet Suite 2 resource sharing works with the "channel groups" abstraction (in addition to specifying the flow spec for individual channels/flows, you also specify the aggregate flow-spec for the group, and the network nodes locally decide between individual vs. aggregate resource allocation), and we also looked at "establishment relationships" among channel group members. 

 I'd like to refer you to my Berkeley research page  http://www.cs.berkeley.edu/~amit/research/index.html, and in particular, the sections on "Resource sharing" and "Inter-channel relationships" for more information.

 thanks

 -amit

---

From: "Steve Blake" <[email-masked]>
Date: Wed, 03 Jul 1996 14:36:12 +22299904

> that the application might have some idea how the layers combine (although

That was me, in the second RSVP WG meeting in Montreal.  My comment was that
admission control algorithms may assume statistical independence for flows,
where, depending on the layering scheme, there could be significant
correlation between the flow rates.  Further, such an admission control
policy is potentially much less efficient than a joint reservation approach
for layered flows.

As a demonstration of this circumstance, consider the following token bucket
parameters for three videoconferencing sequences (this is taken from my
dissertation:
http://www2.ncsu.edu/eos/info/ece_info/www/ccsp/tech_reports/abs/abs9517.html)

                                          Claire     Dave    Salesman

peak rate         (p) (bits/sec)          563520    730260   1135920

token bucket rate (r) (bits/sec)          235290    315300    471030

token bucket size (b) (bits)               39471    229536     80429

EBW @ 10^-9 CLR                           359480    465289    729596

EBW @ 10^-3 CLR                           272189    360531    548008

SMG @ 10^-9 CLR                             1.65      1.66      1.64

SMG @ 10^-3 CLR                             2.18      2.14      2.18

The sequences were encoded using an H.261 encoder with Q=12 (fixed), with
transmission rate shaping constrained by 100 msec of encoding latency and a
token bucket filter.  The token bucket rate was set so that r = 1.3 Ravg,
where Ravg was the average encoder rate over the sequence (this was chosen
conservatively to take into account the fact that the sequences were
relatively short).  The token bucket size was chosen as the minimum needed
to prevent underflow for the given r.  The equivalent bandwidths (EBW) were
computed using Saito's algorithm for a 155 Mbps link with a 256 cell
(0.72 msec) buffer, at the corresponding loss rates (CLR).  The statistical
multiplexing gains (SMG) were computed relative to peak rate allocation for
a target load of 95%.  The PSNRs for all three sequences were above 35 dB
for Q=12.

The two-layer encoding experiments I performed used the H.261 encoder for
the base-layer, with some rather sophisticated rate-control based on token
bucket shaping, and with spectral filtering of the DCT coefficients to
account for perceptual response.  The enhancement layer requantized and
encoded the base-layer residuals, with optional rate-control.  Two-layer
encoding of this type is fairly insensitive to enhancement-layer loss,
since the enhancement layer is coded intraframe.  The consequence of this
is that the coding effiency is reduced, since greater quantization noise
in the base layer leads to reduced motion prediction accuracy.  After
numerous attempts to improve the efficiency of the two-layer codec I
concluded that efficiency invariably drops fairly rapidly as the ratio of
base-layer to single-layer rate declines, to the point that when the
base-layer/single-layer rate approaches 0.33, it is more efficient to
transmit simultaneous single-layer encodings at the respective quantizer
stepsizes.

The other thing I realized was that, since EBW >= r for any semi-conservative
admission control algorithm (at any loss rate), there is no benefit to
transmitting the enhancement layer when the base layer rate at the target Q
would be less than r.  I argue that admission control should be fairly
conservative in this case since the video codec is shaping its transmission
rate and trying to achieve the best encoding quality subject to the token
bucket constraint.  So the rate control scheme I implemented allowed the base
layer Q to float depending on the token bucket constraints I imposed for the
base layer as well as the encoder buffer occupancy, turning off the
enhancement layer whenever the base layer rate falls below r (the actual
mechanism is more complex).  This means that the enhancement layer is
essentially idle except when the base layer is transmitting at or near its
maximum rate, leading to high positive correlation between the rates of the
two layers.

The approach I took for describing the two-layer flow was to specify 4
token bucket parameters: peak rate base (p_b), peak rate total (p_t),
token bucket rate (r), and token bucket size (b).  Admission control for
the base layer would be performed using the tuple (p_b, r, b) at the
desired loss rate; in this case, CLR = 10^-9.  Admission control for the
total stream would be computed using the (p_t, r, b) tuple, at CLR ~= 10^-4,
assuming a smaller cell buffer (128 - 192 cells).  This assumed that the
only scheduling would be FIFO with a dropping threshold for tagged cells
(enhancement-layer cells were automatically tagged by the encoder).
Admission control succeeds only if both tests pass.  Using this approach
I came up with the following parameters, which were chosen so that the
base layer test usually failed slightly sooner than the total stream test:

                                          Claire     Dave    Salesman

peak rate total   (p_t) (bits/sec)        591750    766800   1192800

pead rate base    (p_b) (bits/sec)        300000    396600    603000

token bucket rate (r)   (bits/sec)        258750    346800    518100

token bucket size (b)   (bits)             79500    450000    165000

EBW @ 10^-9 CLR (base)                    316158    417972    635576

SMG @ 10^-9 CLR (base)                      1.88      1.84      1.88

SMG increase             (%)                13.7      11.3      14.8

This resulted in the following admitted loads (worst-case):

           Peak rate allocation   Single-layer VBR   Two-layer VBR

Claire            0.31              0.50              0.58

Dave              0.31              0.52              0.62

Salesman          0.30              0.50              0.58

Even with the very conservative CAC algorithm, the small buffer, and the lame
FIFO+threshold scheduling, I was able to show a statistical multiplexing gain
using a two-layer codec.  I'm convinced that, with proper scheduling, it
should be possible to load a link with two-layer video traffic and still
achieve tight queueing latencies and low loss for the base layer.  This is
fairly important for "high quality" video, as the end-to-end queueing +
propagation latency in the network needs to be subtracted from the total
end-to-end latency (bounded by human factors), and higher jitter in the
network means less opportunity for rate shaping at the encoder.

My conclusions from this, vis-a-vis IntServ, are that, if the desire is to
support heterogeneous receivers with widely varying access capability,
then hierarchical encoding using H.26x or MPEG-x derived algorithms will
not be very effective for the users with "high quality" expectations, and
multiple single-layer encodings, each scaled by transmission rate, will
be a more (network) efficient approach.  If the desire is to increase the
probability of admission and more efficiently utilize the reservable capacity
of the network, then the best approach would be a service class that
allowed joint reservations for layered streams with scalable QoS for each
layer.  A service like Predictive Delay++, which could offer a reasonable
assurance of service within delay bound D for the total stream, but could
guarantee no loss and delay <= D for the base layer, would be very useful.
This could be implemented either by packet tagging or by some form of
Session Groups.  I don't think that using shared explicit reservations
alone for the multiple layers would be as effective, since it doesn't
convey enough information to allow admission control and the scheduler to
prioritize the layers in terms of perceptual significance.

/*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
| Steven L. Blake              [email-masked] |
| Internetworking Technology          (919)254-2030 |
| IBM Networking Hardware Division                  |
| "You like the 'Net?  You ain't seen nothin' yet!" |
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=*/

---

From: Jon Crowcroft <[email-masked]>
Date: Thu, 04 Jul 1996 09:25:26 +0100

>correlation between the flow rates.  

for classical layered coding a la MPEG scalable schemes this is probably
true - but a lot of multi-layered coding nowadayas use different
scshemes altogether for the different levels (e.g. our robust audio
tool, a video tool 've seen that uses DCT at top level, but
feature/model schemes for lower level and a hybrid of texture maps 
and HVQ for an intermediate one...)

these may be less correlated than systems based on pulling out
different 'resolutions' of the same source image sequence

i guess we need some experience with real coders to see how much its
true (usual nasty problem about video source statistics is that they
don't seem amenable to general modeling:-)

a different, but also interesting problem with layered coding and
RSVP/mmulticast is the following:

if receivers adjust the rate of traffic by joining seperate groups for
seperate scale/quality parts of the stream (c.f. SIGCOMM 96 paper
upcoming), how do we ensure stability of the traffic flow since the
reservation at the traffic fan out points (rsvp merge points) will
fluctuate radically.....as different receivers change their mix at
different points in time.....??

cheers

jon