Mobile edge computing is emerging as a new computing paradigm that provides enhanced experience to mobile users via low latency connections and augmented computation capacity. As the amount of user requests is time-varying, while the computation capacity of edge hosts is limited, Cloud Assisted Mobile Edge (CAME) computing framework is introduced to improve the scalability of the edge platform. By outsourcing mobile requests to clouds with various types of instances, the CAME framework can accommodate dynamic mobile requests with diverse quality of service requirements. In order to provide guaranteed services at minimal system cost, the edge resource provisioning and cloud outsourcing of the CAME framework should be carefully designed in a cost-efficient manner. Specifically, two fundamental issues should be answered: (1) what is the optimal edge computation capacity configuration? and (2) what types of cloud instances should be tenanted and what is the amount of each type? To solve these issues, we formulate the resource provisioning in CAME framework as an optimization problem. By exploiting the piecewise convex property of this problem, the Optimal Resource Provisioning (ORP) algorithms with different instances are proposed, so as to optimize the computation capacity of edge hosts and meanwhile dynamically adjust the cloud tenancy strategy. The proposed algorithms are proved to be with polynomial computational complexity. To evaluate the performance of the ORP algorithms, extensive simulations and experiments are conducted based on both the widely-used traffic models and the Google cluster usage tracelogs, respectively. It is shown that the proposed ORP algorithms outperform the local-first and cloud-first benchmark algorithms in system flexibility and cost-efficiency.

Hierarchical abstraction is a scalable strategy to deal with large networks. Existing visualization methods have allowed to aggregate the network nodes into hierarchies based on the node attributes or network topology, each of which has its own advantage. Very few previous system has the capability to enjoy the best of both worlds. This paper presents OnionGraph, an integrated framework for the exploratory visual analysis of heterogeneous multivariate networks. OnionGraph allows nodes to be aggregated based on either node attributes, topology, or a hierarchical combination of both. These aggregations can be split, merged and filtered under the focus+context interaction model, or automatically traversed by the information-theoretic navigation method. Node aggregations that contain subsets of nodes are displayed by the onion metaphor, indicating the level and details of the abstraction. We have evaluated the OnionGraph tool in three real-world cases. Performance experiments demonstrate that on a commodity desktop, our method can scale to million-node networks while preserving the interactivity for analysis.

Service composition is popular for composing a set of existing services to provide complex services. With the increasing number of services deployed in cloud computing environments, many service providers have started to offer candidate services with equivalent functionality but different Quality of Service (QoS) levels. Therefore, QoS-aware service composition has drawn extensive attention. Most existing approaches for QoS-aware service composition assume a service's QoS values are not correlated to those of other services. However, QoS dependency exists in real life, and impacts the overall QoS values of the composite services. In this article, we study QoS dependency-aware service composition considering multiple QoS attributes. Based on the Pareto set model, we focus on searching for a set of Pareto optimal solutions. A candidate pruning algorithm for removing the unpromising candidates is proposed, and a service composition algorithm using Vector Ordinal Optimization techniques is designed. Simulation experiments are conducted to validate the efficiency and effectiveness of our algorithms. We are the first to take advantage of Vector Ordinal Optimization techniques to search for Pareto optimal composition solutions with QoS dependency involved. The capturing of QoS dependency enables us to find truly desirable solutions.

Mobile edge computing (MEC) is emerging as an effective computing paradigm which alleviates the conflict between computation-intensive mobile applications and resource-constrained mobile devices. In this paper, a Cloud Assisted Mobile Edge computing (CAME) framework is adopted to enhance the adaptability of MEC to time-varying mobile requests. The resource provisioning problem is investigated to provide guaranteed quality of service (QoS) with minimum system cost. By exploiting the piecewise convexity of the problem, the Optimal Resource Provisioning (ORP) algorithm is developed, which determines the computation capacity at mobile edge and dynamically tunes the usage of cloud resources. Extensive simulations demonstrate that the ORP algorithm yields the minimum system cost, compared with the local-first and the cloud-first algorithms. In addition, the ORP algorithm can flexibly adapt to the time-varying mobile requests.

Big data analytics frameworks are developing towards larger degrees of parallelism and shorter task durations to achieve lower latency. Consequently, millions of scheduling decisions need to be made per second, which has posed a big challenge to today's centralized schedulers. Therefore, many researchers and enterprises turn to distributed scheduling approaches to avoid the throughput limitation of centralized designs. To our knowledge, Omega, Apollo and Sparrow are three famous approaches that make prior moves in distributed scheduling but they each have shortcomings and none of them try peer-to-peer architecture. We then propose a new scheduling approach called Piper that adapts peer-to-peer idea to the domain of distributed scheduling, which provides near-optimal performance. We have implemented Piper using Apache Thrift and the results show that Piper reduces job response times by over 1.5× when compared to Sparrow (we select Sparrow for comparison because it is a leading design and has been open source). In addition, trace-driven simulations have been used to evaluate Piper when scaling to large clusters, which further reveals that Piper provides better performance than Sparrow.

As big data analytics frameworks are developing towards larger degrees of parallelism and shorter task durations to provide lower latency, millions of scheduling decisions per second pose a great challenge to centralized schedulers. Therefore, increasing efforts are devoted to the study of distributed scheduling approaches to avoid the throughput limitation of centralized designs. Among these approaches, Sparrow is a leading design. However, due to Sparrow's sample-based techniques, some tasks in subsequent jobs may be scheduled earlier than those in the head-of-line job, which results in scheduling disorder and inevitably causes poor response times and unfairness. To address these problems, this paper proposes a simple algorithm called probe sharing: jobs that arrive at the same Sparrow scheduler can share their probes to ensure that all tasks in the head-of-line job can be scheduled earlier than subsequent jobs. We have performed theoretical analysis and proved that probe sharing makes a good improvement on Sparrow. We have implemented probe sharing in Sparrow and shown that probe sharing reduces scheduling delays by 2.2× and provides 100% fairness. Trace-driven simulations have been also used to evaluate probe sharing when scaling to large clusters. In addition, the simplicity of probe sharing makes it applicable to many schedulers that use Sparrow's techniques (e.g., Hopper, Tarcil and Eagle).

Mobile edge computing is envisioned as a promising computing paradigm with the advantage of low latency. However, compared with conventional mobile cloud computing, mobile edge computing is constrained in computing capacity, especially under the scenario of dense population. In this paper, we propose a Cloud Assisted Mobile Edge computing (CAME) framework, in which cloud resources are leased to enhance the system computing capacity. To balance the tradeoff between system delay and cost, mobile workload scheduling and cloud outsourcing are further devised. Specifically, the system delay is analyzed by modeling the CAME system as a queuing network. In addition, an optimization problem is formulated to minimize the system delay and cost. The problem is proved to be convex, which can be solved by using the Karush-Kuhn-Tucker (KKT) conditions. Instead of directly solving the KKT conditions, which incurs exponential complexity, an algorithm with linear complexity is proposed by exploiting the linear property of constraints. Extensive simulations are conducted to evaluate the proposed algorithm. Compared with the fair ratio algorithm and the greedy algorithm, the proposed algorithm can reduce the system delay by up to 33% and 46%, respectively, at the same outsourcing cost. Furthermore, the simulation results demonstrate that the proposed algorithm can effectively deal with the challenge of heterogeneous mobile users and balance the tradeoff between computation delay and transmission overhead.

With the increasing popularity of services published online, energy consumption of services computing systems is growing dramatically. Besides Quality of Service (QoS), energy efficiency has become an important issue and drawn significant attention. However, energy efficient request scheduling and service management for large-scale services computing systems face challenges because of the high dynamics and unpredictability of request arrivals. In this paper, we jointly consider the conflicting metrics of performance, queue congestion and energy consumption. We propose a distributed online scheduling and management algorithm which does not require any priori statistical knowledge of request arrivals. Mathematical analysis is conducted which demonstrates that our algorithm can achieve arbitrary tradeoff between performance and energy efficiency. Numerical and real trace data based experiments are carried out to validate the effectiveness of our algorithm in optimizing energy efficiency while stabilizing the system.

With the increasing popularity of social applications, people spend plenty of time in online social networking, such as chatting, sharing daily activities, etc. All these online activities are recorded in social applications and leave fingerprinting in network traffics. Both of these two data sources have the risk of leaking privacy. However, previous studies focus on the privacy leakage in social applications while privacy leakage in network traffics attracts less attention. Moreover, the works on privacy leakage in traffics focus on payload information of the traffics. As the internet is becoming more encrypted, in order to propose a general framework to reveal the privacy problem in the traffics, we turn attention to the traffics without payload information. In this paper, we develop a novel methodology to reveal the risk of relationship privacy leakage in network traffics without payload information. We first extract the chatting flows from the network traffics based on $k$-Nearest-Neighbors method. Then we create the ties between users by matching the chatting flows, and chatting patterns are used to verify whether the matched users are chatting with each other. Finally, network traces are used to evaluate the performance of our methodology. The experiments show we can recognize $96.42\%$ of the chatting flows with the precision of $96.96\%$, and we can detect all the ties between users who are chatting with each other.

Online information sources including Weibo and Wechat bring huge impact to the society. Only a few words of network information can expand rapidly and catalyze the generation of a huge amount of information. Semantic computing on online social networks and research on topics about emergencies have great significance. In this article, a numerical model of text semantic analysis based on artificial neural network is proposed, and a semantic computational algorithm for social network texts as well as a discovery algorithm for emergencies is provided with reference to the information provided by the social nodes itself and the semantic of the text. Semantic vector of micro-information for nodes and closure extension of semantic extensions are defined in order to build up an equivalence of short sentences, and in turn realize the discovery of emergencies.

In recent years, there has been a growing interest in the ability of embedded devices, sensors, and actuators to communicate, and create a ubiquitous cyber-physical world. The growth of the notion of the Internet of Things (IoT) and the rapid development of technologies such as short range mobile communication and improved energy-efficiency is expected to create a pervasive connection of “things.” This will inevitably result in the generation of enormous amount of data, which have to be stored, processed, and accessed. Cloud computing has long been recognized as a paradigm for big data storage and analytics. The combination of cloud computing and IoT can enable ubiquitous sensing services and powerful processing of sensing data streams beyond the capability of individual things, thus stimulating innovations in both fields. For example, cloud platforms allow the sensing data to be stored and used intelligently for smart monitoring and actuation with the smart devices. Novel data fusion algorithms, machine learning methods, and artificial intelligence techniques can be implemented and run centralized or distributed on the cloud to achieve automated decision making. These will boost the development of new applications, such as smart cities, grids, and transportation systems. New challenges, however, arise when IoT meets cloud—there is an urgent need for novel network architectures that seamlessly integrate them, and protocols that facilitate big data streaming from IoT to the cloud. QoS and QoE, as well as data security, privacy, and reliability, are critical concerns during the integration.

The communication delay of train control services has a great impact on the track utilization and speed profile of high-speed trains. This paper undertakes stochastic delay analysis of train control services over a high-speed railway fading channel using stochastic network calculus. The mobility model of high-speed railway communications system is formulated as a semi-Markov process. Accordingly, the instantaneous data rate of the wireless channel is characterized by a semi-Markov modulated process, which takes into account the channel variations due to both large- and small-scale fading effects. The stochastic service curve of high-speed railway communications system is derived based on the semi-Markov modulated process. Based on the analytical approach of stochastic network calculus, the stochastic upper delay bounds of train control services are derived with both the moment generating function method and the complementary cumulative distribution function method. The analytical results of the two methods are compared and validated by simulation.

Software as a Service (SaaS) has become an important application development and service delivery model. Among different architectures, multi-tenant architecture (MTA) not only has advantage on maintenance, but also increases resource utilization by sharing instances. However, sharing instances brings challenges to the security of the service. As one of the three principal properties of the security, availability receives more and more attentions. Recently, there are extensive efforts on technical methods to implement a secure multi-tenant SaaS, but few works on the modeling and analysis of its availability. In this paper, we firstly present the availability issues of the multi-tenant SaaS. Two important mechanisms to implement the MTA SaaS are then introduced: network isolation and database sharing. After that, a stochastic Petri net (SPN) model is developed to analyze the availability. Specific metrics are proposed to measure the availability both from the aspects of the system and the tenant. To extend the SPN model for large scale analysis, we solve the state space explosion problem of SPN model based on the theory of Markov chain aggregation. Finally, numerical results are provided to demonstrate the effectiveness of the SPN model and the analysis is efficient.

To achieve the flexibility in resource optimization, fault tolerance and load balancing, virtual machines(VMs) should be effectively migrated in data center networks(DCN). VMs are regulated by security policies and also required to relocate the policy during VM migration, which is a challenge problem to maintain not only the isolation among different domains and tenants, but also the consistency of policy configuration. In this paper, we consider the problem of policy relocation in Software-defined Network(SDN) context since it provides flexible control. We introduce a formal model describing the problem and present a novel policy relocation scheme called VPRS(a Virtual Policy Relocation Scheme), which is based on policy-aware principle and space-optimized method. It can prevent fragmentation of policy and reduce the memory usage while accurately relocating influenced policies. On the other hand, it also simplifies the management of policy. Specifically, VPRS contains novel algorithms for policy relocation, an app-layer policy management, policy translator and component for controllers notification. We define three actions of policy relocation based on the policy abstraction, and then describe the advantage of our scheme about selecting an optimized network address as target address. Then we introduce the core space-optimized algorithms, and evaluate the effectiveness of our scheme by providing consumption on their running overhead and utilization of rule space. Our scheme performs well on real policy sets, and has dramatic reduction by even up to 90\% on rule space costs with high utilization.

Software as a Service (SaaS) is an increasingly important service delivery model in cloud computing, and multitenancy makes it possible to support large scale customized tenants with only one code base. However, the complexity of multi-tenant architecture may lead to poor performance and low resource utilization. The customized demands may also lead to high operating cost. It is very important to develop an accurate model to predict the performance of the multi-tenant SaaS. To this end, a multi-tenant queueing network model is developed. Based on the model, a balanced SLA-aware tenant placement algorithm is proposed considering that customized tenants may need more resources to be placed together. The algorithm is effective in nearly 90% of the simulations comparing with other heuristic algorithms. Furthermore, the optimization problem on dynamic resource provision to minimize the operating cost is studied. As the original optimization problem is NPhard, a continuous upper bound is used to convert the original optimization problem into a convex optimization which can be solved efficiently in polynomial time. Finally, it is demonstrated that the approximate ratio of the proposed approach is no greater than 1.2 in more than 90% of the simulations.

Since TCP Incast has been identified as a catastrophic problem in many typical data center applications, a lot of efforts have been made to analyze or solve it. The analysis work intends to model Incast problem from certain perspective, and the solutions try to solve the problem through designing enhanced mechanisms or algorithms. However, the proposed models are either closely coupled with particular protocol version or dependent on empirical observations, and the solutions cannot eliminate Incast problem entirely because the underlying issues are not identified completely. There is little work which attempts to close the gap between “analyzing” and “solving”, and present a comprehensive understanding. In this paper, we provide an in-depth understanding of how TCP Incast problem happens. We build up an interpretive model which emphasizes particularly on describing qualitatively how various factors, including system parameters and mechanism variables, affect network performances in Incast traffic pattern, but not on calculating the accurate throughput. With this model, we give plausible explanations why the various solutions for TCP Incast problem can help, but do not solve it entirely.

Mobile cloud computing (MC2) is emerging as a promising computing paradigm which helps alleviate the conflict between resource-constrained mobile devices and resource-consuming mobile applications through computation offloading. In this paper, we analyze the computation offloading problem in cloudlet-based mobile cloud computing. Different from most of the previous works which are either from the perspective of a single user or under the setting of a single wireless access point (AP), we research the computation offloading strategy of multiple users via multiple wireless APs. With the widespread deployment of WLAN, offloading via multiple wireless APs will obtain extensive application. Taking energy consumption and delay (including computing and transmission delay) into account, we present a game-theoretic analysis of the computation offloading problem while mimicking the selfish nature of the individuals. In the case of homogeneous mobile users, conditions of Nash equilibrium are analyzed, and an algorithm that admits a Nash equilibrium is proposed. For heterogeneous users, we prove the existence of Nash equilibrium by introducing the definition of exact potential game and design a distributed computation offloading algorithm to help mobile users choose proper offloading strategies. Numerical extensive simulations have been conducted and results demonstrate that the proposed algorithm can achieve desired system performance.

Recently, Ethernet is enhanced as the unified switch fabric of data centers, called data center Ethernet. One of the indispensable enhancements is end-to-end congestion management, and currently quantized congestion notification (QCN) has been ratified as the corresponding standard. However, our experiments show that QCN suffers from large oscillations of the queue length at the bottleneck link such that the buffer is emptied frequently and accordingly the link utilization degrades, with certain system parameters and network configurations. This phenomenon is corresponding to our theoretical analysis result that QCN fails to enter into the sliding mode motion (SMM) pattern with certain system parameters and network configurations. Knowing the drawbacks of QCN and realizing the advantage that congestion management system is insensitive to the changes of parameters and network configurations in the SMM pattern, we present sliding mode congestion control (SMCC), which can enter into the SMM pattern under any conditions. SMCC is simple, stable, fair, has short response time, and can be easily used to replace QCN because both of them follow the framework developed by the IEEE 802.1Qau work group. Experiments on the NetFPGA platform show that SMCC is superior to QCN, especially when traffic pattern and network states are variable.

Visually analyzing citation networks poses challenges to many fields of the data mining research. How can we summarize a large citation graph according to the user's interest? In particular, how can we illustrate the impact of a highly influential paper through the summarization? Can we maintain the sensory node-link graph structure while revealing the flow-based influence patterns and preserving a fine readability? The state-of-the-art influence maximization algorithms can detect the most influential node in a citation network, but fail to summarize a graph structure to account for its influence. On the other hand, existing graph summarization methods fold large graphs into clustered views, but can not reveal the hidden influence patterns underneath the citation network. In this paper, we first formally define the Influence Graph Summarization problem on citation networks. Second, we propose a matrix decomposition based algorithm pipeline to solve the IGS problem. Our method can not only highlight the flow-based influence patterns, but also easily extend to support the rich attribute information. A prototype system called VEGAS implementing this pipeline is also developed. Third, we present a theoretical analysis on our main algorithm, which is equivalent to the kernel k-mean clustering. It can be proved that the matrix decomposition based algorithm can approximate the objective of the proposed IGS problem. Last, we conduct comprehensive experiments with real-world citation networks to compare the proposed algorithm with classical graph summarization methods. Evaluation results demonstrate that our method significantly outperforms the previous ones in optimizing both the quantitative IGS objective and the quality of the visual summarizations.

Applications running on the same Wireless Sensor Network (WSN) platform usually have different Quality of Service (QoS) requirements. Two basic requirements are low delay and high data integrity. However, in most situations, these two requirements cannot be satisfied simultaneously. In this paper, based on the concept ofpotentialin physics, we propose IDDR, a multi-path dynamic routing algorithm, to resolve this conflict. By constructing a virtual hybrid potential field, IDDR separates packets of applications with different QoS requirements according to the weight assigned to each packet, and routes them towards the sink through different paths to improve the data fidelity for integrity-sensitive applications as well as reduce the end-to-end delay for delay-sensitive ones. Using the Lyapunov drift technique, we prove that IDDR is stable. Simulation results demonstrate that IDDR provides data integrity and delay differentiated services.

Currently, Ethernet is being enhanced to become the unified switch fabric in data centers. With the unified switch fabric, the cost on redundant devices is reduced, while the design and management of data center networks are simplified. Congestion management is one of the indispensable enhancements on Ethernet, and Quantized Congestion Notification (QCN) has just been ratified as the formal standard. Though QCN has been investigated for several years, there exist few in-depth theoretical analyses on QCN. The most possible reason is that QCN is heuristically designed and involves the property of variable structure. The classic linear analysis method is incapable of handling the segmented nonlinearity of the variable structure system. In this paper, we use the phase plane method, which is suitable for systems of segmented nonlinearity, to analyze the QCN system. The overall dynamic behaviors of the QCN system are presented, and the sufficient conditions for the stable QCN system are deduced. These sufficient conditions serve as guidelines toward proper parameters setting. Moreover, we find that the stability of QCN is mainly promised by the sliding mode motion, which is the underlying reason for QCN's stable queue shown in numerous simulations and experiments. Experiments on the NetFPGA platform verify that the analytical results can explain the complex behaviors of QCN.

TCP Incast problem attracts much attention due to the catastrophic goodput drop. In this paper, a goodput model of the problem is built to understand why goodput collapse occurs and a solution to the problem based on the theoretical analysis is proposed. We found that the TCP Incast goodput deterioration is mainly caused by two types of timeouts, one happens at the tail of data blocks and dominates the goodput when the number of senders is small, while the other one at the head of data blocks and governs the goodput when the number of senders is large. The proposed model describes the relationship between these two types of timeouts and the Incast communication pattern, block size, bottleneck buffer size, and so on. The simulation results indicate that the model well characterizes the features of the TCP Incast problem. Enlightened by the analysis, a PRiority-based solution to the TCP INcast problem (PRIN) is proposed, which avoids timeouts at the head of blocks by reducing TCP send window and prevents timeouts at the tail of blocks by leveraging priority technology. The experimental results show that PRIN solves the TCP Incast problem.

As web service has become a popular way for engineering software on the Internet, quality of service (QoS) which describes non-functional characteristics of web services is often employed in service composition. Since QoS is an aggregated concept consisting of several attributes, service composition on enormous candidate sets is a challenging multi-objective optimization problem. In this paper, we study the problem from a general Pareto optimal angle, seeking to reduce search space in service composition. Pareto set model for QoS-aware service composition is introduced, and its relationship with the widely used utility function model is theoretically studied, which proves the applicability of our model. QoS attributes are systematically studied according to their different types of aggregation patterns in service composition, and QoS-based dominance relationships between candidates and between workflows are defined. Taking advantage of pruning candidates by dominance relationships and constraint validations at candidate level, a service composition algorithm using partial selection techniques is proposed. Furthermore, a parallel approach is designed, which is able to significantly reduce search space and achieve great performance gains. A careful analysis of the optimality of our approach is provided, and its efficacy is further validated by both simulation experiments and real-world data based evaluations.

Dynamic network visualization has been a challenging research topic due to the visual and computational complexity introduced by the extra time dimension. Existing solutions are usually good for overview and presentation tasks, but not for the interactive analysis of a large dynamic network. We introduce in this paper a new approach which considers only the dynamic network central to a focus node, also known as the egocentric dynamic network. Our major contribution is a novel 1.5D visualization design which greatly reduces the visual complexity of the dynamic network without sacrificing the topological and temporal context central to the focus node. In our design, the egocentric dynamic network is presented in a single static view, supporting rich analysis through user interactions on both time and network. We propose a general framework for the 1.5D visualization approach, including the data processing pipeline, the visualization algorithm design, and customized interaction methods. Finally, we demonstrate the effectiveness of our approach on egocentric dynamic network analysis tasks, through case studies and a controlled user experiment comparing with three baseline dynamic network visualization methods.

Abstract Wireless sensor networks (WSNs) have been widely investigated in the past decades because of its applicability in various extreme environments. As sensors use battery, most works on WSNs focus on energy efficiency issues (e.g., local energy balancing problems) in statically deployed WSNs. Few works have paid attention to the global energy balancing problem for the scenario that mobile sensor nodes can move freely. In this paper, we propose a new routing protocol called global energy balancing routing protocol (GEBRP) based on an active network framework and node relocation in mobile sensor networks. This protocol achieves global energy efficiency by repairing coverage holes and replacing invalid nodes dynamically. Simulation and experiment results demonstrate that the proposed GEBRP achieves superior performance over the existing scheme. In addition, we analyze the delay performance of GEBRP and study how the delay performance is affected by various system parameters.Copyright © 2013 John Wiley & Sons, Ltd.

Aggregation is a scalable strategy for dealing with large network data. Existing network visualizations have allowed nodes to be aggregated based on node attributes or network topology, each of which has its own advantages. However, very few previous systems have the capability to enjoy the best of both worlds. This paper presents OnionGraph, an integrated framework for exploratory visual analysis of large heterogeneous networks. OnionGraph allows nodes to be aggregated based on either node attributes, topology, or a mixture of both. Subsets of nodes can be flexibly split and merged under the hierarchical focus+context interaction model, supporting sophisticated analysis of the network data. Node aggregations that contain subsets of nodes are displayed with multiple concentric circles, or the onion metaphor, indicating how many levels of abstraction they contain. We have evaluated the OnionGraph tool in two real-world cases. Performance experiments demonstrate that on a commodity desktop, OnionGraph can scale to million-node networks while preserving the interactivity for analysis.

As one of the pricing model offered by Amazon, reserved instance enables users to reserve capacities for their EC2 instances and lowers their average instance cost. To attract more users to adopt the reserved instance, Amazon has provided a platform named Reserved Instance Marketplace to give users the flexibility to sell the remainder of their reserved instances as their needs change. However, the present trading mechanism inside the Reserved Instance Marketplace requires the reserved instance sellers to sell their reserved capacities at month level and set the upfront fee by themselves, which is not flexible enough and hard for an inexperienced seller to specify a suitable upfront fee. To address this problem, this paper proposes an online mechanism for the Reserved Instance Marketplace. Our online mechanism tries to maximize the sellers' revenue by dynamically allocating the reserved capacities among various buyers without the need of specifying upfront fee in advance. The competitive ratio of the online allocation algorithm inside our mechanism is proved to be within a small constant factor of optimal competitive ratio in theory. To evaluate the performance of our online mechanism, we conduct simulations on synthetic data and real data trace from one of Google clusters. The simulation results show that our online mechanism can achieve at least 55% of the offline optimal algorithm in most cases.

Visually mining a large influence graph is appealing yet challenging. Existing summarization methods enhance the visualization with blocked views, but have adverse effect on the latent influence structure. How can we visually summarize a large graph to maximize influence flows? In particular, how can we illustrate the impact of an individual node through the summarization? Can we maintain the appealing graph metaphor while preserving both the overall influence pattern and fine readability? To answer these questions, we first formally define the influence graph summarization problem. Second, we propose an end-to-end framework to solve the new problem. Last, we report our experiment results. Evidences demonstrate that our framework can effectively approximate the proposed influence graph summarization objective while outperforming previous methods in a typical scenario of visually mining academic citation networks.

With the increasing presence of web services on the Internet, Quality of Service (QoS) is becoming important for describing non-functional characteristics of web services, and is often employed in web service composition. As QoS is an aggregated concept consisting of several attributes, service composition on enormous candidate sets is a challenging multi-objective optimization problem. In this paper, we study the problem from a general Pareto-optimal angle, seeking to reduce the search space in service composition. QoS attributes are systematically studied according to their different types of aggregation pattern in service composition, and QoS-based dominance relationships between candidates and between workflows are defined. Taking advantage of pruning candidates by dominance relationships and constraint validations at candidate level, a service composition algorithm using partial selection technique is proposed, which is able to significantly reduce the search space and achieve great performance gains. A careful analysis of the optimality of our approach is provided, and its efficacy is further validated by empirical evaluation.

With the increasing popularity of web services on the Internet, service selection has become an important issue in large-scale web service systems. In recent years, with the growing energy consumption associated with IT systems and services, energy efficiency has drawn extensive attention in service allocation and selection. However, existing approaches for energy efficient web service selection face great challenges, because of the high dynamics and unpredictability of task arrivals, and large scale of current web service systems. In this paper, we present a distributed online approach for web service selection that jointly considers the conflicting performance metrics including response time, queue congestion and energy consumption. Targeting at optimizing the long-term average system reward, our approach does not require any priori knowledge of the statistics or prediction on task arrivals. Mathematical analysis as well as simulation experiments demonstrate its effectiveness in optimizing energy efficiency while stabilizing the system.

With the increasing popularity of web services on the Internet, besides functionalities, Quality of Service (QoS) is becoming an important concern for describing characteristics of web services. QoS rankings provide valuable information for making optimal service selection and recommendation from a set of functionally similar or equivalent service candidates. However, in order to obtain such rankings, a huge number of invocations on the services are usually required, which is extremely expensive and even impractical in reality. To tackle this challenge, this paper proposes a scheme to derive the global ranking from observations of QoS rankings on subsets of the services, while the observations may also be contaminated by noise and errors. We introduce a pairwise comparison model to describe the relationships between services, and thus the ranking can be formulated as random walks over the services. A Markov chain based approach is proposed, and algorithms for deriving global rankings are designed. The efficacy of our approach is validated by both mathematical analysis and simulation experiments.

The proliferation of cloud services makes virtualization technology more important. One important feature of virtualization is live Virtual Machine (VM) migration, which can be employed to facilitate load balancing, fault management and server maintenance etc. Two main metrics of evaluating a live VM migration mechanism are total migration time and downtime. The existing literature on live VM migration mainly focus on designing migration mechanisms to shorten these two metrics or making a tradeoff between them. Few of them can be applied to the applications with delay requirements, such as, delay-sensitive web services or a VM backup process that needs to be done in a specific time. This will not only negatively impact the user experiences, but also reduce the profit of cloud service providers. Besides, the frequently varied bandwidth required by the widely used pre-copy mechanism is difficult to be provided by current network technologies. In this work, we theoretically analyze how much bandwidth is required to guarantee the total migration time and downtime of a live VM migration. We first propose a deterministic-based model as a simple example, then assume that the dirtying frequency of each page obeys the bernoulli distribution. At last, we analyze the statistic features of the typical workload running in a VM and build a reciprocal-based workload model, and theoretically give the required bandwidth value to satisfy the performance metrics of a live VM migration. The experimental results demonstrate that the bandwidth obtained from the reciprocal-based model can guarantee the expected total migration time and downtime.

Big data processing frameworks are developing towards larger degrees of parallelism and shorter task durations in order to achieve lower response time. Scheduling highly parallel tasks that complete in nearly 100 milliseconds poses a major challenge for task schedulers. Taking the challenge, researchers turn to decentralized frameworks to relieve the pressure of task schedulers, among which Sparrow is a good choice. However, little efforts are devoted to fault tolerance of Sparrow, which does not handle worker failures, giving rise to incomplete tasks. We present a fault tolerance mechanism named Heartbeat on Sparrow to handle failures of worker machines. Through simulation, we compare it with a simple mechanism. The result shows that Heartbeat on Sparrow can detect worker failures faster and reschedule all failed tasks more efficiently, achieving recovery of tasks and states in sub-second time. We hope this mechanism will make some contributions to Sparrow and other decentralized designs on fault tolerance side.

With the increasing popularity of Software defined network (SDN), designing a scalable SDN control plane becomes a critical problem. An effective approach to improving the scalability is to design distributed architecture of SDN control plane. However, how to evaluate the scalability of SDN control planes remains unexplored. In this paper, we propose a metric of scalability for SDN control planes, and study three typical SDN control plane structures, including centralized, decentralized and hierarchical architectures. We build performance models for response time, based on which we evaluate the scalability of these three structures. Furthermore, the comparison between different architectures are analyzed by mathematical methods. Numerical evaluations are also conducted to validate the conclusions drawn in this paper.

Enhancing Ethernet as the unified data center fabric to concurrently handle the traffic of Local Area Network (LAN), Storage Area Network (SAN), and High Performance Computing (HPC) has attracted much attention. Congestion management is one critical enhancement to fill the performance gap between traditional Ethernet and the unified data center fabric. Currently, Quantized Congestion Notification (QCN) has been approved as the standard congestion management mechanism. However, lots of work pointed out that QCN suffers from the problem of unfairness among different flows. In this paper, we found that QCN could achieve fairness, merely the convergence time to fairness is quite long. Thus, we build a convergence time model to investigate the reasons of the slow convergence process of QCN. The model indicates that the convergence time of QCN can be decreased if RPs have the same rate increase probability or the rate increase step becomes larger at steady state. We validate the precise of our model by comparing with experimental data on the NetFPGA platform. The results show that it well characterizes the convergence time to fairness of QCN. Based on the proposed model, the impact of QCN parameters, network parameters, and QCN variants on the convergence time is analysed. Finally, enlightened by the analysis, we proposed a mechanism, called QCN-T, which replaces the Byte Counter and Timer at sources with a single modified Timer, to reduce the convergence time of QCN.

Error estimating codes (EEC) have recently been proposed for measuring the bit error rate (BER) in packets transmitted over wireless links. They however can provide such measurements only when there are no insertion and deletion errors, which could occur in various wireless network environments. In this work, we propose ``idEEC'', the first technique that can do so even in the presence of insertion and deletion errors. We show that idEEC is provable robust under most bit insertion and deletion scenarios, provided insertion/deletion errors occur with much lower probability than bit flipping errors. Our idEEC design can build upon any existing EEC scheme. The basic idea of the idEEC encoding is to divide the packet into a number of segments, each of which is encoded using the underlying EEC scheme. The basic idea of the idEEC decoding is to divide the packet into a few slices in a randomized manner -- each of which may contain several segments -- and then try to identify a slice that has no insertion and deletion errors in it (called a ``clean slice''). Once such a clean slice is found, it is removed from the packet for later processing, and this ``randomized divide and search'' procedure will be iteratively performed on the rest of the packet until no more clean slices can be found. The BER will then be estimated from all the clean slices discovered through all the iterations. A careful analysis of the accuracy guarantees of the idEEC decoding is provided, and the efficacy of idEEC is further validated by simulation experiments.

With the rapid development of wireless communication technology, a large number of wireless networks and devices that have different PHY and MAC layers coexist with each other. 2.4GHz Industrial, Scientific and Medical (ISM) band is becoming increasingly crowded. Wireless Sensor Networks (WSNs) which use low-power communication standard IEEE802.15.4 share the unlicensed spectrum with a plethora of other devices and technologies, such as WiFi systems underlying IEEE802.11, Bluetooth systems underlying IEEE802.15.1, and even non-communication appliance like microwave ovens. The ability to detect what radios are operating in the neighborhood is a fundamental need of WSNs, ranging from network management to network security. Since there are no explicit mechanisms to recognize such heterogeneous interference sources, WSNs often have no reasonable way to guard against them. In this paper, we describe the main working principle of heterogeneous interference sources, and present HEIR, a detector that is able to accurately identify heterogeneous interference sources. HEIR builds on the insight that there are hidden repeating patterns of signals which can be used to construct unique signatures and identify different types in most wireless protocols. The method can be implemented through signal sampling, interference estimation, feature extraction, and device classification. We show the experimental evaluation in an indoor testbed that HEIR is accurate in several different scenarios, and can live on sensor nodes' hardware. Since no any channel changes, the network topology is not interrupted, and the stable communication in real-time is ensured then.

In this study, the authors form a wireless channel model for orthogonal frequency‐division multiplexing (OFDM) systems with stochastic high‐level Petri net (SHLPN) formalism in order to simplify the cross‐layer performance analysis of modern wireless systems. Compared with existing finite state Markov channel model whose state space grows exponentially with the number of OFDM subchannels, the author's proposed SHLPN model uses state aggregation technique to deal with this problem. Closed‐form expressions to calculate the transition probabilities among the compound markings of the SHLPN model are provided. When applied to derive the performance measures for OFDM system in terms of the average throughput, average delay and packet dropping probability, the SHLPN model can accurately capture the correlated time‐varying nature of wireless channels. Simulation is performed to show that the numerical results offered by the proposed model are more accurate compared with other simplified channel models for avoiding state space complexity.

In today's data centers, the round trip propagation delay is quite small. Therefore, switch buffer sizes are much larger than the Bandwidth Delay Product (BDP). Based on this observation, in this paper we introduce a new transport protocol which provides bandwidth Sharing by Allocating switch Buffer (SAB) for data centers. SAB sets the congestion windows for flows based on the buffer size of the switches along the path. On one hand, as long as the total buffer allocated to all the flows is larger than the BDP, the network bandwidth can be fully utilized. On the other hand, since SAB only allocates the buffer space to flows, the totally injected traffic will not exceed the network capacity. Thus, SAB rarely loses packets. SAB also reduces flow completion time by allowing flows to reach their fair share of bandwidth quickly. The results of a series of experiments and simulations demonstrate that SAB has the features of fast convergence and rare packet loss. It reduces the latency of short flows and solves theTCP Incast and TCP Outcast problems.

At present, companies and standards organizations are enhancing Ethernet as the unified switch fabric for all of the TCP/IP traffic, the storage traffic and the high performance computing traffic in data centers. Backward congestion notification (BCN) is the basic mechanism for the end-to-end congestion management enhancement of Ethernet. To fulfill the special requirements of the unified switch fabric, i.e., losslessness and low transmission delay, BCN should hold the buffer occupancy around a target point tightly. Thus, the stability of the control loop and the buffer size are critical to BCN. Currently, the impacts of delay on the performance of BCN are unidentified. When the speed of Ethernet increases to 40 Gbps or 100 Gbps in the near future, the number of on-the-fly packets becomes the same order with the buffer size of switch. Accordingly, the impacts of delay will become significant. In this paper, we analyze BCN, paying special attention on the delay. We model the BCN system with a set of segmented delayed differential equations, and then deduce sufficient condition for the uniformly asymptotic stability of BCN. Subsequently, the bounds of buffer occupancy are estimated, which provides direct guidelines on setting buffer size. Finally, numerical analysis and experiments on the NetFPGA platform verify our theoretical analysis.

Energy saving is an important issue in Mobile Ad Hoc Networks (MANETs). Recent studies show that network coding can help reduce the energy consumption in MANETs by using less transmissions. However, apart from transmission cost, there are other sources of energy consumption, e.g., data encryption/decryption. In this paper, we study how to leverage network coding to reduce the energy consumed by data encryption in MANETs. It is interesting that network coding has a nice property of intrinsic security, based on which encryption can be done quite efficiently. To this end, we propose P-Coding, a lightweight encryption scheme to provide confidentiality for network-coded MANETs in an energy-efficient way. The basic idea of P-Coding is to let the source randomly permute the symbols of each packet (which is prefixed with its coding vector), before performing network coding operations. Without knowing the permutation, eavesdroppers cannot locate coding vectors for correct decoding, and thus cannot obtain any meaningful information. We demonstrate that due to its lightweight nature, P-Coding incurs minimal energy consumption compared to other encryption schemes.

Dependability is an important consideration during the design and development of IT systems and services. But in services computing systems, the traditional definition and evaluation methods from the systems' and components' point of view meet challenges. In this paper, we veer from the angle of view and study the dependability and their attributes from the service-oriented perspective. A stochastic model using the semi-Markov process is put forward, and the quantitative analysis of the dependability attributes is carried out. By extending and transforming this model, the mean time to dependability attributes failure is calculated. Based on the analysis and calculations, some theorems are proposed and proved, to show the inter-relationships and comparisons of the different dependability attributes. Furthermore, we model the service composition and conduct workflow analysis to show how this model could deal with complex services. In addition, LANL service systems are analyzed as a case study to show how the proposed model and calculation methods could apply to real systems, and sensitivity analysis is also performed to identify the bottlenecks and find effective ways for dependability optimization.

In this paper, we study the performance of mode selections in device-to-device (D2D) communications in terms of end-to-end average throughput, average delay, and dropping probability, considering dynamic data arrival with non-saturated buffers. We first introduce a general framework that includes three canonical routing modes, namely D2D mode, cellular mode, and hybrid mode, which can be combined with different resource allocation restrictions to represent the semi-static and dynamic selections of the three resource sharing modes. A queuing model is developed when the routing mode for every D2D connection is chosen, and an exact numerical analysis and an approximate decomposition and iteration approach are proposed. The performance measures are obtained from the decomposition approach and validated by means of simulation. We further introduce a mode selection scheme that adaptively chooses to semi-statically or dynamically select the resource sharing modes according to the estimated performance measures.

ABSTRACT The growing popularity of mobile devices in our daily life demands higher throughput of wireless networks. The new communication standard 802.11n has significantly improved throughput because of the use of advanced technologies such as the multiple‐input multiple‐output communication technique. Because mobile devices are usually battery‐operated, power efficiency is critical; on the other hand, delay performance can be improved by transmitting at high power. To address the conflicting requirement of power saving and small delay, power scheduling is needed. In the past, many approaches to power scheduling have been proposed for real‐time applications, but few of them have considered complicated modes of channel state information(CSI) in multiple‐input multiple‐output. In this paper, we study this and classify the CSI into four types, namely, constant, slow fading, fast fading, and unknown. For known CSI, we propose an optimal algorithm for power scheduling. For unknown CSI, we propose an approximate algorithm based on some heuristics. To improve resource utilization, a stochastic delay‐bound method is proposed for fast‐fading condition. Simulation results demonstrate that the performance achieved by the optimal and heuristic algorithms agrees well with the analysis. Copyright © 2012 John Wiley & Sons, Ltd.

The packet loss burstiness over wireless channels is commonly acknowledged as a key impacting factor on the performance of networking protocols.An accurate evaluation of the packet loss burstiness, which reveals the characteristics and performance of the wireless channels, is crucial to the design of wireless systems and the quality-of-service provisioning to end users.In this paper, a simple yet accurate analytical framework is developed to dimension the packet loss burstiness over generic wireless channels.In specific, we first propose a novel and effective metric to characterize the packet loss burstiness, which is shown to be more compact, effective, and accurate than the metrics proposed in existing literature for the same purpose.With this metric, we then develop an analytical framework and derive the closed-form solutions of the packet loss performance, including the packet loss rate and the loss-burst/loss-gap length distributions.Lastly, as an example to show how the derived results can be applied to the design of wireless systems, we apply the analytical results to devise an adaptive packetization scheme.The proposed packetization scheme adaptively adjusts the packet length of transmissions based on the prediction of the packet loss rate and loss-burst/loss-gap lengths of the wireless channel.Via extensive simulations, we show that with the proposed packetization scheme, the channel throughput can be enhanced by more than 10% than the traditional scheme.

The visualization of complex network traffic involving a large number of communication devices is a common yet challenging task. Traditional layout methods create the network graph with overwhelming visual clutter, which hinders the network understanding and traffic analysis tasks. The existing graph simplification algorithms (e.g. community-based clustering) can effectively reduce the visual complexity, but lead to less meaningful traffic representations. In this paper, we introduce a new method to the traffic monitoring and anomaly analysis of large networks, namely Structural Equivalence Grouping (SEG). Based on the intrinsic nature of the computer network traffic, SEG condenses the graph by more than 20 times while preserving the critical connectivity information. Computationally, SEG has a linear time complexity and supports undirected, directed and weighted traffic graphs up to a million nodes. We have built a Network Security and Anomaly Visualization (NSAV) tool based on SEG and conducted case studies in several real-world scenarios to show the effectiveness of our technique.

This paper studies the queuing performance of direct communications between user equipments in cellular networks. Both the fast fading effects of the wireless channel and the dynamic variation of interference from a link associated with its backlogged state are considered in the service process description, which complicates the queuing model and results in the size of the underlying Markov process growing exponentially with the link number. We use the model decomposition and iteration approach in Stochastic Petri Nets (SPN) to deal with the coupling between the service rates of the different links and thus reduce the state space of the Markov process. Simulations are performed to verify the accuracy of the analytical results.

It is a common problem for Wireless LAN (WLAN) users when they face more than one available Access Point (AP): which one may serve them better? In the real world, most WLAN devices and users select the AP by Received Signal Strength (RSS), which doesn't consider the load of APs. Therefore, the RSS-based scheme may result in load imbalance and utilization degradation. This paper proposes a simple scheme to inform WLAN users the available bandwidth when selecting a specific AP. Unlike the previous work, the new scheme concerns about the aggregated traffic patterns in AP, which affects the amount of the available bandwidth. Considering the number of active stations and influence of collision, the available bandwidth is calculated and regarded as a selection metric. Common users can acquire this metric through Service Set IDentifier (SSID) without any modifications on their devices, and users who accept modifications can select the preferable AP dynamically and automatically. This scheme is very simple to be implemented and deployed with negligible overhead to network. We conduct simulations to verify this scheme, which can improve by 200% the user's throughput in some situations.

This paper proposes a new network-wide optimized time division multiple access (TDMA) scheduling scheme for wireless sensor networks (WSNs). It can simultaneously achieve maximum throughput and fair rate allocation given the requirement of network lifetime. To achieve this object, we first formulate the rate allocation problem based on the Lexicographic Max-Min (LMM) criterion, which takes fairness, throughput maximization, and slot reuse into consideration. Then, we develop a polynomial-time algorithm by exploiting iterative linear program (LP) to solve the LMM optimization. Based on the optimal rate allocation vector and relay scheme derived from the optimization model, we present a TDMA scheduling algorithm to achieve a minimum TDMA frame length through slot reuse. We jointly interconnect the LMM rate allocation and TDMA scheduling algorithm with a slot reuse control parameter, and propose a procedure to iteratively calculate a proper value for this parameter. Numerical results show that our proposed TDMA schedule improves the fairness and throughput significantly.

Content-Centric Network (CCN) provides a cleanslate design for the Internet, where content becomes the primitive of communications. In CCN, routers are equipped with content stores, which act as caches for frequently requested content. This design enables the Internet to provide content distribution services without any application-layer support. On the other hand, as caches are integrated into routers, the overall performance of CCN will be influenced by the caching efficiency. This paper studies the performance issues of caches in CCN, with the aim to gain some understanding on how caches should be designed to maintain a high performance in a cost-efficient way. Specifically, we use a two-dimensional discrete-time Markov chain to model the two-layer cache hierarchy formed by CCN routers, and develop an efficient algorithm to calculate the hit ratios of these caches. Simulations validate the accuracy of our modeling method, and convey some understanding on cache design in CCN.

Because of the terrible performance of TCP protocol in data center environment, DCTCP has been proposed as a TCP replacement, which uses a simple marking mechanism at switches and a few amendments at end hosts to adjust congestion window based on the extent of the congestion in networks. Thus, DCTCP can make a proper tradeoff between high throughput and low latency. However, through our observation, we discover that DCTCP causes severe oscillation of queue under some parameters and network configuration. Our perceptual analysis concludes that the rough single-threshold marking mechanism may be the essential reason. Therefore, we propose Double-Threshold DCTCP as an improvement of DCTCP. Then, by applying describing function method in nonlinear control theory, we analyze the stability of both DCTCP and Double-Threshold DCTCP, and theoretically explain why Double-Threshold DCTCP is more stable than DCTCP. At last, we validate theoretical analysis and conclude that the Double- Threshold DCTCP can achieve smaller queue, and the queue length of Double-Threshold DCTCP is less sensitive to the growing number of flows. Further, Double-Threshold DCTCP can postpone the throughput collapse caused by Incast traffic and reduce the tail latency in completion time experiment.

The TCP incast problem attracts a lot of attention due to its wide existence in cloud services and catastrophic performance degradation. Some effort has been made to solve it. However, the industry is still struggling with it, such as Facebook. Based on the investigation that the TCP incast problem is mainly caused by the TimeOuts (TOs) occurring at the boundary of the stripe units, this paper presents a simple and effective TCP enhanced mechanism, called GIP (Guarantee Important Packets), for the applications with the TCP incast problem. The main idea is making TCP aware of the boundaries of the stripe units, and reducing the congestion window of each flow at the start of each stripe unit as well as redundantly transmitting the last packet of each stripe unit. GIP modifies TCP a little at the end hosts, thus it can be easily implemented. Also, it poses no impact on the other TCP-based applications. The results of both experiments on our testbed and simulations on the ns-2 platform demonstrate that TCP with GIP can avoid almost all of the TOs and achieve high goodput for applications with the incast communication pattern.

Distributed computing system is considered as a fundamental architecture to extend resources such as computation speed, storage capacity, and network bandwidth, which are limited for a single processor. Emerging big data processing techniques like Hadoop take advantages of distributed servers to accomplish scalable parallel computations. Large-scale processing jobs can run on different servers or even different clusters interdependently and be combined together as a workflow to provide meaningful outputs. In this paper, we analyze the common demands of big-data processing and distributed big-data workflow processing. According to that, we design Pipe Flow Engine that has the matching features to meet each of these demands. It orchestrates all involved jobs and schedules them in a batched pipeline mode. We also present two online ranking algorithms that make use of the Pipe Flow, sharing the experience and best practice of using Pipe Flow.

Reliability is a critical concern in the provision and placement of web services. A breakdown of service would seriously reduce customers' satisfaction, and thus harm the revenue of service providers. To maintain a high reliability, the common approach is deploying multiple service instances across different physical servers. This would inevitably raise another concern of energy consumption. Thus, greening web services also becomes an important issue. In this paper, we study the fundamental tradeoff between reliability and energy consumption, and propose an optimization framework that considers both factors. In specific, we build a continuous-time Markov model to analyze the steady-state reliability and mean time to failure (MTTF) from a service-oriented perspective, and obtain the minimum number of service instances to meet the given reliability requirement. Then, we show that deploying these instances in the server cluster to minimize energy consumption is NP-hard. To this end, we propose a heuristic algorithm to approximate the result. The analytical and experimental results show the effectiveness, and the approximation ratio is less than 1.25 for 90% of the data sets we use.

With the increase of the energy consumption associated with IT systems and services, energy efficiency is becoming a critical concern in the design, development and management of web service systems. In this paper, both the web service selection and server dynamic speed scaling are optimized by maximizing the quality of service (QoS) revenue and minimizing energy costs. Stochastic models of web service systems are proposed, and quantitative analysis of the performance and energy consumption is carried out. In addition, the service selection and speed scaling problem is formulated as a Markov Decision Process (MDP) problem, and algorithms to solve it are introduced. Furthermore, we propose an agent-based optimization framework and design related algorithms to solve the service selection and speed scaling problem in large-scale web service systems. Finally, their effectiveness is validated by simulation results.

Energy consumption imposes a significant cost for data centers; yet much of that energy is used to maintain excess service capacity during periods of predictably low load. Resultantly, there has recently been interest in developing designs that allow the service capacity to be dynamically resized to match the current workload. However, there is still much debate about the value of such approaches in real settings. In this paper, we show that the value of dynamic resizing is highly dependent on statistics of the workload process. In particular, both slow time-scale non-stationarities of the workload (e.g., the peak-to-mean ratio) and the fast time-scale stochasticity (e.g., the burstiness of arrivals) play key roles. To illustrate the impact of these factors, we combine optimization-based modeling of the slow time-scale with stochastic modeling of the fast time scale.

Enterprises build private clouds to provide IT resources for geographically distributed subsidiaries or product divisions. Public cloud providers like Amazon [1] lease their platforms to enterprise users, thus, enterprises can also rent a number of virtual machines (VMs) from their data centers in the service provider networks. Unfortunately, the networks cannot always guarantee stable connectivity for their clients to access the VMs or low-latency transfer among data centers. Usually, latency and bandwidth are in an uncertain network environment. Being affected by background traffics, the network status can be volatile. To reduce the latency of client accesses, enterprises should consider the network status when they deploy data centers or rent virtual data centers from cloud providers. In this paper, we first develop a long-term oblivious data center deployment scheme for an enterprise to meet its client requirements under uncertain network status. Then, we design the optimal VM assignment schemes to assign VMs residing on each data center to each client in the enterprise. To accommodate to the changes of the network status, a VM migration scheme is adopted. The latter two schemes are short-term optimizations given the data center deployment policy. The two-time-scale optimizations work in a joint way, and lay down a framework to help enterprises make better use of private clouds or public clouds.

Recently, the energy consumption of Ethernet has become one of the hottest topics focused by both academic committee and industry, especially with the increase of the link speed from 1Gbps to 10Gbps nowadays or even 40/100/200Gbps in the near future. To save the energy consumed by the Ethernet, the Energy Efficient Ethernet (EEE) is developed and standardized by the IEEE 802.3az work group. When there is no incoming traffic, the EEE can saves 90 % of its energy consumption by entering into the Low Power Idle (LPI) mode. To maximize the energy saving of Ethernet, the Burst TRansmission (BTR) algorithm, which defines a new way to utilize the LPI mode, is developed as a policy for EEE. Prior work theoretically shows that the BTR algorithm makes a tradeoff between the energy saving and the queuing delay. However, the traffic pattern, on which the performance of EEE greatly depends, is assumed to be deterministic in their analyses. Besides, their models made estimation for many situations. In this paper, assuming that the arrival time of packets can be modeled by Poisson process, we build Markov model for EEE with the BTR algorithm and provide analytical understanding on the BTR algorithm. We propose two actual models: one focuses on the buffer size limit, the other concentrates on tolerable packet delay additionally. We draw some guidelines of parameter selection and policy design for EEE from combination of theory conclusions and simulation results. The results show that the saved energy can be constrained by link occupancy even though the buffer size is variational. The other policy buffer full triggered wake-up can achieve ideal ratio of energy consumption and arrival rate within the scope of the buffer as well. However, the tolerable delay can not be guaranteed by any policies. The buffer size is even fixed, which affects the flexibility of demanded delay for different business. The policy considering tolerable delay is supposed to be a little better than the other policy, with a little more complicated design. Thus we design an adaptive policy: detect the load utilization, apply the buffer full triggered wake-up policy for higher load utilization link, while applying the buffer full and timeout triggered wakeup policy for the delay sensitive business and tiny arrival rate.

Peer-to-peer file sharing systems, most notably BitTorrent (BT), have achieved tremendous success among Internet users. Recent studies suggest that long-term relationships among BT peers could be explored for peer cooperation, so as to achieve better sharing efficiency. However, whether such long-term relationships exist remain unknown. From an 80-day trace of 100,000 real world swarms, we find that less than 5% peers can meet each other again throughout the whole period, which largely invalidates the fundamental assumption of these peer cooperation protocols. Yet the recent emergence of online social network applications sheds new light on this problem. In particular, a number of BT swarms are now triggered by Twitter, reflecting a new trend for initializing sharing among communities. In this paper, we for the first time examine the challenges and potentials of accelerating peer-to-peer file sharing with Twitter social networks. We show that the peers in such swarms have stronger temporal locality, thus offering great opportunity for improving their degree of sharing. Based on the Hadamard Transform of peers' online behaviors, we develop a social index to quickly locate peers of common patterns. We further demonstrate a practical cooperation protocol that identifies and utilizes the social relations with the index. Our PlanetLab experiments indicate that the incorporation of social relations remarkably accelerates the downloading time. The improvement remains noticeable even in a hybrid system with a small set of socially active peers only.

ABSTRACT In this paper, we propose a novel modeling method attack–defense stochastic game Petri nets (or ADSGN) to model and analyze the security issues in enterprise network. We firstly give the definition and modeling method algorithm of ADSGN and then propose the algorithm of the strategy. The proposed ADSGN method is successfully applied to describe the attack and defense courses in the enterprise network. Finally, we analyze the mean time to first security breach and the mean time to security breach in the enterprise network quantifiably, and proved that our method can also be applied to other areas with respect to game issues. Copyright © 2012 John Wiley & Sons, Ltd.

In this paper, we investigate the Frequency Domain Packet Scheduling (FDPS) problem for 3GPP Long Term Evolution (LTE) Uplink (UL). Instead of studying a specific scheduling policy, we provide a unified approach to tackle this issue. First, we formalize a general LTE UL FDPS problem, which is suitable for various scheduling policies. Then, we prove that the problem is MAX SNP-hard, which implies that approximation algorithms with constant approximation ratios are the best that we can hope for. Therefore, we design two approximation algorithms, both of which have polynomial runtime. The first algorithm is based on a simple greedy method. The second one is based on the Local Ratio (L-R) technique and it can approximately solve the LTE UL FDPS problem with an approximation ratio of 2. To further analyze the stability of the 2-approximation L-R algorithm, we derive a specific FDPS problem, which incorporates the queue length and channel quality information. We utilize the Lyapunov Drift to prove the L-R algorithm is stable for any $((\omega_0, \epsilon_0))$-admissible LTE UL systems. The simulation results indicate good performance of the L-R scheduler.

Wireless Sensor Networks (WSNs) are embracing an increasing number of real-time applications subject to strict delay constraints. Utilizing the methodology of potential field in physics, in this article we effectively address the challenges of real-time routing in WSNs. In particular, based on a virtual composite potential field, we propose the Potential-based Real-Time Routing (PRTR) protocol that supports real-time routing using multipath transmission. PRTR minimizes delay for real-time traffic and alleviates possible congestions simultaneously. Since the delay bounds of real-time flows are extremely important, the end-to-end delay bound for a single flow is derived based on the Network Calculus theory. The simulation results show that PRTR minimizes the end-to-end delay for real-time routing, and also guarantees a tight bound on the delay.

The resources especially energy in wireless sensor networks (WSNs) are quite limited. Since sensor nodes are usually much dense, data sampled by sensor nodes have much redundancy, data aggregation becomes an effective method to eliminate redundancy, minimize the number of transmission, and then to save energy. Many applications can be deployed in WSNs and various sensors are embedded in nodes, the packets generated by heterogenous sensors or different applications have different attributes. The packets from different applications cannot be aggregated. Otherwise, most data aggregation schemes employ static routing protocols, which cannot dynamically or intentionally forward packets according to network state or packet types. The spatial isolation caused by static routing protocol is unfavorable to data aggregation. To make data aggregation more efficient, in this paper, we introduce the concept of packet attribute, defined as the identifier of the data sampled by different kinds of sensors or applications, and then propose an attribute-aware data aggregation (ADA) scheme consisting of a packet-driven timing algorithm and a special dynamic routing protocol. Inspired by the concept of potential in physics and pheromone in ant colony, a potential-based dynamic routing is elaborated to support an ADA strategy. The performance evaluation results in series of scenarios verify that the ADA scheme can make the packets with the same attribute spatially convergent as much as possible and therefore improve the efficiency of data aggregation. Furthermore, the ADA scheme also offers other properties, such as scalable with respect to network size and adaptable for tracking mobile events.

In this paper, we study the performance of Device-to-Device (D2D) communications with dynamic interference. In specific, we analyze the performance of frequency reuse among D2D links with dynamic data arrival setting. We first consider the arrival and departure processes of packets in a non-saturated buffer, which result in varying interference on a link based on the change of its backlogged state. The packet-level system behavior is then represented by a coupled processor queuing model, where the service rate varies with time due to both the fast fading and the dynamic interference effects. In order to analyze the queuing model, we formulate it as a Discrete Time Markov Chain (DTMC) and compute its steady-state distribution. Since the state space of the DTMC grows exponentially with the number of D2D links, we use the model decomposition and some iteration techniques in Stochastic Petri Nets (SPNs) to derive its approximate steady state solution, which is used to obtain the approximate performance metrics of the D2D communications in terms of average queue length, mean throughput, average packet delay and packet dropping probability of each link. Simulations are performed to verify the analytical results under different traffic loads and interference conditions.

