An analytical and optimization framework on rate-Cramér-Rao bound (CRB) tradeoff is proposed in this paper for the continuous-aperture array (CAPA)-based integrated sensing and communication (ISAC) system. To evaluate the dual-functional performance, the sensing CRB and communication rate are analyzed concerning the induced electromagnetic (EM) waves of CAPAs. For rate-CRB region characterization, the spatially continuous beamforming of transmit CAPA is optimized under three cases: i) A novel closed-form expression for the optimal CAPA beamformer is derived under the single-user single-target scenario, proven to be aligned within the space spanned by the EM-based sensing and communication channels; ii) A general subspace-based beamforming design approach is proposed to address the intractable continuity, converting the continuous beamforming design in spatial domain to discrete weight design in subspace domain and resorting to the semidefinite relaxation for the globally optimal solution; iii) Moreover, the general beamforming design is specialized to both the low-complexity zero-forcing (ZF) and the conventional spatially discrete array (SPDA)-based designs. Numerical results demonstrate that: i) The proposed subspace-based approach can realize efficient and effective beamforming design for reduced mutual interference, enhanced sensing performance, and guaranteed communication rate; ii) The general CAPA beamforming design achieves broader rate-CRB region than the ZF-oriented design and reaches the ultimate performance of the SPDA-based system.

Enabled by metamaterials, continuous aperture array (CAPA) has been proven to play a crucial role in communication performance enhancement, while its potentials in integrated sensing and communication (ISAC) systems have not been investigated. This paper investigates the performance analysis and optimization of CAPA-based ISAC systems for simultaneous user communication and target sensing. To be specific, communication and sensing rates are evaluated based on electromagnetic channels and a Pareto-optimal problem is formulated for beamforming optimization. Closed-form solutions to CAPA-oriented beamforming are derived under communication-, sensing-, and Pareto-optimal cases, and the attainable ISAC rate region is obtained. Numerical results verify that CAPA-based systems can achieve the ultimate sensing and communication performance of spatially discrete array (SPDA)-based systems and significantly expand the ISAC rate region for Pareto optimality.

Link speed in datacenter networks (DCNs) keeps growing rapidly, inducing an increasingly large portion of network flows to become short flows which can be finished within one round-trip time (RTT). This phenomenon makes many existing congestion control schemes ineffective because they iteratively adjust the sending rate based on the latest congestion feedback in multiple rounds. We find that the representative DCQCN scheme for RDMA exhibits substantial performance degradation when there are many short flows, and this is specially true in High Performance Computing (HPC) scenarios where most of Message Passing Interface (MPI) messages are small. In this paper, we propose a data-driven rate control framework which can learn from long-term online data about past rate control decisions via a lightweight online learning technique named Multi-Armed Bandit (MAB) which has a provable performance guarantee. Utilizing the framework, we devise a rate control scheme named Dolce-RC, which dynamically controls the rate increase and reduction by learning from online data. We implement Dolce-RC in commodity smart NICs, and show via testbed experiments and large-scale simulations that compared to DCQCN, Dolce-RC reduces average completion time of MPI messages by up to 68%, while not requiring any modification to switches.

There is a growing trend that network applications not only require higher throughput, but also impose stricter delay requirements. The current Internet congestion control, which is driven by active queue management (AQM) algorithms interacting with the Transmission Control Protocol (TCP), has been playing an important role in supporting network applications. However, it still exhibits many open issues. Most of AQM algorithms only deploy a single-queue structure that cannot differentiate flows and easily leads to unfairness. Moreover, the parameter settings of AQM are often static, making them difficult to adapt to the dynamic network environments. In this paper, we propose a general framework for designing "self-tuning" queue management (SQM), which is adaptive to the changing environments and provides fair congestion control among flows. We first present a general architecture of SQM with fair queueing and propose a general fluid model to analyze it. To adapt to the stochastic environments, we formulate a stochastic network utility maximization (SNUM) problem, and utilize online convex optimization (OCO) and control theory to develop a distributed SQM algorithm which can self-tune different queue weights and control parameters. Numerical and packet-level simulation results show that our SQM algorithm significantly improves queueing delay and fairness among flows.

The classic utility maximization framework studies the fairness-efficiency tradeoff in various resource allocation problems (e.g., bandwidth allocation). The weighted alpha-fair utility is a common utilitarian metric. However, this classic framework cannot tackle those allocation problems with the online decision-making requirement (e.g., caching capacity allocation under unknown requests). Existing studies on these online allocation problems largely follow the online learning approaches, thus inevitably overlook the allocation fairness. In this paper, we propose a novel utility maximization framework accommodating the online setting. The major challenge of designing this framework lies in the tight coupling between the desirable fairness guarantee and the unknown allocation efficiency. To tackle this, we integrate the weighted alpha-fair utility with the learning rationale, by properly devising the merit-based weights and the increasing fairness levels. Under our proposed framework, the utility-maximizing allocation in each time slot is weighted alpha-fair. Our framework also performs asymptotically as well as the offline optimal/efficient outcome. We demonstrate how this framework functions in two networking applications. In size-based scheduling, it enables network switches to prioritize short flows and avoid flow starvation without the prior flow size information. In file caching, our framework outperforms several state-of-the-art caching policies up to 21% in terms of cache-hit-ratio.

