\documentclass{article}
 \usepackage{graphicx}
\usepackage{verbatim}
\usepackage{fullpage}


\newcounter{qcounter}
\setcounter{qcounter}{1}

\newenvironment{question}
{
%     \begin{minipage}[s]{6.2in}
     \noindent{\bf Question \arabic{qcounter}:}
     \addtocounter{qcounter}{1}
}
%{
 %    \end{minipage}
%}

\newcommand\rr{{\it Route Reflector} }
\newenvironment{answer}
{
     \par\noindent
     \noindent{\bf Answer:}
}

\begin{comment}

      \begin{figure}
      \centering
      \includegraphics[Insert width][Insert angle]{Figure name without .eps extension}
      \caption{Insert caption}
      \end{figure}

%--placing a full page figure.
\clearpage
\begin{figure}
\centering
\includegraphics{Figure name .eps, .ps  extension}
\caption{Insert caption}
\end{figure}
\clearpage

\end{comment}
%{\HalfSpace\par\noindent}{}

\title{15-744 Computer Networks (Fall 2004)\\ Homework 1}

\author{}
\date{}



%\newcommand{\QuadSpace}{\vspace{0.25\baselineskip}}
%\newcommand{\HalfSpace}{\vspace{0.5\baselineskip}}
\begin{document}

\maketitle
{\bf Date Assigned: Oct 1, 2004; Date Due: Oct 8, 2004 (in class)}

\begin{flushleft}

\section{Link Probing}

Harry Bovik dreams up a cute new idea for a networking protocol based on
{\tt traceroute}. traceroute is a tool that prints the route packets take to
a given network host.
Please read the man page to find out how traceroute works. Assume that no
queuing occors in routers, no routes change and that the netwrok consists of
FIFO, drop-tail routers.

\begin{question}
How could Harry modify traceroute to report the latency of a
particular link in the network (i.e. {\bf not} the entire path to that
distance)?\\[0.2 in]

\end{question}

\begin{question}
Harry is on a roll! He decides to modify his new tool so that it can
measure the bandwidth of a specific link along the path. How exactly
can he implement this? (Hint: use packets of 2 different sizes.)
\end{question}

\section{Routing}

\begin{question}
Suppose you are designing a new source routing protocol.  One
important design decision is how your routers exchange routing
information that the routing decisions will be based on. You are
considering two choices
\begin{enumerate}
\item have the routers exchange routing tables as is done in RIP
advertisements.
\item have the routers exchange link state updates as is done in OSPF.
\end{enumerate}

Which one would you choose and why?\\[0.2 in]

\end{question}

\begin{question}
As you have seen in class there are different protocols used for
Inter-AS and Intra-AS routing.  One reason frequently given for not
using OSPF in Inter-AS routing is that it is less scalable.  Assume
that you could completely avoid OSPF's scalability issues by doing
hierarchical routing using areas.  Are there still reasons why BGP
should be used instead of OSPF for Inter-AS routing?\\[0.2 in]

\end{question}


\begin{question}
Suppose there are two feuding ASs X and Y.  
\begin{enumerate}
\item Using BGP, is it possible for AS X to implement a policy
"traffic from my AS should not cross AS Y"?
\item Is it possible for AS Y to implement a policy "I don't want to
carry transit traffic from X"?  Why or why not?\\[0.2 in]
\end{enumerate}
\end{question}

\begin{figure}[hbtp]      
\centering
\includegraphics[width=4.5 in]{fred}
%      \caption{Insert caption}
\end{figure}

\begin{question}
Consider the above network. Assume that the routers use shortest path
link state routing and that the routing tables have all stabilized.
Evil Fred decides to impersonate Bob and sends out IP packets with
Bob's IP address as the source to Alice. How can Alice's router
(Router 1) detect this?\\[0.2 in]

\end{question}

\begin{question}
Is your solution from the previous question also applicable in the case
of a distance-vector protocol?\\[0.2 in]

\end{question}

\begin{question}
What if Alice is now on another network far far away and router 1 is
her border router.  Can you use a similar solution?\\[0.2 in]

\end{question}


\begin{question}
Suppose this is the routing table of a router that uses
the data structure from the D97+ paper for fast routing lookups:\\[0.2 in]

\begin{center}
\begin{tabular}{|l l|}
\hline
Destination &  Iface \\
\hline
0.1.0/18     & eth1 \\
0.4/14       & eth2 \\
0.7/16       & eth3 \\
default      & eth4 \\
\hline
\end{tabular}
\end{center}

What are the first 8 bits of the vector representing the cut through the prefix tree at depth 16?
\end{question} 

\section{Inferring BGP policy}
\begin{question}
Figure \ref{bgp_infer} gives an example of how the routes to a particular
AS may be exported. The vertices of the graph denote different ASs,
and the annotation on the directed edge (i, j) shows the announcement
AS $i$ sends to AS $j$ about its reachability information to P
(Remember, BGP is a AS-path-vector protocol, and each announcement
must contain the AS path and the prefix (in this case, AS P)). Also
recall that BGP is a policy based protocol, and an AS exports a route
to a neighbor only if it is willing to accept and forward traffic for
that prefix from that neighbor.

Such a graph gives us some idea about the relationship between ASs.
From the graph, 
\begin{enumerate}
\item What can you infer about the relationship between AS
200 and AS 100? 
\item What about the relationship between AS 200 and AS 400?
% added from aditya's questions
\item What can you say about the relationship between AS 500 and AS 300?
Explain.
\item What about the relationship between AS 100 and AS 400? Explain.  

