• Error detection and correction
  • Parity checking
  • CRC
• Multiple access protocols
  • Slotted ALOHA
  • Pure ALOHA
  • CSMA/CD
• LAN
  • Addressing: MAC address
    • ARP
  • Ethernet
  • Switch
    • Switch vs routers
• Data center networking
• Exercise
  • P1
  • P2
  • P3
  • P5
  • P6
  • P7
  • P8
  • P9
  • P12
  • P14
  • P15
  • P16

Error detection and correction

Parity checking

• single bit parity: detect single bit errors
• two-dimensional bit parity: detect and correct single bit errors

CRC

Cyclic Redundancy Check

See the exercise section.

Multiple access protocols

Multiple access protocol is distributed algorithm that determines how nodes share channel, i.e., determine when node can transmit. And communication about channel sharing must use channel itself.

• channel partitioning: TDMA, FDMA, CDMA
• random access: ALOHA, S-ALOCA, CSMA, CSMA/CD
• taking turns

Slotted ALOHA

When node obtains fresh frame, transmits in next slot. If no collision, node can send new frame in next slot. If there is a collision, node retransmits frame in each subsequent slot with probability p until success.

Efficiency: N nodes with many frames to send, each transmits in slot with probability p

• prob that given node has success in a slot: $p(1-p)^{N-1}$
• prob that any node has a success: $Np(1-p)^{N-1}$
• max efficiency: find $p^*$ that maximizes $Np(1-p)^{N-1}$
• for many nodes, take limit of $Np^*(1-p^*)^{N-1}$ as N goes to $\infty$, gives: $max \; efficiency = \frac{1}{e}$

Pure ALOHA

Similar with Slotted ALOHA, but no synchronization. With efficiency of only 18%.

CSMA/CD

Carrier sense multiple access, reduces the amount of time wasted in collisons.

Efficiency:

• $t_{prop}$: max prop delay between 2 nodes in LAN
• $t_{trans}$: time to transmit max-size frame

$$efficienty = \frac{1}{1 + 5 \frac{t_{prop}}{t_{trans}}}$$

Better performance than ALOHA: and simple, cheap, decentralized!

LAN

Addressing: MAC address

48-bit MAC address, e.g. 1A-2F-BB-76-09-AD

Each interface on LAN has unique MAC address, and a locally unique 32-bit IP address.

ARP

Address resolution protocol: determine interface’s MAC address, knowing its IP address.

Ethernet

Physical topology: bus connected or switched.

Ethernet is unreliable and connectionless.

Switch

A link layer device

• store, forward Ethernet frames
• examine incoming frame’s MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on segment, uses CSMA/CD to access segment

Switch forwarding table: stored in the switch, self learning.
Contains entry: (MAC addr, interface, TTL)

Switch vs routers

Switch	Router
link layer	network layer
learn forwarding table using flooding	compute tables using routing algorithms

Data center networking

• Border routers
• Tier 1 switches
• Tier 2 switches
• Top of rack switch
• Server racks

Multipath: rich interconnection among switches and racks.

---

Exercise

From Computer Networking: A Top Down Approach 7th Edition

Chapter 6

P1

Suppose the information content of a packet is the bit pattern 1110 0110 1001 1101 and an even parity scheme is being used. What would the value of the field containing the parity bits be for the case of a two-dimensional parity scheme? Your answer should be such that a minimum length checksum field is used.

11101
01100
10010
11011
11000

P2

Show (give an example other than the one in Figure 6.5) that two-dimensional parity checks can correct and detect a single bit error. Show (give an example of) a double-bit error that can be detected but not corrected.

Suppose we begin with the initial two-dimensional parity matrix:

0000
1111
0101
1010

With a bit error in row 2, column 3, the parity of row 2 and column 3 is now wrong in the matrix below:

0000
1101
0101
1010

Now suppose there is a bit error in row 2, column 2 and column 3. The parity of row 2 is now correct! The parity of columns 2 and 3 is wrong, but we can’t detect in which rows the error occurred!0000

0000
1001
0101
1010

The above example shows that a double bit error can be detected (if not corrected).

P3

Suppose the information portion of a packet (D in Figure 6.3) contains 10 bytes consisting of the 8-bit unsigned binary ASCII representation of string “Networking.” Compute the Internet checksum for this data.

P5

Consider the 5-bit generator, G=10011, and suppose that D has the value 1010101010. What is the value of R?

If we divide 10011 into 1010101010 0000, we get 1011011100, with a remainder of R=0100. Note that, G=10011 is CRC-4-ITU standard.

P6

Consider the previous problem, but suppose that D has the value

a. 1001010101

1000110000, with a remainder of R=0000.

b. 0101101010

0101010101, with a remainder of R=1111.

c. 1010100000

1011010111, with a remainder of R=1001.

P7

