Network-coded cooperative communications (NC-CC) refers to the use of network coding (NC) in cooperative communications (CC). Prior studies have shown that NC has the potential to improve the performance of CC when there are multiple sessions in the wireless network. These studies were done for the case when multiple sessions are sharing a single relay node. However, how NC-CC behaves when multiple relay nodes are employed remains an open problem. In this paper, we explore this problem by analyzing the achievable rate of each session in this setting. We develop closed form formulas for the mutual information and the achievable data rate for each session. We show that prior results for a single relay is a special case of our result. Based on these findings, we then study a network optimization problem that requires joint optimization of session grouping, relay node grouping, and matching of session/relay groups. We show that this problem is NP-hard, and present a polynomial time heuristic algorithm to solve this problem. Using simulation results, we show this algorithm is highly competitive and can produce results that are near to optimality.

Network-coded cooperative communications (NC-CC) is a new paradigm for communications in wireless networks that employs network coding (NC) to improve the performance of CC. A key problem to harness the potential of NC-CC is how to put sessions into different groups, and assign a relay node for each group. In this paper, we study this joint grouping and relay node selection problem for NC-CC. We provide a formal proof of NP-hardness for this problem. Due to NP-hardness, we propose a distributed and online algorithm and show that it offers near-optimal solution to this problem. The key idea in this algorithm is to have each neighboring relay node of a new session calculate the best local group that it can offer and advertise this information; and then to have the source node of the new session select the best local group to join among all offers. We show that our distributed algorithm has polynomial time complexity. Using extensive numerical results, we show that our distributed algorithm adapts well to online network dynamics.

End-to-End guaranteed network QoS is a requirement for predictable data transfers between geographically distant end-hosts. Existing QoS systems, however, do not have the capability/intelligence to decide what resources to reserve and which paths to choose when there are multiple and flexible resource reservation requests. In this paper, we design and implement an intelligent system that can guarantee end-to-end network QoS for multiple flexible reservation requests. At the heart of this system is a polynomial time algorithm called resource reservation and path construction (RRPC). The RRPC algorithm schedules multiple flexible end-to-end data transfer requests by jointly optimizing the path construction and bandwidth reservation along these paths. We show that constructing such schedules is NP-hard. We implement our intelligent QoS system, and present the results of deployment on real world production networks (ESnet and Internet2). Our implementation does not require modifications or new software to be deployed on the routers within network.

It has been shown that cooperative communications (CC) has the potential to significantly increase the capacity of wireless networks. However, most of the existing results are limited to single-hop wireless networks. To explore the behavior of CC in multi-hop wireless networks, we study a joint optimization problem of relay node assignment and flow routing for a group of sessions. We develop a mathematical model and propose a solution procedure based on the branch-and-bound framework augmented with cutting planes (BB-CP). We design several novel components to speed-up the computational time of BB-CP. Via numerical results, we show the potential rate gain that can be achieved by incorporating CC in multi-hop networks.

A major benefit of employing network coding (NC) in cooperative communications (CCs) is its ability to reduce time-slot overhead. Such approach is called network-coded CC (or NC-CC). Most of the existing works have mainly focused on exploiting this benefit without considering its potential adverse effect. In this paper, we show that NC may not always benefit CC. We substantiate this important finding with two important scenarios: employing analog network coding (ANC) in amplify-and-forward (AF) CC, and digital network coding (DNC) in decode-and-forward (DF) CC. For both scenarios, we introduce the important concept of network coding noise (NC noise). We analyze the origin of this noise via a careful study of signal aggregation at a relay node and signal extraction at a destination node. We derive a closed-form expression for NC noise at each destination node and show that the existence of NC noise could diminish the advantage of NC in CC. Our results shed new light on how to use NC in CC most effectively.

Network-coded cooperative communications (NC-CC) refers to the use of network coding (NC) in cooperative communications (CC). Prior studies have shown that NC has the potential to improve the performance of CC when there are multiple sessions in the wireless network. These studies were done for the case when multiple sessions are sharing a single relay node. However, how NC-CC behaves when multiple relay nodes are employed remains an open problem. In this paper, we explore this problem by analyzing the achievable rate of each session in this setting. We develop closed form formulas for the mutual information and the achievable data rate for each session and show that prior results for a single relay is a special case of our result. Our findings in this paper offer an important building block on the theory of NC-CC. To demonstrate the application of our theoretical result, we apply it in a numerical study to understand the impact on a session's achievable rate when different sets of relay nodes are employed in NC-CC.

