A practical inter-domain routing and forwarding system remains an open challenge for Named-Data Networking (NDN). At the same time, SCION is an emerging path-aware inter-domain routing and forwarding system designed to improve on the current Internet's BGP-based system in several ways. Both NDN and SCION emphasize end-to-end security and trust, while also offering multipath capabilities. This leads us to consider network layer based on named data that uses NDN for intradomain routing and forwarding, and SCION for inter-domain. Among the challenges to be overcome are where to implement the intra/inter-domain protocol transition, and how to scale the system to handle the vastly larger namespace of NDN. We describe a preliminary approach and lay out some key research questions.

Path aware networking (PAN) is an approach that allows endpoints to participate in the end-to-end path selection, letting them choose paths best suited for each application. This approach offers numerous potential benefits including rapid fail-over, concurrent use of parallel paths, and QoS enabled networks, even spanning multiple domains. The dynamic interconnection of different autonomous systems (ASes) in path aware networks offers both challenges and opportunities for network service providers, which in turn provide opportunities for traffic engineering previously not possible. The SCION path-aware network architecture has been designed from the ground up with security in mind, and features a trust structure that can serve as a basis for more dynamic interconnection between ASes. In this paper, we describe a prototype spot market that lets the ASes sell time-limited excess capacity, allowing buyers to divert traffic to cheaper alternatives temporarily. We believe this market allows for new opportunities both in traffic engineering and inter-domain connectivity that have not existed before. The market benefits all parties involved, as the formerly wasted bandwidth is now used, and provides additional revenue—in varying degrees—to all the participating entities.

Emerging new applications demand the current Internet to provide new functionalities. Although many future Internet architectures and protocols have been proposed to fulfill such needs, ISPs have been reluctant to deploy many of these architectures. We believe technical issues are not the main reasons as many of these new proposals are technically sound. In this paper, we take an economic perspective and seek to answer: Why do most new Internet architectures fail to be deployed? How can the deployability of a new architecture be enhanced? We develop a game-theoretic model to characterize the outcome of an architecture's deployment through the equilibrium of ISPs' decisions. This model enables us to: (1) analyze several key factors of the deployability of a new architecture such as the number of critical ISPs and the change of routing path; (2) explain the deploying outcomes of some previously proposed architectures/protocols such as IPv6, DiffServ, CDN, etc., and shed light on the “Internet flattening phenomenon”; (3) predict the deployability of a new architecture such as NDN, and compare its deployability with competing architectures. Our study suggests that the difficulty to deploy a new Internet architecture comes from the “coordination” of distributed ISPs. Finally, we design a mechanism to enhance the deployability of new architectures.

A key concept of software-defined networking (SDN) is separation of the control and data plane. This idea provides several benefits, including fine-grained network control and monitoring, and the ability to deploy new services in a limited scope. Unfortunately, it is often cost-prohibitive for enterprises (and universities in particular) to upgrade their existing networks to wholly SDN-capable networks all at once. A compromise solution is to deploy SDN capabilities incrementally in the network. The challenge then is to take full advantage of SDN-based services throughout the network, in an integrated fashion rather than in a few "islands" of SDN support. At the University of Kentucky, SDN has been integrated into the campus network for several years. In this paper, we describe two aspects of this challenge, along with our solution approaches. One is the general reluctance of campus network administrations to allow novel or experimental (SDN-based) services in the production network. The other is how to extend such services throughout the legacy part of the network. For the former, we lay out a set of principles designed to ensure that the production service is not harmed. For the latter, we use policy based routing and a graph database to extend our previously-described VIP Lanes service. Our simulation results in a campus-like topology testbed show that we can provide a host with custom path service even if it is connected to a legacy router.

In this paper we consider an alternative possibility for routing money in the Internet ecosystem based on a spot market for interconnection service that operates alongside, or in addition to, the traditional contract service model. Recent work by others showed that under certain assumptions, enabling transit providers (i.e., networks that carry packets between networks) to sell their excess capacity on a best-effort basis improves both provider profit and consumer surplus. While prior work only focused on pricing strategies, we explore the technical feasibility of such a market in this paper. We consider what is needed to make such a spot market possible and focus on the interaction between technical and economic considerations. In particular, we describe two approaches that demonstrate how economic software defined exchanges (ESDXs) can be used as trusted intermediaries to tie the forwarding service to the flow of money.

