Decision tree-based packet classification algorithms are easy to implement and allow the tradeoff between storage and throughput. However, the memory consumption of these algorithms remains quite high when high throughput is required. The Adaptive Binary Cuttings (ABC) algorithm exploits another degree of freedom to make the decision tree adapt to the geometric distribution of the filters. The three variations of the adaptive cutting procedure produce a set of different-sized cuts at each decision step, with the goal to balance the distribution of filters and to reduce the filter duplication effect. The ABC algorithm uses stronger and more straightforward criteria for decision tree construction. Coupled with an efficient node encoding scheme, it enables a smaller, shorter, and well-balanced decision tree. The hardware-oriented implementation of each variation is proposed and evaluated extensively to demonstrate its scalability and sensitivity to different configurations. The results show that the ABC algorithm significantly outperforms the other decision tree-based algorithms. It can sustain more than 10-Gb/s throughput and is the only algorithm among the existing well-known packet classification algorithms that can compete with TCAMs in terms of the storage efficiency.

Understanding the real performance of a proposed algorithm is a basic requirement for both algorithm designers and implementers. However, this is sometimes difficult to achieve. Each new algorithm published is evaluated from different perspectives and based on different assumptions. Without a common ground, it is almost impossible to compare different algorithms directly. Choosing an incompetent algorithm for an application can incur significant cost. This is especially true for packet classification in network routers, since packet classification is intrinsically a hard problem and all existing algorithms are based on some heuristics and filter set characteristics. The performance of the packet classification subsystem is critical to the overall performance of the network routers. Although numerous algorithms have been proposed so far, a benchmark that can give them consistent evaluation and reveal their comparable performance is still missing. This paper summarizes our efforts toward improving this situation. First, we conduct a high-level survey on the existing algorithms and extract some insights on the general design ideas. Second, we describe an open-source platform dedicated for advocacy-free evaluation of packet classification algorithms. Many representative algorithms are actually implemented under a set of uniform conditions and assumptions. The freely available implementations allow other researchers to easily test them under different scenarios. We also enforce some consistent and fundamental criteria for the algorithm evaluation, so that their performance and potentials are directly comparable, regardless of the actual implementation platforms. This project serves dual purpose: It helps the researchers to accelerate the innovation in the area of packet classification algorithm development by relieving them from the labor of replicating the previous work and by enabling them to quickly compare and evaluate algorithms. Meanwhile, it also helps the system implementers to easily choose the capable algorithm for their particular applications. Aiming to build an open-source library, we encourage external contributions of new algorithm implementations and evaluations under the same framework. We believe the practice will benefit the research and design community as a whole.

Networking testbeds have become an increasingly important part of the networking research cycle. One of the primary reasons for this is that testbeds offer researchers access to network conditions and environments which are very difficult to reproduce in a local laboratory. This work presents the design of the Open Network Laboratory (ONL) testbed. The underlying infrastructure of ONL is general enough to support resource extensibility and heterogeneity at a fundamental level. New types of resources (e.g., multicore PCs, FPGAs, network processors, etc) can be added to the testbed without modifying any testbed infrastructure software. Resource types can also be extended to support multiple distinct sets of functionality (e.g., an FPGA might act as a router, a switch, or a traffic generator). Moreover, users can dynamically add new resource extensions without any modification to the existing infrastructure.

Real-time systems on non-preemptive platforms require a means of bounding the execution time of programs for admission purposes. Worst-case execution time (WCET) is most commonly used to bound program execution time. While bounding a programpsilas WCET statically is possible, computing its true WCET is difficult. We present a new technique we call partial program admission, a means of statically enforcing an otherwise untrusted assertion of WCET without adding runtime overhead, by means of code duplication. We apply this technique to real programs from the virtual networking arena and present the results.

Over the last decade, programmable Network Processors (NPs) have become widely used in Internet routers and other network components. NPs enable rapid development of complex packet processing functions as well as rapid response to changing requirements. In the network research community, the use of NPs has been limited by the challenges associated with learning to program these devices and with using them for substantial research projects. This paper reports on an extension to the Open Network Laboratory testbed that seeks to reduce these "barriers to entry" by providing a complete and highly configurable NP-based router that users can access remotely and use for network experiments. The base router includes support for IP route lookup and general packet filtering, as well as a flexible queueing sub-system and extensive support for performance monitoring. In addition, it provides a plugin environment that can be used to extend the router's functionality, enabling users to carry out significant network experiments with a relatively modest investment of time and effort. This paper describes our NP router and explains how it can be used. We provide several examples of network experiments that have been implemented using the plugin environment, and provide some baseline performance data to characterize the overall system performance. We also report that these routers have already been used for ten non-trivial projects in an advanced architecture course where most of the students had no prior experience using NPs.

Hash tables are extensively used in networking to implement data-structures that associate a set of keys to a set of values, as they provide O(1), query, insert and delete operations. However, at moderate or high loads collisions are quite frequent which not only increases the access time, but also induces non- determinism in the performance. Due to this non-determinism, the performance of these hash tables degrades sharply in the multi-threaded network processor based environments, where a collection of threads perform the hashing operations in a loosely synchronized manner. In such systems, it is critical to keep the hash operations more deterministic. A recent series of papers have been proposed, which employs a compact on-chip memory to enable deterministic and fast hash queries. While effective, these schemes require substantial on- chip memory, roughly 10-bits for every entry in the hash table. This limits their general usability; specifically in the network processor context, where on-chip resources are scarce. In this paper, we propose a novel hash table construction calledPeacockhash, which reduces the on-chip memory by more than 10-folds while keeping a high degree of determinism in performance. This significantly reduced on-chip memory not only makes Peacock hashing much more appealing for the general use but also makes it an attractive choice for the implementation of a hash hardware accelerator on a network processor.

The importance of network security has grown tremendously and a collection of devices have been introduced, which can improve the security of a network. Network intrusion detection systems (NIDS) are among the most widely deployed such system; popular NIDS use a collection of signatures of known security threats and viruses, which are used to scan each packet's payload. Today, signatures are often specified as regular expressions; thus the core of the NIDS comprises of a regular expressions parser; such parsers are traditionally implemented as finite automata. Deterministic Finite Automata (DFA) are fast, therefore they are often desirable at high network link rates. DFA for the signatures, which are used in the current security devices, however require prohibitive amounts of memory, which limits their practical use.

Modern high performance routers rely on sophisticated interconnection networks to meet ever increasing demands on capacity. Previous studies have used a combination of analysis and idealized simulations to show that coarse-grained scheduling of traffic flows can be effective in preventing interconnect congestion while ensuring high utilization. In this work, we study the performance of a coarse-grained scheduler in a real router with a scalable architecture similar to those found in high performance commercial systems. Our results are obtained by taking fine-grained measurements within the router that provide a detailed picture of the scheduler's behavior under a variety of conditions, giving a more complete and realistic understanding of the short time-scale dynamics than previous studies could provide.

