North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

2006.06.05 NANOG-NOTES interdomain routng via Wiser, Ratul Mahjan

  • From: Matthew Petach
  • Date: Tue Jun 06 05:58:10 2006
  • Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=beta;; h=received:message-id:date:from:sender:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition:x-google-sender-auth; b=RdP6qK6gM78NQXL5AMVfNjHOZswBepLGasdXmwfK0YdS/iE0swDtLjngpI2l7zHffPfIMl9oMZ4IKWqLjakrRFeKQIURUqelNIjTX7hNkspgjofZDqoyClBGW9ufcvS5m7h80ltz2omsrxgV9/BsOyBXQSbRFE1CtVRyqxPOZxg=

A simple coordination mechasims for interdomain routing
[slides are at:

Ratul Mahjan
David Wetherall
Tom Anderson
University of Washington now @ Microsoft Research

the nature of internet routing
within a contractual framework, ISPs select routes
that are best for themselves.
Potential downsides
higher BW provisioning
requires manual tweaking to fix egregious problems
inefficient end-to-end paths

An alternative approach: coordinated routing
ISPs have joint control
path selection is based on the preferences of both ISPs
Potential benefits
lower BW provisioning
no egregious cases that need manual tweaking
efficient end-to-end paths
 basis for interdomain QoS

Existing mechanisms cannot implement coordinated routing
route optimization boxes help (stub) ISPs pick better
routs from those available
MEDS implement receiver's preferences.
Cannot create better paths that don't already show up
in the routing table.

What makes for a good coordination mechanism?
MEDS have some nice properties
ISPs can express their own metrics
ISPs are not required to disclose sensitive info
requires only pairwise contracts
Provides joint control and benefits all ISPs.

Our solution: Wiser
operates in a lowest-cost routing framework
downstream ISPs advertise their cost
upstream ISPs select paths based on both their
 own and received costs.

Problems with vanilla lowest-cost routing
ISP costs are incomparable
Can be easily gamed

When you bring incomparable costs together, the ISPs
that use higher costs win out.

Cost normalization
Normalize costs such that both ISPs have "equal say"
Normalize such that sum of costs is the same.
Makes the system harder to game.

Bounds on cost usage
Downstreams log cost usage of the upstream ISPs
Compute the ratio of avg. cost of paths used and
Contractually stipulate a bound on the ratio.
Similar to existing ratio requirements.

Wiser in action
Announce costs in routing messages.
normalization occurs between ISP pairs.

Example results
using major ISP topologies for experiments
Wiser provides better control under link failure.
Wiser produces shorter path lengths

XORP prototype
Simple, backward-compatible extensions to BGP
embed costs in non-transitive BGP communities
border routers jointly compute normalization
factors and log cost usage
a slightly modified BGP decision process
Benefits even the first two ISPs that deploy it.

Wiser is a simple mechanism to coordinate
interdomain routing
may lower provisioning, reduce manual tweaking,
produce more efficient paths and help with interdomain
Feedback: [email protected]

Danny McPhereson:
Q: how do you normalize across multiple ISPs?
A: routing advertisements happen on the sum of the
costs announced from me to you, and from you to
me.  He derived it from different values in
his experimentation; utilization and latency
in general.

Q: Randy Bush: Whatever metrics are, you just normalize
by summing them up.  But Danny notes if you have
multiple ISPs, how do you normalize them together?

Q: Danny: where was the 20ms of control plane savings
seen that he claimed in slide 11?
A: That was based on default ISP policy, prefer customers
over peers, etc.
So the delay was control plane plus data plane; it
wasn't control plane alone.
He based it on the old rockefuel equation.

Randy Bush: vendors--this is cool stuff, open your

Break time now.