Chapter 3, 4, and 5 Distributed Systems Concepts PDF

Chapter 3 - Processes Introduction § communication takes place between processes § a process is a program in execution § from OS perspective, management and scheduling of processes is important § other important issues arise in distributed systems § multithreading to enhance performance...

Chapter 3 - Processes Introduction § communication takes place between processes § a process is a program in execution § from OS perspective, management and scheduling of processes is important § other important issues arise in distributed systems § multithreading to enhance performance § how are clients and servers organized § process or code migration to achieve scalability and to dynamically configure clients and servers 1  3.1 Threads and their Implementation § threads can be used in both distributed and nondistributed systems § Threads in Nondistributed Systems § a process has an address space (containing program text and data) and a single thread of control, as well as other resources such as open files, child processes, accounting information, etc. Process 1 Process 2 Process 3 three processes each with one thread one process with three threads 2 § each thread has its own program counter, registers, stack, and state; but all threads of a process share address space, global variables and other resources such as open files, etc. 3 § Threads take turns in running § Threads allow multiple executions to take place in the same process environment, called multithreading § Thread Usage – Why do we need threads? 1. Simplifying the programming model: since many activities are going on at once 2. They are easier to create and destroy than processes since they do not have any resources attached to them 3. Performance improves by overlapping activities if there is too much I/O; i.e., to avoid blocking when waiting for input or doing calculations, say in a spreadsheet 4. Real parallelism is possible in a multiprocessor system § e.g., a wordprocessor has different parts; parts for § interacting with the user § formatting the page as soon as changes are made § timed savings (for auto recovery) § spelling and grammar checking, etc 4 § In nondistributed systems, threads can be used with shared data instead of processes to avoid context switching overhead in intercrosses communication (IPC) context switching as the result of IPC 5 § Thread Implementation § threads are usually provided in the form of a thread package § the package contains operations to create and destroy a thread, operations on synchronization variables such as mutexes and condition variables § two approaches of constructing a thread package a. construct a thread library that is executed entirely in user mode (the OS is not aware of threads) § cheap to create and destroy threads; just allocate and free memory § context switching can be done using few instructions; store and reload only CPU register values § disadv: invocation of a blocking system call will block the entire process to which the thread belongs and all other threads in that process b. implement them in the OS’s kernel § let the kernel be aware of threads and schedule them § expensive for thread operations such as creation and deletion since each requires a system call 6 § solution: use a hybrid form of user-level and kernel-level threads, called lightweight process (LWP) § a LWP runs in the context of a single (heavy-weight) process, and there can be several LWPs per process § the system also offers a user-level thread package for some operations such as creating and destroying threads, for thread synchronization (mutexes and condition variables) § the thread package can be shared by multiple LWPs combining kernel-level lightweight processes and user-level threads 7 § Threads in Distributed Systems § Multithreaded Clients § consider a Web browser; fetching different parts of a page can be implemented as a separate thread, each opening its own TCP/IP connection to the server or to separate and replicated servers § each can display the results as it gets its part of the page § Multithreaded Servers § servers can be constructed in three ways a. single-threaded process § it gets a request, examines it, carries it out to completion before getting the next request § the server is idle while waiting for disk read, i.e., system calls are blocking 8 b. threads § threads are more important for implementing servers § e.g., a file server § the dispatcher(sender) thread reads incoming requests for a file operation from clients and passes it to an idle worker thread § the worker thread performs a blocking disk read; in which case another thread may continue, say the dispatcher or another worker thread a multithreaded server organized in a dispatcher/worker model 9  c. finite-state machine § if threads are not available § it gets a request, examines it, tries to fulfill the request from cache, else sends a request to the file system; but instead of blocking it records the state of the current request and proceeds to the next request § Summary Model Characteristics Single-threaded process No parallelism, blocking system calls Parallelism, blocking system calls Threads (thread only) Finite-state machine Parallelism, nonblocking system calls three ways to construct a server 10  3.2 Anatomy of Clients § Two issues: user interfaces and client-side software for distribution transparency a. User Interfaces § to create a convenient environment for the interaction of a human user and a remote server; e.g. mobile phones with simple displays and a set of keys § GUIs are most commonly used § The X Window System (or simply X) § it has the X kernel: the part of the OS that controls the terminal (monitor, keyboard, pointing device like a mouse) and is hardware dependent § contains all terminal-specific device drivers through the library called xlib 11 the basic organization of the X Window System 12 b. Client-Side Software for Distribution Transparency § in addition to the user interface, parts of the processing and data level in a client-server application are executed at the client side § an example is embedded client software for ATMs, cash registers, etc. § moreover, client software can also include components to achieve distribution transparency § e.g., replication transparency § assume a distributed system with replicated servers; the client proxy can send requests to each replica and a client side software can transparently collect all responses and passes a single return value to the client application 13  transparent replication of a server using a client-side solution § access transparency and failure transparency can also be achieved using client-side software 14  3.3 Servers and design issues 3.3.1 General Design Issues § How to organize servers? § Where do clients contact a server? § Whether and how a server can be interrupted § Whether or not the server is stateless a. How to organize servers? § Iterative server § the server itself handles the request and returns the result § Concurrent server § it passes a request to a separate process or thread and waits for the next incoming request; e.g., a multithreaded server; or by forking a new process as is done in Unix 15 b. Where do clients contact a server? § using endpoints or ports at the machine where the server is running where each server listens to a specific endpoint § how do clients know the endpoint of a service? § globally assign endpoints for well-known services; e.g. FTP is on TCP port 21, HTTP is on TCP port 80 § for services that do not require preassigned endpoints, it can be dynamically assigned by the local OS Ø IANA (Internet Assigned Numbers Authority) Ranges § IANA divided the port numbers into three ranges § Well-known ports: assigned and controlled by IANA for standard services, e.g., DNS uses port 53 16 § Registered ports: are not assigned and controlled by IANA; can only be registered with IANA to prevent duplication e.g., MySQL uses port 3306 § Dynamic ports or ephemeral ports : neither controlled nor registered by IANA § how can the client know this endpoint? two approaches i. have a daemon running and listening to a well-known endpoint; it keeps track of all endpoints of services on the collocated server § the client will first contact the daemon which provides it with the endpoint, and then the client contacts the specific server 17  Client-to-server binding using a daemon ii. use a superserver (as in UNIX) that listens to all endpoints and then forks a process to take care of the request; this is instead of having a lot of servers running simultaneously and most of them idle Client-to-Server binding using a superserver 18 c. Whether and how a server can be interrupted § for instance, a user may want to interrupt a file transfer, may be it was the wrong file § let the client exit the client application; this will break the connection to the server; the server will tear down the connection assuming that the client had crashed or § let the client send out-of-bound data, data to be processed by the server before any other data from the client; the server may listen on a separate control endpoint; or send it on the same connection as urgent data as is in TCP d. Whether or not the server is stateless § a stateless server does not keep information on the state of its clients; for instance a Web server § soft state: a server promises to maintain state for a limited time; e.g., to keep a client informed about updates; after the time expires, the client has to poll 19  § a stateful server maintains information about its clients; for instance a file server that allows a client to keep a local copy of a file and can make update operations 3.3.2 Server Clusters § a server cluster is a collection of machines connected through a network (normally a LAN with high bandwidth and low latency) where each machine runs one or more servers § it is logically organized into three tiers 20  the general organization of a three-tiered server cluster § Distributed Servers § the problem with a server cluster is when the logical switch (single access point) fails making the cluster unavailable § hence, several access points can be provided where the addresses are publicly available leading to a distributed server § e.g., the DNS can return several addresses for the same host name 21  3.4 Code Migration § so far, communication was concerned on passing data § we may pass programs, even while running and in heterogeneous systems § code migration also involves moving data as well: when a program migrates while running, its status, pending signals, and other environment variables such as the stack and the program counter also have to be moved § Reasons for Migrating Code § to improve performance; move processes from heavily-loaded to lightly-loaded machines (load balancing) § to reduce communication: move a client application that performs many database operations to a server if the database resides on the server; then send only results to the client § to exploit parallelism (for nonparallel programs): e.g., copies of a mobile program (a crawler as is called in search engines) moving from site to site searching the Web 22 § to have flexibility by dynamically configuring distributed systems: instead of having a multitiered client-server application deciding in advance which parts of a program are to be run where the principle of dynamically configuring a client to communicate to a server; the client first fetches the necessary software, and then invokes the server 23 § Models for Code Migration § a process consists of three segments: code segment (set of instructions), resource segment (references to external resources such as files, printers,...), and execution segment (to store the current execution state of a process such as private data, the stack, the program counter) § Weak Mobility § transfer only the code segment and may be some initialization data in this case a program always starts from its initial stage, e.g. Java Applets § execution can be by the target process (in its own address space like in Java Applets) or by a separate process § Strong Mobility § transfer code and execution segments; helps to migrate a process in execution § can also be supported by remote cloning; having an exact copy of the original process and running on a different machine; executed in parallel to the original process; UNIX does this by forking a child process 24  Chapter 4 - Communication Introduction § Interprocess communication is at the heart of all distributed systems § communication in distributed systems is based on message passing as offered by the underlying network as opposed to using shared memory § modern distributed systems consist of thousands of processes scattered across an unreliable network such as the Internet § unless the primitive communication facilities of the network are replaced by more advanced ones, development of large scale Distributed Systems becomes extremely difficult 1  Objectives of the Chapter § review of how processes communicate in a network (the rules or the protocols) and their structures § introduce the four widely used communication models for distributed systems: § Remote Procedure Call (RPC) § Message-Oriented Middleware (MOM) § Stream-Oriented Communication § Multicast Communication 2  4.1 Network Protocols and Standards § a protocol is a set of rules that governs data communications § a protocol defines what is communicated, how it is communicated, and when it is communicated § for instance, for one computer to send a message to another computer, the first computer must perform the following general steps § break the data into small sections called packets § add addressing information to the packets identifying the source and destination computers § deliver the data to the network interface card for transmission over the network 3 § the receiving computer must perform the same steps, but in reverse order § accept the data from the NIC § remove transmitting information that was added by the transmitting computer § reassemble the packets of data into the original message § the key elements of a protocol are syntax, semantics, and timing § syntax: refers to the structure or format of the data § semantics: refers to the meaning of each section of bits § timing: refers to when data should be sent and how fast they can be sent § functions of protocols § each device must perform the same steps the same way so that the data will arrive and reassemble properly; if one device uses a protocol with different steps, the two devices will not be able to communicate with each other 4 § Protocols in a layered architecture § protocols that work together to provide a layer or layers of the model are known as a protocol stack or protocol suite, e.g. TCP/IP § each layer handles a different part of the communications process and has its own protocol § Data Communication Standards § standards are essential for interoperability § data communication standards fall into two categories § De facto standards: that have not been approved by an organized body; mostly set by manufacturers § De jure standards: those legislated by an officially recognized body such as ISO, ITU, ANSI, IEEE 5 Network (Reference) Models § Layers and Services § within a single machine, each layer uses the services immediately below it and provides services for the layer immediately above it § between machines, layer x on one machine communicates with layer x on another machine § Two important network models or architectures § The ISO OSI (Open Systems Interconnection) Reference Model § The TCP/IP Reference Model a. The OSI Reference Model § consists of 7 layers § Open – to connect open systems or systems that are open for communication with other systems 6 layers, interfaces, and protocols in the OSI model 7  Media (lower) Layers § Physical: Physical characteristics of the media § Data Link: Reliable data delivery across the link § Network: Managing connections across the network or routing § Transport: End-to-end connection and reliability (handles lost packets); TCP (connection-oriented), UDP (connectionless), etc. § Session: Managing session between applications (dialog control and synchronization); rarely supported § Presentation: Data presentation to applications; concerned with the syntax and semantics of the information transmitted § Application: Network services to applications; contains protocols that are commonly needed by users; FTP, HTTP, SMTP,... trailer Host (upper) Layers 8 a typical message as it appears on the network 9 b. The TCP/IP Reference Model § TCP/IP - Transmission Control Protocol/Internet Protocol § used by ARPANET and its successor the Internet § design goals § the ability to connect multiple networks (internetworking) in a seamless way § the network should be able to survive loss of subnet hardware, i.e., the connection must remain intact as long as the source and destination machines are properly functioning § flexible architecture to accommodate requirements of different applications - ranging from transferring files to real-time speech transmission § these requirements led to the choice of a packet-switching network based on a connectionless internetwork layer § has 4 (or 5 depending on how you see it) layers: Application, Transport, Internet (Internetwork), Host-to- network (some split it into Physical and Data Link) 10 § OSI and TCP/IP Layers Correspondence 11 § Layers involved in various hosts (TCP/IP) § when a message is sent from device A to device B, it may pass through many intermediate nodes § the intermediate nodes usually involve the first three layers 12 § Middleware Protocols § a middleware is an application that contains general-purpose protocols to provide services § example of middleware services § authentication and authorization services § distributed transactions (commit protocols; locking mechanisms) - see later in Chapter 7 § middleware communication protocols (calling a procedure or invoking an object remotely, synchronizing streams for real-time data, multicast services) - see later in this Chapter § hence an adapted reference model for networked communications is required 13 an adapted reference model for networked communication 14  4.2 Remote Procedure Call § the first distributed systems were based on explicit message exchange between processes through the use of explicit send and receive procedures; but do not allow access transparency § in 1984, Birrel and Nelson introduced a different way of handling communication: RPC § it allows a program to call a procedure located on another machine § simple and elegant, but there are implementation problems § the calling and called procedures run in different address spaces § parameters and results have to be exchanged; what if the machines are not identical? § what happens if both machines crash? 15 § Conventional Procedure Call, i.e., on a single machine § e.g. count = read (fd, buf, bytes); a C like statement, where fd is an integer indicating a file buf is an array of characters into which data are read bytes is the number of bytes to be read Stack pointer Stack pointer parameter passing in a local procedure the stack while the called call: the stack before the call to read procedure is active § parameters can be call-by-value (fd and bytes) or call-by reference (buf) or in some languages call-by-copy/restore 16 § Client and Server Stubs § RPC would like to make a remote procedure call look the same as a local one; it should be transparent, i.e., the calling procedure should not know that the called procedure is executing on a different machine or vice versa principle of RPC between a client and server program § when a program is compiled, it uses different versions of library functions called client stubs § a server stub is the server-side equivalent of a client stub 17 § Steps of a Remote Procedure Call 1. Client procedure calls client stub in the normal way 2. Client stub builds a message and calls the local OS (packing parameters into a message is called parameter marshaling) 3. Client's OS sends the message to the remote OS 4. Remote OS gives the message to the server stub 5. Server stub unpacks the parameters and calls the server 6. Server does the work and returns the result to the stub 7. Server stub packs it in a message and calls the local OS 8. Server's OS sends the message to the client's OS 9. Client's OS gives the message to the client stub 10. Stub unpacks the result and returns to client § hence, for the client remote services are accessed by making ordinary (local) procedure calls; not by calling send and receive 18 § Parameter Passing 1. Passing Value Parameters § e.g., consider a remote procedure add(i, j), where i and j are integer parameters steps involved in doing remote computation through RPC The above discussion applies if the server and the client machines are identical but that is not the case in large distributed systems 19 2. Passing Reference Parameters § assume the parameter is a pointer to an array § copy the array into the message and send it to the server § the server stub can then call the server with a pointer to this array § the server then makes any changes to the array and sends it back to the client stub which copies it to the client § this is in effect call-by-copy/restore § optimization of the method § one of the copy operations can be eliminated if the stub knows whether the parameter is input or output to the server § if it is an input to the server (e.g., in a call to write), it need not be copied back § if it is an output, it need not be sent over in the first place; only send the size § the above procedure can handle pointers to simple arrays and structures, but difficult to generalize it to an arbitrary data structure 20 § Parameter Specification and Stub Generation § the caller and the callee need to use the same protocol (format of messages) and the same steps; with such rules the client and server stubs can assemble, communicate, and interpret messages correctly § consider the following example; the procedure foobar has 3 parameters: a character, a floating point number, and an array of 5 integers § assume a word is 4 bytes § one possibility is to transmit the character in the rightmost byte, a float as a whole word, and an array as a group of words equal to the array length preceded by a word giving the length § this way both client stub and server stub can understand outgoing and incoming the corresponding messag messages 21 Asynchronous RPC § A shortcoming of the original model: no need of blocking for the client in some cases § two cases 1. if there is no result to be returned § e.g., inserting records in a database,... § the server immediately sends an ack promising that it will carryout the request § the client can now proceed without blocking a) the interconnection between client and server in a traditional RPC b) the interaction using asynchronous RPC 22 2. if the result can be collected later § e.g., prefetching network addresses of a set of hosts,... § the server immediately sends an ack promising that it will carryout the request § the client can now proceed without blocking § the server later sends the result a client and server interacting through two asynchronous RPCs 23  § the above method combines two asynchronous RPCs and is sometimes called deferred synchronous RPC § variants of asynchronous RPC § let the client continue without waiting even for an ack, called one-way RPC § problem: if reliability of communication is not guaranteed 24 § DCE (Distributed Computing Environment) RPC § a middleware and an example RPC system developed by OSF (Open Software Foundation), now The Open Group § it is designed to execute as a layer of abstraction between existing OSs and distributed applications § The Open Group sells the source code and vendor integrate it into their systems § it uses the client-server programming model and communication is by means of RPCs § services § distributed file service: a worldwide file system that provides a transparent way of accessing files § directory service: to keep track of the location of all resources in the system (machines, printers, data, servers,...); a process can ask for a resource without knowing its location § security service: for protecting resources; access is only through authorization § distributed time service: to maintain clocks on different machines synchronized (clock synchronization is covered in Chapter 6) 25  4.3 Message-Oriented Communication § RPCs are not adequate for all distributed system applications § the provision of access transparency may be good but they have semantics that is not adequate for all applications § example problems § they assume that the receiving side is running at the time of communication § a client is blocked until its request has been processed 26 § Communication can be § persistent or transient § asynchronous or synchronous § persistent: a message that has been submitted for transmission is stored by the communication system as long as it takes to deliver it to the receiver § e.g., email delivery, snail mail delivery § transient: a message that has been submitted for transmission is stored by the communication system only as long as the sending and receiving applications are executing § asynchronous: a sender continues immediately after it has submitted its message for transmission § synchronous: the sender is blocked until its message is stored in a local buffer at the receiving host or delivered to the receiver 27  4.4 Stream-Oriented Communication § until now, we focused on exchanging independent and complete units of information § time has no effect on correctness; a system can be slow or fast § however, there are communications where time has a critical role § Multimedia § media § storage, transmission, interchange, presentation, representation and perception of different data types: § text, graphics, images, voice, audio, video, animation,... § movie: video + audio + … § multimedia: handling of a variety of representation media § end user pull § information overload and starvation § technology push § emerging technology to integrate media 28 § Types of Media § two types § discrete media: text, executable code, graphics, images; temporal relationships between data items are not fundamental to correctly interpret the data § continuous media: video, audio, animation; temporal relationships between data items are fundamental to correctly interpret the data § a data stream is a sequence of data units and can be applied to discrete as well as continuous media § stream-oriented communication provides facilities for the exchange of time-dependent information (continuous media) such as audio and video streams 29 § timing in transmission modes § asynchronous transmission mode: data items are transmitted one after the other, but no timing constraints; e.g. text transfer § synchronous transmission mode: a maximum end-to-end delay defined for each data unit; it is possible that data can be transmitted faster than the maximum delay, but not slower § isochronous transmission mode: maximum and minimum end-to-end delay are defined; also called bounded delay jitter; applicable for distributed multimedia systems § a continuous data stream can be simple or complex § simple stream: consists of a single sequence of data; e.g., mono audio, video only (only visual frames) § complex stream: consists of several related simple streams, called substreams, that must be synchronized; e.g., stereo audio, video consisting of audio and video (may also contain subtitles, translation to other languages,...) 30 § Quality of Service (QoS) § QoS requirements describe what is needed from the underlying distributed system and network to ensure acceptable delivery; e.g. viewing experience of a user § it refers to flow characteristics § Reliability § lack of reliability means losing a packet or acknowledgement, which entails retransmission for some media types § Delay § source-to-destination delay § Bandwidth § requirements of applications 31  § Jitter § the variation in the packet arrival times belonging to the same flow (a) high jitter (b) low jitter § Techniques to improve Network QoS (some are useful for multimedia) § the easiest (but impractical) solution: overprovisioning - provide enough router capacity, buffer space, and bandwidth for all packets; very expensive § five common methods buffering(client side), traffic shaping (Server side), scheduling, admission control and resource reservation 32  4.5 Multicast Communication § multicasting: delivery of data from one host to many destinations; for instance for multimedia applications § a one-to-many relationship 1. Application-Level Multicasting § nodes are organized into an overlay network and information is disseminated to its members (routers are not involved as in network-level routing) § how to construct the overlay network § nodes organize themselves as a tree with a unique path between two pairs of nodes or § nodes organize into a mesh network and there will be multiple paths between two nodes; adv: robust 2. Gossip-Based Data Transmission § use epidemic protocols where information is propagated among a collection of nodes without a coordinator § for details read pages 166-174 33 Chapter 5 - Naming  Introduction § names play an important role to: § share resources § uniquely identify entities § refer to locations § etc. § an important issue is that a name can be resolved to the entity it refers to § to resolve names, it is necessary to implement a naming system § in a distributed system, the implementation of a naming system is itself often distributed, unlike in nondistributed systems § efficiency and scalability of the naming system are the main issues 2  Objectives of the Chapter § we discuss how § human friendly names are organized and implemented; e.g., those for file systems and the WWW § classes on naming systems § flat naming § structured naming, and § attribute-based naming 3  5.1 Names, Identifiers, and Addresses § a name in a distributed system is a string of bits or characters that is used to refer to an entity § an entity is anything; e.g., resources such as hosts, printers, disks, files, objects, processes, users, Web pages,... § entities can be operated on; e.g., a resource such as a printer offers an interface containing operations for printing a document, requesting the status of a job,... § to operate on an entity, it is necessary to access it through its access point, itself an entity (special) 4 § access point § the name of an access point is called an address (such as IP address and port number as used by the transport layer) § the address of the access point of an entity is also referred to as the address of the entity § an entity can have more than one access point (similar to accessing an individual through different telephone numbers) § an entity may change its access point in the course of time (e.g., a mobile computer getting a new IP address as it moves) 5 § an address is a special kind of name § it refers to at most one entity § each entity is referred by at most one address; even when replicated such as in Web pages § an entity may change an access point, or an access point may be reassigned to a different entity (like telephone numbers in offices) § separating the name of an entity and its address makes it easier and more flexible; such a name is called location independent § there are also other types of names that uniquely identify an entity; in any case an identifier is a name with the following properties § it refers to at most one entity § each entity is referred by at most one identifier § it always refers to the same entity (never reused) § identifiers allow us to unambiguously refer to an entity 6 § examples § name of an FTP server (entity) § URL of the FTP server § address of the FTP server § IP number: port number § the address of the FTP server may change § there are three classes on naming systems: flat naming, structured naming, and attribute-based naming 7  5.2 Flat Naming § a name is a sequence of characters without structure; like human names? may be if it is not Ethiopian name! § difficult to be used in a large system since it must be centrally controlled to avoid duplication § how are flat names resolved § name resolution: mapping a name to an address or an address to a name is called name-address resolution § possible solutions: simple, home-based approaches, and hierarchical approaches 8 1. Simple Solutions n two solutions for LANs: Broadcasting and Multicasting, and Forwarding Pointers a. Broadcasting and Multicasting § a computer that wants to access another computer for which it knows its IP address broadcasts this address § the owner responds by sending its Ethernet address § used by ARP (Address Resolution Protocol) in the Internet to find the data link address (MAC address) of a machine § broadcasting is inefficient when the network grows (wastage of bandwidth and too much interruption to other machines) § multicasting is better when the network grows - send only to a restricted group of hosts § multicasting can also be used to locate the nearest replica - choose the one whose reply comes in first 9 b. Forwarding Pointers § how to look mobile entities § when an entity moves from A to B, it leaves behind a reference to its new location § advantage § simple: as soon as the first name is located using traditional naming service, the chain of forwarding pointers can be used to find the current address § drawbacks § the chain can be too long - locating becomes expensive § all the intermediary locations in a chain have to maintain their pointers § vulnerability if links are broken § hence, making sure that chains are short and that forwarding pointers are robust is an important issue 10 2. Home-Based Approaches § broadcasting and multicasting have scalability problems; performance problems and broken links are problems in forwarding pointers § a home location keeps track of the current location of an entity; often it is the place where an entity was created § it is a two-tiered approach § an example where it is used in Mobile IP § each mobile host uses a fixed IP address § all communication to that IP address is initially directly sent to the host’s home agent located on the LAN corresponding to the network address contained in the mobile host’s IP address § whenever the mobile host moves to another network, it requests a temporary address in the new network (called care-of-address) and informs the new address to the home agent 11 § when the home agent receives a message for the mobile host it forwards it to its new address and also informs the sender the host’s current location for sending other packets home-based approach: the principle of Mobile IP 12 § problems: § creates communication latency § the host is unreachable if the home does no more exist (permanently changed); the solution is to register the home at a traditional name service 13 3. Hierarchical Approaches § a generalization of the two-tiered approach into multiple layers § a network is divided into a collection of domains, similar to DNS § a single top-level domain spans the entire network § each domain can be subdivided into multiple, smaller domains § the lowest-level domain is called a leaf domain; typically a LAN § each domain D has an associated directory node dir(D) that keeps track of the entities in that domain leading to a tree of directory nodes § the root (directory) node knows about all entities 14 hierarchical organization of a location service into domains, each having an associated directory node 15  5.3 Structured Naming § flat names are not convenient for humans § Name Spaces § names are organized into a name space § each name is made of several parts; the first may define the nature of the organization, the second the name, the third departments,... § the authority to assign and control the name spaces can be decentralized where a central authority assigns only the first two parts § a name space is generally organized as a labeled, directed graph with two types of nodes § leaf node: represents the named entity and stores information such as its address or the state of that entity § directory node: a special entity that has a number of outgoing edges, each labeled with a name § each node in a naming graph is considered as another entity with an identifier 16  a general naming graph with a single root node, no § a directory node stores a table in which an outgoing edge is represented as a pair (edge label, node identifier), called a directory table § each path in a naming graph can be referred to by the sequence of labels corresponding to the edges of the path and the first node in the path, such as N:, where N refers to the first node in the path 17 § such a sequence is called a path name § if the first node is the root of the naming graph, it is called an absolute path name; otherwise it is a relative path name § instead of the path name n0:, we often use its string representation /home/steen/mbox § there may also be several paths leading to the same node, e.g., node n5 can be represented as /keys or /home/steen/keys § although the above naming graph is directed acyclic graph (a node can have more than one incoming edge but is not permitted to have a cycle), the common way is to use a tree (hierarchical) with a single root (as is used in file systems) § in a tree structure, each node except the root has exactly one incoming edge; the root has no incoming edges Ü each node also has exactly one associated (absolute) path name 18 § The Implementation of a Name Space § a name space forms the heart of a naming service § a naming service allows users and processes to add, remove, and lookup names § a naming service is implemented by name servers § for a distributed system on a single LAN, a single server might suffice; for a large-scale distributed system the implementation of a name space is distributed over multiple name servers § Name Space Distribution § in large scale distributed systems, it is necessary to distribute the name service over multiple name servers, usually organized hierarchically § a name service can be partitioned into logical layers § the following three layers can be distinguished (according to Cheriton and Mann) 19 § global layer § formed by highest level nodes (root node and nodes close to it or its children) § nodes on this layer are characterized by their stability, i.e., directory tables are rarely changed § they may represent organizations, groups of organizations,..., where names are stored in the name space § administrational layer § groups of entities that belong to the same organization or administrational unit, e.g., departments § relatively stable § managerial layer § nodes that may change regularly, e.g., nodes representing hosts of a LAN, shared files such as libraries or binaries, … § nodes are managed not only by system administrators, but also by end users 20 an example partitioning of the DNS name space, including Internet- accessible files, into three layers 21 § the name space is divided into nonoverlapping parts, called zones in DNS § a zone is a part of the name space that is implemented by a separate name server § some requirements of servers at different layers § performance (responsiveness to lookups), availability (failure rate), etc. § high availability is critical for the global layer, since name resolution cannot proceed beyond the failing server; it is also important at the administrational layer for clients in the same organization § performance is very important in the lowest layer, since results of lookups can be cached and used due to the relative stability of the higher layers § they may be enhanced by client side caching (global and administrational layers since names do not change often) and replication; they create implementation problems since they may introduce inconsistency problems (see Chapter 7) 22 Item Global Administrational Managerial Geographical scale of network Worldwide Organization Department Total number of nodes Few Many Vast numbers Responsiveness to lookups Seconds Milliseconds Immediate Update propagation Lazy Immediate Immediate Availability requirement Very High High low Number of replicas Many None or few None Is client-side caching applied? Yes Yes Sometimes a comparison between name servers for implementing nodes from a large-scale name space partitioned into a global layer, an administrational layer, and a managerial layer 23  5.4 Attribute-Based Naming § flat naming: provides a unique and location-independent way of referring entities § structured naming: also provides a unique and location- independent way of referring entities as well as human-friendly names § but do not allow searching entities by giving a description of an entity § each entity is assumed to have a collection of attributes that say something about the entity § then a user can search an entity by specifying (attribute, value) pairs known attribute-based naming § Directory Services § attribute-based naming systems are also called directory services 24  § how are resources described? one possibility is to use RDF (Resource Description Framework) that uses triplets consisting of a subject, a predicate, and an object § e.g., (person, name, Alice) to describe a resource Person whose Name is Alice § Hierarchical Implementations: LDAP § distributed directory services are implemented by combining structured naming with attribute-based naming § e.g., Microsoft’s Active directory service § such systems rely on the lightweight directory access protocol or LDAP which is derived from OSI’s X.500 directory service § a LADP directory service consists of a number of records called directory entries (attribute, value) pairs, similar to a resource record in DNS; could be single- or multiple-valued (e.g., Mail_Servers) 25 Attribute Abbr. Value Country C NL Locality L Amsterdam Organization O Vrije Universiteit OrganizationalUnit OU Comp. Sc. CommonName CN Main server Mail_Servers -- 137.37.20.3, 130.37.24.6,137.37.20.10 FTP_Server -- 130.37.20.20 WWW_Server -- 130.37.20.20 a simple example of an LDAP directory entry using LDAP naming conventions to identify the network addresses of some servers 26 § the collection of all directory entries is called a Directory Information Base (DIB) § each record is uniquely named so that it can be looked up § each naming attribute is called a Relative Distinguished Name (RDN); the first 5 entries above § a globally unique name is formed using abbreviations of naming attributes, e.g., /C=NL/O=Vrije Universiteit/OU=Comp. Sc. § listing RDNs in sequence leads to a hierarchy of the collection of directory entries, called a Directory Information Tree (DIT) § a DIT forms the naming graph of an LDAP directory service where each node represents a directory entry 27 § node N corresponds to the directory entry shown earlier; it also acts as a parent of other directory entries that have an additional attribute, Host_Name; such entries may be used to represent hosts part of the directory information tree 28 Attribute Value Attribute Value Country NL Country NL Locality Amsterdam Locality Amsterdam Organization Vrije Universiteit Organization Vrije Universiteit OrganizationalUnit Comp. Sc. OrganizationalUnit Comp. Sc. CommonName Main server CommonName Main server Host_Name star Host_Name zephyr Host_Address 192.31.231.42 Host_Address 137.37.20.10 two directory entries having Host_Name as RDN § read pages 222 - 226 about Decentralized Implementations 29