Multi-task learning aims to solve multiple machine learning tasks at the same time, with good solutions being both generalizable and Pareto optimal. A multi-task deep learning model consists of a shared representation learned to capture task commonalities, and task-specific sub-networks capturing the specificities of each task. In this work, we offer insights on the under-explored trade-off between minimizing task training conflicts in multi-task learning and improving multi-task generalization, i.e. the generalization capability of the shared presentation across all tasks. The trade-off can be viewed as the tension between multi-objective optimization and shared representation learning: As a multi-objective optimization problem, sufficient parameterization is needed for mitigating task conflicts in a constrained solution space; However, from a representation learning perspective, over-parameterizing the task-specific sub-networks may give the model too many ”degrees of freedom” and impedes the generalizability of the shared representation.

There are limited studies on the semantic segmentation of high-resolution polarimetric synthetic aperture radar (PolSAR) images due to the scarcity of training data and the complexity of managing speckle noise. The Gaofen contest has provided open access a high-quality PolSAR semantic segmentation dataset. Taking this opportunity, we propose a multipath residual network (MP-ResNet) architecture for the semantic segmentation of high-resolution PolSAR images. Compared to conventional U-shape encoder–decoder convolutional neural network (CNN) architectures, the MP-ResNet learns semantic context with its parallel multiscale branches, which greatly enlarges its valid receptive fields and improves the embedding of local discriminative features. In addition, MP-ResNet adopts a multilevel feature fusion design in its decoder to effectively exploit the features learned from its different branches. Comparisons with the baseline method of fully connected network (FCN with ResNet34) show that the MP-ResNet has achieved significant accuracy improvements. It also surpasses several state-of-the-art methods in terms of overall accuracy (OA),$\text{m}F_{1}$and frequency weighted intersection over union (fwIoU), with only a limited increase of computational costs. This CNN architecture can be used as a baseline method for future studies on the semantic segmentation of PolSAR images. The code is available at:https://github.com/ggsDing/SARSeg.

Long-range contextual information is crucial for the semantic segmentation of high-resolution (HR) remote sensing images (RSIs). However, image cropping operations, commonly used for training neural networks, limit the perception of long-range contexts in large RSIs. To overcome this limitation, we propose a wide-context network (WiCoNet) for the semantic segmentation of HR RSIs. Apart from extracting local features with a conventional convolutional neural network (CNN), the WiCoNet has an extra context branch to aggregate information from a larger image area. Moreover, we introduce a context transformer to embed contextual information from the context branch and selectively project it onto the local features. The context transformer extends the vision transformer, an emerging kind of neural networks, to model the dual-branch semantic correlations. It overcomes the locality limitation of CNNs and enables the WiCoNet to see the bigger picture before segmenting the land-cover/land-use (LCLU) classes. Ablation studies and comparative experiments conducted on several benchmark datasets demonstrate the effectiveness of the proposed method. In addition, we present a new Beijing Land-Use (BLU) dataset. This is a large-scale HR satellite dataset with high-quality and fine-grained reference labels, which can facilitate future studies in this field.

The scheduling policy installed on switches of datacenters plays a significant role on congestion control. Shortest-Remaining-Processing-Time (SRPT) achieves the near-optimal average message completion time (MCT) in various scenarios, but is difficult to deploy as viewed by the industry. The reasons are two-fold: 1) many commodity switches only provide FIFO queues, and 2) the information of remaining message size is not available. Recently, the idea of emulating SRPT using only a few FIFO queues and the original message size has been coined as the approximate and deployable SRPT (ADS) design. In this paper, we provide the first theoretical study on the optimal ADS design. Specifically, we first characterize a wide range of feasible ADS scheduling policies via a unified framework, and then derive the steady-state MCT, slowdown, and impoliteness in the M/G/1 setting. Hence we formulate the optimal ADS design as a non-linear combinatorial optimization problem, which aims to minimize the average MCT given the available FIFO queues. We also take into account the proportional fairness and temporal fairness constraints based on the maximal slowdown and impoliteness, respectively. The optimal ADS design problem is NP-hard in general, and does not exhibit monotonicity or sub-modularity. We leverage its decomposable structure and devise an efficient algorithm to solve the optimal ADS policy. We carry out extensive flow-level simulations and packet-level experiments to evaluate the proposed optimal ADS design. Results show that the optimal ADS policy installed on eight FIFO queues is capable of emulating the true SRPT.

The scheduling policy installed on switches of datacenters plays a significant role on congestion control. Shortest-Remaining-Processing-Time (SRPT) achieves the near-optimal average message completion time (MCT) in various scenarios, but is difficult to deploy as viewed by the industry. The reasons are two-fold: 1) many commodity switches only provide FIFO queues, and 2) the information of remaining message size is not available. Recently, the idea of emulating SRPT using only a few FIFO queues and the original message size has been coined as the approximate and deployable SRPT (ADS) design. In this paper, we provide the first theoretical study on ADS design. Specifically, we first characterize a wide range of feasible ADS scheduling policies via a unified framework, and then derive the steady-state MCT and slowdown in the M/G/1 setting. We formulate the optimal ADS design as a non-linear combinatorial optimization problem, which aims to minimize the average MCT given the available FIFO queues. To prevent the starvation of long messages, we also take into account the fairness condition based on the steady-state slowdown. The optimal ADS design problem is NP-hard in general, and does not exhibit monotonicity or sub-modularity. We leverage its decomposable structure and devise an efficient algorithm to solve the optimal ADS policy. Numerical results based on the realistic heavy-tail message size distribution show that the optimal ADS policy installed on eight FIFO queues is capable of emulating the true SRPT in terms of MCT and slowdown.

