Distributed Systems CS 15-440 Naming Lecture 7, September

Distributed Systems CS 15-440 Naming Lecture 7, September

Distributed Systems CS 15-440 Naming Lecture 7, September 16, 2019 Mohammad Hammoud Today Last Session: Architectures Todays Session: Naming Announcements: PS2 is out. It is due on Monday, September 23rd by midnight P1 is due on Wednesday, Oct 2nd Quiz I will be held on Thursday, September 26th Naming Names are used to uniquely identify entities in distributed systems Entities may be processes, remote objects, newsgroups, etc., Names are mapped to entities locations using name resolution An example of name resolution: Name http://www.cdk5.net:8888/WebExamples/earth.html DNS Lookup 55.55.55.55 MAC address 02:60:8c:02:b0:5a Resource ID (IP Address, Port, File Path)

8888 WebExamples/earth.html Host Names, Addresses, and Identifiers An entity can be identified by three types of references a) Name A name is a set of bits or characters that references an entity Names can be human-friendly (or not) b) Address Every entity resides on an access point, and access point has an address Addresses may be location-dependent (or not) E.g., IP Address + Port c) Identifier Identifiers are names that uniquely identify entities A true identifier is a name with the following properties: An identifier refers to at-most one entity Each entity is referred to by at-most one identifier An identifier always refers to the same entity (i.e. it is never reused) Naming Systems A naming system is simply a middleware that assists in name resolution Naming systems can be classified into three classes, based on the type of names used: a. Flat naming b. Structured naming c. Attribute-based naming Classes of Naming Flat naming

Structured naming Attribute-based naming Flat Naming In flat naming, identifiers are simply random bits of strings (known as unstructured or flat names) A flat name does not contain any information on how to locate an entity We will study four types of name resolution mechanisms for flat names: 1. 2. 3. 4. Broadcasting Forwarding pointers Home-based approaches Distributed Hash Tables (DHTs) 1. Broadcasting Approach: Broadcast the name/address to the whole network; the entity associated with the name responds with its current identifier Example: Address Resolution Protocol (ARP) Resolve an IP address to a MAC address In this system, Who has the address 192.168.0.1? x x IP address is the address of the entity MAC address is the identifier of the access point Challenges:

I am 192.168.0.1. My identifier is 02:AB:4A:3C:59:85 Not scalable in large networks This technique leads to flooding the network with broadcast messages Requires all entities to listen (or snoop) to all requests 2. Forwarding Pointers Forwarding pointers enable locating mobile entities Mobile entities move from one access point to another When an entity moves from location A to location B, it leaves behind (at A) a reference to its new location at B Name resolution mechanism: Follow the chain of pointers to reach the entity Update the entitys reference when the present location is found Challenges: Long chains lead to longer resolution delays Long chains are prone to failures due to broken links Forwarding Pointers An Example Stub-Scion Pair (SSP) chains implement remote invocations for mobile entities using forwarding pointers Server stub is referred to as Scion in the original paper Each forwarding pointer is implemented as a pair: (client stub, server stub) The server stub contains a local reference to the actual object or a local reference to another client stub When object moves from A (e.g., P2) to B (e.g., P3), It leaves a client stub at A (i.e., P2) It installs a server stub at B (i.e., P3) Process P2

Process P1 Process P3 Process P4 n = Process n; = Remote Object; = Caller Object; = Server stub; = Client stub 3. Home-Based Approaches Each entity is assigned a home node The home node is typically static (has fixed access point and address) It keeps track of the current address of the entity Entity-home interaction: Entitys home address is registered at a naming service The entity updates the home about its current address (foreign address) whenever it moves Name resolution: Client contacts the home to obtain the foreign address Client then contacts the entity at the foreign location 3. Home-Based Approaches An Example 1. Update home node about the foreign address Mobile entity

