CS 6378 Advanced Operating Systems, Spring 2005

Project 2 Description

  1. Project 2

(As I mentioned in the class, this project draws heavily on Unix’s (or Sun’s) distributed name server. It is a light weight emulation of that. I encourage you to know more about Sun’s Network Information Service (NIS)).

For project 2, you will be expanding Project 1 and work towards a distributed name server. For the hierarchy, let us assume that the “root” node corresponds to the “.edu” domain. The .edu domain has at least 4 children, representing different universities. Assume that each University has at least 4Departments (“skipping” the intermediate hierarchy of Schools). For instance, Computer Science department in UT Dallas will be having the domain name “cs.utdallas.edu”. A machine in CS department would have a name looking like “machine.cs.utdallas.edu” and IP address of this machine has to be provided by the CS name server (the leaf one in the hierarchy). Each server in the tree (server is a process not a machine) maintains at least 2 databases/tables: say, MachineName-IPaddress mapping and UserName-Password mapping.

Now, the clients/users do NOT form part of the above hierarchy. They just get connected to one of the leaf nodes (the Department level server) to resolve a name and then get disconnected. So the connection is for a query-response session. One question is which server a user connects to. For this, let us say the user has to login first with a user name, password, and a domain name (like you do on Windows). Depending on the domain name, the program should connect to the particular server process (configuration file can be used for DomainName-ServerProcess mapping).It is natural to restrict one user to be logged onto only one domain at any point in time. After login, the user can give queries to know the IP address of different machines (with proper error display for non-existing machine names).

1.1Modifying the Mapping Tables

A Super User(system administrator) should be able to modify the table contents for a domain. E.g., a super user for cs.utdallas.edu will be able to modify/delete the entries for that domain. However, s/he will not be able to modify the contents for other domains such as ee.utdallas.edu. Super user operations are also made from “clients”, i.e., by logging in and carrying out query-response operations. Deletions/modifications should be acknowledged and displayed on the window.

1.2Caching and Time-to-Live

Consider a scenario where you are “connected” to cs.utdallas.edu (i.e., you are a student/staff in that domain and “login” there). Now, you want to resolve/know the IP address of a MachineX.cs.mit.edu. Initially, your request will travel up to the root (“.edu” domain) and get forwarded to cs.mit before getting resolved. The resolved address (i.e., the result) will be “cached” by intermediate name servers such as .edu, utdallas.edu, and cs.utdallas.edu. What this means is the following: if a 2nd user at ee.utdallas.edu wants to know the IP address of MachineX.cs.mit.edu, then the server for utdallas.edu will be answering this query using the cached data.

In order to prevent obsolete resolutions, each cached data has a time-to-live (TTL) value that is of the order of any unit time depending on the data (seconds/ minutes/hours). After the elapsed TTL, the entry is removed and further resolution for the same entry will have to go to a higher level server or the “source” server itself (if all intermediate servers have removed the entry from their caches).

Another scenario needs to be considered here. Let us considered a cached entry at cs.utdallas.edu with reference to cs.mit.edu. Before the TTL expires (at cs.utdallas.edu), there is a change (made by the super user) for the entry cs.mit.edu. E.g., IP address of the machine is changed. Now, if a client (of cs.utdallas.edu) uses the obsolete IP address, there will be an error. However, the cs.mit.edu name server will not be sending out any cache invalidation messages. (Why? Because there are thousands of name servers on the Internet. You can imagine the number of changes taking place and the number of invalidation messages that would be needed). So what happens to the erroneous use of the cached IP address? Either the client times out or reaches the wrong machine. In either case, the error would have to be handled by the client. To prevent such mishaps, the TTL for MachineName-IPaddress mapping will be very short (in the order of seconds or few minutes). From the point of view of the technical jargon, these types of caches whose entries are never invalidated are called hints(we will study hints in little bit more detail in Chapter 9).

1.3Master – Slave Servers

To provide redundancy (i.e., fault tolerance) as well as to provide better response time, many name servers (especially the lower/lowest ones) use more than 1 server machine (each machine running at least 1 name server process). Here, one server machine acts as a “master” and others as “slaves”. The idea of the master-slave relationship is to handle updates using the “master copy”. Here, the updates (by the super user) are made first on the master copy and then pushed/propagated to other servers having the database copy (i.e., the slave servers). Note that the master and its slaves need to run in different machines from the point of providing redundancy. And they have the same tables replicated. (Of course, there may be inconsistencies among the table contents before the update is completed at all the slaves. We will handle that later).

  1. Program Design

As you can see in Section 5, 50% of marks are for documentation, comments, and sample logs. This 50% weight is in fact for your design: for the time you spent on thinking and designing the program structure. Hence, you are expected to design most parts of the program yourself. However, I strongly encourage you to check your design with me (before completing the entire coding itself) and check whether you are doing what I am expecting you to do. This (checking with me) is especially important since it is very difficult to make this project description document fully unambiguous while at the same time requiring you to design the program also. No credits will be given later for any misinterpretation of this project description document. Check with me on any doubts you may have.