Despite deep neural network (DNN)'s impressive prediction performance in various domains, it is well known now that a set of DNN models trained with the same model specification and the exact same training data could produce very different prediction results. People have relied on the state-of-the-art ensemble method to estimate prediction uncertainty. However, ensembles are expensive to train and serve for web-scale traffic systems.

Learning effective feature crosses is the key behind building recommender systems. However, the sparse and large feature space requires exhaustive search to identify effective crosses. Deep & Cross Network (DCN) was proposed to automatically and efficiently learn bounded-degree predictive feature interactions. Unfortunately, in models that serve web-scale traffic with billions of training examples, DCN showed limited expressiveness in its cross network at learning more predictive feature interactions. Despite significant research progress made, many deep learning models in production still rely on traditional feed-forward neural networks to learn feature crosses inefficiently.

th for various services. Yet today’s widely used load balancing scheme, i.e., ECMP, may cause serious congestion when hash collision happens. Recent proposals either push load balancing function to a centralized controller or network edges. However, the centralized schemes are too slow for latency-sensitive flows, while the distributed schemes lack the global view and usually cannot make the best choices. In this paper, based on Software-Defined Networking (SDN), we present a new hybrid load balancing scheme called BLEND. It promotes the cooperation among network components and takes advantage of both global view and fast end-host action. BLEND aims to improve the throughput of big flows and reduce the latency of small and medium flows. It employs a controller to assign paths to big flows to achieve high throughput. In addition, in order to provide guidance for fast distributed load balancing decisions, the controller also calculates the optimal network delay thresholds for small and medium flows, while hosts utilize these thresholds to decide whether to change the current paths. BLEND is practical and easily deployable in the current data center networks. Comprehensive experiments demonstrate that BLEND outperforms both the centralized and distributed schemes and achieves at most 40% reduction in FCT and at most 2.8 times improvement in throughput.

Remote Direct Memory Access (RDMA) can be deployed in Content Delivery Networks (CDN) Points of Presence (PoPs) to avoid the high CPU overheads caused by traditional TCP/IP stacks. However, RDMA cannot surmount the drawbacks of the window-based conservative of TCP and is insensitive to Quality of Experience (QoE). Moreover, the requirement of lossless networks hinders the widespread application of RDMA. In this paper, we introduce the parallel multipoint-to-multipoint Request-Grant-Transfer (RGT) mode into RDMA to solve the aforementioned problems. Compared with traditional RGT mode, our scheme supports parallel Dynamic Adaptive Streaming over HTTP (DASH) chunk delivery, thereby improving throughput and reducing initial delays. We differentiate the importance of DASH chunks according to QoE-related properties. In this way, we reduce the response time of specific DASH chunks. We provide an efficient approach to select the optimal number of requests for partially traversing pending requests to reduce the overheads of Request stages. We perform comprehensive experiments to demonstrate that our scheme improves the throughput of CDN PoPs and enhances client QoE.

The Internet is a gigantic distributed system where the end-to-end (E2E) quality-of-service (QoS) plays an important role. Yet the current inter-domain routing protocol, namely, the Border Gateway Protocol (BGP), cannot provide E2E QoS guarantees. The main reason is that an autonomous system (AS) can only receive guarantees from its first-hop ASes via service level agreements (SLAs). But beyond the first-hop, QoS along the path from a source AS to a destination AS is not within the source AS's control regime. This makes it difficult to provide high quality-of-experience services to many Internet users even when many content providers are willing to pay for such high quality E2E guarantees. In this paper, we investigate the feasibility of providing high QoS-guaranteed E2E transit services by utilizing a (small) set of ASes/IXPs to serve as “brokers” to provide supervision, control and resource negotiation. Finding an optimal set of ASes as brokers can be formulated as a Maximum Coverage with$B-$dominating path Guarantee (MCBG) problem, and we show that it is in fact NP-hard. To address this problem, we design a$(\frac{1{-}e^{-\!1}}{2}){-}$approximation algorithm and also an efficient heuristic algorithm when additional constraints (e.g., the path length) are considered. We further analyze the APX-hardness of the MCBG problem to reveal the existence of the best approximation ratio. Based on the current Internet topology, we demonstrate that it is indeed feasible to provide high QoS guarantees for most E2E connections with only a small broker set: with only 0.19, 1.9 or 6.8 percent ASes/IXPs serving as brokers, 53.13, 85.41 or 99.29 percent of all global E2E connections can receive high QoS-guaranteed services. Finally, we provide an economic model to study the behaviours of ASes when cooperating our brokerage scheme with the BGP protocol, and show that there are incentives to form and maintain such a brokerage coalition.

Deploying Software-Defined Networks (SDNs) faces various challenges, and one of them is to implement per-flow control while preserving data plane scalability. Due to the limited rule storage space of commodity SDN switches, achieving flexible control and having a low-latency data plane with a low storage cost are often at odds. Unfortunately, existing SDN architectures fail to implement per-flow control efficiently: they either incur extra delays to packets or pose high storage burden to switches. In this paper, we propose Software-Defined Label Switching (SDLS) to achieve both data plane scalability and per-flow control. SDLS combines central control with label switching to reduce storage burden while maintaining per-flow control. SDLS introduces software switches into the data plane and manages the network in regions for scalability. SDLS is OpenFlow-compatible and employs a hybrid data plane to provide efficient flow setups. We evaluate SDLS by comparing with the state-of-the-art SDN architectures and show that SDLS can rival the best on the latency performance while reducing the number of flow entries and overflows by more than 47%.

