BBN Technologies Internetworking Research: Technical Memos and Reports

Department Technical Memoranda

BBN-TM-1218, A Simulation Study of Paced TCP, (postscript, 689K) (PDF, 3090K)

Joanna Kulik, Robert Coulter, Dennis Rockwell, and Craig Partridge BBN Technical Memorandum No. 1218, August 12, 1999.: Abstract
In this paper, we study the performance of paced TCP, a modified version of TCP designed especially for high delay-bandwidth networks. In typical networks, TCP optimizes its send-rate by transmitting increasingly large bursts, or windows, of packets, one burst per round-trip time, until it reaches a maximum window-size, which corresponds to the full capacity of the network. In a network with a high delay-bandwidth product, however, TCP's maximum window-size may be larger than the queue size of the intermediate routers, and routers will begin to drop packets as soon as the windows become too large for the router queues. The TCP sender then concludes that the bottleneck capacity of the network has been reached, and it limits its send-rate accordingly. Partridge proposed paced TCP as a means of solving the problem of queueing bottlenecks. A sender using paced TCP would release packets in multiple, small bursts during a round-trip time in which ordinary TCP would release a single, large burst of packets. This approach allows the sender to increase its send-rate to the maximum window size without encountering queueing bottlenecks. This paper describes the performance of paced TCP in a simulated network and discusses implementation details that can affect the performance of paced TCP.

BBN-TM-1219, Overview of Languages for the Smart Packets Project, (postscript, 58K) (PDF, 1729K)

Beverly I. Schwartz and Alden W. Jackson BBN Technical Memorandum No. 1219, September 27, 1999.: Abstract
Several programming languages are surveyed to find what already exists that can help with the development of a programming language for Smart Packets. This paper discusses what the issues are for a Smart Packets language, and then gives details about how each of the languages studied can or can't serve the needs of this project.

BBN-TM-1220, Introduction to Spanner: Assembly Language for the Smart Packets Project, (postscript, 32K) (PDF, 945K)

Beverly I. Schwartz BBN Technical Memorandum No. 1220, September 27, 1999.: Abstract
Spanner is a CISC assembly language with high level types created at BBN Corporation for the Smart Packets project. Spanner is designed with compact representation as a goal; a Spanner program must fit into a single unfragmented packet along with header and authentication information.

BBN-TM-1221, Sprocket Language Description for the Smart Packets Project (postscript, 27K) (PDF, 786K)

Beverly I. Schwartz BBN Technical Memorandum No. 1221, September 27, 1999.: Abstract
Sprocket is a language created at BBN Corporation for the Smart Packets project. Sprocket was created because no other existing language had a compact enough representation for the Smart Packets environment. Sprocket programs, after compilation and assembly, must fit into single packet that cannot be fragmented, along with packet headers and a data area. Sprocket was designed with the assumption that ethernet will have the limiting MTU. Sprocket is not limited by this assumption; Sprocket will scale up to a larger limiting MTU. Smart Packets programs, by design, will be short; data abstractions such as structures and classes which are essential for managing large software projects, will not be needed in Sprocket.

BBN-TM-1222, Justifications for Various Sprocket and Spanner Design Decisions (postscript, 22K) (PDF, 513K)

Beverly I. Schwartz BBN Technical Memorandum No. 1222, September 27, 1999.: Abstract
This is a FAQ discussing the reasons why Sprocket and Spanner were constructed, and some of the design decisions behind them.

BBN-TM-1223, Smart Packets (SPKT) Header (postscript, 25K) (PDF, 799K)

Alden W. Jackson and Beverly I. Schwartz BBN Technical Memorandum No. 1223, September 27, 1999.: Abstract
This document describes how to encapsulate a BBN Technologies Smart Packets packet. The BBN Technologies Smart Packets project is one project in DARPA's Active Networks program. Smart Packets packets will be sent within an ANEP (Active Network Encapsulation Protocol) packet. ANEP was developed for the Active Networks program; it is described in an IETF experimental draft. There are four types of Smart Packet headers depending on whether the packet carries program code, data, messages from the user program, or errors from the run-time execution environment or security aspects. They are described separately in the following. When SPKT gets a packet whose type is unknown, it forwards the packet on without further evaluation; at the same time, it sends an SPKT unknown type error message back to the source node.

BBN-TM-1242, Local Group Keying Protocol (postscript, 103K) (PDF, 3424K)

M. Condell, T. Strayer, M. Fredette, A. Snoeren, C. Partridge, and I. Castineyra BBN Technical Memorandum No. 1242, July 12, 2000.: Abstract
This document specifies a mechanism for a network node to discover all of its neighbors one hop away, and to establish a single group key that the node can use with those neighbors. Once a neighbor is discovered using beacons in a join procedure, point-to-point Security Associations (SAs) are established using IKE [RFC2409]. The node's Peer Group Key is then communicated over these SAs to the neighbor, bringing the neighbor into the node's Peer Group. It is expected that the Peer Group Key will be a symmetric key that the node will use to communicate with its Peer Group using IPsec [RFC2401] over broadcast or multicast.

BBN-TM-1243, FLINT Protocol Specification (postscript, 33K) (PDF, 1053K)

C. Partridge, I. Castineyra, T. Strayer, A. Snoeren, and B. Schwartz BBN Technical Memorandum No. 1243, July 12, 2000.: Abstract
This document defines FLINT, a mechanism for encapsulating FIRE routing infrastructure messages for transmission over a network service such that the messages are identifiable as routing infrastructure messages and have a distinct port space. The format allows the use of an existing authenticated network layer service, namely IPsec [RFC2401] or any authentication-enhanced IP [RFC791] or IPv6 [RFC1883] service. A globally assigned IP Protocol number or, if that is obscured by the authentication encapsulation (as happens with IPsec), a well-known Type of Service value, readily identifies these IP packets as facilitating the routing infrastructure. The encapsulation format has a source and destination port field for representing the port space for this IP Protocol.

BBN-TM-1244, FIRE Peering Protocol Specification (postscript, 40K) (PDF, 1393K)

A. Snoeren, C. Partridge, T. Strayer, and I. Castineyra BBN Technical Memorandum No. 1244, July 12, 2000.: Abstract
The Flexible Intra-AS Routing Environment (FIRE) is an interior gateway routing protocol which allows traffic to be routed based on different criteria [FIREARCH]. The FIRE Peering Protocol serves two distinct purposes. First, it establishes peering relationships between routers for the exchange of State Advertisements (SA). Secondly, it selects Designated (DR) and Backup Designated Routers (BDR) for each broadcast subnet. We explicitly support uni-directional links, and allow for the peering of nodes across different links, provided some combination of links provides bi-directional communication between the two nodes.
Designated Routers serve two purposes in FIRE. First, they are responsible for generating SAs for the Network. Secondly, they help to limit the number of peering relationships established over a particular network. Routers on a broadcast network peer only with the Designated Router for the network, and not with the other, non-DR routers.

BBN-TM-1245, FIRE State Message Protocol Specification (postscript, 95K) (PDF, 3380K)

C. Partridge, I. Castineyra, T. Strayer, A. Snoeren, and B. Schwartz BBN Technical Memorandum No. 1245, July 12, 2000.: Abstract
This memo specifies FIRE State Message formats and protocol. FIRE, the Flexible Intra-AS Routing Environment, is a flexible routing system for use within an Autonomous System (AS). Through exchange of state advertisements containing properties associated with links and nodes, each routing node in the AS can build an identical Property Repository. Various routing algorithms are applied to this repository to produce forwarding tables. Filters applied to incoming packets determine which forwarding table is appropriate, permitting various criteria to determine the path of a packet through the network.
FIRE State Messages are the mechanism for exchanging the properties that are used to build the Property Repository.

BBN-TM-1265, Flexible Intra-AS Routing Environment (FIRE): Large Data Transfer Protocol (postscript, 38K) (PDF, 1340K)

C. Partridge, I. Castineyra, B. Schwartz and F. Tchakountio BBN Technical Memorandum No. 1265, November 15, 2000.: Abstract
FIRE is a family of protocols that implement an extensible routing protocol for an autonomous system. Some mechanisms within FIRE require that nodes be able to request a copy of a large piece of data, where a large piece of data is considered to be data sufficiently large to require flow control when being transferred. This memo describes FIRE's large data copy protocol, which is used for large transfers of routing data. The protocol is based on the Trivial File Transfer Protocol (TFTP), altered to run over FIRE's basic protocol and enhanced to support authenticated transfer of data.

BBN-TM-1278, SENCOMM Architecture (postscript, 955K) (PDF, 3844K)

Alden W. Jackson, James P.G. Sterbenz, Matthew N. Condell, Joel Levin, and David J. Waitzman BBN Technical Memorandum No. 1278, January 24, 2001.: Abstract
This document describes the architecture for the Smart Environment for Network Control, Monitoring and Management (SENCOMM) and its components. SENCOMM comprises a Management Execution Environment (SMEE), which coexists with other execution environments (EEs), and runs on top of FreeBSD, Linux, and the DARPA Active Networks NodeOS. Management applications run in the SMEE. An application is mobile executable code that is delivered to active node within an Active Network Encapsulation Protocol (ANEP) datagram.

BBN-TM-1279, An Evaluation of the TSMA Protocol as a Control Channel Mechanism in MMWN (postscript, 640K) (PDF, 2518K)

Rajesh Krishnan and James P.G. Sterbenz BBN Technical Memorandum No. 1279, April 26, 2000.

Abstract
This document reports the findings of the research effort at BBN Technologies to characterize the TSMA protocol, to analyze its performance as a control channel mechanism and to evaluate its applicability to BBN's MMWN (Multimedia support for Mobile, multi-hop, Wireless Networks) Project. Specific contributions include:

Evaluation of TSMA as a control channel protocol in MMWN.
An acknowledgment scheme for TSMA that enhances average-case performance -- increases throughput and decreases delay -- while preserving the worst-case guarantees. Results of analytical and experimental performance evaluation are provided.
Application of a transmit power control scheme developed at BBN that can control the topological properties of the network including the degree, which can potentially enhance TSMA performance in a given network or extend TSMA operation over a wider range of network scenarios.
An implementation of the TSMA protocol, with performance enhancements using acknowledgments and topology control, within the MMWN testbed.
General issues and design guidelines for the practical deployment of TSMA.

Keywords: Control Channel, Conflict-Free Protocols, Time Spread Multiple Access, Time Division Multiple Access, Carrier Sense Multiple Access, Mobile multi-hop Wireless Networks.

BBN-TM-1280, Routing to Highly Mobile Endpoints: A Theoretical and Experimental Study of Limits and Solutions (postscript, 1209K) (PDF, 7993K)

Fabrice Tchakountio and Ram Ramanathan BBN Technical Memorandum No. 1280, December 1, 2001.: Abstract
We consider the problem of routing to endpoints with very high "effective" mobility, i.e., when the period between changes in an endpoint network attachment point is comparable to the time it takes for the location tracking mechanism to converge. This could happen due to increased endpoint speed, decreased cell size, or increased control message latency. When this happens, conventional reactive location tracking mechanisms fail - by the time such mechanisms converge, the endpoint has already moved to a new location. Anticipating future network attachment points and forwarding traffic toward those points might be necessary to reduce the number and duration of interruptions in sessions involving highly mobile endpoints. We present in this paper, three techniques especially tailored to meet performance demands in networks with a high "effective" user mobility.
In the first part of this paper, we characterize the performance degradation of a location tracking mechanism with increasing effective mobility. Specifically, we show that a typical network is in one of three operating states - reactable, late-reactable, and unreactable, and derive expressions for "inflection points" i.e., endpoint speeds at which the system transitions from one state to another. In the second part, we describe "spray routing" -- a simple routing mechanism that uses controlled multicasting to the vicinity of the endpoint's last-known location for highly mobile endpoints . In the third part, we describe "trajectory routing" -- a mechanism that uses past trajectory information to predict future locations. In the fourth part, "trajectory with spray routing" which combines the best features of spray routing and trajectory routing is analyzed.
We show through experiments how each of these mechanisms improves the throughput performance to acceptable levels especially for highly mobile endpoints while maintaining reasonable end-to-end delay. Our work is applicable to high mobility in both cell-based and ad-hoc wireless networks.

