Naming I – Flat Naming

10 minute read

Updated:

Basic definitions

  • Names – are used to share resources, to uniquely identify entities, to refer to locations, etc.
  • Entities – in any computer system must be given names if we are able to have access to them
    • Entities could be software, hardware, disk, file, page, etc
    • Name is a string of bits or characters -usually human readable
  • These names must bound to attributes – how does attributes define the actual name
    • Normally the attributes will give us access to that entity
  • Name is resolved when we translate it into those attributes – you are finding Mr. brown in the audience
  • In DS the implementation of naming system is often described across multiple machines.
    • How this distribution is done plays a key role in efficiency and scalability of naming sys
  • → The end of the day, aim is to access the identity through its name

Name resolution example

  • How can I resolve name in the content of that urL?
  • URL – http://www.acme.com:8080/products/catalog.html
    • Screenshot 2020-02-25 at 8 55 53 pm
    • First thing is to try to look the server where the object or entity is - To access the server I need to know the IP address – there exists DNS look-up who tells you the IP address.
    • Second thing is the port, it may suggest that it’s running on localhost-8080
    • Next is /products/catalog.html – there’s a folder and there’s this HTML file
    • → We try to resolve the name step by step
    • On a web server there’s a file, and what do I need? I will need to actually access the server, which is prolly sitting on a cluster – that IP address is gonna be translated into network address to access THE host machine itself!! we take the network address + port no to access actual host machine.
    • Ip address to network address translation is through ARP
      • Address resolution protocol – I took IP and translated into data link address to have access to host machine which helps you resolve the name

Access points and addresses

  • To operate on any entity – I need special kind of entity called access point - The name of the access point itself is called address.
  • The entity itself can have more than one access point
    • E.g. telephone – access point, telephone number – address. you can have 5 phone number!!
    • In ds, access point – a host running a specific server, address – IP+ port no.
  • Entity may change its access points
    • E.g. computer move from one to another- diff IP address. I should be reachable – and bc mobile IP address keeps changing – so it may change over time
  • In general, don’t want to use an address as a regular name – coz it changes! So we want location-independent name!

Function of a naming system**

  • Naming system manages set of bindings btwn names and attributes of entities in the system.
    • In simplest form is a table of (name, address) pairs
  • Primary function of naming service is naming resolution
  • Secondary functions:
    • To create new binding
    • Delete existing binding – name may say they want to remove that attribute
    • Listing of bound names
    • Can organize the namespace as I want

Flat naming systems

  • Entities are referred to by an identifier - and principles have no meaning at all – it doesn’t tell you how to locate the access point of its associated entity. could not be human readable
  • No structure and it needs special mechanisms to trace the location of entities

1. Broadcasting

  • It broadcasts the ID- a message containing the identifier of the entity is broadcast to each machine and each machine checks if they’ve got it, and send back a reply message with the address of the access point.
  • You require all the process and entities are READY to listen to the incoming call.
  • However, it doesn’t scale beyond the LAN – but in WAN with thousands of machines it will never work coz it doesn’t scale
  • Network bandwidth is wasted by request messages, and too many hosts are interrupted
  • E.g. ARP – Address Resolution Protocol
    • To find MAC address of the machine, you will basically have one of the hosts and say I need to deliver this data to this machine, who has this IP address

2. Forwarding pointers

  • When an entity moves from A to B, it leaves behind in A a pointer to its new location at B.
    • Dereferencing can be made transparently to clients by having a chain of pointers – you keep track of where the entity is
    • Client keeps updating the reference of the entity – good news is entity is always gonna be found
  • Drawbacks
    • If no special measure is taken, a chain for an entity can be so long and hence expensive locating. → latency may be an issue
    • Intermediate locations have to maintain their part of the chain all the time
    • Broken links – one pointer can fail and the whole chain will be broken!!!

  • Example: SSP chains

    • Screenshot 2020-02-25 at 8 58 25 pm
    • Each forwarding pointer – a (client stub, server stub) pair to access object
    • P1- P3- P4 → it leaves behind the client stub – if you want to find me here’s my stub.
    • Prev client will use the stub as a pointer to the next P’s server stub.
    • P2 is looking for the stub – could broadcast does anyone have the client stub? Then p1 has – p1 and p2 will have the same stub – and it will both point to P3’s server stub which leads you to P4’s server stub aka the object you wanna refer to.
    • BUT – there exists a way to make the forwarding pointer more efficient
      • Screenshot 2020-02-25 at 8 59 08 pm (a) and (b)
      • One may break coz it’s too long – why can’t we redirect the pointer by storing a shortcut in a client stub? - hence server stub is no longer referenced.
        • If it is found, it doesn’t need to go through all the pointer – it simply gives a copy of the stub
        • Communication is faster coz fewer process.
      • Once ur entity is found, the server can send some info to initial requester, and give a copy of the stub.
      • Let the object’s home location keep a reference to its current location.