Network-coded cooperative communications (NC-CC) is a new paradigm in wireless networks that employs network coding (NC) to improve the performance of CC. The core mechanism to harness the benefits of NC-CC is to appropriately combine sessions into separate groups, and then have each group select the most beneficial relay node for NC-CC. In this paper, we study this joint grouping and relay node selection problem for NC-CC. Due to NP-hardness of problem, we propose a distributed and online algorithm that offers near-optimal solution to this problem. The key idea in our algorithm is to have each neighboring relay node of a new session determine and offer its best local group; and then to have the source node of the new session select the best group among all offers. We show that our distributed algorithm has polynomial complexity. Using extensive numerical results, we show that our distributed algorithm adapts well to online network dynamics.

Modern data-intensive applications move vast amounts of data between multiple locations around the world. To enable predictable and reliable data transfers, next generation networks allow such applications to reserve network resources for exclusive use. In this paper, we solve an important problem (called SMR3) to accommodate multiple and concurrent network reservation requests between a pair of end sites. Given the varying availability of bandwidth within the network, our goal is to accommodate as many reservation requests as possible while minimizing the total time needed to complete the data transfers. First, we prove that SMR3 is an NP-hard problem. Then, we solve it by developing a polynomial-time heuristic called RRA. The RRA algorithm hinges on an efficient mechanism to accommodate large number of requests in an iterative manner. Finally, we show via numerical results that RRA constructs schedules that accommodate significantly larger number of requests compared to other, seemingly efficient, heuristics.

Recently, cooperative communications, in the form of having each node equipped with a single antenna and exploit spatial diversity via some relay node's antenna, is shown to be a promising approach to increase data rates in wireless networks. Under this communication paradigm, the choice of a relay node (among a set of available relay nodes) is critical in the overall network performance. In this paper, we study the relay node assignment problem in a cooperative ad hoc network environment, where multiple source-destination pairs compete for the same pool of relay nodes in the network. Our objective is to assign the available relay nodes to different source-destination pairs so as to maximize the minimum data rate among all pairs. The main contribution of this paper is the development of an optimal polynomial time algorithm, called ORA, that achieves this objective. A novel idea in this algorithm is a “linear marking” mechanism, which maintains linear complexity of each iteration. We give a formal proof of optimality for ORA and use numerical results to demonstrate its capability.

Next-generation wireless networks such as LTE and WiMax can achieve throughputs of several Mbps with TCP. These higher throughputs, however, can easily be destroyed by frequent handoffs, which occur in urban environments due to shadowing. A primary reason for the throughput drop during handoffs is the out of order arrival of packets at the receiver. As a result, in this paper, we model the precise effect of packet-reordering on the goodput of TCP NewReno. Specifically, we develop a TCP NewReno model that captures the goodput of TCP as a function of round-trip time, average time duration between packet-reorder events, average number of packets reordered during every reorder event, and the congestion window threshold of TCP NewReno. We also developed an emulator that runs on a router to implement packet reordering events from time to time. We validate our NewReno model by comparing the goodput results obtained by transferring data between two hosts connected via the emulator to the goodput results that our model predicts.

It has been shown that cooperative communications (CC) have the potential to significantly increase the capacity of wireless networks. However, most of the existing results are limited to single-hop wireless networks. To illustrate the benefits of CC in multi-hop wireless networks, we solve a joint optimization problem of relay node assignment and flow routing for concurrent sessions. We study this problem via mathematical modeling and solve it using a solution procedure based on the branch-and-cut framework. We design several novel components to speed-up the computation time of branch-and-cut. Via numerical results, we show the significant rate gains that can be achieved by incorporating CC in multi-hop networks.