In this problem, we explore some of the properties of the CRC. For the ­generator G(=1001) given in Section 6.2.3, answer the following questions.

a. Why can it detect any single bit error in data D?

b. Can the above G detect any odd number of bit errors? Why?

a.

Without loss of generality, suppose ith bit is flipped, where 0<= i <= d+r-1 and assume that the least significant bit is 0th bit. A single bit error means that the received data is K=D*2r XOR R + 2i. It is clear that if we divide K by G, then the reminder is not zero. In general, if G contains at least two 1’s, then a single bit error can always be detected.

b.

The key insight here is that G can be divided by 11 (binary number), but any number of odd-number of 1’s cannot be divided by 11. Thus, a sequence (not necessarily contiguous) of odd-number bit errors cannot be divided by 11, thus it cannot be divided by G.

P8

In Section 6.3, we provided an outline of the derivation of the efficiency of slotted ALOHA. In this problem we’ll complete the derivation.

a. Recall that when there are N active nodes, the efficiency of slotted ALOHA is Np(1−p)N−1. Find the value of p that maximizes this expression.

$$\begin{align} E(p) &= Np(1-p)^{N-1} \nonumber\\ E'(p) &= N(1-p)^{N-1} - Np(N-1)(1-p)^{N-2} \nonumber\\ &= N(1-p)^{N-2}((1-p) - p(N-1)) \nonumber\\ E'(p) &= 0 \Rightarrow p^* = \frac{1}{N} \nonumber \end{align}$$

b. Using the value of p found in (a), find the efficiency of slotted ALOHA by letting N approach infinity. Hint: (1−1/N)N approaches 1/e as N approaches infinity.

$$\begin{align} E(p^*) &= N\frac{1}{N}(1-\frac{1}{N})^{N-1} = (1-\frac{1}{N})^{N-1} = \frac{(1-\frac{1}{N})^N}{1-\frac{1}{N}} \nonumber\\ \lim_{N \rightarrow \infty}(1-\frac{1}{N}) &= 1 \nonumber\\ \lim_{N \rightarrow \infty}(1-\frac{1}{N})^N &= \frac{1}{e} \nonumber\\ Thus: \lim_{N \rightarrow \infty}E(p^*) &= \frac{1}{e} \nonumber \end{align}$$

P9

Show that the maximum efficiency of pure ALOHA is 1/(2e). Note: This problem is easy if you have completed the problem above!

$$\begin{align} E(p) &= Np(1-p)^{2(N-1)} \nonumber\\ E'(p) &= N(1-p)^{2(N-2)} - Np2(N-1)(1-p)^{2(N-3)} \nonumber\\ &= N(1-p)^{2(N-3)}((1-p) - p2(N-1)) \nonumber\\ E'(p) &= 0 \Rightarrow p^* = \frac{1}{2N-1} \nonumber\\ E(p^*) &= \frac{N}{2N-1}(1-\frac{1}{2N-1})^{2(N-1)} \nonumber\\ \lim_{N \rightarrow \infty}E(P^*) &= \frac{1}{2} \cdot \frac{1}{e} = \frac{1}{2e} \nonumber \end{align}$$

P12

Graph the efficiency of slotted ALOHA and pure ALOHA as a function of p for the following values of N:

a. N=15

b. N=25

c. N=35

import matplotlib.pyplot as plt

def slotted_efficiency(N: int) -> float:
    return (1 - 1/N)**(N - 1)

def pure_efficiency(N: int) -> float:
    return (N / (2*N - 1)) * ((1 - 1/(2*N - 1))**(2 * (N - 1)))

N = [i for i in range(1, 36)]
pure = [pure_efficiency(i) for i in N]
slotted = [slotted_efficiency(i) for i in N]

plt.plot(N, pure, c="orange", label="pure")
plt.plot(N, slotted, c="blue", label="slotted")
plt.title('The efficiency of slotted ALOHA and pure ALOHA')
plt.xlabel('N')
plt.ylabel('efficiency')
plt.legend()
plt.show()

P14

Consider three LANs interconnected by two routers, as shown in Figure 6.33.

a. Assign IP addresses to all of the interfaces. For Subnet 1 use addresses of the form 192.168.1.xxx; for Subnet 2 uses addresses of the form 192.168.2.xxx; and for Subnet 3 use addresses of the form 192.168.3.xxx.

b. Assign MAC addresses to all the adapters.

c. Consider sending an IP datagram from Host E to Host B. Suppose all the ARP tables are up-to-date. Enumerate all the steps, as done for the single-router example in Section 6.4.1.

1. Forwarding table in E determines that the datagram should be routed to interface 192.168.3.002.
2. The adapter in E creates and Ethernet packet with Ethernet destination address 88- 88-88-88-88-88.
3. Router 2 receives the packet and extracts the datagram. The forwarding table in this router indicates that the datagram is to be routed to 198.162.2.002.
4. Router 2 then sends the Ethernet packet with the destination address of 33-33-33- 33-33-33 and source address of 55-55-55-55-55-55 via its interface with IP address of 198.162.2.003.
5. The process continues until the packet has reached Host B.

