Protocol link layer

PRIORITY CLAIM

0001This application is a Continuation of U.S. Utility Application entitled “Protocol Link Layer,” having application Ser. No. 12/278,145, filed on Aug. 1, 2008, and completed on May 18, 2009, which is a U.S. National Stage application of International Application No. PCT/US07/61487, entitled “Protocol Link Layer,” filed Feb. 1, 2007, which claims the benefit of U.S. Provisional Application, entitled “Protocol Link Layer” having Application Ser. No. 60/763,959, filed Feb. 1, 2006, which is related to U.S. Provisional Application entitled “Protocol Circuit Layer” having Application Ser. No. 60/763,977, filed Feb. 1, 2006, and U.S. Provisional Application, entitled “Congestion Management and Latency Prediction in CSMA Media” having Application Ser. No. 60/764,013, filed Feb. 1, 2006. Accordingly, the present application claims priority to and the benefit of the filing dates of U.S. application Ser. No. 12/278,145, International Application No. PCT/US07/61487, Provisional Application No. 60/763,959, Provisional Application No. 60/763,977, and Provisional Application No. 60/764,013, which are all incorporated by reference herein in their entirety.

BACKGROUND

0002Computers have been networked to exchange data between them for decades. One important network, the Internet, comprises a vast number of computers and computer networks interconnected through communication channels. The Internet is used for various reasons, including electronic commerce, exchanging information such as electronic mail, retrieving information and doing research, and the like. Many standards have been established for exchanging information over the Internet, such as electronic mail, Gopher, and the World Wide Web (“WWW”). The WWW service allows a server computer system (ie., web server or web site) to send graphical web pages of information to a remote client computer system. The remote client computer system can then display the web pages. Each resource (e.g., computer or web page) of the WWW is uniquely identifiable by a Uniform Resource Locator (“URL”). To view a specific web page, a client computer system specifies the URL for that web page in a request (e.g., a HyperText Transfer Protocol (“HTTP”) request). The request is forwarded to the web server that supports that web page. When that web server receives the request, it sends the requested web page to the client computer system. When the client computer system receives that web page, it typically displays the web page using a browser. A browser is typically a special purpose application program for requesting and displaying web pages.

0003Currently, web pages are often defined using HyperText Markup Language (“HTML”). HTML provides a standard set of tags that define how a web page is to be displayed. When a user makes a request to the browser to display a web page, the browser sends the request to the server computer system to transfer to the client computer system an HTML document that defines the web page. When the requested HTML document is received by the client computer system, the browser displays the web page as defined by the HTML document. The HTML document contains various tags that control the display of text, graphics, controls, and other features. The HTML document may contain URLs of other web pages available on that server computer system or on other server computer systems.

