GREEN + IDMaps: A practical soulution for ensuring fairness in a biased internet Page: 3 of 7
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
simplifying assumptions:
BW = MSS x c (1)
RTT x (1
where BW is the bandwidth/throughput of the connection,
MSS is the maximum segment size, RTT is its round-trip
time, and p is the packet-loss probability. c is a constant that de-
pends on the acknowledgment strategy that is used (i.e., delayed
or every packet) as well as on whether packets are assumed to
be lost periodically or at random.
In general, this model may not be applicable to non-SACK
TCP implementations in environments where there are sus-
tained multiple packet-losses for a flow within a single RTT
(causing repeated timeouts). This model may also not apply
to very short connections that never reach steady state, or to
connections whose window sizes are artificially limited by the
receiver's flow control window. We assume that all connections
satisfy the assumptions required for this model.
Now, let us consider a scenario where there are N active
flows at a router on a particular outgoing link of capacity L.
GREEN considers a flow to be active if it has had at least 1
packet go through the router within a certain window of time.
For now we assume that this parameter can be easily estimated,
and briefly explain this parameter in Section VI. The fair-share
throughput of each flow is LIN (assuming each source attempts
to transmit at least at that rate). Substituting L/N for BW in
(1), we derive the following expression for loss probability p:
Nx MSSxc (2
S Lx RTT /(2)
By using this value of p as the dropping probability for con-
gestion notification, GREEN "coerces" flows into sending at
their fair rate. Note that GREEN applies this marking proba-
bility to all arriving packets, where the value of p depends on
the flow. Because p depends on the number of flows and the
round-trip time of each flow, congestion notification is more ag-
gressive for large N and small RTT. And by including RTT
as an inverse parameter in the equation, GREEN eliminates the
bias of favoring TCP connections with smaller RTTs with re-
spect to throughput [10]. (Recall that TCP connections with
smaller RTT8 can increase their window size faster due to the
smaller RTT, and are more aggressive. These flows are able
to grab more than their fair share of bandwidth, which leads to
this bias.)
III. PLACEMENT OF GREEN ROUTERS
GREEN is mainly suited as an edge router, where organi-
zations can enforce fairness between flows leaving the orga-
nization through a bottleneck link. In a situation with widely
varying RTTs, it is desirable to correct TCP's bias and ensure
fairness between flows while maintaining high link utilization
and low packet-loss. In contrast, end-to-end schemes have beenproposed to correct for this bias by requiring TCP senders to in-
crease their congestion windows by a constant proportional to
RTT2 [6] [15]. However, these schemes rely on a window con-
stant that is hard to calculate and varies with the topology of the
network. In contrast, not only can GREEN accurately calculate
the drop probabilities irrespective of network topology, it also
does not require any end-to-end modifications.
IV. RTT ESTIMATION USING IDMAPS
In [5], we presented results for GREEN-Ideal, where the RTT
was assumed to be known at the router. Here, we relax this
constraint by making use of IDMaps. IDMaps [8] is a scalable
Internet-wide service that aims to provide Internet distance es-
timates. For example, the authors have suggested that IDMaps
can be used by hosts for nearest mirror selection. Such a ser-
vice is also well suited to GREEN, which can obtain RTT es-
timates for flows using IDMaps. We propose an architecture
where GREEN routers are part of the IDMaps framework, and
therefore, can perform fast lookups in a local IDMaps database.
A. IDMaps - Architecture
Jamin et al. [8] argue that providing highly accurate delay
estimates (within 5% for example) is not feasible. Instead they
aim to provide a scalable solution with existing technology to
provide delay estimates that are accurate to within a factor of
two. Jamin et al. propose the deployment of tracers in the In-
ternet. Tracers maintain raw distances amongst themselves and
address prefixes (AP). The use of APs, as opposed to actual IP
addresses, makes this solution feasible, trading off accuracy for
scalability. The delay between two IP addresses is estimated by
calculating the sum of the delays between the two tracers clos-
est to the two address prefixes, and the tracer-AP delays. The
IDMaps Project [9] is already running an experimental service
and can be accessed at http://www.closestserver.com/.
B. GREEN using IDMaps
We propose a solution in which GREEN routers also perform
the duties of tracers and exchange distance information with
other tracers. We do not expect this to add much overhead to ex-
isting traffic from routing updates. Furthermore, since GREEN
is an edge router, the delays from sources within the organi-
zation to the GREEN router will be fairly low. GREEN can
perform fast lookups in the local IDMaps database to obtain
RTT estimates for a flow based on the destination IP addresses
(since the source IP address is assumed to be within the orga-
nization). GREEN calculates the drop probability based on the
estimated RTT. The accuracy of IDMaps estimates is sensitive
to the number of tracers and their placement on the Internet.
Jamin et al. have evaluated several graph-theoretic approaches
as well as simple heuristics. In general, the accuracy of esti-
mates increases when tracers are closer to the APs. As men-
tioned earlier, GREEN routers will be co-located with the APs
of that organization, and hence, will result in more accurate es-
timates.
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Kapadia, Apu Chandrasen; Thulasidasan, Sunil & Feng, Wu-Chun. GREEN + IDMaps: A practical soulution for ensuring fairness in a biased internet, article, January 1, 2002; United States. (https://digital.library.unt.edu/ark:/67531/metadc925669/m1/3/: accessed April 19, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.