Subject: [rrg] procedural aggregation

From: William Herrin <[email-masked]>
Date: Tue, 4 Mar 2014 19:11:39 -0500

Hi Folks,

Given recent comments, I thought it'd be an opportune time to introduce a
concept I've been fiddling with for a couple years which I tentatively call
"procedural aggregation."

I have discovered no new math which would overcome the technical challenges
to aggregation identified here in the past. I come at the problem from a
different angle instead.

My basic premise is that with current techniques (not necessarily the exact
protocols) there is no practical upper limit to the number of routes which
can be introduced to the Internet provided that each recipient of a route
advertisement is sufficiently financially compensated. He must be paid
enough for carrying each route to allow him to purchase and operate
hardware that carries all of the routes for which he's being paid. With
that in place, total routes will self-limit based on what technology is
capable of at each price point.

>From there I develop administrative procedures for determining who
announces what aggregates and how to pay who for carriage of the
more-specifics in order to yield a technically useful network configuration.

I'll post a couple examples in the next few days. Before that, I want to
take the remainder of this message to review how the Internet currently
routes packets. I'll largely skip the technical part. You're all experts or
you wouldn't be here. Instead I will clarify the financial process.
Somebody pays each and every organization on the Internet to accept your
packets and forward them to the next hop. Every single Autonomous System.
Every single packet. I'll explain who and I'll explain how that money flows
with the technical parts of packet routing.

Understanding the money flow will be important when I ask you to consider
procedural aggregation. Exterior gateway protocols need not produce *all*
technically possible networks. They need only (must only) produce those for
which the participants are properly compensated.

__ Transit and Peering __

>From a financial point of view there are two types of Internet connections
between two organizations: transit and peering.

transit - Internet provider A provides access to "the entire Internet" to
organization B. B may be an end user or another service provider.

hosting - Internet provider A connects servers under the control of
organization B to "the entire Internet." Hosting is transit plus floorspace.

peering - Internet provider A provides Internet provider Z with access to
only its downstream transit customers and vice versa, not to the entire
Internet.

settlement free peering - peering for which no no money changes hands.

For the purposes of this discussion:

Transit and hosting are the same thing. In each case, someone pays someone
else to connect them to "the Internet." I will only use the term transit.

Usually B pays A for Internet access. Sometimes it's indirect: buy coffee
get "free" Internet. Sometimes A's compensation is non-monetary, e.g. good
will from a charitable donation. Other times A is paid by a third party to
service B. For the purposes of the discussion, transit service is always
paid for: B always pays A for access to the Internet.

For simplicity's sake I will treat all peering as settlement free peering,
even though many service providers opt to behave as robber barons.

__ Routes flow with the money __

We have two types of connections between Autonomous Systems: transit and
peering.

Let's say Endpoint 1 (E1) and endpoint 2 (E2) are both connected to the
Internet. They pay their ISPs who pay ISPs who peer with each other. What
do those connections look like? Typically:

E1 -> B -> A - Z <- X <- E2

* E1 is a transit customer of ISP B. He pays ISP B to connect him to the
entire Internet. So, B is paid to send packets from and receive packets for
E1.

* B is a small ISP. He collects the payments from all of his customers like
E1, keeps some of it and spends some of it on transit service from a larger
ISP A to connect all of his customers to the Internet. A is expected to
send packets from and receive packets for all of B's customers, including
E1.

* E2's relationship with X is the same as E1's relationship with B. X's
relationship with Z is the same as B's relationship with A. The former buys
transit service from the latter.

* A buys transit service from several other large ISPs (not shown) but he
also has a peering relationship with Z. E2 has paid Z (indirectly via X) to
connect him to the Internet, so Z advertises to A that he's willing to
accept packets addressed to E2. That's what X is paying Z for.

So, a packet travels from endpoint 1 (E1) to endpoint 2 (E2):

E1 -> B -> A -> Z -> X -> E2

