-
Notifications
You must be signed in to change notification settings - Fork 3
/
bgp.tex
198 lines (149 loc) · 10.5 KB
/
bgp.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
\chapter{An Introduction to BGP}
As the Internet grew it was no longer possible to keep all routers in a single routing domain.
It was necessary to add another layer of organization.
All the routers that belonged to the same organization and were controlled by the same network administration team were grouped in an Autonomous System.
For example, Universitat Pompeu Fabra belongs to autonomous system Red Iris with Autonomous System Number AS766.
Guifi.net is a community network that has AS49835.
AS numbers (ASN) are assigned by the Internet Assigned Number Authority (IANA) to Regional Internet Registries (RIR).
RIPE-NCC is the European registry.
Autonomous Systems have to apply for their ASN to the RIR.
These steps are also followed for IP addresses assignments.
ASs can be classified in three different types:
\begin{itemize}
\item Multi-homed: An AS that is connected to more than one neighbouring AS.
Even if one of the neighbours fails, a multi-homed AS can retain Internet connectivity via another neighbour.
\item Stub AS: In this case, the AS appears to be connected to a single neighbouring AS.
It can be that an Stub AS has private peering agreements with other ASs.
\item Transit AS: An AS that uses its networks to carry traffic of other ASs.
\end{itemize}
Within an autonomous system, the system administrators configure an Interior Gateway Protocol IGP.
Examples of IGP are RIP, OSPF and IS-IS.
The network administration team agrees in the protocol that is going to be used and the per-hop metrics.
Then the protocol computes the routes that minimize those metrics.
IGP decide which is the next router in the path towards the destination.
There is another layer of routing between Autonomous Systems.
When a network has a packet destined to another autonomous system, it needs to decide to which neighbouring autonomous system that packet will be forwarded.
The protocol that is used in the Internet to route between Autonomous Systems is the Border Gateway Protocol (BGP).
A key difference between IGPs and BGPs is that the latter routes packets between different organizations that not necessarily trust each other nor share the same goals.
Choosing the shorter path is not always the best option, and it is not possible in agreeing in common metric for each connection between two ASs.
If two alternative paths exist, one AS may prefer one path and the other AS the other path.
There are ASs of many different sizes and scopes.
Some ASs are local and provide access to end users, while others are international and only provide services to other ISPs.
An example of the former is Jazztel and an example of the latter is Cogent.
The connections between ISPs can be of two different types: either transit or peering.
In the peering relation, two ISPs exchange traffic without charging each other.
In the case of transit, there is one ISP that is a customer of the other and pays for the carried traffic.
\begin{figure}[!h]
\centering
\includegraphics[width=\linewidth]{figures/peering-and-transit.eps}
\caption{Example network topology with Autonomous Systems and peering and transit connections}
\label{fig:peering-and-transit}
\end{figure}
Fig.~\ref{fig:peering-and-transit} shows an example topology in which clouds represent autonomous systems that are connected with transit and peering links.
Different autonomous systems normally connect at Internet exchange points.
Catnix is one example of an Internet exchange point.
In routing between different ASs, it is necessary to account for policy.
Each ASs has a different policy that is translated to routing announcements and routing decisions.
For example, if C has a packet for the AS G, the shortest path is via AS A.
However, AS C has to pay for the transit that is sent to A, and therefore C prefers to send the packet to AS D with which it has a peering agreement.
In this case, policy is taken into account to make a routing decision.
An example of route announcement conditioned by policy is that AS D does not announce a route to AS E to AS C even though this route exists.
The reason is that AS D is not being payed for carrying transit from AS C to AS E and in principle has no incentive to carry that traffic.
With BGP both route announcements and routing decisions can be conditioned by policy.
In principle, the order of preference for routing a packet is
\begin{itemize}
\item to a client (the AS makes money)
\item to a peer
\item to a provider (the AS pays money)
\end{itemize}
Regarding the announcements, the normal policy is
\begin{itemize}
\item announce the routes of clients to everyone.
\item announce the routes of peers to clients.
\item announce the routes of providers to clients.
\end{itemize}
It is possible to also set policy in the form of BGP filters.
Back in 2008, Pakistan telecom hijacked Youtube traffic by announcing a more specific prefix.
This announcement was not filtered.
Instead it was filtered and propagated by other AS effectively redirecting Youtube traffic to Pakistan Telecom.
The following is a list of events\footnote{quoted from http://www.circleid.com/posts/ 82258\_pakistan\_hijacks\_youtube\_closer\_look}
\begin{quote}
\begin{itemize}
\item 18:47:45 First evidence of hijacked route propagating in Asia, AS path 3491 17557
\item 18:48:00 Several big trans-Pacific providers carrying hijacked route (9 ASNs)
\item 18:48:30 Several DFZ providers now carrying the bad route (and 47 ASNs)
\item 18:49:00 Most of the DFZ now carrying the bad route (and 93 ASNs)
\item 18:49:30 All providers who will carry the hijacked route have it (total 97 ASNs)
\item 20:07:25 YouTube, AS 36561 advertises the /24 that has been hijacked to its providers
\item 20:07:30 Several DFZ providers stop carrying the erroneous route
\item 20:08:00 Many downstream providers also drop the bad route
\item 20:08:30 And a total of 40 some-odd providers have stopped using the hijacked route
\item 20:18:43 And now, two more specific /25 routes are first seen from 36561
\item 20:19:37 25 more providers prefer the /25 routes from 36561
\item 20:28:12 Peers of 36561 start seeing the routes that were advertised to transit at 20:07
\item 20:50:59 Evidence of attempted prepending, AS path was 3491 17557 17557
\item 20:59:39 Hijacked prefix is withdrawn by 3491, who disconnect 17557
\end{itemize}
\end{quote}
Pakistan Telecom advertised a prefix (208.65.153.0/24) that was more specific that the one advertised by Youtube (208.65.152.0/22) and therefore it was used by BGP routers.
The response of Youtube was to announce two even more specific routes /25.
\section{Path Routing}
To make it possible to implement policy routing, BGP uses path announcement.
For example, if G contains the 12.34.56.00/24 network, it will announce it as:
\texttt{through ``G, '' reaches 12.34.56.00/24}.
AS F will re-announce the route as
\texttt{through ``F, G, '' reaches 12.34.56.00/24}.
And AS D will re-announce the route as
\texttt{through ``D, F, G, '' reaches 12.34.56.00/24}.
Then AS C compares this announcement with other announcements such as
\texttt{through ``A, G, '' reaches 12.34.56.00/24}.
And makes a decision according to its policy.
To prevent loops, an AS never accepts a route announcement if it finds itself in the announced path.
\section{Route aggregation}
On of the challenges of the current internet is the growth of the global routing table.
At the time of writing, a DFZ router can see more than half a million routes.
A partial solution to the growth of the number of routes is route aggregation.
A BGP router can combine different announcement of consecutive networks in a single one.
For example, if AS D in Fig.~\ref{fig:peering-and-transit} announces 12.34.58.0/24 and AS E announces 12.34.59.0/24, then AS B can announce 12.34.58.0/23.
\texttt{through ``Sequence(B), Set(D, E) '' reaches 12.34.58.00/23}.
Sequence means that the whole network is announced through B.
Set means that a fraction of the network is announced through D and E.
\section{BGP connections and messages}
IGP protocols such as OSPF and RIP try to discover neighbouring routers to exchange routes.
This is not the case with BGP routers.
In BGP, the administrator configures the BGP neighbours with which the BGP router will exchange routes.
The two neighbours (or peers) then establish a TCP connection and exchange messages.
The BGP messages are the following:
\begin{itemize}
\item OPEN to start the connection.
\item UPDATE to send routing information. When the routing information changes, the BGP routers will send additional UPDATE messages.
\item KEEP-ALIVE to maintain the connection open when there is no other data to send.
\item ROUTE-REFRESH to ask the other party to re-send all routing information.
\item NOTIFICATION to inform of errors.
\end{itemize}
The BGP protocol includes a security feature that requires both parties to agree in common secret and use it to derive an MD5 hash of the exchanged messages that is included in the messages.
The receiving end can re-compute the MD5 value and compare with the received one.
Using the shared secret, BGP can prevent that a malicious attacker forges BGP messages.
\section{Interior BGP}
It is normal that an autonomous system has multiple connections with other AS.
It may have different BGP routers at different locations of the network.
It is necessary that those routers coordinate and for this purpose they can use Interior BGP (or IBGP).
IBGP routers are normally at different borders of the network.
They are not directly attached to each other.
They talk using TCP sessions that cross the AS traversing different routers.
\begin{figure}[!h]
\centering
\includegraphics[width=\linewidth]{figures/ibgp.eps}
\caption{An autonomous system with three BGP routers.}
\label{fig:ibgp}
\end{figure}
Fig~\ref{fig:ibgp} shows an autonomous system with many routers.
Three of them are border routers that exchange information between them using IBGP.
Let's consider that this is AS 33.
In IBGP the routers must accept routing advertisements even if there is their own ASN in the path.
The announcement received via IBGP are not propagated to other IBGP peers.
Therefore, routers B and C in the example will not relay the announcement to each other.
This prevents the creation of roting loops.
As a consequence of the fact that IBGP announcements are not relayed to IBGP neighbours, it is necessary that all IBGP routers of the AS are connected to each other.
If the AS is large and has several IBGP routers, it is not scalable to have all IBGP routers connected as a full mesh.
In this case, there are two possible alternatives: \emph{route reflectors} and \emph{confederations}.