Search

An increasing number of high-performance networks provision dedicated channels through circuit switching or MPLS/GMPLS techniques to support large data transfer. The link bandwidths in such networks are typically shared by multiple users through advance reservation, resulting in varying bandwidth availability in future time. Developing efficient scheduling algorithms for advance bandwidth reservation has become a critical task to improve the utilization of network resources and meet the transport requirements of application users. We consider an exhaustive combination of different path and bandwidth constraints and formulate four types of advance bandwidth scheduling problems, with the same objective to minimize the data transfer end time for a given transfer request with a prespecified data size: 1) fixed path with fixed bandwidth (FPFB); 2) fixed path with variable bandwidth (FPVB); 3) variable path with fixed bandwidth (VPFB); and 4) variable path with variable bandwidth (VPVB). For VPFB and VPVB, we further consider two subcases where the path switching delay is negligible or nonnegligible. We propose an optimal algorithm for each of these scheduling problems except for FPVB and VPVB with nonnegligible path switching delay, which are proven to be NP-complete and nonapproximable, and then tackled by heuristics. The performance superiority of these heuristics is verified by extensive experimental results in a large set of simulated networks in comparison to optimal and greedy strategies.

High-performance networks are capable of provisioning dedicated channels through circuit/lambda-switching or MPLS/GMPLS techniques to support large-scale data transfer. These dedicated links are typically shared by multiple users through advance resource reservations, resulting in varying bandwidth availability in future time periods. Most previous efforts were focused on centralized bandwidth scheduling to improve the utilization of network resources and meet the transport requirements of application users. These centralized scheduling schemes imply the use of a central control plane, posing significant reliability and scalability challenges as the network size rapidly grows. We propose distributed algorithms for path computation and bandwidth scheduling in response to four basic bandwidth reservation requests: (i) fixed bandwidth in a fixed slot, (ii) highest bandwidth in a fixed slot, (iii) first slot with fixed bandwidth and duration, and (iv) all slots with fixed bandwidth and duration. These algorithms are developed through a rigorous extension of the classical breadth first search and Bellman-Ford algorithms to a completely distributed manner, and their performances are evaluated and analyzed through extensive simulations.

The traditional client-server architecture widely adopted on the Internet is not adequate to meet the increasing user loads and bandwidth demands in live streaming systems especially for multimedia content delivery. Peer-to-peer P2P) overlay networks provide excellent system scalability and high resource utilization, which make it an attractive solution to this problem. This paper considers a hybrid hierarchical P2P overlay network structure that consists of both super and normal peers. The media streaming architecture is built upon a tree structured network of super peers and the tree construction process has a significant impact on the overall system performance. We construct network cost models and formulate a Bandwidth Constrained Tree (BCT) construction problem, which aims at maximizing the number of peers that satisfy a specified bandwidth constraint. We prove that BCT is NP-complete and propose optimal algorithms in two special cases and a heuristic approach in a general case. The performance superiority of the proposed method is illustrated by an extensive set of experiments on simulated networks of various sizes in comparison with existing greedy and degree constrained algorithms.

Sensor deployment is one fundamental task in sensor network implementation. We generalize and investigate the problem of deploying a minimum set of wireless sensors at candidate locations in constrained 3D space of interest to achieve k-coverage of given target areas such that each point in the target areas is covered by at least k sensors. Based on different constraints on sensor locations and target areas, we formulate four sensor deployment problems: Discrete / Continuous sensor Locations (D/CL) with Discrete / Continuous Target areas (D/CT). We propose an approximate algorithm for DLDT and reduce DLCT and CLDT to DLDT by discretizing continuous sensor locations or target areas into a number of divisions without loss of sensing precision. We further consider the connected version of these four sensor deployment problems where deployed sensors must form a connected network, and propose an approximate algorithm for each of these connected deployment problems.

The client-server architecture widely adopted on the Internet is not adequate to meet the ever-increasing user loads and bandwidth demands in live streaming systems especially for multimedia content delivery. Peer-to-peer (P2P) overlay networks provide excellent system scalability and high resource utilization, which make it an attractive solution to this problem. We consider a hybrid hierarchical P2P overlay network that consists of both super and normal peers to support live streaming applications. This architecture is built upon a tree-structured network of super peers, which organize normal peers into clusters. The tree construction process has a significant impact on the overall system performance. We formulate a specific type of problem, max-minTC, to maximize the minimum node throughput in tree construction, where the system's stream rate is optimized by constructing an efficient spanning tree among super peers. We present a decentralized approach where super peers run the same algorithm in parallel to derive a tree from an identical database describing the topology of the streaming system. This approach is able to quickly converge to a new tree upon the detection of any topological changes in super peers. The performance superiority of the proposed solution is illustrated by extensive simulations on a large set of simulated networks of various sizes from small to large scales in comparison with other methods.

