Transcript ppt

i3 Status
Ion Stoica
UC Berkeley
Jan 13, 2003
The Problem
• Indirection: a key technique in implementing
many network services, e.g.,
–
–
–
–
Mobility
Multicast, anycast
Web caching, replication, load-balancing
Anonymity
• IP doesn’t provide efficient support for
indirection  difficult and complex to deploy
these services
• Our approach: make indirection a first level
design principle in network architecture
[email protected]
Our Solution: Internet Indirection
Infrastructure (i3)
• Add an efficient indirection layer on top of IP
• Use an overlay network to implement it
– Incrementally deployable; no need to change IP
IP router
i3 node
[email protected]
i3 Communication Abstraction
• Provide a rendezvous based communication
abstraction (instead of point-to-point)
– Each packet is associated an identifier id
– To receive a packet with identifier id, receiver R
maintains a trigger (id, R) into the overlay network
send(R, data)
send(id, data)
Sender
trigger
id
R
[email protected]
Receiver (R)
Service Model
• API
– sendPacket(p);
– insertTrigger(t);
– removeTrigger(t) // optional
• Best-effort service model (like IP)
• Triggers are periodically refreshed by endhosts
• Reliability, congestion control, and flowcontrol implemented at end-hosts
[email protected]
The Promise
• Provide support for
–
–
–
–
Mobility
Multicast
Anycast
Service composition
[email protected]
Mobility
• Host just needs to update its trigger as it moves
from one subnet to another
send(id,data)
Sender
send(R1, data)
id R1
[email protected]
Receiver
(R1)
Mobility
• Host just needs to update its trigger as moves
from one subnet to another
send(id,data)
send(R2, data)
Sender
id R2
Receiver
(R2)
[email protected]
Multicast
• Unifies multicast and unicast abstractions
– Multicast: receivers insert triggers with the same
identifier
• An application can dynamically switch between
multicast and unicast
send(id,data)
Sender
send(R1, data)
id R1
Receiver (R1)
id R2
send(R2, data) Receiver (R2)
[email protected]
Anycast
• Generalize the matching scheme used to
forward a packet
– Until now we assumed exact matching
• Next, we assume:
– Longest prefix matching (LPM) using a prefix larger
than a predefined constant l to avoid collisions
• In the current implementation: ID length, m = 256, l = 128
[email protected]
Anycast (cont’d)
• Anycast is simply a byproduct of the new
matching scheme, e.g.,
– Each receiver Ri in the anycast group inserts IDs
with the same prefix p and a different suffix si
send(R1,data)
Receiver (R1)
send(p|a,data)
Sender
p|s1 R1
p|s2 R2
p|s3 R3
Receiver (R2)
Receiver (R3)
[email protected]
Service Composition
• Use a stack of IDs to encode the successions of
operations to be performed on data
• Advantages
– Don’t need to configure path
– Load balancing and robustness easy to achieve
S_MPEG/JPEG
send((id_MPEG/JPEG,id), data)
Sender
(MPEG)
send(R, data)
send(id, data)
id_MPEG/JPEG S_MPEG/JPEG
[email protected]
id
R
Receiver R
(JPEG)
What We’ve Done Since Summer?
• Performance improvements
– Routing efficiency
– Robustness
• Security
[email protected]
Routing Efficiency
• Recall that i3 uses Chord for routing
• Use simple heuristics to reduce Chord’s
routing latency
• Results using 16,384 node networks (path
length = 7), and real latency distributions
– 90th percentile latency < 500 ms
– 90th percentile relative delay penalty (RDP) < 2
• Note: in i3 the latency cost is paid only
first time when a trigger is accessed
– Trigger’s location is cached after first access
[email protected]
Robustness
• Use cooperative algorithms to reduce time
to detect a node failure
– Same message overhead as a simple keepalive alg.
• Can achieve recovery times on the order
of a few RTTs
– Bottleneck in practice: the time it takes to
make sure that a node has failed with high
probability
• See Shelley and Matt’s talk
[email protected]
Security
• Show that i3’s flexibility can improve (not
hurt) end-host security
• Redesign i3 to make it secure without
compromising its flexibility and
performance (see Dan’s talk tomorrow)
[email protected]
Key Observation
• To improve end-host security it is
necessary to give end-hosts more control
on routing and data forwarding in the
infrastructure
[email protected]
Why?
• End-hosts are in the best position to detect
when they are under attack
– E.g., flash-crowd vs. DoS, SYN attack
• Once an end-host detects an attack, it should
be able to stop/redirect the offending traffic
before it arrives at its inbound connection
– i3 gives end-host this flexibility
[email protected]
Example
• Server maintains a public trigger idpublic
– Clients contact the server via its public trigger
• For each client i , the server allocates a private trigger
– The private trigger is a shared secret between the server and
client
send(idprivateA,data)
Host (A)
idpublic S
idprivateA S
send(idprivateB,data)
idprivateB S
Host (B)
[email protected]
Server
(S)
Attack on Private Trigger
• Defense: just remove trigger under attack!
send(idprivateA,data)
Attacker (A)
idpublic S
idprivateA S
send(idprivateB,data)
idprivateB S
Host (B)
[email protected]
Server
(S)
Attack on Private Trigger
• Defense: just remove trigger under attack
– Offending traffic stopped in the network, before
arriving at server’s inbound connection
send(idprivateA,data)
idpublic S
Attacker (A)
send(idprivateB,data)
idprivateB S
Host (B)
[email protected]
Server
(S)
Attack on Public Trigger
• Server maintains n (instead of one) public
triggers
• To establish a connection, a client randomly
selects one of the public triggers
idpublic1 S
idpublic2 S
…
Attacker (A)
idpublicn S
send(idprivateB,data)
Host (B)
idprivateB S
[email protected]
Server
(S)
Attack on Public Trigger (cont’d)
• Assume flooding attack
• Defense: remove the highest loaded m triggers
– Eliminate f=m/n of the offending traffic
– Trade-off: clients need to make 1/(1-f) tries to connect
– Ongoing connections (i.e., private triggers) not affected
idpublic1 S
idpublic2 S
…
Attacker (A)
idpublicn S
send(idprivateB,data)
Host (B)
idprivateB S
[email protected]
Server
(S)
Attack on Public Trigger (cont’d)
• An intelligent attacker can detect when a public
trigger was removed and redirect its attack on
the remaining public triggers
• Server can defend against this by periodically
changing the subset of active triggers
– Every period T make active a different subset of m
triggers out of the available n public triggers
[email protected]
Attack on Public Trigger (cont’d)
• Assume bottleneck is computation not communication
• Defense: redirect traffic to a fake server instead of
removing triggers
– Make it more difficult for attacker to detect when a trigger was
redirected
idpublic1 F
idpublic2 F
…
Attacker (A)
idpublicn S
send(idprivateB,data)
Host (B)
idprivateB S
[email protected]
Fake
server
(F)
Server
(S)
Attack on Public Trigger (cont’d)
• Have the fake server reply with puzzles which, if
solved, reveal active public triggers
• Can use captchas, i.e., puzzles easy to solve by
humans, but very difficult by machines
– E.g., distorted words:
• A human user can always connect after the second
try
[email protected]
Conclusions
• Indirection, key primitive to support
– Basic communication abstractions, e.g., multicast,
anycast, mobility
– Improve end-host security
• This research advocates for:
– Leaving IP do what is doing best: point-to-point unicast
communication
– Building an efficient Indirection Layer on top of IP
[email protected]
Future Work
• More applications
– So far: mobility, multicast
– Next: light-weight name resolution, modular
protocols, …
• Resource management and QoS
[email protected]
Increasing Routing Efficiency
• i3 uses Chord for routing
– Study simple heuristics to reduce Chord’s
routing latency
• Proximity Node Selection, PNS(K)
– Each node maintains for each finger the set of
its K successors
– Chose the closest successor of the finger to
route instead the finger
• Proximity Route Selection (PRS)
– Choose a finger that balances the progress in
the ID space vs. the latency cost
[email protected]
Service Composition (cont’d)
• Receiver can also specify the operations to be
performed on data
S_MPEG/JPEG
send(R, data)
send(id, data)
id_MPEG/JPEG S_MPEG/JPEG
Sender
(MPEG)
send((id_MPEG/JPEG, R), data)
id
(id_MPEG/JPEG, R)
[email protected]
Receiver R
(JPEG)
Collaborators
• Students:
–
–
–
–
–
• Faculty:
Daniel Adkins
Karthik Lakshminarayanan
Ananth Rajagopala-Rao
Sonesh Surana
Shelley Zhuang
– Randy Katz
– Scott Shenker
• Postdocs:
– Kevin Lai
[email protected]