A new adaptive transmission protocol is introduced to improve the performance of slotted ALOHA. Nodes use known periodic schedules as base policies with which they collaboratively learn how to transmit periodically in different time slots so that packet collisions are minimized. The Adaptive Policy Tree (APT) algorithm is introduced for this purpose, which results in APT-ALOHA. APT-ALOHA does not require the presence of a central repeater and uses explicit acknowledgements to confirm the reception of packets. It is shown that nodes using APT-ALOHA quickly converge to transmission schedules that are virtually collision-free, and that the throughput of APT-ALOHA resembles that of TDMA, where slots are pre-allocated to nodes. In particular, APT-ALOHA attains a successful utilization of time slots- over 70% on saturation mode.

We present SCR, a secure content replication protocol for the Content-Centric Networking (CCN) architecture. The goal of SCR is to allow a data producer to cache protected content in off-path semi-trusted caches or replicas. In contrast to the standard “take what you want” model of CCN, SCR ensures that no unauthorized, off-path entity can obtain data from these replicas, even if the content is encrypted. SCR allows a producer to encrypt data under any viable access control scheme, such as group-based access backed by broadcast encryption, and delegate the delivery of said content to distributed replicas in the network. SCR is analogous to “blind caching” in IP-based networks, which aim to provide caching as a service in the presence of end-to-end encryption via TLS. We discuss the design details and security features, e.g., revocation, of SCR. We then compare SCR to the HTTP(S)-based blind caching model. We show that our scheme can outperform blind caching due to (1) less protocol complexity and message overhead, (2) faster session establishment, and (3) the ability to obtain data in parallel from multiple, independent replicas.

We describe a method to use hardware-assisted hash tables for CCNx routing on variable length names. Hardware-assisted hash tables typically have fixed key and fixed result sizes, with performance knees at specific cutoffs, such as 32 bytes or 64 bytes for combined key and result sizes. CCNx names, like a URI, use a variable number of path segments, where each segment may be of variable length. The method presented here uses a combination of standard hash lookups plus compressed key hash lookups to handle path segments that exceed the maximum fixed key size. We present results based on an EzChip NP-4 network processor. This paper presents three main results. Based on analysis of a Stanford WebBase trace, we find the first and second order statistics for URLs which clearly shows that including application state (i.e. a Query String) in the name significantly bloats the name. Second, we analyze NP4 performance using several software-based hash functions to compress long CCNx Name components. Third, we present a design for the EzChip NP4 network processor to forward CCNx interest packets. We show the feasibility of the approach based on assumptions from the URL analysis. We estimate the forwarding scheme will achieve 37 Mpps on a single 100 Gbps EzChip NP4 and be able to store 5.6 million forwarding table entries in 2 GB of RAM.

Information Centric Networks (ICN), such as Content Centric Networks (CCNx) or Named Data Networks (NDN) disseminate data using hierarchal names for each chunk of data, where a chunk is roughly the size of an IP datagram. To secure the named exchange, each chunk has a digital signature or a hash-based name. Because these datagrams may be much larger than a link MTU, there is a need for fragmentation, and to date several hop-by-hop, end-to-end, and mid-to-end fragmentation schemes have been proposed. Only one scheme, FIGOA, a cut-through mid-to-end fragmentation scheme (i.e. Without reassembly) claims to be secure by using delayed authentication. We propose a secure cut-through fragmentation scheme derived from FIGOA that allows immediate validation. We also consider queuing and timing issues that were not discussed in FIGOA.

We present an algorithm to assign time slots to nodes in a TDMA network that minimizes the jitter in time slot assignments. By reducing the jitter in time slots around the TDMA frame, we can provide more consistent network access and reduce the overall delay seen by an application with time-varying traffic patterns, such as normal web traffic. Our algorithm can reduce the average delay seen by all nodes in a network by up to 51%, based on our numerical analysis. The algorithm is designed for TDMA MAC layers where a node has the potential to reserve some number of time slots out of a larger selection of available slots, and one wishes to choose the slots that most evenly distribute them around the TDMA ring. The algorithm solves the Minimum Variance Placement problem for the special case of a directed ring. After describing an exact solution using dynamic programming, we present a much faster run time heuristic that closely approximates the exact solution.

We present the design and performance of a new approach to packet switching for MANETs, which we call context aware protocol engines (CAPE). With CAPE, nodes disseminate information in the network by means of context-aware packet switching that enables the statistical multiplexing of bandwidth, processing and storage resources using integrated signaling covering channel access, routing and other functions, to share and store the context within which information is disseminated. Data packet headers consist of simple pointers to their context, and elections and opportunistic reservations integrated with routing are used to attain high throughput and low channel-access delay.

