Subject: Re: [rbridge] multiple nicknames in an LSP?

From: Donald Eastlake <[email-masked]>
Date: Wed, 1 Apr 2009 21:10:32 -0400

There seem to be a number of complexities in this idea but no big
advantages obvious to me over just using multiple trees with different
roots.

Complexities include the question of whether these multiple nicknames
for the same RBridge have different or similar priorities (priorities
for the RBridge to hold that nickname). Note that one of the nicknames
could collide and have to be changes while the other might not...

Then there is the need to have a different tie breaker, otherwise you
don't get different trees. So how is this new and different tie
breaker going to work? Tie breaking can be thought of as comparing the
value of a function of various parameters related to the links between
which the choice is being made. The current function is the identity
function of the system ID at the other end of the link. So what's the
new function? MD5 ( SystemID, root nickname )?

And why are we doing all this instead of just having more trees rooted
at other RBridges?

Donald

See also comment below.

On Sun, Mar 29, 2009 at 2:30 PM, Radia Perlman <[email-masked]> wrote:
> The point someone was making is that they want multiple trees rooted at
> the same place (say R1)
> where all the trees are shortest path trees from R1, but that they use
> different links. The only way to
> do that is to have different tie breakers where there are choices. The
> way the spec is currently,
> the tie-breaker would be the same, so all the trees rooted at R1 would
> be identical.
>
> But anyway, for now, should we allow the encoding of the nickname TLV to
> allow asking for multiple
> nicknames?
>
> Seems not too hard..given that there is an "L" in the TLV.
>
> Is there anyone who would object to this? Is there anyone who would
> actually want this?
>
> Radia
>
>
> Ayan Banerjee wrote:
>> Radia,
>>
>> Please see inline.
>>
>> Thanks,
>> Ayan
>>
>>
>> On 3/25/09 10:12 AM, "Radia Perlman" <[email-masked]> wrote:
>>
>>
>>> Someone asked me about whether it would be possible for an RBridge to
>>> request more
>>> than one nickname for itself. We could, I suppose, put in the encoding
>>> into the Hello, perhaps
>>> by changing the format of the TLV for "nickname", or just inherently
>>> from the length of the TLV,
>>> allowing a list of nicknames.
>>>
>>> So...the question is -- why might we want multiple nicknames?
>>>
>>> Some reasons people have mentioned to me I'm not sure I understand, so
>>> people can add them.
>>> Other layer 2-ish protocols play tricks with having multiple destination
>>> addresses, I think for
>>> allowing multiple routes to the same destination. I'm not sure those
>>> apply to TRILL
>>>
>>> One reason I do understand, but am not sure I understand how to
>>> accomplish it, is to allow
>>> multiple trees rooted at the same node R1, with the hope that the two
>>> trees can look different (for load
>>> sharing) and yet both be shortest paths from R1. If we had two nicknames
>>> for R1 then R1 can
>>> request some multicast packets travel on each of the trees.
>>>
>>> It's harder than just having the nicknames, because the way the spec
>>> reads today, exactly the same
>>> tree would be computed.
>>>
>>> I'd have to go thinking about this some more, and I think it would be an
>>> excellent research problem for
>>> a student -- how to calculate, without configuration, maximally load
>>> sharing'ness of trees rooted at the same
>>> place, or choosing which nodes to root trees on, etc.
>>>
>>> But here's a quick suggestion, just to show it's somewhat possible:
>>>
>>> Use the root nickname (or root ID, or some other field we can add to the
>>> LSP as a modifier
>>> of the nickname) as a way of doing the tie-breaker.
>>>
>>> so for instance, R1 can say "I want nicknames N1 and N2. I'd like the
>>> tiebreaker salt to be x for N1
>>> and y for N2".
>>>
>>> Then when the tree rooted at N1 is being computed (by any RBridge),
>>> rather than choosing the
>>> ID of the parent as the tie-breaker (as it is today I think), use some
>>> sort of function of
>>> the salt, so that the tie-breaker would be different for the N1 tree
>>> than the N2 tree.
>>
>> [AB] It seems to me that given we have roots tied to graph-ids, we could
>> associate N1 to a graph-id and that makes it "visible" only on that
>> graph-id. Hence, other nodes computing their SPFs will see N1 only in
>> graph-1 and N2 only in graph-2. I am guessing that you are essentially
>> saying the same above, though I do not quite follow the tie-breaker. If it
>> is explicit, node R1 can enforce multicast packets on trees that it desires.

Hi Ayan, I don't understand what you are saying above. It makes no
difference with the current tie breaker what the root of a tree is
called. If the tree is calculated in the same way, it will use the
identical links. The only way I can see to make the trees different
through different root RBridge nicknames is to make the tie breaker
decisions depend in some complex way on a function which takes as one
of its inputs the root RBridge nickname.

>>> Radia
>> _______________________________________________
>> rbridge mailing list
>> [email-masked]
>> http://mailman.postel.org/mailman/listinfo/rbridge

=============================
 Donald E. Eastlake 3rd   +1-508-634-2066 (home)
 155 Beaver Street
 Milford, MA 01757 USA
 [email-masked]
_______________________________________________
rbridge mailing list
[email-masked]
http://mailman.postel.org/mailman/listinfo/rbridge

---