Follow the money:

* E1 sends a packet destined for E2 over to B because it's E1's packet and
he wants it sent. B accepts it because E1 paid B to accept it.

* B sends it to A because E1 paid B to send that packet. A accepts it from
B because B paid A to accept it.

* A sends it to Z because B paid A to send that packet. Z accepts it from A
because X paid Z to _receive_ packets for E2.

See the change there at the peering link? Now the money is flowing from the
other endpoint.

* Z sends the packet to X because X paid Z to receive packets for E2. X
accepts it because E2 paid X to accept it.

*  X sends the packet to E2 because E2 paid X to receive packets for E2. E2
accepts the packet because he wants to receive packets addressed to him.

And that's how everybody gets paid for E1 to send packets to E2. Comparable
payment relationships exist for every combination of two endpoints which
attempt to communicate with each other on the Internet.

__ Key Takeaways __

Sometimes E2 is a transit customer of A or of B instead of being on the
other side of a peering session. In that case A or B got paid twice and
banked a little extra money.
As often as not there's a peering session somewhere in the path. Either
way, some key takeaways are:

1. Everybody involved was directly or indirectly paid by E1, E2 or both to
forward that packet to the next hop.

2. Some or all of them were paid by only E1 or E2 but not both.

3. A packet may cross many paid transit links but no packet will cross two
free peering links.

Now you know who pays for the Internet. And how.

Finally, I offer you this estimate of the worldwide systemic cost of
carrying a BGP route. The estimate is out of date but the methodology is
sound enough to use for discussion purposes:
http://bill.herrin.us/network/bgpcost.html

Before I dive in to how this structure might be beneficially changed with
procedural aggregation, are there any questions about any of this? Anything
I can clarify about how the money moves?

Regards,
Bill Herrin

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

---

From: [email-masked]
Date: Wed, 5 Mar 2014 04:04:58 -0500 (EST)

Interesting.
But, let me quote you wrt to a much more important issue.
You once wrote: 
Problem Statement:
IPv6 comes with too much baggage. All we really needed was IPv4 with a larger address space.

IMHO: IPv6 won't get any boost by the IPv4 address expiration.
But shouldn't that be the most urgent RRG problem ?

Heiner

-----Ursprüngliche Mitteilung----- 
Von: William Herrin <[email-masked]>
An: RRG <[email-masked]>
Verschickt: Mi, 5 Mrz 2014 1:12 am
Betreff: [rrg] procedural aggregation

Hi Folks,

Given recent comments, I thought it'd be an opportune time to introduce a concept I've been fiddling with for a couple years which I tentatively call "procedural aggregation."

I have discovered no new math which would overcome the technical challenges to aggregation identified here in the past. I come at the problem from a different angle instead.

My basic premise is that with current techniques (not necessarily the exact protocols) there is no practical upper limit to the number of routes which can be introduced to the Internet provided that each recipient of a route advertisement is sufficiently financially compensated. He must be paid enough for carrying each route to allow him to purchase and operate hardware that carries all of the routes for which he's being paid. With that in place, total routes will self-limit based on what technology is capable of at each price point.

>From there I develop administrative procedures for determining who announces what aggregates and how to pay who for carriage of the more-specifics in order to yield a technically useful network configuration.

I'll post a couple examples in the next few days. Before that, I want to take the remainder of this message to review how the Internet currently routes packets. I'll largely skip the technical part. You're all experts or you wouldn't be here. Instead I will clarify the financial process. Somebody pays each and every organization on the Internet to accept your packets and forward them to the next hop. Every single Autonomous System. Every single packet. I'll explain who and I'll explain how that money flows with the technical parts of packet routing.

Understanding the money flow will be important when I ask you to consider procedural aggregation. Exterior gateway protocols need not produce *all* technically possible networks. They need only (must only) produce those for which the participants are properly compensated.