The current inter-domain routing protocol, namely, the Border Gateway Protocol (BGP), cannot provide end-to-end (E2E) quality-of-service (QoS) guarantees. The main reason is that an autonomous system (AS) can only receive guarantees from its first hop ASes via service level agreements (SLAs). But beyond the first hop, QoS along the path from source to destination AS is not within the source AS's control regime. In this paper, we investigate the feasibility of providing high QoS-guaranteed E2E transit services by utilizing a (small) set of ASes/IXPs to serve as "brokers" to provide supervision, control and resource negotiation. Finding an optimal set of ASes as brokers can be formulated as a Maximum Coverage with B-dominating path Guarantee (MCBG) problem, which we prove to be NP-hard. To address this problem, we design a (1-e-1/4)-approximation algorithm and also an efficient heuristic algorithm when considering additional constraints (e.g., path length). Based on the current Internet topology, we discover a "3540-alliance" subset (accounting only 6.8%) of 52,079 ASes/IXPs, which can provide high QoS guarantees for 99.29% E2E connections.

In network management today, dynamic updates are required for traffic engineering and for timely response to security threats. Decisions for such updates are based on monitoring network traffic to compute numerical quantities based on a variety of network and application-level performance metrics. Today's state-of-the-art tools lack programming abstractions that capture application or session-layer semantics, and thus require network operators to specify and reason about complex state machines and interactions across layers. To address this limitation, we present the design and implementation of NetQRE, a high-level declarative toolkit that aims to simplify the specification and implementation of such quantitative network policies. NetQRE integrates regular-expression-like pattern matching at flow-level as well as application-level payloads with aggregation operations such as sum and average counts. We describe a compiler for NetQRE that automatically generates an efficient implementation with low memory footprint. Our evaluation results demonstrate that NetQRE allows natural specification of a wide range of quantitative network tasks ranging from detecting security attacks to enforcing application-layer network management policies. NetQRE results in high performance that is comparable with optimized manually-written low-level code and is significantly more efficient than alternative solutions, and can provide timely enforcement of network policies that require quantitative network monitoring.

The decoupling of control and data plane in software-defined networking (SDN) has been shown to be promising to improve routing performance in the context of intradomain routing. The applicability of SDN in inter-domain routing, especially with respect to route convergence, has not been properly explored. In this work, we propose a mathematical model to quantify the BGP convergence time for inter-domain routing by capturing only the essential components in BGP convergence process. Based on the model and some practical observations, we study how SDN may help to facilitate the interdomain routing. We further present a greedy algorithm that selects Autonomous Systems (ASes) for incremental SDN deployment with the objectives of minimizing the BGP convergence time. The simulation result based on the real world Internet topology confirms the effectiveness of our proposed algorithm.

Application Driven Network(ADN) is a new paradigm that provides on-demand differentiated services for applications. A physical network in ADN is sliced into various logically isolated sub-networks. Each network slice can have its own network architecture and protocol to serve one application exclusively. ADN enhances the user experience while keeping the resource efficiency by further imposing multiplexing among these logically isolated sub-networks.

Abstract This paper presents MTor, a low-latency anonymous group communication system. We construct MTor as an extension to Tor, allowing the construction of multi-source multicast trees on top of the existing Tor infrastructure. MTor does not depend on an external service to broker the group communication, and avoids central points of failure and trust. MTor’s substantial bandwidth savings and graceful scalability enable new classes of anonymous applications that are currently too bandwidth-intensive to be viable through traditional unicast Tor communication-e.g., group file transfer, collaborative editing, streaming video, and real-time audio conferencing. We detail the design of MTor and then analyze its performance and anonymity. By simulating MTor in Shadow and TorPS using realistic models of the live Tor network’s topology and recent consensus records from the live Tor network, we show that MTor achieves a 29% savings in network bandwidth and a 73% reduction in transmission time as compared to the baseline approach for anonymous group communication among 20 group members. We also demonstrate that MTor scales gracefully with the number of group participants, and allows dynamic group composition over time. Importantly, as more Tor users switch to group communication, we show that the overall performance and utilization for group communication improves. Finally, we discuss the anonymity implications of MTor and measure its resistance to traffic correlation.

Recent emergence of software-defined networks offers an opportunity to design domain-specific programming abstractions aimed at network operators. In this paper, we propose scenario-based programming, a framework that allows network operators to program network policies by describing representative example behaviors. Given these scenarios, our synthesis algorithm automatically infers the controller state that needs to be maintained along with the rules to process network events and update state. We have developed the NetEgg scenario-based programming tool, which can execute the generated policy implementation on top of a centralized controller, but also automatically infers flow-table rules that can be pushed to switches to improve throughput. We study a range of policies considered in the literature and report our experience regarding specifying these policies using scenarios. We evaluate NetEgg based on the computational requirements of our synthesis algorithm as well as the overhead introduced by the generated policy implementation. Our results show that our synthesis algorithm can generate policy implementations in seconds, and the automatically generated policy implementations have performance comparable to their hand-crafted implementations.

Data center network architecture is regarded as one of the most important determinants of network performance. As the most typical representatives of architecture design, the server-centric scheme stands out due to its good performance in various aspects. However, there still exist some critical shortcomings in these server-centric architectures. In order to provide an efficient solution to these shortcomings and improve the efficiency of server-centric architectures, in this paper, we propose a hardware based approach, named “Forwarding Unit”. Furthermore, we put forward a traffic aware routing scheme for FlatNet to further evaluate the feasibility and efficiency of our approach. Both theoretical analysis and simulation experiments are conducted to measure its overall performance with respect to cost-effectiveness, fault-tolerance, system latency, packet loss ratio, aggregate bottleneck throughput, and average path length.