BBN-TM-1281, TCP over Load-Reactive Links (postscript, 771K) (PDF, 3959K)

Rajesh Krishnan BBN Technical Memorandum No. 1281, February 12, 2001.: Abstract
A load-reactive link (LRL) is a link which has capacity that can be varied in response to the offered load. In this paper we study the behavior of a single TCP connection over a particular type of LRL that uses a hysteresis control mechanism for capacity allocation that reacts to current traffic loads.
Our results indicate that good performance for a single TCP connection can be achieved with appropriate choice of control parameters. We also show that other control parameters make it difficult or impossible for TCP to function.
If confirmed by additional experiments, these results have potential applications in traffic engineering schemes that use allocable link layer technologies overlaid by IP services.
Keywords: TCP performance, load-reactive links, hysteresis control, traffic engineering and management.

BBN-TM-1284, Hash-Based IP Traceback (postscript, 422K) (PDF, 186K)

Alex C. Snoeren, Craig Partridge, Luis A. Sanchez, W. Timothy Strayer, Christine E. Jones, Fabrice Tchakountio, and Stephen T. Kent BBN Technical Memorandum No. 1284, February 7, 2001.: Abstract
The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet. Even in the absence of any deliberate attempt to disguise a packet's origin, wide-spread packet forwarding techniques such as NAT and encapsulation may obscure the packet's true source. Techniques have been developed to determine the source of large packet flows, but, to date, no system has been presented to track individual packets in an efficient, scalable fashion.
We present a hash-based technique for IP traceback that generates audit trails for traffic within the network, and can trace the origin of a {\em single} IP packet delivered by the network in the recent past. We demonstrate that the system is effective, space-efficient (requiring approximately 0.5\% of the link capacity per unit time in storage), and implementable in current or next-generation routing hardware. We present both analytic and simulation results showing the system's effectiveness.

BBN-TM-1296, A History of the BBN Piano (postscript, 34K) (PDF, 20K)

Beverly Schwartz BBN Technical Memorandum No. 1296, August 3, 2001.: Abstract
BBN Corporation purchased a Steinert grand piano in 1980. This essay tells the story of the piano and the author's personal relationship with it.

BBN-TM-1301, Hazy Sighted Link STate (HSLS) Routing: A Scalable Link State Algorithm (postscript, 2.0M) (PDF, 531K)

Cesar Santivanez and Ram Ramanathan BBN Technical Memorandum No. 1301, August 31, 2001.: Abstract
In this work, we introduce a class of approaches that attempt to scale link-state routing by limiting the scope of link state update dissemination is space and over time. We present the first fundamental analysis of this generic class, which we call `Fuzzy Sighted Link State routing'. Using a novel perspective on the `overhead' of a protocol that includes not only the overhead due to control messages but also due to route sub-optimality, we formulate an analytical model whose solution automatically leads to the best algorithm in this class.
This algorithm is shown to have nearly the best posible asymptotic overhead for any routing algorithm -- proactive or reactive. Simulation results are presented that compare the performance of several algorithms in this class.

BBN-TM-1321, Using Signal Processing to Analyze Wireless Data Traffic (postscript, 636K) (PDF, 3.0M)

