[RRG] On guaranteeing that route/map state changes propagate

["William Herrin" <bill@herrin.us>]

Hi Folks,

From recent conversations, it strikes me that we could usefully
discuss what kinds of systems do (and do not) guarantee that knowledge
of a state change (in this case a route or a map) propagates to all
interested parties. A canonical list could help us make a first cut as
we evaluate proposals to trim BGP, expand multihoming and enable
mobility. I'll get the ball rolling:


Monolithic Push guarantees that state change propagates.

If every node carries the entire route-state knowledge, changes can be
sequenced in lockstep with neighbor-to-neighbor verification so that
absent an intentional filter state changes will propagate within A*N
where A is the time it takes for a neighbor to receive and process a
change and N is the longest node chain from one side of the system to
the other. If something does fall out of sequence, it's obvious and a
node can refresh the full data set from its neighbors.

Major benefits: Nodes can make decisions immediately because they
already have the system state knowledge.
Major liabilities: Scales poorly. High cost is a barrier to entry.

Example: BGP


Monolithic Push with the edge node exception guarantees that state
change propagates.

Same as above except that edge nodes where all neighbors are upstream
for all non-local destinations can sacrifice state information at the
expense of a mild loss of efficiency.

Major benefits: Nodes can make decisions immediately because they
already have the system state knowledge.
Major liabilities: Still scales poorly.

Example: BGP with a default route sent to the customer.


Pulled Cache with Time to Live (timeout) guarantees that state change
propagates.

If every entry in a node's working set of destinations with which it
is communicating will time out within some fixed period of time X
after which it must be re-requested from an authoritative source then
any state change will propagate to interested nodes in no more than X.

Major benefits: Unbounded scalability with respect to the total system state.
Major liabilities: Delay for initial lookup. Overhead cost to refresh
the working set.

Example: DNS


Pulled Cache with Change Notification DOES NOT guarantee that state
change propagates.

With change notification, someone has to remember which caches are
currently subscribed to knowledge about which states. Should that
memory agent fail, the cache will retain state knowledge when no one
else knows that it needs to receive updates.



Comments? Criticisms? Should the scope of some of these claims be
narrowed or expanded? Evidence for or against, or do we have
consensus?

Are there additional approaches distinct from the above that guarantee
that state changes propagate?

Are there additional approaches which merit mention because they seem
promising but -fail- to guarantee that state changes propagate? I note
that such methods could offer useful assists when used as a supplement
to a method which does make the guarantee.

Your input is solicited. I'll keep a running tally at
http://bill.herrin.us/network/statechange.html


Regards,
Bill Herrin



-- 
William D. Herrin herrin@dirtside.com bill@herrin.us
3005 Crane Dr. Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg