\errorcontextlines=99

\documentclass[nopagebreak,ps,10pt,a5paper]{ppr-prv}% DO NOT EDIT---WILL BE OVERWRITTEN
\geometry{margin=10mm}% DO NOT EDIT---WILL BE OVERWRITTEN

\usepackage{alltt,key,xr,cols,rcs,acro,nick,%
  graphicx,varioref,explanation,booktabs,multicol,amstext}
\usepackage[nolineno,noindent]{lgrind}
\usepackage[toc,highlight,Tycja]{HA-prosper}

% Copyright (c) 2004 by Nick Urbanik <nicku(at)nicku.org>.
% This material may be distributed only subject to the terms and
% conditions set forth in the Open Publication License, v1.0 or later
% (the latest version is presently available at
% http://www.opencontent.org/openpub/).
                                                                                \RCS $Revision: 1.3 $

\renewcommand*{\bs}{\texttt{\char '134}} % Backslash `\'
%\newcommand*{\labTitle}{Routing Tables and Route Summarisation}
\newcommand*{\subject}{Systems and Network Management}
\newcommand*{\emphcolour}[1]{\emph{\red#1}}

\providecommand*{\RPM}{\acro{RPM}\xspace}
\providecommand*{\CD}{\acro{CD}\xspace}
\providecommand*{\IPC}{\acro{IPC}\xspace}
\providecommand*{\UID}{\acro{UID}\xspace}
\providecommand*{\GID}{\acro{GID}\xspace}
\providecommand*{\SMP}{\acro{SMP}\xspace}
\providecommand*{\API}{\acro{API}\xspace}
\providecommand*{\OK}{\acro{OK}\xspace}
\providecommand*{\IETF}{\acro{OK}\xspace}
\providecommand*{\MS}{\acro{MS}\xspace}
\providecommand*{\NAT}{\acro{NAT}\xspace}
\providecommand*{\SME}{\acro{SME}\xspace}
\providecommand*{\BGP}{\acro{BGP}\xspace}
% Get rid of that horrible hash mark in slide numbers in ppr-prv.cls:
\def\no{}


\title{\blue{}Routers and Routing}
\subtitle{Routing Tables and Route Summarisation}
\author{Nick Urbanik \texttt{<nicku\at{}nicku.org>}\\
  \footnotesize{}Copyright Conditions: Open Publication License\\
  \footnotesize{}(see
  \url{http://www.opencontent.org/openpub/})\\
\institution{A computing department}}%
%\author{Nick Urbanik \texttt{<nicku\at{}nicku.org>}\\
%\footnotesize{}Copyright Conditions: GNU FDL (see
%\url{http://www.gnu.org/licenses/fdl.html})}
%\institution{A computing department}
\slideCaption{SNM --- Routing Tables and Route Summarisation --- ver. \RCSRevision}
%\Logo{\includegraphics[width=15mm]{ict-logo-smaller}}

\DefaultTransition{Wipe}
\TitleSlideNav{FullScreen}
\NormalSlideNav{ShowBookmarks}
\LeftFoot{SNM --- ver. \RCSRevision}
\RightFoot{Routing Tables and Route Summarisation}
\begin{document}
\maketitle

\tsection{Routing}

\begin{slide}{Modern Routing Tables}
  \begin{itemize}
  \item Each entry in a routing table has 3 main items:
  \item A network address (the destination)
  \item A netmask length
  \item A next hop address
\begin{alltt}\scriptsize
$ \textbf{route -n}
Kernel IP routing table
Destination     Gateway         Genmask         Flags Iface
172.19.64.0     0.0.0.0         255.255.192.0   U     eth0
127.0.0.0       0.0.0.0         255.0.0.0       U     lo
0.0.0.0         172.19.127.254  0.0.0.0         UG    eth0
\end{alltt}%$
\end{itemize}
\end{slide}

\begin{slide}{The Routing Algorithm}
  \begin{itemize}
  \item For a given destination IP address
  \item Search the routing table for the longest prefix match for the address
  \item Extract the next hop address from the routing table entry
  \item Send the packet to the next hop address
  \item If no match found, report that the destination is unreachable.
  \end{itemize}
\end{slide}

\begin{slide}{Longest Prefix}
  \begin{itemize}
  \item So what does ``{\blue{}longest prefix match}'' mean?
  \item To see if the prefix matches,
    \begin{itemize}
    \item Bitwise AND netmask with destination
    \item Bitwise AND netmask with network from routing table entry
    \item If the two results are equal, then the prefix matches
    \end{itemize}
  \item If we do the same for all entries in the routing table, the
    match with the longest netmask wins.
  \end{itemize}
\end{slide}

\begin{slide}{Example:}
  \begin{itemize}
  \item Given this routing table, where does the packet with
  destination 192.168.0.3 go to?
\begin{alltt}\scriptsize
192.168.0.0     0.0.0.0         255.255.255.0   U     eth0
192.168.25.0    0.0.0.0         255.255.255.0   U     vmnet1
192.168.0.0     172.19.35.254   255.255.0.0     UG    ppp1
0.0.0.0         202.180.160.251 0.0.0.0         UG    ppp0
\end{alltt}
\item How about 192.168.128.48?
\item 192.168.25.10?
\item 192.169.0.1?
\end{itemize}
\end{slide}

\tsection{CIDR}

\begin{slide}{The Big Emergency}
  \begin{itemize}
  \item In the early 90s, it became apparent that two problems were
    quickly going to become overwhelming:
    \begin{itemize}
    \item \emphcolour{Address depletion} --- we were running out of IP
      addresses
    \item \emphcolour{Router table explosion} --- the routing tables
      were growing too fast for the router hardware to cope
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{The Solution: CIDR and NAT}
  \begin{itemize}
  \item Two solutions were developed:
  \item \CIDR (Classless Internet Domain Routing), and
  \item \NAT (Network Address Translation).
    \begin{itemize}
    \item \NAT allows a firewall or router to present one address to
      the outside world, but many to the inside.
    \item In Linux, use iptables.
    \item Use private addresses:
    \item 192.168.0.0/16
    \item 172.12.0.0/12
    \item 10.0.0.0/8
    \end{itemize}
  \end{itemize}
\end{slide}

%% \begin{slide}{Problems CIDR solves}
%%   \begin{itemize}
%%   \item \CIDR helps solve two main problems:
%%     \begin{itemize}
%%     \item Address depletion
%%     \item Router table explosion
%%     \end{itemize}
%%   \end{itemize}
%% \end{slide}

\begin{slide}{Address Depletion}
  \begin{itemize}
  \item Class C was too small for medium sized enterprises
  \item Class B was too big
  \item Many organisations asked for (and received) class B networks
    when they needed only a /22 or /21 network
  \item This used up the available $2^{32}$ addresses too fast
  \item Later there was a need for small Internet allocations of 1 or
    2 addresses.
    \begin{itemize}
    \item Class C was too wasteful for this.
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Router Table Explosion}
  \begin{itemize}
  \item As class B addresses became scarce, \SME{}s were given a number
    of class C network allocations
  \item But each class C needed a separate routing table advertisement
  \item Local information about the internal network structure of a
    company needed to be advertised world wide
  \item This did not scale
  \item By now routing would need much more \CPU and \RAM than is
    currently used, and the Internet would have slowed further.
  \end{itemize}
\end{slide}

\begin{slide}{How does CIDR solve them?}
  \begin{itemize}
  \item New address allocations can be sized accurately to the need
    \begin{itemize}
    \item When requesting addresses, the authority
      (\url{http://www.apnic.net/}) will reserve some addresses for
      future growth if you specify you will need them
    \end{itemize}
  \item New address allocations are made taking into account
    neighbouring networks
  \item Aim is to \emphcolour{summarise} many routes into as few
    routes as possible.
  \end{itemize}
\end{slide}

\tsection{Aggregating Routes}

\begin{slide}{Aggregating routes}
  \begin{itemize}
  \item Routers summarise routes themselves when they use
    \emphcolour{classless} routing protocols such as:
    \begin{itemize}
    \item \RIP{}2
    \item \OSPF
    \item \BGP
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Without Route Summarisation}
  \begin{center}
    \includegraphics[width=\slideWidth]{four-routers-no-summarisation}
  \end{center}
\end{slide}

\begin{slide}{With Route Summarisation}
  \begin{center}
    \includegraphics[width=\slideWidth]{four-routers-with-summarisation}
  \end{center}
\end{slide}

\begin{slide}{Explanation}
\begin{itemize}
\item The first diagram shows \emphcolour{all} subnets behind router A
  advertised everywhere
  \begin{itemize}
  \item This is because the routers are unable to summarise the routes
  \end{itemize}
\item The second diagram shows the subnets behind A summarised into
  two routes instead of 5
  \begin{itemize}
  \item The routers must be running a classless routing protocol such
    as \OSPF or \RIP{}2.
  \end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{How the Routes were Summarised}
  \begin{itemize}
  \item 200.200.24.0/24: 24$_{10}$ = 00011000$_{2}$
  \item 200.200.25.0/24: 25$_{10}$ = 00011001$_{2}$
  \item 200.200.26.0/24: 26$_{10}$ = 00011010$_{2}$
  \item 200.200.27.0/24: 27$_{10}$ = 00011011$_{2}$
    \begin{itemize}
    \item So these can be summarised into:
    \item 200.200.24.0/22
    \end{itemize}
  \item 200.200.28.0/24: 28$_{10}$ = 00011100$_{2}$
    \begin{itemize}
    \item This cannot be summarised with the other routes, so it must be
      advertised separately.
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Route Aggregation: \texttt{NetAddr::IP}}
  \begin{itemize}
  \item There is a Perl module for working with IP addresses (of
    course):
  \item \texttt{NetAddr::IP}
  \item Includes the method \texttt{compact()}, which takes a list of networks
    and returns a list of summarised address blocks.
  \item The next slide shows a little program that will aggregate
    address blocks given on the command line or on standard input.
\end{itemize}
\end{slide}

\begin{slide}{\texttt{route-aggregate}}
\begin{verbatim}
#! /usr/bin/perl -w
use NetAddr::IP;
$| = 1;
our ( @ips, @ip );
if ( @ARGV ) {
    @ips = @ARGV
} else {
    @ips = <STDIN>;
}
foreach my $ip ( @ips ) {
    push @ip, NetAddr::IP->new( $ip );
}
my @aggregated = NetAddr::IP::compact( @ip );
print "@aggregated\n";
\end{verbatim}%$
\end{slide}

\tsection{Addressing Scheme}

\begin{slide}{Designing an Addressing Scheme}
  \begin{itemize}
  \item Given one (or two) blocks of addresses, how do we allocate
    addresses to a network involving routers?
  \item Need also to allocate addresses to links between
    routers---these need their own little subnet
  \end{itemize}
\end{slide}

\begin{slide}{Example Problem}
  \begin{itemize}
  \item Given a physical network layout as shown in the figure below
  \item Has 10 subnets (excluding the link Z)
  \item All three routers support \CIDR addressing
  \end{itemize}
  \begin{center}
    \includegraphics[width=\slideWidth]{routing-problem-2}
  \end{center}
\end{slide}

\begin{slide}{Example Problem}
  \begin{itemize}
  \item You are given:
    \begin{itemize}
    \item The information on previous slide
    \item Two address blocks:
      \begin{itemize}
      \item 172.19.0/20
      \item 172.19.128/28
      \end{itemize}
    \end{itemize}
  \item Requirements are:
    \begin{itemize}
    \item Subnets 1 to 8 must each support up to 140 computers
    \item Subnets must be assigned to allow maximum route aggregation
    \item Any unused addresses must be kept in single blocks so that
      they can be used elsewhere or for future expansion
    \end{itemize}
  \end{itemize}
\end{slide}

\renewcommand{\extrarowheight}{0pt}

\begin{slide}{Solution --- Links}
  \begin{itemize}
  \item General strategy: determine the lower and upper limits on each
    subnet.  Allocate networks in the order of smallest to largest.
      
  \item The smallest block of addresses is only suitable for
    allocating to the links, so allocate them first.
  \item Minimum size of each serial link is 4, as $2^{\lceil \log_2 (2
      + 2)\rceil} = 2^{2}$, giving a prefix size of $32 - 2 = 30$,
    i.e., /30.
      
  \item Allocate adjacent subnets to links X and Y, so that router C can
    aggregate routes to them.

    \begin{tabular}[t]{@{}ll@{}}
      \toprule%
      \emph{subnet} & \emph{network}\\
      \midrule%
      subnet X & 172.19.128.0/30 \\
      subnet Y & 172.19.128.4/30 \\
      \bottomrule
    \end{tabular}
    
    \smallskip%
  \end{itemize}
\end{slide}

\begin{slide}{Solution --- Larger Subnets --- 1}
  \begin{itemize}
  \item For each of the larger subnets, minimum size is 256, i.e., a
    /24 subnet
    
  \item $2^8$ is the lowest power of 2 that contains $140 + 2$.
    ($2^{\lceil \log_2 (140 + 2)\rceil} = 2^{8}$; so $\text{prefix
      length} = 32 - 8 = 24$).

  \end{itemize}
\end{slide}  

\begin{slide}{Solution --- Larger Subnets --- 2}
  \begin{itemize}
  \item Let us allocate the lowest 8 /24 blocks from 172.19.0/20:

      \begin{tabular}[t]{@{}ll@{}}
        \toprule%
        \emph{subnet} & \emph{network} \\
        \midrule%
        subnet 1 & 172.19.0.0/24 \\
        subnet 2 & 172.19.1.0/24 \\
        subnet 3 & 172.19.2.0/24 \\
        subnet 4 & 172.19.3.0/24 \\
        subnet 5 & 172.19.4.0/24 \\
        subnet 6 & 172.19.5.0/24 \\
        subnet 7 & 172.19.6.0/24 \\
        subnet 8 & 172.19.7.0/24 \\
        \bottomrule
      \end{tabular}%
      \par\medskip\par
    \item In a tutorial exercise, you will determine what routes each
      router advertises.
    \end{itemize}  
\end{slide}

\tsectionandpart[toc=Gateway Protocols]{Gateway Protocols\\[5ex] Border Gateway
  Protocol --- BGP}

\providecommand*{\EGP}{\acro{EGP}\xspace}
\providecommand*{\MED}{\acro{MED}\xspace}
\providecommand*{\IGP}{\acro{IGP}\xspace}
\providecommand*{\ARPANET}{\acro{ARPANET}\xspace}
\renewcommand*{\AS}{\acro{AS}\xspace}

\begin{slide}{Classes of Routing Protocols}
  \begin{itemize}
  \item Distance Vector or Link-State are two types of routing protocols.
  \item Another way to classify routing protocols is as follows:
  \item Intra-Domain routing:
    \begin{itemize}
    \item routing of packets within the same Autonomous System
      (\emphcolour{AS})
    \item Interior Gateway Protocol \IGP, \RIP2, \OSPF,\,\ldots
    \end{itemize}
  \item Inter-Domain routing:
    \begin{itemize}
    \item Inter-Domain routing is between multiple Autonomous Systems.
    \item Exterior Gateway Protocol \EGP, Border Gateway Protocol
      {\red\BGP}
    \end{itemize}
  \item Autonomous System ({\red{}\AS}) refers to a group of
    routers (i.e. networks) administered by the same organization.
  \item Each {\red{}\AS} is assigned a number.  \AS numbers range from
    1 to 65,535, with 64512 to 65535 reserved for private (internal
    networks) use.
  \end{itemize}
\end{slide}

\begin{slide}{Gateway Protocols}
  \begin{itemize}
  \item Inter-domain and Intra-domain routing protocols are also
    referred as Exterior and Interior routing protocols respectively.
  \item The first widely used exterior gateway protocol is called
    Exterior Gateway Protocol (\EGP), it was designed to communicate
    reachability among the core routers of \ARPANET.
  \item \EGP is more a reachability protocol than a routing protocol,
    it only tests reachability but not makes intelligent routing
    decisions.
  \item \EGP is replaced by the Border Gateway Protocol (\BGP).  The
    current version of \BGP is version 4
    \begin{itemize}
    \item earlier versions don't support \CIDR, so are obsolete
    \end{itemize}
  \end{itemize}
\end{slide}

\tsection{BGP: AS Types}

\begin{slide}{Border Gateway Protocol BGP}
  \begin{itemize}
  \item \BGP is an inter-domain (inter-\AS) routing protocol.  However,
    \BGP can also be used within an \AS.
  \item When used between \AS, \BGP is referred as Exterior \BGP (e\BGP). 
  \item When used within an \AS, \BGP is referred as Interior \BGP (i\BGP).
  \item \BGP is mainly used in core routers in the Internet, for
    connections between Internet Service Providers.  Large networks
    (universities and big enterprises) also use \BGP to connect to
    \ISP{}s.  Within these networks, however, other Interior Gateway
    Protocols (such as \RIP or \OSPF) are used rather than i\BGP.
  \end{itemize}
\end{slide}

\begin{slide}{Single-homed Autonomous Systems}
  \begin{center}
    \includegraphics[width=\slideWidth]{stub-network}
  \end{center}
\end{slide}

\begin{slide}{Single-homed Autonomous Systems}
  \begin{itemize}
  \item Single homed \AS, or \emphcolour{stub \AS}
    \begin{itemize}
    \item An \AS has only one exit point to outside networks.  Quite
      often, a single-homed \AS is referred as a \emphcolour{stub
        network}.
    \end{itemize}
  \item An \ISP can use three different methods to advertise a
    customer's network, a single-homed \AS,
    so that the Internet community can learn about such a network.
    \begin{itemize}
    \item Using static/default routes
    \item Using \IGP, such as \OSPF and \RIP
    \item Using \EGP, such as \BGP
    \end{itemize}
  \item In most cases, simple static routes are used.
  \item \BGP is not commonly used due to the difficulty stub
    networks have with getting a registered \AS number.
  \end{itemize}
\end{slide}

\begin{slide}{Multi-homed Non-transit AS}
  \begin{itemize}
  \item An \AS is a multi-homed system if it has more
    than one exit point to the outside networks.  An \AS
    connected to the Internet can be multi-homed to a single \ISP or
    multiple \ISP{}s.
  \item Non-transit refers to the fact that transit traffic does not
    pass through the \AS.  A non-transit \AS
    would advertise only its own routes to the \ISP{}s to which it
    connects, it would not advertise routes that it learned from one
    \ISP to another.
  \item A multi-homed Non-transit \AS does not really
    need to run \BGP with their \ISP{}s.  Other routing methods can be
    used instead.  However, some \ISP{}s may prefer the customers to use
    \BGP.
  \end{itemize}
\end{slide}

\begin{slide}{Multi-homed Transit AS}
  \begin{center}
    \includegraphics[width=\slideWidth]{multi-homed-transit-as}
  \end{center}
\end{slide}

\begin{slide}{Multi-homed Transit AS}
  \begin{itemize}
  \item A multi-homed transit \AS can be used for transit
    traffic of other autonomous systems.  \BGP can be used internally
    so that multiple border routers in the same \AS can
    share \BGP information.
  \item i\BGP is run inside the \AS.  Routers that
    route i\BGP traffic are \emphcolour{transit routers}.
  \item e\BGP is run between the local and the external \AS{}s.
    Routers on the boundary of an \AS that use e\BGP to exchange
    information with the \ISP are \emphcolour{border} (or
    \emphcolour{edge}) routers.
  \end{itemize}
\end{slide}

\begin{slide}{BGP: to use or not to use}
  \begin{itemize}
  \item If the routing policy of an \AS is consistent
    with the \ISP's policy, it is not
    necessary to use \BGP to exchange routing information with the
    \ISP.  If the \AS and \ISP's policy are
    different, \BGP is preferred.
  \item If the \AS uses different \ISP{}s for redundancy, (or load
    sharing) a combination of static and default routes could be used
    instead of \BGP.
  \item If the \AS uses multiple connections to \ISP{}s
    that are active at the same time, \BGP is preferred.
  \end{itemize}
\end{slide}

\tsectionandpart{BGP Attributes}

\begin{slide}{BGP}
  \begin{itemize}
  \item BPG is designed to be used on the Internet.  Many route
    parameters, called \emphcolour{attributes}, can be used with
    \BGP so that better routing policies are provided.
  \item \BGP supports \CIDR which helps reduce the routing table size.
  \item \BGP packets are carried through \TCP connection.  When two
    neighbor routers wish to exchange \BGP route information, a \TCP
    connection is established first.
  \item \BGP routers do not send periodic updates.  Full routing
    information are exchanged when the \TCP connection is first
    established, afterward, only \emphcolour{changed} routes will be
    advertised.  Also, only the \emph{\blue{}optimal path} (i.e. there
    are alternate paths) to a destination network is advertised
    through routing updates.
  \end{itemize}
\end{slide}

\begin{slide}{BGP Attributes}
  \begin{itemize}
  \item Routes learned via \BGP have associated properties that are
    used to determine the best route to a destination when multiple
    paths exist.  These properties are referred to as \BGP attributes.
  \item The following \BGP attributes can be used to determine the
    best path:
    \begin{itemize}
    \item Weight (Cisco proprietary, highest priority)
    \item Local Preference 
    \item \AS Path
    \item Origin
    \item Multi-Exit Discriminator (lowest priority)
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{BGP Weight Attribute}
  \begin{itemize}
  \item \emphcolour{Weight} is a Cisco-defined attribute that is local
    to a router.  The \emphcolour{weight} attribute is not advertised
    to neighboring routers.
  \item If the router learns about more than one route to the same
    destination, the route with the highest \emphcolour{weight}
    will be preferred.
  \item When there are two routes/paths to a destination, both will be
    maintained in the \BGP routing table.  However, only the route
    with the highest \emphcolour{weight} will be installed in the \IP
    routing table.  That is, when forwarding \IP packets, the route
    with the highest \emphcolour{weight} is used.
  \end{itemize}
\end{slide}

\tsection{Preferring One Link}

\begin{slide}{BGP Local Preference Attribute}
  \begin{itemize}
  \item The \emphcolour{local preference} attribute is used to
    prefer an exit point from the local autonomous system
  \AS.  If there are multiple exit points from the
  \AS, the \emphcolour{local preference}
    attribute is used to select the exit point for a specific route.
  \item For example, two routers (A \& B) connect a local \AS{}100 to
    another \AS{}200, and both routers receive route advertisement for
    a particular network 10.0.0.0/8.  If router A is set a
    \emphcolour{local preference} value of 50 while router B is set a
    value of 55, the route through router B will be used to forward
    traffic from local \AS to the particular network 10.0.0.0/8.
  \item \emphcolour{Weight} attribute is similar to the
    \emphcolour{local preference} attribute in that they are used
      to set an outgoing path.  Their difference is that
    \emphcolour{weight} attribute is local to a router while
    \emphcolour{local preference} attribute is propagated
      throughout the local \AS.
  \end{itemize}
\end{slide}

\begin{slide}{BGP \texttt{LOCAL\_PREF}}
  \begin{center}
    \includegraphics[width=\slideWidth]{bgp-local-pref}
  \end{center}
\end{slide}

\begin{slide}{BGP MED Attribute}
  \begin{itemize}
  \item The \emphcolour{multi-exit discriminator} (\MED) is used to
    suggest an external \AS regarding the preferred
    route into the local \AS that is advertising the
    route.
  \item The external \AS, which receive the \MED{}s, may not take the
    ``suggestion'' and may use other \BGP attributes for route
    selection.
  \item \MED{}s are advertised throughout the local \AS.
  \end{itemize}
\end{slide}

\begin{slide}{BGP \texttt{MULTI\_EXIT\_DISC}}
  \begin{center}
    \includegraphics[width=\slideWidth]{bgp-multi-exit-disc}
  \end{center}
\end{slide}

\begin{slide}{BGP: Selecting one Link}
  \begin{center}
    \includegraphics[width=\slideWidth]{bgp-local-pref-mult-exit-disc}
  \end{center}
\end{slide}


\begin{slide}{BGP AS\_path Attribute}
  \begin{itemize}
  \item When a route advertisement passes through an autonomous
    system, the \AS number is added to an ordered list
    of \AS numbers that the route advertisement has
    traversed.
  \item The \emphcolour{AS\_path} attribute can
    be used to detect routing loops.
    \begin{itemize}
    \item If a router receives a route advertisement with an ordered
      list containing an \AS number the same as the \AS that the router
      belongs to, it ignores the route advertisement.
    \end{itemize}
  \item The \emphcolour{AS\_path} attribute can be used to select the
    better path.
    \begin{itemize}
    \item The route that contains the shortest \emphcolour{AS\_path}
      (i.e. the order list that contains the shortest list of \AS
      numbers) is selected.
    \end{itemize}
  \end{itemize}
\end{slide}

\tsection{BGP Messages}

\begin{slide}{BGP Message Types}
  \begin{itemize}
  \item Four \BGP message types are specified in RFC 1771 (i.e. \BGP
    version 4).
  \item The \emphcolour{Open Message} opens a \BGP communication
    session between peers and is the first message sent by each side
    after a \TCP connection is established.
  \item The \emphcolour{Update Message} is used to provide routing
    updates to other \BGP systems, allowing routers to construct a
    consistent view of the network topology.  Update messages can
    withdraw one or more unfeasible routes from the routing table and
    simultaneously can advertise a route.
  \item The \emphcolour{Notification Message} is sent when error
    condition is detected.  Notifications are used to close an active
    session.
  \item The \emphcolour{Keep-alive Message} notifies \BGP peers that a
    device is active.
  \end{itemize}
\end{slide}

\newcommand*{\scale}{0.73}

\begin{slide}{BGP Packet Formats}
  \begin{itemize}
  \item {\mbox{}\blue{}All \BGP message types use the}
    \emphcolour{basic packet header}\\
  \par\smallskip\par
  \includegraphics[scale=\scale]{bgp-header}
  \item The basic packet header contains:
    \begin{itemize}
    \item a 16-byte \emphcolour{marker} field which contains
      authentication value
    \item a 2-byte \emphcolour{length} field which contains the total
      length of the message
    \item a 1-byte \emphcolour{type} field which specifies the message type
    \item data of variable length, this field carry the upper-layer
      information
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}[toc=Open Message]{Additional Fields: Open Message}
  \begin{itemize}
  \item {\mbox{}\blue{}Open}, {\blue{}update} and
    {\blue{}notification} messages {\green{}have additional fields}, but
    {\blue{}keep-alive messages} use only the {\blue{}basic packet header}.
  \item {\mbox{}\blue{}Additional fields} of the \emphcolour{Open Message} contains:
    \begin{itemize}
    \item \BGP \emphcolour{version number} (i.e., 4)
    \item \emphcolour{AS number} of sender
    \item \emphcolour{hold-time}
    \item \emphcolour{\BGP identifier} of the sender (\IP address)
    \item \emphcolour{optional parameters} such as authentication data.
    \end{itemize}
  \end{itemize}
  \par\medskip\par
  \includegraphics[scale=\scale]{bgp-open-fields}
\end{slide}

\begin{slide}[toc=Update Message]{BGP Additional Fields: Update Message}
  \begin{itemize}
  \item {\mbox{}\blue{}Additional fields} of \emphcolour{Update
      Message} contains:
    \begin{itemize}
    \item \emphcolour{Withdrawn routes}: a list of IP address prefixes for the
      routes being withdrawn
    \item \emphcolour{Network layer reachability} information: a list of \IP
      address prefixes (e.g. 10.1.1.0/24) for the advertised routes
    \item \emphcolour{Path attributes} (such as origin, \AS{}\_path,
      \MED, \texttt{LOCAL\_PREF},\,\ldots) that describe the characteristics of
      the advertised path.
    \item \emphcolour{Unfeasible routes length}, i.e., length of
    withdrawn routes field
    \item \emphcolour{Total path attribute length}, i.e., length of
    the path attributes field
    \end{itemize}
  \end{itemize}
  \par\medskip\par
  \includegraphics[scale=\scale]{bgp-update-fields}
\end{slide}


\begin{slide}[toc=Notification Message]%
  {BGP Additional Fields: Notification Message}
  \begin{itemize}
  \item {\mbox{}\blue{}Additional fields} of \emphcolour{Notification
      Message} contains:
    \begin{itemize}
    \item \emphcolour{Error code} that indicates the type of error that occurred.
    \item Error \emphcolour{sub code}
    \item \emphcolour{error data}.
    \end{itemize}
  \end{itemize}
  \par\medskip\par
  \includegraphics[scale=\scale]{bgp-notification-fields}
\end{slide}

\end{document}