## iof-docs / bgp_model / bgp_model.tex @ d5aa08f5

History | View | Annotate | Download (11.2 KB)

1 |
\documentclass[twocolumn, 10pt]{article} |
---|---|

2 |
\usepackage{acronym} |

3 |
\usepackage{tikz} |

4 |
\usepackage{amssymb} |

5 |
\usepackage{amsmath} |

6 |
\usetikzlibrary{calc,shapes,arrows} |

7 |
\usepackage{cleveref} |

8 | |

9 |
\title{BGP model and other oddities} |

10 |
\begin{document} |

11 |
\maketitle |

12 | |

13 |
\acrodef{ADV}{advertisement} |

14 |
\acrodef{AS}{autonomous system} |

15 |
\acrodef{MiCe}{Milani Centrality} |

16 | |

17 |
We model a eBGP speaker graph; in the following \ac{AS}, speaker and node are used interchangeably. |

18 | |

19 |
\section{Preliminaries} |

20 |
Nodes form a communication network to propagate BGP \acp{ADV}, the BGP messages. |

21 |
\acp{ADV} can be of several types, the two related to prefix/destinations are |

22 |
\begin{itemize} |

23 |
\item UPDATE; |

24 |
\item WITHDRAWAL. |

25 |
\end{itemize} |

26 |
We are not interested in the others, devoted to connection management. |

27 | |

28 |
We use the terms prefix and destination interchangeably and they indicate an IP subnet or a collection of IP subnets. |

29 | |

30 |
A route is a pair $r=(d,\xi)$ of destination and attributes. |

31 |
$\xi$ contains information such as: |

32 |
\begin{itemize} |

33 |
\item path, which is a list of \acp{AS}; |

34 |
\item originator id, which is the IP address for the entry point of the originating \ac{AS}. |

35 |
\end{itemize} |

36 | |

37 |
\section{BGP graph} |

38 |
Nodes form a strongly connected bidirectional graph $G(V,E)$. |

39 |
We indicate as $G^k(V^k, E^k)$ the fully connected subgraph of tier-one BGP nodes, such that, $V^k\subset V,\ E^K = V^k\times V^k$. |

40 | |

41 |
Links can be either peer-to-peer or customer-provider depending on the role involved nodes are playing. |

42 |
We indicate with $\Lambda=\{\pi,c,s\}$ the labels indicating peer, consumer and provider respectively. |

43 |
The function $\lambda:E\to \Lambda$ assigns to a node edge $(i,j)$ the role $i$ has with respect to $j$. |

44 |
Hence, $\lambda(i,j) = \pi \iff \lambda(j,i)=\pi$ and $\lambda(i,j) = c \iff \lambda(j,i)=s$ |

45 | |

46 |
Note that, $\lambda(i,j) = \pi\ \forall i,j\in V^k$. |

47 | |

48 |
We call $N_i = \{j\in V: \exists (i,j)\in E\}$ the set of neighbours for node $i$ and $C_i=\{j\in N_i: \lambda(i,j)=s\}$ the set of customers of node $i$. |

49 |
\section{Advertisement propagation} |

50 |
When a node $i\in V$ generates an \ac{ADV} for the route $r$, it is propagated to all nodes using the links of $G(V,E)$. |

51 |
Propagation considers: |

52 |
\begin{itemize} |

53 |
\item $\lambda()$; |

54 |
\item node policies blocking \ac{ADV} forwarding. |

55 |
\end{itemize} |

56 | |

57 |
In the following we neglect blocking policies for the ease of analysis but it should not change it too much. |

58 |
\begin{figure} |

59 |
\centering |

60 |
\begin{tikzpicture} |

