Buffer Overflow Management in QoS Switches (Part 1)

This will be the first of a series of  seminars over the coming weeks based upon papers that I have started reading involving packet-level switching policies in a network with differentiated quality of service.

A typical problem involves a single network switch that receives incoming packets and can deliver one outgoing packet at given increments.  The system is limited either by a requirement that there is a fixed-sized buffer for holding packets that have not yet been delivered or by a requirement that individual packets must be forwarded within a certain time frame or else be dropped.  In either case, an algorithm may be forced to drop some of the packets.  We use competitive analysis to measure the overall value of those packets that are successfully delivered by an online algorithm versus the maximum value that could have been achieved on an instance by an omniscient offline algorithm.