0004New protocols exist, such as Extensible Mark-up Language (“XML”) and Wireless Access Protocol (“WAP”). XML provides greater flexibility over HTML. WAP provides, among other things, the ability to view web pages over hand-held, wireless devices, such as cell phones and portable computers (e.g. PDA's). All of these protocols provide easier ways to provide information to people via various data processing devices. Many other protocols and means for exchanging data between data processing devices continue to develop to further aid the exchange of information.

BRIEF DESCRIPTION OF THE DRAWINGS

0005<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram illustrating the relationship of the link layer to the other layers of the CoCo Protocol Suite in some embodiments.

0006<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram illustrating the relationship of various layers in the CoCo Protocol Suite in various embodiments.

0007<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram illustrating a detailed view of the link layer protocols in some embodiments.

0008<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram illustrating a CoCo protocol header in some embodiments.

0009<figref idref="DRAWINGS">FIG. 5</figref> is a block diagram illustrating a packet format that is employed by a link setup sublayer in some embodiments.

0010<figref idref="DRAWINGS">FIG. 6</figref> is a block diagram illustrating a link setup packet in some embodiments.

0011<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram illustrating an acknowledgement section of the Link Setup Packet in some embodiments.

0012<figref idref="DRAWINGS">FIG. 8</figref> is a block diagram illustrating an encoding section of a link setup packet in some embodiments.

0013<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram illustrating a public key section of a link setup packet in some embodiments.

0014<figref idref="DRAWINGS">FIG. 10</figref> is a flow diagram illustrating how to determine roundtrip times and reception quality in some embodiments.

0015<figref idref="DRAWINGS">FIG. 11</figref> is a state diagram showing link states in various embodiments.

0016<figref idref="DRAWINGS">FIG. 12</figref> is a block diagram illustrating a link data packet in some embodiments.

0017<figref idref="DRAWINGS">FIG. 13</figref> is a block diagram illustrating multicasting in some embodiments.

0018<figref idref="DRAWINGS">FIG. 14</figref> is a block diagram, illustrating a destination set section of a link data packet in some embodiments.

0019<figref idref="DRAWINGS">FIG. 15</figref> is a flow diagram illustrating a technique for folding hash values used in some embodiments.

0020<figref idref="DRAWINGS">FIG. 16</figref> is a block diagram illustrating a signature field section of a data link packet in some embodiments.

0021<figref idref="DRAWINGS">FIG. 17</figref> is a block diagram illustrating a packet information section of a data link packet in some embodiments.

0022<figref idref="DRAWINGS">FIG. 18</figref> is a block diagram, illustrating a fragmentation section of a link data packet in some embodiments.

0023<figref idref="DRAWINGS">FIG. 19</figref> is a block diagram illustrating fields in an acknowledgement section of a link data packet in some embodiments.

DETAILED DESCRIPTION

The Link Concept

0024A link is a software abstraction that represents a direct connection between two CoCo nodes. The principle task of the link layer is to detect the presence of neighboring CoCo devices and establish links to them.

Description of Link Layer Protocol Functionality

0025Link establishment employs a variation on the traditional three-way handshake protocol (packets containing “hello,” “hello-ack,” and “final-ack”; see [1SI]). Link establishment includes the negotiation of an encoding method and a DiffieHellman key exchange so that all communication sent over the link may be cryptographically check-summed [S]. This ensures consistency of identity; that is, a node is guaranteed that all packets received over a link came from the node with which it established that link.

0026Once a link is established, the link layer <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0027">Relays packets between the network interface layer and higher protocol layers (the routing and circuit layers).</li><li id="ul0002-0002" num="0028">Monitors Quality of Service (QoS) statistics and is able to report these to higher protocol layers.</li><li id="ul0002-0003" num="0029">Supports multicasting by suppressing redundant packet transmission across a single network interface.</li><li id="ul0002-0004" num="0030">Performs fragmentation when packet sizes exceed the network interface Maximum Transmission Unit (MTU).</li><li id="ul0002-0005" num="0031">Closes inactive links to free system resources for new link requests.</li></ul></li></ul>

The Link Layer in the Context of Other Protocol Layers

0032<figref idref="DRAWINGS">FIG. 1</figref> illustrates the relationship of the link layer to the other layers of the CoCo Protocol Suite. The CoCo Protocol Suite layers are shown with italic font in <figref idref="DRAWINGS">FIG. 1</figref>.

0033More details about the routing layer, circuit layer, and naming system layer may be found, respectively, in commonly owned U.S. patent application Ser. No. 12/160,597 (hereinafter referred to as “[BLMS]”), commonly owned U.S. patent application Ser. No. 12/278,144 (hereinafter referred to as “[BMV]”), and commonly owned U.S. patent application Ser. No. 12/160,599 (hereinafter referred to as “[BELM]”). The network interface layer is the operating system's device driver for a physical network device such as an Ethernet card.

Components of the Link Layer

0034<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram illustrating the relationship of various layers in the CoCo Protocol Suite. The link layer connects to the network interface layer and is comprised of the following components: <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0035">The Protocol Abstraction Layer (PAL), which converts the incoming data frames that arrive on network interfaces into packet objects used by the CoCo Protocol Suite.</li><li id="ul0004-0002" num="0036">The link setup sublayer, which establishes links with neighboring nodes in a CoCo network.</li><li id="ul0004-0003" num="0037">The link data sublayer, which transfers data across established links.</li><li id="ul0004-0004" num="0038">The QoS handler, which monitors the quality of links.</li></ul></li></ul>

0039<figref idref="DRAWINGS">FIG. 3</figref> gives a more detailed view of the link layer protocols, including their interfaces. Each arrow in <figref idref="DRAWINGS">FIG. 3</figref> represents a function call that is part of the interface. An arrow from layer A to layer B indicates a procedure or function in layer B is called from layer A. A circle at the tail of an arrow indicates a function that returns a value to the caller.

Link Layer Interface

0040The link layer interface offers the following functions, which the routing and circuit layers use to determine the presence and absence of links, and to send and receive packets over links: <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0000"><ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0041">LinkUp(link)</li></ul></li></ul>

0042The link layer calls LinkUp(link) to inform the circuit and routing layers that a link has opened. <ul id="ul0007" list-style="none"><li id="ul0007-0001" num="0000"><ul id="ul0008" list-style="none"><li id="ul0008-0001" num="0043">LinkDown(link)</li></ul></li></ul>

0044The link layer calls LinkDown (link) to inform the circuit and routing layers that a link has closed. <ul id="ul0009" list-style="none"><li id="ul0009-0001" num="0000"><ul id="ul0010" list-style="none"><li id="ul0010-0001" num="0045">Receive(packet,link)</li></ul></li></ul>

0046The link layer calls Receive (packet, link) to inform the circuit and routing layers that a packet arrived over a link. <ul id="ul0011" list-style="none"><li id="ul0011-0001" num="0000"><ul id="ul0012" list-style="none"><li id="ul0012-0001" num="0047">Send(packet, link)</li></ul></li></ul>

0048The circuit or routing layer calls Send (packet, link) to send a packet over a link. <ul id="ul0013" list-style="none"><li id="ul0013-0001" num="0000"><ul id="ul0014" list-style="none"><li id="ul0014-0001" num="0049">GetQos(link)</li></ul></li></ul>

0050The circuit or routing layer calls GetQos (link) to obtain the QoS metrics associated with the given link.

Link Layer Packet Types

0051After the PAL parses the incoming data frames, it discards the network interface header; the data that remains is either a link setup packet or a link data packet. <ul id="ul0015" list-style="none"><li id="ul0015-0001" num="0000"><ul id="ul0016" list-style="none"><li id="ul0016-0001" num="0052">Link setup packet: A link setup packet contains information necessary to establish a link. Its packet header is the entire link setup packet; there is no separate data portion of a link setup packet. Link setup packets are used only within the link layer.</li><li id="ul0016-0002" num="0053">Link data packet: In addition to actual user data (and any data relevant to higher protocol layers), link data packets contain extra fields to handle data packet acknowledgements, data packet fragmentation, and a cryptographic checksum. Link data packets are forwarded to the routing and circuit layers.</li></ul></li></ul>

Protocol Abstraction Layer

0054The Protocol Abstraction Layer (PAL) of the link layer parses the incoming data frames that arrive on network interfaces (such as Ethernet or Satellite interfaces), uses that data to create a CoCo header and address translation table, and then discards the header of the network interface data frame. After the network interface header is discarded, the data that remains is either a link setup packet or a link data packet. The link layer examines these packets and sends link setup packets to the link setup sublayer and link data packets to the link data sublayer.

0055To summarize, the PAL: <ul id="ul0017" list-style="none"><li id="ul0017-0001" num="0000"><ul id="ul0018" list-style="none"><li id="ul0018-0001" num="0056">Gets data frames from a network device or connection.</li><li id="ul0018-0002" num="0057">Constructs a CoCo header and address translation table that capture relevant information from the network interface layer (which is typically a device driver for a network device such as an Ethernet card).</li><li id="ul0018-0003" num="0058">Removes and discards the network interface layer header.</li><li id="ul0018-0004" num="0059">Passes the modified packet to either the link setup sublayer or the link data sublayer.</li></ul></li></ul>

The CoCo Header and Address Translation Table

0060The CoCo header and address translation table are replacements for the header from the network interface layer. The PAL creates them after receiving a packet from the network interface. When a frame arrives from any physical network interface, the PAL reads the frame header to construct a CoCo header and add an entry to its address translation table.

0061The address translation table exists only in memory and is used only by the PAL. The PAL extracts the source address from the frame header and associates it with the universal node identifier (UNI) of the source node, storing the association in an address translation table. An address translation table is created for each type of physical transport used by the node. The UNI is then used throughout the CoCo Protocol; the address translation table may be needed only when data is sent to the network interface layer. (See [BLMS] for more information about UNIs.)

0062The format of the CoCo header is uniform—it is the same regardless of which interface type the packet arrived on. The CoCo header is stored in memory and is available to higher protocol layers; its structure is shown in <figref idref="DRAWINGS">FIG. 4</figref>, with the bit size of each field given in parentheses.

0063The Type field describes the type of packet that follows the CoCo header—either a link setup packet or a link data packet. The Encrypt field describes whether or not the packet is encrypted. Since encryption may not happen until after a link has been established, all link setup packets are unencrypted; all broadcast packets are also unencrypted because of the difficulty of encrypting a message that would be decrypted by multiple nodes. The Packet Size field is the size in bytes of the entire packet that follows the CoCo header.

0064CoCo nodes also send the CoCo header over the physical network interface to act as a check on the packet integrity. After the PAL composes the CoCo header in the usual manner, the results are checked against the CoCo header that was sent over the wire; if they do not match, the packet is discarded.

0000Transports that the PAL Supports

0065The PAL supports numerous network interface formats, including: <ul id="ul0019" list-style="none"><li id="ul0019-0001" num="0000"><ul id="ul0020" list-style="none"><li id="ul0020-0001" num="0066">Ethernet (IEEE 802.3)</li><li id="ul0020-0002" num="0067">Token-ring (IEEE 802.5)</li><li id="ul0020-0003" num="0068">Wi-Fi (IEEE 802.11)</li><li id="ul0020-0004" num="0069">Synchronous Optical Network (SONET)</li><li id="ul0020-0005" num="0070">Asynchronous Transfer Mode (ATM)</li><li id="ul0020-0006" num="0071">Satellite</li></ul></li></ul>

0072Because other transport technologies use the network interface formats listed previously, the link layer also supports: <ul id="ul0021" list-style="none"><li id="ul0021-0001" num="0000"><ul id="ul0022" list-style="none"><li id="ul0022-0001" num="0073">Internet Protocol (IP)</li><li id="ul0022-0002" num="0074">Transmission Control Protocol (TCP)</li><li id="ul0022-0003" num="0075">User Datagram Protocol (UDP)</li><li id="ul0022-0004" num="0076">Global System for Mobile Communications (GSM) and Code Division Multiple Access (CDMA)</li><li id="ul0022-0005" num="0077">Cellular Digital Packet Data (CDPD)</li><li id="ul0022-0006" num="0078">General Packet Radio Service (GPRS), and 1XRTT</li></ul></li></ul>

0079The PAL can be easily extended to support other formats because of its modular design.

Link Setup Sublayer

0080The link setup sublayer performs the following functions: <ul id="ul0023" list-style="none"><li id="ul0023-0001" num="0000"><ul id="ul0024" list-style="none"><li id="ul0024-0001" num="0081">Discovers the presence and maintains awareness of other nodes</li><li id="ul0024-0002" num="0082">Establishes links to nodes within range</li><li id="ul0024-0003" num="0083">Establishes a Diffie-Hellman key for each link</li><li id="ul0024-0004" num="0084">Establishes an encoding method for each link</li><li id="ul0024-0005" num="0085">Computes and verifies work tokens to resist denial-of-service attacks</li><li id="ul0024-0006" num="0086">Monitors round-trip times for each link</li><li id="ul0024-0007" num="0087">Determines when links are inactive and closes them</li></ul></li></ul>

0088The link setup sublayer uses an iterative, two-phase process for nodes to exchange information to accomplish the preceding functions.

Link Setup Packet

0089The link setup sublayer uses a single packet format, as is illustrated in <figref idref="DRAWINGS">FIG. 5</figref>, that is referred to as a link setup packet.

0090The link setup packet provides a mechanism for a node to announce its presence and identity to other nodes, and to simultaneously inform other nodes that it has heard such announcements from them. Therefore, in some contexts the link setup packet acts as a hello packet, and in other contexts it acts as an acknowledgement, or ack packet.

0091To facilitate the dynamic addition and deletion of nodes on the network, each node broadcasts a link setup packet at fixed time intervals. This also makes it possible for the link setup packet to serve as both a hello and an ack in the same packet. This fixed time interval is called the hello interval and is typically one second. Acknowledgements are piggybacked onto outgoing hello packets. Each node maintains a set of nodes called the ack-set from which it has received a hello within a fixed time interval called the ack-interval, approximately 5-10 seconds.

0092The ack-interval is a link timeout parameter; if a node A does not receive any hello packets from node B for ack-interval or longer, it drops B from its ack-set and no longer acknowledges B in its outgoing hello messages.

0093To prevent security attacks from packet floods, each node computes a work token that is included in every link setup packet. A work token is valid for an amount of time called the work token validity interval (WTVI), which is typically a length of time greater than the hello interval but less than the ack-interval. When a work token expires (based on the WTVI), a new work token should be computed by the node before sending out its next link setup packet.

0094A fourth time interval used by the link layer is the Diffie-Hellman cache interval (DHCI), which should be greater than the WTVI and should also be longer than the ack-interval. The DHCI is the length of time that a node A keeps a cached version of the Diffie-Hellman key it uses to communicate with node B. Because computing the Diffie-Hellman key is resource intensive, it is useful to keep a cached version of the key even after the link has been dropped, in case node B tries to re-establish its link to node A. If node A does not receive a link setup packet from node B within the DHCI, node A purges its cached copy of the key.

0095The link setup packet—separated by section—is shown in <figref idref="DRAWINGS">FIG. 5</figref>, where dashed lines indicate sections of the packet that can be repeated, and numbers in parentheses indicated the bit-size of each field.

0096The link setup packet contains the following sections: <ul id="ul0025" list-style="none"><li id="ul0025-0001" num="0000"><ul id="ul0026" list-style="none"><li id="ul0026-0001" num="0097">Link establishment fields</li><li id="ul0026-0002" num="0098">A set of acknowledgments and associated fields (the ack-set)</li><li id="ul0026-0003" num="0099">A list of supported encodings</li><li id="ul0026-0004" num="0100">The public key of the node</li></ul></li></ul>

Link Establishment Section of the Link Setup Packet

0101The initial fixed-length portion of the link setup packet, illustrated in <figref idref="DRAWINGS">FIG. 6</figref>, is comprised of the following fields:

0102Work Token (<b>128</b>) The random number that is used for work token validation, as described in the “Work Token” section. This helps prevent denial-of-service attacks. A work token is valid only for a length of time determined by the work token validity interval, after which a new work token should be computed.

0103TimeStamp (<b>64</b>) The time (using us time data format) at which the work token was computed. This field is updated every work token validity interval, rather than at every hello interval.

0104UNI (<b>64</b>) The universal node identifier (UNI) that uniquely identifies this CoCo node. It is an unranked UNI; see [BLMS] for more information.

0105HelloNum (<b>32</b>) A sequence number that increments with every link setup packet sent by this CoCo node. Link setup packets are broadcast at regular intervals called the hello interval.

0106NumAcks (<b>16</b>) The number of acknowledgements that are piggybacked onto this packet.

0107NumEncodings (<b>16</b>) The number of encodings that the sending CoCo node supports.

Acknowledgement Section of the Link Setup Packet

0108<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram illustrating an acknowledgement section of the Link Setup Packet in some embodiments.

0109This set of fields contains the acknowledgement of the receipt of link setup packets from another CoCo node. These acknowledgements are piggybacked onto the link establishment section of the link setup packet. There can be several acknowledgements in a single link setup packet, each acknowledging the receipt of a link setup packet from a different CoCo node. The number of acknowledgements in a link setup packet is given by the NumAcks field of the link establishment section (see <figref idref="DRAWINGS">FIG. 6</figref>). Each acknowledgement is comprised of the following set of fields:

0110Node Acked (<b>64</b>) The universal node identifier (UNI) of the node being acknowledged.

0111HelloNum Last Heard (<b>32</b>) The HelloNum of the last packet received from node being acknowledged.

0112Hold Time (<b>32</b>) The time elapsed since the arrival of the last packet from the node being acknowledged; see <figref idref="DRAWINGS">FIG. 10</figref>.

0113Ack Signature (<b>64</b>) A hash of the Diffie-Hellman key negotiated between this CoCo node and the CoCo node of the packet being acknowledged, used to prevent spoofing of acks. The hash function that is used is negotiated by that pair of nodes as explained in the “Encoding and Security” section below.

Encoding Section of the Link Setup Packet

0114<figref idref="DRAWINGS">FIG. 8</figref> is a block diagram illustrating an encoding section of a link setup packet. This section comprises a sequence of Encoding fields, one for each pair of encryption/hash encoding methods that the source node supports. The number of Encoding fields in a link setup packet is given by the NumEncodings field of the link establishment section (see <figref idref="DRAWINGS">FIG. 6</figref>). Each Encoding field is comprised of the following subfields:

0115Encryption (<b>4</b>) A 4-bit identifier for the encryption method to be used with its associated Hash as an encoding pair. Encryption methods currently supported are RC4, DES, 3DES, Blowfish, and AES.

0116Hash (<b>4</b>) A 4-bit identifier for the hashing method to be used with its associated Encryption as an encoding pair. The hashing methods currently supported are MD5, SHA1, and RIPEMD

0117Reserved (<b>8</b>) Reserved for future use.

Public Key Section of the Link Setup Packet

0118<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram illustrating a public key section of a link setup packet.

0119PublicKey Size (<b>16</b>) The size, in bytes, of the Public Key field.

0120Public Key (variable; commonly <b>512</b>) The public key used for the Diffie-Hellman key exchange; see the “Encoding and Security” section.

Determining Roundtrip Times and Reception Quality

0121<figref idref="DRAWINGS">FIG. 10</figref> is a flow diagram illustrating how to determine roundtrip times and reception quality.

0122The link setup sublayer enables each node to determine: <ul id="ul0027" list-style="none"><li id="ul0027-0001" num="0000"><ul id="ul0028" list-style="none"><li id="ul0028-0001" num="0123">Roundtrip times to every other node.</li><li id="ul0028-0002" num="0124">The quality of the signals from other nodes.</li><li id="ul0028-0003" num="0125">The quality of its own signal, as perceived by other nodes.</li></ul></li></ul>

0126For a node A to compute the roundtrip time to a node B, node A notes the time elapsed between the time it sends a setup packet to node B and the time it receives a link setup packet from node B acknowledging setup (checking that the value of hello-num is the same), and then subtracts the hold time that appears in that acknowledgement.

0127In addition to roundtrip time computation, the link setup layer can determine signal quality based on the percentage of link setup packets that it sends which are later acknowledged. For example, if node B receives hello packets from node A numbered 1, 2, 3, 4, . . . then it knows that it has a strong signal from node A. On the other hand, if node B receives hello packets from node A numbered 4, 9, 15, 23, . . . then it knows that the signal from node A is relatively weak. Similarly, if node A receives acknowledgements from node B and A's hello packets contain gaps in the numbered sequence, (for example, 5, 11, 17, 21, . . . ) then node A knows that the signal from node B is weak, its signal to node B is weak, or both.

Encoding and Security

0128The encoding and security of the link layer relies upon a Diffie-Hellman key exchange between nodes, as well as the exchange of work tokens to prevent denial-of-service attacks.

Work Tokens

0129A rogue node could mount denial-of-service attacks against a network by: <ul id="ul0029" list-style="none"><li id="ul0029-0001" num="0000"><ul id="ul0030" list-style="none"><li id="ul0030-0001" num="0130">Flooding nodes within its range with link setup requests.</li><li id="ul0030-0002" num="0131">Simulating the existence of a multitude of fake nodes.</li></ul></li></ul>

0132These actions constitute an attack since nodes that receive link setup requests should perform a Diffie-Hellman key-exchange computation, which is resource intensive (approximately one millisecond on a 400 MHz XScale processor). In the presence of a large number of malicious establishment requests, link establishment requests from legitimate nodes may be delayed or denied altogether due to timeouts.

0133Therefore, the link setup protocol uses a mechanism called a work token to force nodes attempting to establish a link to perform a nontrivial computation. This makes such denial-of-service attacks more costly for the attacker, lessening their likelihood or preventing them altogether, depending on the attacker's computational resources.

0134Because of these considerations, validating a work token precedes the Diffie-Hellman computation. If the work token is invalid, the node may not devote time computing a Diffie-Hellman key, which is a much more expensive computation than the work token verification.

0135Before node A can send a link setup packet to node B, node A should compute a valid work token, W, which it places in the work token field of its link setup packet (see <figref idref="DRAWINGS">FIG. 6</figref>).

0136This timestamp T is also included in the link setup packet (see <figref idref="DRAWINGS">FIG. 6</figref>). Upon receipt of the link setup packet, node B uses the timestamp to determine whether the work token has expired (and is therefore invalid).

Work Token Algorithms

0137In the following work token algorithms, the function h is a global hash function set within the protocol source code that is used by all CoCo nodes. The outputs of h are distributed uniformly across its range [0, MAX].

0138The value r in Step 3.b of the following algorithms is chosen to be small relative to MAX. This value r is set at the time of network provisioning and can be chosen for a particular deployment as a way of calibrating the tradeoff between security and efficiency of this protocol. This is because Step 3.b succeeds probabilistically with MAX/r expected iterations, since the outputs of h are uniformly distributed over its range.

0139The notation (Z, Y) used in the following algorithms indicates string concatenation of the binary representations of Z and Y.

Work Token Computation

0140Node A should ensure that all link setup packets it sends out contain a valid work token. If the time difference between the current time and the timestamp, T, of its most recently-sent packet is less than the work token validity interval, node A resends its most recent packet. Otherwise, the previously-sent work token is now invalid and should be recomputed by performing the following steps: <ul id="ul0031" list-style="none"><li id="ul0031-0001" num="0000"><ul id="ul0032" list-style="none"><li id="ul0032-0001" num="0141">1. Node A identifies itself by setting the UNI field of its link setup packet (see <figref idref="DRAWINGS">FIG. 6</figref>) to its name, N.</li><li id="ul0032-0002" num="0142">2. Node A sets the TimeStamp field of its link setup packet to the current time, T.</li><li id="ul0032-0003" num="0143">3. Node A then <ul id="ul0033" list-style="none"><li id="ul0033-0001" num="0144">a. Chooses a 128-bit random number, X.</li><li id="ul0033-0002" num="0145">b. Tests to see if c=h(X,T,N,X)&lt;r. (The comma represents the concatenation operation.)</li><li id="ul0033-0003" num="0146">c. Repeats Steps 3.a and 3.b until it finds an X such that the resulting c is indeed less than r.</li></ul></li><li id="ul0032-0004" num="0147">4. Node A sets the Work Token field of its link setup packet to the work token, W, which is the successful value of X that was used to complete Step 3.c.</li></ul></li></ul>

0148With a new valid work token now computed, node A sends out the link setup packet, containing the values of W, T, and N in the appropriate fields of the link establishment section of the packet.

1.1.1.1.1 Work Token Validation

0149When node B receives a link setup packet from node A, it should verify that the work token is valid before continuing with its link establishment to node A. Because verifying the work token is much faster than computing the Diffie-Hellman key, overhead is reduced because not all link setup packets will contain a valid work token and resources will not be wasted on computing a Diffie-Hellman key for those packets. In addition, by silently ignoring all link setup packets that contain invalid work tokens, the protocol reduces the number of packets it uses, and hence the overall traffic overhead induced by the protocol is also reduced. Silently ignoring the failures also reduces exposure to attacks, since the less activity the protocol generates, the fewer the opportunities there are to exploit it.

0150Each node B maintains a cache of previously-calculated Diffie-Hellman keys for each node A from which it has received valid link setup requests. This ensures that node B may not need to recalculate the Diffie-Hellman key in the case where its acknowledgment to node A gets lost. The cached key can also be use to quickly re-establish recently dropped links. Node B eventually purges its cached key for node A if it receives no link setup packets from node A for a duration of time that exceeds the Diffie-Hellman cache interval.

0151To verify that the work token in the link setup packet from node A is valid, node B performs the following: <ul id="ul0034" list-style="none"><li id="ul0034-0001" num="0000"><ul id="ul0035" list-style="none"><li id="ul0035-0001" num="0152">1. Node B extracts W, T, and N from the Work Token, Time Stamp, and UNI fields, respectively, of the link setup packet it received from node A; see <figref idref="DRAWINGS">FIG. 6</figref>.</li><li id="ul0035-0002" num="0153">2. Node B checks whether the work token has expired, based on the timestamp, T, in the link setup packet, the current time, and the work token validity interval. <ul id="ul0036" list-style="none"><li id="ul0036-0001" num="0154">a. If the work token has expired, node B ignores the link setup request because node A might be attempting a packet flood attack or a reply attack by using previously-valid values of W and T</li><li id="ul0036-0002" num="0155">b. If the work token has not expired, node B continues with the verification process.</li></ul></li><li id="ul0035-0003" num="0156">3. Node B checks whether it has a cached Diffie-Hellman key from node A. <ul id="ul0037" list-style="none"><li id="ul0037-0001" num="0157">a. If a cached key for node A exists, node B acknowledges node A in the next link setup packet it sends out, setting the Ack Signature field (see <figref idref="DRAWINGS">FIG. 7</figref>) to the hashed key in its cache.</li><li id="ul0037-0002" num="0158">b. If a cached key for node A does not exist, node B continues with the verification process.</li></ul></li><li id="ul0035-0004" num="0159">4. Node B computes v=h(W,T,N,W). (The comma represents the concatenation operation.) The value of v should be the same as the successful value of c that was computed in Step 3.b of the work token computation (described previously), and therefore v should be less than r. <ul id="ul0038" list-style="none"><li id="ul0038-0001" num="0160">a. If v≧r, node B ignores the link setup request because node A has not sent a valid work token and therefore might be a rogue node.</li><li id="ul0038-0002" num="0161">b. If v&lt;r, node A has sent a valid work token so node B continues with the link setup process.</li></ul></li></ul></li></ul>

0162With a valid work token verified, node B is ready to continue with the link setup process by acknowledging the link setup packet it received from node A.

Acknowledging a Link Setup Request

0163After verifying that node A sent a valid work token, node B continues with the link setup. If node B does not already have a cached value of the Diffie-Hellman key for its link with node A (see Step 3 of the work token validation algorithm), it performs the following steps: <ul id="ul0039" list-style="none"><li id="ul0039-0001" num="0000"><ul id="ul0040" list-style="none"><li id="ul0040-0001" num="0164">1. Node B computes the Diffie-Hellman key for its link with node A. See the section “Diffie-Hellman Key Exchange” for more information.</li><li id="ul0040-0002" num="0165">2. Node B caches the Diffie-Hellman key with the UNI that identifies node A. Because node A regularly broadcasts its link setup hello packet and node B acknowledges each hello it receives from node A, it can be useful to keep a cached version of the Diffie-Hellman key.</li><li id="ul0040-0003" num="0166">3. Node B establishes an encryption and hashing function pair for the link. See the section “Establishing Link Encryption and Hashing” for more information.</li><li id="ul0040-0004" num="0167">4. Node B acknowledges node A in the next link setup packet it broadcasts, setting the Ack Signature field (see <figref idref="DRAWINGS">FIG. 7</figref>) to the hashed Diffie-Hellman key it computed. This enables node A to quickly authenticate the acknowledgement, preventing a rogue node from spoofing acks, which would keep unused links open and degrade performance because of all the extra acks that node A would need to include in its link setup packets.</li></ul></li></ul>

Diffie-Hellman Key Exchange

0168Because the Diffie-Hellman key exchange is a component to the security and encoding of the link layer, this section provides a brief overview of the process.

0169Nodes A and B agree on a prime number, p, and a generator, g, modulo p. (The values p and g are supplied to each device at provision time and can be publicly known.) Node A chooses a private key a; node B chooses a private key β (α and β are each between 1 and p−1). CoCo nodes may be supplied with private keys at provision time, or they may choose a private key at startup time by any of several standard methods (see the section “Generating Keys” in [S]). The key exchanged between the two nodes is computed as follows: <ul id="ul0041" list-style="none"><li id="ul0041-0001" num="0000"><ul id="ul0042" list-style="none"><li id="ul0042-0001" num="0170">1. Node A sends node B its public key—the value P_A=g^α (sent in the link setup hello packet from A to B in the public key field; see <figref idref="DRAWINGS">FIG. 9</figref>).</li><li id="ul0042-0002" num="0171">2. Node B sends node A its public key—the value P_B=g^β (sent in the link setup ack packet from B to A in the public key field; see <figref idref="DRAWINGS">FIG. 9</figref>).</li><li id="ul0042-0003" num="0172">3. Node A computes (P_B)^α=(g^β)^α</li><li id="ul0042-0004" num="0173">4. Node B computes (P_A)^β=(g^α)^β</li><li id="ul0042-0005" num="0174">5. These two values from Steps 3 and 4 are the same, so it can be referred to as k_DH(AB), or simply k if the context is understood. This value is known to both A and B, and to no one else, since determining α from g^α is computationally infeasible (see [S]). Therefore A and B can use it as a secret key for the encryption method they will use for all data sent over the link between them (see “Establishing Link Encryption and Hashing”). <br /> Continuity of Identity after a Diffie-Hellman Key Exchange </li></ul></li></ul>

0175After an exchange of link setup packets and the Diffie-Hellman key between nodes A and B, each node knows that the other should have had a valid private key. The key k_DH(AB)is then used throughout the session in which this link is used, so there can be no man-in-the-middle attacks once a session begins. Any man-in-the-middle attack should have happened prior to link establishment and should last for the lifetime of the link. The Diffie-Hellman key exchange guarantees continuity of identity; that is, once a node begins communicating over a link, it is guaranteed to be talking to the same node for the duration of the link session.

Establishing Link Encryption and Hashing

0176Each node maintains an ordered list of encodings it supports. Each encoding in the list represents an encryption method paired with a hashing function. When a node sends a link setup packet, it includes the encodings that appear in this list in the encoding section of the packet (refer to <figref idref="DRAWINGS">FIG. 5</figref> and <figref idref="DRAWINGS">FIG. 8</figref>). The encodings appear in the link setup packet in the same order they appear in its ordered list.

0177After node A sends a link setup (hello) packet to node B and node B sends a link setup ack packet to node A, nodes A and B each have a list of the paired encryption methods and hash functions supported by the other, ordered by preference. Nodes A and B each perform the following steps to determine which of these encoding methods to use over the newly established A-B link. <ul id="ul0043" list-style="none"><li id="ul0043-0001" num="0000"><ul id="ul0044" list-style="none"><li id="ul0044-0001" num="0178">1. Determine whether node A or node B is the preferential encoder (see the following section).</li><li id="ul0044-0002" num="0179">2. Pick the encoding method highest on the preferential encoder's list that also appears on the list of the other node. If no match is found, communication occurs over this link unencrypted. (If security requirements demand that no data be transmitted over an unencrypted link, the circuit used for the data transmission will never incorporate an unencrypted link; see [BMV] for more information.)</li></ul></li></ul>

0180This link encoding selection algorithm is efficient because it requires the receipt of only a single packet by each participant.

Algorithm to Determine the Preferential Encoder

0181This algorithm is a deterministic process by which both nodes A and B conclude by agreeing on the outcome. Nodes A and B perform this algorithm by comparing (P_A−P_B) modulo p and (P_B−P_A) modulo p. If the former is larger, node A is the preferential encoder; if the latter is larger, node B is the preferential encoder. Here, P_Aand P_Bare the Diffie-Hellman public keys of nodes A and B, respectively, and p is the prime modulo that is used to perform the Diffie-Hellman computation. Note that this algorithm is deterministic, so both nodes A and B compute the same preferential encoder.

Link State

0182<figref idref="DRAWINGS">FIG. 11</figref> is a state diagram showing possible link states.

0183Every node keeps a link state table, which includes an entry for each node it has heard from that contains: <ul id="ul0045" list-style="none"><li id="ul0045-0001" num="0000"><ul id="ul0046" list-style="none"><li id="ul0046-0001" num="0184">The Diffie-Hellman key used to communicate with that node; see the “Encoding and Security” section.</li><li id="ul0046-0002" num="0185">The last hello-num it received from that node.</li><li id="ul0046-0003" num="0186">The hello-num in the last acknowledgement it has heard from that node.</li></ul></li></ul>

0187Every node also maintains a state machine for each node it has heard from. The state machine on node A manages the state of its link with node B and is called the A-B link state machine. The A-B link state machine for node A can exist in one of four states (see <figref idref="DRAWINGS">FIG. 11</figref>): <ul id="ul0047" list-style="none"><li id="ul0047-0001" num="0000"><ul id="ul0048" list-style="none"><li id="ul0048-0001" num="0188">Blank: node A is not aware of node B.</li><li id="ul0048-0002" num="0189">0-way: node A is aware of node B but has not received a link setup hello from node B. (A knows of B but hasn't heard from B.)</li><li id="ul0048-0003" num="0190">1-way: node A has received a link setup hello from node B but has not received an acknowledgment from node B. (A hears B but doesn't know whether B hears A.)</li><li id="ul0048-0004" num="0191">2-way: node A has received a link setup hellop from node B and has also received an acknowledgement from node B. (A hears B and knows that B also hears A.)</li></ul></li></ul>

0192Node A will send link data packets to node B only when the A-B link state machine is in state 2-way.

0193Let M be the A-B link state machine for node A. The state machine M can change in one of the following six ways: <ul id="ul0049" list-style="none"><li id="ul0049-0001" num="0000"><ul id="ul0050" list-style="none"><li id="ul0050-0001" num="0194">1. M is in state blank or 0-way and node A receives a link setup hello packet from node B, then <ul id="ul0051" list-style="none"><li id="ul0051-0001" num="0195">M transitions to one of the following states: <ul id="ul0052" list-style="none"><li id="ul0052-0001" num="0196">State 1-way if the link setup packet from node B does not contain an ack for node A.</li><li id="ul0052-0002" num="0197">State 2-way if the link setup packet from node B also contains an ack for node A. (This would happen, for example, if node A initiated the link setup with node B).</li></ul></li><li id="ul0051-0002" num="0198">Node A: <ul id="ul0053" list-style="none"><li id="ul0053-0001" num="0199">Validates the work token.</li><li id="ul0053-0002" num="0200">Establishes an encryption and hashing function pair for the link.</li><li id="ul0053-0003" num="0201">Computes and caches a Diffie-Hellman key (if the key is not already cached).</li><li id="ul0053-0004" num="0202">Adds node B to its ack-list.</li></ul></li></ul></li><li id="ul0050-0002" num="0203">2. If M is in state 1-way and node A receives a link setup acknowledgement about itself from node B, then <ul id="ul0054" list-style="none"><li id="ul0054-0001" num="0204">M transitions to state 2-way.</li></ul></li><li id="ul0050-0003" num="0205">3. If M is in state 2-way and node A does not receive an acknowledgement about itself from node B for longer than the ack-interval, then <ul id="ul0055" list-style="none"><li id="ul0055-0001" num="0206">M transitions to state 1-way.</li></ul></li><li id="ul0050-0004" num="0207">4. If M is in state 1-way or 2-way and node A does not receive a link setup hello from node B for longer than ack-interval, then <ul id="ul0056" list-style="none"><li id="ul0056-0001" num="0208">M transitions to state 0-way.</li><li id="ul0056-0002" num="0209">Node A removes node B from its ack-list.</li></ul></li><li id="ul0050-0005" num="0210">5. If M is in state 0-way and node A's Diffie-Hellman cache interval expires, then <ul id="ul0057" list-style="none"><li id="ul0057-0001" num="0211">M transitions to state blank.</li><li id="ul0057-0002" num="0212">Node A removes the Diffie-Hellman key for node B from its cache.</li></ul></li><li id="ul0050-0006" num="0213">6. In all states, node A sends at every hello-interval a link setup packet containing an (incremented) hello-num, a time stamp and work token, and acknowledgements for each node it has heard from in the last ack-interval (which have entries in its link state table).</li></ul></li></ul>

Link Data Sublayer

0214The link data sublayer is responsible for getting data from one node to another across an established link, managing data flow, monitoring QoS measurements such as latency and roundtrip times, and performing compression and fragmentation.

Higher Layer Packet Types

0215Any packet that is not a link setup packet is treated by the link layer as data destined for higher protocol layers; in the CoCo Protocol these include the routing layer, circuit layer, and naming system layer. <ul id="ul0058" list-style="none"><li id="ul0058-0001" num="0000"><ul id="ul0059" list-style="none"><li id="ul0059-0001" num="0216">Clustering packets contain information related to clusters, a recursive decomposition of CoCo nodes that permits more efficient routing (see [BLMS]).</li><li id="ul0059-0002" num="0217">Advertising packets contain information about the cost of reaching nodes (see [BLMS]).</li><li id="ul0059-0003" num="0218">Circuit control packets contain information about the establishment and maintenance of circuits, which are dedicated end-to-end communication paths (see [BMV]).</li></ul></li></ul>

The Link Data Packet

0219Unlike link setup packets, link data packets contain user data. The length of the data is not specified in the packet header because the entire packet length is given in the CoCo header that was constructed by the Protocol Abstraction Layer (see <figref idref="DRAWINGS">FIG. 4</figref>). The CoCo header for each data packet is stored in the node's memory so it can be easily accessed by the higher protocol levels that will use the packet data.

0220Before a data packet can be sent between them, a link should be established between nodes A and B. Therefore, nodes A and B will have exchanged link setup packets and will have calculated a Diffie-Hellman key k_DH(AB)that is specific to their link (see the “Diffie-Hellman Key Exchange” section). Nodes A and B will have also negotiated a hashing function h_ABand an encryption method e_ABthat are specific to the A-B link (see the “Establishing Link Encryption and Hashing” section).

0221The entire data packet content is encrypted with the function e_AB. Note that “none” is one of the encryption methods, so if both nodes A and B agreed upon “none” as the encryption method, each of A and B knows not to attempt to encrypt when sending nor decrypt when receiving.

0222The link data packet—separated by section—is shown in <figref idref="DRAWINGS">FIG. 12</figref>, where dashed lines indicate sections of the packet that can be repeated, and numbers in parentheses indicated the field size in bits.

0223The link data packet contains the following sections: <ul id="ul0060" list-style="none"><li id="ul0060-0001" num="0000"><ul id="ul0061" list-style="none"><li id="ul0061-0001" num="0224">Fields used when the data packet is multicast</li><li id="ul0061-0002" num="0225">A signature that serves as a secure checksum of the data packet</li><li id="ul0061-0003" num="0226">Information specific to each data packet</li><li id="ul0061-0004" num="0227">Fragmentation information so the data can be reconstructed if the packet needs to be fragmented</li><li id="ul0061-0005" num="0228">A set of acknowledgments of received data packets</li><li id="ul0061-0006" num="0229">The average hold time of the packets being acknowledged</li><li id="ul0061-0007" num="0230">The actual data that will be either processed by the higher protocol layers or sent to the network interface layer</li></ul></li></ul>

Multicast Section of the Link Data Packet

0231<figref idref="DRAWINGS">FIG. 13</figref> is a block diagram illustrating multicasting. The link layer protocol supports multicasting. Multicast support enables non-redundant transmission of data sent from a single source to multiple destinations, meaning only one copy of the data packet is sent across a broadcast interface if the links from the source to the destinations share the interface. For example, suppose node A has links to nodes B and C using the same wireless interface, as shown in <figref idref="DRAWINGS">FIG. 13</figref>. To send the same packet to both nodes B and C, node A broadcasts the packet on the interface only once.

0232For multicast messages with many recipients sharing the same broadcast link, multicast support represents a substantial reduction of bandwidth utilization. However, since the recipients of a multicast use different Diffie-Hellman keys for encrypting data over their links to the source node, multicast data packets are not encrypted. <figref idref="DRAWINGS">FIG. 14</figref> shows the multicast section of a link data packet; this section is not present in unicast data packets.

Using a Destination Set to Improve Multicast Efficiency

0233<figref idref="DRAWINGS">FIG. 14</figref> is a block diagram illustrating a destination set section of a link data packet. Before sending a multicast packet, a node should identify which nodes are the intended recipients of the broadcast data. For each intended recipient, it computes and attaches a signature to the outgoing packet (see “Signature Section of the Link Data Packet”). In addition, the broadcasting node creates a 24-bit hash value from the concatenation of the intended recipients' UNIs. This hash value is put into the DestSetHash field of the link data packet (see <figref idref="DRAWINGS">FIG. 14</figref>). The DestSetHash value provides a quick way for nodes that receive a broadcast packet to determine whether they are any of the intended recipients.

0234When a node receives a broadcast packet it compares the DestSetHash field of the received packet against a table of previously-received DestSetHash values. The table cross-references the DestSetHash with the position of that node's signature in the array of signatures that are sent with the packet. If the node is not an intended recipient, the signature position will be 0 for that DestSetHash value, and the node can discard the packet.

0235If the DestSetHash field of the received packet is not in the table, the node calculates its signature for the packet (see “Signature Section of the Link Data Packet”) and compares its signature with each of the signatures attached to the packet (which indicate the intended recipients). If the node finds a match, it adds the DestSetHash value and the signature position to its table of known DestSetHash values. If no signature match is found, the DestSetHash value is added to the table with a signature position of 0, indicating that the node is not one of the intended recipients for broadcast packets that contain this DestSetHash; the node then discards the packet.

0236Because signatures also act as checksums for packet integrity, a packet with incomplete data will have a different signature than that same packet when it is complete. If such an incomplete packet arrived at an intended recipient with a new DestSetHash value, the intended recipient would not find any matching signatures and would therefore incorrectly conclude that this DestSetHash value indicates that this node (which received the packet) is not an intended recipient. This node would then incorrectly ignore all future broadcast packets with this DestSetHash value. This can be avoided by relying on checksums performed at the Medium Access Control (MAC) level, which is part of the network interface level, to ensure packet integrity.

Fields in the Multicast Section of the Link Data Packet

0237NumSigs (<b>8</b>) The number of signatures that appear in the packet; it is in the range from 1 to 255. A separate signature is created for each intended recipient of the multicast data packet (see “Signature Section of the Link Data Packet”). This field appears only in multicast data packets; it is absent in unicast data packets.

0238DestSetHash (<b>24</b>) Contains a unique value created from a hash of the set of intended destination nodes. This field appears only in multicast data packets; it is absent in unicast data packets.

Signature Section of the Link Data Packet

0239The signature section of the link data packet serves as a secure checksum for the packet data and also authenticates the data sender. The sender of a data packet, node A, computes a hash of the data and Diffie-Hellman key used for the recipient—h(k, D, k)—and places it in the Sig field of the link data packet header. When node B receives the packet, it applies the hash function h to the string k,D,k and verifies that the result matches the contents of the Sig field. If the two match, node B knows that the data arrived uncorrupted with high probability (because h(k,D,k) is a checksum), and it also knows that the data should have come from node A (because only A knows the value of k).

Folding the Hash Value

0240<figref idref="DRAWINGS">FIG. 15</figref> is a flow diagram illustrating a technique for folding hash values. The output of the standard hash functions—for example, MD-5—is a 128 bit hash value. This is collapsed into a 32-bit quantity by a process called folding. To fold a 128 bit hash value h₁₂₈into a 32-bit result h₃₂, the exclusive-or operator is applied bit-wise to the four 32-bit substrings of h₁₂₈. More precisely:

0000<br /><i>h</i>₃₂<i>[i]=h</i>₁₂₈<i>[i]θh</i>₁₂₈<i>[i+</i>32<i>]θh</i>₁₂₈<i>[i+</i>64<i>]θh</i>₁₂₈<i>[i+</i>96] for each <i>i=</i>0 . . . 31

0241where θ represents the exclusive-or operator.

0242To see this more graphically, suppose h₁₂₈is the string shown at the top of <figref idref="DRAWINGS">FIG. 15</figref>. By realigning the four 32-bit substrings shown as a stack of four 32-bit strings in <figref idref="DRAWINGS">FIG. 15</figref>, one can obtain a single 32-bit hash value as the result of the bit-wise exclusive-or of the four bits that appear in each column. Although 2⁹⁶different hash values in h₁₂₈fold into a single hash value in h₃₂, the 2³²different values of h₃₂make it difficult to spoof a node by simply guessing the hash value.

Fields in the Signature Section of the Link Data Packet

0243<figref idref="DRAWINGS">FIG. 16</figref> is a block diagram illustrating a signature field section of a data link packet. Sig (<b>32</b>) Serves as a secure checksum for the data and authenticates the data sender. Node A sets this field to the 32-bit folded string of h(k, D, k), where h is the negotiated hash function, k is the Diffie-Hellman key for the link and D represents the data in the packet, which follows the packet header. In this context, the comma represents the concatenation operator. A unicast data packet has only one Sig field, whereas a multicast data packet can have multiple Sig fields, with the actual number of signatures given by the NumSigs field in the multicast section of the packet (see <figref idref="DRAWINGS">FIG. 14</figref>).

Packet Information Section of the Link Data Packet

0244Once nodes A and B establish a link with each other, packets sent from A to B are numbered sequentially (0, 1, 2 . . . ) with a Packet ID (PID). Likewise, packets sent from B to A are also numbered sequentially, using a separate sequence for its own PIDs. To safeguard against reply attacks, the link layer discards packets that arrive with a PID less than HighestPID or greater than HighestPID+RangePID, where HighestPID is the highest value of a PID so far received in any link data packet, and a typical constant value for RangePID is 1000. In any implementation, appropriate adjustments should be made to handle “wraparound,” that is, accommodating the smooth transition from the PID with bit pattern of all ones to the PID with bit pattern of all zeros. This is necessary to because the PID is a 32-bit unsigned integer field, so arithmetic is performed modulo 2³².

Fields in the Packet Information Section of the Link Data Packet

0245<figref idref="DRAWINGS">FIG. 17</figref> is a block diagram illustrating a packet information section of a data link packet. PID (<b>32</b>) An integer that increments sequentially with each packet sent over the life of the link (per link, per direction).

0246NumAcks (<b>8</b>) The number of acknowledgements of incoming packets that are included with this (outgoing) packet. See “Acknowledgement Section of the Link Data Packet” for more information.

0247ToS (<b>2</b>) Specifies the type of service for the data passed over the link. The currently supported ToS types are given in Table 1.

0000<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 1</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Currently supported ToS types</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="56pt" align="center" /><colspec colname="2" colwidth="161pt" align="left" /><tbody valign="top"><row><entry>ToS filed</entry><entry /></row><row><entry>(decimal)</entry><entry>Description</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row><row><entry>0</entry><entry>Video-audio broadcast (passive media streaming)</entry></row><row><entry>1</entry><entry>Media-stream interactive (active voice conversation)</entry></row><row><entry>2</entry><entry>Passive data file transfer (ftp)</entry></row><row><entry>3</entry><entry>Interactive data file transfer (web browsing)</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0248If more types are identified and considered desirable, some of the 6 bits in the reserved field adjacent to the ToS field in the link data packet header may be used.

0249Type (<b>8</b>) Describes the type of data contained in the packet, as shown in Table 2. This field is set to 0 if the packet contains only acknowledgements. Otherwise, this field is available for the purposes of higher protocol layers.

0000<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="center" /><thead><row><entry namest="1" nameend="1" rowsep="1">TABLE 2</entry></row></thead><tbody valign="top"><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row><row><entry>Possible values for the Type field</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="42pt" align="center" /><colspec colname="2" colwidth="175pt" align="left" /><tbody valign="top"><row><entry>Type field</entry><entry /></row><row><entry>(decimal)</entry><entry>Purpose</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="1" colwidth="42pt" align="char" char="." /><colspec colname="2" colwidth="175pt" align="left" /><tbody valign="top"><row><entry>0</entry><entry>Acknowledgement-only packet</entry></row><row><entry>1</entry><entry>Advertisement packet (routing layer)</entry></row><row><entry>2</entry><entry>Test packet (routing layer)</entry></row><row><entry>128</entry><entry>Circuit data (CDAT) packet (circuit layer)</entry></row><row><entry>129</entry><entry>Circuit establishment (CEST) packet (circuit layer)</entry></row><row><entry>130</entry><entry>Circuit close (CCLS) packet (circuit layer)</entry></row><row><entry>131</entry><entry>Circuit acknowledgement (CACK) packet (circuit layer)</entry></row><row><entry>132</entry><entry>Circuit reset (CRST) packet (circuit layer)</entry></row><row><entry>133</entry><entry>Circuit unknown (CUNK) packet (circuit layer)</entry></row><row><entry namest="1" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0250Frag (<b>1</b>) Set to 1 when a packet represents one of several fragments from an original data packet; otherwise set to 0. When a packet size exceeds the network interface MTU, the link data layer breaks the data portion of the packet into fragments sufficiently small enough that when combined with the link data header the resulting packet is within the MTU constraint. See “Fragmentation Section of the Link Data Packet” for more information.

0251AckCom (<b>1</b>) Set to 1 when there is acknowledgement compression, which means that acknowledgements are 8 bits in length instead of 32 bits; otherwise set to 0. See “Acknowledgement Section of the Link Data Packet” for more information.

0252Res (<b>6</b>) Reserved for future use.

Fragmentation Section of the Link Data Packet

0253<figref idref="DRAWINGS">FIG. 18</figref> is a block diagram illustrating a fragmentation section of a link data packet.

0254The link layer protocol supports a process called link packet fragmentation. When the link layer receives a packet from the circuit and routing layers, the packet may be too large for the network interface layer to handle. This may be due to hardware-related maximum transmission unit (MTU) restrictions. In this case, the link layer fragments the packet it receives into smaller packets before sending them to the network interface. Similarly, when it receives such fragmented packets, it reformats them to their original packet configuration before relaying them to the routing and circuit layers. The MTU is the largest packet size that the underlying network transport technology can support and varies for different technologies such as Ethernet, satellite, WiFi, and wireless carrier.

0255All packets that contain fragments from a single higher-level packet—such as a circuit layer packet—contain the same PID. The receiving node sends an acknowledgement for this PID only after receiving all the fragments.

0256Each data packet fragment contains a offset that describes that fragment's position within the higher-level packet. These offsets, along with a bit that indicates the last fragment, enable the receiver to reassemble the fragments.

0257The Frag field of the Packet Information section (see <figref idref="DRAWINGS">FIG. 17</figref>) indicates whether the current data packet is a fragment of a larger block of data. The remaining fields related to packet fragmentation are shown in <figref idref="DRAWINGS">FIG. 18</figref>.

Fields in the Fragmentation Section of the Link Data Packet

0258LastFrag (<b>1</b>) Set to 1 if the packet contains the last of a series of fragments; otherwise set to 0.

0259Fragmentation Offset (<b>31</b>) Set to the byte offset of this fragment from the beginning of the original data packet.

Acknowledgement Section of the Link Data Packet

0260The link layer recognizes packets by using a system that attaches acknowledgements of incoming packets to outgoing packets—for as many incoming packets as possible within time and space constraints, up to a fixed limit. When an outgoing packet is ready to be sent, the link layer attaches available acknowledgements. If acknowledgements are available but there are no ready outgoing packets, the link layer should wait for one of two events: <ul id="ul0062" list-style="none"><li id="ul0062-0001" num="0000"><ul id="ul0063" list-style="none"><li id="ul0063-0001" num="0261">A fixed time limit has elapsed</li><li id="ul0063-0002" num="0262">A fixed number of acknowledgements accumulate</li></ul></li></ul>

0263Regardless of which state occurs, the link layer creates a blank packet unrelated to any active data stream, attaches the waiting acknowledgements, and sends the packet.

0264When acknowledgement compression is used (by setting the AckCom field of the Packet Information section; see <figref idref="DRAWINGS">FIG. 17</figref>), only the 8 lowest-order bits are used from the PID of the packet being acknowledged. As long as the ack is received by the sending node within the 256 most-recent packets it has sent, the node can reliably determine which packet is being acknowledged.

Fields in the Acknowledgement Section of the Link Data Packet

0265<figref idref="DRAWINGS">FIG. 19</figref> is a block diagram illustrating fields in an acknowledgement section of a link data packet. Ack (<b>8</b> or <b>32</b>) Contains the PID of an incoming packet received and being acknowledged. The size of the field is 8 bits or 32 bits, depending on the value of the AckCom field in the Packet Information section (see <figref idref="DRAWINGS">FIG. 17</figref>). The number of Ack fields present is given by the NumAcks field (also in the Packet Information section).

0266Average Hold Time (<b>32</b>) Contains the average of the hold times of each of the packets being acknowledged by this packet. This field is used for measuring quality of service.

0000Distinguishing Multicast from Unicast

0267The procedure OnReceiveDataPacket( ), outlined in the following psuedocode, describes how the link layer distinguishes a unicast packet from a multicast data packet. This processing is performed in the PAL. When a sender wants to perform a multicast, it computes a value, DestSetHash, determined by the set of the intended recipients (see “Multicast Section of the Link Data Packet” for more information about the DestSetHash value). Although each node that physically receives the packet is able to determine if it is one of the sender's intended recipients by scanning the signatures in the packet header, the DestSetHash value provides a way to more quickly determine whether the local node is an intended recipient by eliminating the need to always scan through the list of signatures in the packet header.

0268In the procedure OnReceiveDataPacket( ), the variable DestSetTable is an array indexed by values of DestSetHash. Each entry contains an unsigned integer value. The local node is in DestSetHash if DestSetTable [DestSetHash] is nonzero, in which case the value of DestSetTable [DestSetHash] indicates the position of the signature (in the list of signatures attached in the data packet header) that should match the local node's signature. If the value of DestSetTable [DestSetHash] is zero, the local node is not an intended recipient and it should discard the packet.

0269The value of DestSetTable [DestSetHash] is defined only after the local node receives a packet containing the value DestSetHash in the DestSetHash field of the packet. Prior to that, DestSetTable [DestSetHash] is undefined. If a sender broadcasts packets with a different set of intended destinations, it computes a new value of DestSetHash for the DestSetHash field on the data packet it sends. When the local node receives a multicast packet that contains a new DestSetHash value, it calculates its signature and scans for a match among the signatures in the packet header. The position of the matching signature is placed into DestSetTable [DestSetHash]; if no signatures match, DestSetTable [DestSetHash] is set to zero and the packet is discarded.

0000<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><thead><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>procedure OnReceiveDataPacket (linkID)</entry></row><row><entry>{</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>if frame header indicates network frame is not broadcast then</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>Process this packet normally, as a unicast packet;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="14pt" align="left" /><colspec colname="1" colwidth="203pt" align="left" /><tbody valign="top"><row><entry /><entry>else // This packet is a broadcast packet.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>// See if the local node is an intended recipient:</entry></row><row><entry /><entry>if DestSetTable[DestSetHash] is defined then</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>sigOffset ← DestSetTable[DestSetHash];</entry></row><row><entry /><entry>if sigOffset ≠ 0 then</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>// Previously determined to be an intended recipient.</entry></row><row><entry /><entry>Process packet using signature at sigOffset position;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>else // Local node is not an intended recipient.</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>Discard the packet;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="28pt" align="left" /><colspec colname="1" colwidth="189pt" align="left" /><tbody valign="top"><row><entry /><entry>else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>sig ← sig of a packet using negotiated key for linkID;</entry></row><row><entry /><entry>if sig appears in the list of sigs in this packet then</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>sifOffset ← offset of this sig in the packet header;</entry></row><row><entry /><entry>DestSetTable[DestSetHash] ← sigOffset;</entry></row><row><entry /><entry>Process this packet normally;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="42pt" align="left" /><colspec colname="1" colwidth="175pt" align="left" /><tbody valign="top"><row><entry /><entry>else</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="56pt" align="left" /><colspec colname="1" colwidth="161pt" align="left" /><tbody valign="top"><row><entry /><entry>DestSetTable[DestSetHash] ← 0;</entry></row><row><entry /><entry>Discard the packet;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="1"><colspec colname="1" colwidth="217pt" align="left" /><tbody valign="top"><row><entry>}</entry></row><row><entry namest="1" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

QoS Measurements

0270The link layer monitors the cost of sending data across a link. Some common cost metrics include bandwidth, latency, jitter, reliability, congestion, and actual monetary expense (for example, a network may lease the use of a satellite link). The circuit layer uses this data to establish circuits that satisfy user-specified QoS requirements. <ul id="ul0064" list-style="none"><li id="ul0064-0001" num="0000"><ul id="ul0065" list-style="none"><li id="ul0065-0001" num="0271">getQos( )</li></ul></li></ul>

0272The getQos_{( )}function returns a set of QoS metrics. The metrics returned are implementation-specific.

Packet Delivery

0273Packets are delivered to higher protocol layers through a call to ReceivePacket (see <figref idref="DRAWINGS">FIG. 3</figref>). If a packet has its Type field set to test packet or advertisement (see Table 2 and the section “Packet Information Section of the Link Data Packet”), the link data layer calls ReceivePacket in the routing layer. If a packet has a type field set to one of the circuit-related packet types (see Table 2) then the link data layer calls ReceivePacket in the circuit layer.

CONCLUSION

0274The link layer protocol creates and manages links, which are direct connections between pairs of CoCo nodes. The link layer detects the presence of neighboring CoCo devices and establishes links to them. Link establishment includes the negotiation of an encoding method and a Diffie-Hellman key exchange so that all communications sent over the link can be secure.

0275Once a link is established, the link layer relays packets between the network interface layer and higher protocol layers, monitors Quality of Service (QoS) statistics and is able to report these to higher protocol layers. It supports multicasting by suppressing redundant packet transmission across a single network interface, performs fragmentation when packet sizes exceed the network interface Maximum Transmission Unit (MTU), and closes inactive links to free system resources for new link requests.

0276The link layer uses a Diffie-Hellman key exchange and a work token computation to provide a level of security that is absent from TCP and IP. This protocol is designed specifically for mobile ad hoc networking, and is superior to TCP/IP for this purpose.

0277The following are possible:

02781. A method for establishing links in a heterogeneous communications network that is scalable and dynamic.

02792. A method for detecting the presence of other network nodes in communications networks.

02803. A method for making links with other network nodes secure. If A and B are two network nodes joined by a link, then when A sends a packet to B, B is guaranteed that only A could have sent it and A is guaranteed that only B can read it.

02814. A method to prevent man-in-the-middle attacks. Once a link is established between two nodes A and B, no rogue node is able to interpose itself between A and B and impersonate each to the other. Hence CoCo networks prevent so-called man-in-the-middle attacks.

02825. A method to prevent denial-of-service attacks. Any node attempting to flood a network with spurious packets is forced to use significant computational resources. Hence CoCo networks prevent so-called denial of service attacks.

02836. A method for monitoring the quality of links in communication networks.

02847. A method for using measured link quality to establish circuits satisfying specified QoS requirements in communication networks.

02858. A method for assigning uniform addresses (uniform network identifiers) to network nodes in heterogeneous communications networks.

02869. A method for nodes to negotiate appropriate security mechanisms during link establishment.

028710. A method to support multicasting by suppressing redundant packet transmission across a single network interface.

028811. A method to detect when links should be closed.

Semantic Concepts Involved

0000<ul id="ul0066" list-style="none"><li id="ul0066-0001" num="0000"><ul id="ul0067" list-style="none"><li id="ul0067-0001" num="0289">Link</li><li id="ul0067-0002" num="0290">Bandwidth</li><li id="ul0067-0003" num="0291">Latency</li><li id="ul0067-0004" num="0292">Encryption</li><li id="ul0067-0005" num="0293">Diffie-Hellman key negotiation</li><li id="ul0067-0006" num="0294">Universal Node Identifier</li><li id="ul0067-0007" num="0295">Protocol Abstraction Layer</li><li id="ul0067-0008" num="0296">Denial-of-service prevention</li><li id="ul0067-0009" num="0297">Man-in-the-middle attack prevention</li><li id="ul0067-0010" num="0298">Link setup packets</li><li id="ul0067-0011" num="0299">Round trip time computation</li><li id="ul0067-0012" num="0300">Acknowledgements</li><li id="ul0067-0013" num="0301">Multicasting</li><li id="ul0067-0014" num="0302">Unicasting</li><li id="ul0067-0015" num="0303">Link state machine</li></ul></li></ul>

0304From the foregoing, it will be appreciated that specific embodiments of the invention have been described herein for purposes of illustration, but that various modifications may be made without deviating from the spirit and scope of the invention. Accordingly, the invention is not limited except as by the appended claims.