We propose a new hop-by-hop routing protocol for ad hoc wireless networks that uses a novel sequence number scheme to ensure loop-freedom at all times.We use a single large per-destination label space to order nodes in a topological sort (directed acyclic graph).Nodes manipulate the label set innetwork without needing destination-controlled resets, so path repair is localized.The label size is large enough that it should never be exhausted in the lifetime of any given network.Route request flooding is performed through a new method that exploits the inherent partial order of the network, so nodes can share RREQ floods.Whereas most previous route request pruning techniques create a request tree, the new technique creates a directed acyclic request graph.Simulation results compared to AODV, DSR and OLSR show that the new protocol has in most cases equivalent or better packet delivery ratio and latency, but with a fraction of the network load.

We present a new class of on-demand routing protocols called split label routing (SLR). The protocols guarantee loop-freedom at every instant by ensuring that node labels are always in topological order, and thus induce a directed acyclic graph (DAG). The novel feature of SLR is that it uses a dense ordinal set with a strict partial order to label nodes. For any two labels there is always some label in between them. This allows SLR to "insert" a node in to an existing DAG, without the need to relabel predecessors. SLR inherently provides multiple paths to destinations. We present a practical, finitely dense implementation that uses a destination-controlled sequence number. The sequence number functions as a reset to node ordering when no more label splits are possible. The sequence number is changed only by the destination. Simulations show that our proposed protocol outperforms existing state-of-the-art on-demand routing protocols.

The use of dominating-set neighbor elimination as an integral part of the distribution of route requests using the ad hoc on-demand distance vector (AODV) protocol as an example of on-demand routing protocols is investigated. We use detailed simulations to show that simply applying dominant pruning (DP) to the distribution of route requests in AODV results in pruning too many route requests in the presence of mobility and cross-traffic. Accordingly, we introduce several heuristics to compensate the effects of DP and show that the resulting AODV with dominating set heuristics (AODV-DS) has comparable or better delivery ratio, network load, and packet latency than the conventional AODV. AODV-DS exhibits over 70% savings on RREQ traffic than conventional AODV, and in some situations, AODV-DS may have a lower control overhead using Hello packets than conventional AODV without Helios.

A new protocol is presented for on-demand loop-free routing in ad hoc networks. The new protocol, called labeled distance routing (LDR) protocol, uses a distance invariant to establish an ordering criterion and per-destination sequence numbers to reset the invariant resulting in loop-freedom at every instant. The distance invariant allows nodes to change their next hops or distances to destinations without creating routing-table loops. The destination sequence number, which only the destination may increment, permits nodes to reset the values of their distance invariants. The performance of LDR is compared against the performance of three other protocols that are representative of the state-of-the art, namely AODV, DSR and OLSR.

Mobile wireless ad-hoc networks lack some basic abilities taken for granted in wired networks, such as the ability to know adjacent nodes. We present a neighbor discovery protocol, with particular application to broadcast flooding. The neighbor exchange protocol (NXP) has two main improvements over simple periodic broadcast schemes: (1) it only sends Hello packets when necessary to maintain topology and (2) uses sequence numbers in redistributed information to aid in convergence. In simulation, we compare NXP to a periodic protocol and simple flooding for all-node packet broadcasts and two dissemination techniques. We show that we maintain similar delivery rates while using fewer control packets in most configurations.

We study the performance of reliable and unreliable all-node broadcast over ad-hoc networks that use contention-based channel access. To obtain analytical results while preserving hidden-terminal and node clustering characteristics of ad-hoc networks, we introduce a novel differential-equation fluid model for information flow through a network of cluster trees, where a spanning tree joins groups of fully connected nodes. Through numerical analysis and simulations in GloMoSim, we show throughput, goodput, and loss rates for reliable and unreliable networks. For reliable broadcast, we also find NAK rates, NAK loss rates, and retransmission rates. We show that using end-to-end sequence numbers, which are common in reliable multicast, for NAK generation in ad-hoc networks creates substantial unnecessary traffic.

We study group loss probabilities of forward error correction (FEC) codes in shared loss multicast communication. We present a new analysis model with explicit state equations using recursive formulae. Our method looks at an FEC group as a whole, rather than analyze the number of transmissions of a particular packet. Our work applies to C(n,k) erasure codes, where any k out of n packets may decode the entire group. We find the cumulative distribution function that all leaf nodes in a shared loss tree successfully decode a C(n,k) FEC group, the probability mass function (p.m.f.) for the number of leaf nodes that successfully decode a transmission group, the expected number of packets received on successful decode and the expected number of missing packets on decode failure for a particular leaf node of the multicast tree, the p.m.f. that all leaf nodes hold the same packets in common, and the expected height of packet loss. Most of our findings generalize to arbitrary trees with non-uniform link loss. Our results also apply to non-FEC trees. We illustrate applications of our work with examples.