The Northbound (NB) APIs that SDN controllers provide differ in terms of architecture, syntax, naming convention, data resources, and usage. Using NB APIs to write SDN applications makes each application dependent on the API of a specific controller. To bring NB APIs from different vendors under one umbrella and make programming of SDN applications independent of specific controllers, we propose a unified software defined development framework that we call Umbrella. This paper presents the key components of the software and reports some preliminary results.

Using SDN to configure and control a multi-site network involves writing code that handles low-level details. We describe preliminary work on a framework that takes a network description and set of policies as input, and handles all the details of deriving routes and installing flow rules in switches. The paper describes key software components and reports preliminary results.

Software Defined Networking (SDN) offers flexibility to program a network based on a set of network requirements. Programming the networks using SDN is not completely straight-forward because a programmer must deal with low level details. To solve the problem, researchers proposed a set of network programming languages that provide a set of high level abstractions to hide low level hardware details. Most of the proposed languages provide abstractions related to packet processing and flows, and still require a programmer to specify low-level match-action fields to configure and monitor a network. Recently, in an attempt to raise the level at which programmers work, researchers have begun to investigate Intent-based, descriptive northbound interfaces. The work is still in early stages, and further investigation is required before intent-based systems will be adopted by enterprise networks. To help achieve the goal of moving to an intent-based design, we propose an SDN-based network programming framework, the Open Software Defined Framework (OSDF). OSDF provides a high level Application Programming Interface (API) that can be used by managers and network administrators to express network requirements for applications and policies for multiple domains. OSDF also provides a set of high level network operation services that handle common network configuration, monitoring, and Quality of Service QoS provisioning. OSDF is equipped with a policy conflict management module to help a network administrator detect and resolve policy conflicts. The paper shows how OSDF can be used and explains application-based policies. Finally, the paper reports the results of both testbed measurements and simulations that are used to evaluate the framework from multiple perspectives, including functionality and performance.

We present a novel emulation testbed design to test wireless protocols in an efficient, realistic, and reproducible manner, and use Wi-SUN Field Area Network (FAN) protocols to demonstrate its efficiency. The testbed provides emulated Layer 2 connectivity for a mesh of wireless nodes without needing to manipulate Layer 1 signals or inject radio frequency interference. An early version of the testbed that relied on a centralized server to forward packets introduced excessive differential delay that interfered with protocol operation. The improved version described in this paper achieves near-simultaneous delivery of a packet to the set of nodes within range of a sender. To provide an emulated delivery mechanism, the testbed uses multicast addressing in an unusual way. Each node is assigned a unique bit position within the multicast address space. Instead of sending outgoing packets to an emulation server, a node forms a multicast address with bits of the address set for all nodes within range, and multicasts the packet. Conceptually, each node is configured to accept a large set of multicast destination addresses that correspond to transmissions from neighbors in the emulated mesh topology. In practice, the testbed achieves packet recognition efficiently, without requiring a network interface to handle large numbers of multicast addresses. As a result, all neighbors of a node in the emulated mesh topology receive a copy of a packet at approximately the same time, like an actual wireless network. The paper also describes a software-defined programmable management system that uses scripted testbed commands to run sequences of tests.

We present a technique of providing resiliency in a computer network which some mission-critical applications require. The technique involves the use of redundancy through packet duplication and transmission over multiple disjoint paths between a pair of nodes in a network. To create a general-purpose resiliency system, we introduce a new network element, a Redundancy Controller (RC) that establishes and maintains the redundancy end hosts request. An RC also monitors path performance and replaces poorly performing paths. End users are able to specify criteria required for the performance of paths. The paper reports on work in progress. It outlines the motivation behind the project and describes our implementation plan.

This paper addresses the problem of scheduling variable-size packets from large number of distinct traffic flows. Although the problem of fair packet scheduling in computer networks has received thorough theoretical consideration, practical high-speed packet scheduling systems remain elementary. The disparity arises because algorithms with theoretically favorable delay and fairness characteristics have unacceptably high computational cost, while algorithms of low complexity have substantially inferior properties. A variety of hybrid scheduling methods have been proposed as a compromise, but we argue that existing hybrid algorithms are either impractical, or do not provide full spectrum of required features. We then formally define requirements for a packet scheduler and propose a hybrid scheduling algorithm which guarantees these requirements. We develop a theoretical framework to prove that our algorithm indeed provides all the properties claimed.

In this paper we propose design principles for implementation of hybrid packet schedulers with parallel and pipelined hardware architecture. Packet schedulers are the algorithms used to schedule variable-sized packets from large number of distinct traffic flows, sharing a single network link. Hybrid schedulers are intended to achieve constant deviation from ideal general processor sharing (GPS) scheduler and constant computational complexity per single packet transmission. While theoretical properties of hybrid algorithms have been studied well, their practical implementation had not been addressed yet. This paper describes an approach to create a generic framework, suitable for efficient implementation of hybrid schedulers. We introduce a concept of an atomic scheduling object, called a scheduling queue (SQ), and demonstrate how a hybrid scheduler can be constructed as a set of interacting SQs. We also present experimental results obtained on a prototype system.

This paper addresses the problem of scheduling variable-size packets from large number of distinct traffic flows. Although the problem of fair packet scheduling in computer networks has received thorough theoretical consideration, practical high-speed packet switching systems remain elementary. The disparity arises because algorithms with theoretically favorable delay and fairness characteristics have unacceptably high computational cost. A variety of hybrid scheduling methods have been proposed as a compromise; this paper discusses the design and implementation of hybrid schedulers. We focus on algorithms suitable for high speed networks, and the study is experimental - the algorithms are implemented on network processor hardware, and actual packet data is used to assess performance.

In a computer network that consists of M subnetworks, the L-bit address of a machine consists of two parts: A prefix s/sub i/ that contains the address of the subnetwork to which the machine belongs, and a suffix (of length L-Is/sub i/I) containing the address of that particular machine within its subnetwork. In fixed-length subnetwork addressing, Is/sub i/I is independent of I, whereas, in variable length subnetwork addressing, Is/sub i/I varies from one subnetwork to another. To avoid ambiguity when decoding addresses, there is a requirement that no s/sub i/ be a prefix of another s/sub i/. The practical problem is how to find a suitable set of s/sub i/s in order to maximize the total number of addressable machines, when the ith subnetwork contains n/sub i/ machines. Not all of the n/sub i/ machines of a subnetwork i need be addressable in a solution: If n/sub i/>2(L-|s/sub i/|), then only 2(L-|s/sub j/|) machines of that subnetwork are addressable (none is addressable s/sub i/ the solution assigns no address s/sub i/ to that subnetwork). The abstract problem implied by this formulation is: Given an integer L, and given M (not necessarily distinct) positive integers n/sub 1/,...,n/sub M/, find M binary strings s/sub 1/,...,s/sub M/ (some of which may be empty) such that (1) no nonempty string s/sub i/ is prefix of another string s/sub j/, (2) no s/sub i/ is more than L bits long, and (3) the quantity /spl Sigma/(|s/sub k/|/spl ne/0) min{n/sub k/,2(L-|s/sub k/|)} is maximized. We generalize the algorithm to the case where each n/sub i/ also has a priority p/sub i/ associated with it and there is an additional constraint involving priorities: Some subnetworks are then more important than others and are treated preferentially when assigning addresses. The algorithms can be used to solve the case when L itself is a variable; that is, when the input no longer specifies L but, rather, gives a target integer /spl gamma/ for the number of addressable machines, and the goal is to find the smallest L whose corresponding optimal solution results in at least /spl gamma/ addressable machines.

A congestion avoidance and control scheme that monitors the incoming traffic to each destination and provides rate-based feedback information to the sources of bursty traffic so that sources of traffic can adjust their packet rates to match the network capacity is described. The congestion avoidance mechanism at nodes on the periphery of the network controls incoming traffic so that it does not exceed the capacity of paths to different destinations. The congestion control mechanism at each node monitors the performance of adjacent links and generates rate control messages that warn the sources of traffic before congestion develops. Some existing schemes are reviewed, and the congestion avoidance and control scheme and its applicability to various transport protocols are discussed. Experiments show that the scheme is effective in preventing congestion inside the network and that it manages to restrict the traffic on any overloaded path to 80%-90% of its capacity.>

As networks and internetworks of computers expand in size and scope, discovery and location of resources becomes a primary function of the networked computing environment. Static tables describing network resources have been replaced by dynamic directory services, such as X.500 and the Internet Domain Name System. These dynamic directory services provide more timely and accurate information about network resources than static tables.A wide variety of services address various components of the resource discovery and location problem. These services can be loosely classified as either low-level protocols or high-level services. Low-level protocols, such as RARP and ICMP, are simple delivery protocols and provide limited information; high-level services, such as the Internet Domain Name System and X.500, use complex delivery protocols to answer complex queries. Neither class of directory service is appropriate in all situations. Low-level services are too restrictive in the type of queries and information they support, while high-level services may be too expensive for some low-function networks.

A network-level communication abstraction called flow is discussed as a communication channel that has specific performance characteristics associated with its traffic. The underlying delivery system guarantees to meet performance requirements of a flow once it accepts a flow request. Upper layers use flows to implement transport-level protocols and high performance applications. The authors describe the concept of flows in detail and present algorithms that implement flows in a high-speed packet-switched network under development at Purdue University.>

The use of long-haul networks by the scientific community to access resources at supercomputing centers has created a need for high-level user services and tools to provide transparent and efficient access to remote resources. A way to provide a computational service for supercomputer access in a distributed environment is described. The issues involved in the design of such a service are discussed, and attention is focused on a remote job submission facility. A prototype implementation is also described.>

It is ACM's 40th year and an old debate continues. Is computer science a science? An engineering discipline? Or merely a technology, an inventor and purveyor of computing commodities? What is the intellectual substance of the discipline? Is it lasting, or will it fade within a generation? Do core curricula in computer science and engineering accurately reflect the field? How can theory and lab work be integrated in a computing curriculum?We project an image of a technology-oriented discipline whose fundamentals are in mathematics and engineering — for example, we represent algorithms as the most basic objects of concern and programming and hardware design as the primary activities. The view that “computer science equals programming” is especially strong in our curricula: the introductory course is programming, the technology is in our core courses, and the science is in our electives. This view blocks progress in reorganizing the curriculum and turns away the best students, who want a greater challenge. It denies a coherent approach to making experimental and theoretical computer science integral and harmonious parts of a curriculum.Those in the discipline know that computer science encompasses far more than programming. The emphasis on programming arises from our long-standing belief that programming languages are excellent vehicles for gaining access to the rest of the field — but this belief limits out ability to speak about the discipline in terms that reveal its full breadth and richness.The field has matured enough that it is now possible to describe its intellectual substance in a new and compelling way. In the spring of 1986, ACM President Adele Goldberg and ACM Education Board Chairman Robert Aiken appointed this task force with the enthusiastic cooperation of the IEEE Computer Society. At the same time, the Computer Society formed a task force on computing laboratories with the enthusiastic cooperation of the ACM.The charter of the task force has three components: Present a description of computer science that emphasizes fundamental questions and significant accomplishments.Propose a new teaching paradigm for computer science that conforms to traditional scientific standards and harmoniously integrates theory and experimentation.Give at least one detailed example of a three-semester introductory course sequence in computer science based on the curriculum model and the disciplinary description.We immediately extended our task to encompass computer science and computer engineering, for we came to the conclusion that in the core material there is no fundamental difference between the two fields. We use the phrase “discipline of computing” to embrace all of computer science and engineering. The rest of this paper is a summary of the recommendation.The description of the discipline is presented in a series of passes, starting from a short definition and culminating with a matrix as shown in the figure. The short definition:Computer science and engineering is the systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation, and application. The fundamental question underlying all of computing is, “What can be (efficiently) automated?”The detailed description of the field fills in each of the 27 cells in the matrix with significant issues and accomplishments. (That description occupies about 16 pages of the report.)For the curriculum model, we recommend that the introductory course consist of regular lectures and a closely coordinated weekly laboratory. The lectures emphasize fundamentals; the laboratories emphasize technology and know-how. The pattern of closely coordinated lectures and labs can be repeated where appropriate in other courses. The recommended model is traditional in the physical sciences and in engineering: lectures emphasize enduring principles and concepts while laboratories emphasize the transient material and skills relating to the current technology.

A new message communication paradigm based on conversations that provides an alternative to memo - and conference -based mail is described. A conversation-based message system groups messages into conversations, and orders messages within a conversation according to the context in which they were written. The message context relation leads to an efficient implementation of conversations in a distributed environment and supports a natural ordering of messages when viewed by the user. Experience with a prototype demonstrates the workability of conversation-based mail and suggests that conversations provide a powerful tool for message communication.

