Subject: [rrg] Anycast in the core architecture

From: William Herrin <[email-masked]>
Date: Sun, 19 Apr 2009 12:13:55 -0400

> Put differently, anycast addresses are no different than, and arguably
> worses than, PI addresses.  A whole lot of our work is to get PI addresses
> out of the core table.  Getting PI out, but allowing unlimited anycast in
> would not be progress.

Several of you have made comments like the above. In my head I can
almost see  the rest of you behind your screens, sagely nodding your
heads in agreement that anycast shouldn't be a first-class citizen in
the architecture.

Before anyone nods his way into a mistake, I'd ask you to consider a
simple question: What might anycast look like in the various
approaches we've discussed to solving the routing problem?

Let's look at a map-encap strategy A system first. What can't it do
adequately without anycast? And how can it provide routeless anycast?

First off your non-local packets need to find an ingress router. The
more specific local routes will keep local packets away. The rest will
follow a default route to the ingress router. Or is there some other
way you'll find the ITR? Somehow force it inline with all packets
routed?

You'll no more run your network on just one ingress encoder than you'd
run it on a single DNS server or a single T1. Okay, well, some of you
will but those of you who are serious about reliability won't. No,
you'll have two or several ingress routers. And each one will ANYCAST
the default route so that if one of them fails the packets seamlessly
reroute to the other.

What about the transition period? For a while there'll be both legacy
routing and the ITR/ETR routing. How will you bridge the legacy
systems in? Well, every one of us who has come up with a strategy-A
solution has posited some sort of ITR in the core that advertises
short prefixes out to the legacy system and encodes the packets it
gets for delivery in the new system. Will we have one for all the ETRs
serving 192.0.0.0/8 and one for all the ETRs serving 193.0.0.0/8? Yeah
right. We'll have 20 geographically distributed ITRs for 192.0.0.0/4,
each of which will announce 192.0.0.0/4 via ANYCAST.

And if you plan to go out and query a distributed map database (as
more of you do now than did two years ago when I proposed it) then
you'll announce your map roots via ANYCAST too.

But that's only half the equation. Strategy A systems don't just
consume anycast routes, they provide them. And unless you do something
really bone-headed in your design, they do it in the map without
consuming slots in the routing table.

You do a map lookup on the destination. You get a prioritized list of
of egress routers. Though presumably multiple entry points into the
same system, this is no more a rule than with routes in the BGP table.
Make each egress an entrance to a different, geographically and
topologically diverse, host. The akamai-like map server dynamically
reorders the list based on its heuristic guess as to which of the
hosts are closer or further from you. Presto! You connect to the
nearest server through minor magic in the map.

Give the ingress router a mild resistance to change during relookups
and you even get anycast with a very high probability of packets
reaching the same respondent over time -- rather handy for anycast TCP
which isn't really practical in the current routing system.

Stable TCP over anycast would, by the way, be fantastic news for the
CDNs and their customers which include, oh, just about every major
content provider on the web.

Of course, you might implement strategy A badly. You can build a rigid
design where the map is static and the ingress router has no
discretion whatsoever for which egress it sends to. But none of you
made that mistake in your designs, right?

Strategy B systems alter or replace TCP with a protocol that doesn't
use the layer-3 address for its transport identity. They use a map to
find the current set of "locators." Routeless anycast here works in
much the same way as strategy A. The map is like an enhanced DNS SRV
record. Better really: not only do the endpoints know which set of
locators to try first, they know which locators match each of the
multiple hosts returned by the lookup. You're actually guaranteed to
get the same respondent for the duration of the layer-4 connection.
It's SO easy.

And, of course, anycast and unicast routes are identical in every
respect in strategy D, E and F systems since the routes on those RIBs
function identically to what we have today.

With this in mind, I propose a statement which is, on its face,
absurd. Yet each time you consider it in the coming months and years,
you'll find it makes more and more sense:

Unicast is a special case of anycast in which there is only one
destination endpoint.

Food for thought.

Regards,
Bill Herrin

-- 
William D. Herrin ................ [email-masked]  [email-masked]
3005 Crane Dr. ...................... Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: Tony Li <[email-masked]>
Date: Sun, 19 Apr 2009 09:44:28 -0700

Bill,

> approaches we've discussed to solving the routing problem?

What you're proposing is certainly reasonable.  The gist is that you 
don't end up with a global route per service, and that you use the 
mapping function to convert anycast into a unicast service.

Some folks do that already today (e.g., http://www.pool.ntp.org) with 
DNS as the mapping function.  That's certainly fine and has no impact on 
  routing whatsoever, obviously.  We just don't call it anycast.

> Unicast is a special case of anycast in which there is only one

Nothing absurd about it.  It's been said many times that unicast is a 
special case of multicast and your observation is that anycast fits in 
the middle of that hierarchy, since anycast is also a special case of 
multicast where delivery is to only one receiver.

Regards,
Tony

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 19 Apr 2009 13:42:40 -0400

I suspect that our disagreement may relate to the definition of Anycast.
For example, IPv6 anycast, which as I understand it is a prefix followed 
by all zero bits, and routes to any place that handles the prefix.  Is 
sensible, routable, scalable, and ought to be aggregateable.  I have no 
problem with it.

I also have no problem with the fact taht DNS names often resolve to 
multiple IP addresses, any of which can be used by the client aplicaiton 
to reach the entity of interest.

Where I have trouble is treating as a name for a topological location in 
the net, a quantity as long as the full address (32 IPv4 bits or 128 
IPv6 bits) and having that thing reachable in multiple distinct 
topological locations, with no aggregation possible.  While that can be 
used for special purposes, it appears to me that it is a special purpose 
hack, placing application / service information in the routing system, 
rather than a first class service component usable at whatever scale 
anyone wants to use it.

Having read the text below, given that you refer to multiple routes to a 
prefix as a form of anycast, I am left confused as to what you are 
arguing should be treated as a full part of the architecture.

Yours,
Joel

---

From: Jeroen Massar <[email-masked]>
Date: Sun, 19 Apr 2009 20:09:00 +0200

[sidetrack: anycast ipv6 note]

Joel M. Halpern wrote:
> by all zero bits,

Actually, it is just like IPv4, you configure a /128 in IPv6 or a /32 in
IPv4 and route it. The host that picks it up wins.

The one you mention is called a 'subnet anycast address', which is the
"0" on the subnet, if you have a /64, it is is the all-zero address; if
you have a /127 though, you suddenly have a problem: 0 = subnet anycast,
1 is the first address, and indeed then it is full and it does not work.
Which is why /127's are a bad idea to use; 2x /128 works of course ;)

Ggreets,
 Jeroen

---

From: William Herrin <[email-masked]>
Date: Sun, 19 Apr 2009 19:32:53 -0400

> I suspect that our disagreement may relate to the definition of Anycast.

Hi Joel,

I'm talking about anycast as described in RFCs 1546, 3068 and 3258.

I'm not well familiar with RFC 2526 but it seems to describe some
subnet-centric considerations which would be outside of the RRG's
scope.

On Sun, Apr 19, 2009 at 12:44 PM, Tony Li <[email-masked]> wrote:
> special case of multicast and your observation is that anycast fits in the
> middle of that hierarchy, since anycast is also a special case of multicast
> where delivery is to only one receiver.

Hi Tony,

I disagree with you there. Broadcast and Multicast are forms of
non-determinisitic routing. Anycast and unicast are both forms of
deterministic routing.

There's a wide gulf between deterministic and non-deterministic
routing. What works efficiently for one just flat doesn't work well
for the other.

I claim that on the deterministic side, the difference between anycast
and its unicast subset is sufficiently trivial that a well conceived
protocol will neither need nor want to treat the two cases
differently.

When I say, "Unicast is a case of anycast in which there is only one
destination endpoint," I really mean it. Unicast doesn't exist. It's
just a convenience label for Anycast in which only one destination
endpoint is currently active, and that's precisely how the routing
system treats it.

The same can't be said of multicast. Multicast has different semantics
even if there's only one host in the group.

Still think I haven't proposed a radically different way to visualize
the routing system?

> What you're proposing is certainly reasonable.  The gist is that you don't
> end up with a global route per service, and that you use the mapping
> function to convert anycast into a unicast service.
>
> Some folks do that already today (e.g., http://www.pool.ntp.org) with DNS as
> the mapping function.

If using DNS that way worked, we could all go home. Unfortunately,
what happens is that the ntp server looks up the name to address
binding once when the machine boots and never reconsiders it during
the year and a half the server is running, even after queries to the
server's IP address stop returning data.

This is typical. Though their operational cycle is usually limited to
days or weeks, web browsers do the same thing. (DNS pinning)

The strategy B systems essentially replace DNS with a system where the
timeouts are mandatory. The strategy A systems add an additional layer
of indirection between DNS and routing so that the DNS is free to
continue its trend toward static bindings. In both approaches we
acknowledge that decades of practice have rendered the existing
forward DNS irretrievable as a source of dynamic binding to the
routing elements.

>  That's certainly fine and has no impact on  routing
> whatsoever, obviously.  We just don't call it anycast.

If it quacks like a duck...

Regards,
Bill

---

From: Robin Whittle <[email-masked]>
Date: Mon, 20 Apr 2009 14:51:37 +1000

Short version:    I support a relatively specific, narrow, use
                  of the term "anycast" - where one of two or more
                  destination hosts may receive the packet.

                  I recognise "anycast" is used rather loosely -
                  one of those words which needs to be preceded by
                  someone waving a red flag and carrying a definition
                  for the purposes of the discussion.

                  Also correcting what I think are some
                  misunderstandings about Ivip.

Hi Bill,

I won't comment on all you wrote - just on a few points.

I grappled with the meaning of "anycast" in 2007 and 2008:

http://www.google.com/search?q=Robin+anycast+RRG+-%22rrg+Discussion+Archive%22

Initially I called the ITRs in the core "anycast ITRs in the
core/DFZ".  I was convinced by one of the LISP team that this was an
incorrect use of "anycast".  So I renamed them to OITRDs - "Open ITRs
in the DFZ".

I decided that the best meaning to assume for "anycast" is an address
or prefix which is advertised as in a local routing system and/or the
DFZ from multiple routers and where the packets are actually handled
by separate hosts.

So if an ISP has two border routers both advertising 12.34.56.0/24
and within that, the address 12.34.56.78 is handled by a single host,
then this is not "anycast" - it is just advertising the same route
from two or more border routers.

If there are two or more hosts responding to the same address -
12.34.56.78 - and each one has its own router advertising the
encompassing prefix, then this is a true use of "anycast".  The
address 12.34.45.67 is not the name for any particular device - it is
just an address which is used by multiple destination hosts, all of
which presumably use the received packets in some consistent and
useful manner.  They don't have to respond in exactly the same
manner, but they presumably exist for a common purpose and can
collectively be relied upon to perform one or more tasks.

In the case of OITRDs there are typically more than one OITRD which
advertises a given MAB (Mapped Address Block).  They all tunnel
packets addressed to any given micronet (such as 12.34.56.77 to
12.34.56.80) to one ETR address.  Generally, with Ivip, that will
mean one (non-anycast) ETR which will forward the packets to one
end-user network where the packets will go to one host.  So I think
that OITRDs, LISP Proxy Tunnel Routers (PTRs) etc. are not inherently
a form of anycast.

I could imagine anycast being used with with Ivip - and probably in
principle with LISP, APT or TRRP:

  1 - Anycast ETRs.   There could be multiple physical ETRs with the
      same address.  So the packets are tunneled from ITRs to
      whichever (typically "closer") ETR the DFZ and internal routing
      system forwards the tunneled packet to.

      It is a separate issue whether those multiple ETRs forward the
      packets to a single destination host or to a separate host for
      each ETR.

  2 - Anycast hosts.  There may be one ETR or there might be anycast
      ETRs as above.  There are two or more destination hosts with
      the same address, and depending on how the one or more ETRs
      link to these destination hosts, the packets may go to one
      or another of them.

I am not sure what use these arrangements might be - but they may
well have uses for non-TCP, simple request and response protocols.

There may well be a role for anycast query servers in local networks
- however I think it is more likely to involve anycast or some other
zero configuration default arrangement so that ITRs can discover
their nearest Query Servers' addresses and so use one or more of
them.  I may use TCP between the ITR and the Query Server, so we
can't have the Query Servers on anycast addresses.

> the default route so that if one of them fails the packets seamlessly

Likewise, I don't think that the word "anycast" should be used to
describe multiple ITRs (internal to a network or OITRDs in the DFZ)
advertising the same MAB - since this doesn't necessarily and won't
typically result in the packets being handled by multiple destination
hosts.

> gets for delivery in the new system. 

This is a description of Ivip OITRDs or LISP PTRs.  However, I don't
think of it as a "transition period".  I expect there will always be
some networks which don't have ITRs, and so there will always be a
need for OITRDs.

> Will we have one for all the ETRs

There are various ways it could be done.

You could have a single set of widely distributed OITRDs each
advertising every MAB.

You could have one set of OITRDs advertising one or more MABs and
another set advertising others.

See: Ivip business models: fast push & OITRDs  2008-04-18
     http://www.ietf.org/mail-archive/web/rrg/current/msg02100.html

> you'll announce your map roots via ANYCAST too.

I think LISP-ALT is the only other currently developed proposal (AKA
candidate architecture) which uses a global query server system, as
does your TRRP system.  TRRP is a DNS-like query server system and
LISP-ALT's is totally different - there are no servers advertised in
the Internet in any way.  Each ITR is either a part of the ALT
network or it connects to a Map Resolver which is.

So AFAIK, TRRP is the only one which might use anycast as part of the
mapping system, in the form of anycast servers in the global DNS-like
query server system.

Anycast may well have a role in LISP Map Resolvers, but this is not
the same as anycast DNS-like servers as you would use in TRRP.

> content provider on the web.

I can't imagine any robust approach to TCP using anycast.  The
routing system could change at any time and direct the packets to
another destination host.  Unless all those hosts were in some way
linked to behave as a single system, TCP or any other protocol in
which the host stores state, would not be reliable.

> You do a map lookup on the destination. You get a prioritized list
> of of egress routers.

Ivip's mapping has no list.  The mapping specifies the matching
micronet and has a single ETR address.  If that ETR goes down, it is
up to the end-user network - or more likely a multihoming monitoring
company they appoint to do the work - to decide on an alternative ETR
address and to send this as a real-time mapping update, which all the
ITRs which need it will get in a few seconds.

See the new section "The actual source of mapping changes" in the
recently updated Summary and Analysis:

  http://www.firstpr.com.au/ip/ivip/Ivip-summary.pdf

> made that mistake in your designs, right?

This is not a mistake in Ivip.  It is a core part of the architecture.

It is GOOD that the end-user network can and must control the mapping
in real time.  Then there is no need for multiple ETR addresses, ITRs
having to decide between them etc.  Also, it modularly separates the
decision making process about where to tunnel packets (for instance
due to an outage being detected) right out of the core-edge
separation system.

LISP, APT and TRRP monolithically integrate this, because in none of
these systems do you have essentially real-time mapping distribution
- so you must provide multiple ETR addresses and add a lot of
complexity to ITRs so they can decide which ETR address to use.

  - Robin

---

From: Tony Li <[email-masked]>
Date: Sun, 19 Apr 2009 22:02:56 -0700

Hi Bill,

> non-determinisitic routing. Anycast and unicast are both forms of

Interesting.  That rumbling sound you here is Dino's keyboard...  ;-) 
How do you figure it's non-deterministic?   If you take a global 
snapshot at any given point in time, then for any given mcast packet 
sent by a given source, it's straightforward to compute the receivers.

Similarly for broadcast, it's trivial to see who should receive it.

> endpoint is currently active, and that's precisely how the routing

Except that we haven't figured out how to aggregate anycast, which from 
a routing perspective, makes it completely unique.

> even if there's only one host in the group.

Say more please, I'm not following.

> Still think I haven't proposed a radically different way to visualize

Not yet, but I don't grok your perspective yet.

> server's IP address stop returning data.

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?

> forward DNS irretrievable as a source of dynamic binding to the

Hmmm...  not at all convinced.  And I'm still not seeing how strategy A 
does anything significantly different other than giving us a chance to 
re-implement differently.  You certainly don't want the ITR to be 
application/service aware, so it's simply forced into periodic retries. 
  It seems like that is also going to have numerous downsides, such as 
broken anycast connections.

> If it quacks like a duck...

It doesn't seem to quack at all.  ;-)

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 20 Apr 2009 10:01:34 -0700

> Interesting.  That rumbling sound you here is Dino's  
> keyboard...  ;-) How do you figure it's non-deterministic?   If you  
> take a global snapshot at any given point in time, then for any  
> given mcast packet sent by a given source, it's straightforward to  
> compute the receivers.

;-)

