Naming vs. Locating Entities Simple Solution for a

Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Naming vs. Locating Entities
Simple Solution for a Location Service
Till now: resources with fixed locations (hierarchical, caching, ...)
Problem: some entity may change its location frequently
Using Broadcast or Multicast
Simple solution: record aliases for the new address or the new name
Broadcast is typically offered in LANs
But: efficiency, re-use of old names, ...
Simple locating process: broadcast identifier and wait on a reply
(principle used in the Internet protocol ARP [Address Resolution Protocol])
New approaches are necessary, e.g. identifiers for an resource
But: inefficient in large systems
More efficient: using multicast for location
Entity ID
But: you need to build up and to know the multicast group
a) Direct, single level mapping between names and addresses
b) Two-level mapping using identifiers. Needs a location service to resolve identifiers
45
Chapter 3: Naming
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Chapter 3: Naming
46
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Forwarding Pointers (1)
Forwarding Pointers (2)
More popular approach
for location:
Forwarding Pointers
old location
Principle:
• A moving entity leaves
behind a reference to
the new location
• Client follows the chain
of forwarding pointers
When an object moves it leaves behind a proxy having the new location
reference
But...
Long chains make the location process very expensive
Intermediate nodes have to store all pointers as long as needed
Broken links prohibit location
Short chains and robust pointers are needed
Chapter 3: Naming
new location
Location is transparent for the client, request is forwarded along the chain
Object sends back its new location to the caller, the forwarding pointer is
redirected
47
Chapter 3: Naming
48
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Home-Based Approaches
Hierarchical Approaches
Extending the home-based approach to several layers
Network is divided into domains, sub-domains, ... (similar to DNS)
Leaf domains: local area network, cell in a mobile telephone network, ...
• Popular approach for large-scale networks: home location
• principle of Mobile IP
• But: increase in communication latency, fixed home location
Chapter 3: Naming
An entity located in domain D is represented by a location record in directory
node dir(D)
Location records on higher hierarchies point to next sub-domain directory node
49
Chapter 3: Naming
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Information Stored in Nodes
Location Lookup
• Entities may have multiple addresses (e.g. replication)
• Higher-level node stores pointers to each location
• Scalability problem: root node has to store all information…
Chapter 3: Naming
50
51
•
•
•
Looking up a location in a hierarchically organized location service
Client contacts directory node in its own domain
Go up hierarchy to the first directory node holding the information
Chapter 3: Naming
52
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Location Update
Pointer Caches
• Caching can be used to store locations of 'stable' nodes
Install a replicate in a new domain: new pointers have to be set
• Location caching: inefficient lookup with each location change
• Pointer caching: Caching a reference to a directory node (dir(D)) of the lowest-level
domain in which an entity (E) will reside most of the time.
a) An insert request is forwarded to the first node that knows about entity E.
b) A chain of forwarding pointers to the leaf node is created.
Similar operation: deletion of pointers
Chapter 3: Naming
53
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Chapter 3: Naming
54
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Invalidation of Pointer Caches
Scalability Issues
• Root directory node becomes bottleneck
• Solution: placing sub-nodes of a partitioned root across the network
• Spread sub-nodes uniformly; but… new scalability problems: which node
to give responsibility???
• A cache entry that needs to be invalidated because it returns a non-local address,
while such an address is available.
Chapter 3: Naming
55
Chapter 3: Naming
56
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
The Problem of Unreferenced Objects
•
•
•
•
Solution: Reference Counting
• Simply count the references pointing to you
• Problem: unreliable communication
Process P expects to get an acknowledgement when it increases the
skeletons counter
Acknowledgement can get lost
P sends the increase message again
• Necessary to detect duplicates
Problem with forwarding pointers: unreferenced object
Garbage collection for remote objects: hidden from clients and objects itself
How many proxies point to another one?
Reference graph
Chapter 3: Naming
57
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Chapter 3: Naming
58
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Reference Counting
Advanced Referencing Counting
Weighted reference counting: each object has
Another problem: copying a remote reference to another process
• A fixed total weight
• A partial weight, initialised with the total weight
Creating a remote reference causes transmitting half the partial weight to the
referencer
a) Copying a reference to another process and incrementing the counter too late
b) Solution by using acknowledgements
One more problem: performance problems in large-scale systems by communication
overhead
Chapter 3: Naming
59
a) The initial assignment of weights in weighted reference counting
b) Weight assignment when creating a new reference.
Chapter 3: Naming
60
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Weighted Referencing Counting
Weighted Referencing Counting
• Problem: the partial weight of the remote object can become zero. What is with
former objects which want to make a reference?
• Make use of indirections when partial weight reaches one
• Copying a reference to P2 causes P1 in transmitting half the weight
• Deleting a reference causes the remote object to subtract the weight of the
referencer from its total weight
• When the total weight becomes zero, there are no more references
Chapter 3: Naming
• When copying the reference to P2, P1 creates a local skeleton with some total
weight and the same partial weight
• Then transmitting half the partial weight to P2
61
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Chapter 3: Naming
62
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Generation Referencing Counting
And much simpler...
• Alternative to the use of indirections: generation reference counting
Reference listing
• Skeleton keeps track of the proxies having a reference to it, i.e. it has a list of all
these proxies (reference list) instead of a counter
No problems with duplicated increments
Easy to keep the list consistent in case of process failures
Problem: copying a reference and deleting it too early (as in reference
counting)
• Associate a generation and a copy counter with each referencing process
• Both counters are initialised with zero
• When copying a reference, the copy counter is increased; the new referencer
becomes the next generation compared to the old one
• Skeleton maintains the numbers of outstanding copies for each generation; in case
of a decrement request, the counter for the referencer's generation is decreased.
The copies of the referencer is added to the next generation. If all generation
entries are zero, there are no more references
Chapter 3: Naming
63
Main drawback: bad scalability in case of many references
• Used in Java RMI
Chapter 3: Naming
64
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Tracing-based Garbage Collection
Tracing in Groups
How can isolated referencer groups be located?
1. Marking the skeletons
Tracing all entities in a distributed system
• Hard mark: reachable from a root object, a hard marked proxy, or an external object
Removing all non-reachable entities
• Soft mark: only reachable from inside the group
Scalability problems! → only consider groups
of processes
2. Propagating marks to proxies
Chapter 3: Naming
3. Repeating these steps till no more change is made
65
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Chapter 3: Naming
66
Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Tracing in Groups
Conclusion
If there are no more changes: deletion of soft-marked objects
Different concepts:
• Naming Services for mapping of logical names to addresses
• Directory Services for searching addresses by describing the needed object
• Discovery Services as a name database in “dynamic” networks
• Location Services for supporting moving objects
• Some close relations to file systems and reference counting
What is the best concept?
There is no general answer – it always depends on the application
• reduction of objects in groups
• after that: analysis of intergroup references on higher-level groups
Chapter 3: Naming
67
Chapter 3: Naming
68