Although the principle goal of the DARPA Domain Name project is to provide a distributed name resolution mechanism for host names in the DARPA Internet, it is envisioned that the domain naming scheme will also support names for mailboxes in a global mail system that extends to mail networks beyond the DARPA Internet. In addition to overviewing the fundamental ideas behind the domain name scheme and outlining a proposal for using domain names as an umbrella naming system for computer mail, we discuss the administrative and technical problems involved in using domain names in the global mail system.

Researchers at Bell Labs have recently developed a silicon compiler, named Plex, that automatically generates VLSI layouts of high performance and area efficient microprocessors. Plex takes as input a specification of the function to be executed and generates a complete mask-level layout of a customized microprocessor to execute that function. The Plex microprocessor interacts with the external world, via input and output wires, and interrupts. The dedicated function performed by a Plex microprocessor typically involves real-time handling of inputs and interrupts-and the real-time generation of output signals.

CSNET is built on the Department of Defense network (ARPANET), public packet-switched physical networks (Telenet), and a telephone-based relay network (Phonenet). Some CSNET sites have direct connections to ARPANET, some have direct connections to Telenet, and some have connections only to telephone-based relay machines. The chief objective of CSNET is to provide a network interconnection for all groups engaged in Computer Science Research.

Abstract The programming language Pascal was designed and implemented in a non‐interactive programming environment. This paper surveys proposals for incorporating interaction into Pascal, and focuses on a scheme known as ‘lazy evaluation’. It presents and compares performance measurements of two Pascal run‐time systems for the same compiler; a buffered, non‐interactive version, and a modification of that system to support lazy evaluation.

Efficient algorithms are presented for two geometric problems. Both problems involve finding the best projection of a set of points from two-space onto a line, with two different notions of “best”. The key technique is to identify critical angles in between which the functions to be optimized have nice trigonometric forms that can be solved exactly. Applications to hashing arise when we look for the best linear combination of two hashing functions.

Abstract Ffg is a simple database system that consists of a set of many independent programs, called primitives, each of which performs a single operation. The user composes primitives by connecting the output of one to the input of the next to achieve a computation. Because they are independent, primitives are easily modified or replaced, and one can add programs to the set of primitives. Unlike the strongly typed interconnections provided by many languages, interconnections of ffg primitives are not type‐checked. The implementation ffg is also novel because ffg primitives are constructed out of lower level primitives instead of conventional programs. The selection of primitives, the type checking mechanism and the implementation are discussed.

Abstract When a document is prepared using a computer system, it can be checked for spelling errors automatically and efficiently. This paper reviews and compares several methods for searching an English spelling dictionary. It also presents a new technique, hash‐bucket search, for searching a static table in general, and a dictionary in particular. Analysis shows that with only a small amount of space beyond that required to store the keys, the hash‐bucket search method has many advantages over existing methods. Experimental results with a sample dictionary using double hashing and the hash‐bucket techniques are presented.

Abstract In an excellent paper1, Young describes a tool that aids the Pascal programmer by providing support for data abstractions. This paper compares Young's work to a similar tool for Pascal that has been designed and implemented by the authors. It demonstrates that parameterized module instantiations allow one to express some abstractions more naturally than does Young's method. The design goals and implementation details are discussed.

A trie is a distributed-key search tree in which records from a file correspond to leaves in the tree. Retrieval consists of following a path from one root to a leaf, where the choice of edge at each node is determined by attribute values of the key. For full tries, those in which all leaves lie at the same depth, the problem of finding an ordering of attributes which yields a minimum size trie is NP-complete. This paper considers a “greedy” heuristic for constructing low-cost tries. It presents simulation experiments which show that the greedy method tends to produce tries with small size, and analysis leading to a worst case bound on approximations produced by the heuristic. It also shows a class of files for which the greedy method may perform badly, producing tries of high cost.

The art of programming is taught, learned, and often practiced as if programs are disposable, personal objects owned, solely by the programmer. This paper uses examples to illustrate why real software is neither personal nor disposable; it shows how even simple programs are shared by others. From the examples, the paper extracts four principles for program development. Finally, it draws conclusions about programming practices and the education of programmers.

The median split tree is an elegant technique for searching static sets of keys when the frequency of access is highly skewed. This paper generalizes the median split search technique, relates it to sequential search and binary search, discusses the choice of an optimum search strategy for a given set of keys, and poses several related optimization problems.

