Network Problems
Q1 Consider the singlesender CDMA example in Kurose & Ross. What would be the sender's output (for the 2 data bits shown), if the sender's CDMA code were (1, 1, 1, 1, 1, 1, 1, 1)?
Q2 Suppose an 802.11 b station is configured to always reserve the channel with the RTS/CTS sequence. Suppose this station suddenly wants to transmit 1,000 bytes of data, and all other stations are idle at this time. As a function of SIFS and DIFS, and ignoring propagation delay and assuming no bit errors, calculate the time required to transmit the frame and receive the acknowledgment.
Q3 Suppose you worked for a Canadabased company that wanted to develop its own MIB for managing a product line. Where in the object identifier tree would it be registered? (Hint: You'll have to do some digging through RFCs or other documents to answer this question.)
Q4 'BER encoding example' in Kurose & Ross. What would be the BER encoding of {weight, 276}{lastname, "Harrison"}?
Q5 A 3000kmlong T1 trunk is used to transmit 64byte frames using GoBackN protocol. If the propagation speed is 6 microseconds/km, how many bits should the sequence numbers be?
Q6 A simple telephone system consists of two end offices and a single toll office to which each end office is connected by a 1MHzfullduplex trunk. The average telephone is used to make five calls per 8hour workday. The mean call duration is 6 min. Ten percent of the calls are longdistance (i.e., pass through the toll office). What is the maximum number of telephones an end office can support? (Assume 4 kHz per circuit, and note that you may need to do some additional readings about transmission media and telephone systems, either in the library or on the Internet for this question. Please list what you read if this is the case.)
Q7 Suppose the information content of a packet is the bit pattern 1011011011101011, and an even parity scheme is being used. What would the value of the checksum field be for the case of a twodimensional parity scheme? Your answer should be such that a minimumlength checksum field issued. Note:You may need to do some additional readings about data encoding, and error detection and correction, either in the library or on the Internet for this question. Please list what you read if this is the case.
Q8 Suppose two nodes, A and B, are attached to opposite ends of an 800 m cable, and that they each have one frame of 1 024 bits (including all headers and preambles) to send to each other. Both nodes attempt to transmit at time t = 0. Suppose there are five repeaters between A and B, each inserting a 20bit delay. Assume the transmission rate is 10 Mbps, and CSMA/CD with backoff intervals of multiples of 512 bits is used. After the first collision, A draws K = 0 and B draws K = 1 in the exponential backoff protocol after sending the 48bit jam signal.
a. What is the oneway propagation delay (including repeater delays) between A and B in seconds? Assume that the signal propagation speed is 2*10^8 m/sec.
b. At what time (in seconds) is A's packet completely delivered at B?
c. Now suppose that only A has a packet to send, and that the repeaters are replaced with switches. Suppose that each switch has a 16bit processing delay in addition to a storeandforward delay. At what time, in seconds, is A's packet delivered at B?
Note: you must include all the delays occurred according to CSMA/CD protocol.
Q9 Two CSMA/CD stations are each trying to transmit long (multiframe) files. After each frame is sent, they contend for the channel, using the binary exponential backoff algorithm. What is the probability that the contention ends on round k, and what is the mean number of rounds per contention period?
Q10 UDP and TCP use the 1s complement for their check sums. Suppose you have the following three 8bit bytes: 10011001, 01010010, and 01011001.
a. What is the 1s complement of the sum of these 8bit bytes? Show all your work.
b. Why is it that UDP takes the 1s complement of the sum; that is, why not just use the sum?
c. With the 1s complement scheme, how does the receiver detect errors?
d. Is it possible that a lbit error will go undetected? How about a twobit error? (Note that although UDP and TCP use 16bit words to compute the checksum, for this problem you are being asked to consider 8bit summands.)
Q 11 Consider a scenario in which a Host, A, wants to simultaneously send messages to Hosts B, C, and D. A is connected to B, C, and D via a broadcast channel, and a packet sent by A is carried by this channel to each of B, C, and D. Suppose that the broadcast channel connecting A, B, C, and D can independently lose and corrupt messages (and so, for example, a message sent from A might be correctly received by B, but not by C and D). Design a stopandwaitlike errorcontrol protocol for reliably transferring a packet from A to B, C, and D, such that A will not get new data from the upper layer until it knows that B, C, and D have correctly received the current packet. Give FSM descriptions of A and B. (Hint:The FSM for C and D should be essentially the same as for B.) Also, give a description of the packet format(s) used.
Q 12. The following table is used to compute the shortest path from A to all other nodes in a network, according to linkstate algorithm.
Step

N.

D(v),P(v)

D(w),P(w)

D(x),P(x)

D( y),P( y)

D(z),P(z)

0

u

2,u

5,u

1,u

∞

∞

1

ux

2,u

4,x


2,x

∞

2

uxy

2,u

3,y



4,y

3

uxyv


3,y



4,y

4

uxyvw





4,y

5

uxyvwz






1. Interpret the table in your own words.
2. Consider the following network. With the indicated link costs, use Dijkstra's shortestpath algorithm to compute the shortest path from x to all network nodes. Show how the algorithm works by computing a table similar to the table above.
Q 13. A router has the following (CIDR) entries in its routing table:
Address/mask Next hop
135.46.56.0/22 Interface 0
135.46.60.0/22 Interface 1
192.53.40.0/23 Router 1
Default Router 2
For each of the following IP addresses, what does the router do if a packet with that address arrives?
a. 135.46.63.10
b. 135.46.57.14
c. 135.46.52.2
d. 192.53.40.7
e. 192.53.56.7
Note: to answer this question you may need to search on the Web for related documents, and study those online documents or tutorials.
Q 14. For a 1Gbps network operating over 5000 km, the delay is the limiting factor, not the bandwidth. Consider a MAN with the average source and destination 20 km apart. At what data rate does the roundtrip delay due to the speed of light equal the transmission delay for a 1KB packet? Assume the speed of light in fibre to be 2/3 the speed of light in a vacuum.