Most of today's high-speed switches and routers adopt an input-queued crossbar switch architecture. Such a switch needs to compute a matching (crossbar schedule) between the input ports and output ports during each switching cycle (time slot). A key research challenge in designing large (in number of input/output ports N) input-queued crossbar switches is to develop crossbar scheduling algorithms that can compute “high quality” matchings - i.e., those that result in high switch throughput (ideally 100%) and low queueing delays for packets - at line rates. SERENA is one such algorithm: it outputs excellent matching decisions that result in 100% switch throughput and reasonably good queueing delays. However, since SERENA is a centralized algorithm with O(N) time complexity, it cannot support switches that both are large and have a very high line rate per port. In this work, we propose SERENADE (SERENA, the Distributed Edition), a parallel iterative algorithm that provably precisely emulates SERENA in only O(logN) iterations between input ports and output ports, and hence has a time complexity of only O(logN) per port.

Hybrid switching for data center networks (DCN) has received considerable research attention recently. A hybrid-switched DCN employs a much faster circuit switch that is reconfigurable with a nontrivial cost, and a much slower packet switch, to interconnect its racks of servers. The research problem is, given a traffic demand (between the racks), how to properly schedule the circuit switch so that it removes most of the traffic demand, leaving little for the slower packet switch to handle. All existing solutions make a convenient but unnecessarily restrictive assumption that when the circuit switch changes from one configuration to another, all input ports have to stop data transmission during the reconfiguration period. However, the circuit switch can usually readily support partial reconfiguration in the following sense: Only the input ports affected by the reconfiguration need to pay a reconfiguration delay, while unaffected input ports can continue to transmit data during the reconfiguration. In this work, we propose BFF (best first fit), the first solution to exploit this partial reconfigurability in hybrid-switched DCNs. BFF not only significantly outperforms but also has much lower computational complexity than the state of the art solutions that do not exploit this partial reconfigurability.

Backpressure-based adaptive routing algorithms have been studied extensively in the literature. Although backpressure-based adaptive routing algorithms have been shown to be network-wide throughput optimal, they typically have poor delay performance under light or moderate loads because packets may be sent over unnecessarily long routes. Further, backpressure-based algorithms have required every node to compute differential backlogs for every destination queue with the corresponding destination queue at every adjacent node. This computation is expensive given the large number of possible pairwise differential backlogs and requires many exchanges of backlog information between adjacent nodes. In this paper, we propose new backpressure-based adaptive routing algorithms that only use shortest-path routes to destinations when they are sufficient to accommodate the given traffic load, but the proposed algorithms will incrementally expand routing choices as needed to accommodate increasing traffic loads. We show analytically by means of fluid analysis that the proposed algorithms retain network-wide throughput optimality, and we show empirically by means of simulations that our proposed algorithms provide substantial improvements in delay performance. Our evaluations further show that in practice, our approach dramatically reduces the number of pairwise differential backlogs that have to be computed and the amount of corresponding backlog information that has to be exchanged because routing choices are only incrementally expanded as needed.

Chang et al. proposed the load-balanced switch in their seminal work [1], which has received wide attention due to its inherent scalability properties in both size and speed. These scalability properties continue to be of significant interest due to the relentless exponential growth in Internet traffic. The main drawback of the load-balanced switch is that packets can depart out-of-order from the switch, which can significantly degrade network performance by negatively interacting with TCP congestion control. Hence, a large body of subsequent work has proposed a variety of modifications for ensuring packet ordering, but all the proposed approaches tend to increase packet delay significantly in comparison to the basic load-balanced switch. In this paper, we show that the amount of packet reordering that can occur with the load-balanced switch is actually quite limited, which means that packet reordering can simply be rectified by employing reordering buffers at the switch outputs. In particular, we formally bound the worst-case amount of time that a packet has to wait in these output reordering buffers before it is guaranteed to be ready for in-order departure with high probability, and we prove that this bound is linear with respect to the switch size. This linear bound is significant because previous approaches can add quadratic or cubic delays to the load-balanced switch. In addition, we use a hash-grouping method that further reduces resequencing delays significantly. Although simple and intuitive, our experimental results show that our output packet reordering approach substantially outperforms existing load-balanced switch architectures.

