Large-scale disasters affecting both network and datacenter (DC) infrastructures can cause severe disruptions in cloud-based services. During post-disaster recovery, repairs are usually carried out in stages in a progressive manner due to limited repair resource availability. The order in which network elements and DCs are repaired can significantly impact users' reachability to important contents/services. We investigate joint progressive network and DC recovery in which network recovery and DC recovery are conducted in a coordinated manner such that users have access to the maximum possible amount of contents/services at each repair stage. We first solve the optimization problem of joint progressive recovery to find the optimal sequence of network element and DC repairs with the objective to maximize cumulative weighted content reachability in the network. We then propose a scalable heuristic for scheduling the sequential repair of network nodes/links and DCs. Our model assumes that, at each repair stage, one network node with adjacent links and one DC can be fully repaired; however, full recovery may not be guaranteed due to limited resource availability. Hence, we also propose a “resource-aware” approach (with two resource-allocation strategies, namely “selective allocation” and “adaptive allocation”), which considers both full and partial recovery of elements based on available resources at each stage. We show that, compared to disjoint progressive recovery approach, in which network recovery and DC recovery plans are independent, our joint progressive recovery approach provides significantly higher per-stage content reachability in the network.

Physical resources are highly virtualized in todays datacenter-based cloud-computing networks. Servers, for example, are virtualized as Virtual Machines (VMs). Through abstraction of physical resources, server virtualization enables migration of VMs over the interconnecting network. VM migration can be used for load balancing, energy conservation, disaster protection, etc. Migration of a VM involves iterative memory copy and network re-configuration. Memory states are transferred in multiple phases to keep the VM alive during the migration process, with a small downtime for switchover. Significant network resources are consumed during this process. Migration also results in undesirable performance impacts. Suboptimal network bandwidth assignment, inaccurate pre-copy iterations, and high end-to-end network delay in wide-area networks (WAN) can exacerbate the performance degradation. In this study, we devise strategies to find suitable bandwidth and pre-copy iteration count to optimize different performance metrics of VM migration over a WAN. First, we formulate models to measure network resource consumption, migration duration, and migration downtime. Then, we propose a strategy to determine appropriate migration bandwidth and number of pre-copy iterations, and perform numerical experiments in multiple cloud environments with large number of migration requests. Results show that our approach consumes less network resources when compared with maximum and minimum-bandwidth provisioning strategies while using an order of magnitude less bandwidth than maximum-bandwidth strategy. It also achieves significantly lower migration duration than minimum-bandwidth scheme.

Traditionally, networks operate at a small fraction of their capacities; however, recent technologies, such as software-defined networking, may let operators run their networks harder (i.e., at higher utilization levels). Higher utilization can increase the network operator's revenue, but this gain comes at a cost: daily traffic fluctuations and failures might occasionally overload the network. We call such situations Resource Crunch. Dealing with Resource Crunch requires certain types of flexibility in the system. We focus on scenarios with flexible bandwidth requirements, e.g., some connections can tolerate reducing their bandwidth allocation. This may free capacity to provision new requests that would otherwise be blocked. For that, the network operator needs to make an informed decision, since reducing the bandwidth of a high-paying connection to allocate a low-value connection is not sensible. We propose a strategy to decide whether or not to provision a request (and which other connections to degrade) focusing on maximizing profits during Resource Crunch. To address this problem, we use an abstraction of the network state, called a connection adjacency graph (CAG). We propose an algorithm, called PROVISIONER, which integrates our CAG solution with an efficient linear program (LP). We compare our method to existing greedy approaches and to LP-only solutions, and show that our method outperforms them during Resource Crunch.

Decoupling control and data planes in a software-defined network (SDN) has its advantages along with its challenges. Especially, resilient communication between elements in the data plane (switches) and in the control plane (controllers) is key to SDN's success as disruption of this communication after a failure can severely affect data-plane functions. After a failure, simultaneous recovery of all switch-controller communication paths (control paths) may not be possible, and multiple recovery stages may be required. Since restoration of disrupted data paths depends on the recovery of disrupted control paths feeding control information to switches, the performance of control-path recovery seriously affects data-path recovery performance. The assignment of controller to switches and the routing of controller-switch control paths are what determines the control-plane recovery performance, and hence should be performed in conjunction with a recovery plan after failures. This study proposes an algorithm for recovery-aware switch-controller assignment and routing (RASCAR), which enables fast data-path recovery after a set of failures (e.g., single point of failures and disasters). We formulate the problem as an integer linear program and propose an efficient heuristic algorithm to solve large problem instances. Our illustrative numerical studies show that RASCAR significantly reduces the data-path restoration times after any failure with a minor increase in resource consumption of control paths.

