[RRG] Abstraction action boundary & geo-aggregation router behavior

[Robin Whittle <rw@firstpr.com.au>]

Hi Tony,

If this was a maths class, I would be sure that this Friday's test
would include questions on "abstraction action boundary" and
"abstraction naming boundary"!

Perhaps you could give a more concrete example of how you envisage
routers behaving in a geographic address aggregation setting - in
particular by explaining what you mean by "abstraction action
boundary" and by giving some examples of the geographical limits and
addressing arrangements of a "geo-patch".  Diagrams would really
help me.

To constructively discuss this, I find myself having to construct a
reasonably concrete understanding of how a network would behave,
based on limited material in your messages.  This can be very
difficult.  Likewise with Brian Dickson's recent message:

  http://psg.com/lists/rrg/2008/msg01873.html

Other than your use of "abstraction action boundary" in recent
messages, below is the sum total of what I could discover about the
term.

 - Robin



The RRG list from 2007-11-26:

http://www.mail-archive.com/search?q=abstraction+action+boundary&l=rrg%40psg.com

Other than messages in recent days, in which Tony used it several
times, the original use of the term is:

  http://psg.com/lists/rrg/2007/msg00631.html   (Tony)

  > The real question is: what happens at the geo-patch abstraction
  > (action) boundary?  Where is that boundary?  Who is responsible
  > for traffic arriving into the geo-patch?  What happens if the
  > topology within the geo-patch is internally disconnected?
  >
* > The traditional explanation is that there must be regulations
* > requiring an interconnect for the geo-patch and all providers
* > must connect to that interconnect.  The alternative is that
* > providers with links outside of the geo-patch end up receiving
* > traffic destined for other providers and end up providing free
* > transit.
  >
* > More generally, if the entry point at an abstraction action
* > boundary is not directly connected to all of the
* > sub-abstractions, then you have a situation where traffic must
* > traverse a sub-abstraction, which will violate commercial
* > constraints.  Thus, the abstraction action boundary must be
* > located where there is common (or free) connectivity to all of
* > the sub-abstractions.  You can conceivably shift the abstraction
  > action boundary away from the abstraction naming boundary to
  > help with this (i.e., do proxy aggregation), but how is this
  > maintained in the face of changing topology and across
  > hierarchical levels?
  >
  > The OSPF assumption that all routers are willing to carry all
  > traffic simply doesn't hold in the inter-domain routing arena.


Earlier references, from Tony nearly 10 years ago:

http://www.rtg.ietf.org/lurker/message/19981005.192053.8342df0a.en.html

  > |> Why do you want to define multiple level of hierarchy ?
  > |> Just because it would "cool" to do it ? Or do you know
  > |> of any (big) customers that really need it ?
  > |
  > | THIS IS the most important question, of course. ISPs input
  > | welcome and awaited here. From my little pigeon-hole, I saw
  > | that they were unhappy with the fact that the routing in a 2
  > | layer hierarchy is non-optimal and that prevents them from
  > | runnning multi-level at all so far ... So maybe the more
  > | realistic problem to work on in this area would be to optimize
  > | the L1/L2 routing globally first.
  >
  > There are several big customers that are thinking of moving to
  > using 2 layer hierarchy. It would behoove us to stay one step
  > ahead of them. ;-)
  >
  > In addition, there are multiple ways of attacking the optimality
  > problem.  One interesting alternative is to do level-skipping
  > when performing prefix aggregation. In level-skipping, L1
  > prefixes and not aggregated when injected into L2. Instead, they
  > are only abstracted when injected into L3. Thus it helps to have
  > an L3 to inject into.
  >
  > The result of level-skipping is that you extend the abstraction
  > action boundary and thus decrease the amount of sub-optimality
  > introduced by the abstraction mechanisms. One can see that
  > today's suboptimality occurs because the abstraction action
  > boundary and the abstraction naming boundary coincide, with a
  > resultant loss of information being most critical immediately
  > outside said boundary. By extending the abstraction action
  > boundary, we can hope to encompass more of the relevant
  > topology, thereby decreasing the amount of sub-optimality in
  > the routing.
  >
  > Of course, there is no true technology that will yield optimal
  > routing other than a completely flat system, and we've also seen
  > (from traffic engineering work) that optimal routing is not
  > what's truly desired anyway.