You can consider Project 1 guidelines for this as well. Other basic possibilities that can be considered during your design are:

  • A simple, scrolling user interface is just fine. But the evaluator should be able to understand the sequence of operations being done.
  • Reasonable names for the domains (i.e., nodes on the tree) may be assigned by you.
  • Mapping tables may be “populated” in a reasonable manner. You should have around 40-50 entries for Machine-IPAddress and UserName-Password mapping.
  • No need for encrypting the password: authentication (for user login) is a simple string matching function.
  • You will/might need to “parse” the user query to identify the different components of domain name. E.g., “cs.utdallas.edu” has 3 components viz., cs, utdallas, and edu.
  • Each leafserver in the tree (server is a process not a machine) maintains at least 2 databases/tables: say, MachineName-IPaddress mapping and UserName-Password mapping. (You can show with more databases, if you would like to). Put in at least 40-50 entries in each table.
  • Each “non-leaf” server will also maintain at least 1 database (machineName-IPaddress table for its children at least).
  • Caching: will typically be done using a separate table so that the entries can be purged easily. Cached entries are not usually mixed with the “regularly maintained” table entries. So design a separate cache table(s).
  • Make sure that you can show the effect of TTL (i.e., the presence and absence of cached entry) during demo. Perhaps, TTL can be a run time parameter.
  • Alarm features provided by the operating system (such as Unix) can be used for checking TTL expiry.
  • Master-slave update: show at least 1 master-slave update mechanism. Master-slave update makes more sense at the lowest level, say cs.utdallas.edu. Use 1 master and at least 2 slave servers for at least 1 leaf domain. Show how additions/deletions/changes are first made at the master copy (by the super user) and later propagated to the slaves.
  • Master-slave regular usage: note that the basic idea of having master-slave structure is to provide redundancy AND handle more users. Show that users can “connect” to any of the servers (master/slave) for a particular domain at the login time. E.g., assume cs.utdallas.edu has 1 master and 2 slaves. When a user logs in, show that s/he can get attached to any one of the 3 servers (picked by your program in some fashion – including random choice).
  • Again, master and its slaves should be run on different machines. Same set of replicated tables should be used by the master and its slaves.
  • Log files should show the queries made at the client side, responses received, etc. Log files should be shown for intermediate sites as well (forwarding queries and the responses received). Log files may be generated by disabling the keyboard inputs needed, i.e., using some auto mechanisms that read inputs from files.
  • Especially for showing request distribution among master-slave processes. This can be done by generating several concurrent logins to the same domain having the master-slave facility.
  • You will need the above auto mechanism during demo to show that your program can handle several requests.
  • I am not too concerned about the termination part of the program e.g., Ctrl-C is just fine.

Obviously, you can follow different approaches than the ones mentioned above. Again, if in doubt, get in touch with me. Email is fine.

  1. Demonstration

As explained earlier, the program should be demonstrated with the tree structure described in Section 1. All these processes in the tree should run on at least 4 different machines: make a parent and its child to be on different machines (multiple children may be on the same machine). Note that master and slave processes need to run on different machines. The addresses of the systems and if necessary, the process names/identifiers can be put in a configuration file or as a runtime parameter.

During the demo, you have to show 2 main things:

  1. How a machineName-IPaddress query is resolved. Show this includes demonstrating the effect of caching, TTL, etc.
  2. How master-slave concept works: you need to show 2 things for this.
  3. How updates are handled by the master copy based update mechanism. Updates include addition, deletion, changes (name or IP address) to entries.
  4. How requests are distributed among master and slave servers. For this, it may be better to show multiple user logins without user interfaces and demonstrate how different users get connected to master or slave servers.

Demo should show login and name resolution by different servers in the hierarchy. For 2(b), use the auto script and show request distribution among master – slave servers. For (1), you need to show (using the auto mechanism) that your program can handle at least 200 requests (for different name resolutions) from 1 client (after 1 login).

  1. Submission

All submissions should be made through WebCT. (If you are new to WebCT, visit webct.utdallas.edu). Programs can be submitted in floppy only if it is extremely difficult to do the submission through WebCT. Submission should include the program, executable file, make files (if any), sample logs, ReadMe file (describing important aspects such as how to execute the program etc.) and a documentation file. The documentation file should describe the design aspects of the program and mention whatever assumptions made in the program. It (the documentation) should be concise and to the point (no stories, please). A reasonable expectation is 3 to 5 pages in length. Also, the program should be well commented and structured. The log file for each process (including root) can describe the program execution sequence: e.g., how many messages (including the content) and acknowledgements were sent and received.

  1. Grading

Most probably, the programs have to be demonstrated (to the TA and/or me). The demonstration may include a short oral question and answer session. The questions will be very basic in nature covering the algorithm, the program, and the design decisions made in the program. Failure to answer the basic questions will be considered seriously in grading the programming project. For instance, if a student does not answer any of the basic questions, s/he may not get any credit for this programming project. Possible break-up for grading is as follows:

  1. 20 % for documentation;
  2. 15 % for program comments and structure
  3. 15% for the sample log files;
  4. 20% for demo (1), including the at least 200 requests
  5. 15% for demo 2(a)
  6. 15% for demo 2(b)

Important note: For the first 50% (above steps a – c), your program should be compilable and executable. The basic tree should also be constructed after execution.

Program Due: 11.55pmMarch 20, 2005.

Deadline will be strictly enforced. Late submissions will have a penalty. WebCT’s clock does not allow you to submit even few seconds late.