Campus networks and enterprise networks increasingly depend on middleboxes (e.g., firewalls, NAT, load balancers, IDS/IDP) to provide essential services or enforce network policies. These middleboxes often limit the performance of network applications, especially those involved in big data transfer. To address this problem, we propose a Software Defined Networking (SDN) campus network architecture, called VIP Lanes, that provides the ability for pre-authorized, trusted users to create flows that bypass middleboxes, thereby enabling those users to achieve substantially better performance while maintaining security and policy compliance for other network traffic. In this paper, we present the VIP Lanes abstraction and describe an authorization and policy-enforcement service used to establish trusted VIP Lanes. We describe an initial prototype implementation that not only demonstrates the viability of the VIP Lanes approach, but also gives an indication of the types of performance improvements that are possible - in some cases approaching a two order of magnitude reduction in transmission times.

Internet Exchange Points (IXPs) play a major role in the current Internet architecture, serving as the connection point between Internet Service Providers (ISPs). Software-Defined Exchange Points (SDXs)-programmable versions of Internet Exchange Points (IXPs)-have been proposed as a way to give ISPs finer-grained control over the way packets are routed between ISPs. Leveraging software-defined networking (SDN) technology, an SDX enables control software to insert forwarding rules that route traffic on the granularity of individual flows. In this paper, we describe work-in-progress developing controllers for Software-Defined Internet Exchange Points that facilitate dynamic establishment of forwarding relationships between transit ISPs. The core hypothesis of our work is that the SDX can serve as a trusted intermediary, both facilitating establishment of dynamic peering agreements between ISPs, and enforcing their routing policies. Moreover, this building block, which we dub the Coin-Operated SDX, can be used to construct much more dynamic and fine-grained end-to-end routing services than are possible in today's infrastructure. In our model, each ISP independently but cooperatively defines the policies that the SDX enforces on its behalf. The SDX may also serve as a clearinghouse for the inter-ISP economic transactions that drive these policies, i.e., as Economic SDX (ESDX). We describe the overall architecture of a Coin-Op SDX, as well as the specific operations it must support to offer dynamic services. We believe that Coin-Op SDX can play a critical role in future software-defined inter-domain Internet infrastructure.

Deployment of innovative new networking services requires support by network providers. Since economic motivation plays an important role for network providers, it is critical that a network architecture intrinsically considers economic relationships. We present the design of a protocol that associates access to network services with economic contracts. We show how this protocol can be realized in fundamentally different ways, using out-of-band signaling and in-band signaling, based on two different prototype implementations. We present results that show the effectiveness of the proposed protocol and thus demonstrate a first step toward realizing an economy plane for the Internet.

Homes now constitute a significant fraction of the Internet's “edge”. Despite a number of recent efforts, hard data about the structure and use of home networks is still hard to come by. In particular, data sets that include information about the traffic going into and out of homes tend to include very limited numbers of endpoints. Two of the main challenges in collecting such information are: (i) the computational and storage requirements of passive measurement systems, relative to the limited capabilities of home routers; and (ii) individuals' concerns about the privacy of their traffic data. In this paper we introduce HNFL, a lightweight, privacy-preserving passive measurement infrastructure for home networks. HNFL provides a lightweight network flow data collector in Linux kernel, which presents flow data in the form of bipartite graphs that support both latitudinal and longitudinal studies and a scalable and irreversible method to hide traffic identities from flow data while maintaining longitudinal comparison. We evaluate the correctness and efficiency of HNFL, and explore some applications for both networking researchers and home network users.

Test beds such as GENI provide an ideal environment for experimenting with future internet architectures such as Choice Net. Unlike the narrow waist of the current Internet (IP), Choice Net encourages alternatives and competition at the network layer via an economic plane that allows users to choose and purchase precisely the services they need. In this paper we describe our experiences implementing the Choice Net architecture on GENI. Some features of GENI, such as the ability to program the network layer, to leverage existing protocols and software, to run real applications generating realistic traffic, and the ability to perform long-running experiments made GENI an ideal platform for Choice Net experimentation. However, we found that GENI currently lacks the tools needed to make it easy to use these features. To address this issue, we designed and implemented a GENI Experimenter Tool specifically designed and tailored to perform tasks commonly needed by experimenters such as dynamically configuring nodes, loading and compiling node-specific code, executing Click modules, running commands on sets of nodes, accessing the local file system on nodes, and dynamically logging into nodes.

Recent research has considered various architectural approaches in which route determination occurs separately from forwarding. Such offers many advantages, but also brings a number of challenges, not least of which is scalability. In this paper we consider the problem of computing domain-level end-to-end routes in the Internet. We describe a system architecture and a prototype route computation service that provides performance information along with paths. The results of our experiments, which involve updating billions of routes and serving thousands of requests per second, suggest that the resource requirements for a single-domain end-to-end path service (i.e., a service that provides paths from one access domain to all others) are fairly modest.

Network virtualization is becoming a fundamental building block of future Internet architectures. Although the underlying network infrastructure needed to dynamically create and deploy custom virtual networks is rapidly taking shape (e.g., GENI), constructing and using a virtual network is still a challenging and labor intensive task, one best left to experts.

