sequence numbers in routing information messages

[Martha Steenstrup <[e-mail]>]

Hi Woody,

A bit of history: 

To be useful, routing information message identifiers must always
distinguish new routing information messages from old.  If these
identifiers can wrap around, then recency is harder to determine.
Options for handling identifier wrapping include:
- annihilator messages used to wipe out all traces of a particular
  message in the routing information database in each route server
  and policy gateway (as in OSPF);
- new public/private keys used to sign messages at the node whose
  identifier has wrapped (as suggested by Radia Perlman in her thesis).

For IDPR routing information we decided to use identifiers that we
expected would always increase during the life of the protocol.
Hence, we decided on 32-bit timestamps (in fact UNIX-like timestamps)
with the granularity of seconds as the identifiers for routing
information messages.  We also added a 16-bit sequence number field to
enable a policy gateway to generate more than one routing information
message at a given time (for example, to handle a situation in which
its clock is frozen during clock resynchronization).  All of this was
designed before CMTP.

While I believe that in practice, the CMTP transaction identifier
would adequately serve as the routing information message identifier,
I have some reservations about them being non-increasing as follows.

If the CMTP transaction identifier were non-volatile, that is, if a
policy gateway could remember its current transaction identifier even
when the policy gateway was removed from service, then we wouldn't
have to worry about non-increasing identifiers.  Moreover, I doubt
that a CMTP transaction identifier would wrap during the lifetime of
IDPR, even at very busy policy gateways.  However, I don't think that
we can be sure that each policy gateway will be able to remember its
current CMTP transaction identifier during a power failure, for
example.  Hence, I expect a reset to 0 after each failure and hence
non-increasing identifiers for routing information messages.

Assuming that the transaction identifier is volatile, we would then
need a negotiation procedure to execute with neighbor policy gateways
for incrementing the policy gateway transaction identifier to the
value it had before the failure.  Actually, an analogous procedure is
already part of the IDPR routing information distribution protocol,
not for the transaction identifier, but for updating the routing
information database of a policy gateway.  This does complicate the
notion of the CMTP transaction identifier as a simple counter, as
negotiation would happen whenever a policy gateway generated a routing
information message after that policy gateway had returned to service
following a failure.

None of this is to say that we couldn't use the CMTP transaction
identifiers as routing information message identifiers.  However, I am
saying that it does complicate the implementation a little bit.  The
advantages of using transaction identifiers are:
- The removal of the 16-bit sequence number field from the routing
  information message.  This will save link bandwidth and memory space
  in the routing information database.  The amount saved depends on
  the boundaries to which you pad.
- Generation of unique routing information message identifiers
  during a clock freeze without any special fields.
The disadvantages are:
- Renegotiation of the transaction identifier following a policy gateway
  failure.
- Tying the identifier to the IDPR control message transport mechanism.
  If CMTP were to change or be replaced, we would end up having to generate
  an identifier in the routing information message protocol itself (as
  we now do currently).

At this point, I would be hesitant to change your gated software.  As
far as changing the protocols themselves, that is a toss up.  I am
leaning toward leaving the protocol as is, because of my concern about
tying the routing information message identifier to a value
computed by another protocol.  Any comments?

m