2006.06.05 NANOG-NOTES AS-PATH prepending measurements

2006.06.05 Active measurement of the AS path
prepending method.
[ slides are at

This is the research forum part of the meeting,
people doing real research on real networks.
Samantha Lo and Rocky KC Chang
department of computing
Kowloon, Hong Kong

Dr. Rocky Chang is her supervisor.

Apply AS-path prepending on a trial-and-error
basis to control the inbound traffic.
How effective can the AS-path prepending method be?
what would happen to the routes after prepending on
a link?

The measurement setup; dual-homed stub AS.
connected to 9304 and 4528
Two upstream links, L1 and L2.
Announce a beacon prefix to both links with
prepending on L1.

graph of prepending length on the X axis.
from 0 to 5, then back down. Wait 6 hours
between each change to stabilize.
goes from 102:29 at 0 on L1, to 14:91 at 5
on L1.
Greatest change is between prepending length
of 2 and 3.
When decreasing, see an unbalanced phenomenon.

Who was responsive to prepending?
Incoming link to beacon prefix changes,
next-hop of routes also changes in remote AS

Passive-responsive are those where the next-hop
for the route didn't change, but the subsequent
path is different.

Active-responsive, next-hop actually changes.

Non-responsive ASes, see no change.
43 ASes
no change in either incoming link or next-hop
On L1: 14 ASes
use one next-hop only

Passive-responsive ASes
26 ASes
incoming link change
no change in next-hop

Active responsive ASes
47 ASes:
both incoming link and next-hop changes
possible reasons:
apply shortest-path policy
no localpref override.

Active responsive ASes:
bunch of others, slide went pretty quickly

Most of them are located 4 AS-hops away from L1;
after prepending, they are 5 AS-hops away from L2.

Routes to L1 at 4, via L2 at 6 when starting.

What if both ASpaths via L1 and L2 have the
same length?
equal to or greater policy:
located 4 AS hops via L1, and 5 AS hops via L2.
AS3662 has prepended once.
So prepending once on L1, 5 < 6, no change.
prepending twice on L1, 6 = 6, route changes to L2
even though they're equal.

AS3257, located same as 1239
when increasing prepending to 2,
L1 is 6 (4+2), L2 is (5+1), but still uses L1.
When increased to 3, 7>6, it finally changes to L2.
When decreasing to 2 again, it's equal again, but
it doesn't flip back to L1 until the prepending is
down to 1, at which point 5 < 6, then it finally
shifts to L1.
This is the "greater than" policy. Same prepending
length, uses different routes. 'sticks' to previously
used path.

BGP update graph.
After prepending, update messages continue for several

Conclusions and future work
Route changes are introduced by active-responsive
shortest path policies
topology -> when they will change
possible applications
predict amount of traffic shifts
discover the upstream ASes policies

Thankss to Michael Lo and Lorenzo Collitti

Q: Randy Bush, IIJ, notes that from her slides,
Tim Griffen describes her "delayed reaction"
as 'BGP wedgies'. It comes from the BGP tie
breakers, it's not something you'll be able
to predict.
Q: Randy insists it's not a matter of policy
choice; it's built into BGP, and not something
they have control over.

Moving on to next speaker