Networking Midterm Exam

Problem 1: OSI Architecture

1. Match the following to one of the seven OSI layers:

i. reliable end-to-end data transportation – Transport (4)
ii. network selection – Network (3)
iii. defines frames – Data Link (2)
iv. provides user services such as e-mail and file transfer – Application (7)
v. transmission of bit stream across physical medium – Physical (1)
vi. communicates directly with user’s application program – Presentation (6)
vii. error correction and retransmission – Transport (4)
viii. mechanical, electrical and functional interface – Physical (1)
ix. responsibility for information between adjacent nodes – DataLink (2)
x. reassembly of data packets – Transport (4)
xi. establishes, manages, and terminates sessions .- Session (5)
xii. ensures reliable transmission of data – Transport (4)
xiii. log - in and log -out procedures – Application (7)

Problem 2: Encoding, Framing and Error Control

(a) A host wishes to send the following nine bits: 011101100
Assume that NRZI signals start low. Show the NRZI signal encoding of this data.

(b) True or false: [2 points for circling all correct answers, -0.5 points for each wrong
answer]

i. CRC can both correct and detect errors. FALSE
ii. 2-d parity can detect all 2-bit errors and correct all 1-bit errors. TRUE
iii. 4B/5B encoding solves the problem of long sequences of zeroes but still has
issues with long sequences of 1s. FALSE

(c) Suppose we want to transmit the message 101010101 and protect it from errors using
the CRC polynomial x ^3+x+1. Use polynomial long division to determine the message
that should be transmitted. Show your work for full credit.
101010101 100

Problem 3: Bridging
Consider hosts X, Y, Z, W, U and learning
bridges B1, B2, B3, B4 with initially empty
forwarding tables, connected in the following
manner:

(a) Assuming B1 has the lowest bridge identifier,
and B4 the highest, show the spanning tree for
the above network.

(b) Say B4 is connected to U, B2, B3 and Z via its
ports 1, 2, 3 and 4, respectively. Assuming no failures, which of these ports will B4
never forward on (i.e. which ports are blocked)?
3, 4

(c) Suppose X sends its first packet to Z. Which bridges learn where X is? Does Y’s
network interface see this packet?
All bridges will learn. Yes, Y’s interface will see this packet.

(d) Suppose Z now sends its first packet to X. Which bridges learn where Z is? Does Y’s
network interface see this packet?
B1, B2, B3 will learn. Y will not see this packet.

(e) Suppose Y now sends to X. Which bridges learn where Y is? Does Z’s network
interface see this packet?
B1, B2 will learn. Z will not see this packet.

Problem 4: Short Answers
a. Which is more efficient, a Manchester encoding or a 4B/5B encoding?
Manchester encoding is only 50% efficient whereas 4B/5B is 80% efficient.

b. What is the hidden terminal problem ?

If B can hear both A and C, but A and C cannot hear each other due to being out of range,
A may start an interfering transmission to one already in progress from C to B, creating a
collision at B that A cannot detect.
Note: A may be transmitting to another node D, rather than C, and a collision would still
occur at B.

c. How does 802.11 solve it ? (Hint: RTS/ CTS method )
The transmitting node sends a RTS and the receiving node sends a CTS before
transmission, indicating the period that the channel will be busy. Nodes that can
hear the receiver will hear the CTS and stay silent for that period of time.

d. List one advantage and one disadvantage for Datagram based forwarding schemes
Advantages: Ability to re-route packets dynamically in case of failures.
Can send traffic immediately.
Disadvantages: Header requires full unique address .
May not be possible to deliver packet
Successive packets may not follow the same route
Global address to path translations require significant storage.

Problem 5: Bandwidth and Delay
Suppose a 100-Mbps point-to-point link is being set up between the Earth and a new
lunar colony. The distance from the earth to moon is approximately 385,000 km, and data
travels over that link at the speed of light, 3*108 m/second. The maximum packet size for
this networking technology is 1-kilobyte.
(a) Calculate transmission delay and propagation delay?

Transmission delay = L/R = 1 kilobyte / 100 Mbps = 8000 bits/ (100*106 bits/sec) = 80 micro seconds
Propagation delay = distance / speed = 385000 km/(3*108m/sec) = 1.28 sec

(b) From the above, calculate the minimum roundtrip time for this link.

Minimum RTT = 2*(Transmission delay + Propagation delay) = 2.56sec

(c) Using the RTT as the delay, calculate the delay * bandwidth product for this link .
Delay bandwidth product = 2.56* 100 Mbps = 256 Mb

(d) Say we have to transfer a 1000KB file. It takes duration of 2RTT for initial
handshaking (i.e., connection setup). After finishing sending each packet, we must
wait one RTT before sending the next. Compute the total time to transfer the file.

1000 KB file => 1000 packets, each packet being 1 KB size
Total Transfer Time
= 2 x initial RTT + Size of Data / Bandwidth + 999 * RTT
= 2*2.56 + 1000KB/100Mbps + 999*2.56
= 5.12 + 0.08 + 2557.44 = 2562.56 seconds

Problem 5
Consider the following Banyan network:

Consider of arrival of two packets
- Packet 1 arriving at input port 0 with 110
as the three bit self-routing header
- Packet 2 arriving at input port 3 with 001
as the three bit self-routing header

Draw the paths taken by the both packets.

Bonus
Show (on the diagram) how another packet on another input, destined for a different
output port, can collide with 101 inside the Banyan network (i.e., they occupy the same
wire).

Consider a packet 3 arriving at input port 5 with 111, i.e., it has to be routed
“down” “down” “down”. Thus, packet 3 is destined to port 7. However, it has to
share the first two “wires” along with packet 1, thus causing collisions.

Prev Next