>From a financial point of view there are two types of Internet connections between two organizations: transit and peering. 

transit - Internet provider A provides access to "the entire Internet" to organization B. B may be an end user or another service provider.

hosting - Internet provider A connects servers under the control of organization B to "the entire Internet." Hosting is transit plus floorspace.

peering - Internet provider A provides Internet provider Z with access to only its downstream transit customers and vice versa, not to the entire Internet. 

Transit and hosting are the same thing. In each case, someone pays someone else to connect them to "the Internet." I will only use the term transit. 

Usually B pays A for Internet access. Sometimes it's indirect: buy coffee get "free" Internet. Sometimes A's compensation is non-monetary, e.g. good will from a charitable donation. Other times A is paid by a third party to service B. For the purposes of the discussion, transit service is always paid for: B always pays A for access to the Internet. 

For simplicity's sake I will treat all peering as settlement free peering, even though many service providers opt to behave as robber barons. 

We have two types of connections between Autonomous Systems: transit and peering.

Let's say Endpoint 1 (E1) and endpoint 2 (E2) are both connected to the Internet. They pay their ISPs who pay ISPs who peer with each other. What do those connections look like? Typically:

* E1 is a transit customer of ISP B. He pays ISP B to connect him to the entire Internet. So, B is paid to send packets from and receive packets for E1.

* B is a small ISP. He collects the payments from all of his customers like E1, keeps some of it and spends some of it on transit service from a larger ISP A to connect all of his customers to the Internet. A is expected to send packets from and receive packets for all of B's customers, including E1.

* E2's relationship with X is the same as E1's relationship with B. X's relationship with Z is the same as B's relationship with A. The former buys transit service from the latter.

* A buys transit service from several other large ISPs (not shown) but he also has a peering relationship with Z. E2 has paid Z (indirectly via X) to connect him to the Internet, so Z advertises to A that he's willing to accept packets addressed to E2. That's what X is paying Z for.

Follow the money:

* E1 sends a packet destined for E2 over to B because it's E1's packet and he wants it sent. B accepts it because E1 paid B to accept it.

* B sends it to A because E1 paid B to send that packet. A accepts it from B because B paid A to accept it.

* A sends it to Z because B paid A to send that packet. Z accepts it from A because X paid Z to _receive_ packets for E2.

See the change there at the peering link? Now the money is flowing from the other endpoint.

* Z sends the packet to X because X paid Z to receive packets for E2. X accepts it because E2 paid X to accept it.

*  X sends the packet to E2 because E2 paid X to receive packets for E2. E2 accepts the packet because he wants to receive packets addressed to him.

And that's how everybody gets paid for E1 to send packets to E2. Comparable payment relationships exist for every combination of two endpoints which attempt to communicate with each other on the Internet.

__ Key Takeaways __

Sometimes E2 is a transit customer of A or of B instead of being on the other side of a peering session. In that case A or B got paid twice and banked a little extra money. 
As often as not there's a peering session somewhere in the path. Either way, some key takeaways are: 

1. Everybody involved was directly or indirectly paid by E1, E2 or both to forward that packet to the next hop. 

3. A packet may cross many paid transit links but no packet will cross two free peering links. 

Finally, I offer you this estimate of the worldwide systemic cost of carrying a BGP route. The estimate is out of date but the methodology is sound enough to use for discussion purposes: http://bill.herrin.us/network/bgpcost.html

Before I dive in to how this structure might be beneficially changed with procedural aggregation, are there any questions about any of this? Anything I can clarify about how the money moves?

Regards,
Bill Herrin

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

---

From: William Herrin <[email-masked]>
Date: Wed, 5 Mar 2014 11:09:40 -0500

> But shouldn't that be the most urgent RRG problem ?

Hi Heiner,

The "procedural aggregation" approaches I'll discuss are agnostic
about the IP version number. They work as well (and as poorly) for
both IPv4 and IPv6.

Before I dive in to that, does everybody follow the economics of
Internet routing as presented in my prior message? Can I answer any
questions about how it works?

Regards,
Bill Herrin

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 05 Mar 2014 11:30:21 -0500

My understanding is that the packet forwarding paths, and the money 
exchanges, are more complex than the picture you painted.  Your picture 
matches the general theory.  However, I have repeatedly been told that 
the reality does not match that theory.

Yours,
Joel

---

From: William Herrin <[email-masked]>
Date: Wed, 5 Mar 2014 12:05:27 -0500

On Wed, Mar 5, 2014 at 11:30 AM, Joel M. Halpern <[email-masked]> wrote:
> matches the general theory.  However, I have repeatedly been told that the
> reality does not match that theory.

Hi Joel,

What differences do you believe exist based on your understanding?
Would you mind elaborating?

Regards,
Bill Herrin

---

From: William Herrin <[email-masked]>
Date: Wed, 5 Mar 2014 12:55:22 -0500

Hi Joel,

I'll state that the settlement fees involved in common peering
arrangements (peering as defined in my post) are irrational, couched
in the language of fairness but based entirely on what the
participants believe they can get away with. I have taken that into
consideration with the structures I'll propose for procedural
aggregation.

Are you aware of any other specific divergence between the financial
structure I described and the reality on the ground? What is it?

Regards,
Bill Herrin

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 05 Mar 2014 13:20:38 -0500

I am told that
1) The set of traffic allowed is more nuanced and varied than just the 
two categories of transit and peer.
2) If I have understand your description properly, it looks similar to 
the frequent "valley free" assumption.  And there are multiple papers 
that make it clear that the actual paths are not "valley free".  (Sorry, 
I do not have pointers to the papers.  I am not actually a researcher.)

Yours,
Joel

---

From: William Herrin <[email-masked]>
Date: Wed, 5 Mar 2014 13:52:54 -0500

On Wed, Mar 5, 2014 at 1:20 PM, Joel M. Halpern <[email-masked]> wrote:
> 1) The set of traffic allowed is more nuanced and varied than just the two
> categories of transit and peer.

Hi Joel,

Barring a specific example, I respectfully disagree. Service providers
often use BGP communities to give transit customers nuanced control
over their routing, however those are still simple transit business
relationships. If you pay someone for access to networks who aren't
paying him, it's a transit link, however nuanced your actual use may
be.

Likewise, peering can be partial (typically regional) or full but
either way it functions as a peering relationship, nothing else.

> 2) If I have understand your description properly, it looks similar to the
> frequent "valley free" assumption.  And there are multiple papers that make
> it clear that the actual paths are not "valley free".  (Sorry, I do not have
> pointers to the papers.  I am not actually a researcher.)

No problem, Google is an old friend. My understanding is that such
valleys are a result of misconfiguration, not an intentional part of
the system. Nor does the desired function of the system depend on
their presence. Do you disagree?

Regards,
Bill Herrin

---

From: William Herrin <[email-masked]>
Date: Sat, 8 Mar 2014 21:56:23 -0500

> categories of transit and peer.

Howdy,

Following up on a private suggestion from Joel, I polled network
operators and identified either a modification to the definition of
transit or a third kind of interaction between ASes depending on how
you want to look at it. For now I'll treat it as a third kind call
these REN links after the Research and Education Networks where they
most commonly appear.

REN links happen when several networks share a tightly bound market
niche, such as schools in a particular region. Networks serving this
niche agree to peer to take data off of their paid transit
connections. Then they take the extra and mutual step of permitting
each neighbor who serves the niche to transit their internal backbones
to each other neighbor serving the same niche. This creates a sort of
shadow network improving the customers' access to each other.

This seems to serve as an entry fee to gain access to the market niche
-- customers are disinclined to choose a service provider who does not
participate. It may also be a mechanism for protecting these typically
smaller service providers from competition by large multinational
networks who would find it challenging to participate due to the size
and complexity of their networks.

