1、Internet Indirection Infrastructure (i3 ),Ion Stoica, Daniel Adkins, Shelley Zhuang, Scott Shenker, Sonesh SuranaUC BerkeleySIGCOMM 2002Presented by: Ao-Jan Su,Motivations,Todays Internet is built around a unicast point-to-point communication abstraction: Send packet “p” from host “A” to host “B”Poi
2、nt-to-point communication Implicitly assumes there is one sender and one receiver, and that they are placed at fixed and well-known locations Example: a host identified by the IP address 165.124.180.xxx is located in NU,Motivations,This abstraction allows Internet to be highly scalable and efficient
3、, but not appropriate for applications that require other communications primitives: Multicast Anycast Mobility More general abstraction is needed,Solution,Use an overlay network to implement this layer Incrementally deployable; dont need to change IP,Solution,An indirection layer based on overlay n
4、etwork (decouples sending and receiving),Multicast,Anycast,Mobility,Service Composition,IP Layer,Internet Indirection Infrastructure (i3),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,Service Model,AP
5、I sendPacket(p); insertTrigger(t); removeTrigger(t) / optional Best-effort service model (like IP) Triggers periodically refreshed by end-hosts ID length: 256 bits,Mobility,Host just needs to update its trigger as it moves from one subnet to another,Sender,Multicast,Receivers insert triggers with sa
6、me identifier Can dynamically switch between multicast and unicast,Sender,Receiver (R1),Receiver (R2),Anycast,Use longest prefix matching instead of exact matching Prefix p: anycast group identifier Suffix si: encode application semantics, e.g., location,Stack of Identifiers,idstack: (id1, id2, id3,
7、idk) idi is either identifier or an address Packet p = (idstack, data) Trigger t = (id, idstack),Using i3,Service Composition Server initiated Receiver initiated Large Scale Multicast,Service Composition: Sender Initiated,Use a stack of IDs to encode sequence of operations to be performed on data pa
8、th,Sender (MPEG),Receiver R (JPEG),ID_MPEG/JPEG,S_MPEG/JPEG,ID,R,S_MPEG/JPEG,Service Composition: Receiver Initiated,Receiver can also specify the operations to be performed on data,Sender (MPEG),Receiver R (JPEG),S_MPEG/JPEG,Large Scale Multicast,Can create a multicast tree for scalability,R2,R1,R4
9、,R3,gR2,gR1,g x,xR4,xR3,(g, data),Implementation Overview,ID space is partitioned across infrastructure nodes Each node responsible for a region of ID space Each trigger (id, R) is stored at the node responsible for id Use Chord to route triggers and packets to nodes responsible for their IDs O(log
10、N) hops,Properties,Robustness, Efficiency, Scalability, Stability Robustness: refresh triggers , trigger replication, back-up triggers Efficiency: Routing optimizations Incremental deployment possible Legacy applications can be supported by proxy which inserts triggers on behalf of client,Example,ID
11、 space 063 partitioned across five i3 nodes Each host knows one i3 node R inserts trigger (37, R); S sends packet (37, data),Example,ID space 063 partitioned across five i3 nodes Each host knows one i3 node R inserts trigger (37, R); S sends packet (37, data),Optimization: Path Length,Sender/receive
12、r caches i3 node mapping a specific ID Subsequent packets are sent via one i3 node,Optimization: Location-aware Triggers,Well-known (public) trigger for initial rendezvous Exchange a pair of (private) triggers well-located Use private triggers to send data traffic,Private Triggers: - S can insert a
13、trigger 1,S that is stored at server 3 - R can chose a trigger 30,R that is stored at server 35,Security,i3 end-points also store routing information New opportunities for malicious users Goal: make i3 not worse than todays Internet,Some Attacks,Solutions,Eavesdropping: Use private triggers, periodi
14、cally change them, multiple private triggersDoS Attacks: Challenges, Fair Queueing for resource allocation, loop detectionDead-End: Use push-back,Experimental Results,Simulation over two topologies Power-law random graph topology Transit-stub topologyLatency Stretch = (i3 latency)/(IP latency) First
15、 Packet Latency, End-to-end Latency,First Packet Latency,90th percentile latency stretch vs. no of i3 servers for Transit-stub topology,HeuristicsClosest Finger Replica: Store r successors of each fingerClosest Finger Set: Use base b 2 to find fingers, but consider only log2N closest fingers when ro
16、uting,End-to-end Latency,90th percentile latency stretch vs. no of samples (16384 i3 servers) i3 latency = (sender to i3 server)+(i3 server to receiver),Conclusions,Indirection key technique to implement basic communication abstractions Multicast, Anycast, Mobility, This research Advocates for building an efficient Indirection Layer on top of IP Explores the implications of changing the communication abstraction,