From: Radia Perlman <[email-masked]>
Date: Thu, 02 Apr 2009 00:31:20 -0700

> And why are we doing all this instead of just having more trees rooted

On the theory that you want multiple shortest path trees from R1. If you 
calculate a tree from
a different root, the paths from R1 might not be so great. If you really 
just want to load split
traffic emanating from R1, you'd want shortest paths from R1 -- that's 
the theory, but as you
point out, we need some sort of tie breaker that is different for each 
nickname, either using
the nickname itself as a salt for tie breaking, or an explicit salt, or 
something else (like the
order in which the nicknames are listed in R1's LSP).

And as you point out, there are other issues, like whether there is a 
separate priority for each nickname, or
whatever...

Radia

---

From: Radia Perlman <[email-masked]>
Date: Sun, 05 Apr 2009 12:32:40 -0700

After thinking about this some more, I do like the idea of having 
different tiebreakers for different roots.
Without doing simulations, etc., I don't know what the real gains are, 
but intuition says that if
the parent with lowest ID is always chosen in a tie-breaker, that nodes 
with lower IDs will have more children,
and traffic won't be spread as well.

So...the questions are:
a) whether we use the nickname number as the salt (the thing that will 
influence the tie-breaker
differently in different trees)
b) have explicit salt,
c) allow acquisition of multiple nicknames

Having explicit salt changes the packet format, and since we do have the 
ability to configure nicknames, I think
we should just use the nickname number.

Allowing multiple nicknames seems harmless, and might be useful.

So I'd suggest that we say:
a) the nickname TLV can have multiple nicknames, and the number of them is
determined based on the "L".
b) the tie-breaker is, that when calculating a particular tree from root 
nicknamed
"R": if node N has k particular parents, then you sort the IDs of the 
parents, and
take the Nth one, mod k.

If we are going to do this, it has to be now, because otherwise we'd 
never be
able to interwork if some RBridges are calculating trees differently.

Radia

---

From: Joe Touch <[email-masked]>
Date: Mon, 06 Apr 2009 08:28:48 -0700

Hi, Radia, et al.,

Any mechanism for tiebreaking necessarily needs to use a single
identifier, whether that's a single namespace or the concatenation of
namespaces.

Regardless of the names used, low-named parents will have more children.
There's no way around that.

Using configurable values for tie-breaking is dangerous due to the
impact of misconfiguration, e.g., when values are duplicated. If such
names are used as *part* of the tiebreaking, a more conventional value
(e.g., the ID) should be used to "tie-break the tiebreaker" in the case
of duplicates. However, as per my second note above, it's not clear why
this is a win.

Joe

---

From: Donald Eastlake <[email-masked]>
Date: Mon, 6 Apr 2009 12:02:30 -0400

Hi Joe,

To be a bit more particular and precise, if you are building a tree
rooted at the RBridge with nickname N and in the process come across
an RBridge with k equal cost parents with System IDs ID0, ID1, ID2,
..., ID(k-1), you sort those potential system IDs as unsigned
integers, then you divide N by k and use the remainder to select from
the ordered list. Assuming there were multiple trees whose
construction encountered RBridges with that same set of potential
equal cost parents, the selections for the different trees will be at
least somewhat randomly distributed over the ID0...ID(k-1) set,
including trees for different nicknames that were might be given to
the same distribution tree root RBridge.

Donald

On Mon, Apr 6, 2009 at 11:28 AM, Joe Touch <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi, Radia, et al.,
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (MingW32)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iEYEARECAAYFAknaH7AACgkQE5f5cImnZrs+xwCbByCVp1lLiSvPlhiBh8PVOzJL
> SzcAoMWliDN0vZzyVkhueR2TF45y22Fa
> =F1NZ
> -----END PGP SIGNATURE-----

--

---

From: Dinesh G Dutt <[email-masked]>
Date: Mon, 06 Apr 2009 10:54:57 -0700

Radia,

> c) allow acquisition of multiple nicknames
I'm in favor of (a) and (c). Explicit salt or some other implicit scheme 
is OK with me, though explicit salt seems superior.

The main reason we need (a) is as you point out, for multi-destination 
frames, we don't get utilization of all links in the network. Two trees, 
associated with two different switches, could both choose the same set 
of links largely negating the advantage of multiple trees.

The reason I want (c) too is because I'm aware of networks where the 
number of optimal roots is small enough that it results in many nodes 
not using all their links for multi-destination frames. Choosing a 
different set of roots results in an unscalable number of trees. Having 
the optimal roots pick multiple nicknames solves the problem.

Dinesh

-- 
We make our world significant by the courage of our questions and by 
the depth of our answers.                               - Carl Sagan

---

From: "Anoop Ghanwani" <[email-masked]>
Date: Mon, 6 Apr 2009 12:43:44 -0700

I don't have a preference for (a) or (b),
but (c) definitely seems like a good idea.

Anoop 

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Dinesh G Dutt
> Sent: Monday, April 06, 2009 10:55 AM
> To: Radia Perlman
> Cc: TRILL/RBridge Working Group
> Subject: Re: [rbridge] Fancier tie-breaking in trees for more 
> load-splitting, plus multiple nicknames
> 
> Radia,
> 
> Radia Perlman wrote:
> > So...the questions are: