path: root/Master/texmf-dist/doc/latex/bytefield/bf-example.tex

\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{longtable}
\usepackage[bitheight=6ex]{bytefield}
\usepackage{color}
\usepackage[bookmarksopen=true]{hyperref}

\title{Integrating \texttt{bytefield} and \texttt{hyperref}}
\author{\href{http://www.pakin.org/~scott}{Scott Pakin 
  \texttt{<scott+bf@pakin.org>}}}
\date{18 January 2011}
\hypersetup{%
pdftitle={Integrating bytefield and hyperref},
pdfauthor={Scott Pakin <scott+bf@pakin.org>},
pdfsubject={Example of bytefield package},
pdfkeywords={bytefield, hyperref, multicast transport protocol, hyperlink, example}}

% Set up hyperlink colors
\definecolor{darkred}{rgb}{0.5,0,0}
\definecolor{darkgreen}{rgb}{0,0.3,0}
\definecolor{darkblue}{rgb}{0,0,0.5}
\definecolor{darkbrown}{rgb}{0.28,0.07,0.07}
\hypersetup{%
  colorlinks=true,
  citecolor=darkblue,
  urlcolor=darkgreen,
  linkcolor=darkred,
  menucolor=darkbrown}

\begin{document}
\sloppy
\maketitle

\begin{abstract}
This document is a demonstration of how the \texttt{bytefield} package can
integrate seamlessly with \texttt{hyperref}.  The text that follows was
copy-and-pasted from
\href{http://www.rfc-editor.org/rfc/rfc1301.txt}{RFC~1301, ``Multicast
Transport Protocol''}~\cite{Armstrong92}.

The important thing to note is the way the fields in the protocol diagrams
(drawn with \texttt{bytefield}) are hyperlinked to their descriptions (with
\texttt{hyperref}).  Few typesetting systems enable authors to specify
hyperlinks from within a figure to the surrounding text.  Fewer still do
not require hyperlinks to be re-specified when the figure changes.
\texttt{bytefield}~+ \texttt{hyperref} can do both.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setcounter{section}{1}

\section{Protocol description}

   MTP is a transport in that it is a client of the network layer (as
   defined by the OSI networking model).\footnote{The network layer is not
   specified by MTP. One of the goals is to specify a transport that can be
   implemented with equal functionality on many network architectures.}
   MTP provides reliable delivery of client data between one or more
   communicating processes, as well as a predefined principal process. The
   collection of processes is called a web.

   In addition to transporting data reliably and efficiently, MTP
   provides the synchronization necessary for web members to agree on
   the order of receipt of all messages and can agree on the delivery of
   the message even in the face of partitions.  This ordering and
   agreement protocol uses serialized tokens granted by the master to
   producers.

   The processes may have any one of three levels of capability. One
   member must be the master. The master instantiates and controls the
   behavior of the web, including its membership and performance. Non
   master members may be either producer/consumers or pure consumers.
   The former class of member is permitted to transmit user data to the
   entire membership (and expected to logically hear itself), while the
   latter is prohibited from transmitting user data.

   MTP is a negative acknowledgement protocol, exploiting the highly
   reliable delivery of the local area and wide area network
   technologies of today. Successful delivery of data is accepted by
   consuming stations silently rather than having the successful
   delivery noted to the producing process, thus reducing the amount of
   reverse traffic required to maintain synchronization.

\subsection{Definition of terms}

\begin{center}
  \fbox{Skipped; see~\cite{Armstrong92}}
\end{center}

\subsection{Packet format}

   An MTP packet consists of a transport protocol header followed by a
   variable amount of data. The protocol header, shown in
   Figure~\ref{fig:packet-format}, is part of every packet. The remainder
   of the packet is either user data (packet type = data) or additional
   transport specific information.  The fields in the header are statically
   defined as n-bit wide quantities. There are no undefined fields or
   fields that may at any time have undefined values.  Reserved fields, if
   they exist, must always have a value of zero.

\begin{figure}[htbp]
  \centering
  \begin{bytefield}{32}
    \bitheader{0,7-8,15-16,23-24,31} \\

    \begin{rightwordgroup}{transport \\ header}
      % We have to do the \parbox explicitly in the next line because
      % \hyperlink typesets its argument in horizontal mode.
      \bitbox{8}{\hyperlink{protocol-version}{\parbox{\width}{\centering protocol version}}} &
      \bitbox{8}{\hyperlink{packet-type-modifier}{packet type}} &
      \bitbox{8}{\hyperlink{packet-type-modifier}{type modifier}} &
      \bitbox{8}{\hyperlink{subchannel}{client channel}} \\

      \wordbox{1}{\hyperlink{source-connect}{source connection identifier}} \\

      \wordbox{1}{\hyperlink{dest-connect}{destination connection identifier}} \\

      \wordbox{1}{\hyperlink{msg-accept}{message acceptance criteria}} \\

      \wordbox{1}{\hyperlink{heartbeat}{heartbeat}} \\

      \bitbox{16}{\hyperlink{window}{window}} &
      \bitbox{16}{\hyperlink{retention}{retention}}
    \end{rightwordgroup} \\

  \begin{rightwordgroup}{data \\ fields}
    \wordbox[lrt]{1}{%
      \parbox{0.6\width}{\centering (data content and format dependent on packet type and modifier)}} \\
    \skippedwords \\
    \wordbox[lrb]{1}{} 
  \end{rightwordgroup}
  \end{bytefield}
  \caption{MTP packet format}
  \label{fig:packet-format}
