Subject: [Isis-wg] Running SPF

From: "Sugar, Sylvia" <[email-masked]>
Date: Mon, 21 Feb 2005 13:20:19 +0000 (GMT)

Hi,

When i run my SPF is it fair to add all my connected adjacencies directly to the TENTs, without
checking if they are already in the PATHs? Is it ever possible for a directly connected neighbor
to be in the PATHs already and us getting this information again?

Also when processing pseudonode LSPs, is there anything special that we need to take care of? In
our implementation we process the LSPs from our adjacent neighbor and then look for the pseudonode
LSP if it exists. If yes, then I am thinking of adding the neighbors listed in the pseudonode LSPs
directly to the PATHs.

Is this correct interpretation of the ISO 10589 and RFC 1195 standard?

Sylvia

___________________________________________________________ 
ALL-NEW Yahoo! Messenger - all new features - even more fun! http://uk.messenger.yahoo.com

_______________________________________________
Isis-wg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/isis-wg

---

From: Radia Perlman <[email-masked]>
Date: Mon, 21 Feb 2005 10:52:55 -0800

>to be in the PATHs already and us getting this information again?
Yes, you may very well find more paths, and if you don't check if 
something is
already in PATH, you would not be doing correct behavior.
Being in PATHs says that this is the best path from you (S)
to target T. You might find lots more paths to T, which will all be 
worse than the path
in PATHs, but if your implementation keeps looking for "the shortest 
path still in TENT"
and looking at paths through that, you'll never terminate.

Radia

---

From: Radia Perlman <[email-masked]>
Date: Tue, 22 Feb 2005 08:32:48 -0800

Mike...maybe you and I interpreted the original quesiton differently.
There's no problem with doing what you said, but what I thought he
was asking was ignoring the check, during the run of SPF, to see if
a node was already in PATHs. With my interpretation of his question,
I think the algorithm would keep finding longer paths. I suppose if
when you put something from TENT into PATH, if you then looked to
see if that node was already in PATH it would terminate, but it would
be quite inefficient to explore a longer path to D once you have already
found the shortest path to D.

Anyway, you and I are not disagreeing...we're just answering different
questions. Hope one of us has interpreted his question correctly.

Radia

mike shand wrote:
> At 10:52 21/02/2005 -0800, Radia Perlman wrote:
> 
> 
> 
>>Sugar, Sylvia wrote:
>>
>>
>>>Hi,
>>>
>>Yes, you may very well find more paths, and if you don't check if something is
>>to target T. You might find lots more paths to T, which will all be worse 
>>than the path
>>in PATHs, but if your implementation keeps looking for "the shortest path 
>>still in TENT"
> I'm confused. Surely adding all your directly connected adjacencies to TENT 
> is exactly equivalent to processing you own LSP first and then adding the 
> contents to TENT. Or are you suggesting your own LSP may have a different 
> content than your adjacency set?
> 
> I must be misunderstanding something.
> 
> 
> 
>>Radia
>>
>>
>>
>>

---

From: mike shand <[email-masked]>
Date: Tue, 22 Feb 2005 17:28:16 +0000

>found the shortest path to D.

I agree.

>questions. Hope one of us has interpreted his question correctly.

Yes. Whichever it was, we have between us provided a correct answer to it :-)

         Mike

---

From: mike shand <[email-masked]>
Date: Tue, 22 Feb 2005 09:09:51 +0000

>listed in the pseudonode LSPs

The normal way to do this is to treat the pseudonode as a normal node, with 
the exception that if there are multiple nodes with the same (lowest) cost 
at the top of TENT you should choose a pseudonode in preference to a 
non-pseudonode. If you don't do this you will not find the equal cost paths 
correctly.

I don't really follow what you are proposing, but the "adding the nodes 
listing in the psuodonode LSPs directly to PATHs" doesn't sound right.

         Mike

---

From: stefano previdi <[email-masked]>
Date: Tue, 22 Feb 2005 11:04:10 +0100

> already in PATH, you would not be doing correct behavior.

I'm not sure but I believe here we are referring to the adjacent 
neighbors
of the router computing SPF. In such case I would say that:

- The only place in SPF algorithm where the computing router moves its
   adjacent neighbors in TENT is when the algorithm starts:

	- step-0: tent and paths are empty
	- step-1: move myself to tent
	- step-2: move best node from tent to paths (i.e.: move myself to 
paths)

	<at this stage TENT is empty and PATHS only contains one node: myself>

	- step-3: move my neighbors to tent
	- ....

- Therefore, at the time the computing node moves its neighbors in TENT,
   TENT is always empty so the check is not strictly necessary.

Having said that, from an implementation perspective, the check is
probably always done since the SPF processing loop starts at step-2
and step-2 applies to all nodes, not only ourselves.

s.

---

From: mike shand <[email-masked]>
Date: Tue, 22 Feb 2005 08:59:17 +0000