With the rapid growth of content-based network services, there is increasing interest in reducing the emissions associated with brown-energy consumption in Content Delivery Networks (CDNs). At the same time, content needs to be placed in safe Data Center (DC) locations, which are unlikely to be hit by disasters. Further risk reduction is achieved using content replication which provides inter-DC content redundancy. Unfortunately, there is contention between the objectives of brown-energy minimization and risk reduction since replicating content increases brown-energy consumption. To address these contradictory issues, we leverage the concept of content fragmentation used inside DCs and propose an inter-DC Content Fragmentation (CF) scheme which aims to achieve brown-energy saving by reducing storage overhead while maintaining low risk compared to basic replication schemes. We also propose a Green and Low-Risk Content Placement approach (GR-CP) to address the tradeoff between brown-energy consumption and disaster risk. Both CF and replication schemes are implemented in GR-CP and evaluated over a range of content popularity and redundancy levels. Our results show that CF outperforms replication scheme except when content popularity is high and the risk constraint is stringent. When popularity and risk are both low, CF can save more brown energy by using low-redundancy fragmentation techniques.

Traffic in optical backbone networks is increasing and becoming more heterogeneous with respect to bandwidth and QoS requirements due to the popularity of high-bandwidth services (such as cloud computing, e-science, telemedicine, etc.), which need to coexist with traditional services (HTTP, etc.). Mixed-line-rate (MLR) networks that support lightpaths of different rates such as 10, 40, 100 Gb/s, etc., are being studied to better support the heterogeneous traffic demands. Here, we study the important topic of degraded services in MLR networks, where a service can accept some degradation (i.e., reduction) in bandwidth in case of a failure in exchange for a lower cost, a concept called partial protection. Network operators may wish to support degraded services to optimize network resources and reduce cost. We propose using multipath routing to support degraded services in MLR networks, a problem that has not been studied before and is significantly more challenging than in single-line-rate (SLR) networks. We consider minimum-cost MLR network design (i.e., choosing which transponder rates to use at each node), considering the opportunity to exploit multipath routes to support degraded services. We propose a mixed-integer-linear-program (MILP) solution and a computationally efficient heuristic, and consider two partial-protection models. Our illustrative numerical results show that significant cost savings can be achieved due to partial protection versus full protection and is highly beneficial for network operators. We also note that multipath routing in MLR networks exploits volume discount of higher-line-rate transponders by cost-effectively grooming requests over appropriate line rates to maximize transponder reuse versus SLR.

Spectrum elastic optical networks support flexible central frequency and spectrum assignment for lightpaths. When provisioning a new connection in an elastic optical network that allows traffic grooming, the control plane has to solve two problems: the electrical-layer routing and optical-layer routing and spectrum assignment (RSA). The electrical-layer routing determines how to route the new connection through a combination of new and existing lightpaths, while the optical-layer RSA decides how to establish new lightpaths under the spectrum-continuity constraint. The flexibility (e.g., bandwidth variability of lightpaths) provided by elastic optical networks makes it suitable for accommodating dynamic traffic. It is important and challenging to exploit the full potential of the flexibility when dealing with the above two problems. In this study, we propose a multi-layer auxiliary graph to jointly solve the electrical-layer routing and optical-layer RSA. Various traffic-grooming policies (objectives) can be achieved by properly adjusting the edge weights in the auxiliary graph. Also, we propose a spectrum reservation scheme that can efficiently utilize the bandwidth variability of lightpaths by reserving bandwidth for non-fully utilized lightpaths and grooming future connections onto them. We show that there is a tradeoff among different traffic-grooming policies, and the spectrum reservation scheme can be easily incorporated into various traffic-grooming policies and lead to a significant reduction in operational expenditure (OPEX) and better spectrum efficiency.

As new Internet applications are emerging, traffic in optical backbone networks is increasing with heterogeneity in bandwidth and QoS requirements. Higher bit-rate wavelength channels of 40 Gbps, 100 Gbps, and beyond are being deployed in WDM backbone networks to meet these growing traffic needs. Mixed-line-rate (MLR) networks that support various line rates on the same fiber are becoming popular to address the heterogeneous traffic growth. We study the important problem of long-term cost-effective dimensioning of WDM backbone networks with MLR. Our study should enable operators to dimension their networks with deployment of MLR transponders and optical cross-connect (OXC) ports over multiple time periods. We study two multi-period dimensioning approaches: all-periods planning and incremental planning. Our approaches predict the network equipment to be deployed at various nodes in the network during each time period while exploiting the cost reduction of network equipment over time to support traffic growth over multiple time periods. We propose mixed-inter-linear-program (MILP) solutions and a computationally-efficient heuristic. Our illustrative examples show that significant cost savings can be achieved by our long-term planning approaches.

Many telecom, customers have applications with time varying reliability requirements. However, current for a service-level agreement (SLA) frameworks provide the same reliability during the entire holding time, rather than providing high reliability only when required. Recent papers describe the need for time-differentiated resilience and establish an SLA framework to support this using Critical Windows (CW). CWs are scheduled, regularly repeating time periods where additional resilience is required. We expand the previous work to a more general and dynamic network setting and further investigate the structural properties of critical windows. We propose and evaluate first an algorithm for CW-aware path assignment in mesh telecom networks, and then a CW-aware algorithm that also employs Shared-Path Protection (SPP). Our study shows: 1) that CWs provide a substantial performance improvement in mesh networks; 2) CW performance gain is insensitive to several network parameters; and 3) CWs can be implemented on top of generic SPP to provide even better performance.

