LM CCN Section 4.2: Routing Across Autonomous Systems
Computer and Communication Networks
Routing Across Autonomous Systems John Easton
1
Learning Objectives
o Learn how we describe autonomous systems
o Understand the principles behind inter-AS routing
– Path Vector Routing
– Policy Routing
– Border Gateway Protocol
2
Autonomous Systems
o TheglobalInternettopologyconsistsofa collection of Autonomous Systems (AS) o ASareidentifiedbyASnumbers(ASN)
– Limitednumericalspace o 16-bit until 2007
– asplain notation e.g. “65526” o 16/32-bit since 2007
– asdot notation e.g. 65546 becomes “1.10” o RoutingandAS
– Internally,ASselectroutesbasedontheirInteriorGatewayProtocol choice
– Externally,ASmustuseaknownExteriorGatewayProtocol(EGP) such as the Border Gateway Protocol (BGP)
3
1
LM CCN Section 4.2: Routing Across Autonomous Systems
Types of Autonomous System
o Around 60,000 unique AS on the Internet in March 2018 – Largest included 5420 routable prefixes
– Google only has 384
o Three main types: – Transit
– Multihomed
– Stub
o Main functional difference is in routing policy
– Only transit AS relay traffic destined for other AS
4
Transit AS
o Characterised by multiple, redundant connections to the outside o Carry transit traffic to other networks
o Transit is typically charged
– Mbit / second / month
– Normally include minimum bandwidth requirement o May include Service Level Agreement (SLA)
– Money back if QoS criteria not delivered o Examples include:
– ISPs
– JANET
5
Multihomed AS
o Multihomednetworksareconnectedviamultiplelinks,butdonotcarry transit traffic
o Normallydesignedto:
– Increasereliabilityorperformance – Reducecosts
o Host multihoming
– Singledevicetomultiplenetworks(e.g.3Gandwireless)
o Classical multihoming
– Networkconnectedbytwoormoreproviders,usingownindependent
address range, ASN, and BGP routers. Expensive o Multihomingwithmultipleaddresses
– Twoormoreproviderswithindependentaddresses(e.g.BTandVirgin) o Careneededtoavoidsinglepointsoffailureupstream
– Routers,DNSserversetc.
6
2
LM CCN Section 4.2: Routing Across Autonomous Systems
Stub AS
o Stub AS are networks connected to the wider Internet by a single physical or logical link
– No knowledge of other AS
– Carry only traffic to/from machines in their own address space
o Does not require an ASN (network prefixes included in provider’s routing table)
o Examples include:
– Enterprise LANs
– Home user connected to an ISP
7
Peering
o Voluntary interconnection of separate networks – Mutual agreement to carry traffic
o Distinct from transit service – Settlement-free
o Public and private models
– “Shared fabric” linked at Internet Exchanges (public) – Dedicated physical link not shared with others
o Motivations include:
– Improved redundancy
– Greater choice and control of routing options – Increased capacity
– Improved external perception
8
Path Vector Routing
o Similar in principle to distance vector routing in IGP
o One node “speaks” for the AS
– Holds the AS routing table
– Publishes routing table to
neighbours
o Advertised routing is based on path, not metric
– e.g. path to prefix 147.188.146.0/24 o Three phases
– Initialisation – Sharing
– Updating
9
3
LM CCN Section 4.2: Routing Across Autonomous Systems
Path Vector Routing – Initialisation
o Initially, each speaker only knows its own nodes – Those within the AS
o At this stage, each router’s table includes local references only
R1
Destination
Path
201.2.0.0/24
AS1
201.2.1.0/24
AS1
201.2.2.0/24
AS1
10
Path Vector Routing – Sharing
o Speaker from each AS shares their table with neighbours – AS1 shares to AS2, AS3, AS4
– AS2 shares to AS1
– AS3 shares to AS1, AS4
– AS4 shares to AS1, AS3, AS5 – AS5 shares to AS4
o Over time information diffuses around the network
1
3
2
4
5
11
12
Path Vector Routing – Updating
o Speaker nodes update their own routing table based on information received, adding its own AS to the path
o Formation of loops is a risk
– On receipt, speakers check path for their own AS – If already present, they reject the advertisement
o Where possible addresses are aggregated as updates are received
o Ranges may include address blocks not present in the AS
Figure from Russ White, Danny McPherson, and Srihari Sangli (2004) Practical BGP, Addison Wesley ISBN-10: 0-321-12700-5
4
LM CCN Section 4.2: Routing Across Autonomous Systems
Policy Routing
o Policy routing allows network administrators to add rules preventing or promoting routes via particular AS
o It can be easily implemented in a path vector routing scheme
o On receipt of an advertisement, router checks path
– If a listed AS is against policy, the advertisement is ignored
o The path is not added to the routing table
o The path is not shared to neighbours
13
Border Gateway Protocol
o De facto standard protocol for inter-AS routing o Enables AS to:
– Obtain reachability information from neighbours
– Propagate reachability information internally
– Determine “good” routes to subnets based on
policy
– Advertise subnet existence to other AS
o “I exist, and I am here” o Path vector approach
o Complex
– Many issues still not well understood
14
BGP Basics
o BGP is based on semi-permanent TCP connections
– Link BGP peers
– Configured o 2 session types:
– eBGP
– iBGP
o Connection and messages constitute BGP session
eBGP iBGP
15
5
LM CCN Section 4.2: Routing Across Autonomous Systems
BGP Messages
o Speakers (peers) are manually configured
o Connection set-up managed via state machine
– Idle
– Connect
– OpenSent -> Active (if failed) – OpenConfirm
– Established
o Once connection is established peers begin to exchange routing information
State machine image by Johannes Rössel, via Wikimedia Commons https://upload.wikimedia.org/wikipedia/commons/a/a8/BGP_FSM.svg
16
BGP Messages (Cont.)
o BGP messages have common header
– Marker – 16 bytes, used for authentication
– Length – 2 bytes, defines message length inc. header – Type – 1 byte, defines packet type
Figure from Garcia, A. L., & Widjaja, I. (2000). Communication networks. Ed. McGraw Hill.
17
BGP Messages (Cont.)
o 5 message types: – Open
– Update
– KeepAlive
– Notification
– Route-Refresh
o KeepAlive and Route-Refresh only used in established state
o Advertised routes added / ignored as discussed earlier in the lecture
Open
Update
BGP Messages
KeepAlive
Notification
Route- Refresh
18
6
LM CCN Section 4.2: Routing Across Autonomous Systems
BGP Messages (Cont.)
o OPEN message
Figure from Garcia, A. L., & Widjaja, I. (2000). Communication networks. Ed. McGraw Hill.
Marker
Length
Type: Open
Version
My autonomous system
Hold time
BGP Identifier
Opt. param. length
Optional parameters
19
AS_PATH and NEXT_HOP
o BGP uses several path attributes – RFC 4271 to find out more
o Key attributes are:
– AS_PATH – Contains the ASs through which the
advertisement has passed
– NEXT_HOP – Lists the router interface the path starts on
AS1 x
AS2
z
20
BGP Route Selection
o Routers may be aware of multiple paths to a prefix – Selection process required
o Rules invoked sequentially until only one remains – Local preference
– Path length (distance vector)
– Closest next hop
– Lowest BGP identifier
21
7
LM CCN Section 4.2: Routing Across Autonomous Systems
Route Policies
o Policyisthedominantconsiderationforinter-domainrouting – Performanceofrouteislessimportant
o No “cost” criteria beyond # hops in route selection… – …unless defined by policy!
o BGPdividesintoimportandexportpolicies
– Importappliedatreceiptofrouteadvertisements – Exportdeterminetheroutesadvertised
o Commonpolicycriteriainclude:
– Routecosts,billing,peeringagreements
– Securityconsiderations
– National/regionallimitationsondatatransit – Preferencetoolderroutes
o Policiescanbeusedtomanageknownissues
22
Selective Route Advertisement
o Allows AS to influence the traffic passing through them
o A multihomed network may know it connects two AS, but will not
advertise the path
– Doesn’t allow transit
o Not advertising routes removes potential redundancy A
– Not great for resilience of the larger network
o No official rules for this
– Why policy is so important
C
B
D
23
BGP Route Processing Flow
24
8
LM CCN Section 4.2: Routing Across Autonomous Systems
BGP Convergence and Instability
o GloballycorrelatedinstabilityinBGProutechoices not uncommon
– Somearewellunderstood…
– …otherslessso
o BGPdoesnotguaranteeconvergenceonaunique
solution
– Unpredictableorderofupdatesdetermines
which wins on any given day o Noguaranteeofconvergence
– NP-completeproblemtocheckconfigurations o Overlycomplexpoliciescanintroduceanomalies
25
BGP Convergence and Instability
(Cont.)
o Understanding of instability comes from empirical measurement – Routing loops
o Persistent or transient – Connectivity may change – Route flapping
– Instability due to attacks
o Congestion leading to TCP timeouts and loss of KeepAlive messages
o Occasional vendor update / configuration issues – Much like security in ICS
26
Summary
o Learn how we describe autonomous systems
o Understand the principles behind inter-AS routing
– Path Vector Routing
– Policy Routing
– Border Gateway Protocol
27
9