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 / 45,000,000 = 0.25 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 .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:

  1. Code the character string "zezeezeeezeeeezeeeeez."
  2. 1110111010111010101101101011

  3. Why is it possible to decode the characters e and z uniquely without the need for commas as a delimiter between characters?

It works because the first bit of the encoding determines how many bits are in the encoding. If 0 is the first bit, theres 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.

  1. (1) E20.16 Design a compression algorithm similar to that described in "Data Compression Algorithms" on page 558 for the following situation: There are known to be three characters in the source, e, s, and v, where es are far more common than ss, which are far more common than vs.

The question suggest the frequency of appearance is as following.

(e > s > v)

Therefore, we want to assign some string bits for multiple ss.

For example, depending on the frequency of the appearance, we would assign like followings. Each entrys 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:

    1. larger hard drive
    2. more main memory
    3. faster CPU
    4. faster CD-ROM reader
    5. larger monitor

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.

 

Clarification: You are doing web site design, not web hosting. With $2,000, it is almost impossible to host a web after purchasing all the hardwares specified above. It would be helpful to get more credit, if you include a sentence or two explaining why you made that decision.

 

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.