Recent parallel programming frameworks such as OpenCL and OpenMP allow us to enjoy the parallelization freedom for real-time tasks. The parallelization freedom creates the time versus density tradeoff problem in fluid scheduling, i.e., more parallelization reduces thread execution times but increases the density. By system-widely exercising this tradeoff, we propose optimal parameter tuning of real-time tasks aiming at maximizing the schedulability of multicore fluid scheduling. Our experimental study by both simulation and actual implementation shows that the proposed approach well balances the time and the density, and results in up to 80 percent improvement of the schedulability.

As the software complexity drastically increases for multiresource real-time systems, industries have great needs for analytically validating real-time behaviors of their complex software systems. Possible candidates for such analytic validations are the end-to-end response time analysis techniques that can analytically find the worst-case response times of real-time transactions over multiple resources. The existing techniques, however, exhibit severe overestimation when real-time transactions visit the same resource multiple times, which we call a multiple visit problem. To address the problem, this paper proposes a novel analysis that completely changes its analysis viewpoint from classical per-job basis-aggregation of per-job response times-to per-resource basis-aggregation of per-resource total delays. Our experiments show that the proposed analysis can find significantly tighter bounds of end-to-end response times compared with the existing per-job-based analysis.

Several research studies have been devoted to improving the reliability and performance of the Internet by utilizing redundant communication paths between end points. Multihoming, coupled with intelligent route control, and overlay networks are two main streams in this area of research which attempt to leverage redundant connections of the Internet for increased reliability and performance. However, the effectiveness of these approaches depends on the natural diversity of redundant paths between two endhosts in terms of physical links, routing infrastructure, administrative control, and geographical distribution. Even in the case of redundant paths, if traffic between two hosts is not actually routed along completely disjoint paths, congestion or failure of a single shared link or router can adversely affect the end-to-end performance or availability of all paths. This paper presents an experimental study of path diversity on the Internet, focusing on the impact of path diversity on multihomed and overlay networks. We base our analysis on traceroutes and routing table data collected from several vantage points in the Internet including: looking glasses at 10 major Internet service providers (ISPs), RouteViews servers from 20 ISPs, and more than 50 PlanetLab nodes globally distributed across the Internet. Using this data, we quantify the extent of path diversity in multihoming and overlay networks, highlighting the limitations, and also identifying the source of the limitations in these architectures. From the analysis, we learn that both multihoming route control and current overlay networks are not able to ensure path diversity, which makes it very difficult to provide high-availability services even with the use of these systems. We believe that this work provides the insight into building future systems based on understanding path diversity

Recently, overlay networks have emerged as a means to enhance end-to-end application performance and availability. Overlay networks attempt to leverage the inherent redundancy of the Internet's underlying routing infrastructure to detour packets along an alternate path when the given primary path becomes unavailable or suffers from congestion. However, the effectiveness of these overlay networks depends on the natural diversity of overlay paths between two endhosts in terms of physical links, routing infrastructure, administrative control, and geographical distribution. Several recent studies realized that a measurable number of path outages were unavoidable even with use of such overlay networks. This stems from the fact that overlay paths might overlap with each other when overlay nodes are selected without considering the underlying topology. An overlay network's ability to quickly recover from path outages and congestion is limited unless we ensure path independence at the IP layer. This paper proposes a novel framework for topology-aware overlay networks. In this framework, we expressly design overlay networks, aiming to maximize path independence without degrading performance. We develop measurement-based heuristics for 1) placement of overlay nodes inside an ISP and 2) selection of a set of ISPs. We base our analysis on extensive data collection from 232 points in 10 ISPs, and 100 PlanetLab nodes. On top of node placement, we present measurement-based verification to conclude that single-hop overlay routing performs as well as multi-hop routing with respect to both availability and performance. Our analysis results show that a single-hop overlay path provides the same degree of path diversity as the multi-hop overlay path for more than 90% of source and destination pairs. Finally, we validate the proposed framework using real Internet outages to show that our architecture is able to provide a significant amount of resilience to real-world failures.

Multi-homed and overlay networks are two widely studied approaches aimed at leveraging the inherent redundancy of the Internet's underlying routing infrastructure to enhance end-to-end application performance and availability. However, the effectiveness of these approaches depends on the natural diversity of redundant paths between two endhosts in terms of physical links, routing infrastructure, administrative control and geographical distribution. This paper quantitatively analyzes the impact of path diversity on multihomed and overlay networks and highlights several inherent limitations of these architectures in exploiting the full potential redundancy of the Internet. We based our analysis on traceroutes and routing table data collected from several vantage points in the Internet including: looking glasses at ten major Internet service providers (ISPs), RouteViews servers from twenty ISPs, and more than fifty PlanetLab nodes globally distributed across the Internet. Our study motivates research directions - constructing topology-aware multihoming and overlay networks for better availability.

This paper proposes the concept of a fault-tolerant virtual private network (FVPN) within an autonomous system-a framework for supporting seamless network fail-over by leveraging the inherent redundancy of the underlying Internet infrastructure. The proposed architecture includes an application-level module, which is integrated into gateways at VPN end-points. This module enables fail-over to a redundant path without waiting for the underlying routing protocol converging to a new route. The paper introduces two algorithms for establishing redundant backup paths while minimizing overlapping network links. The proposed schemes are evaluated using topology information and sample routing logs from a regional Internet service provider network.

In this paper, we deal with a network design problem arising from the deployment of synchronous optical networks (SONET), a standard of transmission using optical fiber technology. The problem is to find an optimal clustering of traffic demands in the network such that the total number of node assignments (and, hence, add—drop multiplexer equipment requirements) is minimized, while satisfying the ring capacity and node cardinality constraints. This problem can be conceptualized as an edge-capacitated graph partitioning problem with node cardinality constraints. We formulate the problem as a mixed-integer programming model and develop a new branch-and-cut algorithm along with preprocessing routines for optimally solving the problem. We also prescribe an effective heuristic procedure. Promising computational results are obtained using the proposed method. © 2000 John Wiley & Sons, Inc.