Novel network architectures with distributed service components on both routers and end-systems have been proposed to provide the necessary flexibility in the next-generation Internet. Such architectures allow services to be composed along the data path to satisfy different communication requirements. A major operational challenge in such systems is to determine where to perform the required services along the data path. This problem, which we call as the "service placement problem" is proven to be NP-complete when considering resource (e.g., link and processing capacity) constraints. In this paper, we present an evaluation of several existing and newly developed heuristic algorithms for solving the problem. We explore the quality of the achieved placement in terms of effective use of system resources, end-to-end delay, connection drop rate, and load balancing. Our results show the design trade-offs of these different algorithms.

In the next-generation Internet architecture, more functionality will be placed in the data path of routers in the form of "services" and other packet processing features. This trend will increase the amount of state information that is maintained by system inside the network. In this paper, we present a framework for structuring and managing network state information distributed across the next-generation Internet architecture.

Many next-generation Internet architectures propose advanced packet processing functions in the data path of the network. Such "services" are typically performed on some nodes along the path of a packet. We present a novel decentralized algorithm that can determine an allocation of services to network nodes. The algorithm can obtain globally optimal solutions for a single service and approximate solutions for two or more services. In our simulation results, we validate the correctness of the algorithm, quantify the quality of the approximations, and compare the results to those of a centralized algorithm. Our results show that the proposed algorithm presents an effective solution to the service placement problem that can be implemented in a realistic network.

Advanced packet processing functions in the data path of routers are commonly used in the current Internet and are likely to expand in next-generation networks. One of the key challenges related to such “network services” is to develop a suitable control plane infrastructure for routing and connection setup. In this paper, we present a novel distributed algorithm and routing protocol to facilitate allocation of services during connection setup. The protocol is scalable for deployment in large networks and can obtain globally optimal solutions for a single service and approximate solutions for two or more services. We have implemented a prototype on Emulab to evaluate the proposed protocol. Our implementation shows that the proposed protocol is indeed an effective and scalable solution to the routing problem in networks with data-path services.

Considerable research efforts in the networking community are focused on defining a new Internet architecture that not only solves some of the problems of the current design, but also meets future needs. Our work focuses on the issue of how to provide suitable abstractions for communication between end-systems. This is a particularly important aspect of the network architecture as it is exposed to all applications and also determines what kind of services can be provided by the network. We present an architecture for network services that are implemented on router systems. We illustrate how control and data plane interact to provide the necessary end-to-end functionality. Our prototype implementation indicates that such a design is feasible and scalable for high-performance networks.