Survivability is a critical concern in modern telecom mesh networks because the failure of a network element may cause tremendous data and revenue loss in such networks using high-capacity optical fibers employing wavelength-division multiplexing (WDM). Multipath provisioning is a key feature of next-generation SONET/SDH networks (which can be used on top of optical WDM), and they can support virtual concatenation (VCAT); thus, multipath provisioning can significantly outperform single-path provisioning in resource efficiency, service resilience, and flexibility. However, in multipath provisioning, differential delay is an important constraint that should be considered. We investigate survivability of service paths based on differential-delay constraint (DDC) and multipath provisioning together in telecom backbone mesh networks. We propose the Shared Protection of the Largest Individual Traversed link (SPLIT) method for survivable multipath provisioning and present a DDC-based algorithm for multipath routing subject to DDC. We also compare the DDC-based algorithm with theKshortest link-disjoint paths (KDP) algorithm, using SPLIT, under dynamic service requests. We find that exploiting link-disjoint paths is very efficient for survivable multipath provisioning, and our algorithm is resource-efficient, has low signaling overhead, and has fast fault recovery for survivable multipath provisioning with DDC. For a 5-ms DDC, our algorithm can decrease the bandwidth blocking ratio (BBR) significantly in typical U.S. backbone networks.

A service-level agreement (SLA) typically specifies, among other metrics, the availability a service provider (SP) promises to a customer. In an optical wavelength division multiplexing (WDM) network, connection-oriented provisioning is commonly based on whether the path's statistical availability complies with the SLA-requested availability. Because of the stochastic nature of network failures, the actually provisioned availability over a specific time period is subject to uncertainty, and hence the SLA is usually at risk. We consider this uncertainty and study provisioning to minimize SLA violations. We show that the SLA Violation Risk is affected by a number of factors (e.g., failure profiles, availability target, and penalty period), and hence cannot simply be characterized by statistical path availability. We formulate the problem of risk-aware provisioning in WDM mesh networks, where path selection is dictated by SLA Violation Risk. In particular, we focus on devising an efficient scheme capable of computing path(s) that are likely to successfully accommodate the SLA-requested availability. A novel technique is applied to convert links with heterogeneous failure profiles to reference links that capture the main risk features in a relative manner. Based on the “reference link” concept, our Risk-Aware Provisioning scheme uses only limited failure information. We also extend our Risk-Aware Provisioning to use shared-path protection (SPP) for connections with strict availability requirements. We evaluate the performance and demonstrate the effectiveness of our schemes in terms of SLA violation ratio compared to the generic availability-aware approaches.

Internet customers may have strict resilience requirements for specific times periods. However, these time-differentiated resilience requirements are not effectively addressed by current SLA frameworks. To satisfy the resilience-sensitive periods, a generic SLA framework typically provides upgraded protection over the entire service duration, which is unnecessary and expensive. In this study, we propose a novel SLA framework, which allows customers to specify Critical Windows (CW) to address time-differentiated resilience demands. CWs correspond to the periods that require extra protection, and are backed up using path-level pre-cross-connected protection. Considering the complementary profiles of CWs, we identify the opportunity for backup resource sharing in the time domain. To exploit backup sharing, a heuristic scheme is proposed (Globally-CW-Aware connection assignment) to reduce backup resources. Our study shows that, using the proposed SLA framework: 1) low operational complexity can be achieved; 2) backup resources can be significantly reduced; and 3) high resilience (Service Level) can be achieved for CWs.

Since telecom networks consume a large (and increasing) amount of energy, "green" strategies are desirable to help Service Providers (SP) operate their networks and provision services more energy-efficiently. In this study, we focus on operating optical backbone networks with green strategies. We consider a typical optical backbone network architecture, and minimize the Operational Power for service provisioning following a Traffic Engineering (TE) approach. Service provisioning is schematically decomposed as multiple serial operations, and power efficiency is analyzed for both optical bypass and traffic grooming. We propose a novel auxiliary graph, which can capture the flow of operations and their associated power. Based on the auxiliary graph, we present a Power-Aware scheme that minimizes the Operational Power. Simulation results show reduced power consumption by our scheme, in comparison to a generic traffic grooming approach.

A Service Level Agreement (SLA) typically specifies the availability a Service Provider (SP) promises to a customer. In an Optical Transport Network, finding a lightpath for a connection is commonly based on whether the availability of a lightpath availability complies with the connection's SLA-requested availability. Because of the stochastic nature of network failures, the actual availability of a lightpath over a specific time period is subject to uncertainty, and the SLA is usually at risk. We consider the network uncertainty, and study routing to minimize the probability of SLA violation. First, we use a single-link model to study SLA Violation Risk (i.e., the probability of SLA violation) under different settings. We show that SLA Violation Risk may vary by paths and is affected by other factors (e.g., failure rate, connection holding time, etc.), and hence cannot be simply described by path availability. We then formulate the problem of risk-aware routing in mesh networks, in which routing decisions are dictated by SLA Violation Risk. In particular, we focus on devising a scheme capable of computing lightpath(s) that are likely to successfully accommodate a connection's SLA-requested availability. A novel technique is applied to convert links with heterogeneous failure profiles to reference links which capture the main risk features in a relative manner. Based on the "reference link" concept, we present a polynomial Risk-Aware Routing scheme using only limited failure information. In addition, we extend our Risk-Aware Routing scheme to incorporate shared path protection (SPP) when protection is needed. We evaluate the performance and demonstrate the effectiveness of our schemes in terms of SLA violation ratio and, more generally, contrast them with the generic availability-aware approaches.

