[ih] Exterior Gateway Protocol

[tony.li at tony.li]

To add a bit of color:

>  And there were shortest-path-first (alias link-state) protocols. With history going back to the second ARPAnet routing protocol, these included:
> <> ISIS, from the DECnet effort, and
> <> OSPF, for Open Shortest Path First, from the IETF.
> These were more sophisticated both in theory and practice, but converged quickly and had other nice technical properties.  A key challenge is that the SPF algorithm is executed on all the routers within the AS in a consistent way; if done correctly, this can result in nicely optimized routes and rapid convergence times.


Both of these are supposedly evolved from BBN’s Spread protocol, which I think is what was documented here: https://www.cs.yale.edu/homes/lans/readings/routing/mcquillan-darpa_routing-1980.pdf <https://www.cs.yale.edu/homes/lans/readings/routing/mcquillan-darpa_routing-1980.pdf>

While link state has many good properties, scaling it turns out to be challenging, both in state volume and in messaging in dense topologies. Hierarchy was introduced to help with the amount of state, but flooding has not been addressed until very recently. In the interim, many sites have turned to using BGP as their IGP to avoid this issue.


>  It's worth noting that BGP can be viewed as a distance-vector protocol, with the entire AS-path as its metric.  Note that BGP does *not* dictate which of several possible routes a given AS will prefer (and propagate).  And, sure enough, it can exhibit a really nasty version of the "counting to infinity" problem.


Namely, it explores every possible loop-free recovery path until all possible paths are known to have failed. Yes, this can be painful, but what can you do short of an oracle?


>  While I'm not aware of anyone actually doing this, it is interesting to contemplate what an SPF-based *EGP*.  This could have advantages (e.g., more optimal inter-AS routing and rapid convergence times), but having any Global agreement on which inter-AS routes will be preferred would be very unlikely.


This was explored as part of a BBN research project in the late ‘80s called Inter-Domain Policy Routing (lead: Martha Steenstrup) (IDPR — not to be confused with IDRP). As noted, getting routing policy out of commercial players was discussed and violently discarded. Routing policies are encodings of corporate relationships and to be able to see inequalities in treatment would have caused extreme reactions in the industry.

Noel also applied link-state to his NIMROD proposal.


>  Again, I focus on the late 1980s for historical focus.  And also, since, once a pretty good system, especially with BGP in the generic EGP/inter-AS context, evolves, it's hard to make big changes.
>  Comments?


We await better ideas. :-)  Deployment is possible through an overlay, as we initially did with BGP.

Regards,
Tony