To address shortcomings of the current Internet, many researchers are taking a clean-slate approach toward re-designing the Internet. These so-called clean-slate approaches discard the old assumptions, design principles, and constraints of the current Internet, set aside concerns about compatibility with existing software, and rebuild the entire network from scratch. Clean-slate approaches have the potential to produce a completely new Internet with new features and applications. However, clean-slate approaches are rarely backward compatible, thereby rendering existing legacy software and applications useless. Rewriting huge numbers of existing legacy applications to run in a clean-slate environment is simply not practical. This paper attempts to address this challenge of running legacy software on a clean-slate network architecture. We propose a general framework that supports a translation and policy interface by which users and administrators (or applications) can map legacy software onto emerging clean-slate networks. Using the framework, users are able to take advantage of the features of a clean-slate network while running existing applications. To check the correctness and completeness of our framework, we implemented an initial prototype and applied it in the context of our clean-slate Postmodern (PoMo) Internet Architecture. Using our system we show how existing applications can make use of, and benefit from, PoMo's multi-path routing capabilities.

There has been a great interest in defining a new network architecture that can meet the needs of a future Internet. One of the main challenges in this context is how to realize the many different technical solutions that have developed in recent years in a single coherent architecture. In addition, it is necessary to consider how to ensure economic viability of architecture solutions. In this work, we discuss how to design a network architecture where choices at different layers of the protocol stack are explicitly exposed to users. This approach ensures that innovative technical solutions can be used and rewarded, which is essential to encourage wide deployment of this architecture.

Hierarchical, topology-based addressing has long been considered crucial to routing and forwarding scalability. Recently, however, a number of research efforts are considering alternatives to this traditional approach. With the goal of informing such research, we investigated the efficiency of address assignment in the existing (IPv4) Internet-that is, the assignment of prefixes to ASes. In particular, we ask the question: "Exactly how much does addressing hierarchy help us at the interdomain level?" To do so, we first define a notion of efficiency or locality based on the total number of bit-hops required to advertise all prefixes in the Internet in BGP, and compute this quantity for the current Internet using Route Views data. In order to quantify how far from "optimal" the current Internet is, we assign prefixes to ASes "from scratch" in a manner that preserves observed semantics, using three increasingly strict definitions of equivalence. These results provide an indication of the efficiency of addressing at the interdomain level in the current Internet.

Proxy signatures have found extensive use in authenticating agents acting on behalf of users in applications such as grid computing, communications systems, personal digital assistants, information management and e-commerce. Importance of proxy signatures has been repeatedly highlighted by applied cryptographers through different variations, namely threshold proxy signatures, blind proxy signatures and so forth. Unfortunately, most recent constructions of proxy signatures only improve on minor weaknesses of previously built schemes, and most often do not deliver formal security guarantees. In this study, the authors propose a technique to construct provably secure proxy signature schemes using trapdoor hash functions that can be used to authenticate and authorise agents acting on behalf of users in agent-based computing systems. They demonstrate the effectiveness of their approach for creating practical instances by constructing a discrete log-based instantiation of the proposed generic technique that achieves superior performance in terms of verification overhead and signature size compared with existing proxy signature schemes. Formal definitions, security specifications and a detailed theoretical analysis, including correctness, security and performance, of the proposed proxy signature scheme have been provided.

Aggregate signatures can be a crucial building block for providing scalable authentication of a large number of users in several applications like building efficient certificate chains, authenticating distributed content management systems, and securing path vector routing protocols. Aggregate signatures aim to prevent resources (signature and storage elements, and computation) from growing linearly in the number of signers participating in a network protocol. In this paper, we present an efficient and scalable quasi-aggregate signature scheme, CLFSR, based on third-order linear feedback shift register (cubic LFSR) sequences that can be instantiated using both XTR and GH public key cryptosystems. In the proposed CLFSR construction, signers sign messages sequentially; however, the verfier need not know the order in which messages were signed. The proposed scheme offers constant length signatures, fast signing, aggregation, and verification operations at each node, and requires the least storage elements (public keys needed to verify the signature), compared to any other aggregate signature scheme. To the best of our knowledge, CLFSR is the first aggregate signature scheme to be constructed using LFSR sequences. We believe that the CLFSR signature scheme can be catalytic in improving the processing latency as well as reducing space requirements in building secure, large-scale distributed network protocols. We perform extensive theoretical analysis including correctness and security of CLFSR and also present a performance (computation and communication costs, storage overhead) comparison of the proposed scheme with well-known traditional constructions.