Craig Partridge, David Cousins, Alden W. Jackson, Rajesh Krishnan, Tushar Saxena, and W. Timothy Strayer BBN Technical Memorandum No. 1321, May 22, 2002.: Abstract
Experts have long recognized that it is possible to perform traffic analysis on encrypted packet streams by analyzing the timing of packet arrivals (or transmissions). We report on experiments using basic signal processing techniques from acoustics to attempt to perform traffic analysis on encrypted transmissions on wireless networks. While the work discussed here is preliminary, we are able to demonstrate two very interesting results. First, it is possible to extract interesting timing information, such as round-trip times of TCP connections, from traces of aggregated data traffic. Second, it is possible to determine how data is routed through a network using coherence analysis. These results led us to suggest that signal processing techniques will prove valuable network analysis tools in the future.

Department Technical Reports

BBN-TR-8333, Explicit Transport Error Notication (ETEN) for Error-Prone Wireless and Satellite Networks (postscript, 1.5M)

Rajesh Krishnan, Mark Allman, Craig Partridge, and James Sterbenz BBN Technical Report No.8333, February 29, 2002, Revised March 22, 2002.: Abstract
Wireless and satellite networks have non-negligible error rates that can signicantly influence TCP performance because TCP considers every packet loss as an indicator of congestion, and thus throttles the packet transmission rate. Explicit transport error notification (ETEN) mechanisms can aid TCP in distinguishing packets that are lost due to congestion from ones that are lost due to corruption. If TCP can retransmit a packet lost due to corruption without needlessly reducing the transmission rate, a performance benefit can be realized.
In this study we propose two types of ETEN mechanisms: (i) per-packet mechanisms that notify endpoints of each detected corruption; and (ii) cumulative mechanisms that notify endpoints of aggregate corruption statistics. We have implemented the proposed mechanisms in the ns-2 simulator. We present simulation results on performance gains achievable for TCP Reno and TCP SACK, using ETEN mechanisms over a wide range of bit error rates and traffic conditions. We compare TCP Reno and TCP SACK enhanced with ETEN mechanisms against TCP Westwood, which uses a bandwidth estimation strategy in place of the traditional AIMD congestion avoidance algorithm. We discuss two issues related to the practical deployment of ETEN mechanisms: corruption detection mechanisms (and their co-operation with ETEN-based recovery in the transport layer) and security aspects. We include recommendations for further work. Our conclusions from this study are:
(1.) per-packet ETEN mechanisms offer substantial gains in bulk TCP goodput in the absence of congestion; however, in the presence of congestion, TCP congestion avoidance mechanisms dominate resulting in insignificant gains from ETEN
(2.) the proposed per-packet mechanisms provide useful upper bounds on performance that can be used to evaluate future proposals of per-packet and cumulative ETEN techniques
(3.) per-packet mechanisms present significant challenges to practical implementation by providing a new opportunity to exploit Internet security vulnerabilities and by requiring intermediate nodes to reliably extract information from the headers of corrupted packets
(4.) cumulative ETEN techniques are more attractive to implementation; however, the particular mechanism we evaluated did not realize the potential gains of per-packet techniques
(5.) future work in this area should focus on alternative cumulative ETEN mechanisms, accurate loss inference at endpoints to avoid tracking congestion losses at every hop, interactions with forward error correction, and cross-layer co-operation for ETEN

BBN-TR-8339, A Swifter Start for TCP (postscript, 2.4M)

Craig Partridge, Dennis Rockell, Mark Allman, Rajesh Krishnan, and James Sterbenz, BBN Technical Report No.8339, March 22, 2002.: Abstract
While TCP is capable of adapting its data rate to almost any capacity, it has long been known that TCP takes a long time to achieve full data rates on paths with high capacity (especially links with long delays, e.g. satellite links). In this paper we present a new way for TCP to estimate available network capacity and swiftly scale its transmission rate at the start of a TCP connection. While the method does estimate capacity, as predicted by prior simulation, [KCRP99], the limited studies reported in this paper suggest it performs slightly worse than regular TCP over a low-delay modest-bandwidth Internet path.

BBN-TR-8340, Latency-Aware Information Access with User-Directed Fetch Behaviour for Weakly-Connected Mobile Wireless Clients (postscript, 1.7M) (PDF, 899K)

