Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Congestion Pricing
Explicit Congestion Notification
Mean Square Error
Positional Information
Probabilistic Packet Marking
Random Exponential Marking
Time To Live
Related Publications
(8)
REM: Active Queue Management
Real and complex analysis
Random early detection gateways for congestion avoidance
The Probabilistic Method
Optimization flo...
Subscribe
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,Jinyi Cai,Jonathan K. Shapiro,Donald F. Tow
Edit
Estimation of Congestion Price Using Probabilistic Packet Marking
(
Citations: 22
)
BibTex

RIS

RefWorks
Download
Micah Adler
,
Jinyi Cai
,
Jonathan K. Shapiro
,
Donald F. Towsley
One key component of recent pricingbased 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 wellknown 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 REMlike 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 REMlike and RAMlike 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 timetolive field in IP to provide the necessary path position information.
Conference:
IEEE INFOCOM  INFOCOM
, vol. 3, pp. 20682078 vol.3, 2003
DOI:
10.1109/INFCOM.2003.1209228
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.
(
eprints.kfupm.edu.sa
)
(
www.informatik.unitrier.de
)
(
www.ieeeinfocom.org
)
(
www.comsoc.org
)
(
reference.kfupm.edu.sa
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(21)
...Examples include the Random Exponential Marking (REM) [6], Random Additive Marking (RAM) [
7
], Deterministic Quantisation Marking (DQM) [8], Variablestructure Congestioncontrol Protocol (VCP) [9] and eXplicit Congestion Protocol (XCP) [3]...
Mussie Woldeselassie
,
et al.
Forecasting FullPath 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 timetolive (TTL) field...
Ihsan Ayyub Qazi
,
et 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 2dimensional 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 Bach
,
et 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. Andrew
,
et 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. Thommes
,
et al.
Deterministic packet marking for timevarying congestion price estimat...
References
(14)
Resource pricing and the evolution of congestion control
(
Citations: 448
)
Richard J. Gibbens
,
Frank P. Kelly
Journal:
Automatica
, vol. 35, no. 12, pp. 19691985, 1999
Optimization Flow Control, II: Implementation
(
Citations: 27
)
Sanjeewa Athuraliya
,
Steven H. Low
Published in 2000.
Requirements for internet hostscommunication layers
(
Citations: 508
)
R. Braden
Published in 1989.
Measurement and Classification of OutofSequence Packets in a Tier1 IP Backbone
(
Citations: 86
)
Sharad Jaiswal
,
Gianluca Iannaccone
,
Christophe Diot
,
James F. Kurose
,
Donald F. Towsley
Conference:
IEEE INFOCOM  INFOCOM
, vol. 2, pp. 11991209 vol.2, 2003
The Addition of Explicit Congestion Notification (ECN) to IP
(
Citations: 518
)
K. K. Ramakrishnan
,
Sally Floyd
,
D. Black
Published in 2001.
Sort by:
Citations
(22)
Forecasting FullPath Network Congestion Using One Bit Signalling
Mussie Woldeselassie
,
Richard G. Clegg
,
Miguel Rio
Published in 2010.
Congestion Control using Efficient Explicit Feedback
(
Citations: 10
)
Ihsan Ayyub Qazi
,
Taieb Znati
,
Lachlan L. H. Andrew
Conference:
IEEE INFOCOM  INFOCOM
, pp. 1018, 2009
A Novel Information Transmission Problem and Its Optimal Solution
Eric Bach
,
Jinyi Cai
Conference:
Fundamentals of Computation Theory  FCT
, pp. 6475, 2007
Adaptive Deterministic Packet Marking
(
Citations: 9
)
Lachlan L. H. Andrew
,
Stephen V. Hanly
,
Sammy Chan
,
Tony Cui
Journal:
IEEE Communications Letters  IEEE Commun. Lett.
, vol. 10, no. 11, pp. 790792, 2006
Deterministic packet marking for timevarying congestion price estimation
(
Citations: 4
)
Richard W. Thommes
,
Mark Coates
Journal:
IEEE/ACM Transactions on Networking  TON
, vol. 14, no. 3, pp. 592602, 2006