Many networking applications require distribution of data from a central point to multiple destinations; this distribution can be efficiently achieved by the means of multicasting. Traditionally, multicasting has been considered for on-demand applications such as HDTV, Video-on-Demand (VoD), IPTV, which usually require to start data transmission immediately. However, in the case of emerging e-Science and high-performance applications (which frequently need to replicate large datasets to multiple locations), the data distribution does not necessarily need to take place instantaneously; instead, the multicast session can be accommodated considering a flexible start time for the large data transfer. We study the efficient provisioning of Multicast Data-Distribution Requests (MDDRs) with flexible scheduling over WDM networks. We consider the practical case of multicast sessions that may require less than the entire capacity of a wavelength; hence the multicast sessions need to be "traffic-groomed". Our first multicast provisioning approach (named Rand) generates randomized alternate multicast trees on which we try to provision the multicast session, and then attempts to assign wavelengths and schedule the session's start time. In our second approach (named AllSlots), for each available start time S, we dynamically generate trees depending on the network state at time S. In our next approach (named Break), for the cases when provisioning an entire multicast tree fails, we enable the possibility of "breaking" the tree into subtrees (with independent start times) serving subsets of destinations. Moreover, we study the impact of partitioning the datasets into pieces on our multicast provisioning approaches, and also compare our multicast algorithms with an unicast approach.

We study the problem of reliably provisioning traffic using multipath routing in a mesh network. Traditional approaches handled reliability requirements using full-protection schemes. Although full-protection approaches offer high assurance, this assurance can be costly. We take a less expensive approach to maintain reliability by offering partial-protection. Specifically, our approach guarantees part of the requested bandwidth, rather than the full amount, in the event of a link failure. We first show that the amount of partial-protection that can be guaranteed is limited by the topology of the network and the bandwidth requirement of a connection request. We then propose an effective multipath algorithm that attempts to provision bandwidth requests while guaranteeing the maximum partial-protection possible. Results show that by effectively selecting paths that limit edge overuse, our algorithm achieves very low bandwidth blocking probability. Our algorithm also serves significantly more requested bandwidth than the protection approach.

A service level agreement (SLA) typically specifies the availability a service provider (SP) promises to a customer. Current schemes usually employ backup resources to achieve high SLA satisfaction. We propose a new provisioning framework, called service cluster (SC), which uses no explicit backup resources. By grouping several services with (typically) different availability specifications, an SC can dynamically re-allocate resources to avoid SLA violations. Services that can tolerate additional down time lend resources to services that need to be kept running. We first analyze a condition for admission control. We then propose a dynamic resource allocation scheme (ADT1balancing scheme, SC-ABS) and apply it to the SC framework. The dynamic management of SC-ABS is realized by novel SLA-violation estimation in an event-driven manner without continuous monitoring. We compare SC-ABS with shared-path protection, and numerically show its various advantages in terms of: 1) higher SLA satisfaction (up to 30% more); 2) lower service blocking ratio; 3) higher tolerance of failures; 4) more balanced SLA satisfaction; and 5) consuming no explicit backup (or standby) resources. Our scheme can meet the SLA of significantly more services than protection-based schemes, thus providing more profit for the SP and lower cost for the customer.

Many large-scale scientific applications need to aggregate large amounts of data from multiple distributed sites to a centralized facility. We call such a request as a data-aggregation request (DAR). In this study, we investigate the novel problem of on-demand DAR provisioning over a wavelength-division multiplexing (WDM) backbone network. We provide a mathematical formulation for our problem as a mixed integer linear program (MILP). To solve large versions of our problem, we propose a DAR provisioning heuristic (called DARP). We use the MILP with various objectives as a benchmark for studying the performance of DARP.

Service level agreement (SLA) is a contract between the service provider (SP) and the customer. Among various parameters, SLA imposes penalties on the SP when the customer's quality-of-service (QoS) requirements are violated. Hence, it is desirable to avoid SLA violations and such penalties. SLA also states the maximum amount of downtime a connection may tolerate during its lifetime. In this study, we present a dynamic provisioning scheme called Preemption-Oriented SLA-Aware Provisioning (POSAP) for telecom mesh networks, which considers a connection's (1) availability requirements, (2) penalty, and (3) state. In addition to the connection's various parameters (availability, penalty, etc.), the amount of affordable downtime is used as a metric to determine the risk of violating the connection's SLA, and hence, its priority. Connection's priority is denoted by urgency level. Our scheme allows resource preemption among connections, i.e., high-priority connections may preempt backup resources from low-priority connections. Also, new connection requests may preempt resources from existing connections. Urgency level determines how resources can be preempted. Our scheme is applied to a US-wide network. Our results show the improved performance in terms of (1) reduced SLA violations, (2) increased network utilization, and (3) increased network revenue, compared to a dedicated primary-backup (P-B) scheme.

