Summary form only given. Delay-Tolerant Networking and Information-Centric Networking represent two new approaches to networking that have been proposed by the research community over the last few years. DTN has explored methods to interconnect networks with various naming, routing and delivery semantics with store-carry-forward delay-tolerant operations, while several ICN-related projects are exploring the naming of data objects instead of nodes, in-network caching and routing, and support for a form of delay-tolerance as a byproduct. In this talk I will cover the basic goals and results of each style of networking, and highlight common lessons learned that contrast the benefits of these approaches with the current IP-based Internet architecture.

We introduce a protocol which routes on flat, location-independent identifiers with guaranteed scalability and low stretch. Our design builds on theoretical advances in the area of compact routing, and is the first to realize these guarantees in a dynamic distributed setting.

We revisit the problem of scaling software routers, motivated by recent advances in server technology that enable high-speed parallel processing--a feature router workloads appear ideally suited to exploit. We propose a software router architecture that parallelizes router functionality both across multiple servers and across multiple cores within a single server. By carefully exploiting parallelism at every opportunity, we demonstrate a 35Gbps parallel router prototype; this router capacity can be linearly scaled through the use of additional servers. Our prototype router is fully programmable using the familiar Click/Linux environment and is built entirely from off-the-shelf, general-purpose server hardware.

We review the rationale behind the current design of the Delay/Disruption Tolerant Networking (DTN) Architecture and highlight some remaining open issues. Its evolution, from a focus on deep space to a broader class of heterogeneous networks that may suffer disruptions, affected design decisions spanning naming and addressing, message formats, data encoding methods, routing, congestion management and security. Having now achieved relative stability with the design, additional experience is required in long-running operational environments in order to fine tune our understanding of DTN concepts and the types of capabilities that are worth the investment in implementation complexity. We expect key management, handling of congestion, multicasting capability, and routing to remain active areas of research and development, and that DTN may continue to be an active research endeavor for at least the next few years.

The eight papers in this special issue focus on delay and disruption tolerant wireless communication. The papers cover routing and network coding for spare mobile ad hoc networks, cross-layer design for sensor networks, satellite communication, and DTN architectural issues.

Abstract The Delay Tolerant Networking (DTN) architecture approaches the problem of reliable message delivery in intermittent networks using a store‐and‐forward approach where messages may remain stored for relatively long periods of time in persistent storage at DTN routers. Forwarded messages are removed from persistent storage only when transfer acknowledgment to another router or final recipient is received. Congestion in such networks takes the form of persistent storage exhaustion. Several solutions exist including slowing sources, using alternative routes, discarding traffic, or migrating messages to alternative storage locations. We propose storage routing (SR), a congestion management solution of the last form. SR employs nearby nodes with available storage to store data that would otherwise be lost given uncontrollable data sources (such as sensors). SR determines a collection of messages and neighbors to migrate them to using a set of locally scoped distributed algorithms, possibly incorporating loops that are known to be optimal for some DTN routing scenarios and decouples storage management from global DTN route selection. Simulations show up to a 500 per cent performance improvement using SR as compared with a comparable scenario lacking SR. Furthermore, we show a desirable parameter insensitivity to node storage capacity, neighborhood search radius, and message lifetime. Copyright © 2007 John Wiley & Sons, Ltd.

Researchers have proposed a variety of metrics to measure important graph properties, for instance, in social, biological, and computer networks. Values for a particular graph metric may capture a graph's resilience to failure or its routing efficiency. Knowledge of appropriate metric values may influence the engineering of future topologies, repair strategies in the face of failure, and understanding of fundamental properties of existing networks. Unfortunately, there are typically no algorithms to generate graphs matching one or more proposed metrics and there is little understanding of the relationships among individual metrics or their applicability to different settings. We present a new, systematic approach for analyzing network topologies. We first introduce the dK-series of probability distributions specifying all degree correlations within d-sized subgraphs of a given graph G. Increasing values of d capture progressively more properties of G at the cost of more complex representation of the probability distribution. Using this series, we can quantitatively measure the distance between two graphs and construct random graphs that accurately reproduce virtually all metrics proposed in the literature. The nature of the dK-series implies that it will also capture any future metrics that may be proposed. Using our approach, we construct graphs for d=0, 1, 2, 3 and demonstrate that these graphs reproduce, with increasing accuracy, important properties of measured and modeled Internet topologies. We find that the d=2 case is sufficient for most practical purposes, while d=3 essentially reconstructs the Internet AS-and router-level topologies exactly. We hope that a systematic method to analyze and synthesize topologies offers a significant improvement to the set of tools available to network topology and protocol researchers.

