Transcript Presentation - Suraj @ LUMS

Sufficient Conditions to Guarantee Path
Visibility
Akeel ur Rehman Faridee
2005-03-0021
The Internet
End-hosts
Routers
(General Picture)
The Internet
(Original Picture)
Internet is actually divided into different Autonomous Systems
(AS’s), governed by different organization entities.
Endhosts
AS 2
AS 5
AS 1
AS 6
AS 3
AS 4
AS 7
Autonomous Systems (ASes)
An autonomous system is a region of the Internet that is administered
by a single entity and that has a unified routing policy
Economically independent
All must cooperate to ensure reachability
Each AS is assigned an autonomous number (ASN)
Interdomain routing is concerned with determining paths b/w AS’s
RFC 1930: Guidelines for creation, selection,
and registration of an Autonomous System
Interdomain vs Intradomain
AS 2
AS 2
EGP (e.g., BGP)
IGP (e.g., OSPF)
IGP (e.g., RIP)
Intradomain routing
Routing is done based on metrics
Routing domain is one autonomous system
Interdomain routing
Routing is done based on policies
Routing domain is the entire Internet
5
What Problem is BGP Solving?
Underlying problem
Distributed means of
computing a solution.
Shortest Paths
RIP, OSPF, IS-IS
X?
BGP
Reachability Information
BGP
AS 1
Prefixes reachable from AS 1
AS 2
Prefixes reachable
from AS 3
7
AS 3
Two Flavors of BGP
iBGP
eBGP
• External BGP (eBGP): exchanging
routes between ASes
• Internal BGP (iBGP): disseminating
routes to external destinations
among the routers within an AS
Two flavors?
• Most ASes have more than one
“border” router that talks to other
peers
• Must disseminate information inside
the AS and through the AS.
– Must have complete visibility.
COMPLETE VISIBILITY:
For every external destination, each router picks the
same route that it would have picked had it seen the
best routes from each eBGP router in the AS.
iBGP
iBGP sessions run on TCP.
Overlay over intra-domain routing protocol.
Routing messages and data packets forwarded via IGP within AS.
Routes from iBGP session not propagated to another iBGP session.
Originally FULL MESH – All routers see all routes
– causing scaling problems
Route Reflectors and Confederations are the solution.
iBGP Mesh Does Not Scale
eBGP update
•
N border routers means N(N-1)/2
peering sessions
iBGP updates
•
Each router must have N-1 iBGP
sessions configured
•
Size of iBGP routing table can be
order N larger than number of best
routes (remember alternate routes!)
•
Each router has to listen to update
noise from each neighbor
11
Problems with Route Reflectors
Lack of complete visibility: every router is not guaranteed to
see its best available route.
Single point of failure – can be fixed easily
All clients take same path – compromises complete visibility
Some configurations may provide complete visibility BUT not all !
Route Reflectors
RR
RR
RR
• Route reflectors can pass on
iBGP updates to clients
•
•
Each RR passes along ONLY
best routes
ORIGINATOR_ID and
CLUSTER_LIST attributes are
needed to avoid loops
13
BGP Blackhole
A missing iBGP session can create network partition even the
underlying IP topology is connected.
A missing iBGP session might keep one router from receiving route
information for some prefixes, making it a blackhole for that
prefix.
Knowing the sufficient conditions to gaurantee the VISIBILITY of all
available path to prevent the blackhole, both in case of partitions
and common case, is of greater interset.
Blackhole: A router that drops all the packets
of a particular prefix (because it doesn’t have
the reachability information for this prefix) is
called the black hole for this prefix.
Selected BGP RFCs
Internet Engineering Task Force (IETF)
http://www.ietf.org
•
IDR : http://www.ietf.org/html.charters/idr-charter.html
•
RFC 1771 A Border Gateway Protocol 4 (BGP-4)
•
RFC 1772 Application of the Border Gateway Protocol in the
Internet
•
RFC 1773 Experience with the BGP-4 protocol
•
RFC 1774 BGP-4 Protocol Analysis
•
RFC 2796 BGP Route Reflection An alternative to full mesh IBGP
•
RFC 3065 Autonomous System Confederations for BGP
Acknowledgements
Some of the slides/figures are taken from Hari
Balakrishnan and Nick Feamster website.
References
[1] Hari Balakrishnan, 2001-2005, and Nick Feamster, Chapter 4: Interdomain Internet
Routing, 2005, http://nms.csail.mit.edu/6.829-f05/lectures/L4-routing.pdf
[2] M Vutukuru, P Valiant, S Kopparty, Hari Balakrishnan How to Construct a correct
and Scalable iBGP Confuguration, Proceedings of IEEE INFOCOM, 2006
[3] T. Bates, R. Chandra, and E. H. Chen. BGP Route Reflection – An Alternative to
Full Mesh iBGP, April 2000
[4] Timothy Griffin and Gordon T. Wilfong. On the Correctness of iBGP
Configuration. In Proc. ACM SIGCOM, pages 17-29, Pittsburgh, PA, August 2002
[5] FEAMSTER, N., AND BALAKRISHNAN, H. Verifying the correctness of widearea Internet routing. Tech. Rep. MIT-LCS-TR-948, Massachusetts Inst. of Tech.,
May 2004
[6] Nick Feamster, Jared Winick, and Jennifer Rexford. A Model of BGP Routing for
Network Engineering. In ACM Sigmetrics - Performance 2004, New York, NY,
June 2004.