We investigate dynamic bandwidth allocation with flexible transmission rates for deadline-driven requests (DDRs) in wavelength-division multiplexing (WDM) mesh networks. DDRs provide more scheduling flexibility to the network operator compared with typical requests with no deadline and requiring a fixed bandwidth. By choosing the bandwidth and adapting the transmission rate depending on network state, the network's performance can be improved. We investigate several bandwidth allocation policies and study their benefits on network performance. Our investigation shows that an adaptive policy generally performs the best. Further improvement can be achieved by using dynamic readjustment of the allocated bandwidth.

Multipath provisioning is a key feature of next-generation SONET/SDH networks (which can be used on top of optical WDM) and they can support virtual concatenation (VCAT); thus, multipath provisioning can significantly outperform single-path provisioning in resource efficiency, service resilience, and flexibility. However, in multipath provisioning, differential delay is an important constraint which should not be ignored. We investigate survivability of service paths based on differential-delay constraint (DDC) and multipath provisioning together in a telecom backbone mesh network. We present a DDC-based K link-disjoint paths algorithm (DDCKDP) for multipath provisioning subject to DDC. We also compare it with the minimum-cost-flow (MCF) and K shortest link-disjoint paths (KDP) algorithm, using Shared Protection of the Largest Individual Traversed link (SPLIT), under dynamic service request with several different DDCs. We find that (1) exploiting link-disjoint paths is very efficient for survivable multipath provisioning; and (2) SPLIT-DDCKDP is resource efficient, has low signaling overhead, and has fast fault-recovery for survivable multipath provisioning with DDC. For a 5 ms DDC, DDCKDP can decrease the Bandwidth Blocking Ratio (BBR) by more than 100% compared with KDP in a typical US backbone network.

We study the problem of reliably provisioning traffic in high-capacity backbone mesh networks supporting virtual concatenation (VCAT). VCAT enables a connection to be inversely multiplexed on to multiple paths, a feature that has many advantages over conventional single-path provisioning. We propose improved routing algorithms which use minimum- cost flow to find efficient collections of paths that satisfy the traffic requests. We first investigate the performance of our scheme under a uniform setting with symmetric traffic distribution and equal link capacities. We then apply our algorithm in a more realistic setting with asymmetric traffic and differing link capacities. Our algorithm is effective in both the uniform and non-uniform settings, and is much more effective than previously proposed schemes. Our study in the non-uniform setting is significant as it gives insight into the performance of our algorithm under more realistic scenarios.

Many researchers have considered security policy management, including how to configure policies manually and even how to automatically generate security policies based on security requirements. Both can be error prone, especially when properties of the network topology change, because security requirements are usually not bound to any particular route path. Our DETER lab emulation results show that conflicts could be caused by these factors. Therefore, a systematic way to validate the correctness of the security policies is essential. This paper presents an approach, CLID (conflict and looping identification and detection), to verify whether a set of security policies (e.g. IPSec/VPN tunnels) satisfy the given security requirements, without causing any conflicts. This approach utilizes the definition of a security policy lo include network routing data as well as traffic selector information, thus it works for general network topologies. We also analyze and justify the correctness of the approach. The paper concludes with our simulation results and addresses future work.

Abstract In this paper we present new empirical results for splay trees. These results provide a better understanding of how cache performance affects query execution time. Our results show that splay trees can have faster lookup times compared with randomly built binary search trees (BST) under certain settings. In contrast, previous experiments have shown that because of the instruction overhead involved in splaying, splay trees are less efficient in answering queries than randomly built BSTs—even when the data sets are heavily skewed (a favorable setting for splay trees). We show that at large tree sizes the difference in cache performance between the two types of trees is significant. This difference means that splay trees are faster than BSTs for this setting—despite still having a higher instruction count. Based on these results we offer guidelines in terms of tree size, access pattern, and cache size as to when splay trees will likely be more efficient. We also present a new splaying heuristic aimed at reducing instruction count and show that it can improve on standard splaying by 10–27%. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract — We design network topologies and routing strategies which optimize several measures simultaneously: low cost, small routing diameter, bounded degree and low congestion. This set of design issues is broader than traditional network design and hence, our work is useful and relevant to a set of traditional and emerging design problems. Surprisingly, a simple idea from the research on small-world models, inspires a fruitful approach and useful techniques here. Starting with a simple model we consider adding long links to an n×n grid graph. Ideally, for a given budget to buy additional long links, we consider mechanisms for choosing links such that the routing diameter is small enough (poly-log of n) while the congestion ratio (between the most used link and the average one) is minimized, assuming uniform traffic between any two of the n 2 nodes. We show that by adding O(1) long links to each node we achieve an almost logarithmic routing diameter and maintain a near optimal trade-off between congestion ratio and average weight (of long links): Weight×CongestionRatio = O(n). Our results are comparable to the best similar network structures when the trade-off space we consider is reduced to those in the compared designs (with fewer trade-off factors). We also consider extensions of our results to more general settings. We propose two construction schemes: 1) a static (fixed link) design and 2) a dynamic (random link) design. While the former provides our best trade-off results, the later is more scalable, better suited for dynamic and fault-tolerance issues, and can be useful for wireless ad-hoc networks. I.

