Tuesday December 16, 2008 Random ramblings
Tuesday December 16, 2008 I'm curious if there's any well-reasoned argument, preferably with data, that shows that constructing a giant conspiracy to get kids to believe that a fat man delivers presents to kids across the world, in one night, in a flying, reindeer-driven sled, is a good idea, does anyone know?
Maybe it's just me, but it confused me greatly that all these adults enjoyed lying to me to make me think men in obviously fake beards knew whether I was good or not.
These same adults who would tell me lying was bad and chastise me if I did so. That I was asked to believe in two different variants of the beardy-with-presents story1 didn't aid its credibility Also, it distressed my poor little sister, who was completely enthralled by the whole thing, terribly when she found out at age 4 or 5 or so that there was no Santa (it might have been me who told her - she hasn't forgiven me to this day). 
Perhap's there's some parental joy to be had in deceiving your child so fully, that I havn't yet had the chance to experience.. Does this Santa conspiracy really serve children, or more the adults?
1. The other one, Sinter Klaas, was a bit less fantastical and more plausible though. He was a bishop and dressed like those funny old men you'd see in church sometimes; he arrived by boat from Spain, with a bunch of Moorish helpers; he'd arrive a week or more in advance; he travelled the country on a white horse traditionally, but would avail of modern transport; he left the presents on your front-door step on the evening of the 6th of December. A sceptical child could still imagine he distributed the presents in advance, with the parents colluding in the final delivery (my uncle always disappeared before the knock on the door, I noticed). Still, I couldn't quite understand why adults so enjoyed us believing in this strange beardy - but it didn't matter as long as I got presents.
( Dec 16 2008, 04:03:57 PM GMT ) Permalink Comments [5]Choosing better BGP MRAI values
The IETF IDR working group is hopefully in the process of deprecating the default MRAI values given in [RFC4271]. The below text is from a defunct draft I wrote on what is known about the MRAI, with minor modifications to reflect some of the discussion on IDR. It suggests that 5s would be a better value for the general Internet, BGP MRAI (1s or lower for iBGP). Posted here for archival purposes.
Background
The proper functioning of the [BGP] routing protocol is of great importance to the Internet. Issues regarding matters of its stability and convergence have been documented widely, such as in [BGP-STAB], [bgp-converge] and [Potaroo0607].
One such issue is the effect of 'Minimum Route Advertisement Interval' (MRAI).
The MRAI Timer
The Minimum Route Advertisement Interval (MRAI) timer is specified in [RFC4271]. This timer acts to rate-limit updates, on a per-destination basis. [BGP] suggests values of 30s and 5s for this interval for eBGP and iBGP respectively. The MRAI must also be applied to withdrawals according to [RFC4271], a change from the earlier RFC1771.
Some implementations apply this rate-limiting on a per-peer basis, presumably an adequate approximation. Some implementations apply it to withdrawal methods (often called "WRATE" in the literature). Some implementations do not apply MRAI at all.
Known effects of the MRAI timer on convergence
The MRAI timer serves to suppress messages which BGP would otherwise send out to describe transitory states, and so allow BGP to converge with significantly fewer messages sent. This beneficial effect of the MRAI timer, in terms of # of messages, increases as the timer is increased until an optimum value is reached, after which the beneficial effect stabilises. [bgp-converge] [mrai-final]
In terms of convergence time, a similar beneficial effect is seen as the MRAI increases to near the same optimum value. However as the timer value is increased past this point, the convergence time increases again linearly. The scale of this increase is significantly worse with WRATE, i.e. applying the MRAI to withdrawals has an adverse effect on BGP convergence time. [bgp-converge] [mrai-final]
The optimum MRAI timer value is dependent on several factors, most particularly the topology in its layout and propagation times. The optimum value will differ between different subsets of the Internet. [mrai-final]
It is believed to be infeasible to try directly calculate this value. However a useful approximation can be made from the diameter of the topology if it is known, along with some assumptions about the the topology, such as the latency between nodes. [mrai-internet]
The interaction between extensions to BGP designed to improve convergence, such as those that allow propagation of additional and/or backup paths, and the MRAI timer is as yet unknown. However, it seems reasonable to speculate these extensions might have the effect of leading to a lower optimum MRAI than would be indicated by an approximation based on the diameter of the BGP topology. Further work on these questions would be useful.
Interaction with Flap-Damping
As the MRAI helps eliminate some updates, it interacts with flap-damping. The lower the MRAI timer, the greater the risk of crossing below the threshold of the optimum value. If that threshold is crossed, there will be an increased number of updates somewhere within the BGP system, and hence an increased risk of paths being dampened which otherwise would not.
So, in presence of significant flap-damping deployment and given the uncertainty of what the optimum is, it is reasonable to err towards selecting a value of the MRAI timer significantly higher than the optimum.
However, given that flap-damping increasingly is discouraged [RIPE-378] in Internet routing, this particular need to be conservative in the choice of MRAI timer value may be less important.
Current Status of the MRAI
The current recommended value of 30s may be far higher than is optimal for the Internet, based on observations of certain parameters related to its topology. In [mrai-final] it is suggested that the optimal value may be between 5s ('semi-safe') to 15s ('safe'). The estimation of the 'safe' value here is of no relevance if WRATE is universally deployed, as in such a case the 'semi-safe' value will be the same as the 'safe' value. Further empirical work by the same authors [mrai-internet] suggests that the optimal, Internet MRAI may be below 5s.
Further, [BGP-STAB] and [Potaroo0607] argue that operational conditions (e.g. different routers using different MRAI values) mean the MRAI is having an adverse effect even on the number of messages sent, and so further exacerbating convergence problems in the global BGP system, such as path hunting. The [BGP-STAB] document goes further still and argues that MRAI be deprecated in favour of some better way of damping BGP UPDATES, however there are no clear proposals before the IDR as of this writing for such changes to BGP.
Risk Evaluation in the Choice of MRAI Time
Though there is an optimum value for the MRAI, it's unlikely that it can be determined empirically or otherwise for the general Internet. It may even not be possible, as the optimum MRAI will differ for different subsets of the Internet. Some degree of guesstimation at a reasonable value for the MRAI is required, which is an exercise in risk; whether to err towards fast convergence at the risk of a disproportionate increase in BGP messaging, or to err to the side of an optimal number of messages at the expense of convergence.
Arguably, economising on bandwidth and control-plane processing power is of less importance than the convergence time of BGP, compared to times past. Presuming this, any new recommendations for the MRAI should seek to err slightly to the side of convergence, rather than erring towards minimising BGP traffic.
Further, if we assume most implementations apply the MRAI to withdrawals, then the Internet BGP topology effectively is WRATE-enabled, and [mrai-final] suggests there is even less benefit to erring toward a higher MRAI.
There may be risks in mismatched MRAI values between speakers in an AS as revised MRAI values are deployed. The MRAI values in [RFC4271] were deliberately specified to be lower for iBGP than for eBGP, so as to allow interior routing to converge while minimising the effect on eBGP state. So with mismatched values there is an increased risk that the external stability of an AS's routes would be affected by transient, internal states.
This last risk suggests that the existing iBGP/VPN values should be the lower-bound for any conservative revision of the eBGP MRAI value.
The most definite risk of lowering the MRAI is the increased risk of flap-damping, if the value is set too much below the optimum. Therefore, taking into account estimations of that optimum is required. That said, at least one BGP implementation by default does not apply any MRAI at all.
Recommendations on the MRAI
The suggested default values for the MinRouteAdvertisementIntervalTimer given in [RFC4271] are almost certainly too high. The author agrees with [mrai-internet] and suggests that values 5s or less for eBGP connections, and 1s or less for iBGP connections, would be more suited to Internet topologies. Opinions here differ, some think these values err too low for safety and others think the MRAI timer should be removed altogether.
These values may not be suitable for topologies which differ from the Internet, be that in scale, arrangement or otherwise. Such non-Internet, BGP topologies likely would have lower optimum values, assuming they are always significantly smaller in scale than the Internet BGP topology.
Acknowledgements
The author would like to thank Manav Bhatia for his helpful review and comments; as well as Robert Raszuk, Samita Chakrabarti, Danny McPherson and Jeffrey Haas for their useful comments; dissenting or otherwise.
The authors of the cited documents are thanked for their contributions to the understanding of BGP, of which this document is a simple summary.
References
BGP: A Border Gateway Protocol 4 (BGP-4) Y. Rekhter, T. Li and S. Hares, January 2006.
BGP-STAB: BGP Stability Improvements, T. Li and G. Huston, June 2007.
BGP-DAMP: BGP Route Flap Damping, C. Villamizar, R. Chandra and R. Govindan, Nov. 1998.
Potaroo0607: Damping BGP G. Huston, June 2007.
RIPE-378: RIPE RRG: Recommendations on Route-flap Damping P. Smith, C. Panigl, May 2006.
bgp-converge: An Experimental Analysis of BGP Convergence Time T. Griffin and B. Premore, Nov. 2001, Proc. of ICNP pages 53-61.
mrai-final: An Experimental Study of the BGP Rate-limiting Timer J. Qui, R. Hao and X. Li, June 2003, Bell Labs Technical Memo ITD-03-44604H.
mrai-internet: The Optimal Rate-Limiting Timer of BGP for Routing Convergence J. Qui, R. Hao and X. Li, IEICE TRANS. Comm. Vol.E88–B, No. 4.
( Dec 16 2008, 07:21:28 AM GMT ) Permalink Comments [0]