James P.G. Sterbenz, Tushar Saxena, and Rajesh Krishnan, BBN Technical Report No.8339, May 9, 2002.: Abstract
Mobile wireless clients have highly variable network connectivity and available bandwidth. There are times when they may be completely disconnected from the larger Internet. This dynamism of connectivity poses unique constraints for the problem of information access in general, and Web access in particular. These and other factors (such as loaded servers and congested networks) contribute to unpredictably high response times in content retrieval.
We examine the problem of improving the utility of information access applications for these imperfectly connected devices. In particular, we are concerned with three related problems:
1. Providing information to the user on the estimated response time to retrieve content, the freshness of cached content, and the status on the strength of connection to the network. This information allows the user to make informed decisions about which content to retrieve, and how to retrieve it. We propose that client applications should be latency-aware with location translucency.
2. Giving the user control over how the client application behaves when desired content is either not fresh or absent from the cache, for example, whether the user waits for the content, uses an out-of-date cached version, or both. We propose that clients should support user-directed fetch behaviour.
3. Keeping the content cache as current as practical. In addition to conventional techniques such as demand prefetching and push preloading, we propose to build a profile of user activity. During periods of strong connectivity, the client application should hoard to keep the cache fresh, so that content will be locally available when disconnected from the network.
We describe the problem, through a motivating, application, and present our architecture, design, and prototype implementation, followed by a discussion of research issues to be explored. Our work draws on the experiences of designing mobile clients in other scenarios such as distributed file systems (e.g. Coda), as well the large body of work on Web caching and anticipation.

BBN-TR-8384, An Integrated Architecture for Attack Attribution (postscript, 3.32M) (PDF, 387K)

W. Timothy Strayer, Christine E. Jones, Isidro Castineyra, Joel B. Levin, and Regina Rosales Hain, BBN Technical Report No.8384, December 31, 2003.: Abstract
Anonymity is important to perpetrators of network-based attacks. One of the simplest ways to remain anonymous is to hide the source of an attack by chaining together multiple connections into an extended connection. This is typically done by logging into a remote host, then from there logging into a third and fourth and so on until, at the final host, an attack is launched. These intermediate hosts are called stepping stones. Tracing such an attack back to the original source is difficult. Some techniques exist to trace individual connections, but tracing an extended connection requires identifying related connection pairs at each stepping stone.
This paper examines the problems and approaches to connection tracing, focusing on tracing extended connections across stepping stones. We survey the literature and discuss the several techniques that have been offered so far for discovering related connection pairs, and offer a taxonomy of these techniques. We then discuss a set of experiments performed on four selected algorithms to compare them and gain better understanding of their relative strengths and weaknesses. An architecture for an integrated attack attribution system, including both stepping stone detection and IP traceback, is offered, followed by concluding remarks and observations. Our future work will include constructing the master function and installing stepping stone detection extensions into SPIE to provide a more complete traceback solution.

BBN-TR-8385, SPIE Memory Requirements Reduction (postscript, 65K) (PDF, 43K)

Charles Lynn, Walter Milliken, and W. Timothy Strayer, BBN Technical Report No.8385, December 31, 2003.: Abstract
The Source Path Isolation Engine (SPIE) is an architecture used to trace a single packet back to its point of entry into an internetwork that has been instrumented with the requisite technology. The technology can be deployed either within the internetwork's routers or as a ``tap box'' associated with the routers. The functionality results in a graph through the instrumented internetwork. This graph does not exclude any nodes through which the given packet might have passed (no false negatives), and a configurable parameter that controls the inclusion of nodes through which the packet might have passed but did not (false positives).
Given that the traceback happens after the fact, memory is required to save information for later use. The amount of memory is determined both by the acceptable level of false positive nodes (routers) in the resulting graph and by the sum of the time required to isolate the attack packet, pass it to the traceback system for processing, and for the processing to be completed. The parameters used in the papers cited above use about 0.5% of a router's bandwidth times the length of time required to complete traceback processing. The amount of memory required becomes an issue for high speed routers (e.g., that have many OC-192 links).
This paper examines tradeoffs that may reduce the amount of memory needed in an enabled internetwork.