In the current Internet architecture, functions such as addressing, routing, and forwarding are entangled. Among other consequences, this makes it difficult to modify one without affecting the others, and obscures the role of policy at various places in the architecture. This paper considers a network layer designed as a set of separable component mechanisms that work together to provide a best-effort datagram service. Our thesis is that separating concerns makes the architecture more flexible and robust. After presenting the functions that make up the recursive (hierarchical) routing and forwarding service, we discuss the initialization process. The separation and delegation of functions, along with the use of flat, topology-independent identifiers, allows the architecture to be self-configuring as much as possible, leaving the components whose function is affected by policy to be configured.

We present a ”clean-slate” design for a network-layer routing and forwarding system intended to address short-comings of the current Internet Protocol. Our design separates routing from both forwarding and topology discovery; requires only a flat, topology-independent namespace; and allows for policies of both users and service providers to be supported. Channels serve as the primary abstraction, allowing the network topology to be viewed at multiple levels of abstraction using the same identifiers. In this paper we present the basic design, which is based on loose source routing. Our routing and forwarding scheme is part of a larger project to produce a “clean-slate” network layer design.

We study the problem of building an optimal network-layer clustering hierarchy, where the optimality can be defined using three potentially conflicting metrics: state, delay and bandwidth. The problem of network clustering where a node's addresses depends on the node's location (e.g. in the hierarchy) is well studied. We study a problem where network nodes are addressed by specifications that might not be tied to locations in the topology. We propose and compare several distributed clustering algorithms: (i) clustering based solely on topology, (ii) clustering based solely on semantics (node specifications) and (iii) a combination of the above methods (toposemantic network clustering), where we specify a parameter that determines how much the clustering depends on topology and how much on semantics. We show that the toposemantic method yields the best results when we know the right parameter value for a given topology and assignment of specifications. We propose an algorithm that does not require a parameter, but nevertheless yields better results than the first two methods.

We consider the problem of choosing multiple paths across an overlay network in order to provide applications with high-throughput data transfer. Approaches based on traditional (link state) routing algorithms involve a substantial (quadratic) overhead for exchange of state information in fully-connected overlays. Moreover, in the absence of coordination, an apparently "good" link may be selected by multiple sessions simultaneously, causing it to become congested. The simple solution-more frequent exchange of state information-only exacerbates the overhead problem. We present an alternative algorithm that uses a lazy approach to collect link state information, and computes paths by finding the intersection of sets of candidate intermediate hops. Results from experiments show that this intersection-based approach produces paths that provide better performance, has significantly lower overhead, and distributes load more evenly through the network than link-state alternatives.

The Metaverse project aims to develop technology for low-cost, high-resolution networked immersive display environments that can be used for distributed collaboration, exploration of 3D data models, scientific visualization, and other Grid-related applications. Such applications often deal with massive data sets and need a high-capacity, low-latency transport service to effectively connect distant locations across the wide-area (best-effort) Internet. This work presents the initial design of such an end-to-end transport service for Metaverse applications, along with results of a simulation study evaluating its effectiveness. The transport service features an application programming interface providing enhanced control over the way resources are allocated to data objects, and uses multiple overlay-based end-to-end paths to increase bandwidth delivered to the application.

Emerging network-level services, such as ephemeral state processing (ESP), provide end systems with the ability to control the way in which their packets are processed at routers in the network. Supporting user-defined per-packet processing at today's wire-speeds requires significant computational power. Special-purpose application specific integrated circuit (ASIC) chips offer the performance, but not the extensibility needed to support these, evolving services. In our previous work, we explored the use of programmable (general-purpose) network processors as a potential solution. Although network processors are easily extensible, they pay a performance penalty for that flexibility. In this paper, we explore a third approach; the use of programmable logic devices (PLD) that combine the flexibility of a network processor with the performance of an ASIC. We describe a PLD implementation of the ESP service, discuss the challenges involved, and present performance numbers showing significant speedups over our previous network processor implementation.

We describe a new network service called speccast. Speccast offers a generalized addressing and routing abstraction on which a rich variety of semantic services can be built, and, as such, provides a vehicle for studying the relationships among routing, addressing and topology. Unlike overlay-based systems, we study a more basic problem, in which the topology of the network is given, and there is not necessarily any pre-existing underlying network service. In the speccast model, each packet carries a destination predicate and the network's job is to deliver the packet to all nodes satisfying that predicate. After showing how this generalized routing service subsumes other services both traditional (unicast, multicast) and emerging (publish-subscribe), we present a layered solution for a specific class of simple predicates. We examine the tradeoffs in various forms of our approach, and compare it to existing solutions for unicast and multicast. Studies using transit-stub graphs show that our generic service performs comparably to existing solutions for traditional services, while also effectively supporting new and emerging services.

