Homework 1

CS43

5%, due Feb. 20

1. Problems 8, 9, 12, and 18 from Chapter one of Tanenbaum.
   1. Problem 8.

      The maximum number of hops for a 2-D mesh is order of the length of a side, or square root of the number of processors. However, given a specific number of processors, an exact hop count is required. The worst case path is from one corner to the opposite corner. Counting, this is 30 hops for a mesh which is 16 processors on a side.

   2. Problem 9.

      For a hypercube, the exact number of hops is the log, base 2, of the number of processors. In this case that number is 8.

   3. Problem 12.

      A distributed operating system is tightly coupled software on loosely coupled hardware. It presents the user with a unified view of the system. This makes the underlying hardware appear to be tightly coupled. A network operating system is loosely coupled software on loosely coupled hardware. The user is aware of the distinct resources of the system and the fact that the underlying hardware is loosely coupled.

   4. Problem 18.

      One major problem, which everyone saw, was the distribution of the source files, and re-distribution of the object files, across the network. What no one saw (Have you forgotten the compilation process?) is that the link phase has no parallelism whatsoever. All object files must be collected by one machine, which links them with the necessary libraries to build the executable.

      The point here is that the parallel speed-up of a program is bounded by how much of it is inherently sequential (i.e., non-parallel). The sequential portions are bottlenecks.

2. Using traceroute, determine the route from keystone to one machine in each of the .au (Australia), .jp (Japan), and .uk (United Kingdom) domains. Repeat the experiment later to determine if a different route is taken. Report the routes and the differences. Part of this problem is locating machines in the appropriate domains. Note that traceroute's complete path is /usr/sbin/traceroute.

   I saw no problems here. For your results to really be valid, you should have performed the second round of experiments some hours, and not minutes, later.

3. Using ping's -s switch, vary the size of packets sent to a California site from 8 bytes to 4096 bytes and graph packet size versus transit time. Is the graph linear all the way through the packet size range? If not, can you give a reason? Report the methodology used for determining the transit times (I'm looking for evidence that the times you report are fairly precise). Note that ping's complete path is /sbin/ping.

   Most of you need brushing-up on lab techniques. You had an exponential graph because your X-axis was exponential. You should have used a log-axis with your data points and then you would have seen linearity.

4. Using ping's -c switch, send two echo request packets to abacus (204.171.15.202). Then, do the same thing to 204.171.15.255 (be careful not to send more than two requests to this IP address). Explain this result. (Hint: look at the output of the command ifconfig we0, run at keystone. ifconfig's complete path is /sbin/ifconfig.)

   Typically, .255 is the broadcast address (addressed to everyone on the network) and since ping is an echo request everyone on the network sends back an echo packet, leading to numerous duplicates. What I found interesting is that there are no duplicates if only one ping is sent.