Transcript Bottleneck Bandwidth Estimation

Bottleneck Bandwidth
Estimation
Instructor: Dr. Aggarwal
Present by: Jason Wei
Outline
•
•
•
•
Introduction of bandwidth estimation
Related Work
Our algorithm and experiment
Summary
Introduction
•
•
“A high-end user's connection speed grows
by 50% per year” [1]
Monitoring the performance of the
network, especially the network bandwidth,
still is a challenging research topic.
Introduction (Cont’d)
What is network bandwidth?
The bandwidth of a network, also called
throughput, is given by the number of bits that
can be transmitted over the network in a certain
period of time.
For example, the bandwidth of a STS-1 network
is 51.840 Mbps, which means that the transfer
ability of the network is 51.840 million bits per
second.
Introduction (Cont’d)
•
Bottleneck link bandwidth
If there is no other traffic in the path, bottleneck
link bandwidth is the maximum throughput that
the path can provide from source to destination.
It is limited by the bottleneck link’s underlying
capacity.
•
Available bandwidth
Available bandwidth is the maximum rate that
the path can provide to a flow without reducing
the rate of the cross traffic.
Introduction (Cont’d)
Why measure bandwidth?
• Network users benefit from knowing the
bandwidth.
• Measuring bandwidth is the key to congestion
control and QoS (Qualities of Service).
• Dynamical server selection
• It is important to know bandwidth for mobile
computing.
Relation work
Bottleneck link bandwidth measurement
can be divided into two categories:
• Single-packet algorithms
• packet-pair algorithms
Relation work (Cont’d)
Single-packet algorithm
•
•
•
Use time-to-live (TTL) field in IP packet. TTL is
used to monitor and remove the packets.
Once TTL is decremented to zero, the packet will
be discarded and the router will send back an
ICMP time exceeded packet to the original sender
By sending out a series of probe packets with
different values of TTL. Bandwidth and latency of
each link can be calculated by using statistics to
analyze the time when error packets are received.
Relation work (Cont’d)
Single-packet algorithm
RTT= q1 + (lat1 + size/bwn1) + q2 + forward
+ q3 + (lat2+error_size/bwn2) + q4 [2]
Relation work (Cont’d)
Packet-Pair algorithm [3]
Bandwidth = Size/Q b
Relation work (Cont’d)
Cartouche algorithm[4]
• Harfoush, Bestavros and Byers presented
Cartouche algorithm.
• Cartouche probe [apm {pq}r-1pm] can measure
the bottleneck bandwidth of targeted path
segments (i,j).
s(p)>s(m)=s(q),D(a)=i, D(p)=D(q)=j, D(m)=A
Sender
R1
Ri-1
Ri
Rj
Rj+1
Rn
Receiver
Relation work (Cont’d)
Before the target path segment:
Relation work (Cont’d)
After the target path segment:
Our algorithm
The problems of Cartouche algorithm
• Need to install software on receiver side.
• If the result will be inaccurate when the
cross traffic becomes high.
Sender
Ra
Ra+1
Ri
Rj
Rb
Rb+1
Receiver
Our algorithm (Cont’d)
Two steps:
• First, use single-packet algorithm to check the
network structure, get position of the bottleneck
link Li.
Li
Sender
Ra
Ra+1
Ri
Ri+1
Rb
Rb+1
Receiver
Our algorithm (Cont’d)
Second step:
Send [(Hdmrd)s] probes to measure the
bandwidth of bottleneck link.
Size(H)>>Size(d)=Size(m),
Dest(H)=Li, Dest(d)= Li+1 Dest(m)=Receiver
d m … m d H … d m … m d H
Our algorithm (Cont’d)
Before probes reach bottleneck link:
Sender
d m …m d H
•
•
Ra
Ra+1
Ri
d m …m d H
Size(H)>>Size(d)=Size(m)
If there is cross traffic between the sender and
Ri , because of s(H )>>s(d), the interval between
d still should be same.
Our algorithm (Cont’d)
When the probes reach bottleneck link:
d
m … m
d
d m … m d H
m … m
Ri
Ri+1
Receiver
H
ACK
d
d
ACK
•
•
Dest(H)=Li, Dest(d)= Li+1 Dest(m)=Receiver
Only the ICMP of packet d will be return from
Router i+1
Our algorithm (Cont’d)
After the probes reach bottleneck link, ICMP
packets come back
Sender
Ra
d
d
ICMP
•
•
Ra+1
Ri
d
d
ICMP
If there is no cross traffic, the interval of d can
be keep.
If the interval of d is large enough, the time they
pass the link with cross traffic should be same.
Our algorithm (Cont’d)
•
•
•
Send several times of (Hdmrd)
Record the interval of d and analyze them
to get the interval Idd. (The minimum value
of them may be the value we need)
Bandwidth=Size(d)*(r+1)/ Idd
The improvement of our
algorithm
Compared with single-packet algorithm:
• Both use ACK, so we do not need to install
software on receiver side.
• We just use single-packet algorithm to
check the network structure (the position
of the network bottleneck link)
• Our algorithm is accurate than singlepacket algorithm in the case that cross
traffic exists.
The improvement of our
algorithm (Cont’d)
Compared with Cartouche algorithm:
•
We use ACK. So we do not need to install
software on receiver side.
Verify our algorithm
• Current work: Make my own network simulator
to verify our algorithm. (partly finished)
Verify our algorithm (Cont’d)
Next Step:
• Use Network Simulator [5]to demo the
algorithm.
• If possible, set up a real network with
routers, computers, and cross traffic,
implement the algorithm.
Reference
1. Nielsen's Law of Internet Bandwidth
http://www.useit.com/alertbox/980405.html
2. Using pathchar to Estimate Internet Link Characteristics
Allen B. Downey ACM SIGCOMM '99 Pages: 241-250
3. Congestion Avoidance and Control
Van Jacobson, In Proceedings of ACM SIGCOMM‘98, Pages: 314—329
4. Measuring Bottleneck Bandwidth of Targeted Path Segments
Khaled Harfoush, Azer Bestavros, John Byers Boston University, 2001
5. Network Simulator (NS), version 2
http://www.isi.edu/nsnam/ns/
Summary
•
•
•
Introduce the basic network bandwidth
algorithms.(Single packet, packet pair)
Cartouche algorithm and problems
Our algorithm