Re: [Pppext] [rbridge] TRILL, IS-IS, and System ID

[Vernon Schryver <[e-mail]>]

I don't understand the second application of the Birthday Paradox in
http://tools.ietf.org/html/draft-simpson-isis-ppp-unique-01

It is true that the probability that at least 2 of N random, uniformly
distributed selections from the set of M numbers from 1 to M are the
same is greater than 0.5 when N is greater than the square root of M.
That justifies the first application of the Paradox in section 2.

I don't understand the reasoning behind the claim in section 3:

]                                                   The probability
]  of conflict is defined by a birthday attack of the order N/2**16;
]  where N is the number of systems in the same IS-IS area.
]
]  Also, many companies reuse the same MAC for different product lines,
]  or different speeds or types of media.

It is true that for a single OUI, a vendor can assigned 2**24 distinct
non-multicast MAC addresses.  My problems are that:

  - The square root of 2**24 is 4096 instead of 2**16.  Where did 2**16
     come from?

   - Companies making more than 2**24 devices have always been able
     to get additional OUIs.

  - The least significant 24 bits of the MAC addresses for a given OUI
     seen in a given network are often not uniformly distributed, which
     makes the Birthday Paradox inapplicable.  If you buy many devices
     made by a single vendor, you might well get 'runs' of consecutive
     addresses.  That can significantly reduce the likelihood of
     collision.

   - During the approximately dozen years that I was the MAC address czar
     for a computer vendor, I was aware of one or two cases of duplicate
     MAC addresses.  They were cases where the people on the factory
     floor messed up and used re-used blocks of numbers that I had
     released instead of asking for another block.  The resulting
     distributions of duplicate addresses going out the factory door
     or arriving at customer sites were not at all uniform, again
     making the Birthday Paradox the wrong model.

   - After decades of IEEE 48-bit MAC address assignments, it must be
     possible to measure the probability of 48-bit IEEE MAC address
     collisions.  Handwaving about vendors too lazy to get additional
     OUIs and talk about broken, 1990 vintage Ethernet-FDDI bridges
     cannot justify solving a problem that can now be measured and
     found serious, non-existent, or somewhere between.  It is necessary
     to collect 48-bit IEEE addresses and look for duplicates.  If the
     probability of duplicate MAC addresses in an IS-IS area using
     TRILL is enough smaller than probability of other failures, then
     the problem 'MUST NOT' be solved.


Vernon Schryver    [e-mail]