Most of the current work in policy management for IPSec/VPN focuses on how to configure a single IPSec box or a pair of IPSec boxes. However, it has been shown (Fu et al. (2001)) that the local correctness of IPSec policies in every box individually does not necessarily guarantee global correctness. Therefore, it is critical to have a systematic way to analyze the security requirements globally and to generate, automatically and correctly, a set of IPSec policies to ensure the security for all the end-to-end connections. Previously (Fu et al. (2001)), two different algorithms (i.e. bundle and direct) were introduced to solve the policy generation problem in an "offline" fashion. While these two algorithms are efficient in producing globally correct policy rules, the number of output policy rules (i.e., the results themselves) is much greater than necessary. In other words, while the existing approaches can produce a solution quickly, the quality of the solution is far from optimal. In practice, this is undesirable for several reasons. For instance, "more IPSec policy rules" implies "more complicated virtual network topology". Therefore, in this paper, we focus on "how to produce a minimum set of IPSec/VPN tunnels". We formulate this problem as a special type of task-scheduling problem and develop a new method, the ordered-split approach, to produce a provably minimum set of globally correct policy rules. We have also compared the new approach with existing methods in simulation, and our results clearly demonstrate that the ordered-split approach performs significantly better.

We analyze the properties of Small-World networks, where links are much more likely to connect "neighbor nodes" than distant nodes. In particular, our analysis provides new results for Kleinberg's Small-World model and its extensions. Kleinberg adds a number of directed long-range random links to an nxn lattice network (vertices as nodes of a grid, undirected edges between any two adjacent nodes). Links have a non-uniform distribution that favors arcs to close nodes over more distant ones. He shows that the following phenomenon occurs: between any two nodes a path with expected length O(log2n) can be found using a simple greedy algorithm which has no global knowledge of long-range links.We show that Kleinberg's analysis is tight: his algorithm achieves θ(log2n) delivery time. Moreover, we show that the expected diameter of the graph is θlog n), a log n factor smaller. We also extend our results to the general k-dimensional model. Our diameter results extend traditional work on the diameter of random graphs which largely focuses on uniformly distributed arcs. Using a little additional knowledge of the graph, we show that we can find shorter paths: with expected length O(log3/2n) in the basic 2-dimensional model and O(log1+1/k) in the general k-dimensional model (fork≥1).Finally, we suggest a general approach to analyzing a broader class of random graphs with non-uniform edge probabilities. Thus we show expected θ(log n) diameter results for higher dimensional grids, as well as settings with less uniform base structures: where links can be missing, where the probability can vary at different nodes, or where grid-related factors (e.g. the use of lattice distance) has a weaker role or is dismissed, and constraints (such as the uniformness of degree distribution) are relaxed.

No abstract available.

Integrity critical databases, such as financial information used in high-value decisions, are frequently published over the Internet. Publishers of such data must satisfy the integrity, authenticity, and non-repudiation requirements of clients. Providing this protection over public data networks is an expensive proposition. This is, in part, due to the difficulty of building and running secure systems. In practice, large systems can not be verified to be secure and are frequently penetrated. The negative consequences of a system intrusion at the publisher can be severe. The problem is further complicated by data and server replication to satisfy availability and scalability requirements. To our knowledge this work is the first of its kind to give general approaches for reducing the trust required of publishers of large databases. To do this, we separate the roles of data owner and data publisher. With a few digital signatures on the part of the owner and no trust required of a publisher, we give techniques based on Merkle hash trees that publishers can use to provide authenticity and non-repudiation of the answer to database queries posed by a client. This is done without requiring a key to be held in an on-line system, thus reducing the impact of system penetrations. By reducing the trust required of the publisher, our solution is a step towards the publication of large databases in a scalable manner.

XML is increasingly becoming the format of choice for information exchange, in critical areas such as government, finance, healthcare and law, where integrity is of the essence. As this trend grows, one can expect that documents (or collections thereof) may get quite large, and clients may wish to query for specific segments of these documents. In critical applications, clients must be assured that they are getting complete and correct answers to their queries. Existing methods for signing XML documents cannot be used to establish that an answer to a query is complete. A simple approach has a server processing queries and certifying answers by digitally signing them with an on-line private key; however, the server, and its on-line private key, would be vulnerable to external hacking and insider attacks. We propose a new approach to signing XML documents which allows untrusted servers to answer certain types of path queries and selection queries over XML documents without the need for trusted on-line signing keys. This approach enhances both the security and scalability of publishing information in XML format over the internet. In addition, it provides greater flexibility in authenticating parts of XML documents, in response to commercial or security policy considerations.

