Homework 11

22C:116, Spring 1997

Due Friday Apr. 18, 1997, in class

Douglas W. Jones
  1. Background: Consider the following load balancing algorithm for use in a network of computers connected by point-to-point links. Each computer in the network communicates only with its nearest neighbors in the network. The load on machine i is Li. Machine i periodically offers to accept load from its neighbors only if Li<Toffer, and it only accepts offers if Li>Taccept. Note that Taccept>Toffer.

    If an overloaded machine i receives an offer from machine j, and that machine has a process p imposing a load Lp where Lp<(Li-Lj)/2, then process p is a candidate for migration. The largest process meeting this criteria is the one actually moved.

    Assume that the machine loadings Li and the thresholds T are stated in terms of the interval 0 (no load) to 1 (saturation).

    The Problem, part A: Assuming that processes of a wide variety of sizes are constantly being created, and that processes live for a random interval, and that there are only two machines, how well does this algorithm work as the interval between Taccept and Toffer changes over the interval 0 to 1. Assume that the period between offers on an unloaded machine is significantly less than the average process life.

    The Problem, part B: Consider a large network of computers, where the period between balancing offers from each underloaded machine is on the order of 1/10 the average process lifetime, how does the ability of this algorithm to balance the load vary with the diameter of the network grows.

    The Problem, part C: Compare this algorithm with the algorithms discussed in part 12.3 of the text. Which is it most similar to, and in what way is it most different from that similar algorithm.

  2. Background: Consider a stateless file server. Files are identified by the server using file numbers similar in spirit to UNIX I-node numbers, and the server has no conception of open or close operations; it merely allows users to issue UNIX-style read and write operations on files, by number.

    Sitting on top of this file server is a directory server. This server accepts textual file names from users and returns, to the user, the file number to be used for I/O to that file. All user-server interactions are formulated as RPCs in this system. The directory server maintains UNIX style directories using the resources of the file server to do so.

    The Problem, Part A: Write pseudocode for the open, read, write and close services on the user's machine, assuming that each user process uses unix style file handles (small integers from 0 to 31), and that there is only one file server and only one directory server in the system. Do not delve into the details of the RPC protocols used, but assume that appropriate client-side stubs are available!

    The Problem, Part B: Write pseudocode for the directory server that clearly identifies all of the server-to-server communication involved in the open operation. Again, assume that appropriate client-side stubs are available!

    The Problem, Part C: How could you improve the performance of the file server by adding state information, in the server, on behalf of users, and how much of this performance advantage could you gain by appropriate cacheing strategies in the server.

    The Problem, Part D: In a network file system, client side caching and server side caching are both practical. Explain the semantic differences that users would observe between these options.