Transcript Network Layer (3)

Network Layer (3)
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?
Binary search tree?
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?
– Binary search tree
– 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 you location on the circle. You know
the location of successor(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. He remembers the
successors of m locations if the node ID and
key are m bits.
• Consider a node with ID k. The i^{th} entry of
his finger table is the IP address of the
successor of k+2^i mod 2^m.
• 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 you are done because you know the IP
address of successor(RP).
• Else, let the next RP be the one in the RP’s
finger table that is closest predecessor of F.
Repeat.
Chord
• Chord needs m routing steps.
• The reason is every time, the distance from
the RP to the key is at least halved.
Internet Protocol (IP)
• Universal service in a heterogeneous world
– IP over everything
• Globally unique logical address for a host
IP Packet
IP Addressing
• A 32-bit number that uniquely identifies a
location
• Written using dotted decimal notation
IP Addressing
• IP address is assigned to each network
interface
• Routers connect two or more physical
networks
– Each interface has its own address
• Multi-homed host
– A host having multiple connections to Internet
– Multiple addresses identify the same host
– Does not forward packets between its interfaces
IP “Classful” Addressing Scheme
• Three unicast address classes: A, B, and C
• One multicast: class D
class
A
0 network
B
10
C
110
D
1110
1.0.0.0 to
127.255.255.255
host
network
128.0.0.0 to
191.255.255.255
host
network
multicast address
32 bits
host
192.0.0.0 to
223.255.255.255
224.0.0.0 to
239.255.255.255
Routing IP Packets
• Get the network address.
• If local, send the packet to the destination.
• If not local, send the packet to the next hop
based on the network address.
Classless Inter-Domain Routing
• Classful addressing scheme wasteful
– IP address space exhaustion
– A class B net allocated enough for 65K hosts
• Even if only 2K hosts in that network
• Solution: CIDR
– Eliminate class distinction
• No A,B,C
– Keep multicast class D
Classless Addressing
• Addresses allocated in contiguous blocks
– Number of addresses assigned always power of 2
• Network portion of address is of arbitrary
length
• Address format: a.b.c.d/x
– x is number of bits in network portion of address
network
part
11001000 00010111 00010000 00000000
200.23.16.0/23
host
part
IP Addressing
first 24 bits are network address
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.2.2
223.1.3.27
LAN
223.1.3.1
223.1.3.2
IP Addressing
223.1.1.2
223.1.1.1
Interconnected
system consisting
of six networks
223.1.1.4
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.7.1
223.1.8.1
223.1.8.0
223.1.2.6
223.1.2.1
223.1.3.27
223.1.2.2
223.1.3.1
223.1.3.2
CIDR
• A router keeps routing table with entries
– IP address, 32-bit mask, outgoing line
• When an IP packet arrives, the router checks
its routing table to find the longest match.
NAT – Network Address Translation
Virtual Circuit
• Destination information is large and the table
is large
– Consider 32 bit IP address. A full table will have 4G
entries.
• If an IP packet is 1250 byte long and the link speed is
10Gbps, how much time do you have for this lookup?
• (1. You don’t have to implement the full table. 2. You
can also use pipeline.)
Virtual Circuit
• Circuit means a path between the source and the
destination.
• Real circuit switching has a physical path set up between
the source and the destination, like telephone network
– When you dial, a request is sent to the network, network finds if
there are free links on the path and reserve that link for you.
• Virtual circuit is different – used in packet switching
networks.
– No real path set up, because it is packet switching (although link
bandwidth can be reserved).
– But still has the connection phase. The purpose is to let the
routers know how to route the packets of this virtual circuit.
Virtual Circuits
•
•
•
•
When setting up the virtual
circuit, a VC identifier is picked.
The router knows where to
forward a packet with a certain
VC identifier.
Each packet will carry the VC
identifier, which is much
shorter than the full destination
address, so allows more
efficient table lookup.
Resources can also be reserved.
QoS.
A practical problem in a
distributed environment –
different stations may pick the
same VC identifier.
•
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