In this paper, we formalize a general Frequency Domain Packet Scheduling (FDPS) problem for 3GPP LTE Downlink (DL). The DL FDPS problem incorporates the SingleUser Multiple Input Multiple Output (SU-MIMO) technique, and can express various scheduling policies, including the Proportional-Fair metric, the MaxWeight scheduling, etc. For LTE DL SU-MIMO, the constraint of selecting only one MIMO mode (transmit diversity or spatial multiplexing) per user in each transmission time interval (TTI) increases the hardness of the FDPS problem. We prove the problem is MAX SNP-hard, which implies approximation algorithms with constant approximation ratios are the best we can expect. Subsequently, we propose an approximation algorithm of polynomial runtime. The solution is based on a greedy method for maximizing a non-decreasing submodular function over a matroid. The algorithm can solve the general DL FDPS problem with an approximation ratio of 4. We implement the proposed algorithm and compare its performance with other well-known schedulers.

Wireless networks are expected to support a diverse range of quality of service requirements and traffic characteristics. This paper undertakes stochastic performance analysis of a wireless finite-state Markov channel (FSMC) by using stochastic network calculus. Particularly, delay and backlog upper bounds are derived directly based on the analytical principle behind stochastic network calculus. Both the single user and multi-user cases are considered. For the multi-user case, two channel sharing methods among eligible users are studied, i.e., the even sharing and exclusive use methods. In the former, the channel service rate is evenly divided among eligible users, whereas in the latter, it is exclusively used by a user randomly selected from the eligible users. When studying the exclusive use method, the problem that the state space increases exponentially with the user number is addressed using a novel approach. The essential idea of this approach is to construct a new Markov modulation process from the channel state process. In the new process, the multi-user effect is equivalently manifested by its transition and steady-state probabilities, and the state space size remains unchanged even with the increase of the user number. This significantly reduces the complexity in computing the derived backlog and delay bounds. The presented analysis is validated through comparison between analytical and simulation results.

In cloud computing, the sensitive data are required to be encrypted before being outsourced to the server, which introduce a heavy computation overhead for key derivation and data management when dynamic hierarchical access control is desired. In this paper, we address this challenging problem by delegating the computation intensive task, such as data re-encryption, key distribution and derivation to cloud servers. Only bilinear pairing and random padding are used in our construction. Extensive analysis shows that the proposed scheme achieves scalability and dynamic simultaneously, and is proved to be secure formally.

Recently, companies and standards organizations are enhancing Ethernet as the unified switch fabric for all of the TCP/IP traffic, the storage traffic and the interprocess communication(IPC) traffic in Data Center Networks(DCNs). Backward Congestion Notification(BCN) is the basic mechanism for the end-to-end congestion management enhancement. To fulfill the special requirements of the unified switch fabric that being lossless and of extremely low latency, BCN should hold the queue length around a target point tightly. Thus, the stability of the control loop and the buffer size are critical to BCN. Currently, the impacts of delay on the performance of BCN are unidentified. When the link capacity increases to 40Gbps or 100Gbps in the near future, the number of on-the-fly packets becomes the same order with the shallow buffer size of switches. Thus, the impacts of delay on the performance of BCN will become significant. In this paper, we analyze BCN, paying special attention on the delay. Firstly, we model the BCN system with a set of segmented delayed differential equations. Then, the sufficient condition for the uniformly asymptotic stability of the BCN system is deduced. Subsequently, the bound of buffer occupancy under this sufficient condition are estimated, which provides guidelines on setting buffer size. Finally, the numerical analysis and the experiments on the NetFPGA platform verify the theoretical analysis.

Recently, Ethernet is being enhanced as the unified switch fabric of data centers, called Data Center Ethernet. The end-to-end congestion management is one of the indispensable enhancements, and Quantized Congestion Notification (QCN) has been ratified to be the standard. Our experiments show that QCN suffers from the oscillation of the queue at the bottleneck link. With the changes of system parameters and network configurations, the oscillation may become so serious that the queue is emptied frequently. As a result, the utilization of the bottleneck link degrades. Theoretical analysis shows that QCN approaches to the equilibrium point mainly through the sliding mode motion. But whether QCN enters into the sliding mode motion also depends on both system parameters and network configurations. Hence, we present the Sliding Mode Congestion Control (SMCC) scheme, which can drive the system into the sliding mode motion under any conditions. SMCC benefits from the advantage that the sliding mode motion is insensitive to system parameters and external disturbances. Moreover, SMCC is simple, stable and has short response time. QCN can be replaced by SMCC easily since both of them follow the framework developed by the IEEE 802.1 Qau work group. Experiments on the NetFPGA platform show that SMCC is superior to QCN, especially in the condition that the traffic pattern and the network state are variable.

This paper investigates the interactions between two-way TCP connections over 3GPP LTE networks. In the LTE network, the two-way TCP flows share buffers on a common bottleneck, i.e., the radio access links. The behaviors of TCPs significantly influence the others in the opposite direction. Specifically, the radio links of LTE are asymmetric, which may induce drastic interactions of TCPs and rapid draining of downlink buffer. The periodic idleness of downlink is a huge waste of the precious radio bandwidth and results in considerable performance degradation. In the viewpoint of Coupled Queues, we thoroughly understand the interacting TCPs and explain the reason for performance degradation. Based on a straightforward modeling procedure, we formalize the evolution of two-way TCPs and model the bottleneck queue size in every slot. The model indicates the queues are close coupled, which is verified with simulations on NS2. If the uplink (queue) is fully utilized, the downlink (queue) will always be underutilized even idle, and vice versa. Furthermore, an effective solution called Preemptive ACK Queueing (PAQ) is designed to decouple the queues, which improves the performance of two-way TCPs over LTE networks.

Energy consumption imposes a significant cost for data centers; yet much of that energy is used to maintain excess service capacity during periods of predictably low load. Resultantly, there has recently been interest in developing designs that allow the service capacity to be dynamically resized to match the current workload. However, there is still much debate about the value of such approaches in real settings. In this paper, we show that the value of dynamic resizing is highly dependent on statistics of the workload process. In particular, both slow time-scale non-stationarities of the workload (e.g., the peak-to-mean ratio) and the fast time-scale stochasticity (e.g., the burstiness of arrivals) play key roles. To illustrate the impact of these factors, we combine optimization-based modeling of the slow time-scale with stochastic modeling of the fast time scale. Within this framework, we provide both analytic and numerical results characterizing when dynamic resizing does (and does not) provide benefits.

Sentiment plays a critical role in many information-centric business scenarios. The opinion mining methods proposed in the recent decade have formed a solid foundation to investigate the sentiment analysis tasks, but are often too complicated and scattered to serve the needs of real customers. We introduce the VISA system in this paper, which applies the visualization technology to synthesize the sentiment analysis results and present to the end user in an interactive manner. VISA builds on the generic sentiment tuple based data model and consumes the different facets of sentiment data with coordinated multiple views, hence is scalable to work with most of existing sentiment analysis engines on various application domains. We showcase the usage of VISA in a real world example and demonstrate the system's effectiveness through the user trail in finding an appropriate hotel for his family trip.

Renewable energy such as solar and wind generation will constitute an important part of the future grid. As the availability of renewable sources may not match the load, energy storage is essential for grid stability. In this paper we investigate the feasibility of integrating solar photovoltaic (PV) panels and wind turbines into the grid by also accounting for energy storage. To deal with the fluctuation in both the power supply and demand, we extend and apply stochastic network calculus to analyze the power supply reliability with various renewable energy configurations. To illustrate the validity of the model, we conduct a case study for the integration of renewable energy sources into the power system of an island off the coast of Southern California. In particular, we asses the power supply reliability in terms of the average Fraction of Time that energy is Not-Served (FTNS).

Practical wireless network coding (e.g., COPE) is a promising technique that can enhance the throughput of wireless networks. However, such a technique also bears a serious security drawback: it breaks the current privacy-preserving protocols (e.g., Onion Routing), since their operations conflict each other. As user privacy in wireless networks is highly valued nowadays, a new privacy-preserving scheme that can function with wireless network coding becomes indispensable. To address such a challenge, we apply the idea of cooperative networking and design a novel anonymity scheme named ANOC, which can function in network-coding-based wireless mesh networks. ANOC is built upon the classic Onion Routing protocol, and resolves its conflict with network coding by introducing efficient cooperation among relay nodes. Using ANOC, we can perform network coding to achieve a higher throughput, while still preserving user privacy in wireless mesh networks. We formally show how ANOC achieves the property of relationship anonymity, and conduct extensive experiments via nsclick to demonstrates its feasibility and efficiency when integrated with network coding.

The increasing transmission of illegal videos over the Internet imposes the needs to develop large-scale digital video forensics systems for prosecuting and deterring digital crimes in the Internet. In this paper, we propose, design, and implement a novel large-scale Digital Forensics Service Platform (DFSP) that can effectively detect illegal content from Internet videos. More specifically, we propose a distributed architecture by taking advantage of Content Delivery Network (CDN) to improve scalability, which can process enormous number of Internet videos in real time. We propose CDN-based Resource-Aware Scheduling (CRAS) algorithm, which schedules the tasks efficiently in the DFSP according to resource parameters, such as delay and computation load. We deploy the DFSP system in the Internet, which integrates the CDN-based distributed architecture and CRAS algorithm with a large-scale video detection algorithm, and evaluate the deployed system. Our evaluation results demonstrate the effectiveness of the platform.

Recently, distributed data storage has gained increasing popularity for reliable access to data through redundancy spread over unreliable nodes in wireless sensor networks (WSNs). However, without any protection to guarantee the data integrity and availability, the reliable data storage cannot be achieved since sensor nodes are prone to various failures, and attackers may compromise sensor nodes to pollute or destroy the stored data. Therefore, how to design a robust sensor data storage scheme to efficiently guarantee the data integrity and availability becomes a critical issue for distributed sensor storage networks. In this paper, we propose a distributed fault/intrusion-tolerant data storage scheme based on network coding and homomorphic fingerprinting in volatile WSNs environments. For high data availability, the proposed scheme uses network coding to encode the source data and distribute encoded fragments with original data pieces. With secure, compact, and efficient homomorphic fingerprinting, our scheme can fast locate incorrect fragments and then initialize data maintenance. Extensive theoretical analysis and simulative results demonstrate the efficacy and efficiency of the proposed scheme.

As an indispensable infrastructure for the future life, smart grid is being implemented to save energy, reduce costs, and increase reliability. In smart grid, control center networks have attracted a great deal of attention, because their security and dependability issues are critical to the entire smart grid. Several studies have been conducted in the field of smart grid security, but few work focuses on the dependability analysis of control center networks. In this paper, we adopt a concise mathematic tool, stochastic Petri nets (SPNs), to analyze the dependability of control center networks in smart grid. We present the general model of control center networks by considering different backup strategies of critical components. With the general SPNs model, we can measure the dependability from two metrics, i.e., the reliability and availability, through analyzing the transient and steady-state probabilities simultaneously. To avoid the state-space explosion problem in computing, the state-space explosion avoidance method is proposed as well. Finally, we study a specific case to demonstrate the feasibility and efficiency of the proposed model in the dependability analysis of control center networks in smart grid.

Multi-resource sharings among virtual machines (VM)are very important in data center, but also bring contentions for cache, disk and network in host server. Recent studies focus primarily on locally optimizing resource sharings in a single server, or global optimization of mitigating cache and memory contentions. But it remains an open question how to efficiently find optimal co-schedules for cache, disk and network contentions simultaneously. Solving these contentions is critical for computing-intensive, memory-intensive, data-intensive and network-intentive applications. This paper is the first to present a comprehensive solution to reduce multiple resource contentions in terms of cache, disk and network contentions in data center. We propose two estimation models, MPain and MVector Distance, to predict co-run performance degradation based on the VM solo running information. Experiment results on real servers reveal that the MVector Distance is more effective than up-to-date task activity vector model in EuroSys'10, reducing the average performace degradation from 8.545% to near zero in exhaustive search cases. We develop both proactive and runtime reactive approximation algorithms, among which, the simple balance algorithm is a three-dimensional coupling algorithm, produces near optimal schedules and shows good scalability. This study offers some techniques which could be directly used in proactive and runtime reative VM co-schedulings.

Strict delay performance guarantees are required by many applications in wireless sensor networks. Different from traditional approaches, the data aggregation and the stochastic characteristic need to be considered for the delay analysis in sensor networks. In this paper, the problem that how to calculate the stochastic delay bound under different aggregation schemes is solved with the stochastic network calculus. Meanwhile, to support multifunction in sensor networks, the impact of the heterogeneous services is brought into the analysis of the stochastic delay bound. From some numerical evaluations and the simulation, it is shown that a good tradeoff between performance and implementation can be achieved with a comprehensive aggregation scheme.

In the service-oriented computing, a single transaction initiated by a client might invoke many different services in other administrative domains. Existing models for authorizing the access assume that all services involved in collaboration are managed by the central authority, which is not always a realistic premise. In this paper, we propose a novel authorization model for dynamic service collaboration. With the authorization discovery process, the client can discover the needed authorization for service access available in other autonomous domains. With extensions to SoD relationship, the conflicts of client interests can be formalized and expressed as constraints. The authorization problems are formalized to choose the optimal access path for each task. At last, the example and experiments show the practicality and the effectiveness of our scheme.

Virtual data center is becoming increasingly popular as the infrastructure of Cloud computing. In order to provide efficient and uninterrupted service, the dependability of the Cloud infrastructure has received extensive attention. But modeling and analysis of dependability of the virtual data center is challenging for the particular characteristics and mechanisms of virtualization. In this paper, we use hierarchical method and develop the hybrid models combining reliability block diagrams and general stochastic Petri nets. Focusing on the two attributes reliability and availability, we give the computation expressions by solving the models. The impact of the characteristics and mechanisms of virtualization such as consolidation backup and live migration on dependability is studied. We analyze the relation between reliability and consolidation ratio, as well as the relation between availability and the workload. In addition, some useful rules are summarized and discussed, which are believed to be helpful to the design and construction of more dependable virtual data center.

In this paper, we consider the Request Routing (RR) strategy in the CDN live streaming application. We show that to find an optimal RR strategy is correspond to a static optimization problem if the total number of clients is known in advance. However, this static approach is ineffective due to the difficulty in precisely estimating the number of clients off-line. We then develop the MPS scheduling algorithm to compute the multiphase RR strategy. Experimental study shows that our algorithm can generate a close-to-optimal strategy with respect to a wide range of the number of clients.

The rapid development of applications running on global information infrastructure poses the problem of securing information sharing among domain collaborations. Existing access control models are defective in dynamic authorization based on user's trustworthiness and do not take full advantages of the infrastructure in implementing access control system. In this work, we propose a trust and role based access control model and the corresponding framework in infrastructure-centric environment. With the extension to RBAC model, trust level requirements, which dictate that the roles in the privilege context must be activated by the trustworthy user, can be specified. The comprehensive trust model, which calculates the user's trust level in multiple trust contexts based on behavior histories, is proposed. Moreover, by taking advantages of the infrastructure services, our scheme is flexible and scalable in that system administrators are free to choose custom scoring functions while the infrastructure trust evaluation services are relieved of the heavy burdens of history record maintenance and trust level update.

Web service composition can make use of distributed services with various functions to accomplish a specific task. Service binding and composition become keywords to service computing. In the context of workflow management, service binding plays an important part in forming a concrete workflow after an abstract one is submitted. Existing research is devoted to selecting a set of servers to run the corresponding services in an application and achieving better QoS. Due to the data intensity of data flow, the communication between two server nodes may bring significant delay that can not be neglected when considering the performance of the whole application process. In this work, we consider not only the QoS on each server but also the transfer delay of data that affects the total latency. Algorithms are designed to determine a set of service candidates for web service workflow with different structural characteristics. We measure and utilize indispensable parameters to implement these algorithms. Further, we propose Lagrange and ARP algorithms to make comprehensive decisions when taking into account other QoS metrics besides latency.

Network coding provides a promising alternative to traditional store-and-forward transmission paradigm. However, due to its information-mixing nature, network coding is notoriously susceptible to pollution attacks: a single polluted packet can end up corrupting bunches of good ones. Existing authentication mechanisms either incur high computation/bandwidth overheads, or cannot resist the tag pollution proposed recently. This paper presents a novel idea termed “padding for orthogonality” for network coding authentication. Inspired by it, we design a public-key based signature scheme and a symmetric-key based MAC scheme, which can both effectively contain pollution attacks at forwarders. In particular, we combine them to propose a unified scheme termed MacSig, the first hybrid-key cryptographic approach to network coding authentication. It can thwart both normal pollution and tag pollution attacks in an efficient way. Simulative results show that our MacSig scheme has a low bandwidth overhead, and a verification process 2–4 times faster than typical signature-based solutions in some circumstances.

Recently, TCP incast problem attracts increasing attention since the receiver suffers drastic goodput drop when it simultaneously strips data over multiple servers. Lots of attempts have been made to address the problem through experiments and simulations. However, to the best of our knowledge, few solutions can solve it fundamentally at low cost. In this paper, a goodput model of TCP incast is built to understand why goodput collapse occurs. We conclude that TCP incast goodput deterioration is mainly caused by two types of timeouts, one happens at the tail of a data block and dominates the goodput when the number of senders is small, while the other one at the head of a data block and governs the goodput when the number of senders is large. The proposed model describes the causes of these two types of timeouts which are related to the incast communication pattern, block size, bottleneck buffer and so on. We validate the proposed model by comparing with simulation data, finding that it can well characterize the features of TCP incast. We also discuss the impact of most parameters on the goodput of TCP incast.

Femtocell technology has gained widespread attention recently due to its advantages, such as infrastructure cost reduction, improved service coverage and high data throughput in indoor environments. As femtocell networks are customer-deployed without proper network planning, their interference environment tends to be much more complicated than traditional cellular networks. The authors present the framework of channel allocation in orthogonal frequency-division multiplexing access (OFDMA) femtocell network with the graphical approaches. A novel graph-based interference coordination scheme is proposed to maximise the system throughput while ensuring proportional rate fairness among femtocells. The scheme explicitly uses the received signal-to-interference-plus-noise-ratio to generate the interference graph of OFDMA femtocell networks, so as to guarantee the acceptable inter-cell interference for all the links. First, all the femtocells are partitioned into different groups by applying a greedy graph colouring algorithm to maximise the sum throughput of each group. The femtocells in the same group share the assigned subchannels while those in different groups are allocated to orthogonal subchannels. Then, an optimisation problem is formulated to determine the number of subchannels assigned to each group. Further, an approximation method is proposed to solve the optimisation problem. Simulation results are conducted to demonstrate the effectiveness of the proposed scheme in terms of throughput and fairness index.

To facilitate a viable evolution of cellular networks toward extensive packet data traffic, the High Speed Downlink Packet Access (HSDPA) technology is introduced. The various link adaptation techniques employed by HSDPA augment the bandwidth variation, which is identified as one of the most important factors resulting in the deterioration of TCP performance. In this paper, we firstly build an analytical model of TCP throughput to explain why the bandwidth variation degrades the TCP performance. Subsequently, a split-connection Window Adaptation TCP Proxy is proposed to improve the TCP throughput in HSDPA networks. To use the precious cellular link resources sufficiently, the length of the queue in Node-B is intentionally kept around the reference value through adaptively adjusting the sending window size of TCP proxy based on the dynamic values of varying bandwidth. Since both the disturbance caused by bandwidth variation and the feedback delay are prone to lead an unstable queue system, the robust sliding mode variable structure control theory is employed to design the proper control law to weaken the impact of noise and delay on the stability of the queue system in Node-B. The theoretical analysis and the enhanced scheme are verified through simulation experiments. The simulation results show that our TCP proxy is able to resist against bandwidth oscillation and improve the cellular link utilization.

