Subject: Re: [rrg] Anycast in the core architecture

From: [email-masked]
Date: Tue, 21 Apr 2009 04:00:51 EDT

What are the requirements for Anycast in a new architecture?
As I understand Anycast  is about delivery to one out of multiple  
destinations within a given scope.
Where is the center point of this scope ? Is it always the location of the  
source ?
Can/should it be something to be provided/signalled (which makes sense if  
alternatives to that case were allowed where the source is this center  
point)?
 
Who determines the final Unicast destination ? the source? the ingress  
router? Or also some router/server along the path?
May an enforced detour of the forwarding path  wind up in  selecting a 
different Unicast destination - done by any transit router?
 
I'll appreciate learning the answers to these questions because I  think 
there are multiple ways to conceive and implement Anycast (not just the  
traditional one). There are quite a few concepts developed for other services  
which are likewise applicable to Anycast: MIP4 care of address server, HIP  
rendez-vous server,...

Heiner

 
In einer eMail vom 21.04.2009 07:58:07 Westeuropäische Normalzeit schreibt  
[email-masked]:

Hi  Bill,

> I have this mental picture of the NFAs and DFAs (finite  automata) used
> to process regular grammars from the formal languages  class I took in
> college. All NFA's can be translated to DFAs but the  translation
> explosively grows the automata.
> 
> Seems to  me like NFAs are decent metaphors for broadcast and multicast
> while  DFAs are metaphors for anycast and unicast. And I think its
> notable  that anycast groups with unicast (it's DFA-like) instead of
> grouping  with multicast.

Ok, I remember these.  Still have the textbook  right here.  ;-)

>> Except that we haven't figured out  how to aggregate anycast, which from 
a
>> routing perspective, makes  it completely unique.
> 
> What do you mean? Anycast aggregates  the same way as unicast: whenever
> the endpoints physically group  together, they aggregate. At a
> practical level, that's rarely useful  for anycast... But then at a
> practical level aggregating unicast that  way (or failing to) is the
> source of our current  grief.

Well, the problem with aggregating anycast is that it ends  up with one 
route per service.  In a world of highly differentiated  services, the 
sheer number of services could be explosive.  And you  can only aggregate 
them if they are numbered appropriately and are  topologically 
correlated.  How often is that going to happen with  anycast?

To be fair, we do get substantial aggregation up to the site  level with 
unicast, it's above that level that things get  iffy.

>>> The same can't be said of multicast. Multicast  has different semantics
>>> even if there's only one host in the  group.
>> Say more please, I'm not following.
> 
> With  anycast, the packet's next hop is always in exactly one
> direction,  precisely the same as with unicast. And knowledge about
> what that next  hop should be propagates precisely the same way.
> 
> With  multicast, the packet is replicated in all currently valid
> directions  with complex subscription/desubscription overhead that has
> to be  maintained even if there's only one receiver in the group.

Having  watched the development of PIM, BGP, OSPF, ARP, HSRP, VRRP, and 
IS-IS, I'm  having a hard time saying that the "complex 
subscription/desubscription"  overhead for multicast is all that much 
worse than what we do for  unicast.

As for the forwarding plane, the differences are NOT that  large.  Ok, 
yes, there is an order of magnitude more complexity in  doing the packet 
replication, but it becomes quite clear that with one  receiver it does 
devolve nicely into an effective unicast.  No one  would implement 
unicast that way, of course, but that's an efficiency  issue, not a 
conceptual one.

Even if multicast's differentiation is  the replication in the data 
plane, I'm not sure I see how that becomes  non-deterministic.  I see no 
references to an oracle.  The right  things always seems to happen with 
total determinism.

>>  Ok, but how would a map resolution change that?  Is the key point here  
that
>> whatever mapping function is used, the map result has a TTL  and needs 
to be
>> refreshed periodically?  Or, the applications  need to be able to 
trigger a
>> refresh?
> 
> You'd put  the map resolution outside the app developer's scope, either
> in the  network (as proposed by strategy A) or in the system-level host
>  software (as proposed by strategy B). Unprivileged applications simply
>  wouldn't be able to diddle with addresses at the routing layer.
>  
> With a guaranteed maximum time that a given map remains valid and  no
> application-level access to the routing element, the protocol  and
> weigh in favor of renumbering for aggregation instead of rerouting  for
> multiple connections.
> 
> But this is rather off on a  tangent from anycast and its rather
> identical nature to  unicast.