http://www.rtg.ietf.org/lurker/message/19981005.222838.1c707551.en.html


  >| ouch, lost some terminology here, what is abstraction action
  >| boundary (that's where you sumamrize & supress components I
  >| guess) and what is abstraction naming boundary then? Naming
  >| is quite a different thing from addressing normally, isn't it?
  >| And what is said boundary? Did I forget to read some
  >| fundamental RFC ?
  >
  > No, you must have missed out on some Noel-speak. Easily
  > remedied:
  >
  > The abstraction that we're forming is an IPv4 prefix that
  > describes all address space within a given subset of the
  > topology. The border of this subset is the abstraction naming
  > boundary.
  >
  > The abstraction action boundary is where we actually stop
  > advertising more specific prefixes and advertise the
  > abstraction.
  >
  > |> Of course, there is no true technology that will yield
  > |> optimal routing other than a completely flat system, and
  > |> we've also seen (from traffic engineering work) that optimal
  > |> routing is not what's truly desired anyway.
  > |
  > | that's true but we could be better than "go to the closest
  > | L2", couldn't we. The simplest solution that comes to my mind
  > | is to inject from every L2 gateway the learned L2 prefixes
  > | with their distance being prefix distance + distance through
  > | L2 domain ... That way L1 systems could route to the optimal
  > | L2 per prefix. That may be equivalent to what you call
  > | "shifting the abstraction action boundary from the abstraction
  > | naming boundary" ;-)
  >
  > Yes. By effectively advertising only default into L1, IS-IS
  > basically dictates how abstraction happens. As you can see, this
  > is not necessarily optimal. Advertising further prefixes into L1
  > improves this, at the cost of more information in L1.
  >
  > One might also decide that if one is not aggregating all of L1
  > when injecting into L2 that one might want to perform this
  > aggregation when injecting into a lower level L1.
  >
  > For example, suppose that one L1 area has prefix A and another
  > L1 area has prefix B. We carry around all longer prefixes of A
  > both within A and within L2. But when injecting into B, we would
  > only inject the aggregate A.


From May 1995:

  http://www.ir.bbn.com/projects/nimrod/defs

    . . .

    "basic entities" - The lowest level items in a network topology;
              i.e. interfaces, nodes, and networks.

    "area", "cluster" - The actual network topology can be modelled
              as a graph, containing nodes and networks, with the
              former connected to the latter via interfaces. An area
              is a (usually contiguous) section of the graph. More
              formally, an area is a collection of nodes, as well as
              those arcs joining them which fall completely within
              the area boundary.  Areas may recursively contain
              other areas. Areas have names, which are the elements
              in locators.

   "entities" - Graph elements, including basic entities and areas.


   "attributes" - Entities may have traits which are either inherent
             (such as bandwidth, delay, etc), which often go under
             the name of 'Quality of Service', or externally applied
             (such as cost and usage restrictions), which are
             usually described as 'policies'. An "attribute" is a
             descriptor of such a trait, applied to a entity. Since
             the two different types of trait are essentially
             indistinguishable as far as the routing is concerned,
             they have only a single name.

   "route", "path" - A sequence of entities which leads from a
             source entity to a destination entity.

   "policies" - Constraints of various kinds, both for inherent
             properties (with regard to such attributes as
             bandwidth, delay, etc), as well externally applied
             restrictions (such as cost and usage restrictions).
             All known policies fall into one of following three
             classes:

                "transit policies", "access control policies"

                   A policy applied to an entity; e.g. only certain
                   classes of traffic are allowed to use a given
                   link.

                "source policies"

                   A policy applied to the selection of a route;
                   e.g. only certain types of link are acceptable in
                   creating a given route.

                "information hiding"

                   A policy applied to the distribution of
                   information about the details of the topolology
                   of some part of the network.


    "abstraction" - A process which reduces the amount of
            information available for making decisions about routes,
            to reduce overhead. In a map based system, this usually
            involves substituting a simplified map of an area
            for the fully detailed map of the area.

    "thinning" - An abstraction process in which some routes differ
            after the abstraction has happened; i.e. some useful
            info is discarded. In other words, the routes are now
            less optimal, and in policy routing, perhaps impossible
            to find, even though a valid route does exist.

    "compression" - An abstraction process in which all routes are
            the same after the abstraction has happened as before;
            i.e. no 'useful' information is discarded. All instances
            of abstraction can be divided into two non-overlapping
            sets, compression and thinning.

    "aggregation" - An term meaning approximately the same thing as
            abstraction, but more limited. It refers to the
            replacement of a number of routing table entries (in a
            routing table based system such as all Destination
            Vector systems) with a single routing table entry. This
            is obviously not quite as flexible as abstraction in map
            based system, where the representation of an abstracted
            area need not be a single node, but may be a simpler map
            than the original. Abstraction in a map based system
            thus allows degrees of thinning which are intermediate
            between the simple "yes/no" decisions of aggregation in
            a routing-table based system.

    "area boundary", "abstraction naming boundary" - The boundary of
            an area on the map of the network topology.

    "scope" - The section of the network over which the detailed
            representation of an area, as opposed to its
            abstraction, is normally available.

    "abstraction action boundary" - A term very similar to the
            above, but used mostly in Destination vector systems. It
            refers to the boundary at which routes to individual
            elements of an aggregate are replaced by a single route
            to the aggregate.




--
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