Back to index
A Framing Strategy for Congestion Management
S.J. Golestani, Bellcore
One-line summary: Admission based congestion control on
multiple streams with varying real-time constraints. Group
packets with similar delay requirements into "time frames", multiplex
the frames onto each link, and at each switch/router, minimize
the "phase difference" (delay between extracting packet from arriving
frame and placing it in next departing frame of the same class).
- Idea: exploit loss tolerance of different classes of RT traffic,
"striking balance between statistical mux'ing gain and packet
- Connection parameters:
- "Frame size" Tg (division of time axis); we call it a
"type g frame". Larger Tg implies shorter frame. Various
Ti's correspond to different
families of services, and need not be multiples of each
other or anything like that.
- Steady state transmission rate Rk
- (r,Tg) smoothness with respect to link L: aggregated
length of pkts received during each arriving frame of
type g over L is no more than r x Tg bits. (For
fixed size pkts of size S, says number of received packets
is at most r x Tg x 1/S.) Note that
this property is dependent on choice of time origin, but
that turns out not to matter.
- Admission rule: any packet that violates (r,Tg)
smoothness of the connection is not admitted
- So, we use this rule to guarantee dropping of packets that
would cause bursts to build up.
- Stop-and-go queueing: goal is to preserve the smoothness property
(above) which we currently guarantee only on entry to the
- Phase mismatch at a switch: delay between the end of the
arrival of a type g
frame, and the beginning of the departure of the
next type g frame on the outgoing link for this
connection. (By definition, always less than Tg.)
- The eligible set of packets to go out on next
outgoing type g frame is at most those packets that
arrived on the last type g frame. Packets from the next
incoming type g frame won't be eligible until the whole
- An eligible type g' packet has priority over an eligible
type g packet frame if g'>g. (I.e. packets in shorter
non-preemptive priority over packets in longer frames)
- Loop: Select and transmit eligible packets until none left.
- Some properties of this algorithm:
- Stop-and-go queueing prevents packet clustering.
- To avoid packet loss for type g, allocate a buffer of size
Tg x C(g,l) x B, where B<3 is a
bounding constant (proof in appendix) and C(g,l) is the
allocated to all connections of type g traversing link l
into the switch.
- Due to minimizing the phase delay, end-to-end delay of a
given packet is deterministic, modulo its position in the
arriving/outgoing frame (which is also bounded). The
amount of variation is dependent on the frame size, so put
more delay-tolerant traffic in larger frames.
- Choice of frame size: trade off end-to-end delay
vs. granularity of xmit capacity.
I.e. as you make the granularity of xmit allocation finer
and finer, the queueing delay goes up and vice versa.
- Buffering: trade off buffer requirements vs. granularity
of xmit capacity.
- Can combine framing with other traffic-mgmt strategies for
delay-tolerant traffic (put into type 0 frames, don't need to
service according to framing strategy).
- Related paper describes how to balance stat. mux'ing of
time-framing with packet loss induced by admission control.
Nice statistical multiplexing argument with some mathematically
developed bounds on queueing delay and buffering---provided you can do
strict admission control and that your traffic fits well into these
constant-frame-size, constant-bit-rate classes. (Seems like you could
dynamically change the class of a connection if needed, but this is a
whole new layer of scheduling and is not even mentioned in the paper.)
- Admission based, so what if senders try to be malicious -- does
algorithm make sure badness doesn't propagate past first switch?
Even so, doesn't that make life miserable for other users of the
- Similarly: compatibility/interoperability w/existing schemes?
(Author talks about coexistence with them, but that's a
much weaker notion)
- Bursty traffic loses. Statistical mux'ing is only for non-RT
traffic (though this may be an acceptable soln)
Back to index