We consider the problem of routing in a delay tolerant network (DTN) in the presence of path failures. Previous work on DTN routing has focused on using precisely known network dynamics, which does not account for message losses due to link failures, buffer overruns, path selection errors, unscheduled delays, or other problems. We show how to split, replicate, and erasure code message fragments over multiple delivery paths to optimize the probability of successful message delivery. We provide a formulation of this problem and solve it for two cases: a 0/1 (Bernoulli) path delivery model where messages are either fully lost or delivered, and a Gaussian path delivery model where only a fraction of a message may be delivered. Ideas from the modern portfolio theory literature are borrowed to solve the underlying optimization problem. Our approach is directly relevant to solving similar problems that arise in replica placement in distributed file systems and virtual node placement in DHTs. In three different simulated DTN scenarios covering a wide range of applications, we show the effectiveness of our approach in handling failures.

The Thorup-Zwick (TZ) compact routing scheme is the first generic stretch-3 routing scheme delivering a nearly optimal per-node memory upper bound. Using both direct analysis and simulation, we derive the stretch distribution of this routing scheme on Internet-like inter-domain topologies. By investigating the TZ scheme on random graphs with power-law node degree distributions, P/sub k//spl sime/k/sup -/spl gamma//, we find that the average TZ stretch is quite low and virtually independent of /spl gamma/. In particular, for the Internet inter-domain graph with /spl gamma//spl sime/2.1, the average TZ stretch is around 1.1, with up to 70% of all pairwise paths being stretch-1 (shortest possible). As the network grows, the average stretch slowly decreases. We find routing table sizes to be very small (around 50 records for 104-node networks), well below their theoretical upper bounds. Furthermore, we find that both the average shortest path length (i.e. distance) d~ and width of the distance distribution /spl sigma/ observed in the real Internet inter-AS graph have values that are very close to the minimums of the average stretch in the d~- and /spl sigma/ -directions. This leads us to the discovery of a unique critical point of the average TZ stretch as a function of d~ and /spl sigma/. The Internet's distance distribution is located in a close neighborhood of this point. This is remarkable given the fact that the Internet inter-domain topology has evolved without any direct attention paid to properties of the stretch distribution. It suggests the average stretch function may be an indirect indicator of the optimization criteria influencing the Internet's inter-domain topology evolution.

We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time-varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no contemporaneous end-to-end path may ever exist. This situation limits the applicability of traditional routing approaches that tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating routing algorithms in such environments. We then develop several algorithms and use simulations to compare their performance with respect to the amount of knowledge they require about network topology. We find that, as expected, the algorithms using the least knowledge tend to perform poorly. We also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. To the best of our knowledge this is the first such investigation of routing issues in DTNs.

The highly successful architecture and protocols of today's Internet may operate poorly in environments characterized by very long delay paths and frequent network partitions. These problems are exacerbated by end nodes with limited power or memory resources. Often deployed in mobile and extreme environments lacking continuous connectivity, many such networks have their own specialized protocols, and do not utilize IP. To achieve interoperability between them, we propose a network architecture and application interface structured around optionally-reliable asynchronous message forwarding, with limited expectations of end-to-end connectivity and node resources. The architecture operates as an overlay above the transport layers of the networks it interconnects, and provides key services such as in-network data storage and retransmission, interoperable naming, authenticated forwarding and a coarse-grained class of service.

Employing an emulation capability in network simulation provides the ability for real-world traffic to interact with a simulation. The benefits of emulation include the ability to expose experimental algorithms and protocols to live traffic loads, and to test real-world protocol implementations against repeatable interference generated in simulation. This paper describes the design and implementation of the emulation facility in the NS simulator a commonly-used publicly available network research simulator.

This paper considers the potentially negative impacts of an increasing deployment of non-congestion-controlled best-effort traffic on the Internet. These negative impacts range from extreme unfairness against competing TCP traffic to the potential for congestion collapse. To promote the inclusion of end-to-end congestion control in the design of future protocols using best-effort traffic, we argue that router mechanisms are needed to identify and restrict the bandwidth of selected high-bandwidth best-effort flows in times of congestion. The paper discusses several general approaches for identifying those flows suitable for bandwidth regulation. These approaches are to identify a high-bandwidth flow in times of congestion as unresponsive, "not TCP-friendly", or simply using disproportionate bandwidth. A flow that is not "TCP-friendly" is one whose long-term arrival rate exceeds that of any conformant TCP in the same circumstances. An unresponsive flow is one failing to reduce its offered load at a router in response to an increased packet drop rate, and a disproportionate-bandwidth flow is one that uses considerably more bandwidth than other flows in a time of congestion.