Network coding (NC) is a promising approach to reduce time-slot overhead for cooperative communications (CC) in a multi-session environment. Most of the existing works take advantage of the benefits of NC in CC but do not fully recognize its potential adverse effect. In this paper, we show that employing NC may not always benefit CC. We substantiate this important finding in the context of analog network coding (ANC) and amplify-and-forward (AF) CC. This paper, for the first time, introduces an important concept of network coding noise (NC noise). Specifically, we analyze the signal aggregation at a relay node and signal extraction at a destination node. We then use the analysis to derive a closed-form expression for NC noise at each destination node in a multi-session environment. We show that NC noise can diminish the advantage of NC in CC. Our results formalizes an important concept on using NC in CC.

Recently, cooperative communications, in the form of keeping each node with a single antenna and having a node exploit a relay node's antenna, is shown to be a promising approach to achieve spatial diversity. Under this communication paradigm, the choice of relay node plays a significant role in the overall system performance. In this paper, we study the relay node assignment problem in a network environment, where multiple source-destination pairs compete for the same pool of relay nodes in the network. The main contribution of this paper is the development of a polynomial time algorithm to solve this problem. A key idea in this algorithm is a "linear marking" mechanism, which is able to offer a linear complexity for each iteration. We give a formal proof of optimality for this algorithm. We also show several attractive properties associated with this algorithm.

Next-generation e-Science applications will require the ability to transfer information at high data rates between distributed computing centers and data repositories. A Lambda-Grid offers dedicated, optical, circuit-switched, point-to-point connections, which may be reserved exclusively for an application. Though such dedicated high-speed connections eliminate congestion in the network, they effectively push the network congestion out to the end systems, as processing speeds have not kept up with networking speeds. Therefore, developing an efficient transport protocol over such highspeed dedicated circuits is of critical importance. In this work, we propose the idea of a lightweight end-system protocol, based on performance monitoring, to significantly improve the performance of data transport over a LambdaGrid. In particular, we focus on dynamically monitoring the OS task scheduling at the receiving end-system so that potential end-system congestion may be detected early and appropriate feedback can be transmitted back to the sending end-system to avoid packet losses. One example of such an evasive action is to suspend transmission for certain duration of time during which the OS on the receiving end-system must handle other computational processes. With this in mind, we propose to extend the Reliable-Blast UDP (RBUDP) protocol to take such evasive action by using a simple feedback mechanism that is activated via performance monitoring. The new protocol, named RBUDP dramatically improves the performance of data transfer over LambdaGrids. We demonstrate the effectiveness of our proposed protocol and illustrate the performance gains achieved via network emulation.

For decades now, the notion of "performance" has been synonymous with "speed" (as measured in FLOPS, short for floating-point operations per second). Unfortunately, this particular focus has led to the emergence of supercomputers that consume egregious amounts of electrical power and produce so much heat that extravagant cooling facilities must be constructed to ensure proper operation. In addition, the emphasis on speed as the performance metric has caused other performance metrics to be largely ignored, e.g., reliability, availability, and usability. As a consequence, all of the above has led to an extraordinary increase in the total cost of ownership (TCO) of a supercomputer. Despite the importance of the TOP500 List, we argue that the list makes it much more difficult for the high-performance computing (UPC) community to focus on performance metrics other than speed. Therefore, to raise awareness to other performance metrics of interest, e.g., energy efficiency for improved reliability, we propose a Green500 List and discuss the potential metrics that would be used to rank supercomputing systems on such a list.

Next-generation e-Science applications will require the ability to transfer information at high data rates between distributed computing centers and data repositories. A LambdaGrid offers dedicated, optical, circuit-switched, point-to-point connections that can be reserved exclusively for such applications. These dedicated high-speed connections eliminate network congestion as seen in traditional Internet, but they effectively push the network congestion to the end systems, as processing speeds cannot keep up with networking speeds. Thus, developing an efficient transport protocol over such high-speed dedicated circuits is of critical importance.We propose the idea of a end-system aware, rate-adaptive protocol for network transport, based on end-system performance monitoring. Our proposed protocol significantly improves the performance of data transfer over LambdaGrids by intelligently adapting the sending rate based on end-system constraints. We demonstrate the effectiveness of our proposed protocol and illustrate the performance gains achieved via wide-area network emulation.