The design of the data center network that interconnects the massive number of servers is very important to ensure the agility and robustness of the data center to meet the requirements of the applications. In response to this challenge, the research community have begun exploring novel interconnect topologies including FatTree, DCell, BCube, HyPaC, etc. However, the solutions proposed so far either scale too slowly, suffer from performance bottlenecks, are server-location dependent, inherit poor availability, or can be too complex/expensive to construct. Motivated by these very important challenges, we propose a new data center interconnect called FlatNet that combines the advantages of previous architectures while avoiding their limitations. FlatNet is a cost-effective, high-performance, reliable and scalable interconnect with almost flat architecture. For example, given an equal-sized data center, the costs of a FlatNet in terms of number of links and switches are roughly 2/3 and 2/5 that of Portland, while still delivering comparable overall performance.

Mega data centers are being built around the world to provide various cloud computing services. As a result, data center networking has recently been a hot research topic in both academia and industry. A fundamental challenge in this research is the design of the data center network that interconnects the massive number of servers, and provides efficient and fault-tolerant routing service to upper-layer applications. In response to this challenge, the research community have begun exploring novel interconnect topologies including Fat-Tree, DCell, and BCube and etc. Understandably, this research is still in its infancy. The proposed solutions either scale too fast (i.e., double exponentially) or too slow, suffer from performance bottlenecks, or can be quite costly in both routing and construction. In this paper, we propose a cost-effective and gracefully scalable data center interconnect termed Hyper-BCube that combines the advantages of both DCell and BCube architectures while avoiding their limitations. We then propose fault-tolerant and routing mechanisms for Hyper-BCube. Finally, we propose a comprehensive benchmarking environment that can be used for accurately and practically evaluating and testing the proposed data center architecture.

We propose the demonstration of SP4, a software-based programmable packet processing platform that supports (1) stateful packet processing useful for analyzing traffic flows with session semantics, (2) uses a task-stealing architecture that automatically leverages multi-core processing capabilities in a load-balanced manner without the need for explicit performance profiling, and (3) a declarative language for rapidly specifying and composing new packet processing functionalities from reusable modules. Our demonstration showcases the use of SP4 for performing high-throughput analysis of traffic traces for a variety of applications, such as filtering out unwanted traffic and detection of DDoS attacks using machine learning based analysis.

High-speed routers rely on well-designed packet buffers that support multiple queues, provide large capacity and short response times. Some researchers suggested combined SRAM/DRAM hierarchical buffer architectures to meet these challenges. However, these architectures suffer from either large SRAM requirement or high time-complexity in the memory management. In this paper, we present scalable, efficient, and novel distributed packet buffer architecture. Two fundamental issues need to be addressed to make this architecture feasible: 1) how to minimize the overhead of an individual packet buffer; and 2) how to design scalable packet buffers using independent buffer subsystems. We address these issues by first designing an efficient compact buffer that reduces the SRAM size requirement by (k-1)/k. Then, we introduce a feasible way of coordinating multiple subsystems with a load-balancing algorithm that maximizes the overall system performance. Both theoretical analysis and experimental results demonstrate that our load-balancing algorithm and the distributed packet buffer architecture can easily scale to meet the buffering needs of high bandwidth links and satisfy the requirements of scale and support for multiple queues.

Virtual Output Queuing (VOQ) is widely used by input-queued (IQ) packet switches to eliminate the head-of-line (HoL) blocking problem. A lot of research has been devoted to design iterative arbitration algorithms to maximize the throughput of this architecture. Nevertheless, these approaches require either a high computation complexity or large contention resolution times for high-speed switches. We investigate in this paper the performance of various such algorithms and based on the analysis of pointer desynchronization effect, we propose a new algorithm approximating maximum size matching (MSM) called Selective Request Round Robin (SRRR) which performs extremely well under various traffic models and is easy to implement in hardware.

High-speed routers rely on well-designed packet buffers that support multiple queues, large capacity and short response times. Some researchers suggested combined SRAM/DRAM hierarchical buffer architectures to meet these challenges. However, these architectures suffer from either large SRAM requirement or high time-complexity in the memory management. Our analysis indicates that they perform exactly the same in the worst case. In this paper, we present a novel packet buffer architecture which reduces the SRAM size requirement by (k-1)/2k, where k denotes the number of DRAMs working in parallel. We use a fast batch load scheme and per-queue Random Round Robin memory management algorithm. Our mathematical analysis and simulation results indicate that the proposed architecture provides guaranteed performance in terms of low time complexity, short access delay and upper-bounded drop rate, when a little speedup is provided.

High-speed routers rely on well-designed packet buffers that support multiple queuing, large capacity and short response times. Some researchers suggested a combined SRAM/DRAM hierarchical buffer architecture to meet these challenges. However, both the SRAM and DRAM need to maintain a large number of dynamic queues which is a real challenge in practice and limits the scalability of these approaches. In this paper, we present a scalable, efficient and novel distributed packet buffer architecture. Two fundamental issues need to be addressed to make this feasible: (a) how to design scalable packet buffers using independent buffer subsystems; and (b) how to dynamically balance the workload among multiple buffer subsystems without any blocking. We address these issues by first designing a basic framework that allows flows to dynamically switch from one subsystem to another without any blocking. Based on this framework, we further devise a load-balancing algorithm to meet the overall system requirements. Both theoretical analysis and experimental results demonstrate that our load-balancing algorithm and the distributed packet buffer architecture can easily scale to meet the buffering needs of high bandwidth links with large number of active connections.