Syslogs on switches are a rich source of information for both post-mortem diagnosis and proactive prediction of switch failures in a datacenter network. However, such information can be effectively extracted only through proper processing of syslogs, e.g., using suitable machine learning techniques. A common approach to syslog processing is to extract (i.e., build) templates from historical syslog messages and then match syslog messages to these templates. However, existing template extraction techniques either have low accuracies in learning the “correct” set of templates, or does not support incremental learning in the sense the entire set of templates has to be rebuilt (from processing all historical syslog messages again) when a new template is to be added, which is prohibitively expensive computationally if used for a large datacenter network. To address these two problems, we propose a frequent template tree (FT-tree) model in which frequent combinations of (syslog) words are identified and then used as message templates. FTtree empirically extracts message templates more accurately than existing approaches, and naturally supports incremental learning. To compare the performance of FT-tree and three other template learning techniques, we experimented them on two-years' worth of failure tickets and syslogs collected from switches deployed across 10+ datacenters of a tier-1 cloud service provider. The experiments demonstrated that FT-tree improved the estimation/prediction accuracy (as measured by F1) by 155% to 188%, and the computational efficiency by 117 to 730 times.

Load-balanced switch architectures are known to be scalable in both size and speed, which is of interest due to the continued exponential growth in Internet traffic. However, the main drawback of load-balanced switches is that packets can depart out of order from the switch. Randomized load-balancing of application flows by means of hashing on the packet header is a well-known simple solution to this packet reordering problem in which all packets belonging to the same application flow are routed through the same intermediate port and hence the same path through the switch. Unfortunately, this method of load-balancing can lead to instability, depending on the mix of flow sizes and durations in the group of flows that gets randomly assigned to route through the same intermediate port. In this paper, we show that the randomized load-balancing of application flows can be enhanced to provably guarantee both stability and packet ordering by extending the approach with safety mechanisms that can uniformly diffuse packets across the switch whenever there is a build-up of packets waiting to route through the some intermediate port. Although simple and intuitive, our experimental results show that our extended randomized load-balancing approach significantly outperforms existing load-balanced switch architectures.

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

In this paper, we explore methods to generate optimal network topologies for wireless sensor networks (WSNs) with and without obstacles. Specifically, we investigate a dense network with n sensor nodes and m=nb(0v) (0 <; v ≤ 1) arbitrarily or randomly distributed obstacles, which block cells they are located in, i.e., sensor nodes cannot be placed in these cells and nodes' communication cannot cross them directly. We find that the overall throughput capacity is bounded by the transmission burden in areas around these blocked cells and introduce a novel algorithm of complexity O(M) to generate optimal sensor nodes' topologies for any given obstacles' distributions. We further analyze its performance for regularly distributed obstacles, which can be taken to estimate the lower bound of the algorithm's performance.

In this paper, we explore methods to generate optimal network topologies for wireless sensor networks (WSNs) with and without obstacles. Specifically, we investigate a dense network with n sensor nodes and m = nb(0 < b < 1) helping nodes, and evaluate the impact of topology on its throughput capacity. For networks without obstacles, we find that uniformly distributed sensor nodes and regularly distributed helping nodes have some advantages in improving the throughput capacity. We also explore properties of networks composed of some isomorphic sub-networks. For networks with obstacles, we assume there are M = Θ(nv) (0 < v ≤ 1) arbitrarily or randomly distributed obstacles, which block cells they are located in, i.e., sensor nodes cannot be placed in these cells and nodes' communication cannot cross them directly. We find that the overall throughput capacity is bounded by the transmission burden in areas around these blocked cells and introduce a novel algorithm of complexity O(M) to generate optimal sensor nodes' topologies for any given obstacles' distributions.

In this paper, we study the multicast capacity-delay tradeoff of a wireless network consisting of mobile wireless nodes and base stations. m = nbbase stations are regularly placed in a square region and n is the number of mobile nodes in the network. We assume that mobile nodes move according to an independent and identical distributed (i.i.d.) pattern and each desires to send packets to k = nddistinctive destinations. Under this basic network model, we study capacity, delay tradeoff in two transmission protocols: 2-hop relay algorithm with and without redundancy. We derive that the upper bound of per-node capacity of 2-hop relay algorithm without redundancy is O(n-min{1, 1 - b + d})and its corresponding delay is Θ(nmin{1, 1 - b + d}/2). The lower bound of delay of this protocol is Θ(n1-b), with a smaller capacity O(nb-2). For 2-hop relay algorithm with redundancy, the largest capacity and its corresponding delay are O(n-min{1, 1 - b + d}) and Θ(nmin{1, 1 - b + d}/2). The smallest delay and its corresponding capacity are Θ(n1 - b/2) and O(nb - 3/2). When d >; 1/2 or b >; min{1+d/3, 1 - d}, adding base stations will improve the tradeoff mentioned in [7].