\section{Global Internet}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Scalability Issues}

   IP ``hides'' hosts in address hierarchy, but...

   \begin{sitem}
      \item Inefficient use of address space
      \begin{sitem}
         \item class C network with 2 hosts (2/255 = 0.78\% efficient)
         \item class B network with 256 hosts (256/65535 = 0.39\% efficient)
      \end{sitem}
      \item Too many networks
      \begin{sitem}   
         \item today's Internet has tens of thousands of networks
         \item routing tables do not scale
         \item route propagation protocols do not scale
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Internet Structure}

   Recent Past

   \pichere{inet-tree.eps,height=2in}

   Today

   \pichere{inet-today.eps,height=2in}

\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Subnetting}

   \begin{sitem}
      \item Add another level to address/routing hierarchy: {\it subnet}
      \item {\it Subnet masks} define variable partition of host part of 
            class A and B addresses
      \item Subnets visible only within site
   \end{sitem}

   \pichere{subaddr.eps,height=3in}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Subnet Example}

   \pichere{subnet.eps,height=5in}

   Forwarding table at router R1

\begin{center}
\begin{tabular}{l|l|l}
\hline
Subnet Number & Subnet Mask & Next Hop \\ 
\hline
128.96.34.0 & 255.255.255.128 &  interface 0 \\
128.96.34.128 & 255.255.255.128 &  interface 1 \\
128.96.33.0 & 255.255.255.0 &  R2
\end{tabular}
\end{center}

\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Forwarding Algorithm}

\begin{tabbing}
xxx \= xxx \= xxx \= xxx \= \kill
\> {\tt D = destination IP address}\\
\> {\tt for each entry $\langle$SubnetNum, SubnetMask, NextHop$\rangle$}\\
\>\> {\tt D1 = SubnetMask \& D}\\
\>\> {\tt if D1 = SubnetNum}\\
\>\>\> {\tt if NextHop is an interface}\\
\>\>\>\> {\tt deliver datagram directly to destination}\\
\>\>\> {\tt else}\\
\>\>\>\> {\tt deliver datagram to NextHop (a router)}
\end{tabbing}

   Notes
   \begin{sitem}
      \item Would use a default router if nothing matches
      \item Not necessary for all ones in subnet mask to be contiguous
      \item Can put multiple subnets on one physical network
      \item Subnets not visible from the rest of the Internet
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Supernetting}

   \begin{sitem}
      \item Assign block of contiguous network numbers to near-by networks
      \item Called CIDR: Classless Inter-Domain Routing
      \item Represent blocks with a single pair
      \begin{quote}
         $\langle$ {\tt first\_network\_address, count} $\rangle$
      \end{quote}
      \item Restrict block sizes to powers of 2
      \item Use a bit mask (CIDR mask) to identify block size
      \item All routers must understand CIDR addressing
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Route Propagation}

   Idea: Impose a second hierarchy on the network that limits what 
   routers talk to each other. (The first hierarchy is the address
   hierarchy that governs how packets are forwarded.)

   \begin{sitem}
      \item Autonomous System (AS)
      \begin{sitem}
         \item corresponds to an administrative domain
         \item examples: University, company, backbone network
         \item assign each AS a 16-bit number
      \end{sitem}
      \item Two-level route propagation hierarchy
      \begin{sitem}
         \item interior gateway protocol (each AS selects its own)
         \item exterior gateway protocol (Internet-wide standard)
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Popular Interior Gateway Protocols}

   \begin{sitem}
      \item RIP: Route Information Protocol
      \begin{sitem}
         \item developed for XNS
         \item distributed with Unix
         \item distance-vector algorithm
         \item based on hop-count
      \end{sitem}

      \item OSPF: Open Shortest Path First
      \begin{sitem}
         \item recent Internet standard
         \item uses link-state algorithm
         \item supports load balancing
         \item supports authentication
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{EGP: Exterior Gateway Protocol}

   \begin{sitem}
      \item Overview
      \begin{sitem}
         \item designed for tree-structured Internet
         \item concerned with {\it reachability}, not optimal routes
      \end{sitem}
      \item Protocol messages
      \begin{sitem}
         \item neighbor acquisition: one router requests that another
               be its peer; peers exchange reachability information
         \item neighbor reachability: one router periodically tests
               to see if the other router is still reachable; exchange
               HELLO/ACK messages; uses a k-out-of-n rule
         \item routing updates: peers periodically exchange their routing
               tables (distance-vector)
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}
   \subsection{EGP Example}

   \pichere{egproutes.ps,width=5in}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{BGP-4: Border Gateway Protocol}

   Assumes the Internet is an arbitrarily interconnected set of AS's. 
   Define{\em local traffic} as traffic that originates at or terminates
   on nodes within an AS, and {\em transit traffic} as traffic that passes
   through an AS, we can classify AS's into three types:

   \begin{sitem}
      \item Stub AS: an AS that has only a single connection to one other 
            AS;	such an AS will only carry local traffic.

      \item Multihomed AS: an AS that has connections to more than one other
	    AS, but refuses to carry transit traffic.

      \item Transit AS: an AS that has connections to more than one other AS,
            and is designed to carry both transit and local traffic.
   \end{sitem}

   Each AS has:
   \begin{sitem}
      \item One or more border routers
      \item One BGP {\it speaker} that advertises:
      \begin{sitem}
         \item local networks
         \item other reachable networks (transit AS only)
         \item gives {\it path} information
      \end{sitem}
   \end{sitem}
\end{slide}

% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{BGP Example}

   \pichere{bgpeg.eps,height=3in}

   \begin{sitem}
      \item Speaker for AS 2 advertises reachability to P and Q
      \begin{quote}
         Network 128.96, 192.4.153, 192.4.32, and 192.4.3, can 
         be reached directly from AS 2.
      \end{quote}
      \item Speaker for backbone network then advertises
      \begin{quote}
         Networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be reached
         along the path $\langle$AS 1, AS 2$\rangle$.
      \end{quote}
      \item Speaker can also cancel previously advertised paths
   \end{sitem}
\end{slide}

