INS/Twine : A Scalable Peer-to-Peer Architecture for Intentional Resource DiscoveryProblem DescriptionINS OverviewResource Discovery GoalsExisting Solutions for ScalabilitySlide 6INS/Twine ContributionsINS/Twine Approach OverviewSlide 9Architecture of One ResolverSplitting Descriptions into StrandsDistributed Hash Table: ChordBasic Lookup“Finger table” allows log(N)-time lookupsBack to ExampleProperties of INS/TwineState ManagementSlide 18Slide 19Slide 20Slide 21Evaluation: Data DistributionEvaluation: Query ResolutionConclusionAppendixSlide 26Describing ResourcesProblems using concatenationSlide 29Problems using prefixesINS/Twine : A ScalablePeer-to-Peer Architecture for Intentional Resource DiscoveryMagdalena Balazinska, Hari Balakrishnan, and David KargerMIT – Laboratory for Computer Sciencehttp://nms.lcs.mit.edu/Problem Description•Abundant ubiquitous computation and communication•Increasingly large computing environments•Dynamic environments•Many possible “cool” applicationsLocate resources using intentional descriptionsINS OverviewINR: Intentional Name ResolverINRINRINRINRINRINRSelf-configuringresolver networkResources advertise their capabilitiesClient describes attributes of required resourcesResource Discovery Goals•Allow client applications to locate services and devices•Handle sophisticated resource descriptions•Handle dynamism in the operating environment•Scale to large numbers of resourcesExisting Solutions for ScalabilitySensorProxySensorProxyResolverSensorProxyResolver ResolverResolverPartitioningResolverBldg 1 Bldg 2Bldg 3Floors 1-3 Floors 4-6?ResolverCamerasExisting Solutions for ScalabilitySensorProxySensorProxyResolverSensorProxyResolver ResolverResolverHierarchiesResolverResolverResolverINS/Twine Contributions•Collaborating peer resolvers: no content or location constraints on queries•Scalability and load distribution via hash-based partitioning of resource descriptions among resolvers•Semi-structured resource descriptions with arbitrary attribute-set•Network dynamism•Designed for an environment where all resources are equally important to usersINS/Twine Approach OverviewResolverResolverResolverResolverResolverResolverResolverresource = camerasubject = trafficresource = motion sensorsubject = trafficsubject = trafficsubject = trafficresource = motion sensorresource = cameraSensorProxyINS/Twine Approach Overview1. A resource advertises its descriptions and network location to any resolver2. The description is converted into a canonical form: attribute-value tree (AVTree)3. Using the content of the advertised description, the resolver determines which resolvers should know about the resource4. The resolver forwards the description to these resolvers for storage5. Similarly for queriesArchitecture of One ResolverResolver0110 1001 0000KeyStrandMapperh : 0110 1001 0000Best(01101001000)K nodes are chosenKeyRouter0110 1001 0000Distributed Hash Tableh = hash(a1v1-a2v2)Res adv.…a1v1a2v2StrandSplitting Descriptions into StrandsResource description: AVTreestrafficrootsubjectresourcecameramanufacturerACompanymodelAModelSix strands•Each strand is then hashed into a 128 bit value which determines the nodes that will store the resource information. •All queries, even short stranded queries require asking only one resolver!resourcecameramanufacturerresourcecameraACompanymodelAModelresourcecameraresourcecameramanufacturer modelresourcecamerasubjecttrafficDistributed Hash Table: Chord•Nodes and keys have 160-bit ID’s•Chord maps ID’s to “successor”•Successor: Node with next highest IDN32N10N5N20N110N99N80N60CircularID SpaceStores key-values for keys 21..32Keys 33..60Basic LookupN32N90N105N60N10N120K80“Where is key 80?”“N90 has K80”Successor pointer“Finger table” allows log(N)-time lookupsN80½¼1/81/161/321/641/128finger[i] points tosuccessor (n + 2i)log(n) fingers in allK = log(n) immediateSuccessors for robustnessStabilization methods for concurrencyBack to ExampleResolverResolverResolverResolverResolverResolverResolverresource = camerasubject = trafficresource = motion sensorsubject = trafficsubject = trafficsubject = trafficresource = motion sensorresource = cameraSensorProxyProperties of INS/Twine•For a resource description with a attributes, t at the top-level : –Number of strands is : s = 2a – t•For R resources, S strands, K replication level, and N resolvers :–Storage requirement at each resolver : (RSK)/N•Advertisement: –SK resolvers contacted (+ O(log N) for key routing)•Query: –K resolvers contacted (+ O(log N) for key routing)–100% success rate for less than K failures–Failure rate decreases exponentially with KState Management•Resources join, move, leave and fail•Resolvers join and fail•How to maintain consistency while achieving fault tolerance?–Hard state–Soft state–Hybrid solution implemented in INS/TwineState ManagementINRINR: Intentional Name ResolverINRINRINRINRINRINRINRResourceState ManagementINRINR: Intentional Name ResolverINRINRINRINRINRINRINRResourceRemoveRemoveRemoveState ManagementINRINR: Intentional Name ResolverINRINRINRINRINRINRINRResourceState ManagementINRINR: Intentional Name ResolverINRINRINRINRINRINRINRResourceExpireExpireExpireEvaluation: Data DistributionCumulative fraction of resolvers 00.10.20.30.40.50.60.70.80.910 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45Fraction of resourcesmp3 descr. Thresh. 50mp3 descriptionsBib entries. Thresh. 100Bibliographical entriesData distribution rather even. Each resolvers holds a small fraction of resource descriptionsEvaluation: Query Resolution00.10.20.30.40.50.60.70.80.910 0.01 0.02 0.03 0.04 0.05 0.06Cumulative fraction of resolversFraction of queriesmp3 descriptionsBibliographical entriesEven distribution of queries among resolversConclusion•Intentional resource discovery•Scalable peer-to-peer network of resolvers•Hash-based mapping of resource descriptions to resolvers•Dynamic and even distribution of resource information and queries•Handles dynamism of resources and resolvershttp://nms.lcs.mit.edu/projects/twine/AppendixINS OverviewINR: Intentional Name ResolverDescribing Resources•INS name-specifier<service>printer <type>color</type> <speed>slow</speed></service><cost> high</cost>[service=printer [type=color] [speed=slow]][cost=high]serviceprinterrootcosthighspeedtypecolorslow•XML•AVTreesProblems using concatenation1. If numerous resources share the same
View Full Document
Unlocking...