3.10: Epilog and Exercises

Along with a few niche protocols, we have focused primarily here on wireless and on virtual circuits. Wireless, of course, is enormously important: it is the enabler for mobile devices, and has largely replaced traditional Ethernet for home and office workstations.

While it is sometimes tempting (in the IP world at least) to write off ATM as a niche technology, virtual circuits are a serious conceptual alternative to datagram forwarding. As we shall see in 20 Quality of Service, IP has problems handling real-time traffic, and virtual circuits offer a solution. The Internet has so far embraced only small steps towards virtual circuits (such as MPLS, 20.12 Multi-Protocol Label Switching (MPLS)), but they remain a tantalizing strategy.

3.11 Exercises

Exercises are given fractional (floating point) numbers, to allow for interpolation of new exercises. Exercise 4.5 is distinct, for example, from exercises 4.0 and 5.0. Exercises marked with a ♢ have solutions or hints at 24.3 Solutions for Other LANs.

1.0. Suppose remote host A uses a VPN connection to connect to host B, with IP address 200.0.0.7. A’s normal Internet connection is via device eth0 with IP address 12.1.2.3; A’s VPN connection is via device ppp0 with IP address 10.0.0.44. Whenever A wants to send a packet via ppp0, it is encapsulated and forwarded over the connection to B at 200.0.0.7.

(a). Suppose A’s IP forwarding table is set up so that all traffic to 200.0.0.7 uses eth0 and all traffic to anywhere else uses ppp0. What happens if an intruder M attempts to open a connection to A at 12.1.2.3? What route will packets from A to M take?

(b). Suppose A’s IP forwarding table is (mis)configured so that all outbound traffic uses ppp0. Describe what will happen when A tries to send a packet.

2.0. Suppose remote host A wishes to use a TCP-based VPN connection to connect to host B, with IP address 200.0.0.7. However, the VPN software is not available for host A. Host A is, however, able to run that software on a virtual machine V hosted by A; A and V have respective IP addresses 10.0.0.1 and 10.0.0.2 on the virtual network connecting them. V reaches the outside world through network address translation (7.7 Network Address Translation), with A acting as V’s NAT router. When V runs the VPN software, it forwards packets addressed to B the usual way, through A using NAT. Traffic to any other destination it encapsulates over the VPN.

Can A configure its IP forwarding table so that it can make use of the VPN? If not, why not? If so, how? (If you prefer, you may assume V is a physical host connecting to a second interface on A; A still acts as V’s NAT router.)

3.0. Token Bus was a proprietary Ethernet-based network. It worked like Token Ring in that a small token packet was sent from one station to the next in agreed-upon order, and a station could transmit only when it had just received the token.

(a). If the data rate is 10 Mbps and the token is 64 bytes long (the 10-Mbps Ethernet minimum packet size), what is the average wait to receive the token on an idle network with 40 stations? (The average number of stations the token must pass through is 40/2 = 20.) Ignore the propagation delay and the gap Ethernet requires between packets.

(b)♢. Sketch a protocol by which stations can sort themselves out to decide the order of token transmission; that is, an order of the stations S₀ … S_n-1 where station S_isends the token to station S_{(i+1) mod n}.

4.0. A seemingly important part of the IEEE 801.11 Wi-Fi standard is that stations do not transmit when another station is transmitting; this is meant to reduce collisions. And yet the standard states “transmission of the ACK frame shall commence after a SIFS period, without regard to the busy/idle state of the medium”; that is, the ACK sender does not listen first for an idle network.

Give a scenario in which the transmission of an ACK while the medium is not idle does not result in a collision! That is, station A has just finished transmitting a packet to station C, but before C can begin sending its ACK, another station B starts transmitting. Hint: this is another example of the hidden-node problem, 3.7.1.4 Hidden-Node Problem, with station C again the “middle” station. Recall also that simultaneous transmission results in a collision only if some node fails to be able to read either signal as a result. (Also note that, if C does not send its ACK, despite B, the packet just sent from A has to all intents and purposes been lost.)