We present new design and analysis techniques for the synthesis of parallel multiplier circuits that have smaller predicted delay than the best current multipliers. V.G. Oklobdzija et al. (1996) suggested a new approach, the Three-Dimensional Method (TDM), for Partial Product Reduction Tree (PPRT) design that produces multipliers that outperform the current best designs. The goal of TDM is to produce a minimum delay PPRT using full adders. This is done by carefully modeling the relationship of the output delays to the input delays in an adder and, then, interconnecting the adders in a globally optimal way. Oklobdzija et al. suggested a good heuristic for finding the optimal PPRT, but no proofs about the performance of this heuristic were given. We provide a formal characterization of optimal PPRT circuits and prove a number of properties about them. For the problem of summing a set of input bits within the minimum delay, we present an algorithm that produces a minimum delay circuit in time linear in the size of the inputs. Our techniques allow us to prove tight lower bounds on multiplier circuit delays. These results are combined to create a program that finds optimal TDM multiplier designs. Using this program, we can show that, while the heuristic used by Oklobdzija et al. does not always find the optimal TDM circuit, it performs very well in terms of overall PPRT circuit delay. However, our search algorithms find better PPRT circuits for reducing the delay of the entire multiplier.

Let G=(V,E) be an undirected, unweighted graph with n nodes, m edges and edge connectivity $\lambda$. Given an input parameter $\delta$, the edge augmentation problem is to find the smallest set of edges to add to G so that its edge connectivity is increased by $\delta$. In this paper, we present a solution to this problem which runs in $O(\delta ^2 nm + \delta^3 n^2 + n F(G))$, where F(G) is the time to perform one maximum flow on G. In fact, our solution gives the optimal augmentation for every $\delta '$, $1 \le \delta ' \le \delta$, in the same time bound. By introducing minor modifications to the solution, we can solve the problem without knowing $\delta$ in advance, and we can also solve the node-weighted version and the degree-constrained version of the problem. If $\delta =1$, then our solution is particularly simple; it runs in O(nm) time, and it is a natural generalization of the algorithm in [K. Eswaran and R. E. Tarjan, SIAM J. Comput., 5 (1976), pp. 653--665] for the case where $\lambda+\delta =2$. We also solve the converse problem in the same time bound: given an input number k, increase the connectivity of G as much as possible by adding at most k edges. Our solution makes extensive use of the structure of particular sets of cuts.

This paper studies the classical dictionary problem using a self-adjusting linear list. We designed and analyzed randomized, on-line algorithms for a sequence of successful and unsuccessful searches which are competitive with off-line algorithms. Our algorithms combined the ps bit technique which speeds up unsuccessful search with the randomized move-to-front scheme of Reingold et al., which they used to speed up successful search.

In a multiple access broadcast network, all network nodes share a single shared communication channel, and there is the possibility of a collision when two or more nodes transmit at overlapping times. We propose a dynamic prioritized conflict resolution algorithm in which, when a collision occurs, all colliding messages are retransmitted according to their priority. When a new message arrives, it is allowed to participate in the algorithm as soon as it finds its priority is higher than that of some broadcast message. Using a time-slotted model, for any arrival pattern and priority distribution, we show that our algorithm runs in expected linear time, i.e., O(r), where r is the total number of message transmitted. We also show that the expected waiting time for any message x is O(rank(x)+log s), where rank(x) is the expected number of messages with higher priority which transmit while x is waiting, and s is the minimum of the total number of messages participating in the algorithm and the total number of nodes in the network. The analysis presented in this work also includes an improved analysis of our original (static) prioritized conflict resolution algorithm. This work is applicable to multimedia communications where different priority values could be assigned to different kinds of traffic, and our algorithm ensures that the high-priority real-time traffic has the minimum delay.

We present new design and analysis techniques for the synthesis of fast parallel multiplier circuits. V.G. Oklobdzija, D. Villeger, and S.S. Lui (1995) suggested a new approach, the three dimensional method (TDM), for partial product reduction tree (PPRT) design that produces multipliers which outperform the current best designs. The goal of TDM is to produce a minimum delay PPRT using full adders. This is done by carefully modelling the relationship of the output delays to the input delays an an adder, and then interconnecting the adders in a globally optimal way. Oklobdzija, et. al. suggested a good heuristic for finding the optimal PPRT, but no proofs about the performance of this heuristic were given. We provide a formal characterization of optimal PPRT circuits and prove a number of properties about them. For the problem of summing a set of input bits within the minimum delay, we present an algorithm that produces a minimum delay circuit in time linear in the size of the inputs. Our techniques allow us to prove tight lower bounds on multiplier circuit delays. These results are combined to create a program which finds optimal TDM multiplier designs.>

No abstract available.

