Computer Networking---CS312

Practice Exam

 

                                                                                                September 30, 2002

 

 

1.        Show the Manchester encoding for the bit pattern shown below.

 

11011001101

 

Assuming non textbook encoding of low-high for zero and high-low for one:

 

-_-__--_-__-_--_-__--_

 

2.        Explain why the shared medium ethernet protocol does not scale to cross-country distances. Be precise.

 

a.        In order to detect collisions, a station must still be sending when the collision bounces back to the sending station.  Assuming a distance of 5000 Km across the country and bits moving at 200,000 Km/sec This would be a time of (2 x 5 x 10^6 )/2x10^8m/s = 50 ms.  During this time a station sending at 10 Mbps would send 10 x 10^6 x 5x10^-2 = 50 x 10^4 or 500,000bits which is 62500 bytes.  Quite a waste if the packet only is sending a single byte of actual data!

b.        We know that utilization is equal to           1

                                                                    ------------------

                                                                     1 +  2eBL/cF

where L is the maximum length between stations.  As L gets large (50000Km is very large), utilization decreases significantly.

 

3.        Is it possible to use a 3-dimensional parity scheme?  If not, explain why not.  If so, describe how.

 

Yes, think of sheets of 2 dimensional parity on top of one another.  Add a top sheet that would contain the parity bits using one bit from each sheet.

 

4.        Show how Hamming Code would encode the bit string 11010110.

 

Hamming code would place the data bits in the non powers of 2 slots

 

_              _              1              ­_              1              0              1              _              0              1              1              0

 

with zeros in the powers of two slots that are the check bits

 

0              0              1              0              1              0              1              0              0              1              1              0

 

Each data bit that is a one would then flip the relevant check bits resulting in:

 

0              0              1              0              1              0              1              0              0              1              1              0

 

 

In this case the check bits re all zero!

 

5.        If we used a generating function of x3 + x2 + 1, and received a message of 11011011001011, would we find that the message had any errors?

 

Divide 11011011001011 by 1101.  If there are any remainders, we would know there is an error.  In this case we have a remainder of 101 indicating that the message is in error.

 

6.        Calculate the total time required to transfer a 1000-Kbit file in the following cases, assuming an RTT of 100msec, a packet size of 1 KB data and an initial 2 x RTT of handshaking before the data is sent.

 

  1. The bandwidth is 1.5 MBPS and data packets can be sent continuously

 

The handshaking would take 200 msec.

Transmission could be continuous and would take 1 x10^6 / 1.5 x 10 ^6 = .67 sec or 670 msec. 

The last bit would take an additional 100 msec for a total of 970 msec assuming no acknowledgement is necessary.

 

  1. The bandwidth is 1.5 Mbps, but after we finish sending each data item, we must wait one RTT before sending another one

 

The handshaking would take 200 msec.

Each packet would take .67 msec to transmit

with a 100 msec wait, resulting in a 100.67 msec per packet X 1000 packets which is 100.67 sec

 

  1. The bandwidth is infinite meaning that we take transmit time to be zero. And up to 30 packets can be sent per RTT. 

 

The handshaking would take 200 msec.

We send 30 packets,  wait for response, repeat.

It would take 34 x RTT to complete which is 3400 +200 msec which is 3.6 sec.

 

  1. The bandwidth is infinite and during the first RTT we can send one packet (21-1), during the second RTT we can send two packets (22-1), during the third we can send four (23-1), and so on.

 

The number of round trips required her would be the number of terms before 1 + 2 +4 +8 +16... = 1000 This would require 10 trips or 10 x 100 msec + 200 msec 1200 msec = 1.2 sec

 

7.        Consider a LAN with a maximum distance of 2 km. At what bandwidth would propagation delay (at a speed of 2  x 108 m/s) equal transmit delay for 100-byte packets.  What about 512 byte packets?

 

Propagation delay = (2 x 10^3)/(2 x 10^8) = 1 x 10^-5 = 10 microsec.

transmit delay = data/rate.

solving for rate, we have rate = data/transmit delay = (8 x 10^2)/(1 x 10^ –5) = 80 x 10^6 which is 80 Mbps

 

For 512 bytes, the data would be 4.096 X 10^3 (8 x 512)

rate = (4.096 x 10^3)/(1 x 10^-5) = 4.096 x 10 ^8 409.6 X 10^6 = 409 Mbps

 

