Internet-connected devices have been surging rapidly during the past years. Many important applications based upon such devices have emerged, such as vehicle tracking systems. These applications often require real-time execution of a large number of computation tasks. Edge computing has shown great potential in processing frequent but less-demanding tasks. Additionally, cloud computing allows for great scalability when substantial computing resources are needed. Edge-cloud computing is a paradigm that combines edge computing and cloud computing. A key problem in edge-cloud computing is how to determine the execution location for each computation task. We propose a dynamic edge-twin computing model in the context of edge-cloud computing. It uses an evaluation mechanism to predict the completion times of the task at both an edge device and a cloud server. The completion time includes data transfer time and computing time and it is determined based on real-time information about the task and the computing environment. The task will be executed by the device with a shorter completion time. We have implemented a vehicle tracking system under the edge-twin model. The experimental results show that the edge-twin model outperforms edge-alone computing and cloud-alone computing.

Traffic measurement provides fundamental statistics for network management functions. To implement the measurement modules on the data plane for real-time query response, modern sketches are designed to work with limited on-die memory allocation from network processors and collect traffic statistics in epochs of a preset length. To handle real-time queries at arbitrary times over traffic in a preceding period${T}$(called${T}$-queries), the prior art sets the epoch length to${T \over n}$and keeps the measurement results in a window of$n - 1$past epochs to support approximate${T}$-queries. Such an approach however drastically increases the memory cost or decreases the accuracy in the query results if the memory allocation is fixed. In this paper, motivated by the concept of offloading in today's edge-cloud computing, we propose a collaborative edge-center traffic measurement model, where the traffic measurement modules at all network devices form the edge, which offloads the traffic measurement results to a measurement center possibly hosted in a datacenter. The center synthesizes the measurements from the past epochs and sends the aggregate results back to the measurement modules to support T-queries. We conduct experiments using real traffic traces to evaluate the performance of the proposed edge-center measurement model. The experimental results demonstrate that the proposed designs significantly outperform the prior art.

We study a fundamental problem of how to schedule complex workflows in the cloud for applications such as data analytics. One of the main challenges is that such workflow scheduling problems involve many constraints, requirements and varied objectives and it is extremely difficult to find high-quality solutions. To meet the challenge, we explore using mixed integer programming (MIP) to formulate and solve complex workflow scheduling problems. To illustrate the MIP-based method, we formulate three related workflow scheduling problems in MIP. They are fairly generic, comprehensive and are expected to be useful for a wide range of workflow scheduling scenarios. Using results from numerical experiments, we demonstrate that, for problems up to certain size, the MIP approach is entirely applicable and more advantageous over heuristic algorithms.

As computational clouds offer increasingly sophisticated services, there is a dramatic increase in the variety and complexity of virtual machine (VM) placement problems. In this paper, we consider a VM placement problem with a special type of anti-colocation requirements-disk anti-colocation-which stipulate that, for every VM assigned to a PM (physical machine), its virtual disks should be spread out across the physical disks of the PM. Once such a requirement is met, the users of the VM can expect improved disk I/O performance. There will also be improvement in fault tolerance and availability. For scalable solutions, we propose a method that combines hierarchical decomposition with mixed integer programming (MIP), where the basic building blocks are independent, small MIP subproblems. We provide experimental results to demonstrate the effectiveness of the proposed method. We show that it is scalable and achieves high performance with respect to the optimization objective.

In this paper, we investigate the issue of minimizing data center energy usage. In particular, we formulate a problem of virtual machine placement with the objective of minimizing the total power consumption of all the servers. To do this, we examine a CPU power consumption model and then incorporate the model into an mixed integer programming formulation. In order to find optimal or near-optimal solutions fast, we resolve two difficulties: non-linearity of the power model and integer decision variables. We first show how to linearize the problem, and then give a relaxation and iterative rounding algorithm. Computation experiments have shown that the algorithm can solve the problem much faster than the standard integer programming algorithms, and it consistently yields near-optimal solutions. We also provide a heuristic min-cost algorithm, which finds less optimal solutions but works even faster.

