\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}