Internet Indirection InfrastructureMotivationsWhy?IP SolutionsApplication Level SolutionsKey ObservationOur Solution: Internet Indirection Infrastructure (i3)i3 Communication AbstractionService ModelThe PromiseMobilitySlide 12MulticastAnycastAnycast (cont’d)Service CompositionService Composition (cont’d)Quick Implementation OverviewRouting ExampleOptimizationsOptimizations (cont’d)Slide 22Examples of Using i3Example 1: Heterogeneous MulticastExample 2: Scalable MulticastExample 3: Load BalancingExample 4: ProximitySecurityEavesdroppingSolutionTrigger hijackingDOS attack on end hostsSolution 1: Stop the AttackSolution 2: Third party firewallTake-home lessonsInternet Indirection InfrastructureSlides thanks toIon StoicaMotivations•Today’s Internet is built around a unicast point-to-point communication abstraction:–Send packet “p” from host “A” to host “B”•This abstraction allows Internet to be highly scalable and efficient, but…•… not appropriate for applications that require other communications primitives:–Multicast –Anycast –Mobility–…Why?•Point-to-point communication abstraction implicitly assumes that there is one sender and one receiver, and that they are placed at fixed and well-known locations–E.g., a host identified by the IP address 128.32.xxx.xxx is located in Berkeley•Network location tied to network layer identifierIP Solutions•Extend IP to support new communication primitives, e.g., –Mobile IP –IP multicast–IP anycast•Disadvantages:–Difficult to implement while maintaining Internet’s scalability (e.g., multicast)–Require community wide consensus -- hard to achieve in practiceApplication Level Solutions•Implement the required functionality at the application level, e.g., –Application level multicast –Application level mobility•Disadvantages:–Efficiency hard to achieve–Redundancy: Each application implements the same functionality over and over again–No synergy: each application implements usually only one service, services hard to combineKey Observation•All previous solutions use a simple but powerful technique: indirection–Assume a logical or physical indirection point interposed between sender(s) and receiver(s)•Examples:–IP multicast assumes a logical indirection point: the IP multicast address–Mobile IP assumes a physical indirection point: the home agentOur 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 IPIP routeri3 nodei3 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 networkSender Receiver (R)id Rtriggersend(id, data)send(R, data)Service Model•API–sendPacket(p);–insertTrigger(t);–removeTrigger(t) •Best-effort service model (like IP)•Triggers are periodically refreshed by end-hosts•Reliability, congestion control, and flow-control implemented at end-hostsThe Promise•Provide support for–Mobility–Multicast –Anycast–Service compositionMobility•Host just needs to update its trigger as it moves from one subnet to anotherSenderReceiver(R1)id R1send(id,data)send(R1, data)Mobility•Host just needs to update its trigger as moves from one subnet to anotherSenderReceiver(R2)id R2send(id,data)send(R2, data)Multicast•Unifies multicast and unicast abstractions–Multicast: receivers insert triggers with the same identifier•An application can dynamically switch between multicast and unicastSenderReceiver (R1)id R1send(id,data)send(R1, data)Receiver (R2)id R2send(R2, data)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 collisionsAnycast (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 siSenderReceiver (R1)p|s1R1send(p|a,data)Receiver (R2)p|s2R2p|s3R3Receiver (R3)send(R1,data)Service Composition•Use a stack of IDs to encode the successions of operations to be performed on data •Similar to the idea of delegation in DOASender(MPEG)Receiver R(JPEG) id_MPEG/JPEGS_MPEG/JPEGidRsend((id_MPEG/JPEG,id), data)S_MPEG/JPEGsend(id, data)send(R, data)Service Composition (cont’d)•Receiver can also specify the operations to be performed on data Receiver R(JPEG) id_MPEG/JPEGS_MPEG/JPEGid(id_MPEG/JPEG, R)send(id, data)S_MPEG/JPEGSender(MPEG)send((id_MPEG/JPEG, R), data)send(R, data)Quick Implementation Overview•i3 is implemented on top of Chord–But can easily use CAN, Pastry, or Tapestry•Each trigger t = (id, R) is stored on the node responsible for id•Use Chord recursive routing to find best matching trigger for packet p = (id, data)Routing Example•R inserts trigger t = (37, R); S sends packet p = (37, data)•An end-host needs to know only one i3 node to use i3–E.g., S knows node 3, R knows node 353720354137 R3720354137 RSRtrigger(37,R)send(37, data)send(R, data)Chord circleSR02m-1Optimizations•Sender/receiver caches node that maps a specific ID•Subsequent packets are sent via one i3 node3720354137 RSRsend(R, data)send(37, data)cache node “41”Optimizations (cont’d)•Address “triangular routing problem”:•Public triggers for initial rendezvous•Private triggers for efficient routing: •Choose private trigger IDs to map onto nearby nodes –Sample identifier space (done off-line), or –Assume end-hosts know the ID of a close by node•Note: only applications are aware of private/public distinction; i3 isn’tOptimizations (cont’d)•H1 wants to contact H2–H1 knows H2’s public trigger (e.g., Hash(cnn.com))idpublicH2H1id1privateid2privateH2H1H2send(idpublic, id1private)send(H2, id1private)send(id1private, id2private)send(id2private, data)send(H2, data)Examples of Using i3•Heterogeneous multicast•Scalable Multicast•Load balancing•ProximityExample 1: Heterogeneous Multicast•Sender not aware of transformationsReceiver R1(JPEG) id_MPEG/JPEGS_MPEG/JPEGid(id_MPEG/JPEG, R1)send(id, data)S_MPEG/JPEGSender(MPEG)send((id_MPEG/JPEG, R1), data)send(R1, data)idR2Receiver R2(MPEG)send(R2, data)Example 2: