WANs are often over-provisioned to accommodate worst-case operating conditions, with many links typically running at only around 30% capacity. In this paper, we show that in-network congestion management can play an important role in increasing network utilization. To mitigate the effects of in-network congestion caused by rapid variations in traffic demand, we propose using high-frequency traffic control (HFTraC) algorithms that exchange real-time flow rate and buffer occupancy information between routers to dynamically coordinate their link-service rates. We show that the design of such dynamic link-service rate policies can be cast as a distributed optimal control problem that allows us to systematically explore an enlarged design space of in-network congestion management algorithms. This also provides a means of quantitatively comparing different controller architectures: we show, perhaps surprisingly, that centralized control is not always better. We implement and evaluate HFTraC in the face of rapidly varying UDP and TCP flows and in combination with AQM algorithms. Using a custom experimental testbed, a Mininet emulator, and a production WAN, we show that HFTraC leads to up to 66% decreases in packet loss rates at high link utilizations as compared to FIFO policies.

We present HALO, the first link-state routing solution with hop-by-hop packet forwarding that minimizes the cost of carrying traffic through packet-switched networks. At each node u, for every other node t, the algorithm independently and iteratively updates the fraction of traffic destined to t that leaves u on each of its outgoing links. At each iteration, the updates are calculated based on the shortest path to each destination as determined by the marginal costs of the network's links. The marginal link costs used to find the shortest paths are in turn obtained from link-state updates that are flooded through the network after each iteration. For stationary input traffic, we prove that HALO converges to the routing assignment that minimizes the cost of the network. Furthermore, we observe that our technique is adaptive, automatically converging to the new optimal routing assignment for quasi-static network changes. We also report numerical and experimental evaluations to confirm our theoretical predictions, explore additional aspects of the solution, and outline a proof-of-concept implementation of HALO.

Current intra-domain routing protocols like OSPF and IS-IS use link-state routing algorithms with hop-by-hop forwarding that sacrifice traffic engineering performance for ease of implementation and management. Though optimal traffic engineering algorithms exist, they tend to be either not link-state algorithms or to require source routing - characteristics that make them difficult to implement. As the focus of this paper, we introduce HALO, the first optimal link-state routing algorithm with hop-by-hop forwarding, where link weights can be calculated locally. Furthermore, our solution can adapt to changing traffic patterns automatically. The optimality of the algorithm is proved theoretically and also verified numerically.

Network-on-chip (NoC) promises better scalability and power efficiency compared to traditional on-chip interconnects. But in order to fully exploit the benefits offered by the new paradigm, especially as the number of cores in the network increases, challenging resource management questions need to be addressed. Of particular interest and the subject of our study is the question of how to map applications to processors (network nodes) in a NoC so as to minimize the dynamic power consumption of the NoC.

Application-aware routing exploits static knowledge of an application's traffic pattern to improve performance compared to generalpurpose routing algorithms. Unfortunately, traditional approaches to application-aware routing cannot efficiently handle dynamic changes in the traffic pattern limiting its usefulness in practice. In this paper, we study application-aware routing under traffic uncertainty. Our problem formulation allows an application to statically specify an uncertainty set of traffic patterns that each occur with a given probability, and our goal is to find a single set of combined routes that will enable high-performance across all of these traffic patterns. We show how efficient combined routes can be found for this problem using convex optimization. These combined routes are optimal when the performance for every traffic pattern using the combined routes is the same as the performance using routes that are specialized for just that traffic pattern. We derive necessary and sufficient conditions for when our optimization framework will find optimal combined routes. We use theoretical and numerical analysis for the important class of permutation traffic patterns to quantify how often optimal combined routes exist and to determine the performance loss when optimal combined routes are infeasible. Finally, we use a cycle-level simulator that includes realistic pipeline latencies, arbitration, and buffered flow-control to study the latency and throughput of combined routes compared to specialized routes and routes generated using general-purpose routing algorithms. The theoretical analysis, numerical analysis, and simulation results in this paper provide a first step towards more flexible application-aware routing.

The problem of distributed learning and channel access is considered in a cognitive network with multiple secondary users. The availability statistics of the channels are initially unknown to the secondary users and are estimated using sensing decisions. There is no explicit information exchange or prior agreement among the secondary users and sensing and access decisions are undertaken by them in a completely distributed manner. We propose policies for distributed learning and access which achieve order-optimal cognitive system throughput (number of successful secondary transmissions) under self play, i.e., when implemented at all the secondary users. Equivalently, our policies minimize the sum regret in distributed learning and access, which is the loss in secondary throughput due to learning and distributed access. For the scenario when the number of secondary users is known to the policy, we prove that the total regret is logarithmic in the number of transmission slots. This policy achieves order-optimal regret based on a logarithmic lower bound for regret under any uniformly-good learning and access policy. We then consider the case when the number of secondary users is fixed but unknown, and is estimated at each user through feedback. We propose a policy whose sum regret grows only slightly faster than logarithmic in the number of transmission slots.

The problem of cooperative allocation among multiple secondary users to maximize cognitive system throughput is considered. The channel availability statistics are initially unknown to the secondary users and are learnt via sensing samples. Two distributed learning and allocation schemes which maximize the cognitive system throughput or equivalently minimize the total regret in distributed learning and allocation are proposed. The first scheme assumes minimal prior information in terms of pre-allocated ranks for secondary users while the second scheme is fully distributed and assumes no such prior information. The two schemes have sum regret which is provably logarithmic in the number of sensing time slots. A lower bound is derived for any learning scheme which is asymptotically logarithmic in the number of slots. Hence, our schemes achieve asymptotic order optimality in terms of regret in distributed learning and allocation.