We provide a formal model for the Change Management process for Enterprise IT systems, and develop change scheduling algorithms that seek to attain the "change capacity" of the system. The change management process handles critical updates in the system that often use overlapping sets of servers, resulting in scheduling conflicts between the corresponding change classes. Furthermore, applications are typically associated with certain permissible downtime windows, which impose constraints on the timing of the change executions. Scheduling of changes for such systems represent a complex dynamic optimization question. In a limiting fluid regime, where changes are assumed nonatomic, we develop a scheduling policy that provably attains the change capacity of the system. We then propose and evaluate an atomic approximation of the optimal fluid scheduling policy, which is well suited for application to a real change management system. Simulation results demonstrate that the expected change execution delay and the capacity attained by the approximate policy is close to the best attainable values, when unavoidable capacity losses due to fragmentation effects are taken into account and is significantly better than a randomized scheduling policy.

Server providers that support e-commerce applications as a service for multiple e-commerce Web sites traditionally use a tiered server architecture. This architecture includes an application tier to process requests for dynamically generated content. How this tier is provisioned can significantly impact a provider's profit margin. In this article we study methods to provision servers in the application serving tier that increase a server provider's profits. First, we examine actual traces of request arrivals to the application tier of an e-commerce site, and show that the arrival process is effectively Poisson. Next, we construct an optimization problem in the context of a set of application servers modeled as M / G /1/ PS queueing systems, and derive three simple methods that approximate the allocation that maximizes profits. Simulation results demonstrate that our approximation methods achieve profits that are close to optimal, and are significantly higher than those achieved via simple heuristics.

Today Internet QoS is deployed piecemeal - typically at known bottleneck links like enterprise access links or wireless links. A more comprehensive, end-to-end QoS deployment, for instance across large enterprise networks or the global Internet, remains elusive. There is growing interest in the idea of using overlay networks to provide differential QoS services (improve performance for some flows at the expense of other flows). A necessary building block is the ability to provide differential service over a single overlay link that traverses many IP router hops. This work presents MPAT, the first truly scalable algorithm for fairly providing differential services to TCP flows that share a bottleneck link. Unlike known schemes, our approach preserves the cumulative fair share of the aggregated flows even where the number of flows in the aggregate is large. Specifically we demonstrate, primarily through experiments on the real Internet, that congestion state can be shared across more than 100 TCP flows with throughput differentials of 95:1. This is up to five times better than differentials achievable by known techniques. Indeed, MPAT scalability is limited only by the delay-bandwidth product of the aggregated flows. With this tool, it is now possible to seriously explore the viability of network QoS through overlay network services.

Server providers that support e-commerce applications as a service to multiple e-commerce websites traditionally use a tiered server architecture. This architecture includes an application tier to process requests that require dynamically generated content. How this tier is provisioned can significantly impact a provider's profit margin. We study methods to provision servers in the application serving tier to increase a server provider's profits. First, we examine actual traces of request arrivals to the application tier of e-commerce sites, and show that the arrival process is effectively Poisson. Next, we construct an optimization problem in the context of a set of application servers modeled as M/G/l/PS queueing systems, and derive three simple methods to approximate the allocation that maximizes profits. Simulation results demonstrate that our approximation methods achieve profits that are close to optimal and are significantly higher than those achieved via simple heuristics.

A major challenge in Internet edge router design is to support both high packet forwarding performance and versatile and efficient packet processing capabilities. The thesis of this research project is that a cluster of PCs connected by a high speed system area network provides an effective hardware platform for building routers to be used at the edges of the Internet. This paper describes a scalable and extensible edge router architecture called Panama, which supports a novel aggregate route caching scheme, a real-time link scheduling algorithm whose performance overhead is independent of the number of real-time flows, a highly efficient kernel extension mechanism to safely load networking software extensions dynamically, and an integrated resource scheduler which ensures that real-time flows with additional packet processing requirements still meet their end-to-end performance requirements. This paper describes the implementation and evaluation of the first Panama prototype based on a cluster of PCs and Myrinet.

A major challenge in Internet edge router design is to support both high packet forwarding performance and versatile and efficient packet processing capabilities. The thesis of this research project is that a cluster of PCs connected by a high-speed system area network provides an effective hardware platform for building routers to be used at the edges of the Internet. This paper describes a scalable and extensible edge router architecture called Panama, which supports a novel aggregate route caching scheme, a real-time link scheduling algorithm whose performance overhead is independent of the number of real-time flows, a highly efficient kernel extension mechanism to safely load networking software extensions dynamically, and an integrated resource scheduler which ensures that real-time flows with additional packet processing requirements still meet their end-to-end performance requirements. This paper describes the implementation and evaluation of the first Panama prototype based on a cluster of PCs and Myrinet.

Placement of computation inside the network is a powerful computation model that can improve the overall performance of network applications. The authors address the problem of providing sound and efficient system support for placing computation in a network router We identify a set of requirements, related to protection, resource control, scheduling and efficiency, that are relevant to the design of this system support. We have developed a system that attempts to meet these requirements, and have used it to write a router application that performs aggregated congestion control.

