Spring Term 2016

Prof. Adrian Perrig

Operating Systems and Networks

Solution 7

Note: these solutions constitute material supplemental to the exercise sessions.

1 Wireless Communication
Consider five wireless stations: A, B, C, D, and E. Station A can communicate with all other stations.
B can communicate with A, C and E. C can communicate with A, B and D. D can communicate with
A, C and E. E can communicate with A, D and B.

a) When A is sending to B, what other communications are possible?

b) When B is sending to A, what other communications are possible?
c) When B is sending to C, what other communications are possible?

Answer:

a) Since all stations will see As packet, it will interfere with receipt of any other packet by any other
station. So, no other communication is possible in this case.
b) Although B’s packet will not be seen by D, other nodes cannot send to D because the packets from
these nodes will interfere with the packets from B at A. Therefore, other communications is not
possible at the same time.
c) B’s packet will be seen by E, A and C, by not by D. Thus, E can send to D at the same time.

2 MACA
Six stations in a straight line, A through F, communicate using the Multiple Access with Collision
Avoidance (MACA) protocol. Is it possible for two transmissions to take place simultaneously? Explain
your answer.
Answer: Yes. Since they are in a straight line and that each station can reach only its nearest neighbors,
A can send to B while E is sending to F.

3 CSMA/CA
To reduce ambiguities about which station is sending, 802.11 defines channel sensing to consist of both
physical sensing and virtual sensing (see Figure 1). Physical sensing simply checks the medium to see if
 Figure 1: MACA

there is a valid signal. With virtual sensing, each station keeps a logical record of when the channel is
in use by tracking the NAV (Network Allocation Vector). Each frame carries a NAV field that says how
long the sequence of which this frame is part will take to complete.
Which of the last two stations do you think is closest to A, and why?
Answer: Station C is the closest to A since it heard the RTS and responded to it by asserting its NAV
signal. D did not respond, so it must be outside A’s radio range.

4 CSMA/CD
If signal propagation speed in twin lead is 2.46 · 108 m/sec and signal propagation speed in multimode
fiber is 1.95 · 108 m/sec,

a) What is the length of a contention slot in CSMA/CD for a 2-km twin-lead cable?
b) What is the length of a contention slot in CSMA/CD for a 40-km multimode fiber optic cable?

Answer:

a) Signal propagation speed in twin lead is 2.46 ∗ 108 m/sec. Signal propagation time for 2 km is 8.13
µsec. So, the length of contention slot is 16.26 µsec.

b) Signal propagation speed in multimode ber is 1.95 ∗ 108 m/s. Signal propagation time for 40 km is
205.13 µsec. So, the length of contention slot is 410.26 µsec.

5 Spanning Tree Algorithm

a) Given the network shown in Figure 2, where the letters A to J represent LANs and the circles B1 to
B7 represent a switch node. Indicate which ports are not selected by the spanning tree algorithm.

b) Given the network shown in Figure 2, assume that switch B1 suffers catastrophic failure. Indicate
which ports are not selected by the spanning tree algorithm after the recovery process and a new
tree has been formed.

Answer:
We depict the collection of switches in a local area network (LAN) as a graph whose nodes are switches and
LAN segments (or cables), and whose edges are the interfaces connecting the switches to the segments.

2
 Exercises

B
B7
C B2
D B5
B1
E F

B3

G H

B4 B6
I
J

Figure
Figure3.37 Network
2: Network for Exercises
for spanning 13 and 14.
tree algorithm

The spanning tree algorithm works as follows 1 B3

: C

• Elect a single switch, among all the switches on all the LANs, to be the Root Bridge.
A B1 B2
• Calculate the distance of the shortest path from the switches to the Root Bridge.
• For each LAN, elect Designated Bridge from among the switches residing on that LAN. The elected
switche is the one closest to the Root Bridge. The Designated Bridge will forward packets from
B4 D
that LAN toward the Root Bridge.
• Choose a port (known as the root port) that gives the best path from each Designated Bridge to
the Root Bridge.
Figure 3.38 Network for Exercises 15 and 16.
• Select ports to be included in the spanning tree. The port selected will be the root port plus any
ports on which ‘self’ has been elected Designated Bridge.
■ A sends to C.
The ports which are not selected by the spanning tree algorithm are shown as red dotted lines in Figure 3.
■ C sends to A.
After the recovery process, the new formed spanning tree is shown in Figure 4. The ports which are not
■ D sends to C.
selected by the spanning tree algorithm are shown as red dotted lines.
Identify ports with the unique neighbor reached directly from that port; tha
the ports for B1 are to be labelled “A” and “B2.”

16 As in the previous problem, consider the arrangement of learning bridges sh

in Figure 3.38. Assuming all are initially empty, give the forwarding tables
each of the bridges B1–B4 after the following transmissions:

1 Radia Perlman. 1999. Interconnections (2nd Ed.): Bridges, Routers, Switches, and Internetworking Protocols.

Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.

3
B7 A B2 B B5

C D F

Root bridge

B1 E B3 Designated bridge

Blocked port

G H

B4 I B6 J

Figure 3: Spanning tree a)

B7 A B2 B B5

C D F

Root bridge

E B3 Designated bridge

Blocked port

G H

B4 I B6 J

Figure 4: Spanning tree b)