Overlays have been proposed as a means to improve application performance in many areas, including multimedia streaming and content distribution. Some overlays use parallel transmission to increase aggregate throughput or use backup paths to improve reliability. For such applications, an important consideration is whether the "virtual links" at the overlay level (i.e. paths between overlay nodes) share links in the underlying network. In particular, choosing parallel or backup paths without any information about path correlation can reduce the effectiveness of the overlay.In this paper we show how to use passive measurement of TCP throughput to provide information about path correlation, for use in overlay routing decisions. Our methods have the advantage that they send no probe traffic to collect path information. We present results of experimental evaluation in both controlled testbed (Emulab) and real wide area network (Planetlab). Our results demonstrate that the methods together work well across a wide range of operating conditions.

One of the challenges in reliable multicast is approximating or replicating TCP's congestion control algorithm. This has led to various proposals to adapt TCP itself for use over multicast. The drawback of these multicast TCP services is that they place significant processing load on the sender and they fail to deal with the problem of ACK implosion. This paper shows how concast, a network-layer aggregation service, can be used in conjunction with a standard (unmodified) TCP implementation to support reliable multicast while avoiding ACK implosion and offloading ACK processing. Our prototype implementation shows that, even for relatively small groups, distributing the ACK processing and reducing ACK losses translates into significant improvements in end-to-end transmission rates.

Secure distribution of information to authorized recipients is an important prerequisite for group applications with commercial potential. Typically in such applications data traffic is encrypted using a single key; that in turn is distributed securely to the group using one of several mechanisms that rely on each member having a unique set of key encryption keys. As users join and leave the group, members' keysets have to be changed according to a rekey policy. The rekey policy is important because it determines the security properties provided to the application (e.g. forward/backward secrecy). In this paper we present a general model of rekey policies for large-scale applications, and use it to compare the effectiveness of policies proposed in the literature for various applications. Unlike prior work, which has focused on the cost of rekeying, our model also accounts for the cost of not rekeying. We cast existing policies in terms of our model and then propose a more flexible policy that we call exposure-oriented rekeying. We present simulation results showing that our new policy reduces the peak and variation in cost to achieve a given level of security, compared with periodic or batch-oriented rekeying policies.

Abstract Multicast services have been used to transmit multimedia data to large receiver groups. Only recently have counterpart network services been introduced to provide similar scalability and anonymity in the opposite direction (i.e. messages from a group of senders destined for a common receiver). In this paper, we explore how these many‐to‐one services, specifically the concast service, can be used to improve the scalability and performance of multimedia applications. In particular, we show how such services can be used in both the control and data planes to overcome well‐known scalability problems (e.g. with Real Time Protocol) that are difficult to solve effectively with end‐system approaches alone. We validate our solutions by presenting experimental results taken from prototype video and audio applications we designed and implemented. Our initial results show substantial reductions in congestion‐induced loss using these generic services. Copyright © 2003 John Wiley & Sons, Ltd.

Enhanced network services often involve allocating resources (bandwidth/buffer space) preferentially to packets belonging to certain flows or traffic classes. Such services are vulnerable to denial-of-service attacks if packet classification is based on information that can be forged, such as source and destination addresses and port numbers. Traditional message authentication codes (MACs), often considered the only solution to this problem, are really not designed to solve it. In particular, their per-packet costs are so high that they enable another form of denial-of-service attack based on overwhelming the verification mechanism. We describe the problem of denial of access to reserved resources and the inadequacies of conventional solutions. We then observe that it is reasonable to trade some of the strong security guarantees provided by conventional MACs for a lower per-packet cost. We propose a new packet authentication algorithm, designed to solve the problem of protecting reserved resources, with a very low, fixed per-packet cost. While it cannot replace conventional MACs for end-to-end authentication, we argue that it is a better solution for the problem considered here. We present measurements from a prototype implementation that can verify a packet of arbitrary size in as few as 1000 machine cycles on an Intel architecture machine.

Some end-to-end network services benefit greatly from network support in terms of utility and scalability. However, when such support is provided through service-specific mechanisms, the proliferation of one-off solutions tend to decrease the robustness of the network over time. Programmable routers, on the other hand, offer generic support for a variety of end-to-end services, but face a different set of challenges with respect to performance, scalability, security, and robustness. Ideally, router-based support for end-to-end services should exhibit the kind of generality, simplicity, scalability, and performance that made the Internet Protocol (IP) so successful. In this paper we present a router-based building block called ephemeral state processing (ESP), which is designed to have IP-like characteristics. ESP allows packets to create and manipulate small amounts of temporary state at routers via short, predefined computations. We discuss the issues involved in the design of such a service and describe three broad classes of problems for which ESP enables robust solutions. We also present performance measurements from a network-processor-based implementation.