4.5.♢ Give an example of a three-sender hidden-node collision (3.7.1.4 Hidden-Node Problem); that is, three nodes A, B and C, no two of which can see one another, where all can reach a fourth node D. Can you do this for more than three sending nodes?

5.0. Suppose the average contention interval in a Wi-Fi network (802.11g) is 64 SlotTimes. The average packet size is 1 kB, and the data rate is 54 Mbps. At that data rate, it takes about (8×1024)/54 = 151 µsec to transmit a packet.

(a). How long is the average contention interval, in µsec?

(b)♢. What fraction of the total potential bandwidth is lost to contention? (See 2.1.11 Analysis of Classic Ethernet for a similar example).

6.0. WiMAX and LTE subscriber stations are not expected to hear one another at all. For Wi-Fi non-access-point stations in an infrastructure (access-point) setting, on the other hand, listening to other non-access-point transmissions is encouraged.

(a). List some ways in which Wi-Fi non-access-point stations in an infrastructure (access-point) network do sometimes respond to packets sent by other non-access-point stations. The responses need not be in the form of transmissions.

(b). Explain why Wi-Fi stations cannot be required to respond as in part (a).

7.0. Suppose WiMAX subscriber stations can be moving, at speeds of up to 33 meters/sec (the maximum allowed under 802.16e).

(a). How much earlier (or later) can one subscriber packet arrive? Assume that the ranging process updates the station’s propagation delay once a minute. The speed of light is about 300 meters/µsec.

(b). With 5000 senders per second, how much time out of each second must be spent on “guard intervals” accommodating the early/late arrivals above? You will need to double the time from part (a), as the base station cannot tell whether the signal from a moving subscriber will arrive earlier or later.

8.0. [SM90] contained a proposal for sending IP packets over ATM as N cells as in AAL-5, followed by one cell containing the XOR of all the previous cells. This way, the receiver can recover from the loss of any one cell. Suppose N=20 here; with the SM90 mechanism, each packet would require 21 cells to transmit; that is, we always send 5% more. Suppose the cell loss-rate is p (presumably very small). If we send 20 cells without the SM90 mechanism, we have a probability of about 20p that any one cell will be lost, and we will have to retransmit the entire 20 again. This gives an average retransmission amount of about 20p extra packets. For what value of p do the with-SM90 and the without-SM90 approaches involve about the same total number of cell transmissions?

9.0. In the example in 3.4 Virtual Circuits, give the VCI table for switch S5.

10.0. Suppose we have the following network:

A───S1────────S2───B
    │         │
    │         │
    │         │
C───S3────────S4───D

The virtual-circuit switching tables are below. Ports are identified by the node at the other end. Identify all the connections. Give the path for each connection and the VCI on each link of the path.

Switch S1:

VCIin	portin	VCIout	portout
1	A	2	S3
2	A	2	S2
3	A	3	S2

Switch S2:

VCIin	portin	VCIout	portout
2	S4	1	B
2	S1	3	S4
3	S1	4	S4

Switch S3:

VCIin	portin	VCIout	portout
2	S1	2	S4
3	S4	2	C

Switch S4:

VCIin	portin	VCIout	portout
2	S3	2	S2
3	S2	3	S3
4	S2	1	D

10.5♢ We have the same network as the previous exercise:

A───S1────────S2───B
    │         │
    │         │
    │         │
C───S3────────S4───D

The virtual-circuit switching tables are below. Ports are identified by the node at the other end. Identify all the connections. Give the path for each connection and the VCI on each link of the path.

Switch S1:

VCIin	portin	VCIout	portout
1	A	2	S2
3	S3	2	A

Switch S2:

VCIin	portin	VCIout	portout
2	S1	3	S4
1	B	2	S4

Switch S3:

VCIin	portin	VCIout	portout
2	S1	2	S4
1	S4	3	S1

Switch S4:

VCIin	portin	VCIout	portout
3	S2	2	D
2	S2	1	S3

11.0. Suppose we have the following network:

A───S1────────S2───B
    │         │
    │         │
    │         │
C───S3────────S4───D

Give virtual-circuit switching tables for the following connections. Route via a shortest path.

