\documentclass{article}
\input{../6829-preamble}

\renewcommand{\theproblem}{\arabic{problem}}
\renewcommand{\thesubproblem}{\arabic{subproblem}}
\renewcommand{\thesubsubproblem}{\alph{subsubproblem}}

\newcommand{\asn}[1]{AS \#\texttt{#1}}

% Scruntch lists and bibliography
\let \olditemize = \itemize
\renewcommand{\itemize}{\olditemize{}\itemsep=-\parskip}
\let \oldenumerate = \enumerate
\renewcommand{\enumerate}{\oldenumerate{}\itemsep=-\parskip}
\let \oldlist = \list
\renewcommand{\list}[2]{\oldlist{#1}{#2}\itemsep=-\parskip}

\sloppy

\begin{document}
\psetnum{2}
\date{2005/09/27}
\collab{Collaborators: $\set{\mathtt{amdragon}}$}

\newcommand{\Pa}{\ensuremath{\mathsf{P1}}}
\newcommand{\Pb}{\ensuremath{\mathsf{P2}}}
\begin{pset}
  \begin{problem}
    \begin{subproblem}
      Consider a full mesh. \Pa{} is satisfied: every router
      advertises to every other router the best routes it sees from
      eBGP, so every router sees the best routes from each eBGP
      router, and hence can choose the best route. \Pb{} is satisfied:
      we assume that the paths learned via eBGP are loop-free. The IGP
      shortest-paths are necessarily also loop-free. Since iBGP does
      not readvertise iBGP-learned paths to other routers, every
      router's path to any destination will consist of an IGP path to
      a route learned by eBGP, both components of which are loop-free.
    \end{subproblem}

    \begin{subproblem}
      This configuration violates \Pa{} and \Pb{}. \textsf{C1} learns
      a route to \textsf{d} via \textsf{R1}, and \textsf{C2} learns a
      route of the same cost to \textsf{d} via \textsf{R2}. However,
      \textsf{C1}'s shortest path to \textsf{R1} is via \textsf{C2}
      (cost 3 rather than 5), and similarly \textsf{C2}'s shortest
      path to \textsf{R2} is via \textsf{C1}. So if \textsf{C1} tries
      to send a packet to \textsf{d}, it will send it to
      \textsf{C2}. If \textsf{C1} had complete knowledge of eBGP
      routes, it would choose to send it to \textsf{R2} to forward to
      \textsf{d} (which has cost 2 rather than 3). So \Pa{} is
      violated. Moreover, when it forwards the packet to \textsf{C2},
      \textsf{C2} will forward it back to \textsf{C1}, creating a
      routing loop, since its best route to \textsf{d} is via
      \textsf{C1} and \textsf{R2}. So \Pb{} is violated.
    \end{subproblem}
    
    \begin{subproblem}
      In this case, the reflectors will forward routes to \textsf{d}
      via both \textsf{R1} and \textsf{R2} to their clients. So
      \textsf{R1} and \textsf{R2} will choose the direct routes,
      \textsf{C1} will choose the optimal route of forwarding to
      \textsf{R2}, and \textsf{C2} will forward to \textsf{R1}. This
      is optimal and loop-free, so \Pa{} and \Pb{} are satisfied.
    \end{subproblem}

    \begin{subproblem}
      If the iBGP configuration satisfies this property, then every
      router $A$ will know about the best routes from every egress
      router $B$: in cases (a), (b), and (c), $A$ learns the route
      directly from $B$, and in case (d), $B$ sends the route to the
      reflector which advertises it to $A$. So $A$ will learn the best
      routes from every egress router $B$, and choose the best of
      these, satisfying \Pa. \Pb is satisfied because $A$ will forward
      the packet along the shortest path to some egress router
      $B$. Because the iBGP configuration satisfies this property, the
      next hop router will also know the best route, and so the
      distance to the egress router is always decreasing. This
      progress condition ensures that forwarding loops are not
      possible, satisfying \Pb.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      \begin{subsubproblem}
        MIT is \asn{3}.
      \end{subsubproblem}

      \begin{subsubproblem}
        The best next hop is \texttt{4.68.0.243}; the router knows how
        to reach this IP via an IGP-discovered route.
      \end{subsubproblem}

      \begin{subsubproblem}
        A packet needs to travel through one AS (\asn{3356}) to
        reach MIT.
      \end{subsubproblem}

      \begin{subsubproblem}
        A traceroute from MIT to route-views follows:
\begin{verbatim}
traceroute to route-views.oregon-ix.net (128.223.60.103), 64 hops max, 40 byte packets
 1  wireless.kalgan.csail.mit.edu (128.30.4.2)  3.843 ms  2.533 ms  2.112 ms
 2  kalgan.trantor.csail.mit.edu (128.30.0.245)  3.791 ms  1.507 ms  9.202 ms
 3  b24-rtr-2-csail.mit.edu (18.4.7.1)  1.599 ms  3.370 ms  1.668 ms
 4  external-rtr-1-backbone.mit.edu (18.168.0.18)  13.945 ms  5.727 ms  1.914 ms
 5  external-rtr-2-backbone.mit.edu (18.168.0.27)  1.776 ms  2.975 ms  8.062 ms
 6  nox230gw1-vl-526-nox-mit.nox.org (192.5.89.89)  3.644 ms  10.391 ms  9.200 ms
 7  nox230gw1-peer-nox-nox-192-5-89-10.nox.org (192.5.89.10)  7.672 ms  32.683 ms  12.576 ms
 8  chinng-nycmng.abilene.ucaid.edu (198.32.8.82)  42.102 ms  29.618 ms  27.834 ms
 9  iplsng-chinng.abilene.ucaid.edu (198.32.8.77)  235.201 ms  251.583 ms  238.747 ms
10  kscyng-iplsng.abilene.ucaid.edu (198.32.8.81)  44.770 ms  44.764 ms  42.351 ms
11  dnvrng-kscyng.abilene.ucaid.edu (198.32.8.13)  65.430 ms  101.479 ms  71.056 ms
12  snvang-dnvrng.abilene.ucaid.edu (198.32.8.1)  78.085 ms  81.139 ms  78.952 ms
13  pos-1-0.core0.eug.oregon-gigapop.net (198.32.163.17)  88.204 ms  89.724 ms  89.129 ms
14  uo-0.eug.oregon-gigapop.net (198.32.163.147)  128.623 ms  120.511 ms  123.037 ms
15  ge-5-1.uonet1-gw.uoregon.edu (128.223.2.1)  102.757 ms ge-5-1.uonet2-gw.uoregon.edu (128.223.2.2)  90.565 ms ge-5-1.uonet1-gw.uoregon.edu (128.223.2.1)  118.008 ms
16  g0-1.route-views.routeviews.org (128.223.60.103)  101.156 ms *  88.975 ms
\end{verbatim}
        This route passes through MIT (\asn3), NOX/GIGAPOP-NE
        (\asn{10578}), Abilene (\asn{11537}), UO (\asn{4600}), and
        UONET (\asn{3582}). This is not the same as the reverse of the
        route in the trace data.
      \end{subsubproblem}

      \begin{subsubproblem}
        The AS path from MIT to routeviews is not the same as the
        reverse of the path from routeviews to MIT because MIT prefers
        a different route (via Abilene), presumably because of a
        \texttt{LOCAL PREF} option in MIT's router.

        The traceroute actually matches the AS path: the
        \texttt{nox.org} addresses are part of \asn{10578} and the
        Abilene hosts are \asn{11537}. The AS appears as \texttt{null}
        in the traceroute because the \texttt{whois} database
        consulted by the traceroute program did not include these
        ASes, but searching a more comprehensive database revealed the
        AS numbers. The brief excursion through \asn{40} at the
        beginning can be explained because \asn{40} is also part of
        MIT, so this is still an internal hop.
      \end{subsubproblem}
      
      \begin{subsubproblem}
        There are 51 routes from routeviews to MIT.
      \end{subsubproblem}

      \begin{subsubproblem}
        The router prefers a route via Level3 (\asn{3356}) to reach
        MIT, because this route has the shortest path length (two
        ASes) and lowest metric (zero).
      \end{subsubproblem}

      \begin{subsubproblem}
        % 174
        % 3356
        % 10578
        % 1239
        MIT's neighboring ASes are:
        \begin{enumerate}
        \item \asn{174} (\texttt{COGENT-PSI-1}) --- Cogent Communications
        \item \asn{1239} (\texttt{SPRINTLINK}) --- Sprint
        \item \asn{3356} (\texttt{LEVEL3)} --- Level 3 Communications
        \item \asn{10578} (\texttt{GIGAPOP-NE}) --- Harvard University
        \end{enumerate}
      \end{subsubproblem}
    \end{subproblem}

    \begin{subproblem}
      \begin{subsubproblem}
        This can be checked by testing whether
        \[ A_i >> (32-m) == A >> (32-m) \]
      \end{subsubproblem}
      
      \begin{subsubproblem}
        The first such address is \texttt{192.0.32.0/21}. This
        corresponds to $2^3 = 8$ class $C$ networks. So CIDR is
        reducing at most 8 routing table entries to 1 here, giving a
        maximum savings of 7. However, some of the address space in
        the \texttt{/21} block might be unused, so some of the class C
        blocks might not need routing table entries, in which case the
        savings would be less.
      \end{subsubproblem}

      \begin{subsubproblem}
        \begin{enumerate}
        \item The prefixes \texttt{4.21.104.0/24} and
          \texttt{4.21.112.0/23} both have routes via the AS path
          $\mathtt{16150 \to 1239 \to 7018 \to 26207}$. This seems to
          be because the same organization (\texttt{AQUILENT}) owns
          both netblocks, but was not allocated a single contiguous
          block; the blocks in between, such as \texttt{4.21.106.0/23}
          are owned by different organizations.
        \item The contiguous blocks \texttt{8.10.114.0/24} and
          \texttt{8.10.115.0/24} both have routes via the same AS path
          $\mathtt{3356 \to 21904}$. This deaggregation might be
          useful in order to allow the possibility of advertising
          different routes to each of the \texttt{/24} blocks, for
          load balancing or similar reasons. But it increases the size
          of every router's routing table.
        \end{enumerate}
      \end{subsubproblem}

      \begin{subproblem}
        \begin{subsubproblem}
          Having only the destination network and mask would not
          provide much useful information, but it would be possible to
          determine which IP addresses are unroutable and hence make
          some guesses about the number of hosts on the
          Internet. Since CIDR supports aggregation, it's not entirely
          unreasonable to use the number of destination network masks
          in the routing table as an estimate of the number of
          distinct networks, but this would not be especially accurate.
        \end{subsubproblem}

        \begin{subsubproblem}
          This would include the best next-hop and AS path for every
          routable address, so it would allow one to determine the
          number of ASes, and some of the links between ASes. It would
          be possible to determine how packets were routed from the
          Oregon Exchange at the time of each snapshot. It would be
          possible to attempt to infer AS relationships from the AS
          paths as in Problem 3, though this provides only a partial
          view since all the other paths are missing.
        \end{subsubproblem}

        \begin{subsubproblem}
          This provides all the information that can be inferred from
          (b), except for information about the next hop IP address,
          and metric/weight/MED/local-pref information. It also
          provides a view of AS links, so could be used to infer AS
          relationships as in Problem 3, using either the degree
          ranking method or the graph pruning method (though only with
          a single vantage point).
        \end{subsubproblem}
      \end{subproblem}
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      A CCDF of AS degree follows:
      \begin{center}
        \input{ccdf}
      \end{center}
      
      \begin{center}
        \textbf{Top 10 ASes by degree}\\
        \begin{tabular}{|c|c|c|}
          \hline
          \textbf{Degree} & \textbf{AS \#} & \textbf{Name} \\
          \hline
          2404 & \texttt{701} & ALTERNET-AS / UUNET Technologies, Inc \\
          2001 & \texttt{7018} & ATT-INTERNET4 / AT\&T WorldNet Services \\
          1763 & \texttt{1239} & SPRINTLINK / Sprint\\
          1267 & \texttt{3356} &  LEVEL3 / Level 3 Communications, LLC\\
          1148 & \texttt{209} &  ASN-QWEST / Qwest \\
          1063 & \texttt{174} &  COGENT-PSI-1 / Cogent Communications \\
          675 & \texttt{3549} &  GBLX / Global Crossing \\
          659 & \texttt{6461} &  ABOVENET / Abovenet Communications, Inc\\
          646 & \texttt{4323} &  TWTC / Time Warner Telecom \\
          598 & \texttt{7132} &  SBIS-AS / SBC Internet Services \\
          \hline
        \end{tabular}
      \end{center}
    \end{subproblem}

    \begin{subproblem}
      \newcommand{\la}{\leftarrow}
      \newcommand{\ra}{\rightarrow}
      \newcommand{\lra}{\leftrightarrow}
      Let ``$A$ obtains transit from $B$'' be denoted as $A \ra B$; ``$A$
      provides transit to $B$'' be denoted as $A \la B$; and a sibling
      relationship between $A$ and $B$ as $A \lra B$.
      
      \begin{subsubproblem}
        $16150 \ra 1239 \ra 701 \la 703 \la 80$
      \end{subsubproblem}
      
      \begin{subsubproblem}
        $7660 \ra 2516 \ra 1239 \ra 7018 \la 2386$
      \end{subsubproblem}

      \begin{subsubproblem}
        $3277 \lra 3267 \lra 3343 \ra 1299 \ra 3549 \la 206$
      \end{subsubproblem}

      \begin{subsubproblem}
        $4513 \lra 7911 \la 3320 \la 8551$
      \end{subsubproblem}
    \end{subproblem}

    \begin{subproblem}
      \begin{subsubproblem}
        The advantage of this ranking scheme is that it can identify
        provider-customer relationships even when the degree is not
        proportional to the AS's size; the paper gives the examples of
        a small ISP that purchases transit from many providers, and a
        large ISP that has peering relationships with only a few
        providers. However, it requires multiple vantage points to be
        effective.
      \end{subsubproblem}

      \begin{subsubproblem}
        The scheme requires multiple vantage points because some links
        may not be visible from every vantage point. For example, an
        ISP will not advertise transit routes it has purchased to its
        peers or other providers, so they will not see these
        routes. Also, multiple vantage points are necessary to
        identify peering relationships: a single vantage point will
        suggest that one peer is a customer of the other, and a
        different one will suggest the opposite.
      \end{subsubproblem}
    \end{subproblem}
  \end{problem}
\end{pset}
\end{document}