Multicast services have been used for many years to transmit multimedia data to large receiver groups. However, only recently have counterpart network services been introduced that provide similar scalability and anonymity in the opposite direction (i.e., messages from a group of senders destined for a common receiver). In this paper, we explore how these emerging services, specifically a concast service (many-to-one communication service), can be used to improve the scalability and performance of multimedia applications. In particular, we show how such services can be used in both the control and data planes to overcome well-known scalability problems (e.g., with RTP) that are difficult to solve effectively with end-system approaches alone. We validate our solutions by presenting experimental results taken from prototype video and audio applications we designed and implemented. Our initial results show a reduction of as much as two orders of magnitude in packet loss rates using these generic services.

Concast is a network layer service that provides many-to-one channels: multiple sources send messages toward one destination, and the network delivers a single "merged" copy to that destination. As we have defined it, the service is generic but the relationship between the sent and received messages can be customized for particular applications. We describe the concast service and show how it can be implemented in a back ward-compatible manner in the Internet. We describe its use to solve a problem that has eluded scalable end-system-only solutions: collecting feedback in multicast applications. Our preliminary analysis of concasting effectiveness shows that it provides significant benefits, even with partial deployment. We argue that concast has the characteristics needed for a programmable service to be widely accepted and deployed in the Internet.

Concast is a scalable "inverse-multicast" network service: messages sent from multiple sources toward the same destination are merged into a single message that is delivered to the destination. The mapping from sent messages to received messages is programmable, so the service can be tailored to the needs of specific applications. However the service can also be used as a building block for other generic network services, such as a packet multiplexing service that encapsulates multiple small packets into a single larger packet and then unencapsulates the small packets at their (common) destination. Such a service offers several potential benefits, including reduced packet processing overhead and increased rate-sharing, but must also be carefully designed to avoid problems caused by added packet delays. We show how concast can serve as the basis for a multiplexing service that can be tailored to the needs of the application. We present simulation results showing that the benefits of our multiplexing service vary with delay. We also show that given certain queue-manipulation capabilities, benefits can be achieved with zero added delay.

Bowman is an extensible platform for active networking: it layers active networking functionality in user space software over variants of the System V UNIX operating system. The packet processing path implemented in Bowman incorporates an efficient and flexible packet classification algorithm, supports multi-threaded per-flow processing, and utilizes real time processor scheduling to achieve deterministic performance in the user-space. In this paper we describe the design and implementation of Bowman; discuss the support that Bowman provides for implementing execution environments for active networking; discuss the network-level architecture of Bowman that can be used to implement virtual networks; and present performance data showing that Bowman is able to sustain 100 Mbps throughput while forwarding IP packets over fast Ethernets.

This paper introduces concast, a new network service. Concast is the inverse of multicast: multiple sources send messages toward the same destination, which results in a single message being delivered to the destination. The received message appears to come from the concast group rather than any particular receiver. Different forms of concast service can be defined by varying the mapping from the set of sent messages to the received message. The service is useful for preventing implosion and reducing bandwidth consumption in cases where many senders transmit to the same receiver-for example in aggregating (or suppressing) positive (or negative) acknowledgements. We define the semantics of a simple concast service that is the inverse of multicast, as well as a more general custom concast, which allows users to define certain aspects of the service's semantics. We describe how to implement the service so that it scales approximately as well as IP multicast. We also present results from a simulation study showing that concast provides significant benefits in a layered-video application.

Active networks allow users to "program" the network infrastructure, by injecting information that describes or controls a distributed algorithm to be executed for the user by the network infrastructure. The nature of the services that can be implemented with such a facility is determined by the programming interface to the active network, i.e. the set of abstractions it exposes to users. The complexity of this interface may range from a few simple parameters to a completely general programming language. We present a model that supports reasoning independently about the correctness of both the underlying active network platform and the algorithms injected into it, in a manner that admits the full range of possible programming interfaces. The model is described without relying on any particular formalism. The interaction between the underlying platform and the user injected program is captured in a specialized form of program composition that allows properties of each to be preserved. The use of the model is illustrated via an example dealing with mobility. For the example, we use the UNITY formalism to be more precise about the programs and properties that are preserved.

A substantial fraction of all network traffic today comes from applications in which clients retrieve objects from servers. The caching of objects in locations "close" to clients is an important technique for reducing both network traffic and response time for such applications. In this paper we consider the benefits of associating caches with switching nodes throughout the network, rather than in a few locations. We also consider the use of various self-organizing or active cache management strategies for organizing cache content. We evaluate caching techniques using both simulation and a general analytic model for network caching. Our results indicate that in-network caching can make effective use of cache space, and in many cases self-organizing caching schemes yield better average round-trip latencies than traditional approaches, using much smaller per-node caches.