A number of other examples were put forward but in my opinion they
were straightforward variants of the transit service I've already
defined. For example, one individual claimed HE's IPv6 tunnels were a
valley because they're free and not limited to peering. However, HE's
tunnel service is clearly simple transit under the definition in my
earlier post.

With that, can anyone offer an additional concrete example of a
relationship between two neighboring ASes besides transit, peering and
REN links? Or have we pretty much captured it?

Regards,
Bill Herrin

---

From: William Herrin <[email-masked]>
Date: Tue, 11 Mar 2014 22:59:24 -0400

Hi Folks,

Here's another circumstance worth mentioning. This particular one is
an undesirable case that exists in BGP today. It would be better if it
didn't work. When I get to procedural aggregation, it'll be important
to consider whether my notions make this scenario worse.

You have three networks: A, B and C. A peers with B, B peers with C.

A-B-C

You have a customer, W. W buys transit service from A (gige) and B (T1).

A-B-C
| /
W

W announces 10.1.2.0/23 to B and announces 10.1.2.0/24 plus 10.1.3.0/24 to A.

Because W is a customer, B announces 10.1.2.0/23 to C but as soon as
the packet arrives at B from C, B sends it to A because of the more
specific route it heard from A.

This allows W to draw a gige of traffic through B even though he's
only paying for a T1.

Regards,
Bill Herrin

---

From: Jakob Heitz <[email-masked]>
Date: Wed, 12 Mar 2014 03:35:36 +0000

No, he doesn't.
W draws a gige from A
How A connects to C is none of W's business.
If it's through B, then it is for A and B to negotiate a suitable peering agreement.
W is using B as backup and wants no traffic from it unless A goes down.
How do you think the traffic should flow in this case?

Cheers,
Jakob.

-----Original Message-----
From: rrg [mailto:[email-masked]] On Behalf Of William Herrin
Sent: Tuesday, March 11, 2014 7:59 PM
To: RRG
Subject: Re: [rrg] procedural aggregation

Hi Folks,

Here's another circumstance worth mentioning. This particular one is an undesirable case that exists in BGP today. It would be better if it didn't work. When I get to procedural aggregation, it'll be important to consider whether my notions make this scenario worse.

A-B-C

A-B-C
| /
W

Because W is a customer, B announces 10.1.2.0/23 to C but as soon as the packet arrives at B from C, B sends it to A because of the more specific route it heard from A.

This allows W to draw a gige of traffic through B even though he's only paying for a T1.

Regards,
Bill Herrin

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

---

From: William Herrin <[email-masked]>
Date: Wed, 12 Mar 2014 00:30:11 -0400

> How do you think the traffic should flow in this case?

Hi Jacob,

A does not connect to C. In the given example, the desired result is
that traffic does not flow from C to A *at all*. The permissible
traffic flows are:

WA
WB
WBC
AB
CB

These traffic flows do not occur:

ABC (A lacks a route for C)
W->A->B->C (A lacks a route for C)

This traffic flow is intended to fail but doesn't because of W's more-specifics:

C->B->A->W

Regards,
Bill Herrin

---

From: "Dale W. Carder" <[email-masked]>
Date: Wed, 12 Mar 2014 22:04:06 -0500

> REN links? Or have we pretty much captured it?

Where do you feel CDN's fit in?   They sometimes are on the CDN owner's
network, sometimes they are also on ISP A's network.  The CDN in A can 
be fed settlement-free into A.  ISP B and C can be settlement-free to A
for CDN traffic.  I have seen this where A wasn't big enough to justify
having the CDN on their own without B and C's eyeballs.  Yet, A doesn't
sell transit to B or C.

Or, how about inter-domain multicast?  Maybe that is out of scope, but
these routing slots are even more scarcely available and it can break a
financial model, just like the "packet replication" from the CDN.

Dale