Tuesday, December 29, 2015

Naming

Naming Entities

  • A name in a distributed system is a string of bits or characters that is used to refer to an entity 
  • Type of names
    • Address
      • The name of an access point of an entity
    • Identifiers
      • A name that uniquely identifies an entity
    • Location-independent name
      • A name that is independent from its addresses

Name Resolution

  • A naming system maintains a name-to-address binding for resources
  • Main problem in naming
    • How to do name resolution in a distributed systems in a scalable way
  • Approaches for name resolution closely tied to naming scheme
  • Flat vs Structure naming
    • In a flat name space, identifiers are random bit strings
    • No information on location embedded in name

Name Resolution in a Flat Name Space

  • Simple solutions that work in a LAN environment
    • Broadcasting & Multicasting
      • Message containing identifier of the entity is boardcast
      • Machine with access point for the entity replies with the address of the access point
        • ARP protocol for finding the data-link address of a machine given the IP address
        • When network grows, multicast is more efficient
    • Forwarding pointers
      • When an entity moves from A to B, it leaves behind a reference to its new location at B
  • Home-based Approaches
    • Home agent keeps track of current location of mobile entity
  • Hierarchical Approaches
    • Similar to DNS


What is a DHT

  • Distributed Hash Table
    • key = hash(data)
    • lookup(key) -> IP address
    • send-RPC(IP address, PUT, key, value)
    • Send-RPC(IP address, GET, key)  -> value
  • Chord


Structure Naming Systems

  • Names are organized into name spaces
    • A name space can be represented as a labeled, directed graph wit two types of nodes
      • Leaf nodes and directory nodes
      • Absolute vs relative path names
      • Local names vs global names
    • Name resolution: the process of looking up a name
      • Closure mechanism
        • Knowing where and how to start name resolution
  • Unix File Name Spaces


Linking and Mounting

  • Symbolic link

  • Mounting remote name spaces




Implementing Name Spaces

  • Naming service
    • A service that allows users and processes to add, remove, and lookup names
  • Name spaces for large-scale widely distributed systems are typically organized hierarchically
  • Three layers used to implement such distributed name spaces
    • Global layer
      • root node and its children
    • Administrational layer
      • Directory nodes within a single organization
    • Managerial layer
  • Example: DNS name space

Iterative vs Recursive Resolution

  • Recursive

    • puts a higher performance demand on each name server
    • cons
      • Too high for global layer name servers
    • Pros
      • Caching is more effective
      • Communication costs may be reduces
    • Example

  • Iterative
    • Example

Attribute-based Naming


  • An entity is described in terms of (attribute, value) pairs
  • Each entity can have several attributes
  • Attribute-based naming service are called directory services
  • LDAP (Lightweight directory access protocol) defacto industry standard
    • Based on OSI X.500 directory service
  • Another example: UDDI for web services

No comments:

Post a Comment