4 - Naming Flashcards

1
Q

What is a Name?

A

Used to denote entities in a distributed system
Bits or letters

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Entity

A

Resources
Eg: Printer, host, hard drive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Address

A

Access point of an entity
Eg: Host address and port

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Why have names different from addresses?

A

Different names for different entities with the same address
One name to represent several addresses
Addresses could change
Addresses are not user friendly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Real Identifier

A

Refers to at most one entity
Each entity is referred to by at most one identifier
An identifier always refers to the same entity

Eg: MAC address

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Is a phone number a real identifier?

A

No. It can change and be transferred

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the challenges of naming systems?

A

Design and implementation
Resolution of names to addresses

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Give three types of naming systmes

A

Flat (linear)
Structured (hierarchical)
Attribute based

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Flat naming

A

Unstructured names with no information for locatisation of an entity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Flat naming: How would you find an entity?

A

Cached Address
Searching the net (flooding/random walks etc)
Search in structured network (DHT, HLS)
Look up in directories

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

DHT

A

Distributed Hash Table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Flat naming search te chniques

A

Broadcast/multicast
Random Walk
Distributed hash tables
Hierarchical Location Services

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Broadcast/multicast search

A

Send every computer message.
Com,puter connected to entity replies with address

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Disadvantage of broadcast/multicast search

A

Traffic
Unnecessary Requests

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

ARP

A

Address Resolution Protocol

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

ARP: Resolves what?

A

Resolves IP to MAC

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

ARP: Method

A

Broadcast IP to all computers
Computer with IP replies with MAC address

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Random Walk Search

A

Msg to random neighbour until entity is found

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Random Walk disadvantage

A

Might take a long time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Distributed Hash Table Search

A

Use hash function to determine identifier.
Find entity using structure of overlay net

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

DHT Nodes concept

A

Distribute items over set of nodes
Nodes given identifiers
Every item hashed to key which refers to the node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Chord

A

Nodes organised into logical ring

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Chord: VIrtual vs Actual Nodes

A

Acual nodes are storage locations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

CHord: What are actual nodes aware of?

A

their successor (clockwise)
their predecessor (anti-clockwise)
additional nodes for fault tolerance

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Chord Mapping: Virtual node storage

A

Items are assigned to the successor. ie actual node with smallest id >= k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Simple Key Location search

A

Simply go around the ring until node is reached
O(N) hops

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Scalable Key Location search

A

Introduce shortcuts
Every node is provided with a finger table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Finger Table

A

Routing table that has m = log(N) entries i = 1,2, …, m
i-th entry: succ(p+2^(i-1)) where p is the current node

29
Q

Scalable Key lookup

A

key k, current node p

if p < k < FTp, go to FTp(1) + stop.
Otherwise, forward to FTp(j) where FTp(j) <= k < FTp(j+1)

30
Q

HLS

A

Hierarchical Location Services

31
Q

HLS Summary

A

Build a search tree
Divide net into hierarchical domains
Each domain rep by sep dir node

32
Q

HLS not to be confused with..?

A

Do not confuse with Hierarchical naming

This is a flat naming technique

33
Q

HLS: Name resolution

A

Localitity principle:

Start at local leaf node
If node knows E, then follow downward
Else go up

34
Q

Locality: Moved within domain…

A

If entity moved in domain, only update leaf.

35
Q

Locality: Moved to other domain…

A

If moved domain, only update leafs up to first common ancestor.

36
Q

Locality: Replicated to other domain

A

If entity replicated in other domain, update nodes from that domain up to common ancestor

37
Q

How might you avoid searching in HLS?

A

Caching
Forwarding Pointers

38
Q

Forwarding Pointers:

A

When an entity changes locaiton, it leaves a pointer to its new location.

39
Q

Forwarding Pointers: Disadvantages

A

Long chain of pointers fault prone
Latency
Home-based Approaches

40
Q

Forwarding Pointers: Disadv solution

A

When client calls server via forwarding pointer, client stub given new location
Pointer removed when required.

41
Q

Home based approaches to avoiding searches

A

Mobile device has home base which maintains mobile address

42
Q

Home based approach: Problems

A

Latency, home base maintenance.
Overhead if mobile address becomes static.
Poor geographic scalability

43
Q

Structured Naming

A

Hierarchical Name Spaces
Can be split into meaningful parts

44
Q

Structured Naming Examples:

A

Internet Domain,
File path,
phone number with country and area

45
Q

Naming Graph

A

represented as directed graph
- Edge label is name part
- Directory node contains table of (ID,label) pairs
- Leaf represents entity
- Leaf attributes describe entity

46
Q

UNIX: Boot block

A

Load OS into main mem

47
Q

UNIX: Superblock

A

Info about file system: size, free blocks and index nodes

48
Q

UNIX Index Nodes

A

Describes a dir, file or link.
Contains attributes
inode number corresponds to node id in naming graph

49
Q

UNIX: Data Block

A

Actual file data

50
Q

UNIX: Regular File

A

User data or exec. files

51
Q

UNIX: Directory:

A

File that contains list of files including inode

52
Q

UNIX: Name Linking

A

Unix allows hard links. The same path can reference the same entity

53
Q

Symbolic Link

A

A type of alias where it does not directly refer to the entity but instead has the actual path as an attribute

54
Q

Mounting

A

Used to merge name spaces in a transparent way

55
Q

Mounting: Required info

A

Access protocol
Server name
Mounting point

56
Q

Name Space Distribution: DNS

A

DNS is distributed over several systems:

Global: tables rarely change
Admin: Relatively stable
Managerial: Nodes change frequently

57
Q

Iterative Name Resolution

A

Client resolves name step by step contacting servers itself.

Next address to check is provided to client

58
Q

Recursive Name Resolution

A

Client asks name server to resolve.
Name server forwards requests.
Repeats until name server is reached with entity.

59
Q

Iterative vs Recursive

A

Less work by servers - iterative
Better server-side caching - recursive
Lower latency - Recursive
Lower mem usage - Iterative

60
Q

Attribute naming systems

A

Assume; Entities have pairs
Search entities by attributes

61
Q

Resource Description Framework

A

Uniiversal language for describing resources (by relations)/

62
Q

LDAP

A

Lightweight Directory Access Protocol

63
Q

Use of LDAP

A

Accessing and maintaining distributed directory services

64
Q

Main functions of LDAP

A

Update: modifying directory information
Query: searching and comparing directory info
Authentication

65
Q

LDAP Schema

In terms of DNs and RDNs

A

Entries consist of set of attributes
Entries have unique distinguished names (DN) which subset these attributes
Each DN attribute is called a relative distinguished name (RDN)

66
Q

Distributed LDAP Systems: DIT

A

Directory Information Tree can be distributed over multiple servers

67
Q

Distributed LDAP servers:What agent does each have?

A

Each has a Directory Service Agent (DSA)

68
Q

Distributed LDAP clients: What agent?

A

Each has a aDirectory User Agent (DUA) that communicate with DSAs to resolve queries