Computational clouds have evolved to go beyond cost-effective on-demand hosting of IT resources and elasticity. The added features now include the ability to offer entire IT systems as a service that can quickly adapt to changing business environments. The new trend introduces challenges in datacenter resource management, including scalability, system-orientation, and optimization supporting both datacenter efficiency and customer system agility and performance. The conventional approach of resource management adopts a flat fine-grained model that results in problem formulations of enormous sizes, it also has the drawback of being less flexible in meeting customers' need. In this paper, we introduce a pack-centric approach to datacenter resource management by abstracting a system as a pack of resources and considering the mapping of these packs onto physical datacenter resource groups, called swads. The assignments of packs to swads are formulated as mixed integer programming problems. Scalability is achieved through a hierarchical decomposition method and parallel solvers. The new datacenter resource management framework is illustrated with a concrete resource placement problem. Numerical experiments show the scalability of the hierarchical decomposition method and the benefits of the overall framework.

The paper investigates theoretical issues in applying the universal swarming technique to efficient content distribution. In a swarming session, a file is distributed to all the receivers by having all the nodes in the session exchange file chunks. By universal swarming, not only all the nodes in the session, but also some nodes outside the session may participate in the chunk exchange to improve the distribution performance. We present a universal swarming model where the chunks are distributed along different Steiner trees rooted at the source and covering all the receivers. We assume chunks arrive dynamically at the sources and focus on finding stable universal swarming algorithms. To achieve the throughput region, universal swarming usually involves a tree-selection subproblem of finding a min-cost Steiner tree, which is NP-hard. We propose a universal swarming scheme that employs an approximate tree-selection algorithm. We show that it achieves network stability for a reduced throughput region, where the reduction ratio is no more than the approximation ratio of the tree-selection algorithm. We propose a second universal swarming scheme that employs a randomized tree-selection algorithm. It achieves the throughput region, but with a weaker stability result. Comprehensive simulation results support the stability analysis of the algorithms. The proposed schemes and their variants are expected to be useful for infrastructure-based content distribution networks with massive content and relatively stable network environment.

We provide an improved bound for the expectation of the stationary delay under the maximum weight scheduling (MWS) policy in one-hop wireless networks. In the model, the interference of the links is characterized by an interference graph G=(V, E). For a vector μ ϵ R|V|+, let χf(G, μ) be the weighted fractional coloring number for the graph G under the weight vector μ. For an arrival rate vector λ in the capacity region, we define a quantity ε(λ)to be the unique value satisfying the condition χf(G, λ+ε(λ)e) = 1, where e = (1, 1,..., 1)T. We show that the stationary delay is upper-bounded by B(2(Σi=1|V|λi) ε(λ)), where B is a constant depending on the arrival process. We show that the new bound is the tightest single-parameter bound obtainable with an often-used analytical framework. Generalizing the above, we also provide the tightest bounds for all MWS-w policies.

Recent studies on queue-length-based randomized link scheduling algorithms have shown their throughput-optimality. But simulation results indicate that the packet delay in such algorithms can be quite large, even when the traffic intensity is low compared with the network capacity. The reason can be traced to the fact that these algorithms need the queues to be sufficiently large before the links have a good chance to be activated for transmission. In this paper, we propose a new randomized scheduling algorithm based on the Ising model in physics. The algorithm does not require queue build-up for link activation and can thus give better delay performance. It is easily implementable in a distributed fashion and it retains throughput-optimality.

We provide bounds for the expectations of the stationary delay and the sum of the stationary queue sizes under the approximate maximum weight scheduling (MWS) policy and under the longest-queue-first (LQF) policy in one-hop wireless networks. For MWS, our results improves the previously provided bounds; for LQF, the results are new. In the derivation of the new bounds, a connection with certain graph theory quantities has been established. We also derive bounds for the sum of the second moments of the stationary queue sizes, which are also bounds for the sum of the queue-size variances. The method is general and it can be used to derive bounds for the sum of even higher moments of the stationary queue sizes. However, for the approximate MWS policy, the bounds for the second or higher moments are only valid when the average arrival rate vector is confined to a subset of the capacity region that depends on the order of the moment.

