Deterministic packet marking for time-varying congestion price estimation

The addition of the two-bit Explicit Congestion Notification (ECN) field to the IP header provides routers with a mechanism for conveying link price information necessary for the successful operation of a number of congestion control schemes. Two recent proposals for probabilistic packet marking at the routers allow receivers to estimate path price from the fraction of marked packets. In this paper we introduce an alternative deterministic marking scheme for encoding path price. Each router quantizes the price of its outgoing link to a fixed number of bits. Every data packet sent along the path encodes a partial sum of the quantized link prices in its ECN field, allowing the receiver to estimate the path price. We evaluate the performance of our algorithm in terms of its error in representing prices, and compare it to probabilistic marking. We show that based on empirical Internet traffic characteristics, our algorithm performs better when estimating time-varying prices and static path price using small blocks of packets