Transcript Week12_1 - FSU Computer Science

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 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.
– 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 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 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.
Routers
These high-end, carrier-grade 7600 models process up
to 30 million packets per second (pps).
Lookup
• The table is learnt manually or through
routing protocols, such as BGP or OSPF.
TCAM
• CAM: Content Addressable Memory.
• CAM reads the data, and returns a list of
addresses where the data is stored, if it finds
any.
• CAM searches the entire memory in one
operation.
• TCAM: three states, 0, 1, or don’t care
TCAM
•
A Priority TCAM IP-Routing Lookup Scheme, Po-Chou Lin and Chung-Ju Chang, Senior Member, IEEE
Switches
• After figuring out the next hop, need to send
the packet to the next hop.
• The switches works in time slots. A large
packet is divided into fixed length cells, cells
are reassembled at the output.
N by N crossbar
• Usually, the switch is a crossbar.
• An input can send at most one cell per time
slot, and an output can receive at most one
cell per time slot.
• Consider unicast packets.
Output contention
• Consider an N by N switch. What if two input
ports both have a cell to send to the same
output port at the same time?
Buffers
• So, buffers have to be added to the switch.
• You may have buffer at the input port, or at
the output port.
• Which one is better?
Input Buffer Switch
• Modern switches are input-buffered.
• Cells arrive at the input port, if cannot be sent
out, will be temporarily stored at the input
buffer.
• How would you organize the buffer? FIFO?
Head-of-Line Blocking
• If simply using FIFO, you will have Head-of-line
blocking.
• Consider the case when at input port 0, you
have 23334. If some other input port gets
grant to send to output 2, while no one is
sending to output port 3, input port 0 is forced
to go idle – no good.
• Throughput bounded 58%.
• Any suggestions?
VOQ
• Organize the cells into Virtual Output Queues
(VOQ).
• At each input port, you have N queues, one
for each output.
• Coming back to the example, at input port 0,
you have 3 non-empty queues:
–2
– 333
–4
Problem?
• Now, every input port can potentially have
cells to every output ports – How to schedule
the transmission of cells?
Bipartite Matching
• Draw a bipartite graph, let the left side vertices
be the inputs, let the output side vertices be the
outputs.
• A left side vertex is adjacent to a right side vertex
if this input port has a cell to send to the output
port.
• Now, recall the constraint that an input port can
send at most one cell, and the output port can
receive at most one cell.
• Therefore, any schedule is a matching.
Maximum Matching
• Maximum Matching in bipartite graphs can be
found in O(n2) time.
• But the schedule must be computed really
really fast, in the order of 10ns.
Maximal Matching
• How about a really simple algorithm – just
pick edges in any arbitrary order until no
edges can be picked?
• How bad can this be, compared to the
maximum matching?
Maximal Matching
• So, can we just run a maximal matching
algorithm?
The algorithm being used
• The materials in following slides are from “The
iSLIP Scheduling Algorithm for Input-Queued
Switches” by Nick McKeown published in
IEEE/ACM Transactions on Networking.
PIM
PIM
iSLIP Algorithm
The iSLIP Algorithm
• Achieves 100% throughput for some simple
type of traffic.