We propose an algorithm for maximizing the lifetime of a wireless sensor network when there is a mobile sink and the underlying application can tolerate some amount of delay in delivering the data to the sink. The algorithm is distributed, and in addition, mostly uses local information. Such an algorithm can be implemented by parallel and/or distributed execution and the overhead of message passing is low. It is also possible to embed the algorithm into a network protocol so that the sensor nodes and the sink can run it directly as part of the network operation. We give a proof of the algorithm's optimality and the boundedness of the queue sizes, both in the long-run average sense. The proof is based on analyzing a Lyapunov drift.

Efficient link scheduling in a wireless network is challenging. Typical optimal algorithms require solving an NP-hard subproblem. To meet the challenge, one stream of research focuses on finding simpler suboptimal algorithms that have low complexity but high efficiency in practice. In this paper, we study the performance guarantee of one such scheduling algorithm, the longest-queue-first (LQF) algorithm. It is known that the LQF algorithm achieves the full capacity region,$\Lambda $, when the interference graph satisfies the so-called local pooling condition. For a general graph$G$, LQF achieves (i.e., stabilizes) a part of the capacity region,$\sigma ^{\ast }(G) \Lambda $, where$\sigma ^{\ast }(G)$is the overall local pooling factor of the interference graph$G$and$\sigma ^{\ast }(G) \leq 1$. It has been shown later that LQF achieves a larger rate region,$\Sigma ^{\ast }(G) \Lambda $, where$\Sigma ^{\ast }(G)$is a diagonal matrix. The contribution of this paper is to describe three new achievable rate regions, which are larger than the previously known regions. In particular, the new regions include all the extreme points of the capacity region and are not convex in general. We also discover a counterintuitive phenomenon in which increasing the arrival rate may sometime help to stabilize the network. This phenomenon can be well explained using the theory developed in this paper.

One of the major challenges in wireless networking is how to optimize the link scheduling decisions under interference constraints. Recently, a few algorithms have been introduced to address the problem. However, solving the problem to optimality for general wireless interference models is known to be NP-hard. The research community is currently focusing on finding simpler suboptimal scheduling algorithms and on characterizing the algorithm performance. In this paper, we address the performance of a specific scheduling policy called Longest Queue First (LQF), which has gained significant recognition lately due to its simplicity and high efficiency in empirical studies. There has been a sequence of studies characterizing the guaranteed performance of the LQF schedule, culminating at the construction of the σ-local pooling concept by Joo In this paper, we refine the notion of σ -local pooling and use the refinement to capture a larger region of guaranteed performance.

In this paper, we investigate the issue of server selection for P2P IPTV system on fiber to the node networks. To achieve high performance and resilience to failures, a peer can make connections with multiple peers simultaneously and receive different portions of the data in parallel. Prior work mostly focuses on user-centric performance objectives, such as reducing the round-trip time or the completion time of individual download, but tend to ignore the congestion caused by the concurrent connections or the network load balance. The latter performance concerns are important for the network operators who provide and manage IPTV services. In this paper, we consider two performance metrics, the worst-case link stress (WLS) and the degree of interference (DOI), and present a server selection scheme that generates the optimal server set with respect to the WLS criterion. Through experiments on PlanetLab, we show that the proposed scheme has the advantages over the random scheme and the closest scheme in the following aspects. First, it minimizes the level of congestion at the bottleneck link. Second, it consumes less network resources in terms of the total bandwidth usage. Third, the network load is well balanced.

The paper studies the complexity of the wireless scheduling problem under interference constraints. We first relate the definition of the capacity region to the weighted fractional coloring problem. Then, the scheduling-for-stability problem under deterministic arrivals is studied in light of this relationship. We emphasize the requirement that the scheduling algorithm uses a tractable amount of processing and storage resources. Two classes of algorithms are defined and a complexity result is derived for the intersection of the two classes. We also exhibit an algorithm that can achieve the storage requirement by relaxing the processing requirement. The results are used to examine interesting sections of the capacity region. Finally, we relate the new interpretation and theory about the capacity region to the notion of set ¿-local pooling.

This paper proposes a framework to maximize the lifetime of the wireless sensor networks (WSNs) by using a mobile sink when the underlying applications tolerate delayed information delivery to the sink. Within a prescribed delay tolerance level, each node does not need to send the data immediately as it becomes available. Instead, the node can store the data temporarily and transmit it when the mobile sink is at the most favorable location for achieving the longest WSN lifetime. To find the best solution within the proposed framework, we formulate optimization problems that maximize the lifetime of the WSN subject to the delay bound constraints, node energy constraints, and flow conservation constraints. We conduct extensive computational experiments on the optimization problems and find that the lifetime can be increased significantly as compared to not only the stationary sink model but also more traditional mobile sink models. We also show that the delay tolerance level does not affect the maximum lifetime of the WSN.

