npt.tex - NLSR - Gitiles

 \section{Name Prefix Table}
 \label{sec:npt}

 \begin{figure}[!h]
   \center
   \includegraphics[width=0.8\linewidth]{npt.pdf}
   \begin{caption}
     A diagram of the NPT and Routing Table.

     \begin{footnotesize}
       The ``wire'' arrows represent references (i.e. ``x has y''),
       whereas the ``solid'' arrows represent inheritance (i.e. ``y subclasses x''). \\
       The quantification (e.g. 0..*) is standard UML.
     \end{footnotesize}
   \end{caption}
   \label{fig:npt-class-diagram}
 \end{figure}

 The Name Prefix Table (NPT) is used by NLSR to maintain a list of all known name prefixes advertised by other routers, including router names.
 The NPT maintains a collection of NPT entries, where each entry represents a name prefix and all of its associated routing table entries.
 Additionally, to optimize the storage and association of the routing table entries, the NPT also maintains a collection of duplicated routing table entries, called routing table pool entries, which have an additional use count attribute.
 The NPT entries keep shared pointers to the appropriate routing table pool entries.
 If a name prefix is advertised by multiple routers, the name prefix will be represented by only one Name Prefix Table Entry, but will have multiple routing table pool entries  which correspond with each origin router.

 If a Name LSA exists with some advertised name prefix, then that prefix must have an entry in the NPT. So, if two routers advertise the same name prefix, i.e. their name LSAs contain a common name prefix, even if one router withdraws that common name prefix, the entry must remain in the NPT, because the other router still advertises it.

 If any type of LSA for a remote router exists in the LSDB, the remote router's name prefix must be in the NPT.
 An NPT Entry for a router name can only be removed when there are no more LSAs in the LSDB from the origin router. Note, even if some NPT entry nas no next hops, it will \emph{not} be removed from the NPT; it may later become possible to route to this prefix. These prefixes will be removed from the FIB, however.

 \subsection{Adding an NPT Entry}
 \label{sec:npt-add}
 The \texttt{NamePrefixTable::addEntry()} method is the public
 interface for name prefixes to be added to the NPT.
 The name prefix as well as the router's prefix which originates the
 name prefix are passed as parameters to the method.

 If the name prefix is new, there will be no NPT entry for it, so one
 will be created. If the name prefix is not new, the existing entry
 will be updated, so the existing entry will also store this new origin
 router's prefix, too. If after updating, the NPT entry has any next
 hops, which are associated to each of the origin router prefixes, the
 NPT will update the FIB to include that prefix and its next hops. The
 next hop list is sorted and truncated to be only as long as the
 \texttt{max-faces-per-prefix} variable.
 n
 \subsection{Removing an NPT Entry}
 \label{sec:npt-del}
 The \texttt{NamePrefixTable::removeEntry()} method is the public
 interface for name prefixes to be removed from the NPT.
 The name prefix as well as the router's prefix which originates the
 name prefix are passed as parameters to the interface.

 This method removes an origin router prefix from some advertised name
 prefix. After this, there may be other origin routers that serve this
 name prefix, so this does not guarantee that the NPT entry will be
 deleted. If after updating the entry has any next hops, the NPT will
 update the FIB to reflect the change. Since the next hop list is
 sorted by ascending cost and its length truncated to
 \texttt{max-faces-per-prefix}, the contents of next hop list will not
 change if the removed origin router prefix was not already in the list
 passed to the FIB.

 Note that even if the entry no longer has any next hops, it will be retained. All FIB entries for this prefix will be removed from the FIB, which will result in unregistrations from NFD, but the NPT entry will be retained. This is because it may become possible later to route to these origin routers again.

 \subsection{Updating an NPT Entry with New Routing Table Entries}
 \label{sec:npt-update-with-new-route}
 When the Routing Table module has finished calculating, it will notify
 the NPT using the \texttt{NamePrefixTable::updateWithNewRoute()}
 method.
 The NPT will then make approximately $m \times n$ calls to
 \texttt{addEntry}, where $m$ is the number of NPT entries and $n$ is
 the number of origin routers for each m. That is, $n$ will vary from
 one NPT entry to the next in most cases.

 \subsection{Routing Table Entry Pool}
 The Name Prefix Table has an internal data structure to help
 de-duplicate Routing Table information. Without this, each Routing
 Table entry has to be stored $n$ times, if $n$ is the number of
 prefixes that origin router advertises. Instead, each time a Routing
 Table entry would be fetched, the NPT first checks its internal data
 structure to see if that Routing Table entry is being used by another
 NPT entry. In that case those two NPT entries can share a pointer to
 that cached copy of the Routing Table entry.

 This internal cache is smart, and will clean up from the cache unused
 entries when they are removed from the last NPT entry.
	\section{Name Prefix Table}
	\label{sec:npt}

	\begin{figure}[!h]
	\center
	\includegraphics[width=0.8\linewidth]{npt.pdf}
	\begin{caption}
	A diagram of the NPT and Routing Table.

	\begin{footnotesize}
	The ``wire'' arrows represent references (i.e. ``x has y''),
	whereas the ``solid'' arrows represent inheritance (i.e. ``y subclasses x''). \\
	The quantification (e.g. 0..*) is standard UML.
	\end{footnotesize}
	\end{caption}
	\label{fig:npt-class-diagram}
	\end{figure}

	The Name Prefix Table (NPT) is used by NLSR to maintain a list of all known name prefixes advertised by other routers, including router names.
	The NPT maintains a collection of NPT entries, where each entry represents a name prefix and all of its associated routing table entries.
	Additionally, to optimize the storage and association of the routing table entries, the NPT also maintains a collection of duplicated routing table entries, called routing table pool entries, which have an additional use count attribute.
	The NPT entries keep shared pointers to the appropriate routing table pool entries.
	If a name prefix is advertised by multiple routers, the name prefix will be represented by only one Name Prefix Table Entry, but will have multiple routing table pool entries which correspond with each origin router.

	If a Name LSA exists with some advertised name prefix, then that prefix must have an entry in the NPT. So, if two routers advertise the same name prefix, i.e. their name LSAs contain a common name prefix, even if one router withdraws that common name prefix, the entry must remain in the NPT, because the other router still advertises it.

	If any type of LSA for a remote router exists in the LSDB, the remote router's name prefix must be in the NPT.
	An NPT Entry for a router name can only be removed when there are no more LSAs in the LSDB from the origin router. Note, even if some NPT entry nas no next hops, it will \emph{not} be removed from the NPT; it may later become possible to route to this prefix. These prefixes will be removed from the FIB, however.

	\subsection{Adding an NPT Entry}
	\label{sec:npt-add}
	The \texttt{NamePrefixTable::addEntry()} method is the public
	interface for name prefixes to be added to the NPT.
	The name prefix as well as the router's prefix which originates the
	name prefix are passed as parameters to the method.

	If the name prefix is new, there will be no NPT entry for it, so one
	will be created. If the name prefix is not new, the existing entry
	will be updated, so the existing entry will also store this new origin
	router's prefix, too. If after updating, the NPT entry has any next
	hops, which are associated to each of the origin router prefixes, the
	NPT will update the FIB to include that prefix and its next hops. The
	next hop list is sorted and truncated to be only as long as the
	\texttt{max-faces-per-prefix} variable.
	n
	\subsection{Removing an NPT Entry}
	\label{sec:npt-del}
	The \texttt{NamePrefixTable::removeEntry()} method is the public
	interface for name prefixes to be removed from the NPT.
	The name prefix as well as the router's prefix which originates the
	name prefix are passed as parameters to the interface.

	This method removes an origin router prefix from some advertised name
	prefix. After this, there may be other origin routers that serve this
	name prefix, so this does not guarantee that the NPT entry will be
	deleted. If after updating the entry has any next hops, the NPT will
	update the FIB to reflect the change. Since the next hop list is
	sorted by ascending cost and its length truncated to
	\texttt{max-faces-per-prefix}, the contents of next hop list will not
	change if the removed origin router prefix was not already in the list
	passed to the FIB.

	Note that even if the entry no longer has any next hops, it will be retained. All FIB entries for this prefix will be removed from the FIB, which will result in unregistrations from NFD, but the NPT entry will be retained. This is because it may become possible later to route to these origin routers again.

	\subsection{Updating an NPT Entry with New Routing Table Entries}
	\label{sec:npt-update-with-new-route}
	When the Routing Table module has finished calculating, it will notify
	the NPT using the \texttt{NamePrefixTable::updateWithNewRoute()}
	method.
	The NPT will then make approximately $m \times n$ calls to
	\texttt{addEntry}, where $m$ is the number of NPT entries and $n$ is
	the number of origin routers for each m. That is, $n$ will vary from
	one NPT entry to the next in most cases.

	\subsection{Routing Table Entry Pool}
	The Name Prefix Table has an internal data structure to help
	de-duplicate Routing Table information. Without this, each Routing
	Table entry has to be stored $n$ times, if $n$ is the number of
	prefixes that origin router advertises. Instead, each time a Routing
	Table entry would be fetched, the NPT first checks its internal data
	structure to see if that Routing Table entry is being used by another
	NPT entry. In that case those two NPT entries can share a pointer to
	that cached copy of the Routing Table entry.

	This internal cache is smart, and will clean up from the cache unused
	entries when they are removed from the last NPT entry.