As the number and variety of Web- and network-based applications continues to increase, so does the need for flexible communication protocols and services to support them. Traditionally, a major impediment to deployment of new protocols is the need to upgrade millions of end-systems with compatible implementations. At the same time, Java-a language explicitly designed to support development and distribution of new applications via the Web-is emerging as a (potentially) ubiquitous system platform. It is therefore natural to consider whether Java might speed the introduction of protocols to better support new applications. We investigate the tradeoffs involved in using Java for protocol implementation and deployment. Using insights from a Java-based protocol suite and supporting subsystem we have implemented, we describe the benefits of using the Java language and quantify the performance cost of implementing a protocol in Java for various combinations of interpretation and compilation. We find that the present performance cost of using Java-based protocols is roughly equivalent to four years of hardware performance gains, i.e., interpreted, Java-based protocol performance on current hardware is roughly equivalent to the performance of compiled C code on four-year-old hardware.

We present UDP datagram demultiplexing techniques that can yield potentially substantial application-independent performance gains over BSD-derived UDP implementations. Our demultiplexing strategies exploit local host and UDP implementation features: (1) how UDP processes connection-less datagrams, (2) local host application as client or server, and (3) local host application "density"-resulting in straight-forward hash-based search strategies that caused demultiplexing speedups as high as 24-to-1 over BSD's one-behind cache. Furthermore, while past researchers have shown that cache-based schemes yield little performance benefit for UDP, we show that cache-based implementations can actually degrade demultiplexing performance. Finally, we recommend simple, non-protocol altering local host modifications for existing and future UDP implementations. We used four server traffic traces and eight algorithms in our trace-driven simulations, and executed more than 60 simulations to obtain our results.

Active networking is the placement of user-controllable computing functionality in the switching nodes of a network. The end-to-end argument states that functions should be placed "in" the network only if they can be cost-effectively implemented there. We argue that active networking is a natural consequence of the end-to-end argument, because certain functions can be most effectively implemented with information that is only available inside the network. We propose a performance model for quantifying the benefit of implementing a particular functionality solely in the end system versus implementing it through a combination of end system and network support. We show how the model applies to specific services, including congestion control and reliable multicast.

Deploying protocols is an expensive and time-consuming process today. One reason is the high cost of developing, testing, and installing protocol implementations. To reduce this difficulty, protocols are developed and executed within environments called protocol subsystems, and protocol software is often ported instead of being coded from scratch. Unfortunately, today a variety of protocol subsystems offer a plethora of features, functionality, and drawbacks; the differences among them often reduce the portability and reusability of protocol code, and therefore present barriers to the deployment of new protocols. In this paper, we consider differences in subsystems and their effect on the portability and reusability of protocols and protocol implementations. We then propose two different approaches, each optimized for a different situation, that allow protocol code implemented in one subsystem to be used without modification within other subsystems, and thus reduce the barriers to protocol deployment. We relate our experiences designing, implementing, and measuring the performance of each approach using, as a baseline, an AppleTalk protocol stack we have developed.

Graphs are commonly used to model the topological structure of internetworks in order to study problems ranging from routing to resource reservation. A variety of graphs are found in the literature, including fixed topologies such as rings or stars, "well-known" topologies such as the ARPAnet, and randomly generated topologies. While many researchers rely upon graphs for analytic and simulation studies, there has been little analysis of the implications of using a particular model or how the graph generation method may affect the results of such studies. Further, the selection of one generation method over another is often arbitrary, since the differences and similarities between methods are not well understood. This paper considers the problem of generating and selecting graphs that reflect the properties of real internetworks. We review generation methods in common use and also propose several new methods. We consider a set of metrics that characterize the graphs produced by a method, and we quantify similarities and differences among several generation methods with respect to these metrics. We also consider the effect of the graph model in the context of a specific problem, namely multicast routing.

Because protocol software is difficult and expensive to implement and test, it is often ported between systems instead of rewritten from scratch. Unfortunately, porting protocol software can be as difficult as from-scratch development, due to inherent differences in subsystem design. Thus, protocol subsystems can have a profound effect on the portability of a protocol implementation. We propose an approach permitting the incorporation of new protocols into a subsystem other than their "native" one without the drawbacks or expense of porting and original development. Our approach is based on protocol module encapsulation, which allows unmodified protocol code developed for one protocol subsystem to be used within another. We relate our experiences designing, implementing, and measuring the performance of our protocol encapsulation modules, using an AppleTalk protocol stack as a baseline.

Protocol software is often difficult and expensive to implement and test in today's computing environments. Several things are done to reduce this difficulty: communications software is subdivided into layers and organized into a protocol graph; communications software is developed within a protocol or networking subsystem; and it is often ported rather than developed from scratch. Today, a multitude of subsystems offer different features, functionality, and drawbacks; the differences among them often reduce portability and efficiency of protocol code. We consider these differences in subsystems and their effect on the portability and performance of protocol implementations. We propose an approach for combining the better features of protocol subsystems by constructing protocol graphs composed of protocols residing in different subsystems. Our approach uses adapter modules spanning the inter-subsystem boundary. We relate our experiences designing, implementing, and measuring the performance of several such adapters using an AppleTalk protocol stack we have developed as a baseline.

