Subject: [RAM] Terminology: Routing Entropy

From: RJ Atkinson <[email-masked]>
Date: Fri, 29 Dec 2006 09:36:19 -0500

While I think the absolute size of the RIB/FIB is a
practical issue, separately there is a broader architectural issue
about the entropy in the routing table.

	If I might, let me try to define a term in the interest
of clarity and a more focused discussion...

"Routing Entropy" is the measure of how much additional detail,
beyond the bare minimum needed to reach all advertised destinations,
exists in the Routing table in (the, any) Default-Free Zone.

For example, if one advertised 3.0/8 then it is not strictly
required for *reachability* (ignoring other aspects like
multi-homing) to advertise 3.1.0/24.

More Examples:
A routing table with minimum entropy has zero more-specific prefixes.
A routing table with high entropy has many more-specific prefixes.

Ran

_______________________________________________
RAM mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ram

---

From: David Meyer <[email-masked]>
Date: Fri, 29 Dec 2006 08:24:15 -0800

Hey Ran,

> A routing table with high entropy has many more-specific prefixes.

	Interesting you should mention this. I'm in the process
	of embarking on some work to see if we can measure the
	Hurst parameter for UPDATEs; the idea is basically
	to look for any LRD (Long Range Dependence) in that
	signal. Currently its just a pilot study; I'm not sure if
	the "passive instrument" we're using (www.routevivews.org
	or the like) produces the kind of data we need to detect
	a signal that lives in low-frequency events, but in any
	event, that result would be nice to have. 

	Now, at the very least, such a result would be useful in
	thinking about the burstiness of the Internet's UPDATE
	stream, and corresponding architecture/protocol
	mechanisms that might be used to control that burstiness
	(if indeed that is an issue; intuitively the burstiness
	of the UPDATE stream "seems" problematic, but I think
	we'd all like to have a better, more quantative
	understanding of what's really going on). 

	Back to the routing entropy issue: The nature of the
	dynamics of the UPDATE stream is directly related to the
	amount (and the granularity of) the information that is
	carried in the DFZ. All of this will effect not only the
	cost of providing Internet service, as well as its
	quality.

	--dmm

---

From: [email-masked]
Date: Fri, 29 Dec 2006 11:44:18 -0500

> 	cost of providing Internet service, as well as its

Is it actually, today? I thought GIH's work last year showed that  
recent/current update dynamics were substantially driven by a  
relatively small number of operators with questionable configs/ 
competence?

http://202.12.29.20/meetings/21/docs/sigs/routing/routing-pres-huston- 
routing-update.pdf
http://streaming.apnic.net/meetings/21/video/routing/huston.mov

Tom

---

From: David Meyer <[email-masked]>
Date: Fri, 29 Dec 2006 09:24:40 -0800

Hey Tom,

> http://streaming.apnic.net/meetings/21/video/routing/huston.mov

	A couple of points: 

	(i).	It defintely appears that the distribution is
		heavy-tailed (which, BTW is a characteristic of
		the autocovariance function of long-memory
		processes). However, these studies didn't focus
		on the burstiness or memory ("lag") of the UPDATE
		stream time series (process), which is what I'm
		after here.

	(ii).	These studies were not, to the best of my
		knowledge, looking for LRD. And as I mentioned,
		there is all kinds of noise in the signal, such
		as the (inherent) smoothing properties of the
		MRAI timer, various effects in the incoming
		messasge queue, to name a few. Further, LRD,
		while mathematically well definted, is a
		particularly difficult property to work with,
		precisely because such a signal "hides" in
		low-frequency events.  
		
	In any event, to the best of my knowledge, no one has
	looked at the UPDATE signal stream from this (LRD)
	perspective (and BTW, someone please correct me if I'm
	wrong).   

	--dmm

---

From: "Chris L. Morrow" <[email-masked]>
Date: Sat, 30 Dec 2006 03:16:49 +0000 (GMT)

> 	understanding of what's really going on).

I'd like to see if there is a dampening effect in the burstiness as well,
is viewing the overall change rate/state from route-views better or worse
than a single edge device with a misbehaving customer set? How much
information is damped out before it exists that ASN? (some of this is
surely dependent upon the specific configurations, but this gets back to
'the DFZ' is not the most hurtful number, the core/internal routetable(s)
are hurting providers even more than the public view of things).

I look forward to the study though :)

---

From: Jari Arkko <[email-masked]>
Date: Sat, 30 Dec 2006 10:13:34 +0200

Tom,
> relatively small number of operators with questionable configs/competence?
I have also understood that its a big component of
what we're seeing today. But at the same time Dave
is right -- the more details we pour into the table
about the edge of the network, the more likely it
is that we will encounter bad setups and bad links.

And I don't think the entire update load can be
classified under questionable practices.

(An interesting question is what we can
do about the part that can be classified as such.
Its very hard for, say, an ISP to push back on
a questionable practice of its peer because
there are economic incentives to stay
connected, and because the price to
this one ISP is small, even if the price
to the entire world is great. Tragedy of
the commons. Are the best practices
documents that the operator community
could write? Has the IETF done enough
to provide guidance on how to use its
tools to do routing and TE?)

--Jari

---

From: [email-masked]
Date: Sun, 31 Dec 2006 10:02:32 -0500

> do about the part that can be classified as such.

Hi Jari,

I think that Geoff's presentations on the subject were/are intended  
to be part of that response.
Since "peer pressure" quite literally fails to be sufficient to  
moderate such behavior, identifying problem operators in public fora  
might expose them to other motivators (e.g., shame) to do better.  
Informed self-interest, informed group interest (peer pressure),  
informed public interest (shame) -- short of changing technology to  
make such problems physically impossible, all we can do is tweak the  
"information" and/or "interest" parameters to encourage community  
members to do better. So, to that end, here again are the networks  
that Geoff identified last year:

AS9121 	TR		TTnet (Turk Telekom)

AS702	US		MCI EMEA (Verizon Business)
AS721	US		DNIC

AS17557	PK		PKTekecom

AS7563	KR		KII-AS Korea Internet Infrastructure
AS9950	KR		Dacom
AS17832	KR		SIXNGIX

AS17974	IN		PT Telekom Indonesia
AS7545	AU		Total Peripheral Group
AS2706	HK		Pacific Internet

Depending on your ontology, 3-4 PSTNs, 2-3 government networks, 3-5  
commercial ISPs. All in all, probably not an easy group to move  
through non-coercive means...

> tools to do routing and TE?)

I'm not really in the right demographic to gives good/representative  
answers to these questions, but I reckon the implicit answers are  
(maybe so, apparently not)....

HNY all,

Tom