Data transmission from sensor nodes to a base station or a sink node often incurs significant energy consumption, which critically affects network lifetime. We generalize and solve the problem of deploying multiple base stations to maximize network lifetime in terms of two different metrics under one-hop and multihop communication models. In the one-hop communication model, the sensors far away from base stations always deplete their energy much faster than others. We propose an optimal solution and a heuristic approach based on the minimal enclosing circle algorithm to deploy a base station at the geometric center of each cluster. In the multihop communication model, both base station location and data routing mechanism need to be considered in maximizing network lifetime. We propose an iterative algorithm based on rigorous mathematical derivations and use linear programming to compute the optimal routing paths for data transmission. Simulation results show the distinguished performance of the proposed deployment algorithms in maximizing network lifetime.

The success of various sensor network applications highly depends on the use of energy-conserving routing methods to prolong network lifetime. We present a heterogeneous sensor network architecture consisting of a small number of high-end sensors serving as sink nodes and a large number of low-end sensors responsible for environmental sensing. We propose a path bottleneck-oriented and energy cost-based routing scheme that uses a multi-objective function to optimize the balance of network-wide energy consumption. Within this routing scheme, we design (i) a centralized version for sensor networks with global topology information, (ii) a semi-distributed version to further improve energy efficiency, and (iii) a fully distributed version to support large-scale sensor networks. Extensive simulation results show that the proposed routing scheme outperforms existing routing algorithms in prolonging the lifetime of sensor networks.

Large-scale computation-intensive applications in various science fields feature complex DAG-structured workflows comprised of distributed computing modules with intricate inter-module dependencies. Supporting such workflows in heterogeneous network environments and optimizing their end-to-end performance are crucial to the success of large-scale collaborative scientific applications. We design and develop a generic Scientific Workflow Automation and Management Platform (SWAMP), which contains a set of easy-to-use computing and networking toolkits for application scientists to conveniently assemble, execute, monitor, and control complex computing workflows in distributed network environments. The current version of SWAMP integrates the graphical user interface of Kepler to compose abstract workflows and employs Condor DAGMan for workflow dispatch and execution. SWAMP provides a web-based user interface to automate and manage workflow executions and uses a special workflow mapper to optimize the end-to-end workflow performance. A case study of the workflow for Spallation Neutron Source datasets in real networks is presented to show the efficacy of the proposed platform.

Peer-to-peer (P2P) overlay networks provide a highly effective and scalable solution to live media streaming systems that require the collective use of massively distributed network resources. A P2P media streaming architecture is typically built completely or partially upon a tree-structured network topology and the process of tree construction has a significant impact on the overall system performance. We build network cost models and formulate a specific type of topology construction problem, Maximum Average Bandwidth Spanning Tree (MABST), which aims at optimizing the system's average stream rate. We prove that MABST is NP-complete by reducing from Hamiltonian Path problem and propose an efficient heuristic algorithm. The performance superiority of the proposed algorithm is justified by experimental results using a live media streaming system deployed in real networks and is also illustrated by an extensive set of simulations on simulated networks of various sizes in comparison with other methods based on a degree constraint or a greedy strategy.

There are an increasing number of high-performance networks that provision dedicated channels through circuit-switching or MPLS/GMPLS techniques to support bulk data transfer in large-scale science or e-commerce applications. These dedicated links are typically shared by multiple users through advance reservations, resulting in varying bandwidth availability in future time periods. Therefore, efficient advance bandwidth reservation algorithms are needed to improve the utilization of network resources and meet the transport requirements of application users. We investigate the bandwidth-oriented path computation problem for two types of data transfer: (i) fixed path with variable bandwidth and (ii) variable path with variable bandwidth to minimize the transfer end time of a given data size. We prove that both problems are NP-complete and propose a heuristic algorithm for each of them. Extensive simulation results illustrate the performance superiority of the proposed heuristics over methods based on greedy strategies.

