SI540: Fall 1999
HW4 Solution
Junho Song(with notes from Prof. Paul Resnick)
Written exercise
1. E20.11 For which of the following situations is the communication link message latency bit rate limited, and for which is it propagation delay limited?
In order to answer this question, it is important to understand concept of trasmission latency, propagation latency, and bit rate.
Also, the following conversion would be useful.
1,000 bytes = 8000 bits
40 bytes = 320 bits
900 kilobytes = 900,000 bytes = 7,200,000 bits
1.4 megabytes = 1,400,000 bytes = 11,200,000 bits
If you think about relationship among message size, propagation delay, and bit rate, you will be able to come up with the following solution.
By comparing those parameters, we can determine whether it is message latency bit rate limited or propagation delay limited.
a. Bit rate 28.8 Kbps, delay 40 milliseconds, message size 1,000 bytes
Method 1: Compare transmission delay(m/B) to propagation delay(t )
Propagation delay(t ): 0.040 sec
Transmission delay(m/B): 8,000 / 28,800 = 0.28 sec
Therefore, it is bitrate limited.
Method 2: Comparing bitrate delay product(number of bits in transit on a link: Bt ) and message size(m)
Bitrate delay product(Bt ): 28,800 x 0.040 = 1,152 bits
Message size(m): 8,000 bits
Therefore, it is bitrate limited. Note that you get same answer from both methods.
b. Bit rate 28.8 Kbps, delay 40 milliseconds, message size 40 bytes
Method 1: Compare transmission delay(m/B) to propagation delay(t )
Propagation delay(t ): 0.040 sec
Transmission delay(m/B): 320 / 28,800 = 0.011 sec
Therefore, it is propagation delay limited.
Method 2: Comparing bitrate delay product(number of bits in transit on a link: Bt ) and message size(m)
Bitrate delay product(Bt ): 28,800 x 0.040 = 11,52 bits
Message size(m): 320 bits
Therefore, it is propagation delay limited. Note that you get same answer from both methods.
c. Bit rate 45 Mbps, delay 10 milliseconds, message size 900 kilobytes
Method 1: Compare transmission delay(m/B) to propagation delay(t )
Propagation delay(t ): 0.010 sec
Transmission delay(m/B): 7,200,000 / 45,000,000 = 0.16 sec
Therefore, it is bitrate limited.
Method 2:
Comparing bitrate delay product(number of bits in transit on a link: Bt ) and message size(m)
Bitrate delay product(Bt ): 45,000,000 x 0.010 = 450,000 bits
Message size(m): 7,200,000 bits
Therefore, it is bitrate limited. Note that you get same answer from both methods.
d. Same as c, except you are downloading a class (program code) that is 1.4 megabytes in size
Method 1:
Compare transmission delay(m/B) to propagation delay(t )
Propagation delay(t ): 0.010 sec
Transmission delay(m/B): 11,200,000
Therefore, it is bitrate limited.
Method 2:
Comparing bitrate delay product(number of bits in transit on a link: Bt ) and message size(m)
Bitrate delay product(Bt ): 45,000,000 x .010 = 450,000 bits
Message size(m): 11,200,000 bits
Therefore, it is bitrate limited. Note that you get same answer from both methods.
2. E20.15 For the compression algorithm illustrated in "Data Compression Algorithms" on page 558:
1110111010111010101101101011
It works because the first bit of the encoding determines how many bits are in the encoding. If ‘0’ is the first bit, there’s only one bit in the encoding, and the next bit starts a new encoding. If 1 is the first bit, then there is always another bit in the encoding of the current set of characters. Note that if we tried to decode from right to left, it would be harder. The last ‘11’ is decoded to ‘z’, but the ‘0’ before that could be either ‘eeee’ or part of ‘10’ that represent just one ‘e’.
The question suggest the frequency of appearance is as following.
(e > s > v)
Therefore, we want to assign some string bits for multiple s’s.
For example, depending on the frequency of the appearance, we would assign like followings. Each entry’s preceding bit should be able to determine the following bit uniquely, preventing any confusion in decoding.
Note that there could be many variations in this answer.
e à 01
s à 001
v à 000
eeee à 10
ss à 11
also, acceptable answer although not preferred
e à 0
s à 10
v à 11
The following would not work because it would not be clear whether 11 represented v or ss:
e à 0
s à 1
v à 11
3. Based on E20.17: Which video source could be more successfully compressed, a feed from a football game or from a surveillance camera in a barber shop?
More compression ratio can be achieved if repetition of the image occurs more. Therefore, a surveillance camera in a barber shop can be more successfully compressed since the image does not change as much as a football game does.
4. You are about to purchase a computer from Dell, in the configuration from the attached printout (or access it on line
here). Suddenly, you learn that you'll be doing statistical analysis of U.S. Census data, which you discover is available on a set of 30 CD-ROMs containing about 20GB of data in all (note: this is a fictitious scenario; I don't how big a data set from the census bureau would really be). Which of the following potential upgrades to your computer do you think would be most useful:First, statistical analysis requires a lot of mathematics calculation with both integer and float numbers. So, I would choose faster CPU(non-Celeron version). Also, adding memory can minimize the amount of virtual memory swapping (i.e., fetching memory locations from the hard disk), yielding greater performance. Large monitor can provide overview statistical data without much scrolling but it does not enhance performance directly. So, this is probably not a priority upgrade. Larger hard drive can be useful, because it lets you copy all the CD-ROM data to harddrive, and there can be faster access from the hard drive. Faster CD-ROM reader can provide speedier access to the data but it is not really critical considering current CD-Rom reader speed, especially if you are transferring all of the data to a hard disk and working from there.
So, which one is the most useful upgrade? Well, it depends on cost/benefit(performance) analysis or even on personal preference. If you choose one over the other, you should provide reasons for doing so.
5. (2) You have decided to start a Web site design and development business, out of your home office. You can spend up to $2000 to purchase equipment (a computer, monitor, printer, and scanner) and a year of Internet connectivity for your home office. Don't worry about software (that comes from a separate budget). Assume that your home office will be the only place you'll have access to computers or the Internet (no fair using the DIAD lab). Consult ads from vendors on-line or in print and fill out a copy of the
linked spread sheet. If you purchase more than one item as a package (e.g., PC and monitor), note that and use only one of the rows in the spreadsheet. Briefly discuss the reasons for any tradeoffs you're making (e.g., you purchased a really big monitor and high-speed Internet access but decided to get a FreePC and put up with all the advertising that comes with it). You can't buy the best of everything for $2000.
Explanation exercise (2 points)
Explain the PC configuration from the attached printout (or access it on line here) to someone who doesn't yet know the difference between a megahertz and megabyte. In your writeup, say what questions the explainee asked you and how you responded.