In current high bandwidth-delay-product networks, traditional end-to-end network protocols cannot guarantee the fair allocation of network resources (i.e., a rogue source that sends at an uncontrolled rate can seize a large fraction of the buffers at an intermediate router which results in dropped packets for other connections). Fair-queuing (FQ) algorithms were proposed to overcome this drawback. However, most of these FQ algorithms either suffer from high time-complexity or greatly rely on the multiple queuing structures which are extremely difficult to implement in large scale due to the access delay of DRAM. Based on the analysis on real-life traces, we are able to determine the short-term stability of number of connections in a trunk. Taking this characteristic into consideration, a new FQ algorithm called Budget Round-Robin (BRR) is proposed in this paper. Both theoretical analysis and experimental results demonstrate that BRR and its corresponding memory hierarchy are much superior to the other FQ algorithms when we have a high bandwidth link with large number of active connections (e.g., high-speed Internet).

Switch-Memory-Switch (SMS) architecture exhibits an excellent performance due to its emulating the Output Queueing structure. However, in order to achieve the maximal matching, the first stage scheduling operates at a huge computational complexity, which blocks the SMS from practical implementation. In order to put SMS into more effective industrial applications, especially in super-large size switches/routers with multi-services environment, two parallel iterative scheduling algorithms, named IS-RRM and AIS-RRM respectively, are proposed in this paper. The algorithms abolish totally the traditional departure-time-compatible (DTC) graph, and by using iteration-sharing technology, greatly reduce the required iteration number in each time slot. Using a discrete-time Markov chain to model the AIS-RRM algorithm, we obtain its upper bound of cell loss rate. Meanwhile, experimental and theoretical results show that so long as the number of shared memories is twice the switch size, AIS-RRM algorithm can achieve a cell loss rate of 10 when the input buffer size is 15 and the iteration number of each time slot is 6, despite the arrival traffic pattern and the switch size. Furthermore, the iteration number required in each time slot can be further decreased by increasing the input buffer size.

With the continuous advances in optical communications technology, the link transmission speed of Internet backbone has been increasing rapidly. This in turn demands more powerful IP address lookup engine. In this paper, we propose a power-efficient parallel TCAM-based lookup engine with a distributed logical caching scheme for dynamic load-balancing. In order to distribute the lookup requests among multiple TCAM chips, a smart partitioning approach called pre-order splitting divides the route table into multiple sub-tables for parallel processing. Meanwhile, by virtual of the cache-based load balancing scheme with slow-update mechanism, a speedup factor ofN-1 can be guaranteed for a system with N (N>2) TCAM chips, even with unbalanced bursty lookup requests.

In this paper, we propose two non-orthogonal approaches to design linear transmit preceding matrices for the downlink of multi-user multi-input multi-output (MU-MIMO) communication over fading wireless channels. Both are better suited to solve the power control problem of minimizing the power output subject to a fixed set of rate requirements and do not have the strict constraint on the transmit and receive antenna numbers as the block-diagonalization (BD) algorithm does. One is named modified MRC scheme in which an iterative approach is introduced and for each user we compute the optimal preceding matrix to compensate the noise and the interference caused by other users without considering the interference it causes to others. The other one is named modified BD scheme in which for each user we only consider the dominant sub-channels that have relatively large channel gains when using the conventional BD algorithm. Theoretic analysis and simulation results reveal that the modified MRC scheme can achieve a better performance than BD algorithm under lower SNR regime and the modified BD scheme outperforms BD algorithm almost in all cases

UNLABELLED: Short interfering RNAs (siRNAs) have been gaining popularity as the gene knock-down tool of choice by many researchers because of the clean nature of their workings as well as the technical simplicity and cost efficiency in their applications. We have constructed siRecords, a database of siRNAs experimentally tested by researchers with consistent efficacy ratings. This database will help siRNA researchers develop more reliable siRNA design rules; in the mean time, siRecords will benefit experimental researchers directly by providing them with information about the siRNAs that have been experimentally tested against the genes of their interest. Currently, more than 4100 carefully annotated siRNA sequences obtained from more than 1200 published siRNA studies are hosted in siRecords. This database will continue to expand as more experimentally tested siRNAs are published. AVAILABILITY: The siRecords database can be accessed at http://siRecords.umn.edu/siRecords/

BACKGROUND: Short interfering RNAs have allowed the development of clean and easily regulated methods for disruption of gene expression. However, while these methods continue to grow in popularity, designing effective siRNA experiments can be challenging. The various existing siRNA design guidelines suffer from two problems: they differ considerably from each other, and they produce high levels of false-positive predictions when tested on data of independent origins. RESULTS: Using a distinctly large set of siRNA efficacy data assembled from a vast diversity of origins (the siRecords data, containing records of 3,277 siRNA experiments targeting 1,518 genes, derived from 1,417 independent studies), we conducted extensive analyses of all known features that have been implicated in increasing RNAi effectiveness. A number of features having positive impacts on siRNA efficacy were identified. By performing quantitative analyses on cooperative effects among these features, then applying a disjunctive rule merging (DRM) algorithm, we developed a bundle of siRNA design rule sets with the false positive problem well curbed. A comparison with 15 online siRNA design tools indicated that some of the rule sets we developed surpassed all of these design tools commonly used in siRNA design practice in positive predictive values (PPVs). CONCLUSION: The availability of the large and diverse siRNA dataset from siRecords and the approach we describe in this report have allowed the development of highly effective and generally applicable siRNA design rule sets. Together with ever improving RNAi lab techniques, these design rule sets are expected to make siRNAs a more useful tool for molecular genetics, functional genomics, and drug discovery studies.