This paper develops shared memory algorithms for asynchronous processor systems that require the same expected work as the best PRAM algorithms. These algorithms operate efficiently under general asynchronous processor behavior (where individual processor speeds are allowed to vary widely over time). This paper achieves these results by employing a methodology that uses randomization to schedule subtasks of a parallel program. The resulting algorithms allow processors to (i) have arbitrary asynchronous behavior, (ii) have fail-stop errors, (iii) join a computation at any time, and (iv) have no unique identifiers. This paper develops a performance metric for asynchronous parallel computations, called work, which is the total number of instructions (including busy-waiting instructions) performed by a collection of parallel processors during a computation. The main result is to compute any associative function of n variables with $O(n)$ expected work, using up to $n/\log n\log^* n$ asynchronous processors, and with $O(n\log n)$ expected work using up to n processors. These results provide a synchronization primitive that can be used to transform any PRAM program into an asynchronous PRAM program.

A fundamental problem in the theory of real-time scheduling is examined: scheduling a set of periodic or sporadic tasks on a uniprocessor without preemption and without inserted idle time. The authors give a necessary and sufficient set of conditions C for a set of periodic or sporadic tasks to be schedulable for arbitrary release times of the tasks. They show that any set of periodic or sporadic tasks that satisfies C can be scheduled with an earliest-deadline-first (EDF) scheduling algorithm. The authors present the scheduling model, briefly review the literature in real-time scheduling, prove that the non-preemptive EDF algorithm is universal for sets of tasks, whether periodic or sporadic, and demonstrate the absence of a universal algorithm for periodic tasks with specified release times. It is proved that the problem of deciding schedulability of a set of concrete periodic tasks is intractable.>

A multiple access broadcast network (MABN) is a computer network in which there is a single shared communication channel and every network node can receive all messages transmitted over the channel. A major difficulty in using broadcast communication is the issue of access to the channel. The authors deal with the following prioritized conflict resolution problem: a collection of c messages is initially distributed among nodes on an MABN; each message is associated with a value representing its priority or deadline; and it is required that the messages be broadcast in ascending order of this value. This problem is solved by a distributed prioritized conflict resolution algorithm. It is proved that the expected waiting time of the ith network node to transmit is Theta (i+log c), which is optimal. It is also shown that the algorithm runs in the expected linear time, which is optimal in both the number of slots used and the total elapsed time including local processing.>

A PRAM (parallel random-access-machine) model that allows processors to have arbitrary asynchronous behavior is introduced. The main result shows that any n-processor CRCW (concurrent-read, concurrent-write) PRAM program can be simulated on an asynchronous CRCW PRAM using O(n) expected work per parallel step and up to n/log n log*n asynchronous processors. It is shown that a synchronization primitive for n parallel instructions can be computed using O(n) expected work by a system of asynchronous processors. Since a special case of asynchronous behavior is a fail-stop error, the simulation technique described above can convert any PRAM program into a PRAM program that is resistant to all fail-stop errors and has the same expected work as the original program.>

An undirected, unweighted graph G=(V, E with n nodes, m edges, and connectivity lambda ) is considered. Given an input parameter delta , the edge augmentation problem is to find the smallest set of edges to add to G so that its edge-connectivity is increased by delta . A solution to this problem that runs in time O( delta /sup 2/nm+nF(n)), where F(n) is the time to perform one maximum flow on G, is given. The solution gives the optimal augmentation for every delta ', 1>

Abstract We compare the performance of network flow algorithms based on Dinic's layered graph approach to the new Goldberg‐Tarjan (GT) algorithm. We show that for networks with small capacities, in particular for unit networks, the Dinic‐like algorithms are asymptotically faster than the GT algorithm. A second setting that we study is parameterized flow computations. Gallo, Grigoriadis, and Tarjan have shown that the GT algorithm solves this type of problem very efficiently. We show that traditional implementations of the Dinic‐like algorithms are much less efficient for solving parameterized flow problems. We also give a new implementation of a Dinic‐like algorithm that is competitive with the GT algorithm on parameterized flow networks.

We discuss network flow in a bipartite graph G with node sets S and T. We show that Karzanov’s algorithm runs in time $O(|S|^2 |T|)$ on G, and that the MPM algorithm can be modified to run in the same bound. For the common case that the degree of each node in T is bounded by a constant, we show that a modified version of the MPM algorithm runs in time $O(|S|^3 + |S||T|)$ on G. The importance of these results comes from the common occurrence of problems that can be modeled and solved using network flow on bipartite graphs where $|S| \ll |T|$. In many applications involving bounded degree on the nodes in T, $|T| = \theta (|S|^2 )$, and our results reduce the best bounds on bipartite flow from $O(|S|^6 )$ to $O(|S|^3 )$. We use our results on bipartite flow to obtain the fastest known bounds on several combinatorial problems, and mention several additional problems involving bipartite flow where $|S|$ is much smaller than $|T|$.

Given n jobs, each of which has a release time, a deadhne, and a processing reqmrement, the problem of determining whether there exists a preemptwe schedule on m uniform machines which completes each .lobm the t~me mterval between its release t~me and its deadlme Js examined An O(m2n 4 + n ~) algonthm is presented which uses a generahzauon of network flow techmques to construct such a schedule whenever one extsts This algorithm is then used wRh search techniques to find a schedule which mmtm~zes maxtmum lateness.Categortes and SubJect Descriptors D 4 1 [