A distinct trend has emerged that the Internet is used to transport data on a more and more massive scale. Capacity shortage in the backbone networks has become a genuine possibility, which will be more serious with fiber-based access. The problem addressed in this paper is how to conduct massive content distribution efficiently in the future network environment, where the capacity limitation can equally be at the core or the edge. We propose a novel technique as a main content transport mechanism to achieve efficient network resource utilization. The technique uses multiple trees for distributing different file pieces, which at the heart is a version of swarming. In this paper, we formulate an optimization problem for determining an optimal set of distribution trees as well as the rate of distribution on each tree under bandwidth limitation at arbitrary places in the network. The optimal solution can be found by a distributed algorithm. The results of the paper not only provide stand-alone solutions to the massive content distribution problem, but should also help the understanding of existing distribution techniques such as BitTorrent or FastReplica.

The advancement of optical network technologies has enabled data-intensive e-science collaborations, which often require the transfer of large files with predictable performance. To support such applications, we design and evaluate two algorithms for scheduling time-constrained bulk transfers on wavelength-based optical research networks. The first one seeks to maximize the network throughput while maintaining a level of fairness among the jobs. The second algorithm works in an overloaded network and serves as an alternative to the first algorithm. It seeks to extend the end times by the smallest possible proportion and complete all the jobs by the extended end times. The main challenge is that the underlying problems are integer optimization problems for wavelength assignment, which have no known fast optimal solutions. We present a heuristic sub-algorithm called LPDAR, which converts fractional solutions from linear programming into integer solutions. LPDAR is the key component used in both aforementioned algorithms. Evaluation shows that LPDAR leads to very good algorithms with a performance level and speed both comparable to those of the LP fractional solutions.

One of the major challenges in wireless networking is how to optimize the link scheduling decisions under interference constraints. Recently, a few algorithms have been introduced to address the problem. However, solving the problem to optimality for general wireless interference models is known to be NP-hard. The research community is currently focusing on finding simpler, sub-optimal scheduling algorithms and on characterizing the algorithm performance. In this paper, we address the performance of a specific scheduling policy called Longest Queue First (LQF), which has gained significant recognition lately due to its simplicity and high efficiency in empirical studies. There has been a sequence of studies characterizing the guaranteed performance of the LQF schedule, culminating at the construction of the σ-local pooling concept by Joo et al. [10]. In this paper, we refine the notion of σ-local pooling and use the refinement to capture a larger region of guaranteed performance.

Data-intensive e-science collaborations often require the transfer of large files with predictable performance. To meet this need, we design novel admission control (AC) and scheduling algorithms for bulk data transfer in research networks for e-science. Due to their small sizes, the research networks can afford a centralized resource management platform. In our design, each bulk transfer job request, which can be made in advance to the central network controller, specifies a start time and an end time. If admitted, the network guarantees to complete the transfer before the end time. However, there is flexibility in how the actual transfer is carried out, that is, in the bandwidth assignment on each allowed path of the job on each time interval, and it is up to the scheduling algorithm to decide this. To improve the network resource utilization or lower the job rejection ratio, the network controller solves optimization problems in making AC and scheduling decisions. Our design combines the following elements into a cohesive optimization-based framework: advance reservations, multipath routing, and bandwidth reassignment via periodic reoptimization. We evaluate our algorithm in terms of both network efficiency and the performance level of individual transfer. We also evaluate the feasibility of our scheme by studying the algorithm execution time.

