CS 268: Computer NetworkingL-18 Naming2Overview• i3• Layered naming• DOA• SFRMulticastS1C1C2S2R RP RRRRRP: RendezvousPoint3MobilityHA FAHome NetworkNetwork 55.0.0.1 12.0.0.4SenderMobileNode5.0.0.345i3: Motivation• Today’s Internet based on point-to-pointabstraction• Applications need more:• Multicast• Mobility• Anycast• Existing solutions:• Change IP layer• OverlaysSo, what’s the problem?A different solution for each serviceThe i3 solution• Solution:• Add an indirection layer on top of IP• Implement using overlay networks• Solution Components:• Naming using “identifiers”• Subscriptions using “triggers”• DHT as the gluing substrate6IndirectionEvery problemin CS … Only primitiveneededi3: Rendezvous Communication• Packets addressed to identifiers (“names”)• Trigger=(Identifier, IP address): inserted byreceiver7Sender Receiver (R)ID Rtriggersend(ID, data)send(R, data)Senders decoupled from receivers8i3: Service Model• API• sendPacket(id, p);• insertTrigger(id, addr);• removeTrigger(id, addr); //optional• Best-effort service model (like IP)• Triggers periodically refreshed by end-hosts• Reliability, congestion control, and flow-control implemented at end-hostsi3: Implementation• Use a Distributed Hash Table• Scalable, self-organizing, robust• Suitable as a substrate for the Internet9Sender Receiver (R)ID Rtriggersend(ID, data)send(R, data)DHT.put(id)IP.route(R)DHT.put(id)10Mobility and Multicast• Mobility supported naturally• End-host inserts trigger with new IP address,and everything transparent to sender• Robust, and supports location privacy• Multicast• All receivers insert triggers under same ID• Sender uses that ID for sending• Can optimize tree construction to balance loadMobility• The change of the receiver’s address• from R to R’ is transparent to the sender11Multicast• Every packet (id, data) is forwarded to eachreceiver Ri that inserts the trigger (id, Ri)1213Anycast• Generalized matching• First k-bits have to match, longest prefix matchamong restSender(R1)(R2)(R3)a ba b1a b2a b3Triggers• Related triggers must be on same server• Server selection (randomize last bits)Generalization: Identifier Stack• Stack of identifiers• i3 routes packet through these identifiers• Receivers• trigger maps id to <stack of ids>• Sender can also specify id-stack in packet• Mechanism:• first id used to match trigger• rest added to the RHS of trigger• recursively continued14Service Composition• Receiver mediated: R sets up chain andpasses id_gif/jpg to sender: sender oblivious• Sender-mediated: S can include (id_gif/jpg, ID)in his packet: receiver oblivious15Sender(GIF)Receiver R(JPG)ID_GIF/JPGS_GIF/JPGID Rsend((ID_GIF/JPG,ID), data)S_GIF/JPGsend(ID, data) send(R, data)Public, Private Triggers• Servers publish their public ids: e.g., viaDNS• Clients contact server using public ids, andnegotiate private ids used thereafter• Useful:• Efficiency -- private ids chosen on “close-by” i3-servers• Security -- private ids are shared-secrets16Scalable Multicast• Replication possible at any i3-server in theinfrastructure.• Tree construction can be done internally17R2R1R4R3g R2g R1gxx R4x R3(g, data)18Overview• i3• Layered naming• DOA• SFR19Architectural Brittleness• Hosts are tied to IP addresses• Mobility and multi-homing pose problems• Services are tied to hosts• A service is more than just one host: replication,migration, composition• Packets might require processing atintermediaries before reaching destination• “Middleboxes” (NATs, firewalls, …)20Naming Can Help• Thesis: proper naming can cure some ills• Layered naming provides layers of indirection andshielding• Many proposals advocate large-scale,overarching architectural change• Routers, end-hosts, services• Proposal:• Changes “only” hosts and name resolution• Synthesis of much previous work21Internet Naming is Host-Centric• Two global namespaces: DNS and IPaddresses• These namespaces are host-centric• IP addresses: network location of host• DNS names: domain of host• Both closely tied to an underlying structure• Motivated by host-centric applications22The Trouble with Host-Centric Names• Host-centric names are fragile• If a name is based on mutable properties of itsreferent, it is fragile• Example: If Joe’s Web pagewww.berkeley.edu/~hippie moves towww.wallstreetstiffs.com/~yuppie, Web links tohis page break• Fragile names constrain movement• IP addresses are not stable host names• DNS URLs are not stable data names23Key Architectural Questions1. Which entities should be named?2. What should names look like?3. What should names resolve to?24Name Services and Hosts Separately• Service identifiers (SIDs) are host-independent data names• End-point identifiers (EIDs) are location-independent host names• Protocols bind to names, and resolve them• Apps should use SIDs as data handles• Transport connections should bind to EIDsBinding principle: Names should bind protocols onlyto relevant aspects of underlying structure25The Naming LayersUser-level descriptors(e.g., search)App sessionApp-specific search/lookupreturns SIDTransportResolves SID to EIDOpens transport connsIPResolves EID to IPBind to EIDUse SID as handleIP hdrEID TCP SID …IPTransportApp sessionApplication26SIDs and EIDs should be Flat0xf436f0ab527bac9e8b100afeff394300• Flat names impose no structure on entities• Structured names stable only if name structurematches natural structure of entities• Can be resolved scalably using, e.g., DHTs• Flat names can be used to name anything• Once you have a large flat namespace, younever need other global “handles”Stable-name principle: A stable name should not impose restrictions on the entity it names27ResolutionServiceFlat Names Enable Flexible Migration<A HREF=http://f012012/pub.pdf>here is a paper</A>HTTP GET:/docs/pub.pdf10.1.2.3/docs/20.2.4.6HTTP GET:/~user/pubs/pub.pdf(10.1.2.3,80,/docs/)(20.2.4.6,80,/~user/pubs/)/~user/pubs/• SID abstracts all object reachability information• Objects: any granularity (files, directories)• Benefit: Links (referrers) don’t breakDomain HDomain Y28Flat Names are a Two-Edged Sword• Global resolution infrastructure needed• Perhaps as “managed DHT” infrastructure• Lack of local name control• Lack of locality• Not user-friendly• User-level descriptors
View Full Document
Unlocking...