Transcript Week11_2

Node Lookup in P2P Networks
Node lookup in p2p networks
• Section 5.2.11 in the textbook.
• In a p2p network, each node may provide
some kind of service for other nodes and also
will ask other node for service.
• The problem is to locate a node who provides
the service I need.
• In our project there is a central server who
assigns nodes to others.
Node lookup in p2p networks
• P2P networks may have a very large number of
nodes, such that a single central server may not
be able to handle.
• Besides, there are legal issues.
• So, how to design lookup mechanism, such that I
can find the node providing the service I need?
• For simplicity, let’s use the same model as in our
project – Each node may have some files, and the
job is to find a node with the file I need.
Node lookup in p2p networks
• Any suggestions?
• Ask the nodes in the network one-by-one?
• Flood the network?
Node lookup in p2p networks
• Two costs you have to consider.
– The lookup time
– The number of messages sent
• Assume that there is only one node with the
file I need, what is the cost for
– Linear search?
– Flood?
– Are they any good?
The key idea
• There is really not so much you can do if the
network does not have a structure.
• Introduce structure to the network.
• Distributed Hash Table (DHT).
Chord
• Each node has a unique ID
– By hashing its IP address by SHA-1 to get a 160-bit
ID.
• Each file also has a unique ID, called key.
– By hashing the file name by SHA-1 to get a 160-bit
ID.
Chord
• Successor of a key x or ID x.
– Arrange the node as a circle. Start at x and travel
clockwise. The first (real) node you visit is the
successor of F.
Chord
• successor(F) is the node in charge of telling
other people where to get F.
• If a node has file F, he tells successor(F) that
he has F.
• So, if you can find successor(F), meaning that
the IP address of it, you are done.
Chord
• How to find successor(F)?
• Any suggestions?
Chord
• You know your location on the circle. You
know the location of F on the circle.
• If every node keeps the IP address of its
neighbor on the circle, need to do a linear
search.
Chord
• But you control what nodes should remember.
• What do you want the nodes to remember,
such that your searching time is small and
your number of message is small?
Chord
• What Chord does is this.
– remembering the successors of m locations if the
node ID and key are m bits.
• Consider a node with ID k. The ith entry of his
finger table is the IP address of the successor
of k+2i mod 2m.
• Given this, how do you design the routing
algorithm?
Chord
• Start with k as the routing point (RP).
• If RP < F < successor(RP), successor(RP) =
successor(F) and we are done.
• Else, let the next RP be the one in the RP’s
finger table that is the closest predecessor of
F. Repeat.
Chord
• Chord needs O(m) routing steps.
• The reason is every time, roughly speaking,
the distance from the RP to the key is at least
halved.
– WLOG, suppose the current RP is 0, and F is
between 2i and 2i+1. So if there is at least one valid
node between 2i and F, we will go to the first such
point, distance is halved.
Connection-orientated Service
Connection in data networks
• Another type of network, such as the
telephone network, was developed based on
the connection idea.
– Before communication, a connection must be set
up, which consists of physical circuits.
– After the communication is over, tear down the
connection.
Advantage
• The resources in the connection is reserved, so
interference-free from other connections. Can
guarantee certain Quality of Service
requirements.
• The connection (the physical circuits in the
routers) has been set up, the processing of data
packets is minimal. No need to check the header
for full destination address. The packet does not
even have to carry the address information.
Disadvantage
• People may reserve more resources than they
need. Such resources, even when idle, cannot
be used by others. A waste.
• The set up of the connection requires time.
For a large network, the delay can be 100ms.
Okay for telephone networks, not oaky for
some data services which just need to send a
single packet.
Virtual Circuit
• Implementing circuit in a datagram network?
– Datagram network forwards packets, there is no
physical circuits that can be set up for connections.
– Still, if we set up a virtual circuit, the routers will
know how to route the packets of this virtual circuit.
To reduce the complexity of routers.
– Before transmission, a virtual circuit is set up. Then, a
packet will carry the ID of the virtual circuit. The
virtual circuit ID is much smaller, and thus much easier
to deal with, than the full destination address. It is
also much smaller than the full destination address,
can save some overhead.
Virtual Circuit
• When setting up the
virtual circuit, a VC ID
is picked. The router
knows where to
forward a packet with
a certain VC ID.
• A practical problem in
a distributed
environment –
different stations may
pick the same VC ID.
– Labels can be
swapped without
causing confusion.
H2
B
D
A
F
C
H1
A’s Table
In
Out
H1, 1 C, 1
H2, 1 C, 2
E
C’s Table
In
Out
A, 1 E, 1
A, 2 D, 1
H3
Exercise
• Find the
shortest
path from
A to all
other
nodes in
the
network.
Exercise
• Suppose a network runs the distance vector
algorithm. Suppose node A is adjacent to B, C,
and D, with link distance of 5, 2, and 9,
respectively. A receives advertisements from B, C,
and D about node E. From B: 5. From C: 10. From
D: 3. So to reach E, A will pick which node as the
next hop and the distance is
a.
b.
c.
d.
B, 12
C, 10
D, 12
None of the above.
Exercise
• A router has the following (CIDR) entries in its routing table:
Address/mask: Next hop
160.36.224.0/19: Interface 0
160.36.240.0/20: Interface 1
160.36.232.0/21: Router 1
Default:
Router 2
For a packet with destination address of 160.36.243.15, the
router will forward it to
a.
b.
c.
d.
Interface 0
Interface 1
Router 1
Router 2
Exercise
• A router just received the following new IP
addresses: 57.6.40.0/21, 57.6.60.0/22,
57.6.36.0/22, all with the same outgoing line.
They
a.
b.
c.
d.
can be aggregated to 57.6.32.0/19.
can be aggregated to 57.6.48.0/19
cannot be aggregated.
None of the above.
Exercise
• Which of the following statements is true?
a. BGP is for routing between the ASes, and suffers
from the count-to-infinity problem.
b. OSPF is for routing within ASes, and is a distance
vector algorithm.
c. ARP is used when a node wants to know the IP
address of itself.
d. None of the above,
Exercise
• Suppose an input buffered switch has 4
inputs/outputs. If the buffer states at input 0 to 3
are (0,2,0,0), (1,2,3,0),(0,0,2,2), and (0,0,1,0),
respectively, what is the maximum number of
packets that can be sent in this time slot?
a.
b.
c.
d.
2.
3.
4.
None of the above.
Exercise
4
• Line FG goes down.
6
• What message will node F have
A
in its routing table when DV is
used? What will he do in the
first step?
6
• What message will node F have
in its routing table when Path
Vector is used? What will he do
E
in the first step?
1
C
B
D
1
2
6
G
1
F
6
1
H
6
2
6
I
J
6
Exercise
4
•
•
•
Line FG goes down.
What message will node F have
in its routing table when DV is
used? What will he do in the first
step?
– B: 5
– E: 4
– I: 5
What message will node F have
in its routing table when Path
Vector is used? What will he do
in the first step?
– B: 5, BCD
– E: 4, EFGCD
– I: 5, IFGCD
6
1
C
B
D
1
2
A
6
G
1
F
6
6
1
H
6
2
E
6
I
J
6