The timely and reliable data transfer required by many networked applications necessitates the development of comprehensive security solutions to monitor and protect against an increasing number of malicious attacks. However, providing complete cyber space situation awareness is extremely challenging because of the lack of effective translation mechanisms from low-level situation information to high-level human cognition for decision making and action support. We propose an adaptive cyber security monitoring system that integrates a number of component techniques to collect time-series situation information, perform intrusion detection, keep track of event evolution, characterize and identify security events, and present a visual representation in order to provide comprehensive situational view so that corresponding defense actions can be taken in a timely and effective manner. We explore the principles of designing and applying appropriate visualization techniques for situation monitoring by defining graphical representations of security events. This differs from the traditional rule-based pattern matching techniques in that security events in the proposed system are represented as forms of correlation networks using random matrix theory and identified through the computation of network similarity measurement. The events and corresponding event types are visualized using a stemplot to show location and quantity. Extensive simulation results on event identification illustrate the efficacy of the proposed system.

Sensor network lifetime is largely affected by the energy consumption for data transmission from sensor nodes to a base station. We generalize and solve the problems of deploying multiple base stations in sensor networks using one-hop and multi-hop communication models to maximize network lifetime. Under the one-hop communication model, the sensors far away from base stations always deplete their energy much faster than others. We propose an optimal solution for small-scale networks and a heuristic approach for large-scale ones based on the smallest enclosing circle algorithm that deploys a base station at the geometric center of each cluster. Under the multi-hop communication model, both the base station locations and the data routing scheme need to be considered in maximizing network lifetime. We propose an iterative algorithm based on rigorous mathematical derivations and use linear programming to compute the optimal routing path for benchmark purposes. Extensive simulation results show superior network lifetime performance of the proposed deployment algorithms in comparison with existing ones.

There are an increasing number of high- performance networks that provision dedicated channels through circuit-switching or MPLS/GMPLS techniques to support large- scale data transfer. The available bandwidths on these dedicated links vary over time and therefore efficient bandwidth scheduling algorithms are needed to improve the utilization of network resources and satisfy diverse user requirements. Based on different path and bandwidth constraints, we formulate four instant scheduling problems for a data transfer request: (i) variable path with variable bandwidth (VPVB), (ii) fixed path with variable bandwidth (FPVB), (iii) variable path with fixed bandwidth (VPFB), and (iv) fixed path with fixed bandwidth (FPFB), with the common objective to minimize transfer end time for a given data size. We design an optimal algorithm for each of these scheduling problems with polynomial- or pseudo- polynomial-time complexity with respect to the network size and total number of time slots in a bandwidth reservation table.

An increasing number of high performance research network testbeds and production networks have the capability of provisioning dedicated channels for high speed data transfer in support of large scale scientific applications. Each dedicated channel in these networks typically consists of one or more physical links that are shared by multiple applications in both time and bandwidth through in advance reservation. The design of efficient bandwidth scheduling algorithms is critical to maximizing the utilization of dedicated network resources and meeting diverse end-to-end transport performance requirements. The topology of a dedicated network is represented by a graph, where each link maintains a list of residual bandwidths specified as segmented constant functions of time. Given a graph with an aggregated time-bandwidth table combining the reservation information on all links, designated source, and destination vertices, and a specified data size, we formulate and investigate five bandwidth scheduling problems to minimize the data transfer end time under different path and bandwidth constraints: (i) variable path with variable bandwidth (VPVB), which computes the widest (highest bandwidth) path in each time slot; (ii) fixed path with variable bandwidth (FPVB), which computes a fixed path with varying bandwidths across different time slots; (iii) variable path with fixed bandwidth (VPFB), which computes one path in each time slot with the same bandwidth; (iv) fixed path with fixed bandwidth (FPFB), which computes a fixed path with a constant bandwidth; and (v) multiple fixed paths with fixed bandwidths (MFPFB), which computes multiple concurrent fixed paths with constant bandwidths. Among these problems, VPVB represents the most flexible scenario where the network resources are fully utilized and the minimal transfer end time is achieved, while FPFB imposes the most stringent transport conditions by fixing both path and bandwidth. We design an optimal algorithm for each of these scheduling problems. VPVB is solved using an extension of the classical Dijkstra's algorithm, and FPVB is solved using Maximum Permutation Algorithm, which tries all possible permutations of throughputs at different time slots to obtain the minimal transfer end time. The algorithm for VPFB, FPFB, and MFPFB are based on Adjacent Time Slots Search, which finds the minimum transfer end time by examining the possibility of data transfer in any number of contiguous time slots. All these algorithms are of polynomial or pseudo polynomial time complexity with respect to the network size and the total number of time slots in a bandwidth reservation table.