\end{figure}

\hypertarget{protocol-version}{\subsubsection{Protocol version}}

   The first 8 bits of the packet are the protocol version number. This
   document describes version 1 of the Multicast Transport Protocol and
   thus the version field has a value of 0x01.

\hypertarget{packet-type-modifier}{\subsubsection{Packet type and modifier}}

   The second byte of the header is the packet type and the following
   byte contains the packet type modifier. Typical control message
   exchanges are in a request/response pair. The modifier field
   simplifies the construction of responses by permitting reuse of the
   incoming message with minimal modification. The following table gives
   the packet type field values along with their modifiers. The
   modifiers are valid only in the context of the type. In the prose of
   the definitions and later in the document, the syntax for referring
   to one of the entries described in the following table will be
   type[modifier]. For example, a reference to data[eow] would be a
   packet of type data with an end of window modifier.

\begin{center}
\renewcommand{\arraystretch}{1.5}
\begin{longtable}{llp{0.6\textwidth}}
   type & modifier & description \\ \hline

   data(0)  & data(0)    & The packet is one that contains user
                           information. Only the process possessing a
                           transmit token is permitted to send data
                           unless specifically requested to retransmit
                           previously transmitted data. All packets of
                           type data are multicast to the entire web. \\

            & eow(1)     & A data packet with the eow (end of window)
                           modifier set indicates that the transmitter
                           intends to send no more packets in this
                           heartbeat either because it has sent as many
                           as permitted given the window parameter or
                           simply has no more data to send during the
                           current heartbeat. This is not client
                           information but rather a hint to be used by
                           transport providers to synchronize the
                           computation and transmission of naks. \\

            & eom(2)     & Data[eom] marks the end of the message to the
                           consumers, and the surrendering of the
                           transmit token to the master. And like a
                           data[eow] a data[eom] packet implies the end
                           of window. \\
   nak(1)   & request(0) & A nak[request] packet is a consumer
                           requesting a retransmission of one or more
                           data packets. The data field contains an
                           ordered list of packet sequence numbers that
                           are being requested. Naks of any form are
                           always unicast. \\

            & deny(1)    & A nak[deny] message indicates that the
                           producer source of the nak[deny]) cannot
                           retransmit one or more of the packets
                           requested. The process receiving the
                           nak[deny] must report the failure to its
                           client. \\

   empty(2) & dally(0)   & An empty[dally] packet is multicast to
                           maintain synchronization when no client data
                           is available. \\

            & cancel(1)  & If a producer finds itself in possession of a
                           transmit token and has no data to send, it
                           may cancel the token[request] by multicasting
                           an empty[cancel] message. \\

            & hibernate(2)&If the master possesses all of the web's
                           transmit tokens and all outstanding messages
                           have been accepted or rejected, the master
                           may transmit empty[hibernate] packets at a
                           rate significantly slower than indicated by
                           the web's value of heartbeat. \\

   join(3)  & request(0) & A join[request] packet is sent by a process
                           wishing to join a web to the web's unknown
                           TSAP (see section~\ref{sec:dest-connect}). \\

            & confirm(1) & The join[confirm] packet is the master's
                           confirmation of the destination's request to
                           join the web. It will be unicast by the
                           master (and only the master) to the station
                           that sent the join[request]. \\

            & deny(2)    & A join[deny] packet indicates permission to
                           join the web was denied. It may only be
                           transmitted by the master and will be unicast
                           to the member that sent the join[request]. \\

   quit(4)  & request(0) & A quit[request] may be unicast to the master
                           by any member of the web at any time to
                           indicate the sending process wishes to
                           withdraw from the web. Any member may unicast
                           a quit to another member requesting that the
                           destination member quit the web due to
                           intolerable behavior.  The master may
                           multicast a quit[request] requiring that the
                           entire web disband. The request will be
                           multicast at regular heartbeat intervals
                           until there are no responses to retention
                           requests. \\

            & confirm(1) & The quit[confirm] packet is the indication
                           that a quit[request] has been observed and
                           appropriate local action has been taken.
                           Quit[confirm] are always unicast. \\

   token(5) & request(0) & A token[request] is a producing member
                           requesting a transmit token from the master.
                           Such packets are unicast to the master. \\

            & confirm(1) & The token[confirm] packet is sent by the
                           master to assign the transmit token to a
                           member that has requested it. token[confirm]
                           will be unicast to the member being granted
                           the token. \\

   isMember(6)&request(0)& An isMember[request] is soliciting
                           verification that the target member is a
                           recognized member of the web. All forms of
                           the isMember packet are unicast to a specific
                           member. \\

            & confirm(1) & IsMember[confirm] packets are positive
                           responses to isMember[requests]. \\

            & deny(2)    & If the member receiving the isMember[request]
                           cannot confirm the target's membership in the
                           web, it responds with a isMember[deny].
