Abstract.

A network router that marks packets to signal congestion should do so fairly. We propose a definition of fairness, using ideas from effective bandwidth theory and economics. Our definition measures both the level of congestion at a router and the contribution of each flow to that congestion, taking into account the flow's burstiness. We then use large deviations to analyse marking algorithms such as RED, point out how they can be unfair, and suggest how they can be made fairer.