Transcript Slides

Lecture 4: BGP
• Presentations
• Lab information
• H/W update
Inter-Domain routing
– At the beginning: the Internet was a single
network
• Funded by the US Government, ARPAnet
• Started in 1969 and lasted until 1985
– As its size grew things became unworkable (see
RFC-827)
– Time to introduce hierarchy:
• All the routers of the same organization belong to
the same Administrative System (AS)
• Routing is between ASes now
Administrative Systems (AS)
• Single organization
– Same routing policy
• Has a unique id – AS Number (ASN)
–
–
–
–
16 bits right now
Valid ids between 1-64511
64 bits are coming
Right now 22,500 are visible in the Internet
Exterior Routing or Inter-domain
routing
• Certain routers in an AS talk to routers in
other ASes and exchange routing
information
• Then they introduce this information inside
their AS
• EXAMPLE
So every Inter-domain protocol
has to do the following
•
•
•
•
Establish the adjacency with the neighbor
Monitor the status of this connection
Exchange routing information
Some similarities with intra-domain routing
protocols but:
– Can not do flooding now, network is too big
– Routing information is different now
• Reachability information
– I can reach network a.b/16 through next-hop nh
• EXAMPLE
What is the cost now?
• It is the cost of transiting an AS network
• What does it mean?
• Can not compare costs from two different
AS
• Cost may have to do more with business
than network engineering
– Sending traffic to a given route may cost me
more
Policy Routing
• By controlling what I export I control what traffic
I carry
– I can have backdoor links for example
• By controlling what I import I control where my
traffic goes
• All these are based on business reasons and do not
have to do much with routing itself
– I have a contract to provide or buy service with a
customer or by a provider
– Configured manually on each border router as a list of
import and export policies
– Can be long, tedious and error-prone
A Naïve Approach: EGP
• For NSFnet:
– Assume 2 level hierarchy with a backbone/stub
networks
– No problem with loops
• Periodic exchange of reachability
information
– Works fine as long as the routes are not too
many
• Advertise a single integer cost with each
reachable destination
– But what do I do with it?
Internet Evolution
• Single network until 1982-84
– ARPAnet
• NSFnet
– 2 level hierarchy
• Internet gradually becomes private around 1985
• Many independent operators
– Complex hierarchy
• Address exhaustion and CIDR in 1992
• Route table size explosion
Classless Inter-Domain Routing (CIDR)
• We saw that the / prefix len can be arbitrary
– Well it was not like that all the time
• Class A, B, C addresses and a large waste of
addresses
– I need 1000 IP addresses I get a a.b/16 and I waste the
other 15K addresses!
– In 1991 class B was in danger of being exhausted
(expected around March 1994)
• A variable prefix length allows more accurate
allocation of addresses and reduces the address
waste
– Instead of a a.b/16 get a.b.c/24, a.b.d/24, a.b.e/24,
a.b.f/24 and I do not waste any address
– BUT routers need to know three networks now,
LARGER routing tables
Hierarchical Address allocation
• This is why the second component of CIDR is the
hierarchical address allocation, routers still know
only a.b/16
• IP addresses are allocated by Internet Assigned
Numbers Authority (IANA)
• and given to Regional Internet Registries (RIRs)
– 5 for each major region of the world
– They assign from the address allocation to other entities
in the region
Protocols adapt to Internet
evolution
• EGP (1984)
– When things were simple
• BGP-1, BGP-2, BGP-3 between 1989-1994
• And BGP-4 at 1995
– To include CIDR and arbitrary hierarchies
• BGP-4 still there with extensions
– Multi-protocol
• To handle new protocols, IPv6 mostly, multicast, VPNs
– RR
• Better scalability
– Communities
• Better management
Internet evolved to…
• Something very large and complex
• Structure is definitely not an acyclic graph
– Dual homing, peering etc…
– I can have routing loops
• Reachable destinations are MANY
– Around 90K unique prefixes these days
• Many more if we count multiple routes to a prefix
– Hard to exchange them periodically
• Each AS has its own internal policies and notion
of cost
– It is not possible to compare between different ASes
How to deal with arbitrary AS
topologies?
• BGP-4
– Path vector, CIDR, policies
• Path vector
– I list all the ASes in the path
– Loop avoidance is trivial:
• make sure that I am not listed in the path
• Add myself in the path when I advertise a prefix
• Of course there is no free lunch:
– Route advertisements are getting large…
– It really depends on the topology of the internet
– Some attempt to measure is at RFC 1774
Paths
• BGP manages paths
• Path consists of
– Network Layer Reachability Information
(NLRI) e.g 12.50.45/24
– A sequence of PATH attributes that give info
related to this destination
• PATH attributes
– Each have a Flags field
• Optional or well known (well known must be
supported by all routers)
• Transitive or local (Transitive gets propagated, local
not)
• Partial or not (partial applies only to part of the path)
Important path attributes
• ORIGIN (well known)
– Is this path learned from IGP, BGP or other
• AS_PATH
– The list of ASes (well known)
• NEXT_HOP
– Next hop to reach the prefix (well known)
• MULTI_EXIT_DISC (MED)
– Helps selection of paths (local, optional)
• LOCAL_PREF
– Helps selection of paths (well known)
BGP next hop
• EXAMPLE
• Can be third party
• IGP knows how to reach the next hop
– Recursive route lookup
– Can use the best route to reach the next hop
• Next hop usually is the loopback address
– Never goes down
Internal BGP
• An AS will have multiple border routers
talking to different peers
– May learn multiple routes for the same prefix
– How do I choose which one to use?
– Border routers must make a consistent decision
• Else I may have routing loops
• All border routers in my AS talk to each
other
– Internal BGP or iBGP
– Over multiple IGP hops, not directly connected
– Must be a full-mesh
MED and Local Pref
• EXAMPLE
• Local pref has effect on outgoing traffic
• MED on incoming traffic