d. Repeat (c), now assuming that the ARP table in the sending host is empty (and the other tables are up-to-date).

ARP in E must now determine the MAC address of 198.162.3.002. Host E sends out an ARP query packet within a broadcast Ethernet frame. Router 2 receives the query packet and sends to Host E an ARP response packet. This ARP response packet is carried by an Ethernet frame with Ethernet destination address 77-77-77-77-77-77.

P15

Consider Figure 6.33. Now we replace the router between subnets 1 and 2 with a switch S1, and label the router between subnets 2 and 3 as R1.

a. Consider sending an IP datagram from Host E to Host F. Will Host E ask router R1 to help forward the datagram? Why? In the Ethernet frame containing the IP datagram, what are the source and destination IP and MAC addresses?

No. E can check the subnet prefix of Host F’s IP address, and then learn that F is on the same LAN. Thus, E will not send the packet to the default router R1. Ethernet frame from E to F:

• Source IP = E’s IP address
• Destination IP = F’s IP address
• Source MAC = E’s MAC address
• Destination MAC = F’s MAC address

b. Suppose E would like to send an IP datagram to B, and assume that E’s ARP cache does not contain B’s MAC address. Will E perform an ARP query to find B’s MAC address? Why? In the Ethernet frame (containing the IP datagram destined to B) that is delivered to router R1, what are the source and destination IP and MAC addresses?

No, because they are not on the same LAN. E can find this out by checking B’s IP address. Ethernet frame from E to R1:

• Source IP = E’s IP address
• Destination IP = B’s IP address
• Source MAC = E’s MAC address
• Destination MAC = The MAC address of R1’s interface connecting to Subnet 3.

c. Suppose Host A would like to send an IP datagram to Host B, and neither A’s ARP cache contains B’s MAC address nor does B’s ARP cache contain A’s MAC address. Further, suppose that the switch S1’s forwarding table contains entries for Host B and router R1 only. Thus, A will broadcast an ARP request message. What actions will switch S1 perform once it receives the ARP request message?
Will router R1 also receive this ARP request message?
If so, will R1 forward the message to Subnet 3?
Once Host B receives this ARP request message, it will send back to Host A an ARP response message. But will it send an ARP query message to ask for A’s MAC address? Why?
What will switch S1 do once it receives an ARP response message from Host B?

Switch S1 will broadcast the Ethernet frame via both its interfaces as the received ARP frame’s destination address is a broadcast address. And it learns that A resides on Subnet 1 which is connected to S1 at the interface connecting to Subnet 1. And, S1 will update its forwarding table to include an entry for Host A.

Yes, router R1 also receives this ARP request message, but R1 won’t forward the message to Subnet 3.

B won’t send ARP query message asking for A’s MAC address, as this address can be obtained from A’s query message.

Once switch S1 receives B’s response message, it will add an entry for host B in its forwarding table, and then drop the received frame as destination host A is on the same interface as host B (i.e., A and B are on the same LAN segment).

P16

Consider the previous problem, but suppose now that the router between subnets 2 and 3 is replaced by a switch. Answer questions (a)–(c) in the previous problem in this new context.

Let’s call the switch between subnets 2 and 3 S2. That is, router R1 between subnets 2 and 3 is now replaced with switch S2.

a.

No. E can check the subnet prefix of Host F’s IP address, and then learn that F is on the same LAN segment. Thus, E will not send the packet to S2. Ethernet frames from E to F:

• Source IP = E’s IP address
• Destination IP = F’s IP address
• Source MAC = E’s MAC address
• Destination MAC = F’s MAC address

b.

Yes, because E would like to find B’s MAC address. In this case, E will send an ARP query packet with destination MAC address being the broadcast address. This query packet will be re-broadcast by switch 1, and eventually received by Host B. Ethernet frame from E to S2:

• Source IP = E’s IP address
• Destination IP = B’s IP address
• Source MAC = E’s MAC address
• Destination MAC = broadcast MAC address: (B’s MAC address).

c.

Switch S1 will broadcast the Ethernet frame via both its interfaces as the received ARP frame’s destination address is a broadcast address. And it learns that A resides on Subnet 1 which is connected to S1 at the interface connecting to Subnet 1. And, S1 will update its forwarding table to include an entry for Host A. Yes, router S2 also receives this ARP request message, and S2 will broadcast this query packet to all its interfaces. B won’t send ARP query message asking for A’s MAC address, as this address can be obtained from A’s query message. Once switch S1 receives B’s response message, it will add an entry for host B in its forwarding table, and then drop the received frame as destination host A is on the same interface as host B (i.e., A and B are on the same LAN segment).

---