3a. Home node forwards the message to the foreign address of the mobile entity Home node 3b. Home node replies to the client with the current IP address of the mobile entity 4. Client directly sends all subsequent packets directly to the foreign address of the mobile entity 2. Client sends the packet to the mobile entity at its home node 3. Home-Based Approaches Challenges The static home address is permanent for an entitys lifetime If the entity permanently moves, then a simple home-based approach incurs higher communication overhead Connection set-up overheads due to communication between the client and the home can be excessive Consider the scenario where the clients are nearer to the mobile entity than the home entity 4. Distributed Hash Table (DHT) DHT is a distributed system that provides a lookup service similar to a hash table (key, value) pair is stored in the nodes participating in the DHT

The responsibility for maintaining the mapping from keys to values is distributed among the nodes Any participating node can serve in retrieving the value for a given key We will study a representative DHT known as Chord DATA KEY Pink Panther Hash function ASDFADFAD cs.qatar.cmu.edu Hash function DGRAFEWRH 86.56.87.93 Hash function 4PINL3LK4DF DISTRIBUTED NETWORK Participating Nodes Chord Entity

with k Node n (node with id=n) 000 Chord assigns an m-bit identifier (randomly chosen) to each node 003 A node can be contacted through its network address 004 Alongside, it maps each entity to a node Entities can be processes, files, etc., Node 000 008 Node 005 040 079 Mapping of entities to nodes Each node is responsible for a set of entities An entity with key k falls under the jurisdiction of the node with the smallest identifier id >= k. This node is known as the successor of k, and is denoted by succ(k) Node 010 Node 301

Map each entity with key k to node succ(k) A Nave Key Resolution Algorithm The main issue in DHT is to efficiently resolve a key k to the network location of succ(k) Given an entity with key k, how to find the node succ(k)? 30 31 00 19 01 02 29 03 28 04 27 05 26 06 25

07 24 08 23 09 22 10 21 11 20 12 19 13 18 n 17 = Active node with id=n 16 p 15 14

= No node assigned to key p 1. All nodes are arranged in a logical ring according to their IDs 2. Each node p keeps track of its immediate neighbors: succ(p) and pred(p) 3. If p receives a request to resolve key k: If pred(p) < k <=p, node p will handle it Else it will forward it to succ(n) or pred(n) Solution is not scalable: As the network grows, forwarding delays increase Key resolution has a time complexity of O(n) Key Resolution in Chord 1 01 2 01 3 01 4 04 5 14 30

31 1 04 2 04 3 09 4 09 i 5 18 1 09 2 09 3 09

4 14 5 20 00 01 26 29 1 (i- 02 03 28 04 27 05 26 28 2 28

3 28 4 01 5 09 07 24 08 23 09 22 10 21 1 11 2 11 3

14 4 18 5 28 11 20 12 19 13 1 21 2 28 3 28 1 20 4

28 2 20 5 04 3 28 4 28 5 04 18 17 16 15 14 ) ) Chord improves key resolution by reducing the time

