CS 436 Winter 2010 - Assignment 1

Due Date: Monday, Feb 8, 2010, 22:00

Notes

• Prepare your answers for Questions 1-5 as a PDF document a1.pdf and use the submit utility in the student.cs computing environment to submit it. Also see Question 6 for submission information.

• As stated in the course outline, you can submit one assignment up to two days late. In this case, please email your late submission to the TA.

• You are permitted to make use of 3rd-party literature (including online resources). However, you must acknowledge any resource that has significantly helped you in producing your answers. Further, you are not permitted to collaborate with other students, other than discussing the assignment in general.

• Make sure to read and understand the relevant policies.

Questions

1. Assume the following code:

   0000000000
   0000011111
   0011100011
   0011111100
   1100100101
   1100111010
   1111000110
   1111011001

   1. (1 point) What is the minimum Hamming distance of this code?
   2. (1 point) What maximum bit errors can be detected?
   3. (1 point) What maximum bit errors can be corrected?

   Briefly explain how you have obtained your results.

2. (1 point) Explain why PPP must have a byte stuffing mechanism, while Ethernet does not.

3. Assume a network that uses a "token passing" medium access control protocol with the following parameters:
   • 10 stations
   • ring length: 500 m
   • frame size: 1000 bytes (assume all 1000 bytes are useful data)
   • transmission rate: 100 Mbit/s
   • propagation speed: 200,000,000 m/s
   • per-station token delay (token forwarding, frame forwarding): 0.000001 s
   • token size is negligible
   • After sending a frame, the sending station waits for the frame to travel around the ring. It then releases the token to give other stations the possibility to send. The station can send next when the token arrives again.
   1. (2 points) What is the overall efficiency, if only a single station has data to send?
   2. (2 points) What is the overall efficiency, if all stations have data to send?

4. (2 points) Why does the frame size not play a role for the efficiency of the Aloha protocol, but for Ethernet's CSMA/CD medium access control?

5. (2 points) Assume an Ethernet network with the following parameters:
   • maximum distance between nodes: 1000 m
   • transmission rate: 10 Mbit/s
   • propagation speed: 200,000,000 m/s

   Compute the minium frame size for CSMA/CD to guarantee that all collisions can be decteted by a sender.

6. (12 points) Implement the Dijkstra algorithm in your favourite programming language. Use the submit tool to submit the source code along with a suitable Makefile/script, etc. (depending on your programming language) as a zip/tar/gzip/bzip2 archive with any of the following corresponding names: dijkstra.{zip,tgz,tbz}.

   Make sure that your submission works in the student.cs environment and include a file named README that explains how to compile (if necessary) and invoke the program. Your program must adhere to the following interface:

   ./dijkstra <origin> <file>
   

   <origin> is the number of the node at which the algorithm is executed. <file> is the name of an input file that lists multiple network links (one per line) according to the following format:

   <node1> <node2> <cost>
   

   Each line describes a symmetric link between <node1> and <node2> with cost <cost>. Nodes are identified by numbers.

   The program must produce output on standard output of the form

   <total cost> <origin> <node1> <node2> ... <destination>
   

   that is, each line describes the shortest path to an destination the path's total cost. The order of the output lines does not matter.

   Your program should perform basic error checking, i.e., it should not just crash when receiving faulty input, but either try to perform the computation or produce an error message and quit. As stated, you can consult 3rd-party resources (example) for this assignment, but you must implement your own solution. You can used third-party unsorted list or array data types, but must not use higher-level container libraries (map, set, queue, etc.). You can implement/use your own container classes.