Subject: [rbridge] On Nick-Names

From: Eric.Gray at marconi.com (Gray, Eric)
Date: Thu, 2 Nov 2006 17:19:32 -0500

Donald,

	Yes, this sounds familiar.  There are issues with this 
negotiation approach, however.  For example, because it is 
non-determinstic, some of the assumptions in this text are 
either incorrect, or subject to race-conditions.

	For example, the statement "once it is stable, nicknames 
should remain stable even as routers go up or down" appears to 
either assume that a nick-name is presistent across a system's
reset/reboot, or assume that this approach will (somehow) result
in selecting the same nick-names again.

	Also, the statement "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" seems to have built-in difficulty
in boot-strapping.  Exactly _how_ does this occur without the 
possibility of two devices each believing the other is the one 
doing the "usurping"? 

	I am also very uncomfortable with the idea of allowing any
implementation choice possible, for nick-name selection, to be 
used, under the assumption that convergence will eventually 
happen, and that persistant nick-names will be a natural result
of this chaotic assumption.

--> -----Original Message-----
--> From: Eastlake III Donald-LDE008 
--> [mailto:Donald.Eastlake at motorola.com] 
--> Sent: Thursday, November 02, 2006 1:03 AM
--> To: Radia Perlman; Gray, Eric
--> Cc: rbridge at postel.org
--> Subject: RE: [rbridge] On Nick-Names
--> 
--> 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 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:
--> 
--> >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
--> >_______________________________________________
--> >rbridge mailing list
--> >rbridge at postel.org
--> >http://mailman.postel.org/mailman/listinfo/rbridge
--> >  
--> >
--> 
--> _______________________________________________
--> rbridge mailing list
--> rbridge at postel.org
--> http://mailman.postel.org/mailman/listinfo/rbridge
-->

---

From: caitlinb at broadcom.com (Caitlin Bestler)
Date: Thu, 2 Nov 2006 14:36:57 -0800

rbridge-bounces at postel.org wrote:
> 	For example, the statement "once it is stable,
> nicknames should remain stable even as routers go up or down"
> appears to either assume that a nick-name is presistent
> across a system's reset/reboot, or assume that this approach
> will (somehow) result in selecting the same nick-names again.
> 
> 	Also, the statement "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" seems to have
> built-in difficulty in boot-strapping.  Exactly _how_ does
> this occur without the possibility of two devices each
> believing the other is the one doing the "usurping"?
> 
> 	I am also very uncomfortable with the idea of allowing
> any implementation choice possible, for nick-name selection,
> to be used, under the assumption that convergence will
> eventually happen, and that persistant nick-names will be a
> natural result of this chaotic assumption.
> 
Why not explicitly state that an RBridge SHOULD use its
prior nick-name as its first choice after a reset/reboot?