\item 
Assume that AS 400 and 600 have a peering relationship with each
other. For each of the possible answers to the question above (the
relationship between AS 400 and AS 100), enumerate whether or not AS
400 will announce a route for P to AS 600. Explain your answers.
\end{enumerate}
\end{question}

\begin{figure}[hbtp]      
\centering
\includegraphics[width=4.5 in]{bgp_infer}
\caption{Figure for question 10}
\label{bgp_infer}
\end{figure}


\section{I-BGP}
\begin{question}
I-BGP is used to exchange external reachability information within a
single AS. But, as opposed to E-BGP sessions that share a physical
link, the I-BGP messages go over a logical link. In essence, the I-BGP
packets are routed over IGP! Assume that each router in the AS needs
to have a default-free routing table. So, each router in the AS has to
participate in I-BGP sessions. 

One scalable way to do this is to have a hierarchy. The set of routers
is partitioned into disjoint sets and there is one \rr (assume it is
one of the routers belonging to the set) for each set. Maintaining
consistency (about the reachability information) among all routers can
then be broken into two sub-problems.  
\begin{enumerate}
\item The {\it Route Reflectors} need to maintain consistency among
themselves, which they typically do by establishing I-BGP sessions
with all other {\it Route Reflectors}. 
\item Each set of routers needs to maintain consistency among
its member routers. This is typically done by having each router maintain an
I-BGP session with the \rr of its set.
\end{enumerate}

The {\it Route Reflectors} also suppress reachability information
which they think is redundant. For example, if they learn of two paths
to a prefix, say one with a cost of 5 and the other with a cost of 10,
they will filter the path with a cost of 10. 

Figure \ref{ibgp} shows a AS (let us call it X) that has 4 routers,
$R_1$, $R_2$, $C_1$, and $C_2$. $R_1$ and $R_2$ are the gateway
routers and also double as Route Reflectors. Imagine, there is another
AS Y (not shown in the figure) adjacent to AS X, and it has two
gateway routers $R_3$ and $R_4$. $R_1$ maintains a E-BGP session with
$R_3$, and $R_2$ maintains a E-BGP session with $R_4$. From its
interaction with $R_3$, $R_1$ learns of $P_1$, a one hop AS-path to AS
Y. Similarly, $R_2$ learns of $P_2$, another one hop AS-path to AS Y.
Each circle denotes a set ($R_1$ maintains 2 I-BGP sessions: one with
$C_1$, other with $R_2$. Similarly, for $R_2$). The edges of the graph
show actual links between the routers, and the edge label denotes the
IGP cost of the link. Note that the graph has an axis of symmetry, and
hence our reasoning about $R_1$, $P_1$ and $C_1$ applies to $R_2$,
$P_2$ and $C_2$ as well.
\begin{enumerate}
\item Which path, $P_1$ or $P_2$, will $R_1$ announce to $C_1$?
\item If $C_1$ needs to get to $R_1$, what path will it take?
\item Say $C_1$ wants to reach some host in AS Y. What happens now?
(Hint: A forwarding loop is the result. Think why?)
\end{enumerate}

\end{question}

\begin{figure}[hbtp]      
\centering
\includegraphics[width=4.5 in]{ibgp}
\caption{Figure for question 11}
\label{ibgp}
\end{figure}


\section{Router Design}
\begin{question}
Assume a 64-port IP router, with each port operating at 2.4 Gbps. Let
the average size of the Internet datagram is 1000 bytes. Also, assume
that there is output-buffering of packets. 
\begin{enumerate}
\item If the forwarding decisions are done at the line card, how fast
should they be made? 
\item What should be the bandwidth of a shared bus, such that it does
not become a bottleneck? 
\item If instead of a shared bus, a switched backplane (64 X 64) is
used, how much speedup is needed, if there should not be any queuing
delays? In practice, what value of speedup works well?
\end{enumerate}
\end{question}


\section{Gearing Up for ns}

ns is a network simulator that will be useful in homeworks, the class
project and in networks research in general.  


The purpose of this assignment is to teach you the basics of using ns
and to make you familiar with the {\em ns manual} (http://www.isi.edu/nsnam/ns/ns-documentation.html).
You will also learn how to develop new components for ns.

For now, you can simply download and install NS. Subsequent
assignments will require you to use NS. 

\begin{enumerate}
\item Download and Install ns \\
Download ns-allinone from the class homepage. This version
of ns contains all the components you need, including the Tcl interpreter.
We recommend using this ``build-it-all-at-once'' approach not only because
it is less hassle-free than to build ns from its constituent pieces;
but also because you might get different results or problems if you use 
a different version of ns or the Tcl interpreter.

Visit http://www.isi.edu/nsnam/ns/ns-build.html\#allinone
for instructions to install
ns. Make sure you have enough disk space on your machine: to build ns you
will need around 250 Mb.
\item Starting ns \\
After installation, you can start ns with the command `ns
$<$tclscript$>$' (assuming that you are in the directory with the ns
executable, or that your path points to that directory), where
`$<$tclscript$>$' is the name of a Tcl script file which defines the
simulation scenario (i.e. the topology and the events). This will be
more clear as you go along. You could also just start ns without any
arguments (ns will return a \% prompt on most systems) and enter the
Tcl commands in the Tcl shell but that is definitely less comfortable.

\item Understanding Otcl\\ You would need a basic understanding of
Otcl for the next homework.\\
http://www.isi.edu/nsnam/otcl/doc/tutorial.html gives a short
introduction to Otcl for C++ programmers, which you might want to read
if you are not familiar with Otcl.

\end{enumerate}

\end{flushleft}

\end{document}