Performance trade-offs between fast data access by local data replication and cache capacity maximization by global data sharing have been extensively studied for many-core Chip Multiprocessors (CMPs). Costly simulations over a wide spectrum of the design space are generally required to gain insight for a sound design. To lower the cost, we develop an abstract model for understanding the performance impact of data replication on CMP caches. To overcome the lack of real-time interactions among multiple cores in the model, we further develop an efficient single-pass stack simulation to study the performance of CMP cache organizations with various degrees of data replication. The global stack logically incorporates a shared stack and per-core private stacks; shared/private reuse (stack) distances can be collected in a single-pass simulation. With the reuse distances, one can calculate the performance of CMP cache organizations with various degrees of data replication. We verify both the model and the stack simulation against execution-driven simulations with commercial multithreaded workloads. The results show that the abstract model provides accurate information about performance trade-offs of data replication. The stack simulation accurately predicts the performance of various cache organizations with 2-9 percent error margins using only about 8 percent of the simulation time.

In this paper, we solve the problem of a joint optimal design of congestion control and wireless MAC-layer scheduling using a column generation approach with imperfect scheduling. We point out that the general subgradient algorithm has difficulty in recovering the time-share variables and experiences slower convergence. We first propose a two-timescale algorithm that can recover the optimal time-share values. Most existing algorithms have a component, called global scheduling, which is usually NP-hard. We apply imperfect scheduling and prove that if the imperfect scheduling achieves an approximation ratio rho, then our algorithm produces a suboptimum of the overall problem with the same approximation ratio. By combining the idea of column generation and the two-timescale algorithm, we derive a family of algorithms that allows us to reduce the number of times the global scheduling is needed.

A distinct trend has emerged that the Internet is used to transport data on a more and more massive scale. Capacity shortage in the backbone networks has become a genuine possibility, which will be more serious with fiber-based access. The problem addressed in this paper is how to conduct massive content distribution efficiently in the future network environment where the capacity limitation can equally be at the core or the edge. We propose a novel peer-to-peer technique as a main content transport mechanism to achieve efficient network resource utilization. The technique uses multiple trees for distributing different file pieces, which at the heart is a version of swarming. In this paper, we formulate an optimization problem for determining an optimal set of distribution trees as well as the rate of distribution on each tree under bandwidth limitation at arbitrary places in the network. The optimal solution can be found by a distributed algorithm. The results of the paper not only provide stand-alone solutions to the massive content distribution problem, but should also help the understanding of existing distribution techniques such as BitTorrent or FastReplica.

In data communication networks, packets that arrive at the receiving host may be disordered for reasons such as retransmission of dropped packets or multipath routing. Reliable protocols such as the Transmission Control Protocol (TCP) require packets to be accepted, i.e., delivered to the receiving application, in the order they are transmitted at the sender. In order to do so, the receiver's transport layer is responsible for temporarily buffering out-of-order packets and resequencing them as more packets arrive. In this paper, we analyze a model where the disordering is caused by multipath routing. Packets are generated according to a Poisson process. Then, they arrive at a disordering network (DN) modeled by two parallel M/M/l queues, and are routed to each of the queues according to an independent Bernoulli process. A resequencing buffer follows the DN. In such a model, the packet resequencing delay is known. However, the size of the resequencing queue (RSQ) is unknown. We derive the probability for the large deviations of the queue size.

To achieve high performance and resilience to failures, many peer-to-peer (P2P) systems have begun to use striping and collaborative downloading, where each peer can download the file or pieces of the file from a number of peers in parallel, and at the same time, serve them to some other peers. These P2P systems intrinsically involve many-to-many mappings from the servers to the clients (or peers to peers) as well as many-to-one mappings from the clients to the server. In this paper, we present a node selection algorithm that generates an optimal server set with respect to the worst link stress (WLS) criterion for a single client and evaluates its network performance metrics for many- to-many mappings and many-to-one mappings. Simulation results show that our system is simple yet effective in achieving the design goals. In particular, it minimizes the level of congestion at the bottleneck link, and it consumes less network resources in terms of total bandwidth usage. The objectives of this in-depth examination are to raise awareness and concern for these issues and to provide alternatives or improved designs that can be incorporated into many P2P systems.

Intelligent sharing cache space among multiple cores on a Chip Multiprocessor (CMP) has become an important research topic. There are many design options to trade off and many possible performance metrics to evaluate. It generally requires costly simulations to gain insights over a wide-spectrum of cache sharing and partitioning methods. In this paper, we use an efficient single-pass stack simulation method to understand the effectiveness of cache sharing through natural competition (i. e. shared cache) and through static or dynamic cache partitioning, such as equal partition, utility-based partition, etc. The results demonstrate that cache occupancy through natural competition favors the core with more frequently misses. It may take away the needed space for other cores and increase the overall miss ratio. Furthermore, we find that the existing cache partitioning schemes based on fixed-length portioning phases may not be optimal compared with the scheme that allows variable phase lengths.

