Transcript 15-829A/18-849B/95-811A/19-729A Internet

15-829A/18-849B/95-811A/19-729A
Internet-Scale Sensor Systems:
Design and Policy
Review
Systems/Techniques to Remember








DNS
Chord
CAN
INS
GHT
IP2Geo
IDMaps
GNP
5/1/2003
Review Lecture
2
The Lookup Problem
N1
Key=“title”
Value=MP3 data…
Publisher
Internet
N4


N2
N5
N3
?
Client
Lookup(“title”)
N6
Problem in DNS, P2P, routing, etc.
Sensor networks: how to find sensor readings?
5/1/2003
Review Lecture
3
DNS: Query Routing
root & edu
DNS server
www.cs.cmu.edu
Client
ns1.cmu.edu
DNS server
Local
DNS server
ns1.cs.cmu.edu
DNS
server
5/1/2003
Review Lecture
4
DNS: Subsequent Query Routing
root & edu
DNS server
ftp.cs.cmu.edu
Client
cmu.edu
DNS server
Local
DNS server
cs.cmu.edu
DNS
server
5/1/2003
Review Lecture
5
Chord: Query Routing






Succ. Table
Properties
i
i id+2
0 1
1 2
2 4
Routing table size O(log(N)),
where N is the total number
of nodes
Guarantees that a file is
found in O(log(N)) steps
Upon receiving a query for item
id, a node
Check whether stores the item
locally
If not, forwards the query to the
largest node in its successor
table that does not exceed id
Items
7
succ
1
2
0
Succ. Table
0
1
7
i
i id+2
0 2
1 3
2 5
query(7)
6
Items
succ 1
2
6
6
2
Succ. Table
i id+2i succ
0 7
0
1 0
0
2 2
2
5/1/2003
Succ. Table
5
3
4
Review Lecture
i id+2i succ
0 3
6
1 4
6
2 6
6
6
CAN: Query Routing

Properties
7

Routing table size O(d)
6
 Guarantees that a file is found in at
most d*n1/d steps, where n is the total 5
number of nodes
4
 If d = log n  O(log n) steps



Each node knows its neighbors in
the d-space
Forward query to the neighbor that
is closest to the query id
Example: assume n1 queries f4
n5
f4
f1
3
n2
n1
2
f3
1
f2
0
0
5/1/2003
n4
n3
Review Lecture
1
2
3
4
5
6
7
7
Name Lookup



What do names/descriptions look like?
How is the searching done?
What type of searches?

Search for particular service, browse available services or
find collection of services (composition)?
 Exact match queries or richer queries?
 Find any one matching instance or find all matching
instances?

5/1/2003
Which instance to choose  what are the right metrics
Review Lecture
8
INS Architecture: Message routing using
intentional names
Client
Service
Name resolver
Name
Late binding
Name with
message
Intentional
multicast
Intentional
anycast
Overlay network of
resolvers
Name
5/1/2003
Review Lecture
9
INS Lookups

Two styles of message delivery
 Anycast
 Multicast

Two types of lookup
 Early
binding
 Late binding
5/1/2003
Review Lecture
10
Storage Models for Sensor Networks

Local


External


External storage always sends fewer
messages than DCS (Data Centric
Storage)
Data Centric


5/1/2003
Local storage has greatest total message
count as n grows
When many more event types detected
than queried for, DCS has least hotspot
message count
DCS permits summarization of events
(return multiple events in one packet)
Review Lecture
11
Geographic Hash Table

Two operations supported:




Put(k;v) stores v, the event, according to key k
Get(k) retrieves the value associated with key k
Hash a key k into geographic coordinates; store and retrieve
events for that key at that location
Spreads load evenly across key space!
5/1/2003
Review Lecture
12
Network Mapping
Difficult to find nearby nodes quickly and
efficiently
 Huge number of paths to measure
 TCP bandwidth and RTT probes are timeconsuming
 No clean mapping of IP address 
location (geographic or network topology)

5/1/2003
Review Lecture
13
IP2Geo Techniques

GeoTrack
 DNS-based:

traceroute names  locations
GeoPing
 Latency-based:
match host to nearest host with
known location

GeoCluster
 BGP-based:
try to cluster host by announced
address prefixes (with some heuristic corrections)
5/1/2003
Review Lecture
14
Sharing Measurements
IDMaps [Francis et al ’99]
A/B
50ms
Server
Probe
A
Probe
Probe
B
5/1/2003
Review Lecture
15
Global Network Positioning (GNP)
Coordinates



Model the Internet as a
geometric space (e.g. 3D Euclidean)
Characterize the position
of any end host with
geometric coordinates
Use geometric distances
to predict network
distances
5/1/2003
Review Lecture
y
(x2,y2,z2)
(x1,y1,z1)
x
z
(x3,y3,z3)
(x4,y4,z4)
16
Some Sample Questions


Imagine a Chord system using 3-bit ids. Let there be 3 nodes
participating with IDs 0, 3 and 7. Fill in the finger table for node 0.
There are three forms of P2P lookup algorithms: centralized,
flooding-based and routing-based. Which of the following
statements is true about these algorithms?
 Flooding-based and centralized systems can support much
richer queries (regular expressions, wildcards) than routingbased systems.
 Routing-based systems are more scalable than flooding-based
systems since they produce less traffic per search.
 Centralized systems are less prone to failure than floodingbased systems.
 Routing-based systems ensure that a client finds the copy of a
file that is closest to it in the network.
5/1/2003
Review Lecture
17
Some Sample Questions

Harry begins by replacing the Web proxy with a global distributed
hash table (DHT)-based lookup system. When a client makes a
HTTP request, it simply performs a DHT-based lookup for the
request among all participating client caches in the world. If the
object is found, the client retrieves the object from the
participating cache. Ignore the impact of this system on server
load for the following questions.
 Harry wants to ensure that no client is forced to keep track of
more than 10 other clients. Which of the DHT solutions
discussed in class is best suited for this and why?

5/1/2003
Given this choice of DHT, how many DHT-level hops are needed
for a system with N total clients?
Review Lecture
18
Some Sample Questions

Which of following is true about DNS?
 While resolving the A-record for the name goldengate.ne.mediaone.net, a name server that does not have the Arecord cached may not need to go to the root or gTLD server.
 While resolving the A-record for the name goldengate.ne.mediaone.net, suppose a name server contacts the
name server for mediaone.net. Now, if the query packet sent
here is lost, a new lookup originating from the root is initiated.
5/1/2003
Review Lecture
19