Data structures representing directed graphs with edges labeled by symbols from a finite alphabet are used to implement packet processing algorithms used in a variety of network applications. In this paper we present a novel approach to represent such data structures, which significantly reduces the amount of memory required. This approach called history-based encoding, execution and addressing (HEXA) challenges the conventional assumption that graph data structures must store pointers of lceillog2nrceil bits to identify successor nodes. We show how the data structures can be organized so that implicit information can be used to locate successors, significantly reducing the amount of information that must be stored explicitly. We demonstrate that the binary tries used for IP route lookup can be implemented using just two bytes per stored prefix (roughly half the space required by Eatherton's tree bitmap data structure) and that string matching can be implemented using 20-30% of the space required by conventional data representations. Compact representations are useful, because they allow the performance-critical part of packet processing algorithms to be implemented using fast, on-chip memory, eliminating the need to retrieve information from much slower off-chip memory. This can yield both substantially higher performance and lower power utilization. While enabling a compact representation, HEXA does not add significant complexity to the graph traversal and update, thus maintaining a high performance.

In recent years, overlay networks have become an important vehicle for delivering Internet applications. Overlay network nodes are typically implemented using general purpose servers or clusters. We investigate the performance benefits of more integrated architectures, combining general-purpose servers with high performance Network Processor (NP) subsystems. We focus on PlanetLab as our experimental context and report on the design and evaluation of an experimental PlanetLab platform capable of much higher levels of performance than typical system configurations. To make it easier for users to port applications, the system supports a fast path/slow path application structure that facilitates the mapping of the most performance-critical parts of an application onto an NP subsystem, while allowing the more complex control and exception-handling to be implemented within the programmer-friendly environment provided by conventional servers. We report on implementations of two sample applications, an IPv4 router, and a forwarding application for the Internet Indirection Infrastructure. We demonstrate an 80x improvement in packet processing rates and comparable reductions in latency.

The Open Network Laboratory (ONL) is an Internet-accessible virtual laboratory facility that can deliver a high quality laboratory experience in advanced networking [3,7]. Our experience with ONL indicates that it has potential to improve student understanding of fundamental networking concepts and increase enthusiasm for experimentation with complex technology. Furthermore, these benefits can be delivered with less effort from the instructor than using a traditional approach of socket programming and ns-2 simulation exercises. The system is built around a set of high-performance, extendible routers which connect personal computers acting as end systems. Users configure their virtual network through the Remote Laboratory Interface (RLI), an intuitive graphical interface. The RLI's real-time charts and user data facility make it easy to directly view the effect of system parameters on traffic behavior. These features can enhance learning by providing users with multiple representations of network phenomena. We describe how the ONL facilities have improved our ability to meet instructional objectives and discuss some approaches to improving the laboratory experience.

Ternary Content Addressable Memory (TCAM), although widely used for general packet classification, is an expensive and high power-consuming device. Algorithmic solutions which rely on commodity memory chips are relatively inexpensive and power-efficient but have not been able to match the generality and performance of TCAMs. Therefore, the development of fast and power-efficient algorithmic packet classification techniques continues to be a research subject.In this paper we propose a new approach to packet classification which combines architectural and algorithmic techniques. Our starting point is the well-known crossproduct algorithm which is fast but has significant memory overhead due to the extra rules needed to represent the crossproducts. We show how to modify the crossproduct method in a way that drastically reduces the memory requirement without compromising on performance. Unnecessary accesses to the off-chip memory are avoided by filtering them through on-chip Bloom filters. For packets that match p rules in a rule set, our algorithm requires just 4 + p + ε independent memory accesses to return all matching rules, where ε << 1 is a small constant that depends on the false positive rate of the Bloom filters. Using two commodity SRAM chips, a throughput of 38 Million packets per second can be achieved. For rule set sizes ranging from a few hundred to several thousand filters, the average rule set expansion factor attributable to the algorithm is just 1.2 to 1.4. The average memory consumption per rule is 32 to 45 bytes.

A large body of research literature has focused on improving the performance of longest prefix match IP-lookup. More recently, embedded memory based architectures have been proposed, which delivers very high lookup and update throughput. These architectures often use a pipeline of embedded memories, where each stage stores a single or set of levels of the lookup trie. A stream of lookup requests are issued into the pipeline, one every cycle, in order to achieve high throughput. Most recently, Baboescu et al. [21] have proposed a novel architecture, which uses circular memory pipeline and dynamically maps parts of the lookup trie to different stages.In this paper we extend this approach with an architecture called Circular, Adaptive and Monotonic Pipeline (CAMP), which is based upon the key observation that circular pipeline allows decoupling the number of pipeline stages from the number of levels in the trie. This provides much more flexibility in mapping nodes of the lookup trie to the stages. The flexibility, in turn, improves the memory utilization and also reduces the total memory and power consumption. The flexibility comes at a cost however; since the requests are issued at an arbitrary stage, they may get blocked if their entry stage is busy. In an extreme case, a request may block for a time equal to the pipeline depth, which may severely affect the pipeline utilization. We show that fairly straightforward techniques can ensure nearly full utilization of the pipeline. These techniques, coupled with an adaptive mapping of trie nodes to the circular pipeline, create a pipelined architecture which can operate at high rates irrespective of the trie size.

Modern deep packet inspection systems use regular expressions to define various patterns of interest in network data streams. Deterministic Finite Automata (DFA) are commonly used to parse regular expressions. DFAs are fast, but can require prohibitively large amounts of memory for patterns arising in network applications. Traditional DFA table compression only slightly reduces the memory required and requires an additional memory access per input character. Alternative representations of regular expressions, such as NFAs and Delayed Input DFAs (D2FA) require less memory but sacrifice throughput. In this paper we introduce the Content Addressed Delayed Input DFA (CD2FA), which provides a compact representation of regular expressions that match the throughput of traditional uncompressed DFAs. A CD2FA addresses successive states of a D2FA using their content, rather than a "content-less" identifier. This makes selected information available earlier in the state traversal process, which makes it possible to avoid unnecessary memory accesses. We demonstrate that such content-addressing can be effectively used to obtain automata that are very compact and can achieve high throughput. Specifically, we show that for an application using thousands of patterns defined by regular expressions, CD2FAs use as little as 10% of the space required by a conventional compressed DFA, and match the throughput of an uncompressed DFA.

While the problem of high performance packet classification has received a great deal of attention in recent years, the research community has yet to develop algorithmic methods that can overcome the drawbacks of TCAM-based solutions. This paper introduces a hybrid approach, which partitions the filter set into subsets that are easy to search efficiently. The partitioning strategy groups filters that are close to one another in tuple space [10], which makes it possible to use information from single field lookups to limit the number of subsets that must be searched. We can trade-off running time against space consumption by adjusting the coarseness of the tuple space partition. We find that for two-dimensional filter sets, the method finds the best-matching filter with just four hash probes while limiting the memory space expansion factor to about 2. We also introduce a novel method for Longest Prefix Matching (LPM), which we use as a component of the overall packet classification algorithm. Our LPM method uses a small amount of on-chip memory to speedup the search of an off-chip data structure, but uses significantly less on-chip memory than earlier methods based on Bloom filters.

The GENI Project (Global Environment for Network Innovation) is a major NSF-sponsored initiative that seeks to create a national research facility to enable experimental deployment of innovative new network architectures on a sufficient scale to enable realistic evaluation. One key component of the GENI system will be the GENI Backbone Platform (GBP) that provides the resources needed to allow multiple experimental networks to co-exist within the shared GENI infrastructure. This paper reviews the objectives for the GBP, the key issues that affect its design and develops a reference architecture that provides a concrete example for how the objectives can be met, using commercially available subsystems.

Optical burst switching (OBS) is an emerging technology that allows variable size data bursts to be transported directly over DWDM links. In order to make OBS a viable solution, the wavelength scheduling algorithms need to be able to utilize the available wavelengths efficiently, while being able to operate fast enough to keep up with the burst incoming rate. For example, for a system with 32 wavelengths per link, each operating at 10 Gb/s, we need to process one BHC every 25 ns, in order to support an average burst length of 1 KByte. When implemented in hardware, the running time of the well-known horizon scheduler is O(1) for practical numbers of wavelengths. Unfortunately, horizon scheduling cannot utilize the voids created by previously scheduled bursts, resulting in low bandwidth utilization. To date, Min-SV is the fastest scheduling algorithm that can schedule wavelengths efficiently. However, its complexity is O(log m) and it requires 10log m memory accesses to schedule a single burst. This means that it can take up to several microseconds for each burst request, which is still too slow to make it a practical solution for OBS deployment. In this paper, we propose an optimal wavelength scheduler using constant time burst resequencing (CTBR), which runs in O(1) time. The proposed CTBR scheduler is able to produce optimal wavelength schedules while having the same processing speed as the horizon scheduler. The algorithm is well-suited to high performance hardware implementation.

This paper addresses the problem of efficient filter updates in TCAMs. Under realistic conditions, filter updates can lead to significant performance degradation. This paper introduces an approach to using TCAMs that encodes filter priority as a TCAM field, allowing the highest priority filter to be identified with a small number of lookups, while greatly simplifying filter set management, and reducing the impact of updates on lookup throughput. Our approach supports wire-speed processing for OC-192 links using commercially available TCAM components.

Reserved delivery subnetworks (RDSs) can provide more consistent quality of service to users by reserving bandwidth on an aggregate basis. Besides the benefit of exclusive bandwidth access, there are other potentials to further improve end-to-end performance in an RDS because the end hosts can utilize the knowledge about the underlying networks to achieve better performance than in the ordinary Internet. In this paper, we propose a source traffic regulation technique to improve end-to-end performance in the environment of an RDS. The basic idea is to regulate the traffic from a server to sink end hosts such that bandwidth usage does not exceed the reserved link bandwidth and overloaded sinks do not affect other well behaved sinks. We propose a per-connection as well as an aggregated source traffic regulation algorithm for both single server and multi-server RDSs. We evaluate our algorithms with simulation studies in the ns-2 network simulator, and the simulation results show great improvements over traditional transport protocols.

There is a growing demand for network devices capable of examining the content of data packets in order to improve network security and provide application-specific services. Most high performance systems that perform deep packet inspection implement simple string matching algorithms to match packets against a large, but finite set of strings. owever, there is growing interest in the use of regular expression-based pattern matching, since regular expressions offer superior expressive power and flexibility. Deterministic finite automata (DFA) representations are typically used to implement regular expressions. However, DFA representations of regular expression sets arising in network applications require large amounts of memory, limiting their practical application.In this paper, we introduce a new representation for regular expressions, called the Delayed Input DFA (D2FA), which substantially reduces space equirements as compared to a DFA. A D2FA is constructed by transforming a DFA via incrementally replacing several transitions of the automaton with a single default transition. Our approach dramatically reduces the number of distinct transitions between states. For a collection of regular expressions drawn from current commercial and academic systems, a D2FA representation reduces transitions by more than 95%. Given the substantially reduced space equirements, we describe an efficient architecture that can perform deep packet inspection at multi-gigabit rates. Our architecture uses multiple on-chip memories in such a way that each remains uniformly occupied and accessed over a short duration, thus effectively distributing the load and enabling high throughput. Our architecture can provide ostffective packet content scanning at OC-192 rates with memory requirements that are consistent with current ASIC technology.

The Open Network Laboratory (ONL) is a remotely accessible network testbed of high performance routers which has been designed with an eye towards ease of use for users from the naïve to the expert. The system is built around a set of high-performance routers that are extendible and easily configurable through the Remote Laboratory Interface (RLI), an intuitive graphical interface. The RLI also makes it easy to configure packet filters in the routers, assign flows or flow aggregates to separate queues with configurable QoS and attach hardware monitoring points to real-time charts. The RLI’s real-time charts and user data facility makes it easy to directly view the effects of traffic as it moves through a router, allowing the user to gain better insight into system behavior and create compelling demonstrations. Each port of the router is equipped with an embedded processor that supports software plugins which allow users to extend the system’s functionality. This paper describes the ONL and how it can be used in networking education. You should checkout our web site onl.arl.wustl.edu which includes a short video.

A reserved delivery subnetwork (RDS) is a semiprivate network infrastructure to enable an information service provider to deliver more consistent service to its customers. In our previous study of the RDS configuration problem, we formulated the problem as a minimum concave cost network flow problem (MCCNFP), and presented an efficient approximation algorithm, largest demand first or LDF, to provide approximate solutions to this NP-hard problem in practice. In this paper, we apply local search algorithms based on negative cost cycle and bicycle reduction to further improve the quality of the results obtained from LDF. Our simulation results show that the local search algorithms improve the quality of LDF solutions, but with added computational complexity. They also further indicate that LDF produces solutions reasonably close to the local optimum without added complexity, and is suitable for large networks in practice.

The Internet has fallen victim to its own stunning success. The interplay of the end-to-end design of IP and the vested interests of competing stakeholders has led to its growing ossification. Alterations to the Internet architecture that address its fundamental deficiencies or enable new services have been restricted to incremental changes. The slow pace of this process stifles innovation and the adoption of disruptive technology. A recent call to arms advances a research agenda to confront this impasse through virtualization (L. Peterson et al., 2004). In addition to describing a virtual testbed for the evaluation of new network architectures, it poses a question about the long-term role of virtualization in the Internet. The architectural "purist" views virtualization as a tool for architecture evaluation and the periodic deployment of successive, singular Internet architectures. In this paper, we advance the "pluralist" view that seeks to make virtualization an architectural attribute of the Internet. By enabling a plurality of diverse network architectures to coexist on a shared physical substrate, virtualization mitigates the ossifying forces at work in the current Internet and enables continual introduction of innovative network technologies. Such a diversified Internet would allow existing architectural deficiencies to be holistically addressed as well as enable the introduction of new architectures supporting new types of applications and services. We provide a detailed exposition of the diversified Internet concept, explain how it can address the problem of network ossification and discuss some of the technical challenges that must be met to turn the vision into reality

The rise and growth of the Internet is one of the great technology success stories of the twentieth century. Unfortunately, the size and scope of the public Internet now makes the introduction and deployment of new network innovations very difficult, leading many to observe that the core technology at the heart of the Internet has become ossified. While solutions too many of the IP protocol's limitations are well-understood, there has been remarkably little progress towards deployment of new capabilities. New network technologies face insurmountable barriers to entry, stifling the competitive forces that allow progress in other technology domains. At the same time, advances in electronics now make it both feasible and practical to deploy high performance network components with unprecedented flexibility and programmability. These capabilities can be used to enable a diverse collection of meta-networks to co-exist within a common physical infrastructure. Diversified networking can enable new network technologies to be developed and deployed on a large scale, stimulating innovation in both core network protocols and advanced services that combine computing and communication in creative new ways. It makes it possible for new network innovations to compete on an equal footing with legacy technologies, stimulating innovation and leading to a broad range of new services.

Some of the fastest practical algorithms for IP route lookup are based on space-efficient encodings of multi-bit tries (M. Degermark, et al., 1997, W. Eatherton, 1999). Unfortunately, the time required by these algorithms grows in proportion to the address length, making them less attractive for IPv6. This paper describes and evaluates a new data structure called a shape-shifting trie, in which the data structure nodes correspond to arbitrarily shaped subtrees of the underlying binary trie for a given set of address prefixes. The ability to adapt the node shape to the trie reduces the number of nodes that must be accessed to perform a lookup, especially for tries with large sparse regions. We give a fast algorithm for optimally dividing a trie into nodes so as to minimize the maximum lookup depth. We show that seven data structure accesses are sufficient for route tables with more than 150,000 IPv6 prefixes. This makes it possible to achieve wire-speed processing for OC192 link using a single QDRII SRAM chip.

A wide variety of packet classification algorithms and devices exist in the research literature and commercial market. The existing solutions exploit various design tradeoffs to provide high search rates, power and space efficiency, fast incremental updates, and the ability to scale to large numbers of filters. There remains a need for techniques that achieve a favorable balance among these tradeoffs and scale to support classification on additional fields beyond the standard 5-tuple. We introduce distributed crossproducing of field labels (DCFL), a novel combination of new and existing packet classification techniques that leverages key observations of the structure of real filter sets and takes advantage of the capabilities of modern hardware technology. Using a collection of real and synthetic filter sets, we provide analyses of DCFL performance and resource requirements on filter sets of various sizes and compositions. An optimized implementation of DCFL can provide over 100 million searches per second and storage for over 200 thousand filters in a current generation FPGA or ASIC without the need for external memory devices.

Packet classification is an enabling technology for next generation network services and often the primary bottleneck in high-performance routers. The performance and capacity of many algorithms and classification devices, including TCAMs, depend upon properties of the filter set and query patterns. Despite the pressing need, no standard filter sets or performance evaluation tools are publicly available. In response to this problem, we present ClassBench, a suite of tools for benchmarking packet classification algorithms and devices. ClassBench includes a filter set generator that produces synthetic filter sets that accurately model the characteristics of real filter sets. Along with varying the size of the filter sets, we provide high-level control over the composition of the filters in the resulting filter set. The tool suite also includes a trace generator that produces a sequence of packet headers to exercise packet classification algorithms with respect to a given filter set. Along with specifying the relative size of the trace, we provide a simple mechanism for controlling locality of reference. While we have already found ClassBench to be very useful in our own research, we seek to eliminate the significant access barriers to realistic test vectors for researchers und initiate a broader discussion to guide the refinement of the tools and codification of a formal benchmarking methodology.

We revisit the question of how much buffer an IP router should allocate for its droptail FIFO link. For a long time, setting the buffer size to the bitrate-delay product has been regarded as reasonable. Recent studies of interaction between queueing at IP routers and TCP congestion control offered alternative guidelines. First, we explore and reconcile contradictions between the existing rules. Then, we argue that the problem of link buffer sizing needs a new formulation: design a buffer sizing algorithm that accommodates needs of all Internet applications without engaging IP routers in any additional signaling. Our solution keeps network queues short: set the buffer size to 2L datagrams, where L is the number of input links. We also explain how end systems can utilize the network effectively despite such small buffering at routers.

Hash tables are fundamental components of several network processing algorithms and applications, including route lookup, packet classification, per-flow state management and network monitoring. These applications, which typically occur in the data-path of high-speed routers, must process and forward packets with little or no buffer, making it important to maintain wire-speed throughout. A poorly designed hash table can critically affect the worst-case throughput of an application, since the number of memory accesses required for each lookup can vary. Hence, high throughput applications require hash tables with more predictable worst-case lookup performance. While published papers often assume that hash table lookups take constant time, there is significant variation in the number of items that must be accessed in a typical hash table search, leading to search times that vary by a factor of four or more.We present a novel hash table data structure and lookup algorithm which improves the performance over a naive hash table by reducing the number of memory accesses needed for the most time-consuming lookups. This allows designers to achieve higher lookup performance for a given memory bandwidth, without requiring large amounts of buffering in front of the lookup engine. Our algorithm extends the multiple-hashing Bloom Filter data structure to support exact matches and exploits recent advances in embedded memory technology. Through a combination of analysis and simulations we show that our algorithm is significantly faster than a naive hash table using the same amount of memory, hence it can support better throughput for router applications that use hash tables.

Buffered multistage interconnection networks offer one of the most scalable and cost-effective approaches to building high capacity routers. Unfortunately, the performance of such systems has been difficult to predict in the presence of the extreme traffic conditions that can arise in the Internet. Recent work introduced distributed scheduling, to regulate the flow of traffic in such systems. This work demonstrated, using simulation and experimental measurements, that distributed scheduling can deliver robust performance for extreme traffic. Here, we show that distributed schedulers can be provably work-conserving for speedups of 2 or more. Two of the three schedulers we describe were inspired by previously published crossbar schedulers. The third has no direct counterpart in crossbar scheduling. In our analysis, we show that distributed schedulers based on blocking flows in small-depth acyclic flow graphs can be work-conserving, just as certain crossbar schedulers based on maximal bipartite matchings have been shown to be work-conserving. We also study the performance of practical variants of these schedulers when the speedup is less than 2, using simulation.

As the focus of networking research shifts from raw performance to the delivery of advanced network services, there is a growing need for open-platform systems for extensible networking research. The Applied Research Laboratory at Washington University in Saint Louis has developed a flexible network services platform (NSP) to meet this need. The NSP provides an extensible platform for prototyping next-generation network services and applications. The paper describes the design of a system-on-chip packet processor for the NSP which performs all core packet processing functions, including segmentation and reassembly, packet classification, route lookup, and queue management. Targeted to a commercial configurable logic device, the system is designed to support gigabit links and switch fabrics with a 2:1 speed advantage. We provide resource consumption results for each component of the packet processor design.

The provision of advanced computational services within networks is rapidly becoming both feasible and economical. As computational services become popular, it is important to have effective methods for configuring application sessions so that they use resources efficiently. In this paper, we discuss the problem of configuring application sessions that require intermediate processing. The problem was introduced in an earlier paper, where we showed how to optimally configure sessions in programmable networks by reducing the session configuration problem to the problem of finding a shortest path in a special graph constructed for the particular problem. This layered graph method is quite flexible and can handle a variety of specific session configuration problems. However, it does not explicitly model limits on link bandwidth or processing capacity. In this paper, we show that the optimal session configuration problem is NP-hard when capacity is constrained. Nevertheless, we have found efficient heuristics for which the network performance closely approximates the performance that can be achieved with optimal session configurations.

Practical crossbar scheduling algorithms for CIOQ switches such as PIM and i-SLIP, can perform poorly under extreme traffic conditions, frequently failing to be work-conserving. The common practice of evaluating crossbar scheduling algorithms according to the packet delay under random admissible traffic tends to obscure significant differences that affect the robustness of different algorithms when exposed to extreme conditions. On the other hand, algorithms such as LOOFA with provably good worst-case performance, don't lend themselves readily to high performance implementation. We advocate evaluating crossbar scheduling algorithms using targeted stress tests which seek to probe the performance boundaries of competing alternatives. Appropriately designed stress tests can reveal key-differences among algorithms and can provide the insight needed to spur the development of better solutions. In this paper, we introduce the use of stress testing for crossbar scheduling and use it to evaluate the performance of PIM, i-SLIP and LOOFA. Our results show that PlM and i-SLIP need large speedups in order to perform well on stress tests, while LOOFA can deliver excellent performance, even for speedups less than 1.5. We then develop improved versions of PIM and i-SLIP, which take output queue lengths into account, making them much more robust. We also develop an algorithm which closely approximates the behavior (and performance) of LOOFA, but which admits a straightforward, high performance hardware implementation.

CAMs are the most popular practical method for implementing packet classification in high performance routers. Their principal drawbacks are high power consumption and inefficient representation of filters with port ranges. A recent paper [Narlikar, et al., 2003] showed how partitioned TCAMs could be used to implement IP route lookup with dramatically lower power consumption. We extend the ideas in [Narlikar, et al., 2003] to address the more challenging problem of general packet classification. We describe two extensions to the standard TCAM architecture. The first organizes the TCAM as a two level hierarchy in which an index block is used to enable/disable the querying of the main storage blocks. The second incorporates circuits for range comparisons directly within the TCAM memory array. Extended TCAMs can deliver high performance (100 million lookups per second) for large filter sets (100,000 filters), while reducing power consumption by a factor of ten and improving space efficiency by a factor of three.

This paper presents and evaluates distributed queueing algorithms for regulating the flow of traffic through large, high performance routers. Distributed queueing has a similar objective to crossbar-scheduling mechanisms used in routers with relatively small port counts, and shares some common high level characteristics. However, the need to minimize communication overhead rules out the iterative methods that are typically used for crossbar scheduling, while the ability to sub-divide the available bandwidth among different ports provides a degree of freedom that is absent in the crossbar scheduling context, where inputs must be matched to outputs. Our algorithms are based on four ideas (1) backlog-proportional-allocation of output bandwidth, (2) urgency-proportional-allocation of input bandwidth, (3) dynamic reallocation of bandwidth and (4) deferred underflow. Our algorithms guarantee congestion-free operation of the switch fabric. Our performance results show that for uniform random traffic, even a very modest speedup is sufficient to reduce the loss of output link bandwidth due to sub-optimal rate allocation to negligible levels, and that even under extreme conditions, a speedup of two is sufficient to eliminate such bandwidth loss.

Time Sliced Optical Burst Switching is a proposed variant of optical burst switching, in which switching is done in the time domain, rather than the wavelength domain. This eliminates the need for wavelength converters, the largest single cost component of systems that switch in the wavelength domain. We examine some of the key design issues for routers that implement time sliced optical packet switching. In particular, we focus on the design of the Optical Time Slot Interchangers (OTSIs) needed to effect the required time domain switching. We introduce a novel nonblocking OTSI design and also show how blocking OTSIs can be used to implement the required switching operations. We study the performance of systems using blocking OTSIs and demonstrate that near ideal statistical multiplexing performance can be achieved using even quite inexpensive, blocking OTSI designs. These results suggest that optical technology may one day be able to provide a cost-effective alternative to electronics in packet switching systems.

Optical burst switching (OBS) is an experimental network technology that enables the construction of very high-capacity routers, using optical data paths and electronic control. We study wavelength converting switches using tunable lasers and wavelength grating routers, that are suitable for use in OBS systems and evaluate their performance. We show how the routing problem for these switches can be formulated as a combinatorial puzzle or game, in which the design of the game board corresponds to the pattern of permutation used at the input sections of the switch. We use this to show how the permutation pattern affects the performance of the switch, and to facilitate the design of permutation patterns that yield the best performance. We give upper bounds on the number of different wavelength channels that can be routed through such switches (regardless of the permutation pattern), and show that for 2×2 switches, there is a simple permutation pattern that achieves these bounds. For larger switches, randomized permutation patterns produce the best results. We study the performance of optical burst switches using wavelength converting switches based on several different permutation patterns. We also present a novel routing algorithm called the most available wavelength assignment and evaluate its benefits in improving the switch throughput. Our results show that for a typical configuration, the switch with the best permutation pattern has more than 87% of the throughput of a fully nonblocking switch.

Internet protocol (IP) address lookup is a central processing function of Internet routers. While a wide range of solutions to this problem have been devised, very few simultaneously achieve high lookup rates, good update performance, high memory efficiency, and low hardware cost. High performance solutions using content addressable memory devices are a popular but high-cost solution, particularly when applied to large databases. We present an efficient hardware implementation of a previously unpublished IP address lookup architecture, invented by Eatherton and Dittia (see M.S. thesis, Washington Univ., St. Louis, MO, 1998). Our experimental implementation uses a single commodity synchronous random access memory chip and less than 10% of the logic resources of a commercial configurable logic device, operating at 100 MHz. With these quite modest resources, it can perform over 9 million lookups/s, while simultaneously processing thousands of updates/s, on databases with over 100000 entries. The lookup structure requires 6.3 bytes per address prefix: less than half that required by other methods. The architecture allows performance to be scaled up by using parallel fast IP lookup (FIPL) engines, which interleave accesses to a common memory interface. This architecture allows performance to scale up directly with available memory bandwidth. We describe the tree bitmap algorithm, our implementation of it in a dynamically extensible gigabit router being developed at Washington University in Saint Louis, and the results of performance experiments designed to assess its performance under realistic operating conditions.

Packets in the Internet can experience large queueing delays during busy periods. Backbone routers are generally engineered to have large buffers, in which packets may wait as long as half a second (assuming FIFO service, longer otherwise). During congestion periods, these buffers may stay close to full, subjecting packets to long delays, even when the intrinsic latency of the path is relatively small. This paper studies the performance improvements that can be obtained for short-lived TCP flows by using more sophisticated packet schedulers, than are typical of Internet routers. The results show that the large buffers found in WAN routers contribute only marginally to improving router throughput, and the higher delays that come with large buffers makes them a dubious investment. The results also show that better packet scheduling algorithms can produce dramatic improvements in fairness. Using ns-2 simulations, we show that algorithms using multiple queues can significantly outperform RED and Blue, especially at smaller buffer sizes. Given a traffic mix of short-lived TCP flows with different round-trip times, longer round-trip time flows achieve 80% of their fair-share using multiqueue schedulers, compared to 40% under RED and Blue. We observe a similar performance improvement for multi-hop paths. We also show that performance results can be reliably scaled across a wide range of parameter values, so long as the ratio of the buffer size to the link bandwidth-delay product is held invariant.

We introduce the concept of a reserved delivery subnetwork (RDS) to allow an information service provider to deliver a higher quality of service to its customers. A network provider implements an RDS by provisioning reserved bandwidth on paths from a central site to distributed locations, where customers of the information service are located. The amount of bandwidth reserved is a function of the mean and variance of the traffic expected at the various locations. To configure an RDS, the network provider must select the links to be included and must dimension the reservations on those links appropriately. Network resource usage can often be reduced by routing flows destined for nearby cities along common paths. We show that the problem can be formulated as a minimum cost network flow problem with a concave cost function (one where the cost per unit flow decreases as the flow increases), which is a well-known NP-hard optimization problem. We introduce an approximate solution method and evaluate it experimentally. Our results are typically within a small factor of an easily computed lower bound.

Optical burst switching (OBS) is an experimental network technology that enables the construction of very high capacity routers, using optical data paths and electronic control. In this paper, we study two designs for wavelength converting switches that are suitable for use in optical burst switching systems and evaluate their performance. Both designs use tunable lasers to implement wavelength conversion. One is a strictly nonblocking design, that also requires optical crossbars. The second substitutes wavelength grating routers (WGR) for the optical crossbars, reducing cost, but introducing some potential for blocking. We show how the routing problem for the WGR-based switches can be formulated as a combinatorial puzzle or game, in which the design of the game board corresponds to the pattern of interconnections used to join the input sections of the switch to the output sections. We use this to show how the interconnection pattern affects the performance of the switch, and to facilitate the design of interconnection patterns that yield the best performance. Our results show that for a typical switch configuration, the WGR-based design can deliver more than 87% of the throughput of a fully nonblocking switch.

Multicast services can be provided either as a basic network service or as an application-layer service. Higher level multicast implementations often provide more sophisticated features, and can provide multicast services, where no network layer support is available. Overlay multicast networks offer an intermediate option, potentially combining the flexibility and advanced features of application layer multicast with the greater efficiency of network layer multicast. Overlay multicast networks play an important role in the Internet. Indeed, since Internet service providers have been slow to enable IP multicast in their networks, Internet multicast is only widely available as an overlay service. This paper introduces several routing algorithms that are suitable for overlay multicast networks and evaluates their performance. The algorithms seek to optimize the end-to-end delay and the interface bandwidth usage at the routing sites within the overlay network. The interface bandwidth is typically a key resource for an overlay network provider, and needs to be carefully managed in order to maximize the number of sessions that can be served. The simultaneous optimization of both delay and bandwidth is an NP-hard problem. We propose several heuristic algorithms and simulate their performance under various traffic conditions and on various network topologies.

Continuing growth in optical link speeds places increasing demands on the performance of Internet routers, while deployment of embedded and distributed network services imposes new demands for flexibility and programmability. IP address lookup has become a significant performance bottleneck for the highest performance routers. Amid the vast array of academic and commercial solutions to the problem, few achieve a favorable balance of performance, efficiency, and cost. New commercial products utilize content addressable memory (CAM) devices to achieve high lookup speeds at an exorbitantly high hardware cost with limited flexibility. In contrast, this paper describes an efficient, scalable lookup engine design, able to achieve high performance with the use of a small portion of a reconfigurable logic device and a commodity random access memory (RAM) device. The Fast Internet Protocol Lookup (FIPL) engine is an implementation of Eatherton and Dittia's previously unpublished Tree Bitmap algorithm (1998) targeted to an open-platform research router. FIPL can be scaled to achieve guaranteed worst-case performance of over 9 million lookups per second with a single SRAM operating at the fairly modest clock speed of 100 MHz. Experimental evaluation of FIPL throughput, latency, and update performance is provided using a sample routing table from Mae West.

Multicast services can be provided either as a basic network service or as an application-layer service. Higher level multicast implementations often provide more sophisticated features and can provide multicast services at places where no network layer support is available. Overlay multicast networks offer an intermediate option, potentially combining the flexibility and advanced features of application layer multicast with the greater efficiency of network layer multicast. In this paper, we introduce the multicast routing problem specific to the overlay network environment and the related capacity assignment problem for overlay network planning. Our main contributions are the design of several routing algorithms that optimize the end-to-end delay and the interface bandwidth usage at the multicast service nodes within the overlay network. The interface bandwidth is typically a key resource for an overlay network provider, and needs to be carefully managed in order to maximize the number of users that can be served. Through simulations, we evaluate the performance of these algorithms under various traffic conditions and on various network topologies. The results show that our approach is cost-effective and robust under traffic variations.

A prototype platform has been developed that allows processing of packets at the edge of a multi-gigabit-per-second network switch. This system, the Field Programmable Port Extender (FPX), enables packet processing functions to be implemented as modular components in reprogrammable hardware. All logic on the on the FPX is implemented in two Field Programmable Gate Arrays (FPGAs). Packet processing functions in the system are implemented as dynamically-loadable modules.

We consider the problem of resource reservation for networks. Current approaches for resource reservation in integrated service networks adopt an all-or-nothing approach, where partially acquired resources must be released if resources are not available at all routers on the chosen path. Furthermore, under high load, end-systems must retry requests repeatedly leading to inefficient allocation and increased traffic. We propose a new approach called Deferred REServation (DRES) that substantially improves performance (reduces the overall flow rejection probability and increases link utilization) over the all-or-nothing reservation approach. Flow admissibility is increased by deferring requests at routers for a limited period of time until resources are available. Analytical and simulation results confirm the performance benefits of our approach.

The provision of advanced computational services within networks is rapidly becoming both feasible and economical. We present a general approach to the problem of configuring application sessions that require intermediate processing by showing how the session configuration problem can be transformed to a conventional shortest path problem for unicast sessions or to a conventional Steiner tree problem for multicast sessions. We show, through a series of examples, that the method can be applied to a wide variety of different situations.

Application-level multicast is a new mechanism for enabling multicast in the Internet. Driven by the fast growth of network audio/video streams, application-level multicast has become increasingly important for its efficiency of data delivery and its ability of providing value-added services to satisfy application specific requirements. From a network design perspective, application-level multicast differs drastically from traditional IP multicast in its network cost model and routing strategies. We present these differences and formulate them as a network design problem consisting of two parts: one is bandwidth assignment in the overlay network, the other is load-balancing multicast routing with delay constraints. We use analytical methods and simulations to show that our design solution is a valid and cost-effective approach. Simulation results show that we are able to achieve network utilization within 10% of the best possible utilization while keeping the session rejection rate low.

Modern networks require the flexibility to support new protocols and network services without changes in the underlying hardware. Routers with general-purpose processors can perform data path packet processing using software that is dynamically distributed. However, custom processing of packets at link speeds requires immense computational power. This paper proposes a design of a scalable, high-performance active router. Multiple network processors with cache and memory on a single application specific integrated circuit are used to overcome the limitations of traditional single processor systems. The proposed design is used as a vehicle for studying the key issues that must be resolved to allow active networking to become a mainstream technology. Benchmark measurements are used to put the design in relation to actual application demands.

Finding the longest matching prefix from a database of keywords is an old problem with a number of applications, ranging from dictionary searches to advanced memory management to computational geometry. But perhaps today's most frequent best matching prefix lookups occur in the Internet, when forwarding packets from router to router. Internet traffic volume and link speeds are rapidly increasing; at the same time, a growing user population is increasing the size of routing tables against which packets must be matched. Both factors make router prefix matching extremely performance critical.In this paper, we introduce a taxonomy for prefix matching technologies, which we use as a basis for describing, categorizing, and comparing existing approaches. We then present in detail a fast scheme using binary search over hash tables, which is especially suited for matching long addresses, such as the 128 bit addresses proposed for use in the next generation Internet Protocol, IPv6. We also present optimizations that exploit the structure of existing databases to further improve access time and reduce storage space.

Field Programmable Gate Arrays (FPGAs) are being used to provide fast Internet Protocol (IP) packet routing and advanced queuing in a highly scalable network switch. A new module, called the Field-programmable Port Extender (FPX), is being built to augment the Washington University Gigabit Switch (WUGS) with reprogrammable logic.

There has been a rapid growth in applications such as World Wide Web browsing, which are characterized by fairly short sessions that transfer substantial amounts of data. Conventional connection-oriented and datagram services are not ideally engineered to handle this kind of traffic. We present a new ATM service, called Dynaflow service, in which virtual circuits are created on a burst-by-burst basis and we evaluate key aspects of its performance. We compare Dynaflow to the fast reservation protocol (FRP) and show that Dynaflow can achieve higher overall throughput due to the elimination of reservation delays, and through the use of shared "burst-stores." We study the queueing performance of the Dynaflow switch and quantify the relationship between the loss ratio and the buffer size.

This paper presents a new communication service for ATM networks that provides one-way, adjustable rate, on-demand communication channels. The proposed dynamic flow service is designed to operate within a multi-service cell switched network that supports both conventional switched virtual circuits and IP packet routing and is designed to complement those services. It is particularly well suited to applications that transmit substantial amounts of data (a few tens of kilobytes or more) in fairly short time periods (up to a few seconds). Much of the current World-Wide Web traffic falls within this domain. Like IP packet networks, the new service permits the transmission of data without prior end-to-end connection establishment. It uses a variant of ATM resource management cells to carry dynamic flow setup information along with the data, including an IP destination address and burst transmission rate. Switches along the path select next an outgoing link dynamically using the burst rate to guide the routing decision. The dynamic flow setup protocol is based on soft-state control and is designed to facilitate the use of buffers that are shared across all ports of a switch, minimizing per port memory costs.

No abstract available.

This paper develops a practical method for connection admission control in ATM networks. The method is based on a virtual cell loss probability criterion, is designed to handle heterogeneous traffic types and allows each traffic source to be described by an individual finite-state model with as many states as are needed to describe the source traffic. To make connection admission decisions with respect to individual links, an aggregate finite state model is computed from the individual models and used to estimate the virtual cell loss probabilities. To reduce the computational requirements for maintaining the aggregate traffic model, the aggregate model uses quantized data rates and is maintained incrementally using direct numerical convolution. The approximations required by the quantization process can be done in a strictly conservative way.

This paper describes the design and implementation of a gigabit ATM switching system supporting link rates from 150 Mb/s to 2.4 Gb/s, with a uniquely efficient multicast switch architecture that enables the construction of systems with essentially constant per port costs for configurations ranging from 8 to 4096 ports and system capacities approaching 10 Tb/s. The system design supports many-to-one and many-to-many forms of multicast, in addition to the usual one-to-many. It also provides multicast virtual paths, constant time configuration of multicast connections and an efficient packet-level discard method, that can achieve 100% link efficiencies, without large buffers.

Internet address lookup is a challenging problem because of increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. IP routing lookup requires computing the best matching prefix, for which standard solutions like hashing were believed to be inapplicable. The best existing solution we know of, BSD radix tries, scales badly as IP moves to 128 bit addresses. Our paper describes a new algorithm for best matching prefix using binary search on hash tables organized by prefix lengths. Our scheme scales very well as address and routing table sizes increase: independent of the table size, it requires a worst case time of log2(address bits) hash lookups. Thus only 5 hash lookups are needed for IPv4 and 7 for IPv6. We also introduce Mutating Binary Search and other optimizations that, for a typical IPv4 backbone router with over 33,000 entries, considerably reduce the average number of hashes to less than 2, of which one hash can be simplified to an indexed array access. We expect similar average case behavior for IPv6.

In a previous paper, one of the authors gave a worst case analysis for the early packet discard (EPD) technique for maintaining packet integrity during overload in ATM switches. This analysis showed that to ensure 100% goodput during overload under worst case conditions requires a buffer with enough storage for one maximum length packet from every active virtual circuit. This paper refines that analysis, using assumptions that are closer to what we expect to see in practice, and examines how EPD performs when the buffer is not large enough to achieve 100% goodput. We show that 100% goodput can be achieved with substantially smaller buffers than predicted by the worst case analysis, although the required buffer space can be significant when the link speed is substantially higher than the rate of the individual virtual circuits. We also show that high goodputs can be achieved with more modest buffer sizes, but that EPD exhibits anomalies with respect to buffer capacity, in that there are situations in which increasing the amount of buffering can cause the goodput to decrease. These results are validated by comparison with simulation.

This paper analyzes two popular heuristics for ensuring packet integrity in ATM switching systems. In particular, we analyze the behavior of packet tail discarding, in order to understand how the packet level link efficiency is dependent on the rates of individual virtual circuits and the degree of the imposed overload. In addition, we study early packet discard and show that the queue capacity needed to achieve high efficiency under worst-case conditions grows with the number of virtual circuits and we determine the efficiency obtainable with more limited queue capacities. Using the insights from these analyses, extensions to early packet discard are proposed which achieve high efficiency with dramatically smaller queue capacities (independent of the number of virtual circuits).

Asynchronous llansfer Mode (ATM) network technology is expected to become a central part of the emerging global information infrastructure.ATM networks introduce a number of feat urea that distinguish them from earlier technologies and introduce new issues in network control.This paper offers a framework for precisely defining and analyzing alternative approaches to the distributed controi of ATM networks and explores some of the key design issues through a series of examples, It is hoped that it will provide a useful foundation for researchers in networking and distributed computing interested in expJoring these issues further and developing more complete SOIUtions.

This paper describes research on new methods and architectures that enable the synergistic combination of IP and ATM technologies. We have designed a highly scalable gigabit IP router based on an ATM core and a set of tightly coupled general-purpose processors. This aItPm (pronounced "IP on ATM" or, if you prefer, "ip-attem") architecture provides flexibility in congestion control, routing, resource management, and packet scheduling.The aItPm architecture is designed to allow experimentation with, and fine tuning of, the protocols and algorithms that are expected to form the core of the next generation IP in the context of a gigabit environment. The underlying multi-CPU embedded system will ensure that there are enough CPU and memory cycles to perform all IP packet processing at gigabit rates. We believe that the aItPm architecture will not only lead to a scalable high-performance gigabit IP router technology, but will also demonstrate that IP and ATM technologies can be mutually supportive.

This paper describes an architecture for a multicast virtual circuit switch using cell recycling. This is the first nonblocking switch architecture that is optimal in both the switching network complexity and the amount of memory required for routing cells in multicast virtual circuits. Furthermore, it is optimal in the amount of effort required for multicast virtual circuit modification. This architecture makes it both technically and economically feasible to construct the large switching systems that will ultimately be needed for wide scale deployment of broadband ISDN to residential users.>

Several methods for analyzing the queuing behavior of switching networks with flow control and shared buffer switches are described. The methods are compared on the basis of accuracy and computation speed, with the performance metric of most concern being the maximum throughput. The best of the methods accurately predicts throughput for multistage networks constructed from large switches (>or=8 ports).>

Results for nonblocking distribution networks are generalized for the multirate environment in which different user connections share a switch's internal data paths for arbitrary fractions of the total capacity. Conditions under which network proposed by Y.P. Ofman (1965), C.D. Thompson (1978), and N. Pippenger (1973) lead to multirate distribution networks are derived. The results include both rearrangement and wide-sense nonblocking networks. The complexity of the rearrangement multirate network exceeds that of the corresponding space-division network by a log log factor, while the complexity of the wide-sense nonblocking network is within a factor of two of the corresponding space-division network.>

A method for analyzing the queueing behavior of switching networks constructed from switches that employ shared buffering or parallel bypass input buffering is presented. The queueing models introduced by Y.C. Jenq (1983) and generalized by T. Szymanski and S. Shaikh (1989) are extended to handle these classes of networks. The analysis explicitly models the state of an entire switch and infers information about the distribution of packets associated with particular inputs or outputs when needed. It is shown that the method can be extended to switching systems with input buffering, including systems supporting bypass queueing. Numerical comparisons of the different buffering techniques are included.>

Several improvements to T.T. Lee's (1988) multicast switch architecture are described. The improvements make Lee's architecture practical, allowing it to achieve maximum network throughput under worst-case conditions and vastly reducing the amount of memory required for the addressing of multicast cells. These improvements allow multicast to be added to a 256-port switch with 150-Mb/s links at a cost of about two additional chips per port.>

The authors describe several methods for analyzing the queueing behavior of switching networks with flow control and shared buffer switches. They compare the various methods on the basis of accuracy and computation speed, where the performance metric of most concern is the maximum throughput. The best of the methods accurately predicts throughput for multistage networks constructed from large switches (>or=8 ports).>

The problem of arbitrating access to a tree-structured communication channel, with large geographic extent, providing multipoint communication among a set of terminals, is considered. Terminals transmit information in bursts consisting of many packets and compete for the right to transmit bursts. In the simplest case, the channel allows only one terminal to transmit at a time; this can be extended to k concurrent transmitters. Two general approaches are identified. The first is based on the idea of transmit permits or tokens; that is, a terminal must have explicit permission to transmit before starting a burst. The second approach allows terminals to transmit whenever the number of bursts they can observe from their vantage point is less than the limiting number; the network then performs arbitration internally, possibly aborting some bursts in the process, to prevent too many bursts from being active on a link at one time. Several specific access arbitration algorithms based on these approaches are presented and assessed.>

The authors generalize known results for nonblocking distribution networks (also known as generalized connection networks) to the multirate environment, where different user connections share a switch's internal data paths in arbitrary functions of the total capacity. In particular, they derive conditions under which networks due to Y.P. Ofman (1965) and C.D. Thompson (1978), N. Pippenger (1973), and J.S. Turner (1989) lead to nonblocking multirate distribution networks. The results include both rearrangeable and wide-sense nonblocking networks. The complexity of most of our nonblocking multirate networks is roughly twice that of the corresponding space division networks. The one exception has complexity that exceeds that of the corresponding space division network by a log log factor.>

An extension of the classical theory of nonblocking networks is identified and studied that is applicable to multirate circuit and fast packet/ATM switching systems. Conditions are determined under which the Clos, Cantor, and Benes networks are strictly nonblocking. Conditions are also determined under which the Benes network and variants of the Cantor and Clos networks are rearrangeable. It is found that strictly nonblocking operation can be obtained for multirate traffic with essentially the same complexity as in the classical context.>

A framework is formulated for high-speed communication in an environment comprising a mix of subnetworks with widely varying characteristics. It combines elements of recent work on high-speed packet switching and on interworking of computer networks. The work on high-speed packet switching is expected to lead to the development of large public networks capable of supporting applications ranging from low-speed data to voice, high-speed data and video. Interworking of existing computer networks with high-speed connection-oriented networks will allow them to be used effectively by applications that require the high performance levels such networks can provide.>

Gigabit networks are but one element of technological revolution, albeit a particularly important one as they will provide the glue that allows the other pieces to interact. The applications of gigabit networks that will have the widest impact will be those that rely on visual information in one form or another, in part because such applications require the higher bandwidths that gigabit networks can provide and in part because they will make the new technology useful to a much wider population of users. There are many applications of such networks that can readily be envisioned, but this technology will certainly enable many applications that cannot yet be foreseen.>

An extension of the classical theory of connection networks is defined and studied. This extension models systems in which multiple connections of differing data rates share the links within a network. Conditions under which the Clos and Cantor networks are strictly nonblocking for multirate traffic are determined. The authors also determine conditions under which the Benes network and variants of the Cantor and Clos networks are rearrangeable. It is found that strictly nonblocking operation can be obtained for multirate traffic with essentially the same complexity as in the classical context.

The results of a simulation study undertaken to evaluate a high-performance packet-switching fabric supporting point-to-point and multipoint communications are presented. This switching fabric contains several components, each based on conventional binary routing networks. The most novel element is the copy network, which performs the packet replication needed for multipoint connections. Results characterizing the performance of the copy network are presented. Several architectural alternatives for conventional binary routing networks are also evaluated. For example, the performance gains obtainable by using cut-through switching in the context of binary routing networks with small buffers are quantified. One surprising result is that networks constructed from nodes with more then two input and output ports can perform less well than those constructed from binary nodes. This result is quantified and explained.>

An overview is given of a system designed to handle a heterogeneous and dynamically changing mix of applications. It is based on fiber-optic transmission systems and high-performance packet switching and can handle applications ranging from low-speed data to voice to full-rate video. A novel feature is a flexible multipoint connection capability suitable for broadcast and conferencing applications. The architecture of a switching systems that can be used to support this network is described.>

The Integrated Services Digital Network (ISDN) has been proposed as a way of providing integrated voice and data communications services on a universal or near-universal basis. In this paper, I argue that the evolutionary approach inherent in current ISDN proposals is unlikely to provide an effective long-term solution and I advocate a more revolutionary approach, based on the use of advanced packet-switching technology. The bulk of this paper is devoted to a detailed description of an Integrated Services Packet Network (ISPN), which I offer as an alternative to current ISDN proposals.

Most research in algorithm design relies on worst-case analysis for performance comparisons. Unfortunately, worst-case analysis does not always provide an adequate measure of an algorithm’s effectiveness. This is particularly true in the case of heuristic algorithms for hard combinatorial problems. In such cases, analysis of the probable performance can yield more meaningful results and can provide insight leading to better algorithms. The problem of minimizing the bandwidth of a sparse symmetric matrix by performing simultaneous row and column permutations, is an example of a problem for which there are well-known heuristics whose practical success has lacked a convincing analytical explanation. A class of heuristics introduced by Cuthill and McKee in 1969, and referred to here as the level algorithms, are the basis for bandwidth minimization routines that have been widely used for over a decade. At the same time, it is easy to construct examples, showing that the level algorithms can produce solutions that differ from optimal by an arbitrarily large factor. This paper provides an analytical explanation for the practical success of the level algorithms, by showing that for random matrices having optimal bandwidth no larger than k, any level algorithm will produce solutions that differ from optimal by a small constant factor. The analysis also suggests another class of algorithms with better performance. One algorithm in this class is shown to produce solutions that are nearly optimal.

The Integrated Services Digital Network (ISDN) has been proposed as a way of providing integrated voice and data communications services on a universal or near-universal basis. In this paper, I argue that the evolutionary approach inherent in current ISDN proposals is unlikely to provide an effective long term solution and advocate a more revolutionary approach, based on the use of advanced packet switching technology. The bulk of this paper is devoted to a detailed description of an Integrated Services Pocket Network (ISPN), which I offer as an alternative to current ISDN proposals.

Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in $O(n(\log n)^{d - 2} )$ steps. This has applications to integrated circuit layout, in particular the layout of Weinberger arrays [41]. This also yields an algorithm for determining the black/white pebble demand of degree three trees. We also show that for degree three trees, cutwidth is identical to search number and give a forbidden subgraph characterization of degree three trees having cutwidth k.

We study the probabilistic performance of heuristic algorithms for the NP-complete bandwidth minimization problem. Let (equation) be a graph with (equation). Define the bandwidth of G by (equation) where τ ranges over all permutations on V. Let A be a bandwidth minimization algorithm and let A (G) denote the bandwidth of the layout produced by A on the graph G. We say that A is a level algorithm if for all graphs (equation) the layout τ produced by A on G satisfies (equation) The level algorithms were first introduced by Cuthill and McKee [1] and have proved quite successful in practice. However, it is easy to construct examples that cause the level algorithms to perform poorly. Consequently worst-case analysis provides no insight to their practical success. In this paper we use probabilistic analysis in order to gain an understanding of these algorithms and to help us design better algorithms.

Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in O(n(logn)d-2) steps. This also yields an algorithm for determining the black/white pebble demand of degree three trees. A forbidden subgraph characterization is given for degree three trees having cutwidth k. This yields an interesting corollary: for degree three trees, cutwidth is identical to search number.