Below are answers to problem set 1. A bit of discussion is included with some of the answers. This page is by no means intended to supplant questions that you may have about this problem set, so don't hestitate to approach me with those.
You will find that questions are in green, answers are in red, and discussion is in blue.
Describe the fault tolerance (and lack of it) of both the star and ring topologies.
The star topology is highly fault tolerant for every host on the edge of the network (i.e. at the "points" of the star). Any number of those could fail without interfering with communications between the remaining hosts. However, stars are not fault tolerant for failures in the central host/switch. Without that single, central host, the entire network fails to operate.
The ring topology is in some sense less fault tolerant, although the characteristics of its fault tolerance are uniform across hosts. Any one host or link can fail while still leaving each host able to every other host. If two links fail, the network is partitioned into two pieces, leaving the hosts in each partition able to communicate with others in the same partition, but not able to communicate across partitions. Any further failures cause further partitioning, still leaving individual partitions operational.
The most common error was to assume that traffic only traveled in one direction around a ring. As a consequence, some believed that a single failure would destroy an entire ring network.
Given a connection that has a bandwidth of 400 MHz and a signal to noise ratio of 50 dB, what is the maximum data rate of that line? (Note that the ratio of signal S to noise N is typically expressed in dB, where 10 log10 (S/N) provides the decibel value.)
First, obtain the signal-to-noise ratio:
10 log10 (S/N) = 50
log10 (S/N) = 5
10log10 (S/N) = 105
S/N = 100,000
So, plugging values into Shannon's equation for the maximum data rate (in bits per second (b/s)):
H lg (1 + S/N)
400,000,000 lg (1 + 100,000)
400,000,000 (16.61)
6,644,000,000 b/s
Given an analog signaling scheme that modulates between 2 frequencies, 2 amplitudes, and 4 phases, what is the relationship between the data rate and the baud rate?
The three different types of modulation are orthogonal, thus allowing any combination of frequency, amplitude, and phase to yield a distinct signal. By multiplying the options for each type of available modulation, we get 2 x 2 x 4 = 16 possible distinct signals. In order to have one bit pattern that corresponds to each signal, we would need to assign 4 bits per signal. Each change of signal (a.k.a. "baud") therefore carries 4 bits of information.
As a consequence, the data (or bit) rate is going to be four times the baud rate.
The IEEE 802.3 (Ethernet) standard dictates that, after the tenth consecutive collision, the range of possible waiting times from which a host randomly makes selection must stop growing. Why is that specification important?
With each collision, the range of possible waiting times doubles. The 802.3 defines a time unit as being approximately 50 microseconds = 0.05 milliseconds, which is derived from the maximum communication time of a signal on a line. Therefore, if one host uniquely selects the smallest waiting time within the given window, it will transmit, and the others will successfully sense the beginning of that transmissions and prevent themselves from also transmitting. At the 10th collision, a host may wait up 0.05 seconds in attempting to retransmit. At this wait time, more than half a second passes before a failure is resported.
However, if the doubling of the wait period continued, the amount of time to wait for a failure would be much longer. The final wait period would be approximately 3 and 1/4 seconds -- which, for devices that perform operations on a microsecond or nanosecond scale, is too long a delay.
To prevent overly long wait times for failure, the range of possible wait times is therefore constrained. On faster broadcast networks where the time to transmit a frame may be substantially shorter, the range of wait times could continue to grow for a larger number of collisions.
I did not expect people to know the actual length of a timeslice, and simply looked for the observation that the time to failure would be large if the doubling of the range continued indefinitely.
It wasn't clear whether or not the question was asking about the principle of constraining the time to failure vs. the specifics of the magic collision number 10. The concept was of course more critical, as the choice of the 10th collision is specific to the capacity of the network and the duration of the timeslices involved.
Secondly, some people attempted to provide further justification for this limitation by claiming that little or nothing could be gained in collision avoidance beyond 1024 time slots, so it wasn't worthwhile to continue increasing the size of the range. This assertion is false, as the larger the range, the smaller the odds of collision. If such a network had hundreds of hosts, and many of those hosts happened to have data to send, then larger ranges beyond 1024 slots could be useful in avoiding collisions sooner.
Consider n hosts connected to a shared, broadcast medium. If an adaptive tree walk protocol is used for arbitrating this shared medium, what is the maximum number of possible collisions that can occur between successful transmissions?
If the n hosts are arranged as the leaves in a balanced, binary logical tree structure, then the tree has height ceil(lg n). In the worst case, assume that permission to transmit is initially granted to all hosts that a leaves of the subtree rooted at level 0 (i.e. the whole tree). With each collision, the protocol will restrict the permission to transmit to one of the subtrees. If no collision occurs, then the other subtree is given permission. If one host transmits, then the protocol is finished. If two or more hosts transmit, causing a collision, the decent into the next level subtree begins.
At worst, two hosts that are part of the same, lowest-level subtree may be transmitting. In that case, the entire height of the tree must be traversed by the protocol, each time contraining further the persmission to transmit until no collision occurs. Therefore, at most ceil(lg n) collisions can occur using the adaptive tree walk protocol.
The most common (and minor) problem here was that people assumed a number of hosts that was a power of 2, expressing their answer as simply lg n, when that value may not be an integer value.
Some people made a slight terminological error is discussing this protocol by referring to it as "the limited contention protocol". Strictly speaking, limited contention describes a class of protocols that selectively reduce the number of hosts allowed to transmit during a given slice of time. The adaptive tree walk protocol is an instance of a limited contention procotol.