Academic
Publications
Estimation of Congestion Price Using Probabilistic Packet Marking

Estimation of Congestion Price Using Probabilistic Packet Marking,10.1109/INFCOM.2003.1209228,Micah Adler,Jin-yi Cai,Jonathan K. Shapiro,Donald F. Tow

Estimation of Congestion Price Using Probabilistic Packet Marking   (Citations: 22)
BibTex | RIS | RefWorks Download
One key component of recent pricing-based conges- tion control schemes is an algorithm for probabilistically setting the Explicit Congestion Notification bit at routers so that a receiver can estimate the sum of link congestion prices along a path. We consider two such algorithms—a well-known algorithm called Random Exponential Marking (REM) and a novel algo- rithm called Random Additive Marking (RAM). We showthat if link prices are unbounded, a class of REM-like algorithms are the only ones possible. Unfortunately, REM computes a biased estimate of total price and requires setting a parameter for which no uniformly good choice exists in a network setting. However, we show that if prices can be bounded and therefore normalized, then there is an alternate class of feasible algorithms, of which RAM is representative and furthermore, only the REM-like and RAM-like classes are possible. For properly normalized link prices, RAM returns an optimal price estimate (in terms of mean squared error), outperforming REM even if the REM parameter is chosen optimally. RAM does not require setting a parameter like REM, but does require a router to knowits position along the path taken by a packet. We present an implementation of RAM for the Internet that exploits the existing semantics of the time-to-live field in IP to provide the necessary path position information.
Conference: IEEE INFOCOM - INFOCOM , vol. 3, pp. 2068-2078 vol.3, 2003
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Examples include the Random Exponential Marking (REM) [6], Random Additive Marking (RAM) [7], Deterministic Quantisation Marking (DQM) [8], Variable-structure Congestioncontrol Protocol (VCP) [9] and eXplicit Congestion Protocol (XCP) [3]...

    Mussie Woldeselassieet al. Forecasting Full-Path Network Congestion Using One Bit Signalling

    • ...ADPM conveys signals with a lower Mean Square Error (MSE) than competitors such as REM [10] and RAM [11]...
    • ...The “side information” contained in the IP header was first used for setting the ECN bits in [11], which considers the timeto-live (TTL) field...

    Ihsan Ayyub Qaziet al. Congestion Control using Efficient Explicit Feedback

    • ...Before doing anything else, A and B agree on a transformation function f. To send x ∈ [0,1], to B, the transmitter A generates random bits, which are i.i.d...
    • ...We might as well assume f is monotonically increasing; otherwise, work with 1 − f. If f is continuous and monotonically increasing then f homeomorphically maps [0,1] to [f(0), f(1)] since [0,1] is compact...
    • ...We might as well assume f is monotonically increasing; otherwise, work with 1 − f. If f is continuous and monotonically increasing then f homeomorphically maps [0,1] to [f(0), f(1)] since [0,1] is compact...
    • ...over smooth functions f that increase from 0 to 1 on [0,1]...
    • ...In this section, we evaluate the limit of this for the optimal f. A corresponding theorem for general f was stated in [2], and proved in [1]...
    • ...on [0,1], and in particular bounded on this interval...
    • ...Proof We may write y = 1 − cos πθ(x) 2 , where θ increases from 0 to 1 on [0,1]...
    • ...Then there is a function θ, increasing from 0 to 1 on [0,1], for which y = 1 − cos(πθ(�(x))) 2 ...
    • ...In the problem we have just addressed, there is one real number x ∈ [0,1] that A wishes to transmit to B. A natural 2-dimensional version of it is this: We have a point x on the convex hull � of {(1,0,0),(0,1,0),(0,0,1)}...

    Eric Bachet al. A Novel Information Transmission Problem and Its Optimal Solution

    • ...It has recently been proposed [6] that the process of setting these bits take into account “side information” contained in the IP header...
    • ...Each router guesses its hop number from the time to live (TTL) value [6]...
    • ...The other schemes REM [5], RAM [6], and [7] estimate the sum of prices...
    • ...For all schemes, the actual price was mapped to a “price”, p, in [0,1]; for [5] this is provided by the exponential mapping p = exp( price), and for [6] and [7], it is the sum of prices scaled by 1/10...
    • ...The results for REM [5] and RAM [6] are the closed form expression, 1/(6k), which is the average of p(1 p)/k for p uniform in [0,1]...

    Lachlan L. H. Andrewet al. Adaptive Deterministic Packet Marking

    • ...Two probabilistic marking proposals have emerged to carry out the latter task [2], [10]...
    • ...We now formalize the problem as in [10], slightly deviating occasionally...
    • ...According to the authors of [10], a marking algorithm must obey some design constraints...
    • ...Adler et al. [10] make the claim that “there is no deterministic marking algorithm under these conditions”...
    • ...forming the estimate b zn = − logÁ(1 − X). This estimate is biased, but does converge to zn almost everywhere, almost surely [10]...
    • ...The performance of REM is highly dependent on the value of φ, as demonstrated by Adler et al. [10]...
    • ...Random Additive Marking (RAM), proposed by Adler et al. [10], is an alternative probabilistic marking scheme . It requires that each link’s price fall in the range bounded by 0 and 1, and that each router be aware of its position i within the path...
    • ...Routers may estimate their position using a method based on the TTL field in the IP header [10]...
    • ...We performed an examination of the error probability of the deterministic estimation to enable comparison with RAM [10] probabilistic price estimation...
    • ...The performance of RAM is shown for comparison (with results derived from expressions in [10])...

    Richard W. Thommeset al. Deterministic packet marking for time-varying congestion price estimat...

Sort by: