Platooning is considered as a promising technology in reducing fuel consumption, improving flow capacity to the future intelligent transportation system. Effective platoon control to maintain a stable platoon relies heavily on the vehicular communication performance. However, network resources become more limited due to the rapid growth in communication devices, and how limited network resources can be utilized to satisfy the platoon control demand becomes an emerging issue. To address this issue, in this paper, we investigate the problem of joint platoon control and resource allocation. Firstly, we model the relation between resource allocation and platoon control requirement based on the error bound and error correction ability. Non-orthogonal multiple access (NOMA) is introduced to support multiple vehicular users sharing a time slot, which improves resource utilization. A distributed control policy is applied based on the state estimation. Then, we propose an optimization problem to minimize total power consumption with control-related communication requirements and a two-staged algorithm to solve it. In the first stage, user scheduling is performed according to platoon control demands. With user scheduling determined, power allocation problem is directly solved in the second stage based on the NOMA decoding order. Finally, the result of experiments demonstrates that our proposed method is efficient in utilizing network resources to achieve effective platoon control.

Non-orthogonal multiple access (NOMA) has become a promising candidate aiming to enhance the system performance in the fifth generation of wireless communication. However, most existing studies on the resource allocation of NOMA systems only consider the short-term performance improvement but ignore the problems caused by the imperfect time-varying channels and the dynamic traffic arrivals, which will result in unsuccessful transmission issues. Different from the existing approaches, we propose a long-term cross-layer resource allocation model with dynamic traffic arrivals and limited channel information. With the low-overhead one-bit feedback, the optimal decoding order, user scheduling, and power allocation are analyzed. Specifically, the problem is formulated as a stochastic optimization framework to minimize long-term power consumption. By applying the Lyapunov optimization framework, the problem can be transformed into a joint traffic rate control and mixed-integer programming resource allocation problem. This NP-hard problem is difficult to be solved directly. Therefore, we devise an efficient sub-optimal algorithm with the dynamic penalty factor. In our theoretical analysis, we prove that the delay-power tradeoff can be achieved by tuning a control parameter. The simulation results confirm that our proposed algorithms can efficiently reduce the power consumption compared with the baseline algorithms while satisfying the QoS requirements.

In a smart grid integrated with vehicle-to-grid (V2G) technique, electric vehicles (EVs) fleets under effective coordination can be considered as a massive aggregated power storage to provide frequency regulation service. In this article, we propose a hierarchical system model to jointly optimize power flow routing and V2G scheduling for providing regulation service. First of all, by installing power flow routers (PFRs) inside the power grid, we formulate the problem of optimal power flow (OPF) routing at the grid level. Through the utilization of the semidefinite programming (SDP) relaxation, we can transform the original non-deterministic polynomial-time hard (NP-hard) problem into a convex problem. The tree decomposition method is then used to further reduce the complexity of the system network. After solving the grid-level OPF routing problem, a forecast-based scheduling problem is formulated at the EV level to coordinate EVs by providing the V2G regulation service. To cope with the forecast uncertainties, an online scheduling problem is in turn formulated. In order to solve these problems in a scalable manner, decentralized algorithms are then devised to control the EV schedules. The simulation results show that the devised online scheduling algorithm can outperform the existing algorithms, which is able to flatten the power fluctuations at the buses with EVs attached. Additionally, we show that grid stability issue can be alleviated through the proposed model. Finally, for different power systems, the uses of PFRs can reduce the system power loss in a great manner while providing voltage regulation.

As an essential role in the intelligent transportation system, the vehicle platoon-based system meets tremendous challenges in guaranteeing low-latency communication for vehicles with dynamic channel information and high mobility. To handle the challenges, non-orthogonal multiple access (NOMA) has been considered as a promising candidate to improve the system capacity and spectrum efficiency. However, it is still an open issue on how to organize multiple transmission links with suitable resource allocation. In this paper, we investigate the problem of the resource allocation for the NOMA-enabled vehicle platoon-based vehicle-to-everything (V2X) system. First, an optimization problem is formulated to jointly consider the resource allocation on vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) links, while satisfying the quality-of-service (QoS) requirements for each vehicle, including the delay requirements, rate demands, and power constraints. To cope with the nonconvex problem, a fractional programming-based transformation is used, and an iterative resource allocation algorithm is proposed to find the solution. The numerical results indicate that our proposed algorithm can significantly reduce the system delay compared with other methods while satisfying the QoS requirements, so as to tackle the latency issues for vehicle platoon-based V2X communications.

Bufferbloat is a phenomenon in computer networks where large router buffers are frequently filled up, resulting in high queueing delay and delay variation. More and more delay-sensitive applications on the Internet have made this phenomenon a pressing issue. Interacting with the Transmission Control Protocol (TCP), active queue management (AQM) algorithms run on routers play an important role in combating bufferbloat. However, AQM algorithms have not been widely deployed due to complicated manual parameter tuning. Moreover, they are often designed and analyzed based on network models with a single bottleneck link, rendering their performance and stability unclear in multi-bottleneck networks. In this paper, we propose a general framework to combat bufferbloat in multi-bottleneck networks. We first present an equilibrium analysis for a general multi-bottleneck TCP/AQM system and provide sufficient conditions for the uniqueness of an equilibrium point in the system. We then decompose the system into single-bottleneck subsystems and derive sufficient conditions for the local asymptotic stability of the subsystems. Using our framework, we develop an algorithm to compute the equilibrium point of the system. We further present a case study to analyze the stability of the recently proposed Controlled Delay (CoDel) in multi-bottleneck networks and devise Self-Tuning CoDel to improve the system stability. Extensive numerical and packet-level simulation results not only verify our theoretical studies but also show that our proposed Self-Tuning CoDel significantly stabilizes queueing delay in multi-bottleneck networks, thereby mitigating bufferbloat.

Non-orthogonal multiple access (NOMA) has become a potential candidate to satisfy the heterogeneous demands in the fifth generation of wireless communication systems. With the optimization on the resource allocation, NOMA can further enhance the system performance. This paper proposes a cross-layer resource allocation framework for downlink NOMA systems. The problem is formulated as a stochastic problem to minimize the long-term total power consumption with dynamic traffic arrivals and time-varying channel under limited feedback. Then, this problem can be transformed to a rate control problem and a mixed-integer programming resource allocation problem solved at each time slot based on the Lyapunov optimization. To reduce the computational complexity, we devise an efficient suboptimal resource allocation algorithm with the dynamic penalty factor. The simulation results show that our proposed algorithms can reduce the power consumption compared with the two baseline algorithms while satisfying the QoS requirements.

Aspect-based (aspect-level) sentiment analysis is an important task in fine-grained sentiment analysis, which aims to automatically infer the sentiment towards an aspect in its context. Previous studies have shown that utilizing the attention-based method can effectively improve the accuracy of the aspect-based sentiment analysis. Despite the outstanding progress, aspect-based sentiment analysis in the real-world remains several challenges. (1) The current attention-based method may cause a given aspect to incorrectly focus on syntactically unrelated words. (2) Conventional methods fail to identify the sentiment with the special sentence structure, such as double negatives. (3) Most of the studies leverage only one vector to represent context and target. However, utilizing one vector to represent the sentence is limited, as the natural languages are delicate and complex. In this paper, we propose a knowledge guided capsule network (KGCapsAN), which can address the above deficiencies. Our method is composed of two parts, a Bi-LSTM network and a capsule attention network. The capsule attention network implements the routing method by attention mechanism. Moreover, we utilize two prior knowledge to guide the capsule attention process, which are syntactical and n-gram structures. Extensive experiments are conducted on six datasets, and the results show that the proposed method yields the state-of-the-art.

The vehicle-to-grid (V2G) technique, which enables the bidirectional power exchange between electric vehicles (EVs) and power grid, becomes promising in current smart grid research. In this paper, a game theoretic model is proposed to study the interaction among EVs in a V2G system with V2G technique incorporated. This V2G game is a game with imperfect information in which each EV does not any private information of other EVs. To find the Nash equilibrium of this game, a machine learning-based algorithm is proposed based on fictitious self-play. Our simulation results show that the proposed algorithm can approximately converge to the Nash equilibrium of the game under imperfect information. This demonstrates the efficacy of the proposed algorithm in solving the V2G game. A pre-training approach is also proposed to accelerate the convergence of the algorithm by using the historical data from the interactions of EVs in the game.

The vehicle-to-grid (V2G) technique, which utilizes electric vehicles (EVs) to provide ancillary services for power grid, becomes promising in current smart grid research. In this paper, a game theoretic approach is proposed to motivate EVs to provide frequency regulation services for power grid. The interaction between the EV aggregator and EVs is formulated as a Stackelberg game. We find that the Stackelberg game admits a unique equilibrium solution, and the existence and uniqueness of the Nash equilibrium are validated. Algorithms have been devised for finding the Nash equilibrium of the game. Our simulation results show that the proposed game theoretic V2G scheduling approach can motivate EVs to schedule their charging/discharging activities so as to smooth out the power fluctuations from the grid while maximizing their own utilities. This demonstrates the effectiveness of the use of the V2G game in providing regulation service to the grid.

Bufferbloat is a phenomenon where router buffers are constantly being filled, resulting in high queueing delay and delay variation. Larger buffer size and more delay-sensitive applications on the Internet have made this phenomenon a pressing issue. Active queue management (AQM) algorithms, which play an important role in combating bufferbloat, have not been widely deployed due to complicated manual parameter tuning. Moreover, AQM algorithms are often designed and analyzed based on models with a single bottleneck link, rendering their performance and stability unclear in multi-bottleneck networks. In this paper, we propose a general framework to combat bufferbloat in multi-bottleneck networks. We first conduct an equilibrium analysis for a general multi-bottleneck TCP/ AQM system and develop an algorithm to compute the equilibrium point. We then decompose the system into single-bottleneck subsystems and derive sufficient conditions for the local asymptotic stability of the subsystems. Using the proposed framework, we present a case study to analyze the stability of the recently proposed Controlled Delay (CoDel) in multi-bottleneck networks and devise Self-tuning CoDel to improve the system stability and performance. Extensive simulation results show that Self-tuning CoDel effectively stabilizes queueing delay in multi-bottleneck scenarios, and thus contributes to combating bufferbloat.

In recent years, the vehicle-to-grid (V2G) system, which utilizes electric vehicles (EVs) to provide ancillary services for power grid, draws a lot of interests in smart grid research community. When considering a large number of EVs distributed in different geographical locations, how to coordinate these EVs to provide ancillary services becomes a critical issue. In this paper, a generic hierarchical framework for V2G system to provide frequency regulation services is proposed to address this issue. A practical multi-level online V2G algorithm is proposed for the hierarchical V2G scheduling and it requires no forecasting information for regulation signals.We test our proposed algorithm in the simulation of a four- level hierarchical V2G system. The results show that the proposed algorithm has advantages over the existing methods on smoothing out the real- time power fluctuations.

The renewables will constitute an important part of the future smart grid. As a result, the growing portion of renewable generation in the power grid will bring challenges to the operations of the power grid because of the fluctuation and intermittency properties of renewables. In order to make the operations of power grid stable and reliable, the power outputs from renewable energy sources must be smoothed. In this paper, we propose a scheme inspired from the idea of the leaky bucket mechanism for smoothing the power output from a renewable energy system. In our proposed method, the settings of energy storage size and power output level have significant effects on the system performance and thus needs to be determined. An optimization framework is thus proposed for storage and power output planning of the renewable energy system. To operate our proposed scheme practically, a load-adaptive power smoothing algorithm is devised aiming to match the power output level with the actual load in the grid. Our simulation studies show that the proposed algorithm can reduce the operation cost comparing to other algorithms and maintain high renewable energy utilization.

Microgrids (MGs) bring considerable advantages in improving reliability, reducing cost, and integrating renewable energy to the future electricity system. However, proper coordination among MGs with renewable resources is necessary for improving the penetration of renewables. In this paper, we propose an adaptive distributed energy scheduling scheme, known as DOPS, for MG cooperation in order to reduce the time-averaged operation cost and improve the utilization of renewable energy (RE) resources. In order to fully utilize the generated RE, a time-averaged RE utilization constraint is proposed and virtual queue technology is utilized to deal with the constraint. Because it is impossible to get the precise information of the future RE generation and load, we make use of Lyapunov optimisation to design the online algorithm for DOPS. Besides, we prove that DOPS can achieve a near-to-optimal performance in terms of the system cost. Furthermore, a trade-off between operation cost and battery size is derived. In the end, our simulation results show that DOPS can help reduce the operation cost and improve the utilization of RE dramatically.

Relaying is a promising technique in cellular networks for improving system capacity and coverage. To facilitate the deployment of relays in remote areas without ready access to the electrical grid, energy-harvesting relays may be deployed. Energy-harvesting has been studied extensively for sensor networks, but it is still an open problem for cellular networks. In this paper, we study the problem of the joint allocation of orthogonal frequency division multiplexing access resource blocks and transmission power to users in a cellular network with energy-harvesting relays. The energy-harvesting process is stochastically described by a time-varying Poisson process. We propose a new metric called survival probability as the selection criteria for an energy-harvesting relay to support data transmissions. We propose a survival probability-based resource allocation (SPRA) algorithm. The algorithm solves the joint problem of resource block allocation, power control, and associating relays to users in a cellular network. We show the achievable data rates of SPRA for different energy harvesting rates.

We investigate bandwidth allocation and scheduling in non-cooperative wireless networks as a mixed integer programming problem. Fast Vickrey-Clarke-Groves (VCG) auction-based bandwidth allocation (FABA), incorporating relaxation-based greedy algorithm (RGA) and split-flow-based algorithm (SFA), is proposed by modifying the traditional VCG auction to make it computationally feasible. With incentives provided by FABA, the dominant strategy of any selfish node in the network is to be cooperative so that the system cost is minimized. We implement FABA via a batching-based mechanism which allocates bandwidth for all call routing requests arriving in a certain batching period simultaneously. Our simulation evaluates the performance in terms of system cost, payment-cost ratio, and setup time.

The combination of loss-based TCP and drop-tail routers often results in full buffers, creating large queueing delays. The challenge with parameter tuning and the drastic consequence of improper tuning have discouraged network administrators from enabling AQM even when routers support it. To address this problem, we propose a novel design principle for AQM, called the pricing-link-by-time (PLT) principle. PLT increases the link price as the backlog stays above a threshold β, and resets the price once the backlog goes below β. We prove that such a system exhibits cyclic behavior that is robust against changes in network environment and protocol parameters. While β approximately controls the level of backlog, the backlog dynamics are invariant for β across a wide range of values. Therefore, β can be chosen to reduce delay without undermining system performance. We validate these analytical results using packet-level simulation.

Topology-transparent scheduling algorithms can work well in mobile ad hoc networks, since they are oblivious to the network topology changes and can provide throughput and delay guarantees. Recently, it has been shown that topology-transparent algorithms can provide comparable or even better performance, compared to topology-dependent algorithms. However, most existing topology-transparent scheduling algorithms are designed for single channel networks and few work have been done in multi-channel (MC) networks. In this paper, we focus on broadcasting and propose a distributed multi-channel topology-transparent broadcast scheduling algorithm. In our algorithm, each node randomly selects one or several subchannels to transmit and utilizes both assigned and unassigned slots efficiently. We study the performance of our algorithm analytically and obtain the optimal number of selected subchannels that maximizes the throughput. The simulation results show that our proposed algorithm outperforms existing multi-channel topology-transparent broadcast scheduling algorithms dramatically. More importantly, our work answers the question “Will dividing the spectrum into subchannels lead to a better network performance?” under different network configurations.

In a vehicle-to-grid (V2G) system, aggregators coordinate the charging/discharging schedules of electric vehicle (EV) batteries so that they can collectively form a massive energy storage system to provide ancillary services, such as frequency regulation, to the power grid. In this paper, the optimal charging/discharging scheduling between one aggregator and its coordinated EVs for the provision of the regulation service is studied. We propose a scheduling method that assures adequate charging of EVs and the quality of the regulation service at the same time. First, the scheduling problem is formulated as a convex optimization problem relying on accurate forecasts of the regulation demand. By exploiting the zero-energy nature of the regulation service, the forecast-based scheduling in turn degenerates to an online scheduling problem to cope with the high uncertainty in the forecasts. Decentralized algorithms based on the gradient projection method are designed to solve the optimization problems, enabling each EV to solve its local problem and to obtain its own schedule. Our simulation study of 1000 EVs shows that the proposed online scheduling can perform nearly as well as the forecast-based scheduling, and it is able to smooth out the real-time power fluctuations of the grid, demonstrating the potential of V2G in providing the regulation service.

Precomputation of the supported QoS is very important for internet routing. By constructing routing tables before a request arrives, a packet can be forwarded with a simple table lookup. When the QoS information is provided, a node can immediately know whether a certain request can be supported without launching the path finding process. Unfortunately, as the problem of finding a route satisfying two additive constraints is NP-complete, the supported QoS information can only be approximated using a polynomial time mechanism. A good approximation scheme should reduce the error in estimating the actual supported QoS. Nevertheless, existing approaches which determine this error may not truly reflect the performance on admission control, meaning whether a request can be correctly classified as feasible or infeasible. In this paper, we propose using a novel metric, known as distortion area , to evaluate the performance of precomputing the supported QoS. We then analyze the performance of the class of algorithms that approximate the supported QoS through discretizing link metrics. We demonstrate how the performance of these schemes can be enhanced without increasing complexity. Our results serve as a guideline on developing discretization-based approximation algorithms.

Recent advances in the physical layer have enabled wireless devices to have multiple packet reception (MPR) capability, which is the capability of decoding more than one packet, simultaneously, when concurrent transmissions occur. In this paper, we focus on the interaction between the MPR physical layer and the medium access control (MAC) layer. Some random access MAC protocols have been proposed to improve the network performance by exploiting the powerful MPR capability. However, there are very few investigations on the schedule-based MAC protocols. We propose a novel m-MPR-l-code topology-transparent scheduling ((m, l)-TTS) algorithm for mobile ad hoc networks with MPR, where m indicates the maximum number of concurrent transmissions being decoded, and l is the number of codes assigned to each user. Our algorithm can take full advantage of the MPR capability to improve the network performance. The minimum guaranteed throughput and average throughput of our algorithm are studied analytically. The improvement of our (m, l)-TTS algorithm over the conventional topology-transparent scheduling algorithms with the collision-based reception model is linear with m. The simulation results show that our proposed algorithm performs better than slotted ALOHA as well.

The congestion control mechanisms in the standardized Transmission Control Protocol (TCP) may misinterpret packet reordering as congestive loss, leading to spurious congestion response and under-utilization of network capacity. Therefore, many TCP enhancements have been proposed to better differentiate between packet reordering and congestive loss, in order to enhance the reordering robustness (RR) of TCP. Since such enhancements are incrementally deployed, it is important to study the interactions of TCP flows with heterogeneous RR. This paper presents the first systematic study of such interactions by exploring how changing RR of TCP flows influences the bandwidth sharing among these flows. We define the quantified RR (QRR) of a TCP flow as the probability that packet reordering causes congestion response. We analyze the variation of bandwidth sharing as QRR changes. This leads to the discovery of several interesting properties. Most notably, we discover the counter-intuitive result that changing one flow's QRR does not affect its competing flows in certain network topologies. We further characterize the deviation, from the ideal case of bandwidth sharing, as RR changes. We find that enhancing RR of a flow may increase, rather than decrease, the deviation in some typical network scenarios.

The class of additive-increase/multiplicative-decrease (AIMD) algorithms constitutes a key mechanism for congestion control in modern communication networks, like the current Internet. The algorithmic behaviour may, however, be distorted when wireless links are present. Specifically, spurious window reductions may be triggered due to packet reordering and non-congestive loss. In this paper, we develop a framework for AIMD in TCP to analyze the aforementioned problem. The framework enables a systematic analysis of the existing AIMD-based TCP variants and assists in the design of new TCP variants. It classifies the existing AIMD-based TCP variants into two main streams, known as compensators and differentiators, and develops a generic expression that covers the rate adaptation processes of both approaches. It further identifies a new approach in enhancing the performance of TCP, known as the compensation scheme. A tax-rebate approach is proposed as an approximation of the compensation scheme, and used to enhance the AIMD-based TCP variants to offer unified solutions for effective congestion control, sequencing control, and error control. In traditional wired networks, the new family of TCP variants with the proposed enhancements automatically preserves the same inter-flow fairness and TCP friendliness. We have conducted a series of simulations to examine their performance under various network scenarios. In most scenarios, significant performance gains are attained.

We study multi path routing with traffic assignment in selfish networks. Based on the Vickrey-Clarke-Groves (VCG) auction, an optimal and strategy-proof scheme, known as optimal auction-based multipath routing (OAMR), is developed. However, OAMR is computationally expensive and cannot run in real time when the network size is large. Therefore, we propose sequential auction-based multi path routing (SAMR). SAMR handles routing requests sequentially using some greedy strategies. In particular, with reference to the Ausubel auction, we develop a water-draining algorithm to assign the traffic of a request among its available paths and determine the payment of the transmission in approximately constant time. Our simulation results show that SAMR can rapidly compute the allocations and payments of requests with small sacrifice on the system cost. Moreover, various sequencing strategies for sequential auction are also investigated.

In order to maintain a small, stable backlog at the router buffer, active queue management (AQM) algorithms drop packets probabilistically at the onset of congestion, leading to backoffs by Transmission Control Protocol (TCP) flows. However, wireless losses may be misinterpreted as congestive losses and induce spurious backoffs. In this paper, we raise the basic question: Can AQM maintain a stable, small backlog under wireless losses? We find that the representative AQM, random early detection (RED), fails to maintain a stable backlog under time-varying wireless losses. We find that the key to resolving the problem is to robustly track the backlog to a preset reference level, and apply the control-theoretic vehicle, internal model principle, to realize such tracking. We further devise the integral controller (IC) as an embodiment of the principle. Our simulation results show that IC is robust against time-varying wireless losses under various network scenarios.

Transmission scheduling is a key problem in mobile ad hoc networks. Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time-division multiple-access (TDMA) frame length in mobile ad hoc networks. Most algorithms are dependent on the exact network topology and cannot adapt to the dynamic topology in a mobile wireless network. To overcome this limitation, several topology-transparent scheduling algorithms have been proposed. The slots are assigned to guarantee that there is at least one collision-free time slot in each frame. In this paper, we consider multicast and broadcast, and propose a novel topology-transparent distributed scheduling algorithm. Instead of guaranteeing at least one collision-free transmission, the proposed algorithm guarantees one successful transmission exceeding a given probability, and achieves a much better average throughput. The simulation results show that the performance of our proposed algorithm is much better than the conventional TDMA and other existing algorithms in most cases.

In this paper, we develop a new scheme to effectively detect the primary signal in a cognitive radio (CR) network. We propose a packet transmission scheme with random censoring. The proposed scheme, known as Censored with Probability Fusion Method~(CPFM), controls the information exchange in cooperative spectrum sensing so as to improve the detection performance and reduce the cooperation overheads. In CPFM, each participating CR device independently senses the spectrum. Based on the energy level received, it may transmit, not transmit, or randomly transmit its observation packet to the fusion centre. The fusion centre then determines the spectrum condition based on all packets received. The simulation results show that CPFM outperforms other detection schemes in terms of improved detection probability and smaller control overheads.

Transmission scheduling is a key design problem in wireless multi-hop networks. Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time division multiple access (TDMA) frame length. Most of the scheduling algorithms are topology-dependent. They are generally graph-based and depend on the exact network topology information. Thus, they cannot adapt well to the dynamic wireless environment. In contrast, topology-transparent TDMA scheduling algorithms do not need detailed topology information. However, these algorithms offer very low minimum throughput. The objective of this work is to propose an adaptive topology-transparent scheduling algorithm to offer better throughput performance. With our algorithm, each node finds a transmission schedule so as to reduce the transmission conflicts and adapt better to the changing network environment. The simulation results show that the performance of our algorithm is better than the existing topology-transparent algorithms.

In wireless networks, TCP performs unsatisfactorily since packet reordering and random losses may be falsely interpreted as congestive losses. This causes TCP to trigger fast retransmission and fast recovery spuriously, leading to under-utilization of available network resources. In this paper, we propose a novel TCP variant, known as TCP for non-congestive loss (TCP-NCL), to adapt TCP to wireless networks by using more reliable signals of packet loss and network overload for activating packet retransmission and congestion response, separately. TCP-NCL can thus serve as a unified solution for effective congestion control, sequencing control, and loss recovery. Different from the existing unified solutions, the modifications involved in the proposed variant are limited to sender-side TCP only, thereby facilitating possible future wide deployment. The two signals employed are the expirations of two serialized timers. A smart TCP sender model has been developed for optimizing the timer expiration periods. Our simulation studies reveal that TCP-NCL is robust against packet reordering as well as random packet loss while maintaining responsiveness against situations with purely congestive loss.

Transmission scheduling is a key design problem in wireless multi-hop networks. Many transmission scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time division multiple access (TDMA) frame length. There exists some interesting scheduling algorithms called topology-transparent TDMA scheduling algorithms, which do not require the detailed topology information, and are suitable for the wireless environment. However, a framework to compare the performance of these algorithms properly and fairly is still lacking. The objective of this work is to propose a uniform framework for topology-transparent scheduling algorithms. Under some fundamental constraints, an optimal solution is provided to the scheduling problem of topology-transparent algorithms. Furthermore, under the proposed framework, we analyze the relationship among all existing topology-transparent algorithms. We then develop an adaptive topology-transparent algorithm, which can always give an optimal solution under a set of the system design parameters.

In this paper, we present a model to analyze the performance of three transmission strategies with smart antennas, i.e. directional antennas with adjustable transmission power. Generally, a larger transmission radius contributes a greater progress if a transmission is successful. However, it has a higher probability of collision with other concurrent transmissions. Smart antennas mitigate collisions with sectorized transmission ranges. They also extend the transmission radii. By modelling three transmission strategies, namely, Nearest with Forward Progress (NFP), Most Forward with Fixed Radius (MFR), and Most Forward with Variable Radius (MVR), our analysis illustrates that the use of smart antennas can greatly reduce the possibility of conflicts. The model considers the interference range and computes the interference probability for each transmission strategy. We have analyzed two Medium Access Control (MAC) protocols using our interference model, namely, the slotted ALOHA protocol and the slotted CSMA/CA-like protocol. The result shows that, for slotted ALOHA, NFP yields the best one-hop throughput, whereas MVR provides the best average forward progress. The overall performance is substantially improved with the slotted CSMA/CA-like protocol, and the network becomes more resilient.

In this paper, we study the problem of computing the supported QoS from a source to a destination with multiple additive constraints. The problem has been shown to be NP-complete and many approximation algorithms have been developed. We propose a new approximation algorithm called multi-dimensional relaxation algorithm. We formally prove that our algorithm produces smaller approximation error than the existing algorithms. We further verify the performance by extensive simulations.

In this paper, we consider the problem of routing with two additive constraints in the hierarchical networks, such as the Internet. In order for scalability, the supported QoS information in the hierarchical networks has to be aggregated. We propose a novel method for aggregating the QoS information. To the best of our knowledge, our approach is the first study to use the area-minimization optimization, the de facto optimization problem of the QoS information aggregation. We use a set of real numbers to approximate the supported QoS between different domains. The size of the set is predefined so that advertisement overhead and the space requirement will not grow exponentially as the network size grows. The simulation results show that the proposed method outperforms the existing methods.

The problems of TCP packet reordering and random loss over wireless networks have motivated the development of a number of TCP variants. However, most of these variants focus on resolving only one of the aforementioned two problems. A few unified solutions for both problems generally extend beyond the scope of the transport layer. In this paper, we propose a new TCP variant, known as TCP for non-congestion loss (TCP-NCL), to tackle both problems under one compact framework. Different from previous unified solutions, the modifications are limited to sender-side TCP only, thereby facilitating possible future wide deployment. A retransmission decision timer and a congestion response decision timer have been installed to trigger packet retransmission and congestion response, respectively. Our simulation studies reveal that TCP-NCL is robust against packet reordering as well as random packet loss while maintaining responsiveness against situations with purely congestive loss.

In this paper, we present a model to analyze the performance of wireless ad hoc networks with smart antennas, i.e. directional antennas with adjustable transmission power. Our results show that smart antennas can improve the network performance by mitigating the effects of interference. We illustrate our model with the NFP (Nearest with Forward Progress) transmission strategy. Our analytical and simulation results show that, for ad hoc networks with smart antennas, NFP yields good throughput and remains stable as the node density varies.

Transmission scheduling is a key design problem in wireless multi-hop networks and many scheduling algorithms have been proposed to maximize the spatial reuse and minimize the time-division multiple- access (TDMA) frame length. Most of scheduling algorithms are graph-based, dependent on the exact network topology information and cannot adapt to the dynamic wireless environment. Some topology-independent TDMA scheduling algorithms have been proposed, and do not need accurate topology information. Our proposed algorithm follows a similar approach but with a different design strategy. Instead of minimizing the TDMA frame length, we maximize the minimum expected throughput, and we consider multicasting and broadcasting. The simulation result shows that the performance of our algorithm is better than the conventional TDMA and other existing algorithms in most cases.

Routing is a process of finding a network path from a source node to a destination node. A good routing protocol should find the "best path" from a source to a destination. When there are independent constraints to be considered, the "best path" is not well-defined. In our previous work, we developed a line segment representation for Quality-of-Service routing with bandwidth and delay requirements. In this paper, we propose how to adopt the line segment when a request has two concave constraints. We have developed a series of operations for constructing routing tables under the distance-vector protocol. We evaluate the performance through extensive simulations.

In this paper, we introduce a framework for distributed opportunistic scheduling in multihop wireless ad hoc networks. With the proposed framework, one can take a scheduling algorithm originally designed for infrastructure-based wireless networks and adapt it to multihop ad hoc networks. The framework includes a wireless link state estimation mechanism, a medium access control (MAC) protocols and a MAC load control mechanism. The proposed link state estimation mechanism accounts for the latest results of packet transmissions on each wireless link. To improve robustness and provide service isolation during channel errors, the MAC protocol should not make any packet retransmissions but only report the transmission result to the scheduler. We modify IEEE 802.11 to fulfill these requirements. The MAC load control mechanism improves the system robustness. With link state information and the modified IEEE 802.11 MAC, we use BGFS-EBA, an opportunistic scheduling algorithm for infrastructured wireless networks, as an example to demonstrate how such an algorithm is converted into its distributed version within the proposed framework. The simulation results show that our proposed method can provide robust outcome fairness in the presence of channel errors.

The problem of finding a path that satisfies two additive constraints, such as delay and cost, has been proved to be NP-complete. Many heuristic and approximation algorithms have been developed to identify a path given a certain QoS request. Unfortunately, these algorithms cannot be applied directly in the Internet because routing in the Internet is based on table lookups and routing tables are computed before a request arrives. In this paper, we develop an approximation algorithm for computing the supported QoS going across a domain. We analyze the approximation error of our algorithm and formally prove that the approximation error of our proposed algorithm is smaller than those of the existing approaches. We further verify our performance using extensive simulations.

In this paper, we investigate the problem of providing QoS to end-to-end flows in multihop ad hoc networks with channel errors through packet scheduling. Each flow is associated with some QoS requirement, which is requested and granted in the form of a desired service rate. The achieved rate is estimated at the destination and fed back to the source periodically. Both the desired rate and achieved rate of a multihop flow are piggybacked on the packets of the flow and propagated from the source node to all its downstream relaying nodes. With such information, a compensation-capable scheduling algorithm originally designed for infrastructured wireless networks can be adapted to each ad hoc node for compensating a lagging flow, i.e., a flow with the achieved rate smaller than the desired rate. We propose the feedback and propagation mechanism as an end-to-end compensation framework, which is the key contribution of this work. We use BGFS-EBA, a scheduling algorithm for infrastructured wireless networks, as an example to demonstrate how such an algorithm is adapted to ad hoc networks within the proposed framework. Our simulation results show that the proposed mechanism maintains outcome fairness and compensate flows that suffer sporadic bursty channel errors effectively.

With the development of wireless communication technologies and the popularity of the P2P applications, an important problem is to determine how to distribute data efficiently in wireless P2P networks. However, data distribution in wireless P2P networks faces many challenges compared with that in th

Traffic scheduling is key to the provision of quality of service (QoS) differentiation and guarantees in wireless networks. Unlike its wireline counterpart, wireless communications pose special channel-specific problems such as time-varying link capacities and location-dependent errors. These problems make designing efficient and effective traffic scheduling algorithms for wireless networks very challenging. Although many wireless packet scheduling algorithms have been proposed in recent years, issues such as how to improve bandwidth efficiency and maintain goodput fairness with various link qualities for power-constrained mobile hosts remain unresolved. In this paper, we devise a simple wireless packet scheduling algorithm called bandwidth-guaranteed fair scheduling with effective excess bandwidth allocation (BGFS-EBA), which addresses these issues. Our studies reveal that BGFS-EBA effectively distributes excess bandwidth, strikes a balance between effort-fair and outcome- fair, and provides a delay bound for error-free flows and transmission effort guarantees for error-prone flows.

The objective of this paper is two-fold. First, we compare the performance, through computer simulations, of some solutions for TCP packet reordering in wireless networks. Second, we present an alternative method to improve the connection goodput in wireless networks through link-layer retransmissions and applying the solutions to TCP packet reordering. Some link-layer retransmission approaches do not attempt to maintain in-order packet delivery. This leads to some segments, which belong to the same TCP flow, to arrive at their destination out of order. Thus, the problem of high channel error rates in wireless networks becomes the problem of packet reordering due to link-layer retransmissions. We performed a simulation study to evaluate the performance of four solutions for TCP packet reordering, namely, RR-TCP, TCP-DCR, TCP-DOOR, and TCP-PR, under the scenarios of an infrastructure-based wireless network and a multi-hop wireless network. We also compared them with SACK TCP and TCPW. Our simulation study reveals that TCP-PR outperforms all of the other five algorithms, enjoying a greater connection goodput and fewer false fast retransmissions.

Transmission control protocol (TCP) is the most popular transport layer protocol for the Internet. Due to various reasons, such as multipath routing, route fluttering, and retransmissions, packets belonging to the same flow may arrive out of order at a destination. Such packet reordering violates the design principles of some traffic control mechanisms in TCP and, thus, poses performance problems. In this paper, we provide a comprehensive and in-depth survey on recent research on packet reordering in TCP. The causes and problems for packet reordering are discussed. Various representative algorithms are examined and compared by computer simulations. The ported program codes and simulation scripts are available for download. Some open questions are discussed to stimulate further research in this area

In this paper, we develop a model to study how to effectively download a document from a set of replicated servers. We propose a generalized application-layer anycasting protocol, known as paracasting, to advocate concurrent access of a subset of replicated servers to cooperatively satisfy a client's request. Each participating server satisfies the request in part by transmitting a subset of the requested file to the client. The client can recover the complete file when different parts of the file sent from the participating servers are received. This model allows us to estimate the average time to download a file from the set of homogeneous replicated servers, and the request blocking probability when each server can accept and serve a finite number of concurrent requests. Our results show that the file download time drops when a request is served concurrently by a larger number of homogeneous replicated servers, although the performance improvement quickly saturates when the number of servers increases. If the total number of requests that a server can handle simultaneously is finite, the request blocking probability increases with the number of replicated servers used to serve a request concurrently. Therefore, paracasting is effective when a small number of servers, say, up to four, are used to serve a request concurrently.

In this paper, we propose a framework to study how to effectively perform load sharing in multipath communication networks. A generalized load sharing (GLS) model has been developed to conceptualize how traffic is split ideally on a set of active paths. A simple traffic splitting algorithm, called packet-by-packet weighted fair routing (PWFR), has been developed to approximate GLS with the given routing weight vector by transmitting each packet as a whole. We have developed some performance bounds for PWFR and found that PWFR is a deterministically fair traffic splitting algorithm. This attractive property is useful in the provision of service with guaranteed performance when multiple paths can be used simultaneously to transmit packets which belong to the same flow. Our simulation studies, based on a collection of Internet backbone traces, reveal that PWFR outperforms two other traffic splitting algorithms, namely, packet-by-packet generalized round robin routing (PGRR), and packet-by-packet probabilistic routing (PPRR).

For pt.1 see ibid., p.694-702 (2006). In this paper, we extend the load sharing framework to study how to effectively perform flow-based traffic splitting in multipath communication networks. The generalized load sharing (GLS) model is employed to conceptualize how traffic is split ideally on a set of active paths. A simple flow-based weighted fair routing (WFR) algorithm, called call-by-call WFR (CWFR), has been developed to imitate GLS so that all packets belonging to a single flow are sent on the same path. We have investigated how to couple the proposed basic packet-by-packet WFR (PWFR) and CWFR algorithms so as to permit a traffic splitter to handle both connection-oriented and connectionless traffic simultaneously. Our simulation studies, based on a collection of Internet backbone traces, reveal that WFR outperforms two other traffic splitting algorithms, namely, generalized round robin routing (GRR), and probabilistic routing (PRR). These promising results form a basis for designing future adaptive constraint-based multipath routing protocols.

In this paper, we propose a simple algorithm to adaptively adjust the value of dupthresh, the duplicate acknowledgment threshold that triggers the TCP fast retransmission algorithm, to improve the TCP performance in a network environment with persistent packet reordering. Our algorithm uses an exponentially weighted moving average (EWMA) and the mean deviation of the length of the reordering events, reported by a TCP receiver with the DSACK extension, to estimate the value of dupthresh. We also apply an adaptive upper bound on dupthresh to avoid retransmission timeout events. In addition, our algorithm includes a mechanism to exponentially reduce dupthresh when the timer expires. With these mechanisms, our algorithm is capable of converging to and staying at a near-optimal interval of dupthresh. The simulation results show that our algorithm improves the protocol performance significantly with minimal overhead, achieving a greater throughput and fewer false fast retransmissions.

The TCP performance can deteriorate substantially in multipath packet-forwarding networks which induce persistent packet reordering. Focusing on these networks, we propose a simple algorithm to adaptively adjust the value of dupthresh, the threshold of duplicate acknowledgement at which the TCP fast retransmission algorithm is triggered, to improve the TCP performance. It uses an exponentially weighted moving average (EWMA) and the mean deviation of the length of reordering events to adjust the value of dupthresh. Our algorithm also computes an upper bound of dupthresh to avoid retransmission timeout events. In addition, it provides a mechanism to decrease dupthresh at the retransmission timeout (RTO) events. The simulation results show that our algorithm improves the protocol performance significantly with very low overhead. It achieves a greater throughput and fewer false fast retransmissions.

We propose a framework to study how to effectively perform load sharing in multipath communication networks. A generalized load sharing (GLS) model has been developed to conceptualize how traffic is split ideally, on a set of active paths. A simple traffic splitting algorithm, called weighted fair routing (WFR), has been developed at two different granularity levels, namely, the packet level, and the call level, to approximate GLS with the given routing weight vector. The packet-by-packet WFR (PWFR) mimics GLS by transmitting each packet as a whole whereas the call-by-call WFR (CWFR) imitates GLS so that all packets belonging to a single flow are sent on the same path. We have developed some performance bounds for PWFR and formed that PWFR is a deterministically fair traffic splitting algorithm. This attractive property is useful in the provision of service with guaranteed performance when multiple paths can be used simultaneously to transmit packets which belong to the same flow. Our simulation studies, based on a collection of Internet backbone traces, reveal that WFR outperforms two other traffic splitting algorithms, namely, generalized round robin routing (GRR), and probabilistic routing (PRR). These promising results form a basis for designing future adaptive constraint-based multipoint path routing protocols.

In this paper, we propose a framework to study the resequencing mechanism in high speed networks. This framework allows us to estimate the packet resequencing delay, the total packet delay, and the resequencing buffer occupancy distributions when data traffic is dispersed on multiple disjoint paths. In contrast to most of the existing work, the estimation of the end-to-end path delay distribution is decoupled from the queueing model for resequencing. This leads to a simple yet general model, which can be used with other measurement-based tools for estimating the end-to-end path delay distribution to find an optimal split of traffic. We consider a multiple-node M/M/1 tandem network as a path model. When end-to-end path delays are Gaussian distributed, our results show that the packet resequencing delay, the total packet delay, and the resequencing buffer occupancy drop when the traffic is spread over a larger number of homogeneous paths, although the network performance improvement quickly saturates when the number of paths used increases. We find that the number of paths used in multipath routing should be small, say up to three. Besides, an optimal split of traffic occurs at paths with equal loads.

The performance of distributed supercomputing computing environments are mainly dependent on three factors: distributed programming tools, computing nodes, and LANs employed. In this paper, we analyze the performance of all these factors experimentally and analytically. The distributed programming tools that we employed are PVM and Express. The computing nodes that we employed are SUN and HP workstations, and the LANs that we considered are an Ethernet and FDDI networks. Extensive timing experiments, including one-to-one communications, exchange operations, and broadcast operations, have been performed and analyzed. Moreover, analytic models have been developed to analyze the behavior of the network protocols employed by the LAN-based platforms as well as to estimate the communication overhead for the computing software tools.