This paper focuses on improving an LSP-based multi-description coding (MDC) scheme for concealing losses when real-time CELP-coded speech data is sent over IP networks. In that scheme, LSP vectors are interleaved because they are highly correlated and can be reconstructed by interpolations when packets are delayed or lost. However, excitation vectors are random in nature and must be replicated in order to conceal losses. To avoid increasing the bit rate of the encoded speech, the excitation vectors are generated from longer subframes. This leads to lower quality of the decoded speech because noise from outside formant regions is over-emphasized, and more excitation information is extracted there. To improve quality, we propose in this paper to modify the perceptual-weighting filter (PWF) in the coder in order to adjust the allocation of noise inside and outside formant regions. We further study a method that selects the PWF in such a way that maintains high quality of the LSP-based MDC across different voice streams and loss scenarios. Experimental results on FS-1016 CELP (4800 bps), ITU G.723.1 ACELP (5300 bps), and ITU G.723.1 MP-MLQ (6300 bps) demonstrate noticeable improvements in decoding quality

A fundamental issue in real-time interactive voice transmissions over unreliable IF networks is the loss or late arrival of packets for playback. This problem is especially serious when transmitting low bit rate-coded speech with pervasive dependencies introduced. In this case, the loss or late arrival of a single packet will lead to the loss of subsequent dependent frames. We study end-to-end loss-concealment schemes for ensuring high quality in playback. We propose a novel multiple description-coding method for concealing packet losses in transmitting low bit rate-coded speech. Based on high correlations observed in linear predictor parameters-in the form of Line Spectral Pairs (LSPs)-of adjacent frames, we generate multiple descriptions in senders by interleaving LSPs, and reconstruct lost LSPs in receivers by linear interpolations. As excitation codewords have low correlations, we further enlarge the segment size for excitation generation and replicate excitation codewords in all the descriptions in order to maintain the same transmission bandwidth. Our proposed scheme can be extended easily to more than two descriptions and can adapt its number of descriptions dynamically to network-loss conditions. Experimental results on FS-1016 CELP, ITU G.723.1, and FS MELP coders show good performance of our scheme.

A fundamental issue in real-time interactive voice transmissions over unreliable IP networks is the loss or late arrival of packets for playback. Such losses cannot be recovered by retransmissions due to tight time constraints in interactive applications. This problem is especially serious in transmitting low bit-rate coded speech when pervasive dependencies are introduced in a bit stream, leading to the loss of subsequent dependent frames when a single packet is lost or arrives late. We propose a novel LSP-based multiple-description coding method that adapts its number of descriptions to network loss conditions in order to conceal packet losses in transmitting low-bit-rate coded speech over lossy packet networks. Based on high correlations observed in linear predictor parameters, in the form of line spectral pairs (LSPs), of adjacent frames, we generate multiple descriptions in a sender by interleaving LSPs, and reconstruct lost LSPs in a receiver by linear interpolations. Without increasing the transmission bandwidth, our scheme represents a trade-off between the quality of received packets and the ability to reconstruct lost packets. Our experimental results on FS CELP show good performance.

If data traffic were Poisson, increases in the amount of traffic aggregated on a network would rapidly decrease the relative size of bursts. The discovery of pervasive long-range dependence demonstrates that real network traffic is burstier than any possible Poisson model. We present evidence that, despite being non-Poisson, aggregating Web traffic causes it to smooth out as rapidly as Poisson traffic. That is, the relationship between changes in mean bandwidth and changes in variance is the same for Web traffic as it is for Poisson traffic. We derive our evidence from traces of real traffic in two ways: first, by observing how variance changes over the large range of mean bandwidths present in 24-hour traces; second, by observing the relationship of variance and mean bandwidth for individual users and combinations of users. Our conclusion, that variance changes linearly with mean bandwidth, should be useful (and encouraging) to anyone provisioning a network for a large aggregate load of Web traffic.

TCP start times for HTTP are nonstationary. The nonstationarity occurs because the start times on a link, a point process, are a superposition of source traffic point processes, and the statistics of superposition changes as the number of superposed processes changes. The start time rate is a measure of the number of traffic sources. The univariate distribution of the inter-arrival times is approximately Weibull, and as the rate increases, the Weibull shape parameter goes to 1, an exponential distribution. The autocorrelation of the log inter-arrival times is described by a simple, two-parameter process: white noise plus a long-range persistent time series. As the rate increases, the variance of the persistent series tends to zero, so the log times tend to white noise. A parsimonious statistical model for log inter-arrivals accounts for the autocorrelation, the Weibull distribution, and the nonstationarity in the two with the rate. The model, whose purpose is to provide stochastic input to a network simulator, has the desirable property that the superposition point process is generated as a single stream. The parameters of the model are functions of the rate, so to generate start times, only the rate is specified. As the rate increases, the model tends to a Poisson process. These results arise from theoretical and empirical study based on the concept of connection-rate superposition. The theory is the mathematics of superposed point processes, and the empiricism is an analysis of 23 million TCP connections organized into 10704 blocks of approximately 15 minutes each.

