Ricky Landry
COP5611 – OS Design Principles
Spring 2012
Homework 02
Question 1.1
For an n-dimensional lattice, we can determine the number of paths to state with the following formula:
So, for the global state we determine the number of paths to be:
To demonstrate that this formula is sound, the following examples, and a brute force determination of their possible paths, have been constructed:
Global State / Paths/ 01-11-21
10-11-21
10-20-21
Global State / Paths
/ 001-011-111-211
001-101-111-211
001-101-201-211
010-011-111-211
010-110-111-211
010-110-210-211
100-101-111-211
100-110-111-211
100-101-201-211
100-110-210-211
100-200-201-211
100-200-210-211
Global State / Paths
/ 001-101-201-301
100-101-201-301
100-200-201-301
100-200-300-301
1.2Sequence numbers are an example of logical clocks which typically exist between two processes. When looking at a TCP connection across the Internet, we can see that the sequence numbers can be used for both flow control and error control. When the congestion window approach is taken for flow control, the sequence numbers of the acknowledgements received by the sender are used to slide the congestion window to allow for slots to be freed for transmission of more packets. These logical clocks provide a form of synchronization between the states of the sender’s send buffer and the receiver’s receive buffer. The role of sequence numbers in error control is straight-forward. The numbers are used to determine if retransmission of a packet is necessary because of an error. These errors could be caused, for example, by the packet failing to arriveat the receiver or the data being corrupt.
1.3An example of a use of real clocks in the Internetis in congestion control. Real clocks are used to measure round-trip times, which can be used in congestion control algorithms. These round-trip times are typically an input to calculations of the timeout value set on resend timers. When a timeout occurs (typically meaning that an acknowledgement of packets sent has not be received by the sender), a packet can be retransmitted by the sender. These measurements of round-trip time can also be used in flow control at the sender.
Question 2 (7.3)
The question states the following:
Of the following, the best example of an end-to-end argument is:
I partially, but not completely, agree with the following tworesponses:
C.Even if a chain manufacturer tests each link before assembly, he’d better test the
completed chain.
E.All important network communication functions should be moved to the
application layer.
Response C seems better used as an example that reinforces the end-to-end argument than it does representing the argument itself. Specifically, the end-to-end argument would state that testing each link is wasted effort, and, therefore overhead, since the end result (the assembled chain) is what needs to be tested. The end-to-end argument would suggest that the testing of each link is only justifiable as a performance enhancement because testing the links prior to assembly could prevent assembling the chain with any weak links that could contribute to failure in the assembled chain’s test.
Response E says that ALL important network communication functions should be moved to the application layer. The end-to-end argument only suggests that application-specific functions be moved to the application layer (i.e. the application knows best). To put ALL network communication functions in the application layer would be inadvisable.
If I had to choose, absolutely, one of these two as an answer, I would be inclined to choose C. E’s use of the word “all” has me personally scoring it as a further deviation from true than response C. If response E said used “some” instead of “all”, or specified “all application-level network communication functions”, then E would be an accurate description of the end-to-end argument.
Question 3 (7.25)
ByteStream Inc. sells three data-transfer products: Send-and-wait, Blast, and Flow-control. Mike R. Kernel is deciding which product to use. The protocols work as follows:
• Send-and-wait sends one segment of a message and then waits for an acknowledgment before sending the next segment.
• Flow-control uses a sliding window of 8 segments. The sender sends until the window closes (i.e., until there are 8 unacknowledged segments). The receiver sends an acknowledgment as soon as it receives a segment. Each acknowledgment opens the sender’s window with one segment.
• Blast uses only one acknowledgment. The sender blasts all the segments of a message to the receiver as fast as the network layer can accept them. The last segment of the blast contains a bit indicating that it is the last segment of the message. After sending all segments in a single blast, the sender waits for one acknowledgment from the receiver. The receiver sends an acknowledgment as soon as it receives the last segment.
Mike asks you to help him compute for each protocol its maximum throughput. He is planning to use a 1,000,000 bytes per second network that has a packet size of 1,000 bytes. The propagation time from the sender to the receiver is 500 microseconds. To simplify the calculation, Mike suggests making the following approximations:
(1) there is no processing time at the sender and the receiver;
(2) the time to send an acknowledgment is just the propagation time (number of data bytes in an ACK is zero);
(3) the data segments are always 1,000 bytes; and
(4) all headers are zero-length. He also assumes that the underlying communication medium is perfect (frames are not lost, frames are not duplicated, etc.) and that the receiver has unlimited buffering.
a. What is the maximum throughput for the Send-and-wait?
b. What is the maximum throughput for Flow-control?
c. What is the maximum throughput for Blast?
Mike needs to choose one of the three protocols for an application which periodically sends arbitrary-sized messages. He has a reliable network, but his application involves unpredictable computation times at both the sender and the receiver. And this time the receiver has a 20,000-byte receive buffer.
d. Which product should he choose for maximum reliable operation:
A. Send-and-wait, the others might hang.
B. Blast, which outperforms the others.
C. Flow-control, since Blast will be unreliable and Send-and-wait is slower.
D. There is no way to tell from the information given.
Mike should choose Flow Control. Blast could overflow the receiver’s buffer since the message size in unknown, and its throughput is less than the network speed of the communication channel. Flow Control is faster than Stop-and-Wait and the transmit window prevents overflow of the receivers buffer. Flow Control also maintains a throughput equal to the network speed of the communication channel.
Question 4 (7.26)
Suppose the longest packet you can transmit across the Internet can contain 480 bytes of useful data, you are using a lock-step end-to-end protocol, and you are sending data from Boston to California. You have measured the round-trip time and found that it is about 100 milliseconds.
a. If there are no lost packets, estimate the maximum data rate you can achieve.
b. Unfortunately, 1% of the packets are getting lost. So you install a resend timer, set to 1000 milliseconds. Estimate the data rate you now expect to achieve.
So, 99 packets out of 100 are sent without any problems: 47520 B in 9900 msec.
100th packet fails and is resent after 1000 msec: 480 B in 1100 msec
c. On Tuesdays the phone company routes some westward-bound packets via satellite link, and we notice that 50% of the round trips now take exactly 100 extra milliseconds. What effect does this delay have on the overall data rate when the resend timer is not in use. (Assume the network does not lose any packets.)
50% of packets take 200 msec RTT
d. Ben turns on the resend timer, but since he hadn’t heard about the satellite delays he sets it to 150 milliseconds. What now is the data rate on Tuesdays? (Again, assume the network does not lose any packets.)
50% of packets have 200 msec RTT, which means 50% of packets will trigger a resend, which yields a total RTT for these missed packets of 250 msec (assuming the best case of the following packet being in the 50% that do not get delayed). So, to simplify this situation, we assume that every other packet triggers a resend, and that resend is a packet that goes through before the timer expires.
e. Usually, when discussing end-to-end data rate across a network, the first parameter one hears is the data rate of the slowest link in the network. Why wasn’t that parameter needed to answer any of the previous parts of this question?
It wasn’t necessary to factor in the slowest link because we were working with round-trip times. This automatically factors in the slowest link.
Question 5(8.3)
For this question, I would respond with choice D: He should have done both A and B.
Choice A is: He should have used fail-fast smoke detectors.
Choice B is: He should have used a voter that ignores failed inputs from fail-fast sources.
Using fail-fast smoke detectors would allow the voter to recognize when the smoke detector is operating incorrectly. Having the voter ignore fail-fast inputs should prevent a group of failing smoke detectors (that have failed in ways that leave them voting falsely for the same condition) from being able to sway the vote to their failure condition. There is, of course, still the chance that the smoke detectors may fail to report failures, in which case this design may still fail to notify the fire department when a fire occurs. This is a risk that must be deemed acceptable since it is unlikely that a system could be designed in such a way that would meet the same effectiveness of human verification when a system reports a fire event.
Question 6 (8.4)
You will be flying home from a job interview in Silicon Valley. Your travel agent gives you the following choice of flights:
A. Flight A uses a plane whose mean time to failure (MTTF) is believed to be 6,000 hours. With this plane, the flight is scheduled to take 6 hours.
B. Flight B uses a plane whose MTTF is believed to be 5,000 hours. With this plane, the flight takes 5 hours.
The agent assures you that both planes’ failures occur according to memoryless random processes (not a “bathtub” curve). Assuming that model, which flight should you choose to minimize the chance of your plane failing during the flight?
So, either flight would be an acceptable choice since the probability of failure is the same.
Question 7 (8.10)
a.)RAID 5 has the advantage over RAID 4 that:
I would respond choice C: Write performance in the absence of errors in enhanced, because parity is distributed across all of the drives in the array, no single drive becomes a bottleneck (unlike in a RAID 4 configuration).
b.)Is there any workload for which RAID 4 has better write performance than RAID 5?
I don't think so. The only situation that might have RAID 4 edging out RAID 5 in write performance is if the entire storage space (all stripes) were to be written to sequentially in one pass. Since the RAID controller wouldn't need to switch which drive it is using for parity when moving on to the next stripe, it may save a little overhead. However, in either configuration, all drives will be used, and if the amount of data resides on a single stripe (and therefore requiring no switching of which drives belong to the stripe and which one belongs to the parity), a chance that any small performance gain in RAID 4 is unlikely. The whole advantage of RAID 5 over RAID 4 is the fact that this parity is distributed across all of the drives in the array, removing the bottleneck from a single drive dedicated to parity.
c.)Louis is also wondering about whether he might be better off using a RAID 1 system. How does the number of disks required compare between RAID 1 and RAID 5?
The minimum number of drives required for a RAID 1 configuration is 2. The minimum number of drives required for a RAID 5 configuration is 3. RAID 1 is a mirroring configuration, so essentially for n number of drives in the array; there are 1 data drive and (n-1) redundant mirrors. Obviously, this configuration can be expensive if a large storage space is desired. The advantage of RAID 1 is that it can tolerate up to (n-1) simultaneous drive failures, since there are n copies of the data present in the array, whereas RAID 5 can only tolerate a single drive failure. RAID 5, however, has a storage space of (n-1) drives (where the smallest drive in the array determines the applicable size on each drive.
d.)Which of RAID 1 and RAID 5 has better performance for a workload consisting of small reads and writes?
Most likely RAID 1, since it's mirroring. The space cost (since the data size is 1/2 the total array size) is high for RAID 1, but because the mirror exists on another drive, writes to the target and mirror can happen concurrently. This small write would occur without the overhead of a parity calculation. Also, the block-level parity scheme of RAID 5 would require a small write to recalculate the parity for an entire block, creating a lot of overhead in calculating these parities, especially if many small writes are performed in quick succession. RAID 5 would, however, likely beat out RAID 1 in write performance for larger writes, since it can effectively write at a speed of (n-1)X, since the primary copy of data can be written concurrently across multiple drives, with a parity calculation occurring at the end.