complexity to O(log n) 1. All nodes are arranged in a logical ring according to their IDs 2. Each node p keeps a table FTp of at-most m entries. This table is called Finger Table FTp[i] = succ(p + 2(i-1)) NOTE: FTp[i] increases exponentially 06 25 1 + 2 p ( c suc 1 14 2 14 3 18 1 18 4 20

2 18 5 28 3 18 4 28 5 01 3. If node p receives a request to resolve key k: Node p will forward it to node q with index j in Fp where q = FTp[j] <= k < FTp[j+1] If k > FTp[m], then node p will forward it to FTp[m] If k < FTp[1], then node p will forward it to FTp[1] Chord Join and Leave Protocol In large-scale distributed Systems, nodes dynamically join and leave (voluntarily or due to failures) 30 It contacts arbitrary node, looks up for

succ(p+1), and inserts itself into the ring 00 01 02 29 03 28 04 27 05 Node 4 is succ(2+1) 26 If a node p wants to join: 31 06 25 07 24

08 02 Who is succ(2+1) ? 23 09 22 If node p wants to leave: It contacts pred(p) and succ(p+1) and updates them 10 21 11 20 12 19 13 18 17 16 15 14 Chord Finger Table Update

Protocol For any node q, FTq[1] should be up-to-date It refers to the next node in the ring Protocol: Periodically, request succ(q+1) to return pred(succ(q+1)) If q = pred(succ(q+1)), then information is up-to-date Otherwise, a new node p has been added to the ring such that q < p < succ(q+1) FTq[1] = p Request p to update pred(p) = q Similarly, node p updates each entry i by finding succ(p + 2(i-1)) Exploiting Network Proximity in Chord The logical organization of nodes in the overlay network may lead to inefficient message transfers Node k and node succ(k +1) may be far apart Chord can be optimized by considering the network location of nodes 1.Topology-Aware Node Assignment Two nearby nodes get identifiers that are close to each other 2.Proximity Routing Each node q maintains r successors for ith entry in the finger table FTq[i] now refers to r successor nodes in the range [p + 2(i-1), p + 2i -1] To forward the lookup request, pick one of the r successors closest to the node q Next Class Structured and attribute-based namings

Recently Viewed Presentations

  • Biodegradation - Rutgers University

    Biodegradation - Rutgers University

    Alkane Biodegradation R. A. Kerr Science 329, 734-735 (2010) Alkanes Alkane Formula Boiling point [°C] Melting point [°C] Solubility at 20 °C Methane CH4 -162 -182 gas Ethane C2H6 -89 -183 63.7 gas Propane C3H8 -42 -188 gas Butane C4H10...
  • The Legacy of Ancient Greece and Rome

    The Legacy of Ancient Greece and Rome

    The Legacy of Ancient Greece and Rome A. Athens and Limited Democracy Greek civilization begins around 2000 B.C.E. Due to geography, initially made up of independent city-states Most powerful of these - Athens City ruled by a council of three...
  • Number Bond Rhymes to Ten Activity Bev Evans,

    Number Bond Rhymes to Ten Activity Bev Evans,

    Activity ©Bev Evans, 2012 . www.communication4all.co.uk. Number Bond Rhymes. to Ten. Click to see the rhyme. Zero and ten. Eggs again! Number Bond Rhymes. to Ten. Click to see the rhyme. Nine and one. Ballooning fun! Number Bond Rhymes. to...
  • Gases - gcate.org

    Gases - gcate.org

    For example, P goes up as V goes down. P1V1 = P2 V2 Robert Boyle (1627-1691). Son of Earl of Cork, Ireland. Boyle's Law and Kinetic Molecular Theory P proportional to 1/V Boyle's Law A bicycle pump is a good...
  • Coastal Processes &amp; Landforms

    Coastal Processes & Landforms

    Heavier load of rock and shingle is deposited on the backshore. Finer, lighter material such as sand is deposited on the foreshore. Over time a beach is formed. A storm beach is made of pebbles and stones. It forms when...
  • Phelps County Disaster Committee - RollaNet

    Phelps County Disaster Committee - RollaNet

    Phelps County Disaster Committee Overview History... Formed as an ad-hoc response to Beaver Manor subdivision flooding, April 2002. Organized & implemented cleanup effort. Follow-up meetings showed need and interest in long-term existence of PCDC. SEMA encouraged incorporation as VOAD. VOAD...
  • The expansion of Industry

    The expansion of Industry

    By the end of 1893, 600 banks, 15,000 businesses failed & 3 million people lost their jobs. By the middle of 1894, 25% of the nation's railroads were in the hands of banks, which allowed large firms like J.P. Morgan...
  • Inventory Theory - Citadel

    Inventory Theory - Citadel

    Echelon. Each stage in a multi-stage inventory system. Supply chain. ... Traditional method: a two-bin system. All units for a particular product held in two bins. Capacity of one bin equals the reorder point. Units first withdrawn from the other...