8.        Calculate the latency (from first bit sent to last bit received) for the following:

 

a)       10 Mbps Ethernet with a single store-and-forward switch in the path and a packet size of 5000 bits.  Assume that each link introduces a propagation delay of 10 microsec and that the switch begins retransmitting immediately after it has finished receiving the packet.

 

Transmit delay is (5 x 10^3)/10 x 10^6) = 500 x 10^-6 or 500 microsec.

Total latency = 500 +10 + 500 + 10 = 1020 microsec or 1.02 msec

 

b)       Same as (a) but with three switches.

 

4(510) = 2.04 msec.

 

c)       Same as (a) but assume the switch implements “cut-through” switching: It is able to begin retransmitting the packet after the first 200 bits have been received.

 

We can think about the last bit sent. It takes 500 microsec before it is put on the wire, it takes 10 microsec to reach the switch and now must wait in a queue of 200 bits. which is 20 micro sec and then 10 microsec to get to teh next station for a total of  540 microsec.

 

9.        Hosts A and B are each connected to a switch S via 10 Mbps links. The propagation delay on each link is 20 microsec. S is a store-and-forward device.  It begins retransmitting a packet 35 microsec after it has finished receiving it.  Calculate the total time required to transmit a message of 10,000 bits from A to B.

a)       as a single packet

b)       as two 5000-bit packets sent one right after another.

c)       Assume there are 100 bits of overhead on each packet.  What would be the optimum packet size to minimize the total time to deliver the 10,000 bit message.

 

 

10.     Consider building a CSMA/CD network running at 10 Mbps over a 1-km linkable with no repeaters.  The signal speed in the cable is 200,000 km/sec.  What is the minimum frame size?

 

propagation time is (1 x10^3)/ (2 x 10^8) = 5 x 10^-6 or 5 microsecs.

transmit time must equal 2 x propagation time (round trip) = 10 microsec

Frame = rate X time = (10 x 10^6) x (10 x 10^-6) = 100 bits or 13 bytes

 

11.     At a transmission rate of 5 Mbps and a propagation speed of 200 m/microsec, to how many meters of cable is the 1-bit delay in a token-ring interface equivalent?

 

Transmission rate is 5 x 10^6 bps or 5 bits/microsec.

so 5 bits will take up 200 meters and 1 bit will take up 40 meters on the wire.

 

12.     A special new LAN technology uses a slotted ring (similar to token ring) to convey short messages between devices at a manufacturing facility.  Multiple messages can be on the ring simultaneously.  Each slot has enough room for 1-byte of control information, a 1-byte source address, a 1-byte destination address, and 16 data bytes.  The ring has 500 devices on a 10 km ring with a data rate of 10Mbps. 

 

A.      What is the maximum amount of slots that could be on the network at one time?  Explain your answer.

 

Each bit takes 20 meters (see problem above) 10 km ring could hold 500 bits (wire) +500 bits (1 per station)= 1000 bits or 125 bytes.  Each slot takes 19 bytes so the ring could hold 6 slots.

 

B.       Sending stations flip a control bit to indicate that a slot is in use and when the message comes all the way around, they flip it back and pass the slot on to the next station.  What issues must be resolved in order for this protocol to work?

 

Similar to the standard token ring:

                What if a station goes down after sending a message but before flipping the bit back.

                How does a station know what slot is theirs?

                Can one station grab every slot? Can a station reuse the slot it just got back? For how long?

                                Could a station be starved?  it doesn’t got any slots

 

13.     Consider a frame consisting of two characters of four bits each.  Assume that the probability of error is 10-3 and that it is independent for each bit.

a)       What is the probability that the received frame contains at least one error?

b)     Now add a parity bit to each character.  What is the probability for error now?

c)       What is the probability that the two words will go through with an undetected error?

The probability of a bit being bad is 10^-3

The probability of a bit being good is 1-10^-3

The probability of 8 consecutive bits being good is (1-10^-3)^8

The probability of at least one error is:

1-(1-10^-3)^8 = 7.97 * 10^-3 = .00797

 

b) Now add a parity bit to each character.  What is the probability for error

now?

 

We now have 10 bits per frame instead of 8.  The probability of error is:

1-(1-10^-3)^10 = 9.95 * 10^-3 = .00995 which is almost a 25% increase in the

chance of an error.

 

Errors would not be detected if exactly 2 or exactly 4 bits were in error in a character.   What are the probabilities of that happening?