A Framing Strategy for Congestion Management

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).

Overview/Main Points

• Idea: exploit loss tolerance of different classes of RT traffic, "striking balance between statistical mux'ing gain and packet loss probability"
• 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 (i.e. dropped).
  • 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 network.
  • 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 frame arrives.
  • An eligible type g' packet has priority over an eligible type g packet frame if g'>g. (I.e. packets in shorter frames have 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 aggregate capacity 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.
• Tradeoffs:
  • 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.

Relevance

Flaws

• 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 first switch?
• 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)