I look forward to Bill's reply.  ;-)

Dino

---

From: Scott Brim <[email-masked]>
Date: Mon, 20 Apr 2009 16:38:26 -0400

> multicast where delivery is to only one receiver.

Tony: I think these are statements about routing, not about
addressing, but I'm not sure.  How would what you say here work with
the definition of a locator?  

> non-determinisitic routing. Anycast and unicast are both forms of

Is that because the _potential_ recipients are already known?

> Still think I haven't proposed a radically different way to visualize

How would you change the definition of a locator to match this?

---

From: William Herrin <[email-masked]>
Date: Mon, 20 Apr 2009 17:53:42 -0400

On Mon, Apr 20, 2009 at 1:02 AM, Tony Li <[email-masked]> wrote:
> Interesting.  That rumbling sound you here is Dino's keyboard...  ;-) How do
> you figure it's non-deterministic?   If you take a global snapshot at any
> given point in time, then for any given mcast packet sent by a given source,
> it's straightforward to compute the receivers.

Hi Tony,

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.

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

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

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

> How would you change the definition of a locator to match this?

Hi Scott,

Outside the context of specific solution strategies, I'm not sure the
term "locator" is useful here, in any of its definitions. The most
helpful term I've found here that could use a definition is
"respondent," the particular anycasted device that you end up talking
to.

On Mon, Apr 20, 2009 at 12:51 AM, Robin Whittle <[email-masked]> wrote:
> Ivip's mapping has no list.

Hi Robin,

Call that a criticism of Ivip then. The change from current routing's
presentation to the app layer will have consequences, some foreseeable
and others unexpected.

> another destination host.

The routing system can change any time, interrupting communication
between two endpoints. From a CDN's perspective, it just has to remain
stable long enough to deliver the content about as often as it
succeeds without anycast.

The real problem with making TCP stable over anycast is not not
routing changes that connect you to a different respondent. It's that
you can be equidistant between two respondents with routing configured
to send packets to one or the other more or less at random.

If you rigged the routing system so that given two equidistant routes
you picked one and then stuck with it until either the one you
selected was withdrawn or until the metric on the other improved by at
least two or three distance units, you'd have TCP over anycast that's
stable enough for a substantial number of use cases.

Certainly stable enough for a case like adding and removing machines
from a geographically distributed web cluster.

Regards,
Bill

---

From: Robin Whittle <[email-masked]>
Date: Tue, 21 Apr 2009 10:35:41 +1000

Short version:   Bill suggests anycast TCP would be practical for at
                 least some purposes if the routing system was
                 "rigged" so (in any given short to medium time
                 period) routers sent packets along one path only.

                 I thought BGP routers at least, and probably all
                 others already did this - but perhaps I am wrong.

                 In a previous message Bill made broad statements
                 about core-edge separation techniques which
                 includes Ivip, which were contrary to how Ivip would
                 work.  I corrected this with a clearer description,
                 and he responded "Call that a criticism of Ivip
                 then." but the things I described look like benefits
                 to me.

Hi Bill,

You wrote, in part:

> Anycast aggregates the same way as unicast: whenever

Routers can't tell the difference between anycast and unicast.  Only
someone with complete knowledge of the network can determine which is
which.  If there are two routers advertising the prefix, that could
be either.  If each such router sends its packet to the one
destination host, it is unicast.  If each sends its packets to a
separate destination host, it is anycast.

> Call that a criticism of Ivip then. 

By investing in real-time (a few seconds) mapping distribution to all
the ITRs which need it, there is no need for multiple ETR addresses
or for ITRs to do any reachability testing and associated ETR address
decision-making.  End-user networks can do whatever they like with
the mapping, whenever they like (for a fee which largely ensures
their activity is not an unfair burden on anyone).

End-user networks can therefore employ any reachability testing they
like, make decisions in any way they like about multihoming and
inbound TE, including real-time changes to reflect changing traffic
patterns which could never be achieved in LISP, APT or TRRP's
ITR-based load spreading approach.  End-user networks can appoint
other companies to control their mapping, so those companies can use
global networks and arbitrarily sophisticated probing and
decision-making algorithms, including taking input from the end-user
network itself, such as for real-time load balancing.

Eliminating the ITR's need for probing ETR reachability (except as a
by-product of the PMTUD stuff which is unfortunately necessary for
encapsulation) means there is no need for extra bits, headers etc. in
traffic packets, or any other ITR <-> ETR communication.  Not needing
any extra bits, this enables the system to use Modified Header
Forwarding instead of encapsulation, once sufficient DFZ and other
routers are upgraded, completely eliminating encapsulation overhead
and PMTUD problems.

This doesn't sound like a critique to me!

> The change from current routing's presentation to the app layer
> will have consequences, some foreseeable and others unexpected.

This was in the same paragraph as your mention of Ivip.  Are you
referring to Ivip or anycast - I can't understand what you mean in
either case, though as mentioned below, I think anycast is generally
unsuitable for session-based protocols.

Anycast with entirely stable router behaviour would be no different
to applications than unicast - as long as there were no outages,
network structure changes etc.  Ivip doesn't affect applications, and
either do the other core-edge separation candidate architectures APT,
LISP or TRRP, except to the extent that some initial packets may be
delayed significantly - which is only a potential problem with
LISP-ALT and TRRP.

> between two endpoints. 

Yes, but when there is a genuine interruption - packets not reaching
their destination - this is a situation from which the routing system
rapidly recovers.

Much more often, when some router decides to send packets a different
way, there is no loss of connectivity at all in a unicast setting.

With anycast, that change may send the packets which formerly went to
destination host A (via its router X) towards some other router Y
which advertises the same prefix, or a prefix encompassing the same
address.  Then the packets go to host B, completely disrupting the
former communication with A.

My understanding, which is compatible with:

  http://en.wikipedia.org/wiki/Akamai_Technologies
  http://en.wikipedia.org/wiki/Content_Delivery_Network

is that CDNs use a fancy DNS server to provide different IP addresses
to different queriers, thereby generally directing hosts to
communicate with nearby CDN servers.  This is not anycast, but
anycast has apparently been used for "DDoS scrubbing", which I think
is not intended primarily to be a normal or reliable service:

  http://en.wikipedia.org/wiki/Prolexic

As is widely known, anycast is fine for many simple, stateless,
non-session-based query and response protocols including UDP-based DNS.

> From a CDN's perspective, it just has to remain

Anycast doesn't look suitable for CDN use, for the reason stated

> to send packets to one or the other more or less at random.

Do DFZ routers actually behave this way?  I recall that BGP has a
mechanism for choosing decisively between two "equidistant" routes
(number of ASes as adjusted by whatever factors have been
configured).  I recall a BGP router is required to chose the route
with the lowest number AS.

> stable enough for a substantial number of use cases.

I thought the routers already behaved this way.

If so, then at present, most people judge anycast, at least in DFZ,
as being unsuitable for any communication protocol such as TCP in
which the hosts store state.  This is not due, AFAIK, to routers
spreading packets over multiple paths, and so potentially to multiple
anycast destination hosts, but purely due to the possibility that a
router changing the packets' path from one peer to another will send
all subsequent packets to a different anycast destination host.

> from a geographically distributed web cluster.

I don't understand this.  The problem with anycast is that a router
could break the communication as just described - sending packets
which previously went to cluster A to a geographically distant
cluster B, which I assume is unable to access or modify the state
stored in cluster A's servers.  So B would be unable to continue to
serve TCP and higher level protocol sessions which A was serving.

  - Robin

