Subject: [rbridge] On Nick-Names

From: Eric.Gray at marconi.com (Gray, Eric)
Date: Wed, 1 Nov 2006 17:59:31 -0500

Folks,

Another thing to consider in potentially reducing the size of 
the RBridge ID name space is that reducing the number of bits
also increases the probability of "name collisions" during the
process of nick-name negotiation - further complicating the
RBridge interactions by increasing the probability that "name
collisions" will result in multiple retries.

Last I heard, the protocol specification was going to spell
out how nick-names would be negotiated.  As I understand it,
the plan was to assert a nick-name based on some substring of
the MAC-derived system ID.  Since this is at least 48 bits
(with perhaps fewer bits relevantly significant), a reduction
to 19 bits was felt to introduce a collision probability that
is not too bad.

Do people feel that collisions are likely to remain rare if 
the name space is reduced to 16 bits?  IMO, that may be an
unreasonable assumption...

--
Eric

---

From: Radia.Perlman at sun.com (Radia Perlman)
Date: Wed, 01 Nov 2006 18:57:58 -0800

I thought the spec did say how to choose nicknames.

I think it should be done based on choosing them at random, (rather than 
some substring
of the MAC address) and if someone with higher priority
asks for the same nickname you did, you have to choose a different one. 
Priority is
based on lower MAC address.

It will converge more quickly if the nickname space is not very densely 
used of course. But I really
think that people are not talking about building campuses with more than 
1000 RBridges, so
with 16 bits it wouldn't be densely assigned.

I don't care what size the nickname is. 16 bits seemed to align nicely, 
but as I said, I don't care.

Radia

Gray, Eric wrote:

>_______________________________________________
>rbridge mailing list
>rbridge at postel.org
>http://mailman.postel.org/mailman/listinfo/rbridge
>  
>

---

From: Donald.Eastlake at motorola.com (Eastlake III Donald-LDE008)
Date: Thu, 2 Nov 2006 01:03:04 -0500

Details on choosing a nickname are in the expired
draft-bryant-perlman-trill-pwe-encap-00. I'll paste them below

Donald

   Each RBridge chooses its own nickname.  However, each RBridge is also
   responsible for ensuring that its nickname is unique.  If R1 chooses
   nickname x, and R1 discovers, through receipt of R2's LSP, that R2
   has also chosen x, then the RBridge with the lower system ID keeps
   the nickname, and the other one must choose a new nickname.

   If two RBridge domains merge, then there might be a lot of nickname
   collisions for a short time, but as soon as each side receives the
   link state packets of the other, the RBridges that need to change
   nicknames will quickly become aware of this, and choose new nicknames
   that do not, to the best of their ability, collide with any existing
   nicknames.

   To minimize the probability of nickname collisions, each RBridge
   chooses its nickname randomly from the set of assigned nicknames.
   Alternatively, we could use some sort of hash algorithm (such as the
   bottom 19 bits of the MD5 of the RBridge's system ID), to choose the
   first nickname, and then if there is a collision, go to the next 19
   bits of the MD5, and so on, until all 128 bits of the MD5 hash are
   exhausted, in which case the RBridge hashes its own system ID again,
   this time together with the constant "1".

   There is no reason for all RBridges to use the same algorithm for
   choosing nicknames.  Picking them at random, or using a hash, are an
   attempt to avoid collisions when the network starts up, but that is
   only an optimization.  Even if all RBridges used the same algorithm,
   say as a worst case, they all start with "1" and count up
   sequentially until they find an uncontested nickname, the network
   will eventually stabilize.  And once it is stable, nicknames should
   remain stable even as routers go up or down.

   To minimize the probability of a new RBridge usurping a nickname
   already in use, an RBridge should wait to acquire the link state
   database from a neighbor before it announces its own nickname.

-----Original Message-----
From: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org] On
Behalf Of Radia Perlman
Sent: Wednesday, November 01, 2006 9:58 PM
To: Gray, Eric
Cc: rbridge at postel.org
Subject: Re: [rbridge] On Nick-Names

I think it should be done based on choosing them at random, (rather than
some substring of the MAC address) and if someone with higher priority
asks for the same nickname you did, you have to choose a different one. 
Priority is
based on lower MAC address.

It will converge more quickly if the nickname space is not very densely
used of course. But I really think that people are not talking about
building campuses with more than 1000 RBridges, so with 16 bits it
wouldn't be densely assigned.

Radia

Gray, Eric wrote:

>Folks,
>
>Another thing to consider in potentially reducing the size of the 
>RBridge ID name space is that reducing the number of bits also 
>increases the probability of "name collisions" during the process of 
>nick-name negotiation - further complicating the RBridge interactions 
>by increasing the probability that "name collisions" will result in 
>multiple retries.
>
>Last I heard, the protocol specification was going to spell out how 
>nick-names would be negotiated.  As I understand it, the plan was to 
>assert a nick-name based on some substring of the MAC-derived system 
>ID.  Since this is at least 48 bits (with perhaps fewer bits relevantly

>significant), a reduction to 19 bits was felt to introduce a collision 
>probability that is not too bad.
>
>Do people feel that collisions are likely to remain rare if the name 
>space is reduced to 16 bits?  IMO, that may be an unreasonable 
>assumption...
>
>--
>Eric