Abstract The programming language Pascal was originally designed for teaching introductory programming. Currently, however, production systems use it as the primary implementation language. This paper describes extensions of Pascal intended to aid the large program developer. The extensions are implemented in a macro preprocessor MAP, which supports constant expression evaluation, source file inclusion, conditional compilation and macro substitution. While each of these features can be used independently, they are all implemented with a simple, uniform syntax. Furthermore, in keeping with the spirit of Pascal, an attempt has been made to make the facilities straightforward and simple. The design and implementation details are discussed.

A trie is a digital search tree in which leaves correspond to records in a file. Searching proceeds from the root to a leaf, where the edge taken at each node depends on the value of an attribute in the query. Trie implementations have the advantage of being fast, but the disadvantage of achieving that speed at great expense in storage space. Of primary concern in making a trie practical, therefore, is the problem of minimizing storage requirements. One method for reducing the space required is to reorder attribute testing. Unfortunately, the problem of finding an ordering which guarantees a minimum-size trie is NP-complete. In this paper we investigate several heuristics for reordering attributes, and derive bounds on the sizes of the worst tries produced by them in terms of the underlying file. Although the analysis is presented for a binary file, extensions to files of higher degree are shown. Another alternative for reducing the space required by a trie is an implementation, called an Ο-trie, in which the order of attribute testing is contained in the trie itself. We show that for most applications, Ο-tries are smaller than other implementations of tries, even when heuristics for improving storage requirements are employed.

In this paper we: 1) discuss the need for quantitatively reproducible experiments in the study of top-down design; 2) propose the design and writing of tutorial papers as a suitably general and inexpensive vehicle; 3) suggest the software science parameters as appropriate metrics; 4) report two experiments validating the use of these metrics on outlines and prose; and 5) demonstrate that the experiments tended toward the same optimal modularity.

Abstract RATFOR is a preprocessor language for FORTRAN that supports structured flow of control statements and macrosubstitution. The RATFOR processor, written in RATFOR, is modular, carefully coded and portable, but extremely inefficient. A profile of the running time revealed that a linear search in the macroprocessor consumed over half of the CPU time. Running time was reduced by over 50 per cent when a binary search was used. Our observation is of interest primarily because it differs from previously reported measurements. A more dramatic improvement in running time was obtained by rewriting the ad hoc lexical scanner using a standard method based on finite automata. For a 3,000‐line source program the standard RATFOR required 185.470 CPU seconds on a CDC 6500 while the automata‐based version needed only 12.723 seconds. We conclude that, contrary to evidence exhibited by the designer of RATFOR, sequential search is often inadequate for production software. Furthermore, in the case of lexical analysis, well‐known techniques do seem to offer efficiency while retaining the simplicity, ease of coding and modularity of ad hoc methods.

Given a file on a secondary store in which each record has several attributes, it is usually advantageous to build an index mechanism to decrease the cost of conducting transactions to the file. The problem of selecting attributes over which to index has been studied in the context of various storage structures and access assumptions. One algorithm to make an optimum index selection requires 2 k steps in the worst case, where k is the number of attributes in the file. We examine the question of whether a more efficient algorithm might exist and show that even under a simple cost criterion the problem is computationally difficult in a precise sense. Our results extend directly to other related problems where the cost of the index depends on fixed values which are assigned to each attribute. Some practical implications are discussed.

Trle structures are a convenient way of indexing files in which a key consists of a number of attributes Records correspond to leaves in the trle Retrieval proceeds by following a path from the root to a leaf, the choice of edges being determined by attribute values The size of a trle for a file depends on the order in which attributes are tested It is shown that determining minimal size tries IS an NP-complete problem for several variants of tries and that, for tries m which leaf chains are deleted, determining the trie for which average access time is minimal is also an NP-complete problem These results hold even for files in which attribute values are chosen from a binary or ternary alphabet KE] WORDS AND PHRASES reformation retrieval, trle indexes, trte size, average search time, complexity CR CATEGORIES 3 74, 4 33, 5 25

Trie structures are a convenient way of indexing files in which keys are specified by values of attributes. Records correspond to leaves in the trie. Retrieval proceeds by following a path from the root to a leaf, the choice of edges being determined by attribute values. The size of a trie for a file depends on the order in which attributes are tested. We show that determining minimal size tries is an NP-complete problem for several variants of tries. For tries in which leaf chains are deleted we show that determining the trie for which average access time is minimal is also an NP-complete problem. Our results hold even for files in which attribute values are chosen from a binary or ternary alphabet.