---

From: Tony Li <[email-masked]>
Date: Mon, 20 Apr 2009 22:15:32 -0700

Hi Scott,

> the definition of a locator?  

Addressing is routing is addressing.  ;-)

I'm not sure I see the connection.  Intrinsically, anycast is _not_ 
about locators.  It is about services.  If you take Bill's approach (how 
about we call it 'anymap'), then obviously, that resolves to a real 
(locator, identifier) tuple.

> Is that because the _potential_ recipients are already known?

The actual recipients are already known.

Tony

---

From: Tony Li <[email-masked]>
Date: Mon, 20 Apr 2009 22:57:32 -0700

Hi Bill,

> notable that anycast groups with unicast (it's DFA-like) instead of

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

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

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

> 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

---

From: William Herrin <[email-masked]>
Date: Tue, 21 Apr 2009 17:53:55 -0400

On Tue, Apr 21, 2009 at 1:57 AM, Tony Li <[email-masked]> wrote:
>> the endpoints physically group together, they aggregate.
>
> 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's that different from, say, cnn.com, aggregated with the other
Turner services and spread across two of Turner's three unicast
routes? If TCP was stable over anycast, they might actually be able to
drop one of those unicast routes.

Seems to me that the aggregability of services has more to do with the
size of the services set than it does with whether the service is
unicast or anycast. Big important web site = at least one more route
in the table.

> 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
> devolve nicely into an effective unicast.

Effective unicast that is an order of magnitude more expensive to implement.

Anycast, on the other hand, is precisely the same as unicast in both
the forwarding and data planes... And as I mentioned, it's relatively
trivial to get it to look precisely the same in each of the two major
solution strategies as well.

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

I think of deterministic as "pick one direction" while
non-deterministic is "travel all valid directions." I'm open to a
better word choice.

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

I had a discussion with a colleague earlier today. He was having a
problem with a mapping app on his web site going through a particular
proxy server that didn't support http keepalive. To render a map page
with all the plotted points, he would generate around 500 ssl http
requests. With keepalive this would generate around 30 ssl
connections. Without keepalive it generates 500 and runs so very much
slower.

Where's the error here? The proxy that doesn't support keepalive? Or
the app that needs to generate 500 https queries in order to render a
web page? Which one do you zero in on and change?

The upper layers set requirements on the routing layer in a manner the
routing layer can't handle efficiently. One answer is that we redesign
the routing layer. Another is that we alter the requirements. Ruling
either answer out of scope would, at the very best, be failing to
think outside the box.

On Tue, Apr 21, 2009 at 4:00 AM,  <[email-masked]> wrote:
> As I understand Anycast  is about delivery to one out of multiple
> destinations within a given scope.

Hi Heiner,

I would have said "closest one from the set of valid destinations,"
but your version is good enough.

> Where is the center point of this scope ? Is it always the location of the
> source ?

I don't understand the question. What is a center point wrt routing?

> What are the requirements for Anycast in a new architecture?

Well, that's the crux of the discussion, isn't it? Anycast and unicast
are identical in every respect in the current architecture. How do we
bound the unforeseeable consequences if that isn't true in the new
one?

I'm getting ready to introduce an anycast route into the table in
order to implement a "continuing operations" system with three sites
half a world apart. "Continuing operations" is a fancy phrase for
"disaster recovery," something that became really popular almost 8
years ago. Once a packet hits any of the always-running sites, a VPN
takes it back to the site with the servers flagged "best" for that
particular address, so holistically its unicast but from the
perspective of the Internet core its anycast from three distinct
locations.

Would this have any hope of working right in an architecture that
didn't accommodate anycast? How many such uses are out there, ready to
impede the deployment of the unwary plan?

Regards,
Bill Herrin

---

From: Robin Whittle <[email-masked]>
Date: Wed, 22 Apr 2009 14:03:36 +1000

Short version:   Detailed discussion, with examples, of anycast ETRs
                 anycast hosts and Bill's current real-world project
                 which is arguably anycast.

                 Ivip (and I guess other core-edge elimination
                 schemes) handle anycast hosts just fine - no extra
                 complications.

                 Anycast ETRs are also possible with Ivip, but they
                 would typically require their own MAB prefix and
                 so would not involve any reduction in burden on the
                 DFZ compared to doing ordinary anycast hosts as is
                 done today.

                 I can't imagine how a core-edge elimination scheme
                 would do anycast hosts.  But that is a question for
                 those who design such things.  I think ILNP is the
                 only such design which is intended to help with
                 routing scalability (this is not a goal of HIP) -
                 and I don't understand ILNP clearly enough to try
                 to think about it doing something like anycast.

Hi Bill,

You wrote, in part:

> the forwarding and data planes... 

I agree.  As I wrote:

  http://www.ietf.org/mail-archive/web/rrg/current/msg04884.html

Routers can't tell the difference between anycast and unicast.  Only
someone with complete knowledge of the network can determine which is
which.  If there are two routers advertising the host's prefix, that
could be either.  If each such router sends its packet to the one
destination host, it is unicast.  If each sends its packets to a
separate destination host, it is anycast.

> And as I mentioned, it's relatively trivial to get it to look
> precisely the same in each of the two major solution strategies
> as well.

I think this is probably not true of Strategy B (core-edge
elimination, in which new host stack and perhaps application
functions do all the work and end-user networks never have their own
stable address space.

Most of this message considers anycast in a core-edge separation
scheme (Strategy A, no host changes - such as LISP, APT, Ivip and
TRRP).

I think core-edge separation schemes naturally support globally
anycast hosts without any difficulties.  They may also be able to
support anycast ETRs - but that is somewhat separate question, since
you could have anycast ETRs and a single, unicast, host.  Anycast
ETRs and anycast hosts may also be possible.

Basically, core-edge separation schemes seem to support anycast hosts
naturally and without any extra complication.  I can't easily imagine
how a core-edge elimination scheme could do so without a lot of extra
complexity.  This is one more reason for me preferring core-edge
elimination over separation.  Other reasons include:

  1 - Separation is possible to introduce voluntarily, since it
      involves no changes to host stacks or applications.  It seems
      very challenging or impossible to introduce core-edge
      elimination on a voluntary basis due to the need for stack and
      probably application changes an the consequent lack of
      support in the new system for hosts without these upgrades.

  2 - I think core-edge separation schemes support the best division
      of labour between hosts and the routing system: the host gets
      a stable IP address and doesn't have to worry about network-
      based things like multihoming, outages, reconfigurations,
      portability, TE, mobility etc.  (Supporters of core-edge
      elimination schemes prefer the network to do less and the
      hosts to do more.)

Perhaps a more stringent statement is true:

   Within a core-edge separation scheme, it will be just as
   impossible for a router or the routing system in general
   to tell the difference between anycast and unicast as it
   is without the scheme.

If so, then I think there is no extra effort required on the part of
host anycast operations or in altering the core-edge separation
scheme to make host anycast indistinguishable from host unicast.

However . . . "host anycast" with a core-edge separation scheme does
not necessarily mean "ETR anycast".  The two could go together, but
without "ETR anycast" a core-edge separation scheme with "host
anycast" alone doesn't look much like the common conventional use of
"host anycast".

With ordinary BGP (and/or an IGP I guess, or the two combined?), just
looking at the routing system, we can't distinguish between unicast
with two separate routers advertising the same address (for
simplicity assumed here to be advertising the same prefix) and anycast:

            R2------R5--\
           /  \     |    \
  SH---->R1   R4---R6    DH     Unicast with R5 and R7 advertising
           \  /     |    /      the same prefix which includes the
            R3------R7--/       one host.

  Fig 1  \___________/          << Scope of the routing system

            R2------R5--->DH1
           /  \     |           Anycast: same address used by two
  SH---->R1   R4---R6           hosts, each host connected to a
           \  /     |           separate router.  Each router
            R3------R7--->DH2   advertises the same prefix.

  Fig 2  \___________/          << Scope of the routing system

Any router and indeed the entire routing system can't tell whether it
is host anycast or not - and host anycast works just fine, within its
well-known limits of being unable to support session based
communications unless the destination hosts have a link and share
session state.

As I wrote in the earlier message, thinking of Ivip for the moment,
where ETRs are typically in the ISP (ignoring mobility for this
discussion - anycast and mobility make no practical sense to me), we
could have anycast ETRs and/or with anycast hosts.

In the following, for brevity, I will assume just the BGP routing
system, but there will also be IGP routers which are not shown.

     ITR               ETR
            R2------R5
           /  \     | \         Single ETR with dual border routers
  SH-I1->R1   R4---R6  E1->DH   advertising its address.
           \  /     | /         Single destination host = unicast.
            R3------R7

         \___________/          << Scope of the BGP routing system

    \_/                 \_/     << Scope of the core-edge separation
                                   scheme

    \_____________________/     << Scope of the now extended
                                   interdomain routing system
  Fig 3

In Fig 3 we have a destination host DH which is part of an SPI-using
(Ivip's Scalable PI space, of individually mapped micronets) end-user
network.  That network is not shown, but is in the same location as DH.

This host's network's ETR E1 is single-homed to an ISP which has two
border routers R5 and R7, both of which advertise the ISP's prefix
which encompasses E1's address.  Many other end-user networks can use
this ETR, and many other ETRs and PI customers can use this prefix,
so Ivip is being used here in a way which greatly reduces the burden
on the BGP control plane compared to each end-user network having its
own BGP advertised prefix.

Fig 4 shows a multihomed example of the same arrangement:

     ITR               ETRs
            R2------R5
           /  \     | \         Single ETR in each ISP.  Each ISP
  SH-I1->R1   R4---R6  E1       has dual border routers advertising
           \  /     | /  \      the ETR address.
            R3------R7    \
             |             \
            R9------R10    DH   Single destination host = unicast.
           /  \       \    /
         R12--R13     E2--/
           \  /       /
            R14-----R11
  Fig 4

ISP1 has ETR E1 whose address is advertised by R5 and R7.
ISP2 has ETR E2 whose address is advertised by R10 and R11.

This is a typical core-edge separation approach to a multihomed
end-user network.  With LISP, the ETRs would be at the destination
network.  With Ivip, they could be, but would probably be in the ISP
networks, where each ETR would also be serving multiple other
end-user networks, via its one IP address.  These ETR devices may
also be ITRs.  (For TTR mobility, E1 and E2 are Translating Tunnel
Routers - and they may be near, or perhaps within, the access
networks where DH has a care-of address.)

The next diagram depicts the theoretical possibility of "anycast"
ETRs.  This is extending the usage of "anycast" somewhat, since it
normally only refers to destination hosts.  However, from the point
of view of the packet being tunneled from the ITR to the ETR, the ETR
is the destination host of the tunneled packet.  If there are two
ETRs on the same address, with separate routers advertising this
address, then it is fair to think of the ETRs themselves being "anycast".

   Note regarding Modified Header Forwarding:

      The above is fine for encapsulation.  I haven't considered
      "anycast ETRs" with Modified Header Forwarding.  I think it
      is possible, but haven't considered the details or what
      benefits there might be.

Whether or not there are one or more destination hosts is a separate
issue.

     ITR                ETRs

            R2---- R5--->E1
           /  \     |      \    "Anycast" ETRs
  SH-I1->R1   R4---R6      DH   Single host (functionally unicast)
           \  /     |      /
            R3-----R7--->E2
  Fig 5

This should be possible with Ivip's non-encapsulation approaches:
Modified Header Forwarding (MHF) across the DFZ.  With the two
separate MHF approaches for IPv4 and IPv6, there is no communication
whatsoever from the ETR to the ITR.  The ITR neither knows nor cares
whether there are 2 separate "anycast" ETRs or not.  As far as host
communications are concerned, the situation is clearly unicast.

Maybe there would be reasons for doing this.

With encapsulation, it would be trickier, since the Ivip ITRs do
sometimes need to engage in two-way communication with ETRs to manage
PMTUD - Path MTU Discovery.  I will assume for the moment this could
be done. (The communications are brief and the system would probably
cope with a router switching its forwarding so the ITR found itself
dealing with E2 instead of E1.)

Changes in the routing system, such as R1 choosing R3 instead of R2
as its next hop for the ETRs prefix, may still result in a differing
PMTU between I1 and whichever ETR receives the packet.  But that
would have occurred in the Fig 4 and Fig 5 scenarios anyway.  I will
consider this anycast ETR scenario when developing Ivip's PMTUD system.

No matter what the ETR arrangement, assuming it works, the above is
still unicast from the point of view of the host.  As with Fig 1 and
2, the BGP routing system can't tell the difference between host
unicast and host anycast.

If encapsulation is used, for PMTUD handling, the core-edge
separation scheme may need to have special mechanisms to cope with
anycast ETRs which presumably don't communicate directly with each
other.

In the above diagram, there is only one ETR address for the micronet,
or in LISP terms, only one RLOC address for the EID.  Multihoming is
not being attempted, but this could still be used for portability,
including for the TTR mobility model.

So in this case, there is no multihoming failure detection decision
to make.  With both Ivip and LISP, the ITRs always tunnel packets to
the one ETR address.   If one ETR becomes unusable, then packets will
be lost as long as its router still advertised that prefix.  This is
the risk taken by whoever chose to have anycast ETRs.  However, if
both ETRs are working fine and can connect to DH, then if R5 dies, or
becomes unreachable to the rest of the Net, then BGP will adapt and
cause all tunneled packets from all ITRs to go to R7 and therefore
E2, with no significant disruption in host-to-host connectivity.

There could be significant differences between how Ivip and LISP
would handle multihoming failures if there were anycast ETRs at one
or both ETR addresses.  Fig 6 depicts two ISPs each with two anycast
ETRs, each with its own border router advertising the ETR address to
the DFZ.  There is still a single destination host.  I am not sure
why anyone would do this, but there may be a reason.

     ITRs               ETRs

            R2------R5-->E1
           /  \     |      \     Each ISP has anycast ETRs.
  SH-I1->R1   R4---R6       \
           \  /     |        \
            R3------R7-->E2---\
             |                DH Single destination host = unicast.
            R9------R10->E3---/
           /  \              /
  SH2-I2-R12--R13           /
           \  /            /
            R14-----R11->E4
  Fig 6

This also shows a second sending host SH2 with its ITR I2.

With LISP, APT or I guess TRRP, each ITR figures out for itself which
of the two ETR address in the mapping it will use for tunneling
packets with the EID address of DH.

With LISP, I will assume the E1/E2 RLOC address is preferred in the
mapping, when the ITR can reach both E1/E2 and E3/E4.  For example,
the initial path taken through the routing system by the encapsulated
packets is:

   I1  R1  R2  R5  E1
   I2  R12 R9  R3  R7 E2

(I2's packets may well have gone via R4, R6, R6 and then to E1, but I
want an example in which I2's packets go to a different ETR than E1,
even though they are anycast on the same address.)

If R7 dies, I2 will still find the RLOC address of E1/E2 reachable,
since the BGP routers will quickly readjust themselves to send the
packets:

   I2  R12 R9  R3  R4  R6  R5  E1

That is fine, since E1 is just as good as E2 (other than any problems
with potential session state in ITR<->ETR communications - maybe LISP
has no such stateful ITR<->ETR communications).  However, going back
to the initial state, if E2 dies, or can't reach DH and in either
case R7 still advertises its address, then there will be trouble
which LISP's I2 ITR will recover from:

I2 will find (by some means, I am not sure what) that E2 is
unreachable.  Since R7 is still advertising the prefix which
encompasses the E1/E2 ETR address, there's no way I2's packets to
this address will get to E1.

So I2 will figure out that the ETR (it assumes one ETR) at the
address of E1/E2 is dead and will therefore use the other RLOC
address instead - that of E3/E4.  Now, the two paths used by packets
will be:

   I1  R1  R2  R5  E1
   I2  R12 R9  R10 E3

The free-wheel'in LISP ITR will have figured out its own arrangements
for coping with a partial outage in the reachability of what, to the
LISP system, is a "single" ETR.

The situation with Ivip might be less happy, since Ivip ITRs don't do
any reachability testing (except, as a by-product of PMTUD
management, which is only needed for encapsulation).  With the above
example, both ITRs would initially be tunneling packets to a single
ETR address: E1/E2.  Ivip ITRs have only a single ETR address to use.
It is up to the end-user network to send a mapping change if it wants
the ITRs to tunnel packets to another ETR address.

With the above failure of E2 on its own, with R7 continuing to
advertise E2's address, I2 would not be able to get packets to DH at all.

The only way the Ivip system could respond to the outage properly
would be for the mapping to be changed to the E3/E4 address instead.
(With Ivip, an end-user network would typically pay a probing company
to constantly probe reachability and to issue mapping changes as
necessary to restore connectivity in the even of one ETR being
unusable - by sending a mapping change with the address of the other ETR.

Therefore, if an end-user network chose to have anycast ETRs, it had
better implement some fancy scheme for testing that every single one
of them is reachable from wherever ITRs might be - and that that each
such anycast ETR is able to get packets to the destination network.
Depending on how topologically separated E1 is from E2, and likewise
E3 from E4, and depending on how many probing servers were used, and
where they were topologically located, it may or may not be possible
to achieve this.

I am not sure why anycast ETRs would be an advantage.  Ivip could
probably support them for MHF, and probably for encapsulation too.  I
doubt if LISP-ALT could support them, because (AFAIK) there is so
much ITR-ETR communication and because ETRs are the authoritative
source of mapping and so have to communicate with the ALT network,
probably via Map Servers.  Assuming Ivip could support anycast ETRs,
special care would be needed in probing the connectivity of all such
ETRs.

The question of whether ETRs are anycast is in some ways separate
from whether the destination hosts are anycast.  Figs 3, 4, 5 and 6
show anycast ETRs with a single unicast DH destination host.

It is easy to have a core edge separation with unicast ETRs and
*locally* anycast destination hosts.  Here is an adaptation of Fig 4
showing three destination hosts, all with the same IP address, in the
same end-user network:

     ITR               ETRs
            R2------R5
           /  \     | \         Single ETR in each ISP.  Each ISP
  SH-I1->R1   R4---R6  E1       has dual border routers advertising
           \  /     | /  \      the ETR address.
            R3------R7    \          DH1
             |             \        /
            R9------R10    [network]--DH2
           /  \       \    /        \
         R12--R13     E2--/          DH3
           \  /       /
            R14-----R11          Three destination hosts = locally
  Fig 7                          unicast.

This local use of anycast clearly has nothing to do with the BGP
routing system or the core-edge separation system, which would
support it perfectly.

What about anycast ETRs each with their own destination hosts, which
are therefore also host anycast?

     ITRs               ETRs

            R2------R5-->E1->DH1
           /  \     |            Each ISP has anycast ETRs.
  SH-I1->R1   R4---R6
           \  /     |
            R3------R7-->E2->DH2
             |
            R9------R10->E3->DH3
           /  \
  SH2-I2-R12--R13                Four destination hosts, each one
           \  /                  anycast in a global sense.
            R14-----R11->E4->DH4
  Fig 8

E1 and E2 are on the same (RLOC) address, which is in a prefix
advertised by both R5 and R7.  Likewise, E3 and E4 are both on
another (RLOC) address, which is advertised by both R10 and R11.

  Note: Just because this could be made to work doesn't
        mean it is a good idea or that this is a use of Ivip
        etc. which helps with scalable routing.

        Fig 8 could in principle help with routing scalability
        since the ETRs E1/E2 are on one address in a prefix of
        one ISP and the E3/E4 ETRs are on another address of
        another ISP.  However, it is only a scalable use of Ivip
        if these same prefixes can be used by many other end-user
        networks.  Presumably R5 and R7 are geographically at
        very different locations, otherwise there would be little
        point in having separate ETRs.  But why would an ISP do
        this?  Maybe they would.  Maybe other customers want a
        similar arrangement.  But if they don't, then this
        represents an irregular use of a prefix and probably the
        only beneficiary is going to be for network with above
        ETRs.  That makes it one or two BGP advertised prefixes
        for one end-user network, which achieves no benefits
        in routing scaling.

        See also Figs 9 and 10 for a similar example.  It might
        be best not to use Ivip or any other core-edge separation
        technique.

I think this would have similar potential problems as the scenario
depicted in Fig 6: LISP-ALT probably not going to work, due to the
difficulties supporting the complex communications of ETRs with ITRs
and the ALT network.  If it did, the free-wheel'in ITRs may be able
to cope on their own with some outages which would be trickier to
detect and cope with if the system was Ivip.

This is genuinely host anycast from the point of view of the hosts.
However, the fact that it is host anycast is only visible to the hosts.

As far as I can see, in all these scenarios, whether the destination
host is unicast, locally anycast (Fig 7) or globally anycast (Fig 8),
the BGP system and the core-edge separation system both work fine and
dandy.  They can't tell anything about the unicast/anycast status of
the destination hosts *because* the core-edge separation scheme has
nothing at all to do with hosts.

I would be surprised if the same would be true of a core-edge
separation scheme.  There, the hosts have much more complex stack and
perhaps application software.  I can't imagine how this would work
with two physical hosts having the same IP address, within the one
local network (Fig 7) or in separate topological places as in Fig 8.

So I think this is another reason to prefer core-edge separation
schemes over core-edge elimination schemes.  The former continues to
allow for the use of anycast hosts, and the latter either doesn't
allow it, or would involve some additional complications to make it,
or something similar to it, work.   However, perhaps in a core-edge
elimination scheme, all the things done by anycast at present are no
longer needed.  (I can't imagine how, but I don't clearly understand
any core-edge elimination schemes.)

I don't support core-edge elimination schemes (AKA Strategy B in
Bill's taxonomy) and will leave someone else to debate how they would
 work with, or replace, anycast hosts.

> bound the unforeseeable consequences if that isn't true in the new

Hopefully the above treatise will be a starting point for foreseeing
any differences and at least some of the consequences.

> perspective of the Internet core its anycast from three distinct

If you had a single server at your single data centre, then this
would be an ordinary unicast server with three separate "border
routers" in your global VPN-linked network.

If you had three separate servers somehow operating on the same
address in your data centre, this would be locally anycast hosts with
three separate routers advertising the same prefix.  I am not sure
why anyone would do this, or how they would work except for stateless
communications, but it would be possible.  Presumably there would be
three routers in the local network, one for each host, and each one
would stop advertising the address as soon as its host died.  That
would give automatic failover.

I understand you have three separate hosts, in the one data centre,
with the same IP address (at least as far as their communications
with the outside world are concerned - they would have other
addresses so you could talk to them separately via TCP etc.).  You
have some system for directing packets to the three servers based on
which VPN they arrived from.  You presumably also take the emitted
packets from each server and send them out on the matching VPN.

Assuming there is a direct 1:1 relationship between VPN and server,
then I think you have a genuine host anycast arrangement.  However,
the servers are co-located and could, in principle, share session
state.  If they did this, then you could use them for session-based
communications.

Anycast servers are not inherently incapable of being used for
session-based communications.  It is just that they are usually
assumed to be physically separate and therefore incapable of sharing
the state of each session.

I think you could implement your project with Ivip.  You want a
single IP address for your three servers and you want packets sent to
this address to be tunneled to your data centre via physically
separate routers at geographically and topologically distant sites
SA, SB and SC.  These routers connect to your data centre by
presumably robust VPN links.

I think the motivation for this must be one or the other or both of:

  1 - You don't trust the interdomain routing system (BGP + Ivip
      or whatever) to get packets from sending hosts to your
      data centre.

      AND you would prefer to rely on the interdomain routing
      system to get the packets to the generally closer sites
      SA, SB and SC together with the costs, reliability etc.
      inherent in the VPN links to your central data centre.

      This may be motivated by concerns over path lengths, delays
      packet loss rates etc.  It may also be motivated by wanting
      to reduce the ability of certain parties to observe the passage
      of these packets between those hosts and your servers.

  2 - You want to use the approximate geographical / topological
      information implied about the sending host due to its
      packet arriving at one of your S1, S2 or S3 sites.

      So you presumably choose to do this rather than use a
      geographically / topologically sensitive DNS system to
      give out different IP addresses to hosts in different
      areas of the Net, as is done by Akamai.

I guess the way you are achieving this now is like:

                    S1
            R2------R5---\
           /  \     |     \
  SH---->R1   R4---R6      \
           \  /     |       \            /-DH1
            R3------R7------[Data center]--DH2
             |      S2      /            \-DH3
             |             /
            R9------R10---/
           /   \   / S3
  SH2----R12--R13-/              3 destination hosts, each one
           \  /                  anycast in a global sense since they
            R14                  have the same address.
  Fig 9

All three routers R5, R7 and R10 advertise the same prefix. Since you
can't use this prefix anywhere else, unless you are using it also for
some other purpose, you have one prefix of your own for this
particular project.  This is either your own PI prefix, or some
prefix you have convinced a single ISP to advertise (and they have
routers at all three sites) or you have somehow convinced separate
ISPs to advertise the one prefix which is not yours.  In the former
case you have portability and in the latter two you do not.

If R5, R7 and R10 are yours and you multihome them like this, then it
should work pretty well, provided each router stops advertising the
prefix the moment the VPN link dies and if your data centre and
servers copes OK with one region's hosts suddenly connecting via one
of the other routers and therefore using a different VPN.  To survive
that, if your servers use session-based protocols, they need to be
able to share the session state.

To achieve point 1 with Ivip, you need to have an ETR at each site
S1, S2 and S3.  These need to have the same IP address, since the
destination hosts have the one IP address and therefore all ITRs will
use the same mapping.  So these will be three anycast ETRs.

   (Side-note on LISP:  If you were doing this with LISP, but LISP
    couldn't support anycast ETRs, you could make it happen by
    having each ETR on its own RLOC address and then have all three
    addresses in the mapping.  Each ETR would have to somehow drop
    packets with source addresses which it decided were indicative
    of the source packet not being in its area.  Then, each ITR would
    discover that only one of the ETRs was reachable.  How could the
    ETRs do this?  They would need to look at the outer source
    address of the packets, which shows the ITR address, and do some
    fancy algorithm to figure out where the ITR was in its
    preferred area or not.   This cannot be discovered from the BGP
    system by any conventional means.  So this is much messier and
    probably less effective than using anycast ETRs with Ivip, in
    which case the BGP system does all the work of sending packets
    from ITRs in a given "area" as defined by the DFZ's current
    forwarding behaviour.)

     ITRs               ETRs
                    S1
            R2------R5-->E1    3 Anycast ETRs - all the same address.
           /  \     |     \
  SH-I1->R1   R4---R6      \
           \  /     |       \            /-DH1
            R3------R7-->E2-[Data center]--DH2
             |      S2      /            \-DH3
             |             /
            R9------R10->E3
           /   \   / S3
  SH2-I2-R12--R13-/              3 destination hosts, each one
           \  /                  anycast in a global sense since they
            R14                  have the same address.
  Fig 10

To do this, R5, R7 and R10 would all be advertising the same prefix.

The most likely arrangement is that you have this prefix only for the
use of this particular set of sites, and this set of 3 servers - and
perhaps also for other similar sets of servers.

This would mean that you are either operating your own routers
directly, or that you are getting someone else to advertise your prefix.

As long as you were the only end-user network using this arrangement,
then there is no benefit to using Ivip, at least in terms of
scalability.  Your prefix would be a MAB (Mapped Address Block) and
this would be only used for your end-user network.  Therefore the
scaling benefits of Ivip - many end-user networks sharing the one MAB
and therefore spreading their burden on the BGP control plane over
exactly one prefix, rather than one or more for each network - would
not apply in this case.  (The same would be true of LISP, APT or TRRP.)

Unless there was some other benefit to using Ivip, I suggest you not
bother with it and continue to do exactly what you are doing now - as
in Fig 9.

In some core-edge separation schemes, there is talk of "transition
periods" and the like, as if one day, it won't be possible for an
end-user network to have its own conventional BGP-mapped prefix.
That is not the case with Ivip.  So you would always be able to do
what you are currently doing.  It is inherently unscalable, but
Ivip can't do exactly what you want in a way which helps with
scalability - unless there are other end-user networks such as your
own which also want to use these ETRs or ETRs in the same prefix in
the same sites S1, S2 and S3.

> impede the deployment of the unwary plan?

You can do it now.  You could probably do it with Ivip (if
encapsulation is used for Ivip, I would need to ensure that the PMTUD
stuff worked OK with anycast ETRs - I am not sure this is possible),
but you are probably better doing it as you do now.  LISP probably
couldn't do it.

AFAIK, as long as you are the only network with anycast anything in
these three locations, then you need your own BGP advertised prefix.
 You need this for the way you do it now and for Ivip - so there are
no scaling advantages to using Ivip.

How would you do this with a core-edge elimination scheme?  That
would have to be answered by someone who designed such a scheme.

  - Robin

---

From: Tony Li <[email-masked]>
Date: Wed, 22 Apr 2009 09:03:58 -0700

Hi Bill,

> drop one of those unicast routes.

So, Turner is aggregating (hopefully) large blocks of end-hosts behind 
each of those prefixes.  This aggregation is purely a network layer 
issue and is not tied to transport or applications.

Anycast looks to be a pure application/service layer issue.  Yes, ok, 
you COULD aggregate anycast for common services that have the same 
source.  I don't see how that helps the general case of services that 
are supported by multiple sources (e.g., DNS, NTP).  Those don't seem to 
aggregate at all.

In some sense, you could draw the analogy between anycast and a 
promiscuous use of PI addresses.

> unicast or anycast. Big important web site = at least one more route

Who decides what's big and important?  And how does that not end up in 
an international court (e.g., ICANN).  If every web site ends up with a 
route, then it's game over.

> non-deterministic is "travel all valid directions." I'm open to a

Non-determinism in the classical CS sense would be 'travel in the right 
direction' where the direction is determined without regard to the 
content of the packet and state in the network and yet somehow, the 
right decision is always made.

I'd favor 'unicast' for "pick one direction" and 'multicast' for "pick 
all valid directions".

> web page? Which one do you zero in on and change?

Having to have proxies (ALG's) in the network in the first place.  Evil, 
evil, evil.  Yes, I have to live behind one.

> either answer out of scope would, at the very best, be failing to

Ok, but asking the routing layer to defy the laws of physics (i.e., 
scale without aggregation) is unlikely to be productive.

Tony

---

From: Robin Whittle <[email-masked]>
Date: Thu, 23 Apr 2009 14:09:36 +1000

Short version: Summarising and extending my previous message to
               include more about anycast with a core-edge
               separation scheme and to explore it with
               a core-edge elimination scheme.

               Replying to Bill about how global anycast would
               work with core-edge elimination.

               In summary:

                  Global anycast has its uses, but it is highly
                  unscalable, since there needs to be a separate
                  prefix advertised in the DFZ for every set of
                  anycast servers - for each anycast IP address.

                  A core-edge separation scheme could achieve the
                  same benefits, by using anycast *ETRs*.  This
                  has no benefits over the conventional BGP-based
                  approach and is equally unscalable.

                  A core-edge elimination scheme *might* be able
                  to do global anycast too - but it would be more
                  complex than with the conventional BGP approach.
                  There would be no scaling benefits - it would
                  be just as unscalable as the conventional BGP
                  approach.  However, a core-edge elimination
                  scheme, once fully adopted, does not allow
                  end-user networks to have their own PI prefixes.
                  So it would not be possible to use the conventional
                  BGP approach.

               I will write a separate message on Disaster Recovery.

Hi Bill,

To summarise and extend:

  http://www.ietf.org/mail-archive/web/rrg/current/msg04897.html

For core-edge separation schemes:

  1 - The routing system - the BGP-based DFZ and probably some other
      routers, plus the ITRs, ETRs etc. of the core-edge separation
      scheme - can't tell the difference between host unicast and
      host anycast.  This is another way of saying they will work
      fine for packets for both scenarios.

  2 - However, just host-anycast with a core-edge separation scheme
      does not have the same effect on packet flow in the DFZ as
      conventional BGP-based host anycast with each host having its
      own separate BGP router.

      The main, perhaps only, reasons people are interested in
      conventional BGP-based host anycast are (AFAIK) as follows.
      These are all dependent on the normal behaviour of the BGP
      routing system.

      a - "Shortest" (generally, in BGP terms) path to the nearest
          router which advertises the prefix of its anycast host.

      b - Automatic failure recovery as long as the router stops
          advertising the prefix if the one or more hosts using
          this prefix dies.  If so, the other BGP routers will
          soon get the packets which would have gone to this one.

      c - Load sharing over many hosts, in geographically and
          topologically diverse sites, which gives the system
          a high capacity and a great resistance to failure
          without involving DNS in any way, since it always
          responds to the one IP address.  This is also extremely
          important as a way of achieving high total bandwidth
          to survive DoS attacks with floods of incoming packets.

      It may also be desired and possible to:

      d - Imply something about sending host location from which
          of the anycast BGP routers got the packet (as you are
          doing with your project which you mentioned at the end
          of msg04894) - but AFAIK this information is not used for
          the most prominent BGP-based host anycast usage: root
          nameservers.

      Host-anycast with a core-edge separation scheme and a single
      (unicast) ETR (Fig 9 as noted below) involves no significant
      difference in the way packets traverse the DFZ compared to
      conventional BGP-based unicast (Fig 3).

      Fig 1 (msg04897) shows BGP-based host unicast - with two border
      routers advertising the prefix.  This is ordinary operation
      for many hosts today, which use PA space on an ISP with
      two DFZ border routers each with its own upstream link to
      separate parts of the DFZ.

      Fig 3 shows core-edge separation with a unicast host and a
      unicast ETR, with two border routers advertising the ETR's
      prefix.  This is likewise basic, ordinary, core-edge
      separation operation as with LISP, APT, Ivip or TRRP - where
      the ETR address is in a PA prefix of an ISP with two BRs.

      Fig 9 - if we ignore the bottom half - is just like Fig 3
      with a unicast ETR, but there is host anycast at the
      one local network the ETR connects to.

      So using a core-edge separation scheme to do host-anycast
      with a single (unicast) ETR (rather than anycast ETRs) brings
      none of the benefits of conventional BGP-based anycast, because
      the ITR->ETR tunnel is conventional unicast.

  3 - To achieve the goals listed above - a, b, c and perhaps d -
      with a core-edge separation scheme, it is necessary to have
      anycast *ETRs*.  This is the only way of achieving the
      desired packet paths through the DFZ and of using the DFZ
      routers to automatically send the packet to the nearest
      router of an ETR which handles the EID (micronet) prefix
      of the multiple anycast hosts.

      Fig 11 shows conventional BGP-based host anycast:

                  R2------R5------>DH1
                 /  \     |
        SH---->R1   R4---R6
                 \  /     |
                  R3------R7------>DH2
                   |
                  R9------R10----->DH3
                 /  \
        SH2----R12--R13                Four destination hosts, each

                 \  /                  one anycast in a global sense.
                  R14-----R11----->DH4
        Fig 11

      To achieve the same DFZ packet flow patterns with a core-edge
      separation scheme, you would use anycast ETRs as with Fig 8:

           ITRs                ETRs

                  R2------R5-->E1->DH1
                 /  \     |            Each of four ISPs has an
        SH-I1->R1   R4---R6            anycast ETR.  So each ISP's
                 \  /     |            router (R5, R7, R10 & R14)
                  R3------R7-->E2->DH2 is advertising the same
                   |                   prefix.
                  R9------R10->E3->DH3
                 /  \
        SH2-I2-R12--R13                Four destination hosts, each

                 \  /                  one anycast in a global sense.
                  R14-----R11->E4->DH4
        Fig 8

      This is anycast ETRs (all with the same "RLOC" = Locator
      address) and anycast hosts (all with the same EID =
      Identifier = micronet address).

      You could also achieve the same DFZ packet paths with four
      identically anycast ETRs, each with a VPN or a dedicated
      link of some kind to a data centre:

                  R2------R5-->E1
                 /  \     |      \
        SH-I1->R1   R4---R6       \
                 \  /     |        \
                  R3------R7-->E2---\
                   |                [Data center]
                  R9------R10->E3---/
                 /  \              /
        SH2-I2-R12--R13           /
                 \  /            /
                  R14-----R11->E4
        Fig 12

      where you could have a single host, which is therefore
      globally unicast.  You could also have multiple hosts
      on the same address at the data centre, and therefore
      locally anycast.  Depending on how the data centre's
      router linked the VPNs to the hosts, you could make the
      system behave like Fig 8, or you could have all the
      incoming packets go to one router, which picks the
      "closest" (or however the IGP chooses the next hop)
      router of each of the locally anycast hosts.

      You could also have some kind of load distributor
      which behaves like a single host but spreads packets
      out to a server farm, ideally maintaining the same
      distribution over sessions, so TCP etc. works fine.

  4 - So with a core-edge separation scheme, you can get the
      benefits of conventional BGP-based anycast, but only
      by using anycast ETRs.  Whether or not these anycast
      ETRs use their own (anycast) hosts (Fig 8) or whether
      they link in some way to one or to multiple hosts
      (Fig 12) is a separate issue.

  5 - Conventional BGP-based anycast (Fig 11) is even more
      unscalable than ordinary PI prefixes for end-user
      networks, for two reasons at least:

        A - Each router needs to withdraw the prefix if
            its host dies.  Therefore, the prefix can
            only realistically be used by one host (or
            perhaps a load-balanced host farm), in which
            case the router still needs to withdraw the
            prefix from the DFZ as soon as the host or
            host farm dies.

            Therefore, the prefix can only be realistically
            used for a single host (or host farm) at each
            location.  Maybe each such host uses multiple IP
            addresses, each of which is globally anycast,
            but whether they have one or multiple such
            addresses doesn't alter the fact that the router
            needs to stop advertising the entire prefix if
            the host or host farm dies.  (Likewise, for
            Fig 12, if the VPN link dies.)

            Therefore, the prefix can't be shared by
            multiple end-user networks, or perhaps even
            by the one end-user network trying to run
            two separate anycast servers from each router -
            each such host (or host farm) needs its own
            prefix so the router can withdraw it if the
            host or host farm dies.

        B - Even if the above was not true, it is unlikely
            that two separate end-user networks would want
            to run their anycast hosts at exactly the same
            sites as some other end-user network.

      Therefore, conventional BGP-based anycast is just as
      unscalable as any other end-user PI prefix, plus the
      additional constraint that if the network wanted to
      run two anycast servers at each site, it would
      need to advertise two separate prefixes at each site.

  6 - While a core-edge separation scheme *could* be used
      to achieve similar "anycast" packet flows in the
      DFZ, by using anycast ETRs, this is no more scalable
      than the conventional BGP-based host anycast, for
      reasons identical to those in point 5, but for which
      the term "host or host farm" is replaced by "ETR".

  7 - So AFAIK, there is no benefit at all using a core-edge
      separation scheme with anycast ETRs, to achieve the
      same or similar DFZ packet flow patterns of conventional
      BGP-based anycast.  The KISS principle therefore rules
      out the use of core-edge separation schemes to achieve
      the same DFZ packet flow benefits of conventional BGP-
      based anycast.

  8 - If the potentially anycast hosts are in a single data
      centre, then you could use conventional BGP techniques
      as you do with your project (Fig 9) or you could use
      a core-edge separation scheme to do it (Figs 10 & 12)
      - but the KISS principle favours the conventional BGP
      approach.

In short, a core-edge separation scheme can be used to achieve the
same benefits of conventional BGP-based anycast and/or fancier VPN
and data-centre based arrangements like your project.  However, there
are no scalability benefits in doing so, and the system would
probably be more complex than using ordinary BGP methods.

I didn't write anything specific about core-edge elimination schemes,
in which the hosts have one or more, potentially unstable, "locator"
addresses (much like a MIP Care of Address, I think) but in which the
applications identify the hosts with persistent Identifier addresses
and so are able to maintain sessions while each host:

  1 - Is mobile - rapidly gaining and losing locator addresses.

  2 - Is portable - the host retains it identifier address whenever
      a new ISP is used, giving the host a new locator address.

  3 - Needs to use a previously unused locator address from ISP-2
      due to the currently used one (from ISP-1) ceasing to function
      - for instance in multihoming service restoration.

HIP is an example of a core-edge elimination scheme.  HIP is not a
practical solution to the routing scaling problem, because it
involves host changes (stack and I think API and applications) to
work, and since the multihoming, TE and portability it could bring
only work with similarly HIP-upgraded hosts.

Since all core-edge elimination schemes involve some new addressing
arrangements (HIP uses a unique namespace for host identifiers) I
think none of them are practical solutions to the routing scaling
problem, since we must rely on voluntary adoption to introduce this
solution to most and ideally all end-user networks over a period of
years:

  http://www.firstpr.com.au/ip/ivip/RRG-2009/constraints/

Since AFAIK no-one else has done so, I will now try to imagine how a
    core-edge elimination scheme (as I understand it) could do
something resembling conventional BGP-based anycast.

There are no ITRs or ETRs in a core-edge elimination scheme.  Just
today's basic routing system, but with fancier hosts which can keep
operating, maintain sessions etc., despite using one or more
potentially unstable locator addresses.

The only benefits of anycast, as far as I can see, are those listed
above: a, b, c and perhaps d.  To achieve these, you need to
replicate the patterns of DFZ packet travel, in which packets
typically travel to the "nearest" router of a functioning anycast host.

This relies on BGP or whatever other routing systems are involved.
To achieve this, a core-edge elimination scheme needs to have
multiple routers advertising the same prefix (or at least a prefix
which includes the "anycast" address).

In the core-edge elimination scheme, this is a locator address.  So
all the "anycast" hosts need the same locator address.

I will refer to the one or more ordinary hosts which is communicating
with one or more of the "anycast" hosts as the Correspondent Host
(CH).  This has one or more, potentially unstable, unicast locator
addresses and a single, globally unique, identifier.

For any CH to be able to communicate with the one or more "anycast"
hosts, it needs to be able to regard that set of hosts as behaving
like one conventional host.  (Unless perhaps the core-edge
elimination scheme has special provisions for implementing something
equivalent to anycast.)  Therefore, all the "anycast" hosts must have
the same identifier.  This is because at any time, the CH could have
its packets sent to a different "anycast" host than the one the
packets were sent to a moment before.

This could be due to:

  1 - The CH starts sending packets from a different locator address.

  2 - Something in the routing system changes, so the packets are now
      sent to a different router which is advertising the prefix of
      the "anycast" hosts.  This includes changes due to of the
      "anycast" hosts going down, or coming up.

Note that this precludes something which would ordinarily be
acceptable for hosts in a core-edge elimination scheme:

         One of the "anycast" hosts changing its locator address and
         therefore requiring its router (or perhaps some other
         router) to advertise a different prefix for its new locator
         address.

This can't work, because the only way this "anycast" scheme can
achieve the desired pattern of packet flow in the DFZ is for all
the hosts to have the same locator address.

So it looks like you *could* use a core-edge elimination scheme to
achieve similar DFZ packet flows as with conventional BGP-based
anycast and so achieve goals a, b, c and perhaps d (with a VPN or
some other link to a central data-centre).

However, you would have to accept the following restrictions, at least:

  1 - You have to organise all the hosts to have the same locator
      and identifier.  (So how do you talk to them for admin
      purposes?  Can a host have multiple identifiers, one of
      which is the same for all these hosts and another which is
      unique?)

  2 - As with 5 A above, you need to devote an entire BGP prefix
      to this particular set of anycast servers.

  3 - As noted below, you actually need an end-user network specific
      prefix, which is at odds with how a core-edge elimination
      scheme is supposed to work.

Therefore, any attempt to use a core-edge elimination scheme for
"anycast" is:

  1 - Probably more complex and constrained than the conventional
      approach.

  2 - Does not allow any scaling benefits which ordinarily come
      from a core-edge elimination scheme.

  3 - Is just as unscalable as conventional BGP-based host anycast.

The scaling benefits of a core-edge elimination scheme result from
all hosts in end-user networks getting at least one address from each
of their one or more ISPs - where those addresses always come from
the large (lots of addresses = short prefix) prefixes which belong to
the ISPs.  In other words: end-user networks do not have their own
prefixes and work perfectly well on PA addresses from the ISP's well
aggregated (highly scalable) prefixes.  For instance, one ISP site
may have one or a few such prefixes which may have millions of IPv4
addresses or bazillions of IPv6 /64s.  Each such prefix is a single
entry in the DFZ routing table but supports the needs of potentially
thousands, millions or whatever end-user networks.

In summary, assuming the goals of "global host anycast" a, b, c and
perhaps d:

   Conventional BGP approach as used today:

      Works fine.  Requires a single prefix for each such set of
      anycast hosts (point 5 A above).  Therefore, is unscalable to a
      high degree - even more so than an ordinary end-user PI prefix,
      since this end-user PI prefix for anycast hosts needs to be
      dedicated to the one set of hosts: the one set on a (typically)
      single IP address.

   Core-edge separation, using anycast ETRs.

      Works about as well as the conventional approach, but is
      equally unscalable for the same reasons.  Since it is more
      complex, it is probably best to avoid it and use the
      conventional BGP approach instead.

   Core-edge elimination

      Could be made to work, but is more complex than the
      conventional approach and is just as bad in terms of
      scaling.   However, if the Internet was somehow converted
      to a core-edge elimination approach, it would be impossible
      to do the conventional BGP approach, in which there was no
      distinction between identifier and locator (the IP address
      means both).

So adoption of a core-edge elimination approach would probably make
global anycasting more difficult than at present.

In contrast, a core-edge separation scheme could do it, in a probably
more difficult manner. - without getting in the way of using the
simpler BGP approach.

***  This is all assuming the core-edge separation scheme is not
     intended to prohibit end-user networks having their own
     conventional PI prefixes, as is required to do conventional
     BGP anycast or its anycast ETR equivalent.  IOW, the
     "separation" is only partial and is not intended to ever be
     complete.

     I recall that a goal of APT (as currently defined - maybe this
     will change) is the eventual complete separation of the "core"
     address space (ISP prefixes for ITRs, ETRs and Default Mappers
     etc.) and  the "edge" address space (EIDs for end-user network
     hosts).

        http://tools.ietf.org/html/draft-jen-apt-01#section-3

     The definitions of "transit space" and "delivery space" imply
     a complete separation of the global unicast address space into
     two classes.  So "transit" addresses are RLOCs for ITRs and
     ETRs and "delivery" space addresses are EIDs for end-user
     network hosts and their internal routers etc.   The definitions
     include two separate routing scopes or "areas".  I understand
     this as meaning complete separation, since it would be
     no route for a packet from any "transit" address to any
     "delivery" address or vice-versa.

     These would be two separate subsets, in various interspersed
     prefixes, in the current global unicast address range.

     I think this is an unnecessary and probably unachievable goal.

     Another aim of APT (IIRC, but I can't easily find a reference)
     is to improve security by somehow trusting packets sent from the
     "core" (transit) subset of the address space in a different
     manner from those sent from the "edge" (delivery) space.  I
     think this would be very difficult to do robustly, since a
     single attacker with control of a host with an ISP's (transit)
     address could do whatever they liked in the "core".

     Ivip, and I think LISP, do not have a specific goal of
     complete separation, as does APT.  So with Ivip and I think
     LISP, it would always be possible for an end-user network to
     use a PI address for a set of globally anycast hosts using
     the conventional BGP approach, or to use the prefix for
     the anycast ETR approach.

It seems that any global use of anycast is inherently costly to the
DFZ routing system -  since it involves a specific prefix for every
set of anycast servers.

This is fine for a limited number of sets which are widely regarded
as being important to everyone - such DNS root servers.   However, if
everyone and his dog (Aussie phrase) starts doing it, for purposes
such as your project (end of msg04894) then the burden all these
place on the DFZ control plane would come under increasing scrutiny.

You wrote, in:

  http://www.ietf.org/mail-archive/web/rrg/current/msg04901.html

> Hi Robin,
>
> What's the difference between anycast and unicast? Is it a
> difference in the forwarding or data planes? Or is it a difference
> in how the respondent machine(s) understand the address?
>
> It's the latter of course.

Yes, but the reason most people want to do it on a global scale is
because of the way the packets flow in the DFZ - to the "nearest" (in
BGP terms) router advertising the prefix which encompasses an
operational host.

> In strategy B,

Core-edge elimination schemes:

  http://bill.herrin.us/network/rrgarchitectures.html
  http://www.firstpr.com.au/ip/ivip/rrgarch/
  http://tools.ietf.org/html/draft-irtf-rrg-recommendation-02

> the host's understanding of
> each packet moves out of the packet forwarding system entirely and
> into the map used by the respective hosts.

Yes - the upper levels of the stack and all the applications don't
care about the "locator" address with which packets are sent and
received.  All they care about is the "identifier" of the hosts
concerned.

> A strategy-B host literally
> doesn't care what layer-3 addresses were attached to the received
> packet.

Like I said!

> The address in the routing system only retains semantics
> associated with the forwarding process itself. So, as long as the
> mapping system adequately supports something that looks like
> anycast, the whole strategy B system does as well.

This is a rather mathematical, rule-based, way of looking at it -
which doesn't seem to recognise some pertinent principles.

AFAIK, the only reasons you want anycast on a global basis are those
reasons a, b, c and perhaps d listed above in point 2.  These all
relate to the way the packets travel in the DFZ, which is determined
by the conventional routing system and the *locator* (layer 3)
destination address of the packets.

So to achieve these benefits with a core-edge elimination scheme, all
the routers need to advertise a prefix which contains the single
*locator* IP address of all the anycast hosts AND (AFAIK) all those
hosts need to have the same identifier.

AFAIK, having multiple hosts with the same locator is a violation of
the general principles behind core-edge elimination schemes.
Likewise, perhaps even more so, is the concept of multiple hosts
having the same identifier.

Yet it brings you no benefits over the conventional BGP approach -
and worse still, AFAIK, you with a core-edge elimination scheme in
place and used by all hosts, you wont be able to use the conventional
BGP approach.

APT, it seems, once fully deployed, would also preclude the
conventional BGP approach or the anycast ETR approach, unless you
fashioned your end-user network as an ISP, got yourself an RLOC (core
= transit) prefix and set up the equivalent of an ISP network, with
Default Mappers ETRs and ITRs etc. in a unified manner somehow
located at your several chosen sites.

I will respond to what you wrote about disaster recovery in a
separate thread.

 - Robin

---

From: William Herrin <[email-masked]>
Date: Thu, 23 Apr 2009 01:05:37 -0400

Hi Robin,

I think maybe you're missing the forest for the trees here. The
functional equivalent of anycast in a strategy-A system is a 1-to-many
address-to-ETR map where the ETRs in question are entries into
distinct networks instead of entries into the same network. The
anycasting functionality happens entirely in the ITR when it chooses
the ETR. The ETR's character is that it has only one attachment in the
topology, not multiple attachments. Giving the ETR multiple
attachments would defeat the purpose.

As for anycast ETRs, I haven't thought of a single sensible use case.

>      distinction between identifier and locator (the IP address

Strategy B is like strategy A except we replace layer 4 with a
protocol suite that handles the ITR/ETR functionality internally,
eliminating the need for ITRs and ETRs. The anycasting decision
happens in the originating host, after which the packet travels (or
fails to travel) to one specific network attachment associated with
the destination. The origin may have selected from be different
attachments for the same host or it could have been attachments for
multiple hosts all of which are capable of responding to the service
request.

>    router which advertises the prefix of its anycast host.

This is the "speed" case. The premise is that the closest one will
have the shortest round trip time and the lowest probability of packet
loss.

>    soon get the packets which would have gone to this one.

Yes.

>    to survive DoS attacks with floods of incoming packets.

Yes. Point being that while DNS would work for this in theory, in
practice it runs into trouble.

>    the most prominent BGP-based host anycast usage: root

I suppose that's possible though I'm not sure what the use case is.

It seems like much of the rest of what you wrote here is based on the
faulty premise of having some kind of anycast ETRs. The only response
I can offer is: of course anycast ETRs don't make sense. Anycast ITRs
make sense. ITRs making anycast decisions while resolving the map make
sense. But ETRs are supposed to be single points of attachment in the
network topology; it wouldn't make any kind of sense for them to be
anycast.

Regards,
Bill Herrin

---

From: Eliot Lear <[email-masked]>
Date: Thu, 23 Apr 2009 09:47:41 +0200

On 4/22/09 6:03 PM, Tony Li wrote:
> are supported by multiple sources (e.g., DNS, NTP).  Those don't seem 
> to aggregate at all.
>

At one point I pondered this idea.  It would be to have several dozens 
of blocks of which people could choose one for their anycast service, 
based on what sorts of localities they wished to cover (and hence 
purchase service from).  The problem is that the number of permutations 
of those localities gets large fast, and it also violates a rule I 
imposed on myself when thinking about the problem, that perhaps is worth 
sharing:

     Any solution should scale up with market competition.

That one is arguably difficult to manage.

---

From: Robin Whittle <[email-masked]>
Date: Thu, 23 Apr 2009 18:48:30 +1000

Was: Re: [rrg] Anycast in the core architecture - sep. OK; elim not?

Short version:   We agree: anycast ETRs are of no value.

                 Bill suggests that in a core edge separation
                 scheme (Strategy A) in which there are potentially
                 multiple ETR addresses, an ITR can choose an ETR
                 in a way as to replicate the overall functionality
                 of the current (unscalable) BGP-based anycast
                 arrangement.

                 I argue they can't, since they have no way of
                 knowing the "distance" to the various ETRs.

                 I suggest the concept of a local "Distance Server"
                 which ITRs query to find out which ETR address is
                 "closest".  This gets a full feed of DFZ routes
                 directly or indirectly from a nearby DFZ router.
                 Its answer is the number of ASes in the most
                 specific DFZ route which matches the queried ETR
                 address.

                 Then there will be a scalable way of doing
                 host anycast and the "Disaster Recovery"
                 arrangement.

                 The same idea can be applied to the host stacks
                 in core-edge elimination schemes (Strategy B)
                 - if the mapping has multiple ETR addresses and
                 instructions to pick the closest one, the host
                 finds out which is closest from its local Distance
                 Server.

                 Ivip, as currently conceived, has only a single
                 ETR address for each micronet.  If this was
                 changed to have potentially multiple ETR addresses
                 then this would enable the same thing to occur as
                 just described for LISP, APT and TRRP.  The best
                 approach would be to add the "Distance Server"
                 function to the full database QSD Query Server
                 function.  Then, the QSD can return to the ITR
                 a single ETR address which it chose as the
                 closest of several.  This involves no extra
                 complexity in the ITR or the ITR<-->QSD query
                 protocol.

                 This same idea - integrating a Distance Server
                 - could also be done for APT's DMs and for
                 LISP-ALT's currently optional Map Resolvers.

                 In this light, I will write more in the future
                 about Bill's example of a "Disaster Recovery"
                 arrangement.  I am working on a message about this
                 but will revise it in the light of the "Distance
                 Server" idea.

                 With BGP, and with existing core-edge separation
                 techniques, I can find no scalable way of doing
                 anycast or "Disaster Recovery" arrangements.
                 However, by adding a "Distance Server" to these
                 schemes, I think it could be done elegantly and
                 perfectly scalably.

                 Below my signature is a copy of what Bill wrote in
                 msg04901 about "Disaster Recovery" and my attempt
                 to create a diagram for it.

Hi Bill,

Thanks for your speedy and thoughtful reply.

> distinct networks instead of entries into the same network. 

> The anycasting functionality happens entirely in the ITR when it
> chooses the ETR.

You could try to do this in LISP, APT or TRRP, where the mapping for
one EID has multiple ETR addresses, but I foresee practical problems
I will discuss below.  I can't do this with Ivip as currently
conceived, since the mapping for each micronet is a single ETR address.

Still, I agree that anycast and disaster recovery are uses of the
network we would very much like to do in a more scalable fashion than
is currently possible.  With OITRDs / PTRs we can make the core-edge
separation scheme work for packets from all hosts - ideally with the
OITRDs and PTRs widely scattered around the Net and therefore
on-path, or close to on-path with the sending host to ETR path.

> The ETR's character is that it has only one attachment in the

I agree.  I explored anycast ETRs in my previous messages and
couldn't find a use for them which was any better than anycast hosts
with ordinary BGP.

> eliminating the need for ITRs and ETRs. 

I think this is a nifty way of describing it.

A core-edge elimination architecture load every host with many more
functions in its stack, not least crypto stuff to securely establish
other hosts' true identity (Identifier).  Also, AFAIK, no useful work
can be done (at least with HIP) before there have been several packet
exchanges to establish this identity.

What is the equivalent of a single, ad-hoc, UDP packet in HIP?
Doesn't it involve the two hosts fussing around before they can send
a traffic packet, or trust its contents?

I will write a fuller critique later, but wile I think the core-edge
elimination division of labor is conceptually elegant, I think it
places too much state, too much complexity etc. in the host.  Also,
especially for slow, expensive, radio links, the management traffic
setting up these host-to-host associations will be economically
expensive and will be slow, especially with higher packet loss rates
on the radio link.

> The anycasting decision

OK, converting this into other terms, as I think suit a core-edge
elimination scheme:

    The originating host (assume for the moment a unicast host
    = unique Identifier and unique Locator) may have selected from
    different Locators for the various remote hosts which perform
    the same function in a manner analogous to anycast: by having
    those remote hosts all having the same Identifier ...

This requires multiple physical hosts to have the same identifier.
Is this kosher in any core-edge elimination scheme to date?

    or it could have been attachments (Locators) for multiple hosts
    (each host has a unique identifier, so this is not really
    "anycast") all of which are capable of responding to the service
    request.

The second half sounds like some mid-level stack arrangement.  For
instance, the application and higher part of the stack in host A,
(assume unicast: a single host A with a single identifier A) is
communicating with what the stack and application treat as a single,
similar, (implicitly unicast) host B  . . . but which is in fact
implemented at a mid level in the stack by choosing one of multiple
hosts with unique Locators and unique Identifiers, none of which are
"B" but which somehow work together so they behave as a host with
Identifier B.

That sounds like it would require additional complexity in all hosts,
including host A which never itself takes part in a set of "~anycast"
hosts, but may sometimes need to communicate with such a set,
presumably in a way which makes them resemble a single host as far as
applications are concerned.

I am sure it could be done - but it would involve more complexity in
all hosts.

> have the shortest round trip time and the lowest probability of packet

Ahh - yes, not just speed but lower packet loss.

> I suppose that's possible though I'm not sure what the use case is.

OK - thanks for confirming this.

> faulty premise of having some kind of anycast ETRs. 

I agree they are faulty - I tried pretty hard to find a use for them
and found none.

> The only response
> I can offer is: of course anycast ETRs don't make sense. 

I agree.

> Anycast ITRs make sense.

Yes - Ivip Open ITRs in the DFZ or LISP Proxy Tunnel Routers.

> ITRs making anycast decisions while resolving the map make sense.

They might . . .

> But ETRs are supposed to be single points of attachment in the

I haven't found a use for anycast ETRs yet - and I probably won't, so
I tend to agree.  But we are designing these things and we can do
what we like with our own creations.

How would you achieve the goals agreed to above via LISP, APT or TRRP
having the ITR choose between multiple ETR addresses?

Current BGP-based anycast uses the natural behaviour of BGP routers
to cause the packet to be forwarded to the "closest" border router
which advertises the most specific matching prefix.  BGP routers do
this naturally - it is not a special function they work hard to achieve.

Let's forget goal 'd' above for now - though it will be achieved fine
without the sending host needing to do anything, just by the
"anycast" or "disaster recovery" system knowing which site the packet
was received at.

Goal 'c' spreading the load over multiple servers, can easily be done
with LISP.  This includes having the servers physically scattered at
different points in the Net.  Simply have a number of ETR addresses,
and the ITR choosing randomly from them.

Still, the ITR has to somehow figure out which of these ETRs is
working and (if this is a separate thing, which it not if the ETRs
are in the end-user networks, as LISP currently assumes) which such
ETRs can reach the destination host.

LISP has some ways of doing this, but I think they are messy and
expensive - which is why Ivip ITRs do not attempt to test
reachability to the ETR, or through the ETR to the destination network.

Part of how a LISP ITR might determine reachability might be testing
to see if the ETR address has an entry in the FIB.  It will have an
entry if the ITR's RIB thinks it has a path to the BGP router (only
one such router, since we have no anycast ETRs) which the RIB thinks
is advertising the most specific prefix matching this ETR address.
That will solve some problems, but it doesn't establish that the ETR
is reachable.

(But what of an ITR which is not actually a router?  It would send a
packet to the address in question and the packet may never get to any
border router, since the prefix may not be advertised at all in BGP.
 Then, ideally, the ITR would get an ICMP destination host/network
unreachable message.  Then it would choose another ETR instead - but
has it kept the packet?  Probably not.  How can it secure the ICMP
message to stop DoS attacks?  The traffic packet needs to carry a
unique nonce in its LISP header, so there has to be a LISP header and
a UDP header in front of that - but the ICMP spec doesn't ensure
routers will actually send back enough of the original packet to
carry this nonce . . . it only needs to send back the UDP header,
IIRC, which precedes the LISP header.)

Goal 'b' would probably be achieved by a suitable solution to the
above problem - but I am yet to see it has been robustly and
efficiently solved.

How would a LISP, APT, or TRRP ITR achieve goals 'a'?

This depends on BGP "distance".  If the ITR is a BGP router, in the
DFZ, then it will have the full DFZ routing table for its specific
point in the network, and it will have "distance" metrics for each of
its best paths.  So the ITR part of the router could interrogate the
RIB and figure out which of the various ETR addresses in the mapping
has the BGP advertised prefix which is "closer".

That is costly, but would work, for an ITR which is a full DFZ
router, as would be PTRs.

However it won't work at all for ITRs which are any of:

   Single homed BGP routers (not carrying the full DFZ table).

   Internal routers (no idea of the DFZ table).

   An ITR in a device which is not a router.

So I disagree with your proposal that it is possible to use multiple
ETR addresses in LISP, APT or TRRP to implement one of the crucial
goals which is routinely achieved, without any extra effort, in
conventional BGP-based anycast (which is admittedly unscalable).

How would I do this stuff - the equivalent of BGP-based anycast or a
similar function for the Disaster Recovery arrangement - with Ivip as
currently conceived?

Ivip can't do load balancing over multiple servers at different parts
of the Net if they are all on the same IP address.  It is necessary
to do round-robin DNS for a given FQDN, such as to cause
Correspondent Hosts (CH's as I will refer to the ordinary client
host) to choose at random one of the IP addresses and stick with it
for the session.

Those multiple IP addresses are all SPI addresses and each one is in
a separate micronet.

If the servers are in one location, the load balancing will be
between two or more ETRs in different ISPs, so the end-user network
changes the mapping of each micronet to one ETR or the other,
spreading the load accordingly.  The same idea works fine if there
are multiple servers in different physical locations.

  Round-robin SPI            Separate
  addresses, each           ETR for each
  assumed to be in          server site
  its own micronet

  3.3.3.0                   45.68.23.1
  3.3.3.1
  3.3.3.2                   32.67.21.7
  3.3.3.3
  3.3.3.4                   21.62.92.7
  3.3.3.5
  3.3.3.6                   65.98.21.4
  3.3.3.7

With 800 active CHs, on average 100 chose a particular one of the
3.3.3.x SPI addresses which are returned by DNS.

Each server site has hosts which respond to every address.

Now by sending mapping changes, the end-user network can steer the
overall burden of work in increments of ~1/8 of the total burden to
its four sites.  The most obvious way is the first two micronets are
mapped to the first ETR address, the 3rd and 4th SPI addresses to the
2nd ETR etc.

If a server site died, or became too busy, a real-time mapping change
could direct one of both of the micronets to another server site.

Assuming session-based protocols and the servers not sharing the
session state, this switch would break sessions - but with an outage
or overload, some or many or the sessions were dead anyway.

Each site could be multihomed - and so could have two ETRs.  Then it
is possible to load-balance the inbound traffic for each site too.

This looks like a good solution for goal 'c' - and with real-time
control by the network administrators and/or some automated load
balancing software it may well be more useful than the load balancing
which is possible with LISP, APT or TRRP.

Goal 'b' is achieved in the same way.  The end-user network sends (or
has a probing company send on its behalf) a mapping change if one of
the sites goes down.  The probing company would actually control the
mapping and as long as all sites were found to be reachable, it would
take instructions from the end-user network itself to achieve load
balancing.  More on this in a new section:  "The actual source of
mapping changes":  http://www.firstpr.com.au/ip/ivip/Ivip-summary.pdf

But how would Ivip achieve something like goal 'a' - having the
packets sent to the "closest" operational ETR?

Ivip can't do this at present - except by using anycast ETRs which
suck and have no scaling benefits over conventional BPG approaches.

But neither can LISP, APT or TRRP, unless perhaps the ITR is in the
DFZ - and most ITRs will internal routers.

How could a host in a core-edge elimination scheme do all this?

I figure it could achieve 'c' and 'b' OK, but it has no access to the
BGP information it needs to do anything like 'a'.

So can we solve this problem by adding to all the schemes some kind
of network service (maybe always available from some *anycast*
address) by which an ITR or a core-edge elimination scheme host could
send one or more IP addresses and get back some relative metrics
about which one was "closer"?

If we could do this, then we could do Disaster Recovery with
generally optimal path-lengths (and therefore shortest times and
lowest packet loss rates) as part of the scalable routing solution in
a *scalable* fashion: that is without pushing more prefixes into the
DFZ and in a responsive manner.

I think this is well worth considering.  It is a new idea to me, but
it could be done, I am sure.

Just have a bunch of "Distance Servers", or routers, or whatever,
scattered around the local network, such as one or a few in every ISP
network, or every end-user network, and or every small section of
some big ISP or end-user network.  Each one has its own global
unicast IP address too.

Each one also responds to some predetermined IP address in an
"anycast" fashion.  (Alternatively, we need some autoconfig
arrangement for every ITR to find it.)

The Distance Server has been configured to communicate with the
nearest DFZ router.  (Further work required if there are two DFZ
routers and the IGP steers some packets to one and others to another.)

Maybe the Distance Server simply pretends to be a BGP router and gets
a full, continually updated, copy of the DFZ router's routes,
complete with the lengths of all the routes it currently has.

The Distance Server could act in some ways like a BGP router and so
pass this on to other Distance Servers, in order not to load the DFZ
router.

Then when this Distance Server gets a query from an ITR about some
ETR address, it matches it to the most specific BGP route and returns
the "BGP distance", which is the number of ASes in that route's
announcement.  A nonce in the query is returned in the reply in order
to secure the system.  UDP queries and responses will be fine, so
multiple local Distance Servers can be anycast.

ITRs (or hosts in the case of core-edge elimination systems) would
query Distance Servers with one or more ETR addresses and so be able
to choose which ETR address was apparently "closer".

This would work fine for any system in which a single EID's mapping
included multiple ETR addresses: LISP, APT and TRRP.

But what of Ivip, where there is currently a single ETR address for
every micronet?

The most obvious approach is to extend Ivip's mapping to an arbitrary
number of ETR addresses.  That could be done.  Another approach would
be to retain a single "ETR" address, but to make a certain range of
addresses have a special meaning.  These would be outside the global
unicast address range, and so could never actually be ETR addresses.
 They would index into a separate set of mapping information and
return multiple ETR addresses.

Either way, Ivip could be modified to have multiple ETR addresses for
each micronet.

Ivip ITRs are already in communication with at least one local full
database Query Server (QSD) perhaps via one or more optional caching
query servers (QSCs), which I will ignore for now.

The QSD can incorporate the functions of the Distance Server.

So the QSD, directly or indirectly, gets DFZ route "distances" for
whichever ISP or end-user network it is located within.

As before, the ITR has a packet to send which it doesn't know the
mapping of.  It sends the destination address with a nonce to its
local QSD.  As before, if the QSD's copy of the mapping database for
this micronet contains an ordinary ETR address, this is what is sent
back to the ITR, along with the starting and ending address of the
micronet and a caching time.  (Within the caching time, the QSD will
tell the ITR if the mapping for any of this micronet changes, to a
new ETR address or if the micronet is split into multiple smaller
micronets.)

If the QSD finds an ETR address in the special range, then it looks
up some other part of its mapping database to find the one or more
real ETR addresses which correspond to this special ETR address.

Then, via looking into its Distance Server sub-function, it
determines which of these is "closest".  Then it sends that ETR
address to the ITR.

This involves no extra complexity in the ITR, but adds some to the
QSD.  This sounds like a good division of labor.  It also is in
keeping with APT's Default Mapper (APT's equivalent of the QSD) which
makes decisions for ITRs based on multiple ETR addresses, and only
sends the answer to the ITR.

This looks like a perfectly good way of enabling Ivip to achieve goal
'a' of the anycast / Disaster Recovery goals.  It involves two extra
sets of complexity and storage in the QSD, but that is fine.

APT could do the same thing - integrated "Distance Server" functions
into the Default Mapper and thereby have suitable mapping options
instructing the DM to choose the "closest" ETR.

LISP-ALT and TRRP have no local query server.  So they would need a
new network element: a Distance Server.

The "Distance Server" could be integrated into LISP-ALT's Map
Resolver function.

  - Robin

> You have two sites: primary in New York (NY), disaster recovery in
> Tokyo (T). Each site has one Internet link, one router and one
> server.
>
> Sprint provides the Internet link to NY. Cogent provides the
> Internet link to T.
>
> The NY router announces 1.2.3.0/24 via BGP at normal priority.
>
> The T router announces 1.2.3.0/24 after prepending the AS# 3 times,
> causing most of the other routers on the Internet to consider the T
> router more distant than the NY router.
>
> The two sites are normally linked together with a VPN traveling
> over the Internet using 5.6.7.8 on one side and 8.7.6.5 on the
> other, addresses provided by the respective ISPs. This functions as
> if there was a private line directly connected between the two
> routers.
>
> Ordinarily, the T router sends packets for 1.2.3.4 over the VPN to
> the NY router while the NY router sends packets for 1.2.3.4 to the
> NY server.
>
> If the VPN fails, the T router will send packets for 1.2.3.4 to the
> T server instead.
>
> If the NY server fails, the NY router will send packets for 1.2.3.4
> over the VPN to the T router and the T router will send packets for
> 1.2.3.4 to the T server.
>
> Both servers answer to 1.2.3.4. Both return identical content.

[ Sprint               1.2.3.4
[           R2------R5----------[RNY]------------(SNY)
[          /  \     |             ! 5.6.7.8
[ SH1--->R1   R4---R6             !
[          \  /     |             ! VPN  (really via R5, R6, R4, R3,
[           R3------R7            !       R9, R10)
             |                    !
             |          1.2.3.4   ! 8.7.6.5
{           R9------R10---------[RT]-------------(ST)
{          /   \   /
{ SH2----R12--R13-/
{          \  /
{ Cogent   R14

---

From: Robin Whittle <[email-masked]>
Date: Thu, 23 Apr 2009 20:13:23 +1000

Olivier Bonaventure mentioned on the LISP list that the ALTO
(Application-Layer Traffic Optimization) WG is working on something
related to the "Distance Server" idea:

  http://tools.ietf.org/wg/alto/
  http://www.ietf.org/html.charters/alto-charter.html
  http://tools.ietf.org/html/draft-ietf-alto-problem-statement-00
  http://tools.ietf.org/html/draft-ietf-alto-reqs-00

I will read up on this.

  - Robin