\end{longtable}
\end{center}

\hypertarget{subchannel}{\subsubsection{Subchannel}}

   The fourth byte of the transport header contains the client's
   subchannel value. The default value of the subchannel field is zero.
   Semantics of the subchannel value are defined by the transport client
   and therefore are only applicable to packets of type data. All other
   packet types must have a subchannel value of zero.

\hypertarget{source-connect}{\subsubsection{Source connection identifier}}

   The source connection identifier field is a 32 bit field containing a
   transmitting system unique value assigned at the time the transport
   is created. The field is used in identifying the particular transport
   instantiation and is a component of the TSAP\@. Every packet
   transmitted by the transport must have this field set.

\hypertarget{dest-connect}{\subsubsection{Destination connection identifier}}
\label{sec:dest-connect}

   The destination connection identifier is the 32 bit identifier of the
   target transport. From the point of view of a process sending a
   packet, there are three types of destination connection identifiers.
   First, there is the unknown connection identifier (0x00000000). The
   unknown value is used only as the destination connection identifier
   in the join[request] packet.

   Second, there is the multicast connection identifier gleaned from the
   join[confirm] message sent by the master. The multicast connection
   identifier is used in conjunction with the multicast NSAP to form the
   destination TSAP of all packets multicast to the entire
   web.\footnote{There's only one such multicast connection identifier per
   web. If there are multiple processes on the same machine participating
   in a web, the transport must descriminate between those processes by
   using the connnection identifier.}

   The last class of connection identifier is a unicast identifier and
   is used to form the destination TSAP when unicasting packets to
   individual members. Every member of the web has associated with it a
   unicast connection identifier that is used to form its own unicast
   TSAP.

\hypertarget{msg-accept}{\subsubsection{Message acceptance}}

   MTP ensures that all processes agree on which messages are accepted
   and in what order they are accepted. The master controls this aspect
   of the protocol by controlling allocation of transmit tokens and
   setting the status of messages. Once a token for a message has been
   assigned (see section 3.2.1) the master sets the status of that
   message according to the following rules~\cite{Armstrong91}:

   \begin{itemize}
     \item If the master has seen the entire message (i.e., has seen the
     data[eom] and all intervening data packets), the status is accepted.

     \item If the master has not seen the entire message but believes the
     message sender is still operational and connected to the master (as
     determined by the master), the status is pending.

     \item If the master has not seen the entire message and believes the
     sender to have failed or partitioned away, the status is rejected.
   \end{itemize}

   Message status is carried in the message acceptance record (see
   Figure~\ref{fig:msg-accept}) of every packet, and processes learn the
   status of earlier messages by processing this information.

   The acceptance criteria is a multiple part record that carries the rules
   of agreement to determine the message acceptance.
   \hypertarget{synchro}{The most significant 8 bits is a flag that, if not
   zero, indicates synchronization is required.}  The field may vary on a
   per message basis as directed by producing transport's client. The
   default is that no synchronization is required.

   \hypertarget{tri-state}{The second part of the record is a 12 element
   vector that represents the status of the last 12 messages transmitted
   into the web.}

\begin{figure}[htbp]
  \centering
  \begin{bytefield}{32}
    \bitheader{0,7-8,15-16,23-24,31} \\

    \bitbox{8}{\hyperlink{synchro}{synchro}} &
    \bitbox{24}{\hyperlink{tri-state}{tri-state bitmask{[12]}}} \\

    \bitbox{16}{\hyperlink{msg-seq}{message sequence number}} &
    \bitbox{16}{\hyperlink{packet-seq}{packet sequence number}}
  \end{bytefield}
  \caption{Message acceptance record}
  \label{fig:msg-accept}