The congestion problem in Wireless Sensor Networks (WSNs) is quite different from that in traditional networks. Most current congestion control algorithms try to alleviate the congestion by reducing the rate at which the source nodes inject packets into the network. However, this traffic control scheme always decreases the throughput so as to violate fidelity level required by the applications. In this paper, we present a solution that sufficiently exerts the idle or underloaded nodes to alleviate congestion and improve the overall throughput in WSNs. To achieve this goal, a traffic-aware dynamic routing (TADR) algorithm is proposed to route packets around the congestion areas and scatter the excessive packets along multiple paths consisting of idle and underloaded nodes. Utilizing the concept of potential in classical physics, our TADR algorithm is designed through constructing a hybrid virtual potential field using depth and normalized queue length to force the packets to steer clear of obstacles created by congestion and eventually move toward the sink. The simulation results show that the proposed solution improves the overall throughput by around 370 percent as compared to MintRoute, which is one of benchmark routing protocols. Furthermore, TADR scheme has low overhead suitable for large-scale, dense sensor networks.

Energy is an extremely critical resource for battery-powered wireless sensor networks (WSN), thus making energy-efficient protocol design a key challenging problem. Most of the existing energy-efficient routing protocols always forward packets along the minimum energy path to the sink to merely minimize energy consumption, which causes an unbalanced distribution of residual energy among sensor nodes, and eventually results in a network partition. In this paper, with the help of the concept of potential in physics, we design an Energy-Balanced Routing Protocol (EBRP) by constructing a mixed virtual potential field in terms of depth, energy density, and residual energy. The goal of this basic approach is to force packets to move toward the sink through the dense energy area so as to protect the nodes with relatively low residual energy. To address the routing loop problem emerging in this basic algorithm, enhanced mechanisms are proposed to detect and eliminate loops. The basic algorithm and loop elimination mechanism are first validated through extensive simulation experiments. Finally, the integrated performance of the full potential-based energy-balanced routing algorithm is evaluated through numerous simulations in a random deployed network running event-driven applications, the impact of the parameters on the performance is examined and guidelines for parameter settings are summarized. Our experimental results show that there are significant improvements in energy balance, network lifetime, coverage ratio, and throughput as compared to the commonly used energy-efficient routing algorithm.

It is widely recognized that the packet loss burstiness over wireless channels has a significant impact on the performance of network protocols. The analysis of packet loss burstiness, however, is very challenging, and there is a lack of well-established analytical models to provide fundamental insights for characterizing the burstiness. To address the issue, in this paper, we develop a generic analytical model to study the packet loss burstiness. In the model, we use the correlation length of packet loss rate as a metric to represent the packet loss burstiness mathematically, and we formulate the metric by investigating the correlations between packet losses. In addition, a closed-form expression of packet loss rate is derived for protocol design. We apply the model to design an adaptive packetization scheme, which can enhance the channel throughput by over 10%. Simulation results are given to validate the proposed model and scheme.

This paper concentrates on the performance analysis of channel contention in wireless ad hoc networks by using Stochastic Game Nets (SGN). We refine the definition of SGN so that it can be used to precisely capture the underlying details of a given system. A SGN model is developed to evaluate the channel utilization in a two-node wireless system. We quantify the system performance under equilibrium strategies. The findings of this paper are instructive for the design and deployment of wireless ad hoc networks.

Cloud computing provides a novel computing paradigm for enterprises to store programs and data in the Cloud in a transparent manner, which poses the challenge of security and privacy. In this paper, based on homomorphic cryptography and Zero-Knowledge Proof, we present a novel privacy-preserving scheme for Cloud publish/subscribe service, which achieve efficient privacy-preserving authentication, data integrity, and publish-subscribe confidentiality. The performance evaluation and security analysis demonstrate the practice and validity of the proposed scheme.

Recently, sensor data storage has gained increasing popularity for reliable access to data through redundancy spread over unreliable nodes in wireless sensor networks. In storage-centric sensor networks, several schemes have been proposed to optimize the performance of data management in terms of data availability, repair bandwidth, etc. However, few works have been undertaken to study the performance of these data management schemes from a comprehensive point of view. In this paper, we adopt a concise graphic model, i.e., Stochastic Petri Nets (SPNs), to analyze the performance of three representative data management schemes. From the steady state probability matrix of the SPNs models, we can easily get the average energy consumption, repair bandwidth, reliability and data availability. Based on numerical results, we provide guidelines for designing sensor data storage systems. The results also demonstrate that our proposed models are suitable for analyzing data management schemes in sensor data storage.

Intricate malware can result in the failure of on-line Comprehensive Protection (CP) in distributed systems, and place the system in an unsafe state which is difficult to recover from. There lacks an effective scheme to defend against this extreme attack. In this paper, based on the Two-layer Protection and Cooperative Recovery (TPCRS) mechanism, we propose an efficient survivable scheme against malware attacks in distributed systems. The basic strategy is to deploy an Emergency Response/Recovery (ER) agent at each node to recognize the state of the system whenever the CP fails, and to carry out cooperative security among multiple nodes so that the infected nodes can be rapidly recovered. Furthermore, a Preventive Maintenance (PM) model is adopted to enhance the reliability of the distributed system. Simulation results demonstrate the practicality and efficiency of the proposed schemes.

The popularity of delay-sensitive applications has been rapidly evolving in recent years. However, the current Internet is not well designed to support the delivery of such traffic. The SRD (Stochastic Rate-Delay) services proposed in this paper empower a user to choose either a higher transmission rate or a low queuing delay at a congested network link. While average low delay remains guaranteed, the delay constraint is allowed to violate occasionally. The implementation enforces the intended service differentiation via link scheduling and sizing of the buffer. We build a model using stochastic network calculus to analyze the SRD services proposal and shed light on its fundamental characteristics quantitatively.

In Cloud computing, users with different service requirements often need to negotiate with service provider via Service Level Agreement (SLA). The unique pay-as-you-go billing way in Cloud computing challenges resource provisioning for service providers. In this paper, based on the Dirichlet multinomial model, we present an efficient reputation-based QoS provisioning scheme, which can minimize the cost of computing resources, while satisfying the desired QoS metrics. Unlike the previous counterparts, we consider the statistical probability of the response time as a practical metric rather than the typical mean response time. Numerical results show the efficiency and effectiveness of the proposed scheme.

Data aggregation is an main method to conserve energy in wireless sensor network (WSN). Prior work on data aggregation protocols are generally based on static routing schemes, such as tree-based, cluster-based or chain-based routing schemes. Although they can save energy to some extent, in dynamic scenarios where the source nodes are changing frequently, they will not only incur high overhead to continuously reconstruct the routing but also can not reduce the communication overhead effectively. Our work aims to design an effective data aggregation mechanism supported by dynamic routing (DASDR) which can adapt to different scenarios without incurring much overhead. Enlightened by the concept of potential field in the discipline of physics, the dynamic routing in DASDR is designed based on two potential fields: depth potential field which guarantees packets reaching the sink at last and queue potential field which makes packets more spatially convergent and thus data aggregation will be more efficient. Simulation results show that DASDR is more effective in energy savings as well as scales well with regard to the network size.

The handover mechanism in wireless networks has been intensively investigated in the past years. The traditional solutions are to customize various protocols in different layers to provide uninterrupted communication, which is particularly important for real time traffic. In this paper, we intend to exploit silence gap, inherently existing in realtime traffic, to improve handover performance. The proposed strategy can be appended to most of handover mechanisms without extra overhead. We theoretically analyze the relationship between gap distribution and handover performance under the assumption of different statistical distribution of gaps on a case-by-case basis. Subsequently, we insert an additional module into the WiMAX network and conduct the simulations using real voice traces. The results confirm the analytical conclusions, showing that the gap-exploiting approach can obtain significant gain in terms of packet loss particularly in low-speed mobile environment.

In this paper, we investigate the frequency-domain packet scheduling (FDPS) problem for 3GPP LTE Uplink (UL). Instead of studying a specific scheduling policy, we provide a unified approach to tackle this issue. First we formalize a general LTE UL FDPS problem which is suitable for various scheduling policies. Then we prove that the problem is MAX SNP-hard, which implies that approximation algorithms with constant approximation ratios are the best that we can hope for. Therefore we design two approximation algorithms, both of which have polynomial runtime. Subsequently, we analyze the two algorithms and find their approximation ratios. The first algorithm is easy to follow, since it is based on a simple greedy method. The second one is based on the local ratio technique and it can approximately solve the LTE UL FDPS problem with a approximation ratio of 2.

Though providing an intrinsic secrecy, network coding is still vulnerable to eavesdropping attacks, by which an adversary may compromise the confidentiality of message content. Existing studies mainly deal with eavesdroppers that can intercept a lim-ited number of packets. However, real scenarios often consist of more capable adversaries, e.g., global eavesdroppers, which can defeat these techniques. In this paper, we propose P-Coding, a novel security scheme against eavesdropping attacks in network coding. With the lightweight permutation encryption performed on each message and its coding vector, P-Coding can efficiently thwart global eavesdroppers in a transparent way. Moreover, P-Coding is also featured in scalability and robustness, which enable it to be integrated into practical network coded systems. Security analysis and simulation results demonstrate the efficacy and efficiency of the P-Coding scheme.

Energy efficient communication is a key requirement of energy-constrained underwater sensor networks (UWSNs). In this paper, we show that the cooperative diversity, which is conventionally utilized to improve reliability in UWSNs, can be employed to reduce energy consumption and preserve a reasonable level of data reliability and communication delay. We first elucidate in what circumstances the cooperative diversity saves energy compared to the non-cooperative diversity. We show that this largely depends on parameters such as distance between the source and the destination node, the location of potential partner node, and the requirements of reliability and communication delay. Second, we propose a simple but effective cooperation scheme to take advantage of the cooperative diversity. The cooperation diversity can achieve a near-optimal energy saving in some circumstances, and it is no worse than the non-cooperative diversity in all cases. Our work provides instructive theoretical guidelines for designing practical UWSNs.

The Wireless Sensor Network (WSN) is embracing an increasing number of real-time applications subject to strict delay constraints. Utilizing the methodology of potential field in physics, we present an effective way to address the challenges in real-time transmission. We propose the Potential based Real-Time Routing (PRTR) protocol, which provides real-time transmission using multi-path routing algorithm based on a composite potential field. PRTR features a delay-minimized real-time routing as well as alleviating congestion simultaneously.

Data aggregation has been widely recognized as an efficient method to reduce energy consumption in wireless sensor networks, which can support a wide range of applications such as monitoring temperature, humidity, level, speed etc. The data sampled by the same kind of sensors have much redundancy since the sensor nodes are usually quite dense in wireless sensor networks. To make data aggregation more efficient, the packets with the same attribute, defined as the identifier of different data sampled by different sensors such as temperature sensors, humidity sensors, etc., should be gathered together. However, to the best of our knowledge, present data aggregation mechanisms did not take packet attribute into consideration. In this paper, we take the lead in introducing packet attribute into data aggregation and propose an Attribute-aware Data Aggregation mechanism using Dynamic Routing (ADADR) which can make packets with the same attribute convergent as much as possible and therefore improve the efficiency of data aggregation. This goal cannot be achieved by present static routing schemes employed in most of data aggregation mechanisms since they construct routes before transmitting the sampled data and thus can not dynamically forward packets in response to the variation of packets at intermediate nodes. Hence, we present a potential-based dynamic routing scheme which employs the concept of potential in physics and pheromone in ant colony to achieve our goal. The results of simulations in series of scenarios show that ADADR indeed conserve energy by reducing the average number of transmissions each packet needs to reach the sink and is scalable with regard to the network size.

Abstract Multipath routing can adapt to traffic changes, increase reliability and enhance the Quality of Service support in communication networks. This routing algorithm has been recognized as one of the salient features in MobileAd hocNetworks (MANETs). However, existing multipath routing protocols are often practically infeasible due to its security venerability if they suffer from attacks in MANETs, such as repudiation attacks, Denial of Service attacks. In this paper we propose a novel secure multipath routing protocol, referred to as SMRP, and investigate its feasibility and performance. SMRP applies a new heuristic algorithm increasing the number of disjoint paths and a smart authentication mechanism to enhance the security against the attacks in MANETs. The performance results from extensive analysis and experiments show that SMRP can efficiently enhance the security in MANETs while preserving the low overhead of computing and communication. Copyright © 2009 John Wiley & Sons, Ltd.

Abstract In this paper, we propose a novel security scheme with key recovery capability for mobile communications. The proposed key recovery mechanism offers a “backdoor” for an authorized agency to monitor suspected communications while protecting legal users from unauthorized disclosure of their data privacy. All the features form a unitary security scheme with monitoring service. The performance analysis shows that our scheme has a low‐computational complexity and it can be practically deployed on contemporary mobile devices. Copyright © 2009 John Wiley & Sons, Ltd.

We present the design and deployment experiences with LiveSky , a commercial hybrid CDN-P2P live streaming system, which inherits the best of both CDN and P2P. We address several key challenges, including: 1) ease of integration with existing CDN infrastructure, 2) dynamic resource scaling while guaranteeing quality-of-service, 3) providing good user experience, ensuring network friendliness and upload fairness. LiveSky has been used for several large-scale live streaming events in China. Our evaluation results from real-world indicate that such a hybrid CDN-P2P system provides quality and performance comparable to a CDN and effectively scales the system capacity.

Seamless handover is one of the most attractive research fields in B3G systems. Many mechanisms are proposed to provide certain QoS guarantees in handovers of mobile systems, which would also introduce new threats, such as DoS and DDOS attacks. In this paper, we extend a cookie-based scheme to protect systems from DoS and DDoS attacks. We also adopt a novel queuing network model to analyze our scheme by estimating two essential metrics, i.e. the mean total response time and the mean queue length of MAP. Numerical results indicate that our mechanism works better than the traditional cookie-based scheme and it could effectively help networks defend against abnormal attacks in the handover process.

In P2P file-sharing applications, distributed virtual payment mechanism is designed to encourage resource sharing among peers and thus restrain free-riding behaviors. However, it does not provide any protection on the security of the transaction process and the quality of the trading contents. We design a fair transaction mechanism for P2P file-sharing applications, in which a trusted third party is constructed and used to guarantee the atomic operation of the file-money exchange, in virtue of the property of distributed payment mechanism. The trading file is signed with the seller's private key, which can be used as proof in case of dissension. Performance analysis indicates that the costs of fair transaction mechanism are limited in both trading session latency and overhead to the system.

An emerging problem facing future high performance multi-core processors is transient faults caused by radiation, noise and other factors. These faults will likely make future multi-core processors less reliable as chip features shrink and the number of cores increase. To address this problem, we propose a new and practical systems approach of managing and allocating reliability according to software process requirements. The asymmetric multi-core architecture is based on cores with differing reliabilities. Critical and non-critical software components are identified and matched with the higher reliability cores. We show that by using asymmetrically reliable cores the overall system failure rate can be reduced by several times when critical processes can be isolated and executed by higher reliability cores, while offering the same or better overall performance, power utilization and chip area as symmetric cores.

BitTorrent is one of the most popular P2P file sharing systems. However, chunk-based file sharing mode makes it difficult to detect content pollution and prevent pollution dissemination during downloading process. In this paper, we propose an early warning scheme against pollution dissemination for BitTorrent. Our idea is to build an early cooperative warning mechanism and rapidly spread alert message among peers in the swarm when pollution is detected at the early stage, which is called "early warning, quickly reacting". The performance evaluation based on fluid model shows the necessity and effectiveness of our scheme, which effectively reduces the traffic abusement and restricts pollution dissemination in BitTorrent-like P2P networks. Another advantage of our solution is that it can handle cheating behaviors made by malicious or unconscious peers, which shows the robustness of our solution.

In this paper, we propose hierarchical Stochastic Game Nets, and use it to model and analyze the security issues in online banking system. Firstly, the definition and modeling algorithm of hierarchical Stochastic Game Nets are given. In which, some theorems are proved. Then we apply hierarchical Stochastic Game Nets to describe the attack and defense course in the online banking. Finally we analyze the attack time and attack probability in the online banking quantitatively based on the model successfully.

Underwater communication is a challenging topic due to its singular channel characteristics. Most protocols used in terrestrial wireless communication can not be directly applied in the underwater world. In this paper, we focus on the issue of energy efficient transmission in underwater sensor networks (UWSNs) and analyze this problem in a rigorous and theoretical way. We formalize an optimization problem which aims to minimize energy consumption and simultaneously accounts for other performance metrics such as the data reliability and the communication delay. With the help of Karush-Kuhn-Tucker conditions (KKT conditions), we derive a simple and explicit, but nevertheless accurate, approximate solution under reasonable assumptions. This approximate solution provides theoretical guidelines for designing durable and reliable UWSNs. Our result also shows that reliability and communication delay are crucial factors to the energy consumption for transmission.

The peer-to-peer (P2P) live video streaming system has been demonstrated to have great potential in the public Internet; the large-scale deployment of such systems, however, critically relies on how effective they can deal with the high dynamics encountered, in particular during flash crowd. The rationale behind is that the scaling in P2P live video streaming systems is heavily determined by the timing requirement that streaming applications demand. In this paper, we present an analytical and experimental study on the inherent relationship between the time constraint and the system scale. We develop a generic model for P2P live video streaming that focuses on the peer joining process during flash crowd. We first illustrate that the simple notion of "demand vs. supply" model is insufficient in describing the system scale. By computing the peer start-up time distribution, we demonstrate that the scale is affected by several key factors, especially the peer uploading capacity and the initial system size. We further show the scale is essentially bounded by the timing requirement and the system's capability to accommodate flash crowd is subject to a maximum limit.

In this paper, we propose a novel modeling method, Stochastic Game Nets (SGN), and use it to model and analyze the security issues in enterprise networks. Firstly, the definition and modeling algorithm of Stochastic Game Nets are given. And then we apply the Stochastic Game Nets method to describe the attack and defense course in the enterprise networks successfully, and find a Nash equilibrium. Finally we analyze the confidentiality and integrity of the enterprise network quantificationally based on the model. The method can also be applied to other areas with respect to a game.

Remote desktop access is commonly used to remotely access a host in enterprise networks; however it also brings in security problems in supervision and auditing. In this paper, a novel proxy-based security audit system is designed and implemented in order to ensure security supervising and auditing remote desktop access. Our system effectively monitors all the accessing sessions of RDP, VNC, and X-window, and provides replay function by recording all the graphics operations from users. Our performance test result shows that for most of small business, just one proxy server is enough to handle all the routine auditing workload of RDP sessions.

P2P-based video-on-demand (P2P-VoD) streaming service has recently emerged as a new paradigm of Internet application. Unlike streaming live content, P2P-VoD system require each user to contribute a small amount of storage since it has less synchrony in the users sharing video content. At the same time, new mechanisms for peer service scheduling are carefully designed. On briefly describing the architectural design based on the real system deployed by PPLive, we develop a stochastic model that seeks to expose the essential behavior of the PPLive P2P-VoD system. The performance evaluation followed shows that the system design of PPLive P2P-VoD system could guarantee good viewing quality, and sheds insight on the fundamental characteristics and limitations of the system quantitatively. Such theoretical analysis on P2P-VoD could help to improve the viewing quality and make such system more robust and scalable.

Links of an end-to-end long lived TCP connection may provide bandwidth with significant variance. In this work, we model and study the effects of variable bandwidth on TCP throughput, taking into account various influencing factors such as random loss of links, buffer size and characteristics of the variable bandwidth in the bottleneck link. Result shows that the variance of bandwidth can severely deteriorate TCP throughput, even making it less than one thirds of the one without bandwidth variance in many cases and arbitrarily low if situations are bad enough, and that under the circumstance of variable bandwidth, a buffer size larger than the traditional recommended bandwidth delay product can greatly improve the throughput. Under the circumstance of variable bandwidth, our model can accurately model the TCP throughput, with an average error around 5%, and a maximum error less than 15%, while traditional formula based TCP throughput prediction can be significantly inaccurate, even with an error larger than 200%.

