The ability of a network node to verify where traffic is coming from and what path that traffic traversed is important for developing secure network protocols and defense mechanisms against attacks. Cryptographic approaches to source authentication and path validation can have significant computational requirements and thus may not be well-suited for high-performance networks. In prior work, we have described Orthogonal Sequence Verification, which uses orthogonal capabilities based on inner product computations, which can be easily realized by basic bitwise operations in a processor. In this paper, we present the results from a prototype implementation of this technique, which shows that the proposed approach is feasible for implementation in practical networks.

Neighbor discovery is a critical first step in establishing communication in a wireless ad-hoc network. Existing quorum-based neighbor discovery algorithms only consider a pair of nodes and ensure that this pair can communicate at least once in a bounded interval. However, when the node density of a wireless network increases, collisions are more likely to happen, which makes these quorum-based algorithms inefficient in practice. We propose a novel self-adapting quorum-based neighbor discovery algorithm that can dynamically adjust its cycle pattern to decrease the impact of such collisions. We first assess the collision problem in wireless networks when using quorum-based neighbor discovery algorithms and then establish a theoretical framework to analyze the discovery delay when considering collision effects. Guided by these theoretical results, we design a self-adapting mechanism for cycle patterns in quorum-based algorithms. Simulation results show that our algorithm can achieve complete neighbor discovery in less time than existing quorum-based neighbor discovery algorithms.

Verifying the authenticity of the source of network traffic and the path that this traffic has traversed is an important building block for secure network protocols and defense mechanisms. We investigate these problems of in-network source authentication and path validation. Existing approaches are either unable to satisfy security requirements or need significant computational resources due to cryptographic operations, thus limiting their suitability in practice where potentially every packet needs to be checked at line rate. We present Orthogonal Sequence Verification (OSV), a lightweight and scalable technique to address this problem. OSV uses orthogonal capabilities to enable source authentication and path verification simultaneously. The verification of these orthogonal capabilities is based on inner product computations, which can be easily realized by basic bitwise operations in a processor. Therefore, OSV significantly reduces computational cost, while achieving the necessary security properties. We present evaluation results which show that OSV is three orders of magnitude faster than the current approaches based on cryptographic operations. Therefore, we believe that our work presents an important contribution toward realizing high-performance, secure network protocols and network attack defenses in practice.

Typical routing algorithms use a single criterion, such as hop count or link weight, to calculate paths. As the requirement of flexible routing arises, there are circumstances where multiple criteria are needed for routing. Though there are proposed solutions to the multi-criteria optimal path selection problem for quality-of-service routing, they usually combine all criteria into a single path optimization metric a priori. However, this approach is not feasible in scenarios where the path consumers' weightings of criteria is not known at compute time. Such circumstances require finding all the Pareto-optimal paths, i.e., all the paths that are not dominated by other paths. In this paper, we present the algorithmic foundations for efficiently computing Pareto-optimal paths. We present ParetoBFS, a variant of a breadth-first search that uses branch-and-bound techniques to find all the Pareto-optimal paths while effectively limiting the potentially very large search space. We present several sampling techniques to further increase the speed of the search while degrading the quality of the results only marginally. Our simulation results show that existing multi-criteria combinatorial optimization approaches can only search a small fraction of all the Pareto-optimal paths while ParetoBFS can obtain the whole path set in shorter time. We also present results from an implementation of ParetoBFS on a software-defined network prototype.

Neighbor discovery is a crucial first step in configuring and managing a wireless network. Most existing studies on neighbor discovery are based on broadcast algorithms, where nodes send 1-way messages without getting response from their neighbors. However, when directional antennas are used, the ability to coordinate with a neighbor is crucial for later communication between nodes, which requires handshake-based (at least 2-way) protocols. In this paper, we provide a detailed analysis of neighbor discovery protocols with 2-way communication when using directional antennas. Based on this analysis, we present the design of a randomized 2-way neighbor discovery algorithm that uses a selective feedback. Our result shows that a node needs Θ(n2/k) time to discover its n neighbors with k antenna sectors, which yields a significant performance improvement over pure randomized algorithms. We also extend our schemes to practical cases, where the number of neighbors is unknown, and show a factor of no more than 4/3 slowdown in performance.

Network architectures for the future Internet envision a variety of novel network services for transmitting, processing, and storaging of data. These network services may involve costly resources that need to be allocated by a service provider. Thus, an important problem is to limit access to authorized users (e.g., Those who have paid for a particular network service). In addition, these resources need to be protected from denial-of-service attacks or attempts to circumvent this access control. Most existing authentication approaches are based on cryptographic techniques. However, the high computational cost of cryptographic operations makes these techniques unsuitable for the data plane of the network, where potentially every packet needs to be checked at Gigabit per second link rates. In this paper, we describe a novel design for data plane capabilities, called OrthCredential, that solves this problem. The main idea is to use a set of orthogonal sequences as credentials that can be verified easily to protect the data plane against various attacks. These orthogonal sequences can be constructed by a Hadamard transform. Our evaluation of a prototype implementation shows that 64-bit credentials only require less than 300 processor cycles for verification, much less than existing access control schemes such as HMAC. And it provides reasonable security properties (e.g., Less than 10 -- 8 probability of successful attack).

Network services, ranging from simple network paths to complex packet processing and content storage, are envisioned as a core aspect of the future Internet. One key challenge is to limit access to these services to traffic that is authorized to use them. In this work, we describe a novel design for data plane capabilities that can provide efficient access control at high-data rates.