Subject: [alto] Pathological network maps: "empty" PIDs and "unreduced" PIDs

From: Bill Roome <[email-masked]>
Date: Wed, 07 Mar 2012 10:57:44 -0500

I've come across two types of oddities in a network map. The first is an
"empty" PID. For example, consider this map:

	PID1: 0.0.0.0/7
	PID2: 0.0.0.0/8
	PID3: 1.0.0.0/8

PID1 is legal, but it contains no endpoints. Every address in 0.0.0.0/7 is
also in 0.0.0.0/8 or 1.0.0.0/8, and because those CIDRs have longer masks,
every endpoint that might be in PID1 is really in PID2 or PID3. Hence PID1
is empty.

The second oddity deals with "unreduced" PIDs. That is, a PID whose set of
CIDRs could be simplified by combining "adjacent" CIDRs and dropping
"overlapped" CIDRs. For example, consider:

	PIDa: 0.0.0.0/8  1.0.0.0/8  2.0.0.0/8  3.0.0.0/8

Those four CIDRs are adjacent, and are equivalent to 0.0.0.0/6. So why not
combine them? Eg, reduce the CIDRs in a PID to the least number? I believe
the reduced form is unique, so each PID would have a canonical set of
CIDRs.

However, in some cases, that reduction can change the endpoint-to-pid
mapping. Consider this network:

	PIDa: 0.0.0.0/8  1.0.0.0/8  2.0.0.0/8  3.0.0.0/8
	PIDb: 0.0.0.0/7

With that definition, any endpoint that starts with 7 zeros is in PIDa.
However, if we deduce PIDa and redefine the map as:

	PIDa: 0.0.0.0/6
	PIDb: 0.0.0.0/7

Then any endpoint that starts with 7 zeros moves to PIDb.

But you'll also notice that in the first, unreduced map, 0.0.0.0/7 in PIDb
was empty. I believe that CIDR-reduction can only shift endpoints if the
map has empty CIDRs.

So that leads to two questions:

1. Should the ALTO spec forbid "empty" CIDRs in the network map?
2. Should the ALTO spec require the CIDRs in a PID to be reduced to
"lowest terms"?

If we do both, then each network map has a unique canonical representation.

	- Bill Roome

---

From: Nicholas Weaver <[email-masked]>
Date: Wed, 7 Mar 2012 08:03:52 -0800

> 2. Should the ALTO spec require the CIDRs in a PID to be reduced to

My thoughts are "No" and "No", because churn will happen.

For the first, the "empty" CIDRs can be effectively catch-all rules, which when a subrule goes in and out may change things.

Likewise, I don't see the benefit of mandatory canonicalization/reduction when there is possible churn, which will force the undoing/redoing of the canonicalization.

---

From: Richard Alimi <[email-masked]>
Date: Sun, 11 Mar 2012 00:23:37 -0800

> Likewise, I don't see the benefit of mandatory canonicalization/reduction when there is possible churn, which will force the undoing/redoing of the canonicalization.

Agreed. While it may be aesthetically pleasing (and perhaps slightly
smaller on the wire) to have a canonical representation, I'm not sure
I see a reason to force this upon servers.

Rich

>
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto