\documentclass{ictlab}
%\documentclass[solutions]{ictlab}

% Copyright (c) 2003 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.11 $

\usepackage{verbatim,key,alltt,amsmath,amstext,answer2,biganswerbox}
\usepackage[hang,bf,nooneline]{caption2}
\ifx\pdftexversion\undefined \else
  \usepackage[pdfpagemode=None,pdfauthor={Nick Urbanik}]{hyperref}
\fi

\newcommand*{\labTitle}{CIDR, Route Summarisation and Routing}
\providecommand*{\BGP}{\acro{BGP}\xspace}
%% \providecommand*{\SNMP}{\acro{SNMP}\xspace}
%% \providecommand*{\MIB}{\acro{MIB}\xspace}
%% \providecommand*{\ID}{\acro{ID}\xspace}
%% \providecommand*{\OID}{\acro{OID}\xspace}
%% \providecommand*{\FAQ}{\acro{FAQ}\xspace}
%% \providecommand*{\RPM}{\acro{RPM}\xspace}
%% \providecommand*{\MRTG}{\acro{MRTG}\xspace}
%% \providecommand*{\CPAN}{\acro{CPAN}\xspace}
%% \providecommand*{\RRD}{\acro{RRD}\xspace}
%% \providecommand*{\URL}{\acro{URL}\xspace}
%% \providecommand*{\DN}{\acro{DN}\xspace}
%% \providecommand*{\LDIF}{\acro{LDIF}\xspace}

\renewcommand*{\floatpagefraction}{0.75} % default is .5, to increase
% density.
\renewcommand*{\bottomfraction}{0.6} % default is 0.3
\renewcommand*{\topfraction}{0.85} % default is 0.7
\renewcommand*{\textfraction}{0.1} % default is 0.2

\newlength{\prefixlen}

\begin{document}

\section{Examples}
\begin{enumerate}
\item Aggregate the following set of 4 24-bit network addresses to
  the highest degree possible.

\noindent%
\begin{tabular}[c]{@{}c@{}}
172.47.30.0/24\\
172.47.31.0/24\\
172.47.32.0/24\\
172.47.33.0/24
\end{tabular}

\vspace{2ex}
             
Here is how to do it:
    
List each address in binary format and determine the common prefix for
all of the addresses:

\settowidth{\prefixlen}{10101100.00101111.0001111}
\noindent%
\begin{tabular}[c]{@{}cl|l@{}}
        & \makebox[\prefixlen][c]{\vline$\leftarrow$\dotfill
          first prefix\dotfill$\rightarrow$} & \\
  172.47.30.0/24 & 10101100.00101111.0001111&\textbf{0}.00000000\\
  172.47.31.0/24 & 10101100.00101111.0001111&\textbf{1}.00000000\\
  \hline
  172.47.32.0/24 & 10101100.00101111.0010000&\textbf{0}.00000000\\
  172.47.33.0/24 & 10101100.00101111.0010000&\textbf{1}.00000000\\
        & \makebox[\prefixlen][c]{\vline$\leftarrow$\dotfill
          second prefix\dotfill$\rightarrow$} &
\end{tabular}

Note that this set of 4 24-bit blocks cannot be summarised as a
single 22-bit block.

\noindent%
\begin{tabular}[c]{@{}cl@{}}
  172.47.30.0/23 & 10101100.00101111.0001111\textbf{0}.00000000\\
  172.47.32.0/23 & 10101100.00101111.0010000\textbf{0}.00000000
\end{tabular}

So the two 23-bit blocks are: 

\noindent%
\begin{tabular}[c]{@{}c@{}}
  172.47.30.0/23\\
  172.47.32.0/23\\
\end{tabular}

Note: it looks as if there could be an 18-bit prefix in common; is it
possible to choose 172.47.30.0/18?  No, because this includes
$2^{32-18=14}= 16384$, while there are only $2^{8}\times 4=1024$
addresses in the original four blocks.  The aim is to include only our
addresses, not those that belong to others.


\paragraph{General Approach:}

\begin{enumerate}
\item Determine which octet the prefix will end in.  Here, we have
  $2^{8} \times 4 = 1024$ addresses, so we have the prefix ending in
  the third octet.
\item Convert that octet only from the first and last address, to
  binary.  So here, we convert $30\dec \to 00011110\bin$ and $33\dec
  \to 00100001\bin$.
\item Do these binary numbers have a common prefix, to the right of
  which all bits count from 000\ldots000 to 111\ldots111?  Well, in
  this case, no, so\ldots
\item Find the power of two over which the third octet counts.  Here,
  the power of 2 is $32=2^5$.  Convert the value before and after the
  power of 2 to binary: $2^{5} - 1 = 00011111\bin$, and $2^5 =
  00100000\bin$.
\item Now compare the first $30\dec \to 00011110\bin$ with $2^{5} - 1
  = 00011111\bin$, and see if we have a common prefix, to the right of
  which all bits count from 000\ldots000 to 111\ldots111.  Well, yes
  we do!  It is 0001111\,\vline\,$x$.
\item Now compare $2^5 = 00100000\bin$ with $33\dec \to
  00100001\bin$.  Can we see a common prefix, with bits to the right
  counting from all 0's to all 1's?  Yes!  It is 0010000\,\vline\,$x$.
\end{enumerate}

%\clearpage
\item Aggregate the following set of (64) 24-bit network addresses to
  the highest degree possible.

\noindent%
\begin{tabular}[c]{@{}c@{}}
  202.1.96.0/24\\
  202.1.97.0/24\\
  202.1.98.0/24\\
  $\vdots$ \\
  202.1.126.0/24\\
  202.1.127.0/24\\
  202.1.128.0/24\\
  202.1.129.0/24\\
  $\vdots$ \\
  202.1.158.0/24 \\
  202.1.159.0/24
\end{tabular}

\vspace{2ex}
             
Here is how to do it:
    
List each address in binary format and determine the common prefix for
all of the addresses:

\settowidth{\prefixlen}{11001010.00000001.011}

\noindent%
\begin{tabular}[c]{@{}cl@{}}
  & \makebox[\prefixlen][c]{\vline$\leftarrow$\dotfill
    first prefix\dotfill$\rightarrow$\vline}\\
  202.1.96.0/24  & 11001010.00000001.011\textbf{00000}.00000000\\
  202.1.97.0/24  & 11001010.00000001.011\textbf{00001}.00000000\\
  202.1.98.0/24  & 11001010.00000001.011\textbf{00010}.00000000\\
  $\vdots$ &             $\vdots$ \\
  202.1.126.0/24 & 11001010.00000001.011\textbf{11110}.00000000\\
  202.1.127.0/24 & 11001010.00000001.011\textbf{11111}.00000000\\
  \hline%
  202.1.128.0/24 & 11001010.00000001.100\textbf{00000}.00000000\\
  202.1.129.0/24 & 11001010.00000001.100\textbf{00001}.00000000\\
  $\vdots$ &             $\vdots$ \\
  202.1.158.0/24 & 11001010.00000001.100\textbf{11110}.00000000\\
  202.1.159.0/24 & 11001010.00000001.100\textbf{11111}.00000000\\
  & \makebox[\prefixlen][c]{\vline$\leftarrow$\dotfill
    second prefix\dotfill$\rightarrow$\vline}
\end{tabular}

Note that this set of 64 24-bit blocks cannot be summarised as a
single 18-bit block

\noindent%
\begin{tabular}[c]{@{}cl@{}}
  202.1.96.0/19 & 11001010.00000001.\textbf{011}00000.00000000 \\
  202.1.128.0/19  & 11001010.00000001.\textbf{100}00000.00000000
\end{tabular}

So the two 19-bit blocks are: 

\noindent%
\begin{tabular}[c]{@{}c@{}}
  202.1.96.0/19\\
  202.1.128.0/19 
\end{tabular}

Could the answer be 202.1.96.0/16?  No, because that includes $2^{16}=
65536$ different addresses, not just the $2^{8} \times 64= 16384$
addresses that we are taking care of.
\end{enumerate}

\paragraph{General Approach Applied to This Problem:}

\begin{enumerate}
\item Determine which octet the prefix will end in.  Here, we have
  $2^{8} \times 64 = 16{,}384$ addresses, so we have the prefix ending
  in the third octet.
\item Convert that octet only from the first and last address, to
  binary.  So here, we convert $96\dec \to 0110\,0000\bin$ and $159\dec
  \to 1001\,1111\bin$.
\item Do these binary numbers have a common prefix, to the right of
  which all bits count from 000\ldots000 to 111\ldots111?  Well, in
  this case, no, so\ldots
\item Find the power of two over which the third octet counts.  Here,
  the power of 2 is $128=7^5$.  Convert the value before and after the
  power of 2 to binary: $2^{7} - 1 = 0111\,1111\bin$, and $2^7 =
  1000\,0000\bin$.
\item Now compare the third octet from the first address block,
  $96\dec \to 0110\,0000\bin$ with $2^{7} - 1 = 0111\,1111\bin$, and
  see if we have a common prefix, to the right of which all bits count
  from 000\ldots000 to 111\ldots111.  Well, yes we do!  It is
  011\,\vline\,$xxxxx$.
\item Now compare $2^7 = 1000\,0000\bin$ with $159\dec
  \to 1001\,1111\bin$.  Can we see a common prefix, with bits to the right
  counting from all 0's to all 1's?  Yes!  It is 100\,\vline\,$xxxxx$.
\end{enumerate}


\paragraph{Some Other Points:}
\begin{itemize}
\item The prefixes do not all have to be the same size.
\item In the two examples given here, we only needed to convert four
  eight-bit numbers to binary, \emph{not} sixty-four 32-bit numbers.
\item You may have to continue to divide these groups of addresses
  until you find a single address block.  In other words, you may need
  to apply the above steps recursively until you find all the address
  blocks.
\item If you want to see a computer algorithm for doing this, see the
  \texttt{compact()} method in the Perl module NetAddr::IP, from
  \CPAN.
\item You can always make a simple sanity check by calculating the
  number of host addresses in the input, and making sure that it
  matches the number in the summarised output.
\end{itemize}

%\clearpage
\section{Questions}
\label{sec:procedure}
\begin{enumerate}
\item 
  \begin{enumerate}
  \item \sloppypar How many 24-bit network blocks are available within
    the \CIDR block 200.56.168.0/21?
    
    (Hint: how many times does $2^{32-24}$ divide into $2^{32-21}$?
    Hmm, $2^{32-21 - (32-24)} = 2^{24-21}$)\answerbox{8}
  
  \item List them.

    \begin{biganswerbox}[6cm]%
      \begin{solution}%
      The last three bits of the third byte select each of the eight
      subnets.  We just count these bits from 0 to 7, giving us each
      of the 24-bit network blocks:

      \noindent%
      \begin{tabular}[c]{@{}lc@{}}
        11001000.00111000.10101$xxx$.$xxxxxxxx$ &
                          200.56.168.0/21\\[1ex]
                          \multicolumn{2}{@{}l}{which can give us:}\\
        11001000.00111000.10101\textbf{\textit{000}}.$xxxxxxxx$ & 200.56.168.0/24\\
        11001000.00111000.10101\textbf{\textit{001}}.$xxxxxxxx$ & 200.56.169.0/24\\
        11001000.00111000.10101\textbf{\textit{010}}.$xxxxxxxx$ & 200.56.170.0/24\\
        11001000.00111000.10101\textbf{\textit{011}}.$xxxxxxxx$ & 200.56.171.0/24\\
        11001000.00111000.10101\textbf{\textit{100}}.$xxxxxxxx$ & 200.56.172.0/24\\
        11001000.00111000.10101\textbf{\textit{101}}.$xxxxxxxx$ & 200.56.173.0/24\\
        11001000.00111000.10101\textbf{\textit{110}}.$xxxxxxxx$ & 200.56.174.0/24\\
        11001000.00111000.10101\textbf{\textit{111}}.$xxxxxxxx$ & 200.56.175.0/24
      \end{tabular}
      \end{solution}
    \end{biganswerbox}
%% %% \begin{verbatim}
%% %% Net #0: 11001000.00111000.10101  000 .xxxxxxxx 200.56.168.0
%% %% Net #1: 11001000.00111000.10101  001 .xxxxxxxx 200.56.169.0
%% %% Net #2: 11001000.00111000.10101  010 .xxxxxxxx 200.56.170.0
%% %% Net #3: 11001000.00111000.10101  011 .xxxxxxxx 200.56.171.0
%% %% Net #4: 11001000.00111000.10101  100 .xxxxxxxx 200.56.172.0
%% %% Net #5: 11001000.00111000.10101  101 .xxxxxxxx 200.56.173.0
%% %% Net #6: 11001000.00111000.10101  110 .xxxxxxxx 200.56.174.0
%% %% Net #7: 11001000.00111000.10101  111 .xxxxxxxx 200.56.175.0
%% %% \end{verbatim}%
%% %% }
%% %}
\end{enumerate}

\item Aggregate the following 24-bit blocks into as few blocks as
  possible:

  \begin{tabular}[c]{@{}c@{}}
    212.56.132.0/24\\
    212.56.133.0/24\\
    212.56.134.0/24\\
    212.56.135.0/24\\
  \end{tabular}

(Hint: determine the prefix common to them all).
\begin{biganswerbox}[0.8cm]%
  \begin{solution}%
    212.56.132.0/22

    So how did I get that answer?  All the action happens in the third
    byte.  Let's look at the binary value of it:

    \smallskip

    \begin{tabular}[t]{@{}ll@{}}
      132 & 100001\textbf{\textit{00}} \\
      133 & 100001\textbf{\textit{01}} \\
      134 & 100001\textbf{\textit{10}} \\
      135 & 100001\textbf{\textit{11}}
    \end{tabular}

    \smallskip

    You notice that the first 22 bits (first two bytes + the first 6
    bits of the third byte) are all the same, while the bits to the
    right of the prefix go through all possible values of all zeros to
    all ones.
  \end{solution}
\end{biganswerbox}

%% \noindent%
%% \mbox{}\answerbox[\linewidth]{212.56.132.0/22}

\item Aggregate the following 24-bit blocks into as few blocks as
  possible:

  \begin{tabular}[c]{@{}c@{}}
    212.56.146.0/24\\
    212.56.147.0/24\\
    212.56.148.0/24\\
    212.56.149.0/24
  \end{tabular}

  \begin{biganswerbox}[6cm]%
    \begin{solution}%
      212.56.146.0/23 and 212.56.148.0/23
      
      To aggregate into one block, the last two bits in the third
      octet must count from 00 to 11.  Let's see what the third octet
      is in binary:

      \medskip

      \begin{tabular}[t]{@{}cc@{}}
        146 & 10010010 \\
        147 & 10010011 \\ \hline
        148 & 10010100 \\
        149 & 10010101 \\
      \end{tabular}

      \bigskip
      
      So we see that we cannot find a common /22 prefix that includes
      all possible values; we can only have two /23 prefixes here:

      \settowidth{\prefixlen}{11010100.00111000.1001001}
      \noindent%
      \begin{tabular}[c]{@{}cl@{}}
        212.56.146.0/24  &
        11010100.00111000.1001001\vline\textbf{\textit{0}}.00000000\\
        212.56.147.0/24  &
        11010100.00111000.1001001\vline\textbf{\textit{1}}.00000000\\
        \hline
        212.56.148.0/24  &
        11010100.00111000.1001010\vline\textbf{\textit{0}}.00000000\\
        212.56.149.0/24  &
        11010100.00111000.1001010\vline\textbf{\textit{1}}.00000000\\
        %& \makebox[\prefixlen][c]{\vline$@<<{}<$%
        %  prefix$@>>{}>$\vline}
        & \makebox[\prefixlen][c]{\vline$\leftarrow$\dotfill
          prefix\dotfill$\rightarrow$\vline}
      \end{tabular}

      \bigskip

      The prefixes are 212.56.146.0/23 and 212.56.148.0/23
    \end{solution}
  \end{biganswerbox}


\clearpage
\item 
Here is a quote from an email:
\begin{explanation}
I'm thinking if we allocate, say 48 groups of 8-bit address space to
you, let's say, from 172.19.16.x -- 172.19.63.x, would it solve your
problem~?  The point is, if you agree on such an arrangement, we don't
have to ask for outside help than CC/IVE(TY) as 172.x.x.x are solely
allocated to us.  What's your opinion~?
\end{explanation}

Aggregate the following 24-bit blocks into as few blocks as
  possible:

  \begin{tabular}[c]{@{}c@{}}
    172.19.16.0/24\\
    172.19.17.0/24\\
    172.19.18.0/24\\
    $\vdots$\\
    172.19.62.0/24\\
    172.19.63.0/24
  \end{tabular}

  \begin{biganswerbox}[15cm]%
    \begin{solution}%
      There are many ways of looking at this problem.  Consider the
      number of addresses there are: $(63 - 16 + 1) \times 2^8 = 48
      \times 256 = 12288$.  Now what power of two can include those
      addresses? $\log_2 12288 \approx 13.58$, i.e., no power of two
      can include all those addresses without including other
      addresses that are not part of this block.  A single \CIDR
      address block always contains a number of addresses that is
      exactly a power of 2.

      Okay, let's look at the third octet.

      \noindent%
%% \begin{tabular}[c]{@{}cr@{.}c@{.}c|>{\bfseries\itshape}l@{.}l}
%%   172.19.16.0/24  & 10101100 & 00010011 & 0001&0000 &
%%             $xxxxxxxx$ \\
%%   172.19.17.0/24  & 10101100 & 00010011 & 0001&0001 &
%%             $xxxxxxxx$ \\
%%              $\vdots$ & \multicolumn{5}{c}{$\vdots$} \\
%%   172.19.31.0/24  & 10101100 & 00010011 & 0001&1111 &
%%             $xxxxxxxx$ \\ \hline
%%   172.19.32.0/24  & 10101100 & 00010011 & 001&00000 &
%%             $xxxxxxxx$ \\
%%              $\vdots$ & \multicolumn{5}{c}{$\vdots$} \\
%%   172.19.63.0/24  & 10101100 & 00010011 & 001&11111 &
%%             $xxxxxxxx$
%%           \end{tabular}

      \settowidth{\prefixlen}{10101100.00010011.0001}

      \begin{tabular}[c]{@{}cl@{}}
        & \makebox[\prefixlen][c]{\vline$\leftarrow$\dotfill
          first prefix\dotfill$\rightarrow$\vline} \\
        172.19.16.0/24  &
        10101100.00010011.0001\vline\textbf{\textit{0000}}.$xxxxxxxx$ \\
        172.19.17.0/24  &
        10101100.00010011.0001\vline\textbf{\textit{0001}}.$xxxxxxxx$ \\
        $\vdots$ & \multicolumn{1}{c}{$\vdots$} \\
        172.19.31.0/24  &
        10101100.00010011.0001\vline\textbf{\textit{1111}}.$xxxxxxxx$ \\
         \hline%
        172.19.32.0/24  &
        10101100.00010011.001\vline\textbf{\textit{00000}}.$xxxxxxxx$ \\
        $\vdots$ & \multicolumn{1}{c}{$\vdots$} \\
        172.19.63.0/24  &
        10101100.00010011.001\vline\textbf{\textit{11111}}.$xxxxxxxx$ \\
        & \settowidth{\prefixlen}{10101100.00010011.001}%
        \makebox[\prefixlen][c]{\vline$\leftarrow$\dotfill
          second prefix\dotfill$\rightarrow$\vline} \\
      \end{tabular}

      \vspace{1ex}

      Note that the prefix is the bits that are shown before the small
      vertical bar on each address.  The bits to the right of the
      prefix must include the entire possible range of bits; the bits
      shown in \textbf{\textit{bold italic}} must range from all zeros to
      all ones, otherwise if we use this prefix, we would be including
      other addresses that we may not own.

      Of course, within one \CIDR address block, the prefix is common.
      
      The 16 address blocks above the horizontal line can be aggregated
      into the \CIDR address block 172.19.16.0/20, while the 32
      address blocks below the hoizontal line can be aggregated into
      the \CIDR address block 172.19.32.0/19.

      Note that I use the terms ``agreggate'' and ``summarise'' to
      mean the same thing.
    \end{solution}
  \end{biganswerbox}
\end{enumerate}

\subsection{Routers and Address Allocation}
\label{sec:routers-and-address-allocation}
\setlength{\extrarowheight}{1pt}

\begin{figure}[htb]
  \centering%
  \bigskip%
  \includegraphics[width=0.7\linewidth]{routing-problem-2}
  \caption{The routing problem from the lecture.}
  \label{fig:routing-problem-2}
\end{figure}
\begin{enumerate}
\item In the example problem given in the lecture (see
  figure~\vref{fig:routing-problem-2}), the addresses were allocated,
  but the routes advertised by each router were not determined.  Using
  the addresses given in the lecture, what routes does Router~A
  advertise at X, and Router~B advertise at Y, and Router~C advertise
  at Z?
  \begin{biganswerbox}[7cm]%
    \begin{solution}%
      Since Router~A has 5 subnets:

      \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 \\
        \bottomrule
      \end{tabular}

      \medskip

      we summarise these into the following routes router~A advertises
      at X:

      \begin{tabular}[t]{@{}l@{}}
        172.19.0.0/22 \\
        172.19.4.0/24
      \end{tabular}

      \bigskip
      
      The subnets behind Router~B summarise from

      \begin{tabular}[t]{@{}ll@{}}
        \toprule%
        \emph{subnet} & \emph{network} \\
        \midrule%
        subnet 6 & 172.19.5.0/24 \\
        subnet 7 & 172.19.6.0/24 \\
        subnet 8 & 172.19.7.0/24 \\
        \bottomrule
      \end{tabular}

      \medskip
      
      to the following routes router~B advertises at Y:

      \begin{tabular}[t]{@{}l@{}}
        172.19.6.0/23\\
        172.19.5.0/24
      \end{tabular}

      \bigskip
      
      Router~C aggregates all these together with the routers for the
      small subnets for the two links, and advertises this at Z:


      \begin{tabular}[t]{@{}l@{}}
        172.19.0.0/21\\
        172.19.128.0/29
      \end{tabular}
    \end{solution}
  \end{biganswerbox}


  \begin{figure}[htb]
    \centering%
    \includegraphics[width=0.8\linewidth]{routing-question-1}
    \caption{A network with five routers and fourteen subnets.}
    \label{fig:routing-question-1}
  \end{figure}
\item Figure~\vref{fig:routing-question-1} shows a network with 5
  routers and 14 subnets.  You may select \IP addresses from the two
  blocks of addresses 172.12.0.0/19 and 192.168.0.0/27.  You must
  leave at least one quarter of these addresses available for other
  purposes.  The requirements are that each of subnets 1, 2,\ldots, 8
  must support up to 128 computers, while subnets 9 and 10 must each
  support up to 520 computers.
  \begin{enumerate}
  \item Allocate a suitable block of addresses to each of the fourteen
    subnets that will allow maximum route aggregation.  (Do not
    include link Z).
    \begin{biganswerbox}[7cm]%
      \begin{solution}%
        General strategy: determine the lower and upper limits on each
        subnet.

        Let's start with the serial links between the routers, which
        each need only two addresses in each link.  These should come
        from the smaller address block 192.168.0.0/27.  The minimum
        size of the required subnets is 4 addresses, since the first
        address is the network address, and the last is the broadcast
        address.  So the lowest power of two that includes these
        addresses is 2, since $2^2=2+2$, so we need a $32-2=30$ bit
        netmask for the links.  Let's allocate these addresses so that
        the routes from the links X and W can be aggregated by router
        D.  So here is our allocation of addresses:

        \smallskip

        \begin{tabular}[t]{@{}ll@{}}
          \toprule%
          \emph{subnet} & \emph{network} \\
          \midrule%
          subnet X & 192.168.0.0/30 \\
          subnet W & 192.168.0.4/30 \\
          subnet V & 192.168.0.8/30 \\
          subnet Y & 192.168.0.12/30 \\
          \bottomrule
        \end{tabular}

        \bigskip
        
        The minimum size of each of the first 8 subnets is 256, i.e.,
        a /24 subnet, as $2^8$ is the lowest power of 2 that contains
        $128 + 2$.
        
        Let us allocate the lowest 8 /24 blocks:

        \begin{tabular}[t]{@{}ll@{}}
          \toprule%
          \emph{subnet} & \emph{network} \\
          \midrule%
          subnet 1 & 172.12.0.0/24 \\
          subnet 2 & 172.12.1.0/24 \\
          subnet 3 & 172.12.2.0/24 \\
          subnet 4 & 172.12.3.0/24 \\
          subnet 5 & 172.12.4.0/24 \\
          subnet 6 & 172.12.5.0/24 \\
          subnet 7 & 172.12.6.0/24 \\
          subnet 8 & 172.12.7.0/24 \\
          \bottomrule
        \end{tabular}
        
        \bigskip
    
        The minimum size of subnets 9 and 10 is $2^{10} = 1024$, since
        $2^{\lceil \log_2 520 \rceil} = 2^{10}$, giving a subnet size
        of /22.
        
        Let us allocate the next lowest 2 /22 blocks:

        \begin{tabular}[t]{@{}ll@{}}
          \toprule%
          \emph{subnet} & \emph{network} \\
          \midrule%
          subnet 9 & 172.12.8.0/22 \\
          subnet 10 & 172.12.12.0/22 \\
          \bottomrule
        \end{tabular}
        
        \bigskip
    
        This would use only half of the available addresses.
      \end{solution}
    \end{biganswerbox}
    
  \item \label{que:no-summarisation}Given your selection in the
    previous part, with route summarisation \emph{disabled} on all the
    routers, list the routes that would be advertised by router A at
    X, by router B at W, by router C at V, by router D at Y, and by
    router E at Z\@.
    \begin{biganswerbox}[15cm]%
      \begin{solution}%
        \emph{Without} route summarisation, router A will advertise
        one route for each of its five subnets:

        \begin{tabular}[t]{@{}l@{}}
          172.12.0.0/24 \\
          172.12.1.0/24 \\
          172.12.2.0/24 \\
          172.12.3.0/24 \\
          172.12.4.0/24
        \end{tabular}
    
        \bigskip
    
        and router B will advertise one route for each of \emph{its}
        three subnets:

        \begin{tabular}[t]{@{}l@{}}
          172.12.5.0/24 \\
          172.12.6.0/24 \\
          172.12.7.0/24
        \end{tabular}

        \bigskip
    
        Router C will advertise one route for each of its two subnets:
    
        \begin{tabular}[t]{@{}l@{}}
          172.12.8.0/22 \\
          172.12.12.0/22
        \end{tabular}
        
        \bigskip
    
        Router D will advertise one route for each of the eight
        subnets behind routers A and B, and the one each for each of
        the links X and W:

        \begin{tabular}[t]{@{}l@{}}
          172.12.0.0/24 \\
          172.12.1.0/24 \\
          172.12.2.0/24 \\
          172.12.3.0/24 \\
          172.12.4.0/24 \\
          172.12.5.0/24 \\
          172.12.6.0/24 \\
          172.12.7.0/24 \\
          192.168.0.0/30 \\
          192.168.0.4/30
        \end{tabular}
    
        \bigskip
    
        Finally router E will advertise one route for each of the ten
        subnets behind routers A, B and C, and one route for each of
        the subnets V, W, X, Y:

        \begin{tabular}[t]{@{}ll@{}}
          172.12.0.0/24 & 172.12.7.0/24 \\
          172.12.1.0/24 & 172.12.8.0/22 \\
          172.12.2.0/24 & 172.12.12.0/22 \\
          172.12.3.0/24 & 192.168.0.0/30 \\
          172.12.4.0/24 & 192.168.0.4/30 \\
          172.12.5.0/24 & 192.168.0.8/30 \\
          172.12.6.0/24 & 192.168.0.12/30  
        \end{tabular}
      \end{solution}
    \end{biganswerbox}

  \item What would be a necessary requirement for the routers to
    support route summarisation?

    \begin{biganswerbox}[1cm]%
      \begin{solution}%
        The routers should be running a classless routing protocol,
        such as \OSPF, \RIP{}2 or \BGP.
      \end{solution}
    \end{biganswerbox}

  \item Repeat part~\ref{que:no-summarisation}, but for the case where
    route summarisation is enabled on all routers.
    \begin{biganswerbox}[6cm]%
      \begin{solution}%
        For router~A, the first four routes will be aggregated
        (summarised), so there will be two routes advertised:

        \begin{tabular}[t]{@{}l@{}}
          172.12.0.0/22 \\
          172.12.4.0/24
        \end{tabular}
        
        \bigskip
    
        Router B will summarise the last two routes:

        \begin{tabular}[t]{@{}l@{}}
          172.12.5.0/24 \\
          172.12.6.0/23
        \end{tabular}
    
        Router C will summarise both routes into one:

        \begin{tabular}[t]{@{}l@{}}
          172.12.8.0/21
        \end{tabular}
    
        \bigskip
    
        Router D will summarise the two routes from router A and the
        two routes from router B into one route, and will sumarise the
        routes to links W and X into one route:

        \begin{tabular}[t]{@{}l@{}}
          172.12.0.0/21 \\
          192.168.0.0/29
        \end{tabular}

        \bigskip
    
        Router E will aggregate the route from router C with the two routes
        from router D, and the routes to links V and Y into two routes:

        \begin{tabular}[t]{@{}l@{}}
          172.12.0.0/20 \\
          192.168.0.0/28
        \end{tabular}
      \end{solution}
    \end{biganswerbox}
  \end{enumerate}
\end{enumerate}
\end{document}