\end{figure}

   Each element of the array is two bits in length and may have one of
   three values: accepted(0), pending(1) or rejected(2). Initially, the
   bit mask is set to all zeros. When the token for message $m$ is
   transmitted, the first (left-most) element of the vector represents
   the the state of message $m - 1$, the second element of the vector is
   the status of message $m - 2$, and so forth. Therefore the status of
   the last 12 messages are visible, the status of older messages are
   lost, logically by shifting the elements out of the vector. Only the
   master is permitted to set the status of messages. The master is not
   permitted to shift a status of pending beyond the end of the vector.
   If that situation arises, the master must instead not confirm any
   token[request] until the oldest message can be marked as either
   rejected or accepted.

   \hypertarget{msg-seq}{Message sequence numbers are 16 bit unsigned
   values.} The field is initialized to zero by the master when the
   transport is initialized, and incremented by one after each token is
   granted. Only the master is permitted to change the value of the message
   sequence number. Once granted, that message sequence number is consumed
   and the state of the message must eventually become either accepted or
   rejected. No transmit tokens may be granted if the assignment of a
   message sequence number that would cause a value of pending to be
   shifted beyond the end of the status vector.

   \hypertarget{packet-seq}{Packet sequence numbers are unsigned 16 bit
   numbers assigned by the producing process on a per message basis.}
   Packet sequence numbers start at a value of zero for each new message
   and are incremented by one (consumed) for each data packet making up the
   message. Consumers detecting missing packet sequence numbers must send a
   nak[request] to the appropriate producer to recover the missed data.

   Control packets always contain the message acceptance criteria with a
   synchronization flag set to zero (0x00), the highest message sequence
   number observed and a packet sequence number one greater than
   previously observed. Control packets do not consume any sequence
   numbers.  Since control messages are not reliably delivered, the
   acceptance criteria should only be checked to see if they fall within
   the proper range of message numbers, relative to the current message
   number of the receiving station.  The range of acceptable sequence
   numbers should be $m-11$ to $m-13$, inclusive, where $m$ is the current
   message number.

\hypertarget{heartbeat}{\subsubsection{Heartbeat}}

   Heartbeat is an unsigned 32 bit field that has the units of
   milliseconds. The value of heartbeat is shared by all members of the
   web. By definition at least one packet (either data, empty or quit
   from the master) will be multicast into the web within every
   heartbeat period.

\hypertarget{window}{\subsubsection{Window}}

   The allocation window (or simply window) is a 16 bit unsigned field
   that indicates the maximum number of data packets that can be
   multicasted by a member in a single heartbeat. It is the sum of the
   retransmitted and new data packets.

\hypertarget{retention}{\subsubsection{Retention}}

   The retention field is a 16 bit unsigned value that is the number of
   heartbeats for which a producer must retain transmitted client data
   and state for the purpose of retransmission.

\subsection{Transport addresses}

   Associated with each transport are logically three transport service
   access points (TSAP), logically formed by the concatenation of a
   network service access point (NSAP) and a transport connection
   identifier. These TSAPs are the unknown TSAP, the web's multicast
   TSAP and each individual member's TSAP.

\subsubsection{Unknown transport address}

   Stations that are just joining must use the multicast NSAP associated
   with the transport, but are not yet aware of either the web's
   multicast TSAP the master process' TSAP\@. Therefore, joining stations
   fabricate a temporary TSAP (referred to as a unknown TSAP) by using a
   connection identifier reserved to mean unknown (0x00000000). The
   join[confirm] message will be sourced from the master's TSAP and will
   include the multicast transport connection identifier in the data
   field. Those values must be extracted from the join[confirm] and
   remembered by the joining process.

\subsubsection{Web's multicast address}

   The multicast TSAP is formed by logically concatenating the multicast
   NSAP associated with the transport creation and the transport
   connection identifier returned in the data field of the join[confirm]
   packet. If more than one network is involved in the web, then the
   multicast transport address becomes a list, one for each network
   represented.  This list is supplied in the data field of
   token[confirm] packets.

   The multicast TSAP is used as the target for all messages that are
   destined to the entire web, such as data and empty. The master's
   decision to abandon the transport (quit) is also sent to the
   multicast transport address.

\subsubsection{Member addresses}

   The member TSAP is formed by using the process' unicast NSAP
   concatenated with a locally generated unique connection identifier.
   That TSAP must be the source of every packet transmitted by the
   process, regardless of its destination, for the lifetime of the
   transport.

   Packets unicast to specific members must contain the appropriate
   TSAP\@.  For producers and consumers this is not difficult. The only
   TSAPs of interest are the master and the station(s) currently
   transmitting data.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{AFM91}
\bibitem[AFM91]{Armstrong91}
S.~Armstrong, A.~Freier, and K.~Marzullo.
\emph{MTP: An atomic multicast transport protocol}.
Xerox Webster Research Center technical report X9100359,
March 1991.

\bibitem[AFM92]{Armstrong92}
S.~Armstrong, A.~Freier, and K.~Marzullo.
\emph{Multicast transport protocol}.
RFC 1301, Internet Engineering Task Force, February 1992.
Available from \url{http://www.rfc-editor.org/rfc/rfc1301.txt}.
\end{thebibliography}

\end{document}