In many networking applications such as file sharing, structured peer-to-peer networks are increasingly used in dynamic situations with fluctuating load, which require proper load balancing. The relationship between the network structure and its load-balancing properties has not been fully understood. In this paper, we focus on the Plaxton-type networks, which are broad enough to include Pastry, Tapestry, and hypercube. We first use hypercube as an example and demonstrate that replicating files at nodes in decreasing order of the length of the common prefix with the original server leads to perfectly balanced load, and does so fast and efficiently. Moreover, this replication strategy coincides with a simple on-demand replication/caching strategy based on the observed load. One of our main contributions is to show that such desirable properties also exist for a large class of random networks, which are less restrictive and more practical than the hypercube. More importantly, we have discovered a multiple-choice random network, which drastically reduces the statistical fluctuation of the load: The maximum load over all replication servers is at most three times the average load for systems of practical sizes. The main insight is that this algorithm is related to a variant of the multiple-choice balls-in-bins problem.

The future chip-multiprocessors (CMPs) with a large number of cores faces difficult issues in efficient utilizing on-chip storage space. Tradeoffs between data accessibility and effective on-chip capacity have been studied extensively. It requires costly simulations to understand a wide-spectrum of design spaces. In this paper, we first develop an abstract model for understanding the performance impact with respect to the degree of data replication. To overcome the lack of real-time interactions among multiple cores in the abstract model, we propose an efficient single-pass stack simulation method to study the performance of a variety of cache organizations on CMPs. The proposed global stack logically incorporates a shared stack and per-core private stacks to collect shared/private reuse (stack) distances for every memory reference in a single simulation pass. With the collected reuse distances, performance in terms of hits/misses and average memory access times can be calculated for multiple cache organizations. The basic stack simulation results can further derive other CMP cache organizations with various degrees of data replication. We verify both the modeling and the stack results against individual execution-driven simulations that consider realistic cache parameters and delays using a set of commercial multithreaded workloads. We also compare the simulation time saving with the stack simulation. The results show that stack simulation can accurately model the performance of various studied cache organizations with 2-9% error margins using only about 8% of the simulation time. The results also show that the effectiveness of various techniques for optimizing the CMP on-chip storage is closely related to the working sets of the workloads as well as the total cache sizes

The advancement of optical networking technologies has enabled e-science applications that often require transport of large volumes of scientific data. In support of such data-intensive applications, we develop and evaluate control plane algorithms for scheduling bulk file transfers, where each transfer has a start time and an end time. We formulate the scheduling problem as a special type of the multicommodity flow problem in which the time line is divided into uniform slices. Bandwidth is allocated to each job on every slice with the objective of improving throughput of the concurrent transfers. We study the effectiveness of using multiple time slices and multiple paths for each file transfer. We show that using a small number of paths per job is generally sufficient to achieve near optimal throughput with a practical execution time.

To achieve high performance and resilience to failures, a client can make connections with multiple servers simultaneously and receive different portions of the data from each server in parallel. However, selecting the best set of servers from the set of all nodes that have the desired data is not a straightforward task, and the obtained performance can dramatically vary depending on the constructed server set. In this paper, we present two server selection schemes that generate optimal server sets with respect to the degree of interference(DOI) criterion and the worst link stress(WLS) criterion in a structured peer-to-peer network. After examining the correctness of the algorithms, we present simulation results demonstrating the benefits of the optimal server selection schemes. Through the simulation results, we conclude that the optimal selection schemes perform better than the random server-selection scheme in the following aspects: (1) load-balancing in the network and the worst-case link stress, (2) network resource used by the connections, including the number of links and total bandwidth, (3) response time, and (4) throughput of TCP connections.