61 |
\tikzset{edge/.style = {->,> = latex',line width=0.2mm}} |

62 | |

63 |
\node[rectangle,text width=5em,align=center,draw=black] (b1) {$j$ receives $r$ from $i$}; |

64 |
\node[diamond,text width=4em,align=center,draw=black,below of=b1,node distance=7em] (b2) {$\lambda(i,j)==c?$}; |

65 |
\node[rectangle,text width=5em,align=center,draw=black] at ($(b2.west)+(-1.0,-1.5)$) (b3) {$j$ propagates to $C_j$}; |

66 |
\node[rectangle,text width=5em,align=center,draw=black] at ($(b2.east)+(+1.0,-1.5)$) (b4) {$j$ propagates to $N_j\setminus \{i\}$}; |

67 | |

68 |
\draw[edge] (b1)->(b2); |

69 |
\draw[edge] (b2)-|(b3) node[midway, draw=none, above] {n} ; |

70 |
\draw[edge] (b2)-|(b4) node[midway, draw=none, above] {y} ; |

71 | |

72 |
\end{tikzpicture} |

73 |
\caption{Flow chart for \ac{ADV} forwarding.} |

74 |
\label{fig:adv_forwarding} |

75 |
\end{figure} |

76 | |

77 |
\cref{fig:adv_forwarding} represents the deciding policy for \ac{ADV} forwarding using the standard policy of \textit{no-valley and prefer-customer}~\cite{elmokashfi2010scalability}. |

78 | |

79 |
Propagation policies and $G$ structure (it includes a full meshed graph $G^k$ of nodes with peer links), implies a very specific pattern of route propagation from one node $i\in V\setminus V^k$ to the rest of the network. |

80 |
We model this pattern by sub-dividing the graph $G$ in three components as the propagation happens in three phases: |

81 |
\begin{itemize} |

82 |
\item Phase 1: node $i\in V\setminus V^k$ generates an \ac{ADV} for route $r$ and this spreads toward a node $z\in V^k$; we call the resulting sub-graph $G^{(1)}(V^{(1)},E^{(1)})$; |

83 |
\item Phase 2: \ac{ADV} propagates toward tier one nodes $V^k$; the resulting sub-graph is $G^{(2)}=G^k$; |

84 |
\item Phase 3: \ac{ADV} propagates from $z\in V^k$ to all the nodes $j\in V\setminus V^k\setminus V^{(1)}$; we call the resulting sub-graph $G^{(3)}(V^{(3)},E^{(3)})$. |

85 |
\end{itemize} |

86 | |

87 |
\subsection{Phase 1 graph} |

88 |
Let $i$ be the \ac{ADV} originator and $j\in V$ another node in $G$. |

89 |
$j\in V^{(1)} \iff \exists p_{ij}$ a path in $G$ between $i$ and $j$, with $p_{ij}=(i,k_0)\dots (k_l,j)$ such that: |

90 |
\begin{itemize} |

91 |
\item $k_x\notin V^k,\ \forall x=0,\dots,l$; |

92 |
\item we have one of the following conditions: |

93 |
\begin{itemize} |

94 |
\item $\lambda(\rho,t)=c\ \forall (\rho,t)\in p_{ij}$; |

95 |
\item $\exists z\leq l: \lambda(\rho,t)=c\ \forall (\rho,t)\in p_{ik_z}, \lambda(k_z,k_{z+1})=\pi, \lambda(\rho,t)=s\ \forall (\rho,t)\in p_{k_{z+1},j}$ |

96 |
\end{itemize} |

97 |
\end{itemize} |

98 |
\subsection{Phase 3 graph} |

99 |
Phase 3 graph is the one connecting the nodes $V^k$ to all the nodes $V^{(3)}=V\setminus V^k\setminus V^{(1)}$. |

100 |
$j\in V^{(3)} \iff \exists p_{ij}$ a path in $G$ between $i\in V^k$ and $j$, with $p_{ij}=(i,k_0)\dots (k_l,j)$ such that: |

101 |
\begin{itemize} |

102 |
\item $j,k_x\notin V^k\cup V^{(1)},\ \forall x=0,\dots,l$; |

103 |
\item $\lambda(\rho,t)=s\ \forall (\rho,t)\in p_{ij}$; |

104 |
\end{itemize} |

105 | |

106 |
\subsection{Propagation graph} |

107 |
Given an originator $i\in V\setminus V^k$, we call propagation graph $G^P=(V^{(1)}\cup V^{(2)}\cup V^{(3)},E^{(1)}\cup E^{(2)}\cup E^{(3)})$ the graph comprising all the feasible links for \ac{ADV} propagation. |

108 | |

109 |
\section{Node Policy} |

110 |
Nodes evaluate route \acp{ADV} with a function $\Gamma: R \to [0,100]\cap \mathbb{N}$, where $R$ is the set of routes. |

111 |
Given two routes $r_1,r_2$, a node prefers $r_1$ if $\Gamma(r_1)\geq \Gamma(r_2)$ and $r_2$ otherwise. |

112 | |

113 |
As noted before, $r\in R$ is a couple $(d, \xi)$ of destination and attributes. |

114 |
The simplest form of policy returns the (possibly weighted) length of the \ac{AS} path indicated in the attributes $\xi$ (hop distance to $d$). |

115 | |

116 |
Policies are implemented defining the $\Gamma_i$ function for each $i\in V$. |

117 | |

118 |
\section{MRAI timers} |

119 |
For each neighbour $j$, every node $i$ consider an MRAI timer value $T_{ij}$. |

120 |
The typical value for it is 30 seconds. |

121 | |

122 |
Each node will consider route advertisements separately. |

123 |
Routes can differ for the destination $d$ or for attributes $\xi$. |

124 |
If two routes share the same destination $d$ but they include different attributes $\xi_1\neq \xi_2$ then node $i$ will process them separately. |

125 | |

126 |
With respect to the destination $d$, node $i$ will not send more than one message every $T_{ij}$ seconds. |

127 |
If multiple route messages $r_1,\dots,r_m$ arrive to $i$ for the same destination $d$ but with different attributes $\xi_1,\dots,\xi_m$, node $i$ will consider them separately. |

128 |
Whenever node $i$ recives a route UPDATE for destination $d$ it updates its Adj-RIBs-In \footnote{the information structure pertaining route \ac{ADV}}, and if the new route $r$ obtain a newly best score $\Gamma(r)$, then it selects $\xi_m$ as the new preferred attribute for destination $d$, and its schedules a new \ac{ADV} to be sent according to MRAI. |

129 |
When the MRAi timer fires only the new best option is advertised. |

130 | |

131 |
For each destination $d$, node $i$ has a queue of route advertisements $r_1,\dots,r_m$, and, for each $j\in N_i$ it keeps a function $\tau(i,j,d): V\times V\times D\to [0,T_{ij}]$ expressing the minimum remaining time for another transmission. |

132 | |

133 |
\subsection{Fabrikant issue} |

134 |
In the Fabrikant et al. paper~\cite{fabrikant2011something} it is describe a possible issue related to timers and path exploration. |

135 | |

136 |
This issue happens when there are multipaths in the propagation graph $G^P$ and a specific timer allocation $T_{ij}$. |

137 |
In the following we suppose that all nodes $i$ have $\tau(i,j,d)=0,\ \forall j\in N_i$ (ready to fire). |

138 | |

139 |
\textbf{Duplicate ADV.} Let $i\in V$ originate a route advertisement $r$ and let $j\in V$ receives it at certain time $t_0$. |

140 |
$j$ will process the \ac{ADV} and propagate it at time $t_0+\epsilon$; if $j$ finds more advantageous, given the new advertisement, to reach $d$ through another node, let's say $z\in V$, it will implement that in its routing table and will propagate the \ac{ADV} with the modified $\xi$. |

141 |
However, if $z$ also receives the \ac{ADV} from $i$ at $t_0$, it has to change its routing table and propagate the \ac{ADV} accordingly but, if it does that at time greater than $t_0+\epsilon$, it happens that $j$ indeed receives the updated route from $z$ which may change again its routing table but it cannot propagate the new information as $\tau(j,k,d)>0,\ \forall k\in N_j$. |

142 | |

143 |
This behaviour makes $j$ send two \acp{ADV} for the same destination $d$, the first of which was computed on outdated information. |

144 |
Worse than that, the updated \ac{ADV} cannot be propagated before $T_{ik}$ seconds to the neighbours $k\in N_j$. |

145 | |

146 |
\textbf{Duplicate duplication.} Suppose that $k\in N_j$ receives the \ac{ADV} at time $t_0+\epsilon$. |

147 |
$k$ generates hence an \ac{ADV} and propagates the wrong information. |

148 |
The duplication can happen again and $k$ receives at $t_1$ an \ac{ADV} from a node $h$ in a path from $k$ and $j$. |

149 |
So $k$ has to wait $\tau(j,x,d)$ seconds before sending the updated information to its neighbour $x\in N_k$. |

150 |
Now, if $T_{kx} > T_{jk}$ then $k$ will receive the update from $j$ and send only one duplicate \ac{ADV}. |

151 |
But, if $T_{kx} < T_{jk}$ it means that the forementioned step can be repeated twice and $k$ will send a total of 4 \ac{ADV} messages. |

152 | |

153 |
\textbf{Exponential explosion.} In general and in presence of multipaths, if $p_{ij}=(i,k_0),\dots,(k_l,j)$ is a propagation path (a path in $G^P$), then the number of \ac{ADV} messages (and route oscillation) is exponential on the overall number of decreasing timers on the path. |

154 | |

155 |
\section{Solution sketch} |

156 |
Ideally, we would like to have increasing $T_{ij}$ along the propagation paths in $G^P$. |

157 |
Because of path aggregation\footnote{It is an important feature but Bird does not perform it.}, $\xi$ does not describe the exact path but just a sequence of node subsets. |

158 |
Hence, it is difficult for a node to select its timer wrt its neighbours. |

159 | |

160 |
Instead we can use \ac{MiCe} to infer the position of a node\footnote{We would need the position on the path but \ac{MiCe} is computed graph-wide.} and tune the timers $T_{ij}$ accordingly. |

161 | |

162 |
Since, two nodes $j_1,j_2$ at the periphery, hence with similar centrality, could be one in $G^{(1)}$ and the other in $G^{(3)}$ respectively, we need to consider their case separately. |

163 | |

164 |
Considering a graph-wide maximum timer $T=30$ and \ac{MiCe} centrality $c_i\in [0,1]$ for node $i$, one strategy could be to assign: |

165 |
\begin{itemize} |

166 |
\item $T_{ij}=\frac{Tc_i}{2},\ \forall i\in V^{(1)}$ |

167 |
\item $T_{ij}=\frac{T}{2},\ \forall i\in V^k$ |

168 |
\item $T_{ij}=\frac{T(1-c_i)}{2}+\frac{T}{2}=\frac{T(2-c_i)}{2},\ \forall i\in V^{(3)}$ |

169 |
\end{itemize} |

170 | |

171 |
\textbf{Note:} we are not sure about \ac{MiCe} normalization in the interval $[0,1]$ applicability. |

172 | |

173 |
\section{Solution sketch No.2} |

174 |
Ideally, we would like to have increasing $T_{ij}$ along the propagation paths in $G^P$. |

175 |
We can propose an extension to the \ac{ADV} UPDATE message so to include sending node MRAI timer. |

176 | |

177 |
\begin{enumerate} |

178 |
\item Node $i$ advertise route $r$; |

179 |
\item Node $i$ sends an UPDATE to $j\in N_i$ for $r$ with an MRAI of $T_{ij}$; |

180 |
\item If node $j$ accepts $r$ than $j$ sets its MRAI for its neighbour $z\in N_j$, $T_{jz}=T_{ij}+c$. |

181 |
\item The procedure repeats from point 2 with $i=j$. |

182 |
\end{enumerate} |

183 | |

184 |
$c$ is a reasonable enough value. |

185 | |

186 |
\bibliographystyle{IEEEtran} |

187 |
\bibliography{biblio} |

188 | |

189 |
\end{document} |