The exponential growth in Internet traffic has motivated the development of a new breed of microprocessors called network processors, which are designed to address the performance problems resulting from the explosion in Internet traffic. The development efforts of these network processors concentrate almost exclusively on streamlining their data paths to speed up network packet processing, which mainly consists of routing and data movement. Rather than blindly pushing the performance of packet processing hardware, an alternative approach is to avoid repeated computation by applying the time-tested architecture idea of caching to network packet processing. Because the data streams presented to network processors and general-purpose CPUs exhibit different characteristics, detailed cache design tradeoffs for the two also differ considerably. This research focuses on cache memory design specifically for network processors. Using a trace-drive simulation methodology, we evaluate a series of three progressively more aggressive routing-table cache designs. Our simulation results demonstrate that the incorporation of hardware caches into network processors, when combined with efficient caching algorithms, can significantly improve the overall packet forwarding performance due to a sufficiently high degree of temporal locality in the network packet streams. Moreover, different cache designs can result in up to a factor of 5 difference in the average routing table lookup time, and thus in the packet forwarding rate.

Suez is a high-performance real-time packet router that supports fast best-effort packet routing and scalable QoS-guaranteed packet scheduling, and is built on a hardware platform consisting of a cluster of commodity PCs connected by a gigabit/sec system area network. The major goal of the Suez project is to demonstrate that the PC cluster architecture can be as cost-effective a platform for high-performance network packet routing as for parallel computing. Suez features a cache-conscious routing-table search algorithm that exploits CPU caching hardware for fast lookup by treating IP addresses directly as virtual addresses. To scale the number of real-time connections supportable with the link speed, Suez implements a fixed-granularity fluid fair queuing (FGFFQ) algorithm that completely eliminates the per-packet sorting overhead associated with conventional weighted fair queuing algorithms. This paper presents the architectural features of Suez, and reports the performance measurements of the Linux-based Suez prototype, which is built on four Pentium-II 400 MHz machines and Myrinet.

Extensive research in TCP's congestion control mechanism has resulted in an effective algorithm that gives fairly precise estimates on the available bandwidth on a given network path (J. Postel, 1981; V. Jacobson, 1988). However, most past efforts focused on enhancing the accuracy and robustness of the path bandwidth estimation algorithms for individual TCP connections. Relatively fewer attempts have been made to further improve data transport efficiency by sharing path bandwidth information among concurrent TCP connections with the same sources and destinations. The paper proposes an aggregate TCP-based congestion control algorithm (ATCP) that allows individual TCP connections to reach their fair shares of the available network path bandwidth more quickly, while still observing TCP's congestion control semantics. In addition, the proposed algorithm is guaranteed to perform no worse than current TCP congestion control algorithm in all cases, and is designed to be implemented in a way that is completely transparent to both ends of a TCP connection. ATCP is particularly useful for TCP connections that are short-lived and yet have a long round-trip delay, such as Web page transfers using HTTP 1.0. Our trace-driven simulation study shows that the aggregate congestion control algorithm can reduce the normalized transaction latency by a factor of up to 2, compared to standard TCP.

In this paper, we share our experience in designing and building a content-based switch which we call L5. In addition to the layer 2-3-4 information available in the packet, a content-based switch uses application level information to route traffic in the network. Making routing decisions based on information contained in the payload is not a new idea. In fact application level proxies which are functionally equivalent to a content-based switch, have been around for years. Our contribution is in combining the functionalities of an application level proxy with the data handling capabilities of a switch into a single system. In this paper, we describe the architecture of the L5 system along with the details of how application level information can be efficiently processed in the switch hardware. We cover two specific application examples that we believe are ideal candidates for content-based switching: one is routing HTTP sessions based on uniform resource locators (URL) and the other is session-aware dispatching of secure socket layer (SSL) connections.

Wire-speed IP (Internet Protocol) routers require very fast routing table lookup for incoming IP packets. The routing table lookup operation is time consuming because the part of an IP address used in the lookup, i.e., the network address portion, is variable in length. This paper describes the routing table lookup algorithm used in a cluster-based parallel IP router project called Suez. The innovative aspect of this algorithm is its ability to use CPU caching hardware to perform routing table caching and lookup directly by carefully mapping IP addresses to virtual addresses. By running a detailed simulation model that incorporates the performance effects of the CPU memory hierarchy against a packet trace collected from a major network router, we show that the overall performance of the proposed algorithm can reach 87.87 million lookups per second for a 500-MHz Alpha processor with a 16-KByte L1 cache and a 1-MByte L2 cache. This result is one to two orders of magnitude faster than previously reported results on software-based routing table lookup implementations. This paper also reports the performance impacts of various architectural parameters in the proposed scheme and its storage costs, together with the measurements of an implementation of the proposed scheme on a Pentium-II machine running Linux.

The trend towards extensible software architectures and component-based software development demands safe, efficient, and easy-to-use extension mechanisms to enforce protection boundaries among software modules residing in the same address space. This paper describes the design, implementation, and evaluation of a novel intra-address space protection mechanism called Palladium, which exploits the segmentation and paging hardware in the Intel X86 architecture and efficiently supports safe kernel-level and user-level extensions in a way that is largely transparent to programmers and existing programming tools. Based on the considerations on ease of extension programming and systems implementation complexity, Palladium uses different approaches to support user-level and kernel-level extension mechanisms. To demonstrate the effectiveness of the Palladium architecture, we built a Web server that exploits the user-level extension mechanism to invoke CGI scripts as local function calls in a safe way, and we constructed a compiled network packet filter that exploits the kernel-level extension mechanism to run packet-filtering binaries safely inside the kernel at native speed. The current Palladium prototype implementation demonstrates that a protected procedure call and return costs 142 CPU cycles on a Pentium 200MHz machine running Linux.