The 2008 Beijing Olympics was an interesting event from a VoD perspective because it involved near real-time video delivery at massive scales over multiple days of a high-profile event. We present some measurement-driven insights into this event through a unique dataset obtained from ChinaCache, the largest CDN in China. The dataset is unique in three respects. First, it gives a "white-box" view into user access patterns which would otherwise be impossible. Second, since the CDN serves different content providers, it allows to compare and contrast the effects of different presentation models on end users. Third, the nature of the content itself is vastly different from traditional VoD systems in terms of the real-time and event-driven nature, which gives rise to unique effects. The dataset allows us to investigate a wide range of interesting issues: (1) how the live nature of the events causes differences in access patterns compared to traditional VoD and User-Generated Content (UGC) systems, (2) how the presentation models affect user behavior, and (3) flash-crowd phenomena. Based on these observations, we discuss implications for future live VoD systems.

With the ever growing network traffic, capacity of paths in the networks nowadays has become increasingly easy to saturate. This brings new challenge to TCP throughput prediction. The main problem is loss rate and RTT during the TCP flow are often expected as inputs for the throughput models used in the prediction; however, only loss rate and RTT before the flow are available and are used instead. If the flow itself causes significant changes in loss rate and RTT, e.g., when the TCP flow attempts to saturate the underlying available bandwidth, the prediction error can be unacceptably large. Though new prediction approaches are being proposed, they basic require record of previous TCP transfers and are applicable only when TCP transfers are performed repeatedly, which limits their application. In this work, by properly using a measurement of the underlying available bandwidth, we develop an analytical TCP throughput model which can explicitly capture changes in loss rate and RTT caused by the target TCP flow and hence, can largely improve the prediction accuracy by making the prediction aware of capacity saturation of paths while at the same does not require any history record of previous TCP transfers as current newly proposed works do. Results show that when the changes in loss rate and RTT are large, the errors by traditional models can be as large as over 200%, whereas the error by the proposed model is usually very small, e.g., with the average error below 10% and the maximum error below 20% for general settings, and is bounded by the measurement error of available bandwidth in the worse case; when the changes in loss rate and RTT are small, even a very rough estimation of available bandwidth, e.g., with an error of around 50%, can lead to very accurate prediction by the proposed model.

Future network systems and embedded infrastructure devices in ubiquitous environments will need to consume low power and process large amounts of network packet traffic. In order to meet necessary high processing efficiency requirements, future processors will have many heterogeneous cores with reduced reliability due to low voltage, small transistor sizes, semiconductor wearout, and environmental factors such as noise and interference. It will be necessary for multi-core network infrastructure software to mitigate transient hardware faults to maintain acceptable system reliability. Applications such as packet processing can benefit from the reliability versus performance tradeoff. We propose a model based on stochastic reward nets to evaluate the performance vs. reliability tradeoff of unreliable embedded multi-core network processors, and apply this model to a multi-core packet processing application.

The virtual infrastructure has become more and more popular in the grid and cloud computing. With the aggrandizement scale, the management of the resources in virtual infrastructure faces a great technical challenge. To support the upper services effectively, it raises higher requirements for the performance, fault-tolerance and scalability of virtual infrastructure management systems. In this paper, we study the performance, fault-tolerance and scalability of virtual infrastructure management systems with the three typical structures, including centralized, hierarchical and peer-to-peer structures. We give the mathematical definition of the evaluation metrics and give detailed quantitative analysis, and then get several useful conclusions for enhancing the performance, fault-tolerance and scalability, based on the quantitative analysis. We believe that the results of this work will help system architects make informed choices for building virtual infrastructure.

IVForensic is a digital forensics service platform for Internet videos, with the aim of revealing illegal videos and preventing them from spreading over the Internet. It a) implements a flexible, secure and scalable architecture for large-scale online monitoring, b) provides an effective and efficient forensic countermeasure for widely-sourced Internet videos, c) guarantees good end-user experience such as flexible settings, simple operations and low startup latency. The results of performance evaluation using data obtained from real-world deployments demonstrate the effectiveness of the platform.

We present our design and deployment experiences with LiveSky, a commercially deployed hybrid CDN-P2P live streaming system. CDNs and P2P systems are the common techniques used for live streaming, each having its own set of advantages and disadvantages. LiveSky inherits the best of both worlds: the quality control and reliability of a CDN and the inherent scalability of a P2P system. We address several key challenges in the system design and implementation including (a) dynamic resource scaling while guaranteeing stream quality, (b) providing low startup latency, (c) ease of integration with existing CDN infrastructure, and (d) ensuring network-friendliness and upload fairness in the P2P operation. LiveSky has been commercially deployed and used for several large-scale live streaming events serving more than ten million users in China. We evaluate the performance of LiveSky using data from these real-world deployments. Our results indicate that such a hybrid CDN-P2P system provides quality and user performance comparable to a CDN and effectively scales the system capacity when the user volume exceeds the CDN capacity.

To weaken the selfish behavior of nodes in mobile ad hoc networks, many payment-based incentive schemes have been proposed recently, yet it is still far from achieving the expected efficiency to encourage node cooperation. In these schemes, source node selects a Least Cost Routing (LCP) for data transmission according to the forwarding cost reported by intermediate nodes and rewards them with some virtual money before or after successful packet forwarding. However, as a result of information asymmetry between source and relay nodes, nodes on LCP may degrade their efforts promised in the previous routing discovery stage if there is no enough motivation for them to work hard, which exercises a negative influence on the forwarding efficiency of LCP schemes. Therefore, the actual transmission efforts of intermediate nodes must be considered by the source node in the processes of route selecting and packet forwarding. In this paper, with adoption of principal-agent theory of economics, we propose a novel LCP scheme (ELCP) based on the intermediate nodes' effort to stimulate nodes cooperation, in which both source and relay nodes can maximize their profits and ensure routing efficiency simultaneously.

Considering the constraint brought by mobility and resources, it is important for routing protocols to efficiently deliver data in Intermittently Connected Mobile Network (ICMN). Different from previous works that use the knowledge of previous encounters to predict the future contact, we propose a storagefriendly REgioN-bAsed protocol, namely, RENA, in this paper. Instead of using temporal information, RENA builds routing tables based on regional movement history, which avoids excessive storage for tracking encounter history. We validate the generality of RENA through time-variant community mobility model with parameters extracted from the MIT WLAN trace, and the vehicular network based on 8 bus routes of the city of Helsinki. The comprehensive simulation results show that RENA is not only storage-friendly but also more efficient than the epidemic routing, the restricted replication protocol SNW and the encounter-based protocol RAPID under various conditions.

Multiple transmission rates are supported in the current 802.11 WLANs, which allows stations to exploit different rates in an adaptive manner to cope with the variability of wireless channels and achieve the higher system throughput. Many efforts have been made at rate adaptation in the literature. The design of rate adaptation algorithms needs to take four basic issues into account. In this paper, by properly addressing the four issues, we present a novel rate adaptation algorithm, idle detection based optimal throughput rate adaptation (ITRA). We apply a comprehensive approach to designing the rate adaptation mechanism and attempt to maximize the overall system throughput. ITRA is furnished with two instructive features. First, ITRA modifies the conventional exponential backoff rule to a constant one. With the help of constant contention window (CW), ITRA can discriminate collisions from channel errors, and does not need RTS/CTS handshakes which are adopted by many existing works. We derive an explicit relation between the throughput and the CW size, and choose the CW size to optimize the throughput as well as improve the fairness. Secondly, ITRA directly estimates the current network throughput and changes transmission rate according to the estimation. Since the fundamental purpose of rate adaptation is to improve the network throughput, using the throughput as the metric is more straightforward than applying indirect criteria like frame transmission statistics or PHY metrics. We evaluate our proposed scheme by simulation, and the result shows that ITRA achieves satisfactory performance.

Peer-to-peer (P2P) paradigm has provided a disruptive market opportunity to define cost-effective multimedia streaming services, but at the same time network-oblivious P2P applications have been posing substantial technical and social challenges on network efficiency, operator economics and user performance. While end users are concerned with quality upgrade, Internet content provider (ICP) considers more on service scale and Internet service provider (ISP) focuses on operating cost. In taming P2P for a more friendly large-scale application, this paper provides a framework of evaluating the P2P media streaming application performance from perspectives of all entities involved, that is ISP, ICP and end users. Three-level performance metrics are defined, essential concerns of each party are theoretically quantified and bottlenecks in affecting quality service are identified. In handling tussles between P2P performance against ISP traffic, system scale against cost and user QoS against Security, the authors present proposals in defining an unprecedented friendly and cost-effective P2P streaming application to achieve the ideal philosophy of ‘more users=better performance+lower cost’. Based on the explorations in academy and industry, the authors envision that a large-scale streaming system will be built with a synergy of P2P and content distribution networks (CDN), and explore the feasibility of a general peer–server–peer (PSP) structure on the basis of our evaluation framework. With our analytical study and industrial deployment, this paper captures a certain essence of deploying large-scale P2P streaming application from a commercial and realistic point of view and suggests many avenues for addressing the emerging tensions between P2P application and network operators.

In this paper, we propose a robust and efficient signature scheme for vehicle-to-infrastructure communications, called binary authentication tree (BAT). The BAT scheme can effectively eliminate the performance bottleneck when verifying a mass of signatures within a rigorously required interval, even under adverse scenarios with bogus messages. Given any n received messages with k ges 1 bogus ones, the computation cost to verify all these messages only requires approximately (k + 1) ldr log(n/k) + 4k - 2 time-consuming pairing operations. The BAT scheme can also be gracefully transplanted to other similar batch signature schemes. In addition, it offers the other conventional security for vehicular networks, such as identity privacy and traceability. Theoretical analysis and simulation results demonstrate the validity and practicality of the BAT scheme.

In this paper, performance of wireless opportunistic schedulers in multiuser systems is studied under a dynamic data arrival setting. Different from the previous studies which mostly focus on the network stability and the worst case scenarios, we emphasize on the average performance of wireless opportunistic schedulers. We first develop a framework based on Markov queueing model and then analyze it by applying decomposition and iteration techniques in the stochastic Petri nets (SPN). Since the size of the state space in our analytical model is small, the proposed framework shows an improved efficiency in computational complexity. Based on the established analytical model, performance of both opportunistic and non-opportunistic schedulers are studied and compared in terms of average queue length, mean throughput, average delay and dropping probability. Analytical results demonstrate that the multiuser diversity effect as observed in the infinite backlog scenario is only valid in the heavy traffic regime. The performance of the opportunistic schedulers in the light traffic regime is worse than that of the non-opportunistic round-robin scheduler, and becomes worse especially with the increase of the number of users. Simulations are also performed to verify the accuracy of the analytical results.

Recently efficient and scalable live video streaming system over the Internet has become a hot topic. In order to improve the system performance metrics, such as startup delay, source-to-end delay, playback continuity and scalability, many previous works developed two successful cases of content distribution network (CDN) and peer-to-peer (P2P) Network for the design of large-scale live video streaming systems, but no single one has yet delivered both the scale and service quality. To combine the advantages of CDN and P2P network has been considered as a feasible orientation for large-scale video stream delivering. In this paper, we propose a peer-assisted content distribution network, i.e. PACDN, which borrows the mesh-based P2P ideas into the traditional CDN to enhance the performance and scalability. The basic features of PACDN include: 1) To meet the real time requirement of live video stream service, i.e. to ensure that the video stream could be continuously and stably delivered from the source to each edge server for offering good QoS to different regions clients, the placement edge servers and source streaming server(s) build a hierarchical multi-tree based and in-hierarchy peer-assisted overlay, which is optimized according to the knowledge of underlying physical topology. This scheme in the design is called "server side peer-assisted". 2) To enhance the system scalability and reduce the deployment cost, clients and edge servers construct a Client/Server based and P2P network assisted overlay with the increasing of viewers, which is called "client side peer-assisted" in this design. We compare the inner performance of PACDN with existing approaches based on comprehensive simulations and analysis. The results show that our proposed design outperforms previous systems in the service quality and scalability. PACDN has been implemented as an Internet live video streaming service and it was successfully deployed for broadcasting many important live programs in China in 2007. The industrial experiences prove that this design is scalable and reliable. We believe that the wide deployment of PACDN and its further development will soon benefit many more Internet users.

Grid services mismatching, resulted from non-compatible interfaces, protocols or behaviors, has been a barrier to realize services composition for coordination of distributed application. So it’s important to check and verify service composition to guarantee smooth interaction among services from different grid domain correctly. Pi-calculus, characterized by name exchanging of different processes, can be seen as a valid theoretical tool to model grid service behavior. In this paper, two typical service interaction patterns are established, based on which some grid service contexts are defined and exemplified by application cases. Depending on the theoretical analysis, Pi-calculus based Grid Service Composition Verification algorithm, PGSCV, is proposed for Verifying the grid service composition and proved available and efficient by experimental results. As a conclusion the future research work is also discussed.

In this paper, we propose a robust and efficient signature scheme for vehicle-to-infrastructure communications, which can effectively eliminate the performance bottleneck when verifying a mass of signatures within a rigorously required interval, even under adverse scenarios with bogus messages. In addition, our scheme offers the other conventional security features for vehicular networks, such as identity privacy and traceability.

The mobility of underwater sensor nodes makes the network topology inconveniently controlled and slowly changed. Thus, in order to enable underwater sensor networks to work more effectively, it is necessary for us to periodically detect the coverage rate and redeploy nodes to non-coverage areas. In this paper, we take the lead in introducing the redeployment issue in underwater sensor networks. In our opinion, the key point of the redeployment issue is coverage. For this special coverage topic, we first propose a coverage rate definition scheme. Then along with the definitions, two redeployment algorithms are introduced, of which one is based on adding new nodes while the other one is by the means of moving redundant ones. By modeling the mobility behavior of underwater nodes with three-dimensional random walks, we employ simulation experiments to verify our ideas, the results of which show the importance of redeployment in the underwater environment.

Most previous models about wireless channels are mainly adopted to obtain average packet error rates or to generate artificial network traces. However, when we combine packet group transmission with error correcting mechanisms, the steady packet error rate (PER) is not accurate enough to depict the short-term error event. In this paper, we propose a Markov chain model for group transmission to indicate influences of group length N and initial channel state on transmission reliability. Based on the model, we prove that the difference between steady PER and packet error rate within a group (PERG) is O(1/N), which can be used to estimate group length under a certain error rate constraint. Finally, we apply the model to compare the multipath transmission with the single-path transmission, and investigate an extreme case where the multipath way is less reliable than the single-path way.

The goal of a video conferencing system is to deliver multimedia data to the conference participants efficiently and securely. To meet the requirement of a video conferencing system over the internet, many issues have to be addressed, such as security, scalability and heterogeneity. In this paper, we propose a secure and scalable video conferencing system named VCNF (Video Conference Network Foundation), to support large number of conferencing groups simultaneously with each group has limited members. We use a P2PSIP overlay to store and lookup the user and group contact information. SIP protocol is used to setup media sessions and a new kind of session-- VPN session. We adopt a layered data transfer mechanism which traits different kinds of media-streams as of different importance level. We have implemented the system and analyzed its performance and security. An Internet video-based game based on our platform has also been deployed over the Internet.

In order to overcome the limitations in traditional access control models such as identity-based access control and meet the access requirements in distributed systems, we propose a Trust and Context based Access Control model called TCAC, it extends the traditional RBAC (role based access control) model with the notion of trust and context. Role assignment in TCAC is based on the trustworthiness and context information of users. The TCAC model is flexible, scalable, and well suitable for the dynamic and distributed systems. Then we provide a trust evaluation mechanism based on the local and global reputation to compute the trust value of a user in distributed system, which can avoid malicious nodes behave correctly in order to get the highest possible trust value. Finally an implementation framework of the access control system based on TCAC is described.

With the popularity of BitTorrent, improving its performance has been an active research area. Super-seeding, a special upload policy for initial seeds, improves the efficiency in producing multiple seeds and reduces the uploading cost of the initial seeders. However, the overall benefit of super seeding remains a question. In this paper, we conduct an experimental study over the performance of super-seeding scheme of BitTornado. We attempt to answer the following questions: whether and how much super-seeding saves uploading cost, whether the download time of all peers is decreased by super-seeding, and in which scenario super-seeding performs worse. With varying seed bandwidth and peer behavior, we analyze the overall download time and upload cost of super seeding scheme during random period tests over 250 widely distributed PlanetLab nodes. The results show that benefits of super-seeding depend highly on the upload bandwidth of the initial seeds and the behavior of individual peers. Our work not only provides reference for the potential adoption of super-seeding in BitTorrent, but also much insights for the balance of enhancing Quality of Experience (QoE) and saving cost for a large-scale BitTorrent-like P2P commercial application.

This paper studies the flow-level performance of a special family of weight-based opportunistic scheduler using discriminatory processor sharing (DPS) model. It is known that this family of schedulers can achieve any feasible long- term throughput vectors by the variation of its weights. The optimal weight setting problem under DPS model is studied by decomposing it into two subproblems. In each subproblem, a guideline as to how the weight should be chosen is derived. The usage of these two guidelines in analyzing the original problem is discussed via theoretical and simulation results.

As the most important issue in wireless sensor networks, power saving is catching researchers' great attentions all the time. Among several power saving strategies, one of the best methods is to make unused components inactive whenever possible, i.e. applying sleep scheduling schemes to sensors. In this paper, by analyzing and concluding existing works, we propose four sleep scheduling schemes (ACAA, SRAA, SAA and NCAA) for different kinds of application environments, then analyze each of them by stochastic petri net (SPN). We can easily get the average power consumptions and event delays of sensor nodes by using the steady state probability matrix of the SPN models. Moreover, the numeric results show that this concise graphic analysis method is suitable for analyzing sleep scheduling schemes.

In this paper, by establishing the probability models, we systematically and comprehensively analyze the roles of the packet retransmission, the block retransmission, and the erasure coding in the reliable transport of wireless sensor networks. And as well as the three kinds of packet level schemes, we also consider the effect of two kinds of bit level strategies, CRC and FEC. At last, based on the numeric results, the appropriate schemes for different BER (high, medium, and low) are determined, and we also present some principles that reveal profound insights in designing reliable protocols and mechanisms in wireless sensor networks.

Since TCP congestion control is ill-suited for high speed networks, designing a replacement for TCP has become a challenge. To address this problem, we extend the population ecology theory to design a novel congestion control algorithm. We treat the network flows as the species in nature, the throughput of the flows as the population number, and the bottleneck bandwidth as the food resources. Then we use the key idea of constructing population ecology models to develop a novel congestion control model, and implement the corresponding end-to-end transport protocol through measurement, which called Population Ecology TCP (PE-TCP). The theoretical analysis and simulation results validate that PE-TCP achieves high utilization, fast convergence, fair bandwidth allocation, and near-zero packet drops. These qualities are desirable for high speed networks.

P2P applications suffer from free-riding. In economics terminology, free-riding is the rational behavior of the participants. So it's feasible to use game theory to analyze this problem and design countermeasures. Tit-For-Tat is a simple and efficient equilibrium strategy in repeated game environments. In this paper, we construct a game model in P2P environments and deduce the constraint under which the strict tit-for-tat is an equilibrium strategy. We then improve and adapt the tit-for-tat strategy to the dynamic property in P2P networks, and deduce the constraint under which it is still an equilibrium strategy. Finally we study through simulations the performance improvement of the enhanced tit-for-tat and give suggestion of how to choose proper system parameters under different network conditions.