(a). A–D

(b). C–B, via S4

(c). B–D

(d). A–D, via whichever of S2 or S3 was not used in part (a)

12.0. Below is a set of switches S1 through S4. Define VCI-table entries so the virtual circuit from A to B follows the path

A ⟶ S1 ⟶ S2 ⟶ S4 ⟶ S3 ⟶ S1 ⟶ S2 ⟶ S4 ⟶ S3 ⟶ B

That is, each switch is visited twice.

A──S1─────S2
   │      │
   │      │
B──S3─────S4

13.0. In this exercise we outline the two-ray ground model of wireless transmission in which the signal power is inversely proportional to the fourth power of the distance, rather than following the usual inverse-square law. Some familiarity with trigonometric (or complex-exponential) manipulations is necessary.

Suppose the signal near the transmitter is \(A \sin(2\pi f t)\), where A is the amplitude, f the frequency and t the time. Signal power is proportional to A². At distance r≥1, the amplitude is reduced by a factor of 1/r (so the power is reduced by 1/r²) and the signal is delayed by a time r/c, where c is the speed of light, giving

\[(\mathrm{A} / \mathrm{r}) \sin (2 \pi \mathrm{f}(\mathrm{t}-\mathrm{r} / \mathrm{c}))=(\mathrm{A} / \mathrm{r}) \sin (2 \pi \mathrm{ft}-2 \pi \lambda \mathrm{r})\]

where \(\lambda = f/v\) is the wavelength.

The received signal is the superposition of the line-of-sight signal path and its reflection from the ground, as in the following diagram:

Sender and receiver are shown at equal heights above the ground, for simplicity. We assume 100% ground reflectivity (this is reasonable for very shallow angles). The phase of the ground signal is reversed 180° by the reflection, and then is delayed slightly more by the slightly longer path.

(a). Find a formula for the length of the reflected-signal path rʹ, in terms of r and h. Eliminate the square root, using the approximation (1+x)^1/2 ≃ 1 + x/2 for small x. (You will need to factor r out of the square-root expression for rʹ first.)

(b). Simplify the difference (because of the 180° reflection phase-reversal) of the line-of-sight and reflected-signal paths. Use the approximation

\[\sin(X) − \sin(Y) = 2 \sin ((X-Y) / 2) \cos ((X+Y) / 2) \simeq(X-Y) \cos ((X+Y) / 2) \simeq(X-Y) \cos (X)\]

for \(X≃Y\) (or else use complex exponentials, noting sin(X) is the real part of i e^iX). You may assume rʹ−r is smaller than the wavelength ��. Start with

\[(A / r) \sin (2 \pi f t-2 \pi \lambda r)-\left(A / r^{\prime}\right) \sin \left(2 \pi f t-2 \pi \lambda r^{\prime}\right)\]

,it helps to isolate the r→rʹ change to one subexpression at a time by writing this as follows (adding and subtracting the identical middle terms):

\[\begin{aligned} &\left((A / r) \sin (2 \pi f t-2 \pi \lambda r)-\left(A / r^{\prime}\right) \sin (2 \pi f t-2 \pi \lambda r)\right)+\left((A / r) \sin (2 \pi f t-2 \pi \lambda r)-\left(A / r^{\prime} \sin \left(2 \pi f t-2 \pi \lambda r^{\prime}\right)\right)\right.\\=&\left.\left(A / r-A / r^{\prime}\right) \sin (2 \pi f t-2 \pi \lambda r)+\left(A / r^{\prime}\right)(\sin (2 \pi t)-2 \pi \lambda r)-\sin \left(2 \pi f t-2 \pi \lambda r^{\prime}\right)\right) \end{aligned}\]

(c). Show that the approximate amplitude of this difference is proportional to 1/r², making the relative power proportional to 1/r⁴.

14.0. In the four-way handshake of 3.7.5 Wi-Fi Security, suppose station B (for Bad) records the successful handshake of station A and the access point. A then leaves the network, and B attempts a replay attack: B uses A’s packets in the handshake. At exactly what point does the handshake break down?