routing-table.tex

\section{Routing Table}
\label{sec:routing-table}

The Routing Table module performs three main tasks: it performs the routing table calculations using a \texttt{RoutingTableCalculator} (Section~\ref{sec:routing-table-calculator}),
it stores the calculated routing table entries in a table, and notifies the Name Prefix Table module (Section~\ref{sec:npt}) when there are changes to the calculated next hops.

\subsection{Routing Table Calculators}
\label{sec:routing-table-calculator}

The \texttt{RoutingTableCalculator} is a base class provides functionality common to both link-state and hyperbolic routing.
The Routing Table module uses the implementation class specific to the type of routing currently enabled.

\subsubsection{Link-State Routing Table Calculator}

The \texttt{LinkStateRoutingTableCalculator} class calculates the routing table uses Dijkstra's algorithm to calculate the shortest paths in the network.
When \texttt{max-faces-per-prefix} is set to one, the \texttt{LinkStateRoutingTableCalculator} can simply run Dijkstra's algorithm.
When \texttt{max-faces-per-prefix} is set to a value indicating multi-path calculation, the \\ \texttt{LinkStateRoutingTableCalculator} will iteratively perform Dijkstra's using only a single neighbor link as a next hop.
The calculation will be performed using each neighbor in order to learn the path costs for each destination through each next hop.


\subsubsection{Hyperbolic Routing Table Calculator}

The \texttt{HyperbolicRoutingCalculator} class calculates the routing table uses the Coordinate LSAs received from each router in the network to determine the cost from each of its neighbors to every other router in the network.
The \texttt{HyperbolicRoutingCalculator} iterates through each of the router's neighbors calculating the hyperbolic distance from the neighbor to every other router in the network (excluding itself and the neighbor router).
The \texttt{HyperbolicRoutingCalculator} then uses these calculated distances to add routing table entries to the destination with the neighbor as the next hop.
The \texttt{HyperbolicRoutingCalculator} also adds a routing table entry to reach the neighbor itself; a routing table entry using the neighbor as a next hop to the neighbor with a cost of zero is added.

\subsection{Notifications for Newly Calculated Next Hops}

Once the Routing Table Module has finished calculating the routing table, it will notify the Name Prefix Table module using the \texttt{NamePrefixTable::updateWithNewRoute} interface.
The Name Prefix Table Module will then update the next hops for each name prefix based on the newly calculated routing table.
This process is described in more detail in Section~\ref{sec:npt-update-with-new-route}.