The peer-to-peer (P2P) based video streaming has emerged as a promising solution for Internet video distribution. Leveraging the resource available at end users, this approach poses great potential to scale in the Internet. We have now seen the commercial P2P streaming systems that are orders of magnitude larger than the earlier academic systems. We believe understanding its basic principles and limitations are important in the design of future systems. The Coolstreaming, first released in summer 2004, arguably represented the first successful large-scale P2P live streaming system. Since then, the system has been significantly modified and commercially launched. This paper takes an inside look at the new Coolstreaming system by exposing its design options and rationale behind them, and examines their implications on streaming performance. Specifically, by leveraging a large set of traces obtained from recent live event broadcast and extensive simulations, we study the workload characteristics, system dynamics, and impact from a variety of system parameters. We demonstrate that there is a highly skewed resource distribution in such systems and the performance is mostly affected by the system dynamics. In addition, we show that there are inherent correlations and fundamental trade-off among different system parameters, which can be further explored to enhance the system performance.

As a potentially competitive technique, erasure coding has been employed in wireless sensor networks (WSNs) to enhance transmission reliability. In this paper, to design a practical and efficient redundancy mechanism in WSNs, we firstly provide a theoretical study of packet delivery probability and average energy consumption for retransmission and redundancy mechanisms. The theoretical results indicate that in WSNs, the adaptive redundancy coding mechanism is more energy efficient than retransmission while keeping the same level of reliability in most scenarios. Then based on the mapping table and two basic design principles obtained from the theoretical analysis, we propose a reliable transport protocol ARRTP which combines the adaptive redundancy mechanism and partial retransmission. The simulation and trace-driven results both verify that when the loss probability varies from low to high, our protocol provides reliability with comparably lower energy consumption. Furthermore, compared with fixed redundancy degrees, the robustness of the adaptive mechanism are also evaluated.

Many P2P applications necessitate statistics aggregate computation of certain information among all individual peers. In contrast to methods of constructing aggregation tree, centralized computing and flooding, gossip-based mechanism has the advantages of good robustness and moderate communication and computing costs. Most algorithms of this type perform aggregate computation recursively on successive time slots called rounds. They require rounds to be globally synchronous on all the nodes, which complicates the algorithm realization. To eliminate the requirement for global round synchronization, we propose a loosely synchronized algorithm to compute global statistic average based on random event triggering mechanism, and prove that the convergence time is O(logN)tau. We then propose a robust method to estimate the number of peers in the network based on this algorithm. Finally, a framework is proposed to generalize the computation of SUM, AVG, MAX, MIN, and CNT(N).

In this paper, the performance of opportunistic scheduling in orthogonal frequency division multiplexing (OFDM) networks is studied. An analytical model is developed to extend the multi-class processor-sharing model in single-carrier networks to multi-carrier OFDM networks, where the total service rate depends on the total number of users. Based on the analytical model, the scheduling gains in both OFDM-TDMA (time division multiple access) and OFDMA (orthogonal frequency division multiple access) networks are evaluated. Different from previous works in this area, we focus on the scheduling performance at the flow level and consider a dynamic network setting with random finite-size service demands. Simulations are performed to verify the analytical results.

The congestion problem in wireless sensor networks (WSNs) is quite different from that in traditional networks. Most current congestion control algorithms try to alleviate the congestion by reducing the rate at which the source nodes inject packets into the network. However, this traffic control scheme always decreases the throughput so as to violate fidelity level required by the application. In this paper, we present a solution that sufficiently exert the idle or under-loaded nodes to alleviate congestion and improve the overall throughput. To achieve this goal, a traffic-aware dynamic routing(TADR) algorithm is proposed to route packets around the congestion areas and scatter the excessive packets along multiple paths consisting of idle and under-loaded nodes. Enlightened by the concept of potential in common physics, our TADR algorithm is designed through constructing a mixed potential field using depth and normalized queue length to force the packets to steer clear of obstacles created by congestion and eventually move towards the sink. The simulation results show that our solution achieves its objectives and improves the overall throughput by around 370% as compared to the benchmark routing protocol. Furthermore, our TADR has low overhead suitable for large scale dense sensor networks.

Underwater communications is a very challenging topic due to its singular channel characteristics. Most protocols used in terrestrial wireless communications can not be directly applied in the underwater world. A high bit error rate and low propagation delay make the design of reliable transport protocols especially awkward. In this paper, we first propose four schemes that combine forward error correction mechanisms at the bit and/or packet level to increase the reliability in a non-cooperative scenario. The broadcast property of the underwater environment allows us to extend them to a cooperative setting. Based on our analyses, we introduce ADELIN: an adaptive reliable transport protocol for underwater sensor networks. We suggest an architecture for implementation and compare our protocol to other schemes. We show that it succeeds in a better probability and energy tradeoff for both single- and multi-hop communications.

In this paper, we propose a communication-efficient re-keying scheme by using a polynomial-based efficient code method. Compared with the previous schemes, the re-keying cost is significantly reduced, since no extra re-keying message header is needed. In addition, the computation overhead is also lightweight since only 2logn hash operations are required for each re-keying. Therefore, the proposed scheme is more suitable for deploying in the group application scenarios with both high dynamic memberships and limited communication channel capacity.

In underwater sensor networks (UWSNs), high-delay acoustic channels are used for communications, which introduces new challenges for analyzing and choosing proper reliable transport mechanisms. In this paper, we investigate four key parameters (node distance, communication frequency, packet length and SNR) influencing the transport of UWSNs. Since treating all the four factors equally will make the analysis almost intractable, we propose a four-step analytical framework. In this framework, by optimizing both the communication frequency and packet length, we firstly show that the average energy consumption and the average communication delay of different transport schemes are only related to node distance and SNR. Then when considering practical scenarios, we further demonstrate that the scheme performances are mainly determined by SNR, which rather simplifies the analysis process. In addition, an important metric PEDP is proposed, which is only related to SNR but has the capability of evaluating the performance of transport schemes roundly and effectively. Finally, the numeric results offer us some profound insights for choosing proper transport schemes in UWSNs.

To effectively address the explosive growth of multimedia applications over the Internet, a large-scale media streaming system has to fully take into account the issues of security, quality of service (QoS), scalability, and heterogeneity. However, current streaming solutions do not address all these challenges simultaneously. To address this limitation, this paper proposes a secure and high-performance streaming system called TrustStream, which combines the best features of scalable coding, content distribution network (CDN) and peer-to-peer (P2P) networks to achieve unprecedented security, scalability, heterogeneity, and certain QoS simultaneously under a unified architecture. In this architecture, raw video is encoded into two layers, namely, the base layer, which contains the most critical media content and is transmitted through a CDN-featured single-source multi-receiver (S-M) P2P network to guarantee a minimal level of quality, and the enhancement layer, which is transmitted in a pure multisource multi-receiver (M-M) P2P framework to achieve maximum scalability and bandwidth utilization. Heterogeneity is therefore addressed by delivering only the layers that a receiver is able to manage. Security is provided by combining our key distribution mechanism and key-embedding scheme under our proposed S-M P2P topology. We have implemented TrustStream system over the Internet. Deployed by ChinaCache, the largest CDN provider in China, TrustStream has broadcasted several popular live video programs over the Internet. The experimental results demonstrate the advantages and effectiveness of our architecture and system.

In this paper, the flow-level performance of opportunistic scheduling in orthogonal frequency division multiplexing (OFDM) networks is studied. The analysis accounts for the applications with a dynamic number of competing flows, such as continuous transfers of file transport protocol (FTP) or web browsing sessions. An analytical model is developed to extend the multi-class processor-sharing model in single-carrier networks to multi-carrier OFDM networks, where the total service rate varies with the number of flows. Based on the analytical model, the scheduling gains in both OFDM-TDMA (time division multiple access) and OFDMA (orthogonal frequency division multiple access) networks are evaluated for low and moderate signal-to-noise ratio (SNR). Different from previous works, we focus on the scheduling performance at the flow level and consider a dynamic network setting with random sized service demands. Furthermore, we use stochastic comparison techniques to examine the effects of physical-layer characteristics, such as fading speed and channel frequency selectivity, on flow-level performance. Simulations are performed to verify the analytical results.

The various link adaptation techniques employed by High Speed Downlink Packet Access (HSDPA) in the third generation (3G) networks augment the bandwidth oscillation, which is identified as one of the most important factors resulting in the throughput deterioration of Transmission Control Protocol (TCP). In this paper, we firstly explain why the bandwidth oscillation degrades the TCP performance through a special simulation experiment. Subsequently, a split connection Window Adaptation TCP Proxy is proposed to improve the TCP throughput over HSDPA networks. In this solution, the built-in attributes of HSDAP system are sufficiently utilized. In order to effectively use the precious cellular link resources, the length of the queue connected with it is intentionally kept around the reference value through adjusting the sending window size of TCP proxy based on the dynamic values of varying bandwidth. A discrete-time stochastic state space model is formulated to analyze the system stability. The validity of enhanced scheme is verified through simulation experiments. The performance of TCP proxy is compared with the standard TCP protocol. The numerical results show that our TCP proxy is able to keep the cellular link utilization over 90%, and to improve TCP throughput by 100% under most conditions.

Abstract IEEE 802.11 wireless local area networks (WLAN) has been increasingly deployed in various locations because of the convenience of wireless communication and decreasing costs of the underlying technology. However, the existing security mechanisms in wireless communication are vulnerable to be attacked and seriously threat the data authentication and confidentiality. In this paper, we mainly focus on two issues. First, the vulnerabilities of security protocols specified in IEEE 802.11 and 802.1X standards are analyzed in detail. Second, a new mutual authentication and privacy scheme for WLAN is proposed to address these security issues. The proposed scheme improves the security mechanisms of IEEE 802.11 and 802.1X by providing a mandatory mutual authentication mechanism between mobile station and access point (AP) based on public key infrastructure (PKI), offering data integrity check and improving data confidentiality with symmetric cipher block chain (CBC) encryption. In addition, this scheme also provides some other new security mechanisms, such as dynamic session key negotiation and multicast key notification. Hence, with these new security mechanisms, it should be much more secure than the original security scheme. Copyright © 2006 John Wiley & Sons, Ltd.

To meet with the ever-increasing needs of large-scale multimedia applications, a streaming media system has to be both secure and scalable. Conventional P2P technology used in streaming media could solve the problem of scalability and bandwidth bottleneck of traditional CIS architecture but still have problems in handling security for losing central manageability and robustness. Therefore, to handle security and scalability issues as a whole, in this paper we present a novel secure and scalable streaming media scheme in a central-controlled P2P framework. By firstly adopting 3D-wavelet coding in P2P streaming, we encode the raw data into different layers and separate security management from data transmission by transmitting the layer with most priority in CIS network to guarantee quality and conduct security management while transmitting the lower priority content layers in the pure P2P network to promote scalability .In our implementation, we specify the 3D-wavelet coding for P2P streaming, and design our handshaking and streaming process, load-balancing gossip-based management protocol for P2P peers. Our experimental results demonstrate our scalable framework exceed CIS streaming and meanwhile achieve better security with accepted encoding/decoding overheads over pure P2P media streaming.

Peer-to-peer technology gives novel opportunities to define a cost-effective multimedia streaming application, but at the same time, it brings a set of technical challenges due to its dynamic and heterogeneous nature. To guarantee QoS and facilitate management in large scale high-performance media streaming, we extend the current P2P networking towards a novel Peer-Server-Peer (PSP) architecture for media streaming, in which carefully-deployed servers form a trustworthy and controllable overlay network to stream P2P cluster peers. An analytical model is presented to calculate the quality of experience (QoE) and mapping QoS parameters to prove the effectiveness of Peer-Server-Peer streaming. Joint with the efforts in industry, we explore the feasibility of PSP streaming in the historical context of "demand economy" for media streaming and "best effort" Internet. The value of this paper lies not in its analytical study of this promising PSP concept with practical implementation but also its insight industrial perspective to attract further application.

The traditional TCP congestion control is inefficient for high speed networks and it is a challenge to design a high speed replacement for TCP. By simulating some existing high speed protocols, we find that these high speed protocols have limitations in convergence and stability. To address these problems, we apply a population ecology model to design a novel congestion control algorithm-Coupling Logistic TCP(CLTCP). It is based on bandwidth pre-assignment that is similar to XCP and MaxNet. The pre-assignment rate factor is computed in the routers based on the information of the router capacity, the aggregate incoming traffic and the queue length. Then the senders adjust the sending rate according to the pre-assignment rate factor which carries by the packet to strengthen the convergence and stability of transport protocol. The theoretical analysis and simulation results show that CLTCP provides not only fast convergence and strong stability, but also high utilization and fair bandwidth allocation regardless of round trip time.

Deep Packet Inspection (DPI) is a critical function in network security applications such as Firewalls and Intrusion Detection Systems (IDS). Signature based scanners used in DPI apply multi-pattern matching algorithms to check whether the packet payload or flow content contains a specified signature in a signature set. Existing multi-pattern matching algorithms sacrifice memory space to achieve better performance. In this paper a novel fast multi-pattern matching algorithm, the Hash Boyer-Moore (HBM) Algorithm, is presented, which reduces the memory footprint of the heuristic table using a hash function and adds another heuristic table to reduce the false-positive ratio. Analyses and simulations show HBM offers higher speed and lower memory cost than some existing algorithms. The HBM algorithm was implemented on the Intel IXP 2400 Network Processor (NP) platform and experiments show suitable performance results in a Gigabit Ethernet LAN environment.

In this paper, based on the Trusted Network Connect architecture, we designed a novel TNC-compatible Network Access Control System which ensures that network administrators enforce security policies on endpoint connection and communication with corporate network depending on the endpoint integrity and security status. The platform framework is built on the Intel IXP2400 network processor and a set of network access control mechanisms is implemented. The paper introduces the system design and implementation based on hardware characteristic of the IXP2400 Architecture, presents emulation performance results of the system, and then proposes systemic performance optimizations, especially cryptographic performances, according to IXP2400 shared memory hierarchy and access latency, which averagely boost the throughput more than 25%. The novelty of system design is the utilization of IXP2400 multi-core and multi-thread network processor's software and hardware platform to implement the NAC system framework through secure and reliable communication to ensure endpoint integrity and platform-authentication, which is compatible with Trusted Network Connect.

More attention has been paid to congestion control in the emerging area of wireless sensor network (WSN). However, most research works in the past stayed at the level of algorithm design or modification, and seldom sought solutions on the viewpoint of architecture. In this paper, Active Networking (AN) technology is used to make congestion control more responsive to detect/recover congestion in WSN. We design a simple Active Backpressure (BP) mechanism to allocate bandwidth Proportional to the Size of tree (ABPS). ABPS introduces programs in each data packet that tell nodes how to react to congestion, and quickly converges to a fair and efficient rate. Finally, we evaluate ABPS extensively on a 50-node wireless sensor network. Simulation results validate the effectiveness of our ABPS.

As an application-driven network, wireless sensor network generally requires high data reliability to maintain detection and response capabilities. Although two approaches, which are retransmission and redundancy, have been proposed to enhance data reliability, the theoretical work is required to evaluate their impact on transmission reliability and energy efficiency. In this paper, we offer a comprehensive theoretical study on the packet arrival probability and average energy consumption for both approaches. Our analysis indicates that when loss probability remains low or moderate, erasure coding, a scheme based on redundancy, is more reliable and energy efficient than retransmission. However, the performance of erasure coding would largely deteriorate under high packet loss condition. We also demonstrate that its resistance capability against packet loss weakens as hop number increases. Furthermore, with the increase in redundancy, erasure coding has to sacrifice the advantage of energy efficiency for reliability.

More attention has been paid to congestion control in the emerging area of wireless sensor network (WSN). However, most research works in the past stayed at the level of the current algorithms design or modification, and seldom sought solutions on the viewpoint of architecture. In this paper, Backpressure(BP) under Active Network(AN) architecture is used to make congestion control more responsive to detect/recover congestion in WSN. We design a simple Active Backpressure mechanism to allocate bandwidth Proportional to the Size of tree (ABPS), and we present a fluid-based analytical model of ABPS using stochastic differential equations. ABPS introduces programs in each data packet that tell nodes how to react to congestion, and quickly converge to a fair and efficient rate. We demonstrate a deterministic approach to analyse the stochastic model, in which we obtain a set of ordinary differential equations from our model, and we derive the average behavior of queue length and flow throughput from the ordinary differential equations. Finally, we evaluate ABPS extensively on a 50-node wireless sensor network. Simulation results validate the effectiveness of our ABPS and match well with the theoretic analysis.

With the development of wireless Internet, the interworking of the third generation (3G) wide area wireless networks and wireless local area networks (WLAN) has become a focus of research. 3G systems have their advantages in charging management, roaming, and security facilities, and WLAN systems have the advantages of high bandwidth and low investment cost. Interworking of 3G-WLAN offers characteristics that complement each other perfectly. Several authentication protocols have been proposed to improve security. In this paper, we firstly introduce the architectures of 3G-WLAN interworking and discuss existing problems related to authentication and key agreement procedures. Then, we present two schemes by applying authentication based on EAP-TLS (extensible authentication protocol-transport layer security) and EAP-TTLS (tunneled TLS) into integrated 3G and WLAN to achieve high end-to-end security and authentication for the users. Finally, we conduct a series of performance evaluation on the energy consumption and latency of standard authentication protocols.

Grid services scheduling is a challenging problem under open grid service architecture (OGSA). Grid services running on clusters must have mechanism and policies for establishing and supporting QoS. A graph theory formal description is introduced into the service grid model in this paper. The necessary and sufficient condition of complete matching of user job and service resources has been given and proved. Optimal solution to matchmaking of grid jobs and grid services is developed based on the running time weight matrix, and the arithmetic has been verified by simulation analysis which proved to be more efficient than the alike arithmetic. The arithmetic has been implemented and running well

Existing isolated and add-on secure systems are rarely robust under attack, misoperation and internal faults. Secure communication only offers little protection if one ore more components are compromised, and are not sufficient for holistic and systemic security. This paper proposes the concept of trustworthy networks, which makes advances along these traditional researches on network security in combination. We outline the key challenges in constructing trustworthy networks, and define three properties, namely security, survivability and controllability. Consulting human interactions, the abstract architecture for trustworthy networks is proposed, depicting protocols layers, topology structure, entities and components, and protocol steps

In this paper, a general fluid model is developed to study the performance and fairness of BitTorrent-like networks. The fluid model incorporates two important features, user settings with multiple groups and inter-group data exchange, in a synthesized way to obtain statistics about the system performance. Our numerical results point out some key parameters of the system, such as the staying time of seeders. Generally, selfish behavior does not receive equal performance degradation, and in some scenarios users have strong incentives of free-riding. We also find content delivery can be greatly deterred when malicious free-riders are overwhelming.

In this paper, an AntiWorm system based on the Intel IXP Network Processor was implemented using the Parallel Bloom filters technique. The AntiWorm system consists of two components: Bloom filters and Exact Matching engines. The Parallel Bloom filters can identify the suspicious traffic quickly and effectively, and then dispatch them to Exact Matching engines for further investigation. Both the principles and the implementation of the AntiWorm system are introduced in detail. With the consideration of the system performance parameters, two feasible implementation solutions are investigated and the advantages and disadvantages are also compared. The selections of configuration parameters of the AntiWorm system are also discussed. A hash scheme based on MD5's function is proposed for implementing fast hash functions. To test the performance of the AntiWorm system, such as throughput and delay, some experiments are carried out with different simulated traffic condition. The internal statistics of IXP network processor are also collected and analyzed for optimizing the system performance. To demonstrate the operation of the AntiWorm system, assaults by Worm Blaster are used in the test bed, and the experimental results prove the effectiveness of the AntiWorm system. The Software Package WormDetector1.0 is also provided as a software release from the research.