Graphs are commonly used to model the structure of internetworks, for the study of problems ranging from routing to resource reservation. A variety of graph models are found in the literature, including regular topologies such as rings or stars, "well-known" topologies such as the original ARPAnet, and randomly generated topologies. Less common is any discussion of how closely these models correlate with real network topologies. We consider the problem of efficiently generating graph models that accurately reflect the topological properties of real internetworks. We compare the properties of graphs generated using various methods with those of real internets. We also propose efficient methods for generating topologies with particular properties, including a transit-stub model that correlates well with the internet structure. Improved models for the internetwork structure have the potential to impact the significance of simulation studies of internetworking solutions, providing a basis for the validity of the conclusions.

Multicast routing is an important topic of both theoretical and practical interest. Several proposed multicast routing algorithms involve the designation of one or more network nodes as the "center" of the routing tree for each multicast group. The choice of this designated router (which we refer to as the "core") influences the shape of the multicast routing tree, and thus influences the performance of the routing scheme. We investigate the relationship between the choice of core and three performance measures. Specifically, we compare various methods of selecting a core with respect to their effect on the bandwidth, delay, and traffic concentration. We conclude that simple methods are adequate for widely distributed groups, but that the addition of group information can be leveraged to improve performance especially when the group is small or exhibits a high degree of locality. We also conclude that core choice can be used to control traffic concentration, in fact traffic concentration effects can be ameliorated by appropriate core choice policies.

Multiprotocol systems can be an important tool for achieving interoperability. As the number of protocols available on such systems grows, there is an increasing need for support mechanisms that enable users to effectively access these protocols. Of particular importance is the need to determine which of several protocols to use for a given communication task. In this work, we propose architectures for a protocol discovery system that uses protocol feedback mechanisms to determine which protocols are supported. We describe the issues related to protocol discovery and present feedback mechanisms necessary to support discovery. We present a prototype implementation of a discovery system that supports multiple protocols.

Multiprotocol systems are a vital tool for achieving interoperability in today's heterogeneous communication networks. An important aspect of these systems is the need to determine which of the multiple available protocols will be used to carry out a given communication task; an uninformed choice can result in failure to communicate when communication should be possible. The authors consider ways to make information about hosts' supported protocol configurations available through directory services. They discuss various representation approaches, and describe a working implementation of a multiprotocol application exemplifying their approach.>

This paper considers ways to achieve modularity in protocol architectures without layering. Modularity promotes interoperability by making it easier to port protocol implementations; layering, on the other hand, has been identified as a performance impediment because it enforces sequential processing of messages. Focusing on end-to-end protocols, the authors propose mechanisms (metaheaders and generic interfaces) that support modular parallel or integrated protocol implementations and encourage architecture-independent specifications. An example illustrates interoperability between two systems that support the same protocols, one using traditional layering and the other supporting parallel protocol composition.>

An inclusive approach to achieving heterogeneous system interoperability based on the use of multiprotocol architectures is considered. A detailed description of a framework and model for describing and constructing multiprotocol architectures is given. A case study based on architectures that mix protocols from the OSI and Internet suites is then described. Solutions to the problem of determining which set of protocols to use for a particular communication task are proposed.>

The use of adaptors for protocol conversion in heterogeneous data networks with layered architectures is proposed. An adaptor is a form of protocol converter enabling a peer component of one protocol to simulate a peer of a different protocol. Adaptors have several advantages over other conversion architectures, especially gateway-type converters: they avoid bottlenecks at network boundaries, and a message is translated twice at most on its way from one peer to the other; adaptors are well-suited for conversion among multiple protocols; and the definition of an adaptor as the quotient of known components is simpler than for other converters, making it simpler to compute an adaptor algorithmically or to verify one derived heuristically. The approach is illustrated with an example involving three different connection-management protocols.>

Consideration is given to ways of overcoming a protocol mismatch using protocol conversion. Three different methods for finding a protocol converter are described. Two of these are bottom up in nature, and involve relating the conversion system to existing protocols. The third approach, which is new, is top down: the desired global properties of the conversion system are used in deriving the converter. An example is used to illustrate each method. The authors discuss more general forms of the abstract problem in the context of layered network architectures.>

A protocol converter mediates the communication between implementations of different protocols, enabling them to achieve some form of useful interaction. The problem of deriving a protocol converter from specifications of the protocols and a desired service can be viewed as the problem of finding the “quotient” of two specifications. We define a class of finite-state specifications and present an algorithm for solving “quotient” problems for the class. The algorithm is applied to an example conversion problem. We also discuss its application in the context of layered network architectures.