One fundamental problem with streaming audio and video data over unreliable IP networks is that packets may be dropped or arrive too late for playback. Traditional error control schemes are not attractive because they either add redundant information that may worsen network traffic, or rely solely on the inadequate capability of the decoder to do error concealment. The authors propose a simple yet efficient transformation based algorithm in order to conceal network losses in streaming real time audio and video data over the Internet. In the receiver side, we adopt a simple reconstruction algorithm based on interpolation, as sophisticated concealment techniques cannot be employed in software based real time playback. In the sender side, we design a linear transformation with the objective of minimizing the mean squared error, assuming that some of the descriptions are lost and that the missing information is reconstructed by simple averaging at the destination. We further integrate the transformations in case of video streaming in the discrete cosine transform (DCT) to produce an optimized reconstruction based DCT. Experimental results show that our proposed algorithm performs well in real Internet tests.

We explore the loss behavior encountered in transmitting real-time voice over the Internet and propose a new loss-concealment scheme to improve its received quality. One known technique to conceal loss is to send interleaved streams of voice samples and reconstruct missing or late samples by interpolation at the receiver. Based on this method, we propose a new transformation-based reconstruction algorithm. Its basic idea is for the sender to transform an input voice stream, according to the interpolation method used at the receiver and the predicted loss behavior, before interleaving the stream. The transformation is derived by minimizing reconstruction error in case of loss. We show that our method is computationally efficient and can be extended to various interleaving factors and interpolation-based reconstruction methods. Finally, we show performance improvements of our method by testing it over the Internet.

To match an ideal Internet gateway which rigorously enforces fair sharing among competing TCP connections, an ideal TCP sender should possess two properties while obeying congestion avoidance and control principles. First, the TCP sender which under-uses network resources should avoid retransmission time-outs. When experiencing network congestion, a TCP connection should not time-out unless it has already reduced its congestion window to one packet but still cannot survive. Second, the TCP sender which over-uses network resources should lower its bandwidth. The congestion window for a connection should decrease each time a lost packet is detected because an ideal gateway will drop packets, during congestion, with a probability proportional to the bandwidth of the connection. Following these guidelines, we propose network-sensitive Reno (Net Reno), a set of optimizations that can be added to a traditional Reno TCP sender. Using the TCP's self-clocking property and the packet conservation rule, Net Reno improves Reno and its variants (New-Reno and SACK), in reducing TCP retransmission time-outs (RTOs) and in being conservative in network usage during the fast recovery phase. We have shown that over 85% of RTOs are due to small congestion windows that prevent fast retransmission and recovery algorithms from being effective. This implies that sophisticated recovery schemes such as SACK will have limited benefits for these loads. Net Reno overcomes this problem with a small window optimization. Net Reno can recover any number of packet losses without time-outs as long as the network keeps at least one packet alive for the connection.

The paper studies the design of data transformation algorithms for audio data transmitted over the Internet, with a goal of reconstructing the original signals by the receiver with little distortions in the presence of bursty loss of packets. It assumes that a single audio stream is interleaved into multiple packets, and a lost sample at the receiver is reconstructed as the interpolation of adjacent samples received. We propose a non redundant transformation based reconstruction algorithm that can minimize the reconstruction error for any fixed, interpolation based reconstruction algorithm. Its basic idea is that the sender transforms the input audio stream optimally, based on the reconstruction method used at the receiver before sending the data packets. Consequently, the receiver is able to recover much better from losses of packets than without any knowledge of what the signals should be. In particular, we study our transformation algorithm based on one popular linear interpolation based reconstruction algorithm. We found that our scheme can improve the signal to noise ratio (SNR) by 1 to 2 dB with very little extra computation efforts as compared to the scheme without transformation.

We present an analysis of an existing rate-based ABR scheduling algorithm described by Kline (see ATM-Forum Contribution 94-0849), and propose an enhanced rate-based round robin (RBR) scheduling algorithm for ATM switches and end systems. One of the novel aspects of RBR is that the scheduler supports available bit rate (ABR) traffic as well as guaranteed bandwidth reservations. In addition, bandwidth overbooking is allowed by the scheduler for ABR services to improve the link efficiency as recommended by most flow control schemes. Under competition, the scheduler distributes the bandwidth in a max-min fair way. Any unused reservations for guaranteed services are reallocated to ABR services. Finally, the operations performed during each scheduling cycle are constant, independent of the number of connections. Simulation results are also presented and analyzed.

In this paper we evaluate the effectiveness of Random Early Detection (RED) over traffic types categorized as non-adaptive, fragile and robust, according to their responses to congestion. We point out that RED allows unfair bandwidth sharing when a mixture of the three traffic types shares a link. This unfairness is caused by the fact that at any given time RED imposes the same loss rate on all flows, regardless of their bandwidths.We propose Fair Random Early Drop (FRED), a modified version of RED. FRED uses per-active-flow accounting to impose on each flow a loss rate that depends on the flow's buffer use.We show that FRED provides better protection than RED for adaptive (fragile and robust) flows. In addition, FRED is able to isolate non-adaptive greedy traffic more effectively. Finally, we present a "two-packet-buffer" gateway mechanism to support a large number of flows without incurring additional queueing delays inside the network. These improvements are demonstrated by simulations of TCP and UDP traffic.FRED does not make any assumptions about queueing architecture; it will work with a FIFO gateway. FRED's per-active-flow accounting uses memory in proportion to the total number of buffers used: a FRED gateway maintains state only for flows for which it has packets buffered, not for all flows that traverse the gateway.