Transcript nov30

CS 101 – Nov. 30
Communication, continued
• TCP/IP review
• Dijkstra’s shortest path algorithm
• Download speeds
Snooping
The “dark side” of TCP/IP
• Web site can track you by IP address
– Localized marketing
– Privacy concerns
• Anonymous IP servers
– Ex. “Anonymouse”
Dijkstra’s algorithm
• How do you find the shortest path in a network?
• General case solved by Edsger Dijkstra, 1959
4
7
9
6
7
3
8
4
2
1
3
6
• Let’s say we want to go from “A” to “Z”.
• The idea is to label each vertex with a
number – its best known distance from A.
As we work, we may find a cheaper
distance, until we “mark” or finalize the
vertex.
1. Label A with 0, and mark A.
2. Label A’s neighbors with their distances
from A.
3. Find the lowest unmarked vertex and mark
it. Let’s call this vertex “B”.
4. Recalculate distances for B’s neighbors
via B. Some of these neighbors may now
have a shorter known distance.
5. Repeat steps 3 and 4 until you mark Z.
A
4
7
2
B
3
C
4
Z
First, we label A with 0. Mark A as final.
The neighbors of A are B and C. Label B = 4
and C = 7.
Now, the unmarked vertices are B=4 and C=7.
The lowest of these is B.
Mark B, and recalculate B’s neighbors via B.
The neighbors of B are C and Z.
– If we go to C via B, the total distance
is 4+2 = 6. This is better than the old
distance of 7. So re-label C = 6.
– If we go to Z via B, the total distance is
4 + 3 = 7.
A
4
7
2
B
3
C
4
Z
Now, the unmarked vertices are C=6 and Z=7.
The lowest of these is C.
Mark C, and recalculate C’s neighbors via B.
The only unmarked neighbor of C is Z.
– If we go to Z via C, the total distance is
6+4 = 10. This is worse than the
current distance to Z, so Z’s label is
unchanged.
The only unmarked vertex now is Z, so we
mark it and we are done. Its label is the
shortest distance from A.
A
4
7
2
B
3
C
4
Z
A
Postscript. I want to clarify something…
The idea is to label each vertex with a number
– its best known distance from A. As we
work, we may find a cheaper distance, until
we “mark” or finalize the vertex.
When you are mark a vertex and look to
recalculate distances to its neighbors:
– We don’t need to recalculate distance
for a vertex if marked. So, only
consider unmarked neighbors.
– We only update a vertex’s distance if it
is an improvement: if it’s shorter than
what we previously had.
4
7
2
B
3
C
4
Z
Shortest Paths
• Dijkstra’s algorithm:
What is the shortest distance between 2 points in a
network/graph ?
• A related problem:
What is the shortest distance for me to visit all the points in
the graph and return home?
This is called the traveling salesman problem. Open
question in CS: why is this problem so hard?
B
8
A
9
12
6
2
C
5
4
6
3
E
4
D
Measuring speed
• Overhead = prepare & assemble message
• Flight time = first bit to arrive at destination
• Bandwidth = max rate to propagate data
(cruising speed)
• Total time =
overhead + flight time + (msg size)/bandwidth
How much longer?
File Size
Progress “time left”
rate
#1
815 KB
65.1%
3:08
1.5 KB/s
#2
5.9 MB
64.8%
24:03
1.5 KB/s
Examples