Seems like useful implementation strategies to me.   And it leads me 
again to the conclusion that it's again not something  that's happening 
within the routing  subsystem.

Tony
_______________________________________________
rrg  mailing  list
[email-masked]
http://www.irtf.org/mailman/listinfo/rrg

---

From: Patrick Frejborg <[email-masked]>
Date: Tue, 21 Apr 2009 12:26:30 +0300

Heiner,

guess there are several ways to implement Anycast in a new
architecture, here is one way of doing it ...

I'm currently rewriting my draft - after I had studied the Dagstuhl
material I noticed that I had used only locators (though using locator
and identifier in my text) and not seen the new dimension (which is
currently named identifier)  . So I'm changing my text, which is not
published yet:
- Area Locator, ALOC (it could also be called Autonomous system
LOCator or Aggregate LOCator). The purpose of the ALOC is to locate an
AS, or a group of AS, in Internet.
- Local Locator, LLOC. The purpose of the LLOC is to locate a host
connected to an ALOC realm
And I have also added an identifier to the draft but later more on
that once there is a consensus about identifier

So here is an example of the usage of Anycast and locator in an architecture.
Note, no session or flow state in the LSR. Also converging from one
LSR to another LSR is depending upon the convergence time of IGP. Hack
or no hack?

3. An overview of the hIPv4 framework
In this section we will discuss the roles of the new elements,
introduced by the hIPv4 framework, and their dependencies.
As mentioned in the introduction section the role of an Area LOCator
(ALOC) prefix is similar as to a country code in PSTN. I.e. the ALOC
prefix provides a location functionality of an Autonomous System (AS),
or a group of AS, in Internet. The ALOC prefix will be used for
routing and forwarding purposes in Internet, thus the ALOC prefix must
be globally unique and is allocated from an IPv4 address block. This
globally unique IPv4 address block is called the Global Locator Block
(GLB).
When an AS (or group of AS) are assigned an ALOC prefix the area has
the potential to become an ALOC realm. In order to establish an ALOC
realm more elements, further than the ALOC prefix, are needed. One or
multiple Locator Swap Router (LSR) must be attached to the ALOC realm.
A LSR element is a node capable of swapping the values of the IPv4
header and the new shim header, called the location/identifier header.
The swap mechanism of the headers is described in detail in section 7,
step 4. Today’s routers do not support the LSR functionality.
Therefore the new functionality will most likely be developed on an
external device attached to a router belonging to the ALOC realm. The
external LSR might be a computer with two interface attached to a
router, the first interface configured with the prefix of the ALOC and
the second interface with any IPv4 prefix. The LSR do not make us of
dynamic routing protocols, neither a forwarding information base (FIB)
is needed - the LSR is producing a service, i.e. swapping headers. The
swap mechanism is applied on per datagram basis and the information
needed to carry out the swap is included in the header of the hIPv4
datagram. Thus a computer with enough computing and I/O resources is
sufficient to take the role as a LSR. Later on, the LSR functionality
might be integrated into the forwarding plane of a router. One LSR can
not handle all the incoming traffic designated for an ALOC realm; it
would also create a potential single point of failure in the network.
Therefore, several LSRs shall be installed in the ALOC realm and the
LSRs shall use the ALOC prefix as their locator and the routers are
announcing the ALOC prefix as an Anycast address within the local ALOC
realm. Also, the ALOC prefix is advertised throughout the DFZ by BGP
mechanisms. The placement of the LSRs in the network will influence on
the ingress traffic to the ALOC realm, the LSR is providing “nearest
routing” functionality.

 -- patte

On Tue, Apr 21, 2009 at 11:00 AM,  <[email-masked]> wrote:
> traditional one). There are quite a few concepts developed for other
> services which are likewise applicable to Anycast: MIP4 care of address
> server, HIP rendez-vous server,...
>
>
> Heiner
>
>
>
>
>>> Except that we haven't figured out how to aggregate anycast, which from a
>>> whatever mapping function is used, the map result has a TTL and needs to
>>> be
>>> refreshed periodically?  Or, the applications need to be able to trigger
>>> a
>>> refresh?
>>