3. Home-based approach

  • It approaches through a home – the home location keeps track of where the entities are.
    • Communication to that IP address is first directed to the home agent.
    • Home agent is located in LAN corresponding to the network address contained in the mobile host’s IP address
    • Whenever mobile host moves to another network, it requests a foreign address (care of address) to use for communication
  • How it works
    • When home agent receives a packet for mobile host, it looks up host’s current loc. If its in local network, packet is forwarded. If not, it is tunnelled to the current location, wrapped as data in an IP packet and sent to the care-of address.

  • Whole mechanism is hidden and transparent!! – location transparency is high

  • Example: mobile IP
    • Screenshot 2020-02-25 at 9 00 04 pm
    • Assume there’s an entity where the home origin is the states, and the entity is now in south Africa lol – and there are client in Singapore that needs to access to the entity that is currently in south africa
      1. First, Singapore client sends packet to the host at home.
      2. Host home will return address of current location aka Singapore AND at the same time, host home will tunnel the packet to the current location – forwarded or tunnelled
      3. Then client will send successive packets to the current location - host name has played the role of intermediary agent
    • Aspect of tunnelling is v important
  • Problems
    • In large scale network, the home may be in complete diff location → increase in communication latency!!
      • What if this client is next door to south Africa – it’s wasting resources!!why would you connect the US
    • Used of fixed home location – it always has to exists, if not, contacting the entity is impossible. The host itself could fail
    • Possible that entity migrates to the location and stay there forever – better if the home could move along to minimize the waste
    • Home address is fixed – it can’t move to somewhere close

4. Distributed Hash Tables

  • The way we organise them is a logical ring – you have entities and they hold some information
    • We expect every node to be with a random m-bit identifier
    • Entity is assigned a unique key
    • Entity with key k – falls under jurisdiction of node with smallest id k – successor of k
  • We can make each node keep track of its neighbour – you start linear search along the ring
    • E.g. you search from 1 ,3, 4, etc until you get to 13 – never scalable and inefficient.

  • We will speak of node p as the node having the identifier p – we are resolving name through a key

  • Principles
    • Finger table – each node p maintains a finger table with less than m entries
      • Calculate and fill in by FTp[i] = succ(p+ 2i−1)
    • Forwarding: q = FTp[j] ≤ k < FTp[j+ 1]

    • Or q = FTp[1] when p < k <FTp[1]

    • Example – resolving k= 26 from node 1 and k= 12 from 28
      • Screenshot 2020-02-25 at 9 04 28 pm
      • Node 1 will look up k = 26 in its finger table, to discover that this value is larger than the last element of the finger table. So its forwarded to 18 which is the last entry. Then 18 will select node 20, as FT[2]<k<FT[3]. Then, the request is forwarded from node 20 to 21, and from there to 28, which is responsible for k =26. (21 < 26 < FTp[1] 18) so q= 28.

5. Hierarchical approaches

  • Idea is to build a large-scale search tree for which the underlying network is divided into hierarchical domains. - Looking to resolve an entity
    • Each domain is represented by a separate directory node.
    • Top-level domain t – root directory node → knows about all entities
    • Lowest level domain – leaf domain – and the information we are looking for is usually here
    • Screenshot 2020-02-25 at 9 05 30 pm

Tree organisation

  • Address of entity E is stored in a leaf or intermediate node
  • BUT how do you lookup for the address of the entity? How to insert and delete?
    • Going back to the basics, tree structure, use concept of pointer.
  • Intermediate nodes contain a pointer to a child iff the subtree rooted at the child stores an address of the entity
  • Assumption is there’s a root node, and is a point of entry, and it knows all about the entities
  • Eg – multiple addresses in different leaf domains
    • Screenshot 2020-02-25 at 9 05 55 pm
    • If entity E has an address in - 2 address in 2 leaf domain - E is replicated in D1 and D2.
    • Then the directory node of the smallest domain (M) containing both D1 and D2 will have 2 pointers, one for each subdomain (N) containing an address
      • The way it works is you can decide with entry node M there’s two pointers aka children. And that N itself will help you store or locate the record of the entity you are looking for

  • Imp at this stage is to understand how to lookup operation works

  • Lookup Operation
    • Screenshot 2020-02-25 at 9 06 35 pm
    • Start lookup at local leaf node and work ur way up by forwarding the request
    • It may come as a request to this domain and this domain may or not hold the info I want – the node knows nothing→ then it sends the request to its parent. Then the parents say it needs to ask the root directory. In this case M, and m knows about it. Hence the request is forwarded to the child.
      • Right child, and helps you locate the entity you are looking for
    • Start always with a leaf and up to the tree to look for information
  • Insert operation
    • You have an insert request going to one of the leaf nodes. If it has no information, request is forwarded to the parent, parent contacts root node M and in this case M has a task to create an entry (coz its insert) so it creates a record and stores the address of the entity
    • A chain of forwarding pointers to the leaf node is created
    • Understand that the right child has info but not the left – one way to replicate that information

Summary

  • 5 different mechanism for flat name space
  • Name space naming service is v imp and the definition of attributes!!
  • Naming services allow us to bind a name to the attributes of some entity in a DS, and resolve a name into those attributes. Entity addresses should not be used as names.
  • Names can be organised into name systems
  • Explored various flat name systems

Leave a comment