Question

Suppose Ethernet physical addresses are chosen at random (using true random bits). (a) What is the probability that on a 1024-host network, two addresses will be the same? (b) What is the probability that the above event will occur on some one or more of \(2^{20}\) networks? (c) What is the probability that of the \(2^{30}\) hosts in all the networks of (b), some pair has the same address? Hint: The calculation for (a) and (c) is a variant of that used in solving the socalled Birthday Problem: Given \(N\) people, what is the probability that two of their birthdays (addresses) will be the same? The second person has probability \(1-\frac{1}{365}\) of having a different birthday from the first, the third has probability \(1-\frac{2}{365}\) of having a different birthday from the first two, and so on. The probability all birthdays are different is thus $$ \left(1-\frac{1}{365}\right) \times\left(1-\frac{2}{365}\right) \times \cdots \times\left(1-\frac{N-1}{365}\right) $$ which for smallish \(N\) is about $$ 1-\frac{1+2+\cdots+(N-1)}{365} $$

Short answer

Part (a): \( \frac{1024 \times 1023}{2^{49}} \). Part (b): \( 1 - e^{-\frac{1023}{2^{19}}} \). Part (c): \( 1 \).

Step-by-step solution

Calculate the probability of two addresses being the same in a 1024-host network (Part a)

In the Birthday Problem analogy, the probability that all addresses are different is computed as: \[ \left(1-\frac{1}{2^{48}}\right) \left(1-\frac{2}{2^{48}}\right) \cdots \left(1-\frac{1023}{2^{48}}\right) \]For small probabilities, this can be approximated by: \[1 - \frac{1 + 2 + 3 + \cdots + 1023}{2^{48}} \approx 1 - \frac{1024 \times 1023 / 2}{2^{48}} = 1 - \frac{1024 \times 1023}{2^{49}} \]Therefore, the probability that at least two addresses are the same is approximately: \[P \approx 1 - \left(1- \frac{1024 \times 1023}{2^{49}}\right) \approx \frac{1024 \times 1023}{2^{49}} \]

Calculate the probability for one or more of \(2^{20}\) networks (Part b)

Given the probability for one network is approximately \( \frac{1024 \times 1023}{2^{49}} \), the probability of no collisions on one network is: \[ P_{no-collision} = 1 - \frac{1024 \times 1023}{2^{49}} \]The probability of no collisions on any of the \(2^{20}\) networks is: \[ \left(1 - \frac{1024 \times 1023}{2^{49}}\right)^{2^{20}} \approx e^{-\left( \frac{1024 \times 1023}{2^{49}} \cdot 2^{20} \right)} \]Since \(1024 = 2^{10}\), this simplifies to: \[ e^{-\left( \frac{2^{10} \times 1023}{2^{49}} \cdot 2^{20} \right)} = e^{-\frac{1023}{2^{19}}} \]The probability of at least one collision on one or more of the networks is approximately: \[ P \approx 1 - e^{-\frac{1023}{2^{19}}} \]

Calculate the probability for the \(2^{30}\) hosts across all networks (Part c)

Using the same method, the probability for no collisions across all \(2^{30}\) hosts is: \[P_{no-collision} = \left(1 - \frac{1}{2^{48}} \right) \left(1 - \frac{2}{2^{48}} \right) \cdots \left(1 - \frac{2^{30}-1}{2^{48}} \right) \]Approximating: \[P_{no-collision} \approx e^{-\left( \frac{(2^{30})(2^{30}-1)}{2 \times 2^{48}} \right)} \approx e^{-\left( \frac{2^{60}}{2^{49}} \right)} = e^{-2^{11}} \]Thus, the probability that at least one pair of the \(2^{30}\) hosts has the same address is: \[ P \approx 1 - e^{-2^{11}} \approx 1 - 0 \approx 1 \]

Key concepts

Birthday Problem in Networks

The Birthday Problem is a classic probability puzzle that helps explain collisions in networking, specifically in Ethernet addresses. Imagine you have a room filled with people, and you want to know the chances that at least two individuals share the same birthday. As more people enter the room, the probability increases. This is similar to what happens in a network when more hosts (computers or devices) are added; the chances that two hosts have the same Ethernet address rise. Instead of birthdays, we're working with addresses. This problem becomes very useful in understanding and solving network-related probability issues, especially when the number of hosts grows significantly.

Ethernet Address Collision

Ethernet addresses, also known as MAC (Media Access Control) addresses, are unique identifiers assigned to network interfaces. These addresses are generally 48-bit numbers, allowing for a vast number of unique combinations (about 281 trillion). However, when Ethernet addresses are chosen randomly, there's still a chance of duplicates, especially as the number of hosts increases. This collision probability can be calculated similarly to the Birthday Problem. For instance, in a 1024-host network, we use the formula to calculate the probability of at least two hosts having the same address. This probability is important for understanding the reliability and performance of a network, as address collisions can lead to network issues.

Probability Calculations in Networking

To determine the likelihood of Ethernet address collisions, we use probability calculations, often guided by principles from the Birthday Problem. Here are the steps:

• First, calculate the probability that all addresses are different in a given network. This is done using the formula: \[ \left(1-\frac{1}{2^{48}}\right) \left(1-\frac{2}{2^{48}}\right) \cdots \left(1-\frac{1023}{2^{48}}\right) \] For small probabilities, this simplifies to: \[1- \frac{1024 \times 1023}{2^{49}} \]
• Then, calculate the probability for multiple networks or a large number of hosts. For instance, on \(2^{20}\) networks, the probability of no collisions can be simplified using an exponential approximation:
\[ \left(1- \frac{1024 \times 1023}{2^{49}}\right)^{2^{20}} \approx e^{-\frac{1023}{2^{19}}} \]
• Finally, for larger groups, like \(2^{30}\) hosts across many networks, the probability is calculated similarly, showing that as the number of hosts increases, the chances of collisions become almost certain. This is demonstrated by the formula:
\[ \left(1- \frac{1}{2^{48}} \right) \left(1- \frac{2}{2^{48}} \right) \cdots \left(1- \frac{2^{30}-1}{2^{48}}\right) \approx e^{-2^{11}} \approx 0 \]
• This means the probability of some pair having the same address becomes nearly 1, indicating the inevitability of collisions as the network scales.

These mathematical tools provide vital insights for network engineers, helping them design more reliable and efficient systems.