Subject: [NSIS] Message Looping in GIMPS

From: "Hancock, Robert" <[email-masked]>
Date: Wed, 17 Mar 2004 15:47:28 -0000

Hi all,

One of Dave Oran's early review comments was (from the email)

> - What led to the decision to use a hop count rather 
>   than a VIA-style path recording?

and from the discussion at the meeting, the issues were
- a VIA mechanism can prune a loop much faster than a hop count
  (and this is the main purpose of the hop count)
- route recording might end up being used (and thus re-invented)
  by many signalling applications anyway

After some thought, at the moment I think that the current
function split between GIMPS and signalling applications is
right and that it is right for GIMPS to use a counter based
mechanism for loop handling. But the argument is quite detailed.

r.

argument follows:

Looping
-------

Message looping can happen at (at least) 3 levels:
1. normal packet looping at the IP level.
2. a message looping around a set of GIMPS-aware nodes without
   finding a signalling application node to be delivered to.
3. messages looping between instances of a signalling application.

(1) is out of our hands; we know it will happen (at least
transiently) and that the IP TTL will sort things out.

(2) - if it happens even after (1) has been dealt with -
has to be handled by GIMPS. Then the question is whether
to handle it with a hop count or VIA mechanism. (But it is not
immediately obvious that (2) can happen, see below.)

(3) could be handled by each signalling application; or,
GIMPS could provide a common service. And in the second
case, it could use the same mechanism used for (2), or
a different mechanism.

Does GIMPS *need* an internal loop-prevention mechanism?
--------------------------------------------------------

One might think that case (2) could never arise (except as 
a side effect of packet looping). Firstly, a discovery message
is supposed to be forwarded precisely like any other IP 
packet; secondly, we would like to have the situation where
the GIMPS routing state refers to [and messaging associations run 
directly between] signalling application peers. So, either things
are handled in the IP layer; or, the looping happens between
instances of the signalling application in question - no pure
GIMPS loops are possible.

However, even in the current design, discovery messages are
not handled exactly like IP datagrams, because of the policy
routing/load balancing problem. If a network implements pf/lb in
all its nodes but only some of them are GIMPS aware, discovery
messages will be forwarded according to their IP header in the
GIMPS unaware nodes but according the flow identifier in the
GIMPS aware nodes; therefore, loops are possible. (I think this
could probably be counted a pathological condition but it can't
be ruled out. In particular, such loops, if they did occur, 
probably would not be transient.)

In addition, it is still possible that people may want to build
networks where C-mode associations are used to trunk signalling
messages through GIMPS-only nodes, or there may be other message
routing mechanisms added later (e.g. for the path-decoupled case).
Once we loosen the connection with IP routing, loop prevention at
the GIMPS level becomes a requirement. 

So, loop prevention within GIMPS for looping at level (2) is needed.

How to do loop prevention within GIMPS?
---------------------------------------

We have a choice here between hop counting and route recording.

There are several trade-offs to make here. If we leave aside the
possibility that applications would want route recording for their
own purposes for now, the issue is of which design option is most
appropriate within GIMPS. I think several aspects point at a hop
count being more appropriate:

*) it's fast. loop detection will be being done mainly on
datagram messages discovering the next NSLP-aware hop, and we know
this is a sensitive area for router performance (people would like
to do this "get this message past a node which doesn't care about
it" in the fast path if possible). So, a check&decrement of a 
counter (in the fixed header) is preferable to scanning a route
record for an identity and inserting a new field.

*) we expect looping to be rare (it shouldn't come about through
GIMPS misconfiguration, initially only pathological IP pf/lb 
situations) so detecting it early and efficiently (which a VIA
mechanism would do) is less important than making the cost of the
processing low.

*) it doesn't lead to message expansion. discovery mode messages
are size limited, and adding route records may make them hard to
propagate. or, people might want to start record trimming and so
on.

*) it's simple. we don't have to get into worries about topology
hiding, what namespaces to use for node identities.

So, I would propose to keep the GHC as a loop detection mechanism
within the GIMPS layer. (Obviously, the rules about how to process
it need to be specified more precisely.) This can then also be used
as *one* weapon to handle message looping at the signalling application
layer (since NSLPs can read and set the GHC in their messages).

Should GIMPS provide route recording as a service?
--------------------------------------------------

Despite all this, it is still possible (likely?) that there is 
a use for route recording for various purposes for use by
signalling applications. That may be for loop detection or
something else. Loops may be caused by negotiation loops within
a single instance of a NSLP (between peers or over a longer
distance), or by feedback between microflow and aggregate signalling,
or any other sort of reason, and the GHC may not be suitable or
powerful enough to handle this. We could make a recording mechanism
almost directly out of the comparable functionality in SIP or
Diameter.

However, I think this functionality comes into the same class as
some other items of 'generally useful signalling protocol' function,
like state refresh management or MLPP: it may be useful for several
signalling applications, but doesn't have a significant interaction
with the other functions within GIMPS itself. Exactly how to make
such re-usable components is an interesting question, but our
assumption within NSIS (up to now) is that it is a question for the
signalling application layer, not for the NTLP layer.

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

---

From: Henning Schulzrinne <[email-masked]>
Date: Wed, 17 Mar 2004 20:54:26 -0500

> GIMPS loops are possible.

I think it's more precise to say that loops are possible, just no 
*infinite* loops. I.e., a packet can circle around the block a few 
times, but it will eventually be dropped on the floor. If the loop is 
tight, it can circle quite a few times.

> probably would not be transient.)

I don't see how this is different. IP TTL will have the same effect in 
either case. Given that the flow label is part of the header, I'm 
confused by the distinction.

> the GIMPS level becomes a requirement. 

That is indeed the more likely concern, in addition to efficiency.

> layer (since NSLPs can read and set the GHC in their messages).

Note that SIP simply chose to do both, since they have complementary 
properties (speed of inspection vs. early discovery and better 
diagnostics). I don't see why we couldn't *allow* (not mandate) that if 
route-recording is used, that entities can inspect this and use it to 
discover loops.

(As a side note: In SIP, we had to deal with 'spirals', where messages 
would visit the same node twice, after modification. I don't think this 
is likely to occur here.)

> Should GIMPS provide route recording as a service?

I respectfully disagree. Since we'd want to be able to record every NTLP 
hop, not just every NSLP hop, it makes sense to offer this as an 
optional service within NTLP.