The ad hoc deployment of a sensor network causes unpredictable patterns of connectivity and varied node density, resulting in uneven bandwidth provisioning on the forwarding paths. When congestion happens, some sensors may have to reduce their data rates. It is an interesting but difficult problem to determine which sensors must reduce rates and how much they should reduce. This paper attempts to answer a fundamental question about congestion resolution: What are the maximum rates at which the individual sensors can produce data without causing congestion in the network and unfairness among the peers? We define the maxmin optimal rate assignment problem in a sensor network, where all possible forwarding paths are considered. We provide an iterative linear programming solution, which finds the maxmin optimal rate assignment and a forwarding schedule that implements the assignment in a low-rate sensor network. We prove that there is one and only one such assignment for a given configuration of the sensor network. We also study the variants of the maxmin fairness problem in sensor networks.

This paper studies the feasibility and algorithms for inferring the delay at each link in a communication network based on a large number of end-to-end measurements. The restriction is that we are not allowed to measure directly on each link and can only observe the route delays. It is assumed that we have considerable flexibility in choosing which routes to measure. We investigate two different cases: 1) each link delay is a constant and 2) each link delay is modeled as a random variable from a family of distributions with unknown parameters. We will answer whether such indirect inference is possible at all, and when possible, how it can be carried out. The emphasis is on developing the maximum-likelihood estimators for scenario 2) when the link delays are modeled by exponential random variables or mixtures of exponentials. We have derived solutions based on the EM algorithm and demonstrated that, even though they do not necessarily reflect the true model parameters, they do seem to maximize the likelihood in most cases and that the resulting probability density functions match the true functions on regions where the probability mass concentrates

Protocols such as TCP require packets to be accepted, i.e., delivered to the receiving application, in the order they are transmitted at the sender. Packets that arrive at the receiving host may be mis-ordered for reasons such as retransmission of dropped packets or multi-path routing. In order to deliver the arrived packets in sequence, the receiver's transport layer is responsible to temporarily buffer out-of-order packets and to resequence them as more packets arrive. We analyze a model where the mis-ordering is caused by multi-path routing. Packets are generated according to a Poisson process. Then, they arrive at a disordering network modelled by two parallel M/M/1 queues, and are routed to each of the queues according to an independent Bernoulli process. A resequencing buffer follows the disordering network. In such a model, the packet resequencing delay is known. However, the size of the resequencing queue is unknown. We derive the probability for the large deviation of the queue size.

Protocols such as TCP require packets to be accepted (i.e., delivered to the receiving application) in the order they are transmitted at the sender. Packets are sometimes mis-ordered in the network. In order to deliver the arrived packets to the application in sequence, the receiver's transport layer needs to temporarily buffer out-of-order packets and resequence them as more packets arrive. Even when the application can consume the packets infinitely fast, the packets may still be delayed for resequencing. In this paper, we model packet mis-ordering by adding an IID random propagation delay to each packet and analyze the required buffer size for packet resequencing and the resequencing delay for an average packet. We demonstrate that these two quantities can be significant and show how they scale with the network bandwidth.

The increasing presence of UDP traffic in the Internet and the emergence of sensing applications which do not require full reliability motivates the search for a robust acknowledgement scheme for unreliable flows. TCP-styled cumulative ack relies on the eventual retransmission of all lost packets and hence cannot be used for unreliable flows. Our contribution is the design and analysis of a simple, yet robust acknowledgement scheme for unreliable flows. We show that our scheme achieves good performance even when the actual network conditions deviate from the designer's estimate. It works in networks having orders of magnitude difference in bandwidth and loss probability, with little variation of overhead and no change to the algorithms.

A central issue in congestion control for available bit rate (ABR) services is the computation of the fair share for every connection at each switching node in the network. An important class of algorithms for the switch behavior computes the fair share according to the exact definition of max-min fairness, and uses it as the explicit rate conveyed to the sources. These algorithms may encounter difficulties due to the complex task of keeping track of active connections. In addition, since these schemes treat all connections equally, they lead to under-utilization of the link capacity when on-off sources are present in the network. To obviate these shortcomings, it has been proposed to use the traffic load to correct the computed fair share when setting the explicit rate. In this paper, first we show that using the traffic load as suggested in literature inherently perturbs rate allocation, and makes the schemes sensitive to the round-trip delay of the connections, leading to unfairness. Then, we introduce a scheme called the enhanced fast max-min rate allocation (E-FMMRA) algorithm, which solves the problem by keeping track of the maximum explicit rate over all backward RM cells. The same technique used in E-FMMRA can also be applied to the popular explicit rate indication for congestion avoidance (ERICA) scheme to solve similar problems associated with the use of the traffic load.