In this paper, a novel secure key sharing and distribution scheme for network mobility (NEMO) group communications is proposed. The scheme offers the capability of multiple key sharing and distribution for current and future application scenarios, and a threshold mechanism that effectively improves flexibility and robustness of the key sharing and distribution process. Both forward and backward secrecy are guaranteed by compulsive key refreshment and automatic key refreshment mechanisms, which provide dynamic in-progress group communication joining/leaving and periodic keys renewal, respectively. Security and performance analysis are presented to demonstrate that the proposed scheme meets the special security requirements for NEMO group communications and is competent for key sharing and distribution service.

Information security has been a critical issue in the design and development of reliable distributed communication systems and has attracted significant research efforts. A challenging task is how to maintain information security at a high level for multiple-destination video applications with the huge volume of data and dynamic property of clients. This paper proposes a novel Content-Aware Secure Multicast (CASM) protocol for video distribution that seamlessly integrates three important modules: 1)a scalable light-weight algorithm for group key management; 2) a content-aware key embedding algorithm that can make video quality distortion imperceptible and is reliable for clients to detect embedded keys; and 3) a smart two-level video encryption algorithm that can selectively encrypt a small set of video data only, and yet ensure the video as well as the embedded keys unrecognizable without a genuine key. The implementation of the CASM protocol is independent of the underlying multicast mechanism and is fully compatible with existing coding standards. Performance evaluation studies built upon a CASM prototype have demonstrated that CASM is highly robust and scalable in dynamic multicast environments. Moreover, it ensures secure distribution of key and video data with minimized communication and computation overheads. The proposed content-aware key embedding and encryption algorithms are fast enough to support real-time video multicasting.

Two novel mutual authentication and key exchange protocols with anonymity are proposed for different roaming scenarios in the global mobility network. The new features in the proposed protocols include identity anonymity and one-time session key renewal. Identity anonymity protects mobile users privacy in the roaming network environment. One-time session key progression frequently renews the session key for mobile users and reduces the risk of using a compromised session key to communicate with visited networks. It has demonstrated that the computation complexity of the proposed protocols is similar to the existing ones, while the security has been significantly improved.

A novel authentication protocol for teleconference service is proposed. The main features of the proposed protocol include identity anonymity, one-time PID (pseudonym identity) renewal and location intractability. Identity anonymity is achieved by concealing the real identity of a mobile conferee in a prearranged pseudonym identity. One-time PID renewal mechanism, in which the mobile conferee's PID is frequently updated communicating with the network centre, is introduced to offer location intractability. It is shown that the security has been significantly enhanced, while the computation complexity is similar to the existing one appeared in the literature.

The guard channel scheme in wireless mobile networks has attracted and is still drawing research interest owing to easy implementation and flexible control. However guard channel schemes can not adapt to changing traffic loads because of static reserved guard channels. Therefore dynamic guard channel schemes have been proposed in the literature to adapt to varying traffic load. This paper presents a novel control-theoretic approach to dynamically reserve guard channels called PI-guard channel (PI-GC) controller. Experiments show that our proposed scheme can maintain the handoff blocking probability (HBP) to a predefined value while it still improves the channel resource utilization.

TCP/IP protocol suite carries most application data in Internet. TCP flow retrieval has more security meanings than the IP packet payload. Hence, monitoring the TCP flow has more strength than only monitoring the IP packet payload in the AntiWorm system. The main idea of this paper is to use the flexibility and high performance of network processors to scan TCP flow for locating worm's binary codes, and cut off their propagation. A stateful TCP flow inspection engine is implemented based on IXP network processor, which can monitor about 512K flows. The performance issues about IXP network processors are evaluated and collected, and an analysis is made for further optimizing the system performance. The system is also demonstrated and proved by using the Internet traces and real assaults of Worms. Software Package TCPScanner 1.0 is also given as a software release of the research

Streaming media over networks has gained renewed interest recently due to the emerging IP-TV and mobile TV. The success of commercial media streaming systems critically depends on two important capabilities, namely, 1) scalability in distributing media content to diverse clients, and 2) security management of the media and the systems. However, existing media streaming systems such as content distribution networks (CDN) and Peer-to-Peer (P2P) networks lack either security or scalability. In this paper, we propose a novel secure and scalable media streaming architecture, called TrustStream. Our architecture combines the best features of CDN and P2P networks to achieve unprecedented security, scalability, and certain quality of service simultaneously. Our experimental results demonstrate the advantages of the TrustStream.

In the multi-service wireless networks, the bandwidth asymmetry is the distinctive characteristic. To avoid wasting uplink and downlink bandwidth in asymmetric network, admissible region for the nonreal-time (NRT) calls has been proposed. But in that scheme the static guard capacity for RT and NRT calls cannot adapt to traffic variation. In addition, the differentiated QoS services to users are not considered. In this paper, we propose an adaptive guard channel reservation (AGCR) scheme, which has the following novelties: i) the guard capacity for each class is dynamically adjusted so as to adapt to dynamic traffic, ii) the blocking probabilities of classes with higher priority are kept below certain targets and iii) differentiated QoS services to users are provided by maintaining the blocking probability ratios over different classes at the predefined targets. Simulation results have demonstrated the proposed AGCR scheme can keep the blocking probabilities of classes with higher priority below certain targets, track the ratios close to the targets well while maintaining a high bandwidth utilization.

This paper presents a fuzzy control approach that guarantees absolute delays in Web servers. Previous work has proposed the use of classical PI controllers for delay guarantees. However, a disadvantage of the classical PI controller is that the system model, which is obtained by system identification, mismatches the real system and inevitably degrades the performance of the Web system. In contrast with classical PI controllers, fuzzy controllers are nonlinear and therefore independent of the accurate model of the plant, i.e. the controlled system. Hence, fuzzy controllers seem to be very suitable for Web servers. Our experiments show that fuzzy controllers indeed perform better than PI controllers presented in earlier papers.

Extended interval temporal logic (EITL), an extension of the traditional point-interval temporal logic (PITL), is proposed. In contrast to PITL that represents the dynamic aspects of deterministic intervals, EITL can model and reason about the temporal relations among nondeterministic intervals in discrete-event systems, in which the duration of an event is indeterminate and only the lower bound and upper bound of the ending time can be predicted in advance. Time Petri nets (TPNs) are used for modeling EITL, for they give a straightforward view of temporal relations between the extended intervals and also provide a number of theoretical and practical analysis methods. An inference engine based on the TPN modeling complemented with algebraic inequalities is proposed to construct an analytical representation of the EITL relations and solve qualitative temporal reasoning problems. Linear inference mechanism based on TPN reduction rules is used to infer new temporal relations and handle quantitative temporal reasoning problems with linear time complexity, as our example shows.

Persistent connections are increasingly being used in Web retrieval due to wide adoption of HTTP/1.1 standards. With persistent connections, the request allocation algorithm used by Web clusters is often session-grained. This article studies the caching performance of Web clusters under session-grained request allocation. It is shown that although content-based algorithms considerably improve caching performance over content-blind algorithms at the request-grained level, most performance gain is offset by the allocation dependency that arises when the requests are allocated at the session-grained level. The performance loss increases with cluster size and connection holding time. An optimization problem is then formulated for improving the caching effectiveness of session-grained allocation. The problem is proven to be NP-complete. Based on a heuristic approach, a session-affinity aware algorithm is presented that makes use of the correlation between the requests in a session. The new algorithm is shown to significantly outperform the content-based algorithm under session-grained allocation. It is also shown that optimizing session-grained allocation cannot fully compensate for the performance loss caused by allocation dependency.

AQM (active queue management) can maintain the smaller queuing delay and higher throughput by the purposefully dropping the packets at the intermediate nodes. Almost all the existed schemes for AQM neglect the impact of large delay on performance. In this study, we firstly verify a fact through simulation experiments, which is the queues controlled by the several popular AQM schemes, including RED, PI controller and REM, appear the dramatic oscillations in large delay networks, which decreases the utilization of the bottleneck link and introduces the avoidable delay jitter. After some appropriate model approximation, we design a robust AQM controller to compensate the delay using the principle of internal mode compensation in control theory. The novel algorithm restrains the negative effect on queue stability caused by large delay. The simulation results show that the integrated performance of the proposed algorithm is obviously superior to that of several well-known schemes when the connections have large delay, at the same time, the buffers keep at small queue length.

Recently, a significant body of research has been dedicated to the analysis and verification of workflows without taking into account the temporal dimension of activities involved. Workflow also has a strong temporal aspect: activity sequencing, deadlines, routing conditions, and scheduling all involve the element of time. Once the temporal aspects of the activities in a process description are taken into account, various types of synchronization anomalies and other undesirable behavior may be detected. In this article, we address both the quantitative temporal aspect and the qualitative temporal aspect of workflow systems. On one hand, based on time Petri net (TPN), we introduce a set of linear inference algorithms to solve some quantitative inference problems of temporal constraints of workflows. On the other hand, based on extended interval temporal logic (EITL), we propose temporal logic workflow models to qualitatively infer temporal relations among tasks of workflow systems. © 2004 Wiley Periodicals, Inc.

A novel VLSI architecture for multidimensional discrete wavelet transform (mD DWT) based on a systolic array is proposed. We divide the input mD image data into 2/sup m/ independent data streams, and then simultaneously pipeline them into a multi-filter chip, and finally obtain 2/sup m/ samples which are from different DWT subbands per clock cycles (ccs). The proposed architecture performs a decomposition of an N/sub 1//spl times/N/sub 2//spl times/.../spl times/N/sub m/ image in about N/sub 1/N/sub 2/...N/sub m//(2/sup m/-1) ccs and requires relatively lower hardware cost than previous architectures. Besides, the advantages of the proposed architecture include very simple hardware complexity, regular data flow and low control complexity.

Handoff is one of the key elements in ensuring quality of service (QoS) in mobile wireless networks. Handoff connections generally have higher priority than new connections. Traditional reservation policies that reserve some channels for handoff connections are not adaptive to traffic load changes. This paper proposes a new dynamic guard channel scheme (DGCS), which 1) adapts to various traffic loads; 2) combines differentiated QoS service model and priority handoff mechanism; 3) provides fairness for differentiated QoS services; 4) does not need to exchange state information among different cells, so it is easy to be implemented and is simple enough to be used in real time environments; 5) and utilizes network resources efficiently and puts a bound on each service blocking probability. The simulation results show that the ratios among different QoS service probabilities are guaranteed to be predefined values and system utilization is improved greatly.

As an enhancement mechanism for the end-to-end congestion control, active queue management (AQM) can keep smaller queuing delay and higher throughput by purposefully dropping the packets at the intermediate nodes. Comparing with RED algorithm, although the PI (proportional-integral) controller for AQM designed by C. Hollot improves the stability, the transient performance of the PI controller is not perfect, such as the regulating time is too long. In order to overcome this drawback, in this paper, the PID (proportional-integral-differential) controller is proposed to speed up the responsiveness of AQM system. The controller parameters are tuned based on the determined gain and phase margins. The simulation results show that the integrated performance of the PID controller is obviously superior to that of the PI controller.

A large network is composed of many autonomous security domains. Based on the definition of security domain, a lattice model of security domains is described. Subsequently, a model of multilevel security domains combined with the multilevel security is derived. Another important concept tied up with multilevel security domains is authentication. According to the trust relationships between different security domains, an authentication architecture and two authentication protocols suitable for multilevel security domains are proposed in this paper. At last, the authentication protocol is formally analyzed with the aid of the BAN logic.

With the increasing needs of security, cryptographic functions have been exploited in network devices. Besides time consuming, security protocols are flexible in algorithm selections. Fortunately, network processors, which serve as the backbone of intelligent network devices, hold performance and flexibility at the same time. In this article, we investigate several principles that can be used with implementing and optimizing cryptographic algorithms on network processors. Also, these principles are applied in real life algorithms, including stream ciphers, block ciphers and digital signatures. Related experiments and benchmark results on Intel IXP1200 network processor are provided.

As an effective mechanism acting on the intermediate nodes to support end-to-end congestion control, active queue management (AQM) takes a trade-off between link utilization and delay experienced by data packets. Most of the existing AQM algorithms are heuristic, and a lack systematic and theoretical design and analysis approach. From the viewpoint of control theory, it is rational to regard AQM as a typical regulating system. Although the PI controller for AQM outperforms the RED algorithm, the mismatches in the simplified TCP flow model inevitably degrade the performance of a controller designed with classical control theory. In this paper, a robust SMVS controller for AQM is put forward based on sliding mode variable structure control (SMVS), its superiority is insensitive to the noise and variance of the parameters, thus it very suitable to a time-varying network system. The principle and guidelines on design of a SMVS controller are presented in detail. The integrated performance is evaluated using ns simulations. The results show that SMVS is very responsive and robust against disturbances. At the same time, a complete comparison between the SMVS controller and PI controller is made. The conclusion is that both the transient and steady performance of the SMVS controller is superior to that of the PI controller, thus the SMVS controller is in favor of the achievement of AQM objectives.

The network traffic control strategies and algorithms are part of the feedback loop that allows such a complex system to operate at an optimal or near-optimal functioning point. Effective performance criteria are an important element for providing the feedback regarding the current state of the system; thus, they represent a key aspect of the design of network traffic control strategies and algorithms. We introduce three synthetic factors of merit regarding the quality of service, the quantity of service and the ratio of the two. The figures of merit may take into account multiple QoS attributes. Each of these figures of merit can be calculated either for individual flows, the flows with a common characteristic, e.g., belonging to the same class, or crossing the same router, or for all the flows in a network. We also define a coefficient of fairness among the flows with a common characteristic, as the ratio of the variance to the expected value of a factor of merit.

In this paper we rethink the tradeoff between proportional controller and PI controller in AQM (active queue management) algorithm design. With the introduction of integral factor, the steady state error in a proportional controller such as RED is eliminated. However the integral factor also slows down the response speed. We present a simple algorithm P/sup 2/I to solve this problem. P/sup 2/I combines the advantage of the proportional controller and the PI controller. The performance of P/sup 2/I is verified and compared with the PI controller using ns-2 simulations. P/sup 2/I is shown to respond much faster than the PI controller while retaining the merits of the PI controller. We also analyze the impact of the traffic pattern on the design and success of AQM.

The performance-evaluating criterion is one of the most important issues for the design of network traffic control strategy and algorithms. The design will be varied with the evaluating criterion. Because the network traffic control strategy has multiple performance objects, how to reach multiple objects simultaneously is one difficult problem. This paper provides a set of integrated performance evaluating criteria from the network traffic control model, and the criteria integrates several objects, such as the network performance, user's QoS requirement and system fairness. Then it is discussed and analyzed in details. Moreover, the integrated performance evaluating criteria can be applied to performance evaluation and improvement in network traffic control strategy and algorithms.

System stability is an important criterion in selecting an appropriate control or scheduling policy for re-entrant line systems. Traditionally, stability analysis was based on the concept of time boundedness and was studied using Foster's criterion, which is a special case of stochastic Lyapunov functions. We emphasized the concept of buffer boundedness as an alternative criterion for characterizing the stability of scheduling policies and analyzed the stability of re-entrant line systems using this concept. A Petri net based framework was introduced to represent the dynamic behavior of re-entrant line systems. The Petri net method has been shown to be intuitive, simple and efficient.

Proposes an integrative scheme of differentiated services (DiffServ) for the Internet. In our scheme, the quality of service (QoS) is ranked according to the levels of both importance and urgency, which makes the service negotiation and the implementation mechanism more flexible and universal. Samples of the implementation mechanism at the edge nodes and interior nodes are described, and stochastic Petri net models of them are given. The performance of the per-hop behavior (PHB) implementation mechanism is analyzed, under both Poisson and self-similar arrivals. An approximate analysis technique of decomposition and iteration is used to reduce the complexity. For self-similar traffic, an MMPP (Markov-modulated Poisson process) based self-similar model of A.T. Andersen et al. (1998) is used.

New schemes of scheduling real-time traffic in high speed ATM networks are proposed for multiple priority queues based on dynamic queue length thresholds in real-time scheduling. The proposed schemes will provide guaranteed real-time service for each connection and cell sequence integrity for virtual channel/path characteristics. We provide the stochastic Petri net model of these schemes and an approximate analysis technique, which significantly reduce the complexity of the model solution and can be applied to real ATM switch models. Using numerical results we show that our schemes outperform well known schemes such as the head-of-line priority control and the queue length threshold policy.

This paper extends the logical inference of Horn clauses in Petri net models to cover a large class of non-Horn clauses. Based on four-valued logic and the conflict transition concept, we show how the Petri net model for this class of non-Horn clauses can be constructed. The clause inference is solved by the T-invariant method or the fixpoint of markings. Both forward and backward inference can be used in our model. It is further shown that these techniques are efficient for the common classes of monotonic reasoning. © 1998 John Wiley & Sons, Inc.

This paper describes a general framework for modeling and analyzing ATM traffic control using the stochastic high level Petri net (SHLPN). The reasons SHLPN is chosen are two fold: it can handle concurrent, asynchronous, nondeterministic and stochastic events; and it provides an intuitive yet efficient mechanism that can decompose a complex model into submodels. In addition, there exists a set of well-developed performance analysis techniques for SHLPN. In order to cope with the well known state space explosion problem, we proposed a novel reduction method which incorporates the bursty characteristic of ATM networks. We show how to apply the SHLPN techniques in modeling and analyzing various ATM mechanisms such as: bursty traffic source and traffic rate control.

In this article we investigate the use of Petri nets for the representation of possible worlds in probabilistic logic. We propose a method to generate possible worlds based upon the reachability tree of the Petri net model. The number of columns in the matrix of possible worlds grows exponentially with the problem size. Nilsson [Proceedings of 1976 National Computer Conference and Readings in Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 1981, pp. 192-199] suggested a method to generate only those columns of the possible world matrix that are likely to be important for the solution. We provide Petri net models for the method suggested by Nilsson and show that they lead to intuitive and simple computational methods. © 1996 John Wiley & Sons, Inc.

This paper presents a framework for modeling and analyzing ATM admission control using Stochastic High Level Petri Net (SHLPN). SHLPN is chosen because it is a powerful graphical and mathematical modeling tool that is able to handle concurrent, asynchronous, nondeterministic and stochastic events. In addition, there exists a set of well-developed performance analysis techniques for SHLPN. This paper uses a hierarchical modeling technique to specify complex ATM network mechanisms using a top-down approach. However, in analyzing the performance of the network, a bottom-up approach is adopted. To tackle the state space explosion problem, a SHLPN model is decomposed into submodels. These subnets are independently evaluated with all possible population which are then substituted by transitions with approximate equivalent performance in the original model. The technique is illustrated by modeling and evaluating a specific connection admission control policy.

Petri net models for the Horn clause form of propositional logic and of first-order predicate logic are studied. A net model for logical inconsistency check is proposed. Algorithms for computing T-invariants of Petri net models of logical inference systems are investigated. The algorithms are based on the idea of resolution and exploit the presence of one-literal, pure-literal, and splitting clauses to lead to faster computation. Algorithms for computing T-invariants of high-level Petri net (HLPN) models of predicate logic are presented.>

A class of stochastic Petri nets called stochastic high-level Petri nets (SHLPNs) is proposed. SHLPNs are high-level Petri nets augmented with exponentially distributed firing times. SHLPNs generally lead to models with a smaller state space. A computer marking concept is introduced that allows a considerable reduction of the number of states and induces a correct grouping of states in the Markov-domain SHLPN models of multiprocessor systems. The main advantage of modeling homogeneous systems using SHLPNs is that the resulting models are simpler and more intuitive and have a smaller number of states, as shown by examples.>