Several algorithms have been proposed for the switch behavior for congestion control of available bit rate (ABR) services. Schemes such as the enhanced proportional rate control algorithm (EPRCA) and the dynamic max rate control algorithm (DMRCA), which use the queue length as the congestion indicator to make a simple approximation of the fair share converge to the actual fair share, have become popular, because they offer a good performance and are simple to implement. In particular, with no VBR traffic in the network, DMRCA has been shown to achieve fairness in all situations, good buffer control, and robust performance. First we show that the performance of these schemes may degrade when ABR traffic interacts with highly-bursty VBR traffic. If VBR traffic induces congestion in the network, the length of the ABR queue cannot serve as a reliable indicator of congestion caused by ABR traffic, and the schemes perform poorly, introducing considerable unfairness. Then, we propose a simple technique to solve these problems. The switch constructs the length of a virtual queue which is not affected by the instantaneous behavior of VBR traffic, and does not depend on how the two types of traffic are served in order to share the common link capacity; thus, it can serve as a reliable indicator of congestion. We use this technique in DMRCA with virtual queueing (DMRCA-VQ), and show that the new scheme achieves fair rate allocation to the ABR connections also in the presence of highly-bursty VBR traffic. The DMRCA-VQ maintains the low hardware complexity of DMRCA. The virtual queueing technique is a solution for the more general problem of separating rate allocation based on the queue length from scheduling of multiple queues for sharing a common resource.

We study shared-memory switches under multicast bursty traffic and characterize the relation between their performance and the multicast distribution that defines the mix of multicast traffic arriving at the switches. We consider two schemes that have been used in practical realizations of these switches to replicate multicast cells: (1) replication-at-receiving (RAR), where multiple copies of a multicast cell are stored in the buffer and served independently, and (2) replication-at-sending (RAS), where a single instance of a multicast cell is stored in the buffer, and the cell is replicated as it is transmitted to the output ports. For each scheme, we study two configurations: (1) the shared-memory-only (SMO) configuration, where the bandwidth of the replication mechanism is sufficient to accommodate even the worst-case replication requirements, and (2) the shared-memory-with-replication-first-in-first-out (SM+RFIFO) configuration, where the bandwidth of the replication mechanism is lower than that required by the worst case, and thus an additional buffer is used in front of the shared memory to temporarily store cells while they are replicated. For all cases, using simulation, we find upper bounds for the buffer requirements to achieve a desired cell-loss rate. We show that these upper bounds are significantly larger than the buffer requirements under unicast traffic and are approached even for very small volumes of multicast traffic; thus, these upper bounds should be used in practice to size the buffers to achieve the desired performance under traffic with general multicast distributions. We also study shared-memory switches with output demultiplexers and characterize and compare the different multicasting schemes that are used in these switches.

We study a shared-memory center-stage switch with input multiplexers and output demultiplexers, where backpressure is applied from the demultiplexers to the center stage, and from the center stage to the multiplexers. We consider three backpressure schemes: (i) non-selective backpressure (NSB), where a congested center stage or a congested demultiplexer applies backpressure indiscriminately to all the traffic destined to it, regardless of the destination; (ii) per-port selective backpressure (PPSB), where the center stage applies backpressure selectively only to the traffic destined to the center-stage port(s) experiencing congestion, but a demultiplexer applies backpressure indiscriminately to all the traffic destined to it; and (iii) per-subport selective backpressure (PSSB), where both center-stage switch and demultiplexers apply backpressure selectively only to the traffic destined to the output link(s) experiencing congestion. We show that NSB introduces heavy HOL blocking which limits the throughput of the system and causes heavy losses. On the contrary, PPSB and PSSB achieve high throughputs, and allow one to increase buffer utilization in the system while keeping the majority of the buffers physically separate in the input multiplexers. Both these schemes perform very well in the case where only limited sharing of the buffers in the center stage is allowed, as required to guarantee fairness in the switch. With PSSB, small buffer sizes in the demultiplexers can be used. If the buffers in the demultiplexers are large, PPSB and PSSB offer comparable performance.