Packet schedulers are essential for managing packet transmission order in high-speed networks, where scheduling metadata must be processed at line rate under bursty traffic conditions. In such systems, packet scheduling and traffic management operate on compact packet descriptors rather than on full packets. FIFO-based schedulers are attractive for their simplicity and throughput, but implementations that statically partition descriptor memory across queues must provision for worst-case occupancy, leading to inefficient memory utilization. This paper presents MetaFlex, a scalable architecture for efficient implementation of calendar-queue–based packet scheduling using shared descriptor memory. MetaFlex dynamically allocates descriptor storage to scheduling queues on demand, allowing memory to be effectively shared across a large number of rank bins while maintaining constant-time enqueue and dequeue operations. Rather than introducing a new scheduling algorithm, MetaFlex focuses on the architectural realization of shared-memory descriptor queues that scale to large queue counts with predictable timing and modest hardware cost. We evaluate MetaFlex using NS2 simulations of weighted fair scheduling and a hardware prototype implemented in VHDL on an AMD/Xilinx Alveo U250 FPGA board. Simulation results show that MetaFlex achieves comparable or lower packet loss than fixed-memory calendar queues under identical descriptor-memory budgets, while using substantially less descriptor storage under typical traffic conditions. The FPGA prototype operates at 322 MHz, sustains 100 Gb/s line rate for packets larger than 370 bytes, and uses less than 1% of logic resources and less than 5% of on-chip memory, demonstrating the practicality of MetaFlex for high-speed hardware datapaths.

Traffic Engineering (TE) has been widely used by network operators to improve network performance and deliver better service quality. One major challenge for TE is providing routing strategies that can adapt to highly dynamic future traffic scenarios. Unfortunately, existing works either suffer severe performance degradation under unexpected traffic fluctuations, or sacrifice optimality to guarantee worst-case performance when traffic remains relatively stable. In this paper, we propose LARRI, a learning-based TE framework that predicts adaptive routing strategies for unknown future traffic scenarios. By integrating future demand range prediction and optimal range routing imitation into a single step, LARRI learns to generate a routing strategy that accommodates a wide range of possible future traffic matrices, thereby achieving a good trade-off between performance optimality and worst-case guarantees. Moreover, LARRI employs a scalable graph neural network architecture, which greatly facilitates both training and inference. Extensive simulations on six real-world network topologies show that LARRI achieves near-optimal load balancing in future traffic scenarios, improves worst-case performance by up to 43.3% over state-of-the-art baselines, and consistently provides the lowest end-to-end delay under dynamic traffic fluctuations.

Software-Defined Wide Area Networking (SD-WAN) has emerged as a popular solution for today’s enterprise networks, where Traffic Engineering (TE) plays a crucial role in optimizing traffic distribution across different overlay tunnels. During network congestion, traditional SD-WAN approaches often switch traffic to backup Multiprotocol Label Switching (MPLS) tunnels with high economic costs. To address this issue, we introduce Dynamic Path Switching (DPS), a novel SD-WAN TE solution that leverages underlay path diversity within an Internet overlay tunnel to maintain high Quality of Service (QoS) while substantially reducing economic costs. DPS operates on a Virtual extensible Local Area Network (VXLAN) overlay and controls the 5-tuple flow ID in the outer encapsulation header of traffic flows at SD-WAN gateways, which enables Internet Service Providers (ISPs) to dynamically switch traffic flows across multiple underlay paths based on the hashing results of their flow IDs. Moreover, we leverage extended Berkeley Packet Filter (eBPF) to implement DPS with high efficiency. Our prototype implementation, evaluated on a real Internet testbed, demonstrates that DPS can provide 99.974% service availability for enterprise traffic while reducing economic costs by 64.26% compared to traditional MPLS-based SD-WAN TE solutions.

Distributed Traffic Engineering (TE) aims to optimize network performance by generating individual routing strategies at each router without a global view of the network. A major challenge for these TE solutions is handling performance degradation caused by unexpected traffic fluctuations and unpredictable link failures. Recently, Machine Learning (ML) techniques have introduced new opportunities to enhance distributed TE. In this paper, we propose Path-Based Graph Neural Network (PathGNN), which leverages the emerging GNN architecture to quickly infer robust and resilient routing strategies in a distributed manner to accommodate unexpected network conditions. PathGNN adopts a novel path-link bipartite graph modeling approach to capture the dynamics of link resources shared by routing paths. It then performs efficient GNN message exchanges among routers to make adaptive local routing decisions for better load balancing. Additionally, PathGNN leverages Supervised Learning (SL) to directly learn from optimal routing strategies through efficient offline training. Evaluation results on four real-world network topologies demonstrate PathGNN’s strong generalization capability. Compared to state-of-the-art distributed TE solutions, PathGNN improves the load balancing performance by at least 24.4% with lower end-to-end delay under dynamic traffic scenarios, and also boosts performance by up to 35.3% under multiple link failures.

Traditional Traffic Engineering (TE) usually balances the load on network links by formulating and solving a routing optimization problem based on measured Traffic Matrices (TMs). Given that traffic demands could change unexpectedly and significantly in realistic scenarios, routing strategies opti-mized based on currently measured TMs might not work well in future traffic scenarios. To compensate for the mismatch between stale routing decisions and future TMs, network operators may perform routing updates more frequently, which could introduce significant network disturbance and service disruption. Moreover, given the high routing computation overhead of TE optimization in today's large-scale networks, routing updates could experience severe delay and thus cannot accommodate future traffic changes in time. To address these challenges, we propose Roracle, a scalable learning-based TE that quickly predicts a good routing strategy for a long sequence of future TMs, while the learning process is guided by the optimal solutions of Linear Programming (LP) problems using Supervised Learning (SL). We design a scalable Graph Neural Network (GNN) architecture that greatly facilitates training and inference processes to accelerate TE in large networks. Extensive simulation results on real-world network topologies and traffic traces show that Roracle outperforms existing TE solutions by up to 36% in terms of worst-case performance under future unknown traffic scenarios. Additionally, Roracle achieves good scalability by providing at least$71\times$speedup over the most efficient baseline method in large-scale networks.

Traffic Engineering (TE) has been widely used by network operators to improve network performance and provide better service quality to users. One major challenge for TE is how to generate good routing strategies adaptive to highly dynamic future traffic scenarios. Unfortunately, existing works could either experience severe performance degradation under unexpected traffic fluctuations or sacrifice performance optimality for guaranteeing the worst-case performance when traffic is relatively stable. In this paper, we propose LARRI, a learning-based TE to predict adaptive routing strategies for future unknown traffic scenarios. By learning and predicting a routing to handle an appropriate range of future possible traffic matrices, LARRI can effectively realize a trade-off between performance optimality and worst-case performance guarantee. This is done by integrating the prediction of future demand range and the imitation of optimal range routing into one step. Moreover, LARRI employs a scalable graph neural network architecture to greatly facilitate training and inference. Extensive simulation results on six real-world network topologies and traffic traces show that LARRI achieves near-optimal load balancing performance in future traffic scenarios with up to 43.3% worst-case performance improvement over state-of-the-art baselines, and also provides the lowest end-to-end delay under dynamic traffic fluctuations.

Emerging applications pose different Quality of Service (QoS) requirements for the network, where Traffic Engineering (TE) plays an important role in QoS provisioning by carefully selecting routing paths and adjusting traffic split ratios on routing paths. To accommodate diverse QoS requirements of traffic flows under network dynamics, TE usually periodically computes an optimal routing strategy and updates a significant number of forwarding entries, which introduces considerable network operation management overhead. In this paper, we propose QoS-RL, a Reinforcement Learning (RL)-based TE solution for QoS provisioning and load balancing with low management overhead and service disruption during routing updates. Given the traffic matrices that represent the traffic demands of high and low priority flows, QoS-RL can intelligently select and update only a few destination-based forwarding entries to satisfy the QoS requirements of high priority traffic while maintaining good load balancing performance by rerouting a small portion of low priority traffic. Extensive simulation results on four real-world network topologies demonstrate that QoS-RL provides at least 95.5 % of optimal end-to-end delay performance on average for high priority flows, and also achieves above 90 % of optimal load balancing performance in most cases by updating only 10% of destination-based forwarding entries.

Push-In-First-Out (PIFO) queue has been extensively studied as a programmable scheduler. To achieve accurate, large-scale, and high-throughput PIFO implementation, we propose the Balanced Multi-way (BMW) Sorting Tree for real-time packet sorting. The tree is highly modularized, insertion-balanced and pipeline-friendly with autonomous nodes.

In this work, for the first time, we demonstrate that computers can automatically learn from observing the heuristic efforts of the last four decades, stand on the shoulders of the existing Internet congestion control (CC) schemes, and discover a better-performing one. To that end, we address many different practical challenges, from how to generalize representation of various existing CC schemes to serious challenges regarding learning from a vast pool of policies in the complex CC domain and introduce Sage. Sage is the first purely data-driven Internet CC design that learns a better scheme by harnessing the existing solutions. We compare Sage's performance with the state-of-the-art CC schemes through extensive evaluations on the Internet and in controlled environments. The results suggests that Sage has learned a better-performing policy. While there are still many unanswered questions, we hope our data-driven framework can pave the way for a more sustainable design strategy.

Traffic Engineering (TE) is an important network operation that routes/reroutes flows based on network topology and traffic demands to optimize network performance. Recently, new emerging applications pose challenges to TE with dynamic network conditions, where frequent routing updates are required to maintain good network performance with Software-Defined Networking (SDN). However, flow rerouting operations could lead to considerable Quality of Service (QoS) degradation and service disruption, which is often neglected by existing TE solutions. In this paper, we apply a new QoS metric named network disturbance to measure the negative impact of flow rerouting operations performed by TE. To achieve near-optimal load balancing performance and mitigate network disturbance together in dynamic network scenarios, we propose a flexible and disturbance-aware TE solution called FlexDATE that combines Reinforcement Learning (RL) and Linear Programming (LP). Specifically, FlexDATE leverages RL to intelligently identify flexible numbers of critical flows for each traffic matrix and reroutes these critical flows based on LP optimization to improve network performance with low disturbance. Empowered by a customized actor-critic architecture coupled with Graph Neural Networks (GNNs), FlexDATE can generalize well to unseen traffic scenarios and remain resilient to single link failures. Extensive simulations are conducted on five real-world network topologies to evaluate FlexDATE with real and synthetic traffic traces. The results show that FlexDATE can achieve the performance target (i.e., 90% of optimal performance) in 99% of network scenarios and effectively mitigate the average and maximum network disturbance by up to 9.1% and 38.6%, respectively, compared to state-of-the-art TE solutions.

Programmable switches have been proposed in today’s network to enable flexible reconfiguration of devices and reduce time-to-deployment. Buffer sizing, an important factor for network performance, however, has not received enough attention in programmable network. The state-of-the-art buffer sizing solutions usually employ either fixed buffer size or adjust the buffer size heuristically. Without programmability, they suffer from either massive packet drops or large queueing delay in dynamic environment. In this paper, we propose Adaptive Buffer Sizing (ABS), a low-cost and deploy-friendly framework compatible with programmable network. By decoupling the data plane and control plane, ABS-capable switches only need to react to the actions from controller, optimizing network performance in run-time under dynamic traffic. Meanwhile, actions can be programmed by particular Machine Learning (ML) models in the controller to meet different network requirements. In this paper, we address two specific ML models for different scenarios, a reinforcement learning model for relatively stable network with user specific quality requirements, and a supervised learning model for highly dynamic network condition. We implement the ABS framework by integrating the prevalent network simulator NS-2 with ML module. The experiment shows that ABS outperforms state-of-the-art buffer sizing solutions by up to 38.23x under various network environments.

Real-time video communication is profoundly changing people's lives, especially in today's pandemic situation. However, packet loss during video transmission degrades reconstructed video quality, thus impairing users' Quality of Experience (QoE). Forward Error Correction (FEC) techniques are commonly employed in today's audio and video conferencing applications, such as Skype and Zoom, to mitigate the impact of packet loss. FEC helps recover the lost packets during transmissions at the receiver side, but the additional bandwidth consumption is also a concern. Since network conditions are highly dynamic, it is not trivial for FEC to maintain video quality with a fixed bandwidth overhead. In this paper, we propose RL-AFEC, an adaptive FEC scheme based on Reinforcement Learning (RL) to improve reconstructed video quality with an aim to mitigate bandwidth consumption for different network conditions. RL-AFEC learns to select a proper redundancy rate for each video frame, and then adds redundant packets based on the frame-level Reed-Solomon (RS) code. We also implement a novel packet-level Video Quality Assessment (VQA) method based on Video Multimethod Assessment Fusion (VMAF), which leverages Supervised Learning (SL) to generate video quality scores in real time by only extracting information from the packet stream without the need of visual contents. Extensive evaluations demonstrate the superiority of our scheme over other baseline FEC methods.

Traffic Engineering (TE) is a widely-adopted network operation to optimize network performance and resource utilization. Destination-based routing is supported by legacy routers and more readily deployed than flow-based routing, where the forwarding entries could be frequently updated by TE to accommodate traffic dynamics. However, as the network size grows, destination-based TE could render high time complexity when generating and updating many forwarding entries, which may limit the responsiveness of TE and degrade network performance. In this paper, we propose a novel destination-based TE solution called FlexEntry, which leverages emerging Reinforcement Learning (RL) to reduce the time complexity and routing update overhead while achieving good network performance simultaneously. For each traffic matrix, FlexEntry only updates a few forwarding entries calledcritical entriesfor redistributing a small portion of the total traffic to improve network performance. These critical entries are intelligently selected by RL with traffic split ratios optimized by Linear Programming (LP). We find out that the combination of RL and LP is very effective. Our simulation results on six real-world network topologies show that FlexEntry reduces up to 99.3% entry updates on average and generalizes well to unseen traffic matrices with near-optimal load balancing performance.

Load Balancing plays a vital role in cloud data centers to distribute traffic among instances of network functions or services. State-of-the-art load balancers dispatch traffic obliviously without considering the real-time utilization of service instances and therefore can lead to uneven load distribution and sub-optimal performance. In this article, we design and implement Spotlight, a scalable and distributed load balancing architecture that maintains connection-to-instance mapping consistency at the edge of data center networks. Spotlight uses a new stateful flow dispatcher which periodically polls instances’ load and dispatches incoming connections to instances in proportion to their available capacity. Our design utilizes a distributed control plane and in-band flow dispatching; thus, it scales horizontally in data center networks. Through extensive flow-level simulation and packet-level experiments on a testbed with HTTP traffic on unmodified Linux kernel, we demonstrate that compared to existing methods Spotlight distributes traffic more efficiently and has near-optimum performance in terms of overall service utilization. Compared to existing solutions, Spotlight improves aggregated throughput and average flow completion time by at least 20 percent with infrequent control plane updates. Moreover, we show that Spotlight scales horizontally as it updates the switches at O(100ms) and is resilient to lack of control plane convergence.

The recent emergence of Connected Autonomous Vehicles (CAVs) enables the Autonomous Intersection Management (AIM) system, replacing traffic signals and human driving operations for improved safety and road efficiency. When CAVs approach an intersection, AIM schedules their intersection usage in a collision-free manner while minimizing their waiting times. In practice, however, there are pedestrian road-crossing requests and spillback problems, a blockage caused by the congestion of the downstream intersection when the traffic load exceeds the road capacity. As a result, collisions occur when CAVs ignore pedestrians or are forced to the congested road. In this article, we present a cooperative AIM system, named Roadrunner+ , which simultaneously considers CAVs, pedestrians, and upstream/downstream intersections for spillback handling, collision avoidance, and efficient CAV controls. The performance of Roadrunner+ is evaluated with the SUMO microscopic simulator. Our experimental results show that Roadrunner+ has 15.16% higher throughput than other AIM systems and 102.53% higher throughput than traditional traffic signals. Roadrunner+ also reduces 75.62% traveling delay compared to other AIM systems. Moreover, the results show that CAVs in Roadrunner+ save up to 7.64% in fuel consumption, and all the collisions caused by spillback are prevented in Roadrunner+.

Software-defined networking (SDN) is increasingly popular in today’s information technology industry, but existing SDN control plane is insufficiently scalable to support on-demand, high-frequency flow requests. Weaknesses along SDN control paths can be exploited by malicious third parties to launch distributed denial-of-service (DDoS) attacks against the SDN control plane. Recently proposed solutions only partially solve the problem, by protecting either the SDN network edges or the centralized controller. We propose SDNShield, a solution based on emerging network function virtualization (NFV) technologies, which enforces more comprehensive defense against potential DDoS attacks on SDN control plane. SDNShield incorporates a three-stage overload control scheme. The first stage statistically identifies legitimate flows with low complexity and performance overhead. The second stage further performs in-depth TCP handshake verification to ensure good flows are eventually served. The third stage intellectually salvages the misclassified legitimate flows that are falsely dropped from the first two stages. Prototype tests and real data-driven simulation results show that SDNShield can achieve high resilience against brute-force attacks, and maintain good flow-level service quality at the same time.

Network operators usually adopt Traffic Engineering (TE) to configure the routing in their networks to achieve good load balancing performance and high resource utilization. While centralized TE can effectively improve network performance with a global view of the network, distributed TE has been considered as an alternative to manage large-scale networks that are usually partitioned into multiple regions. However, it is challenging for distributed TE to reach a global optimal performance since each region can make its local routing decisions only based on partially observed network states. In this paper, we propose a novel distributed TE scheme called FedTe, which leverages supervised learning coupled with a collaborative approach to improve the overall load balancing performance for multi-region networks. FedTe learns from the global optimal routing strategy in a centralized offline manner and predicts the optimal distribution of cross-region traffic among different regions through distributed deployment in real time. The predicted cross-region traffic distribution is integrated with measured local traffic to construct each region’s optimal regional traffic matrix, which is used to perform intra-region TE optimization. FedTe can also handle dynamic traffic variation and link failures with a 2-layer hierarchical graph neural network architecture. To validate the effectiveness of the proposed scheme, we evaluate FedTe with two real-world network topologies and a large-scale synthetic topology. Extensive evaluation results show that FedTe can achieve near-optimal load balancing performance and outperform state-of-the-art distributed TE approaches by up to 28.9% on average.

Traffic Engineering (TE) has been applied to optimize network performance by routing/rerouting flows based on traffic loads and network topologies. To cope with network dynamics from emerging applications, it is essential to reroute flows more frequently than today’s TE to maintain network performance. However, existing TE solutions may introduce considerable Quality of Service (QoS) degradation and service disruption since they do not take the potential negative impact of flow rerouting into account. In this paper, we apply a new QoS metric named network disturbance to gauge the impact of flow rerouting while optimizing network load balancing in backbone networks. To employ this metric in TE design, we propose a disturbance-aware TE called DATE, which uses Reinforcement Learning (RL) to intelligently select some critical flows between nodes for each traffic matrix and reroute them using Linear Programming (LP) to jointly optimize network performance and disturbance. DATE is equipped with a customized actor-critic architecture and Graph Neural Networks (GNNs) to handle dynamic traffic and single link failures. Extensive evaluations show that DATE can outperform state-of-the-art TE methods with close-to-optimal load balancing performance while effectively mitigating the 99th percentile network disturbance by up to 31.6%.

Can we instead of designing yet another new TCP algorithm, design a TCP plug-in that can enable machines to automatically boost the performance of the existing/future TCP designs in cellular networks? We answer this question by introducing DeepCC. DeepCC leverages advanced deep reinforcement learning (DRL) techniques to let machines automatically learn how to steer throughput-oriented TCP algorithms toward achieving applications' desired delays in a highly dynamic network such as the cellular network. We used DeepCC plug-in to boost the performance of various old and new TCP schemes including TCP Cubic, Google's BBR, TCP Westwood, and TCP Illinois in cellular networks. Through both extensive trace-based evaluations and real-world experiments, we show that not only DeepCC can significantly improve the performance of TCP schemes, but also after accompanied by DeepCC, these schemes can outperform state-of-the-art TCP protocols including new clean-slate machine learning-based designs and the ones designed solely for cellular networks.

Power-efficient Data Center Networks (DCNs) have been proposed to save power of DCNs using OpenFlow. In these DCNs, the OpenFlow controller adaptively turns on/off links and OpenFlow switches to form a minimum-power subnet that satisfies the traffic demand. As the subnet changes, flows are dynamically routed and rerouted to the routes composed of active switches and links. However, existing flow scheduling schemes could cause undesired results: (1) power inefficiency: due to unbalanced traffic allocation on active routes, extra switches and links may be activated to cater to bursty traffic surges on congested routes, and (2) Quality of Service (QoS) fluctuation: because of the limited flow entry processing ability, switches may not be able to timely install/delete/update flow entries to properly route/reroute flows. In this paper, we propose AggreFlow, a dynamic flow scheduling scheme that achieves power efficiency and QoS improvement using three techniques: Flow-set Routing, Lazy Rerouting, and Adaptive Rerouting. Flow-set Routing achieves load balancing with a small number of flow entry operations by routing flows in a coarse-grained flow-set fashion. Lazy Rerouting spreads rerouting operations over a relatively long period of time, reducing the burstiness of entry operation on switches. Adaptive Rerouting selectively reroutes flow-sets to maintain load balancing. We built an NS3 based fat-tree network simulation platform to evaluate AggreFlow's performance. The simulation results show that AggreFlow reduces power consumption by about 18%, yet achieving load balancing and improved QoS (low packet loss rate and reducing the number of processing entries for flow scheduling by 98%), compared with baseline schemes.

Although many distributed denial of service (DDoS) attacks detection algorithms have been proposed and even some of them have claimed high detection accuracy, DDoS attacks are still a major problem for network security. The latent and inherent problems of these detection algorithms are 1) Requirement of both normal and attack data for building detection models, and 2) Almost inability to detect novel and unknown DDoS attacks. To conquer the problems, this paper proposes an AutoEncoder based DDoS attacks Detection Framework (AE-D3F), which only uses normal traffic to build the detection model and is able to update itself automatically as time goes. Experimental results on synthetic and public traffic show that our AE-D3F can not only achieve 82.00% detection rate (DR) with 0 false positive rate (FPR), better than classical anomaly detection approaches, but also detect novel and unknown attacks.

These days, taking the revolutionary approach of using clean-slate learning-based designs to completely replace the classic congestion control schemes for the Internet is gaining popularity. However, we argue that current clean-slate learning-based techniques bring practical issues and concerns such as overhead, convergence issues, and low performance over unseen network conditions to the table. To address these issues, we take a pragmatic and evolutionary approach combining classic congestion control strategies and advanced modern deep reinforcement learning (DRL) techniques and introduce a novel hybrid congestion control for the Internet named Orca1. Through extensive experiments done over global testbeds on the Internet and various locally emulated network conditions, we demonstrate that Orca is adaptive and achieves consistent high performance in different network conditions, while it can significantly alleviate the issues and problems of its clean-slate learning-based counterparts.

Traditional Traffic Engineering (TE) solutions can achieve the optimal or near-optimal performance by rerouting as many flows as possible. However, they do not usually consider the negative impact, such as packet out of order, when frequently rerouting flows in the network. To mitigate the impact of network disturbance, one promising TE solution is forwarding the majority of traffic flows using Equal-Cost Multi-Path (ECMP) and selectively rerouting a few critical flows using Software-Defined Networking (SDN) to balance link utilization of the network. However, critical flow rerouting is not trivial because the solution space for critical flow selection is enormous. Moreover, it is impossible to design a heuristic algorithm for this problem based on fixed and simple rules, since rule-based heuristics are unable to adapt to the changes of the traffic matrix and network dynamics. In this paper, we propose CFR-RL (Critical Flow Rerouting-Reinforcement Learning), a Reinforcement Learning-based scheme that learns a policy to select critical flows for each given traffic matrix automatically. CFR-RL then reroutes these selected critical flows to balance link utilization of the network by formulating and solving a simple Linear Programming (LP) problem. Extensive evaluations show that CFR-RL achieves near-optimal performance by rerouting only 10%-21.3% of total traffic.

Since, current widely available network protocols/ systems are mainly throughput-oriented designs, meeting stringent delay requirements of new applications such as virtual reality and vehicle-to-vehicle communications on cellular network requires new network protocol/system designs. C2TCP is an effort toward that new design direction. C2TCP is inspired by in-network active queue management designs such as RED and CoDel and motivated by lack of a flexible end-to-end approach which can adapt itself to different applications' QoS requirements without modifying any network devices. It copes with unique challenges in cellular networks for achieving ultra-low latency (including highly variable channels, deep per-user buffers, self-inflicted queuing delays, and radio uplink/downlink scheduling delays) and intends to satisfy stringent delay requirements of different applications while maximizing the throughput. C2TCP works on top of classic throughput-oriented TCP and accommodates various target delays without requiring any channel prediction, network state profiling, or complicated rate adjustment mechanisms. We have evaluated C2TCP in both real-world environment and extensive trace-based emulations and compared its performance with different TCP variants and state-of-the-art schemes including PCC-Vivace, Google's BBR, Verus, Sprout, TCP Westwood, and Cubic. Results show that C2TCP outperforms all these schemes and achieves lower average delay, jitter, and 95th percentile delay for packets.

Multiple distributed controllers have been used in software-defined networks (SDNs) to improve scalability and reliability, where each controller manages one static partition of the network. In this paper, we show that dynamic mapping between switches and controllers can improve efficiency in managing traffic load variations. In particular, we propose balanced controller (BalCon) and BalConPlus, two SDN switch migration schemes to achieve load balance among SDN controllers with small migration cost. BalCon is suitable for the scenarios where the network does not require a serial processing of switch requests. For other scenarios, BalConPlus is more suitable, as it is immune to the switch migration blackout and does not cause any service disruption. Simulations demonstrate that BalCon and BalConPlus significantly reduce the load imbalance among SDN controllers by migrating only a small number of switches with low computation overhead. We also build a prototype testbed based on the open-source SDN framework RYU to verify the practicality and effectiveness of BalCon and BalConPlus. Experiment confirms the results of the simulations. It also shows that BalConPlus is immune to switch migration blackout, an adverse effect in the baseline BalCon.

Many applications in public clouds require a high fan-in, many-to-one type of data communication (known as TCP incast) in modern Data Center Networks (DCNs). Such communication could cause severe incast congestion in switches and result in TCP throughput collapse, substantially degrading the application performance. The root cause of throughput collapse is the Retransmission Timeouts (RTO) due to packet losses in congested switches. Tenants in public clouds can opt to use a variety of TCP versions. However, the existing solutions rely on modifications of TCP protocols and specific techniques from switches, and thus these existing solutions are not always feasible for public clouds. In this paper, we are inspired by the emerging virtualization and network softwarization technologies to develop a novel scheme called Retransmission timeout Avoidance by Packet Intelligent Discarding (RAPID) using software switches. RAPID considers the number of packets of each incast flow, buffered in the switch to selectively discard some packets, and ensures that the Fast Retransmission/Fast Recovery rather than RTO is invoked at the sender(s) in response to packet loss. Thus, the long idle period of a timeout and the throughput drop are avoided. We prove that, given a predetermined minimum switch buffer space, dedicated to the incast application, RAPID can prevent RTO in all the incast senders. We also present a low-complexity heuristic version of RAPID named RAPID-ED, which combines the principles of RAPID and early detection and is extremely easy to implement on today's software switches. We evaluate the two proposed schemes in a data center network testbed built on NS-3 simulator. The simulation results confirm the theoretical expectation, and show that the RAPID and RAPID-ED perform very well to prevent RTO of TCP incast flows and hence the throughput collapse. Compared with other incast solutions, RAPID and RAPID-ED do not modify TCP protocols and therefore are more suitable in public clouds.

Advances in software-defined networking (SDN) enable a wave of innovation in a wide selection of networks ranging from data center networks to WAN. While existing standard bodies for mobile networks define stringent requirements, they too are embracing the flexibility of SDN in defining the specifications of the next generation of mobile networks. Mobile edge computing (MEC), in particular, is an emerging architecture to bring virtualized network functions and programmable network devices closer to the user. For instance, delay-sensitive or bandwidth-hungry computing resources are moved to the edge of the radio access network (RAN) to provide low latency computation and/or content for users while alleviating the backhaul pressure for network operators. In this paper, we propose an edge gateway (EGW) in the MEC that enables offloading of computation and storage resources to the edge of mobile networks. The EGW is backward compatible with components and protocols of LTE networks and does not require any modification in the user equipment, LTE software, or offloaded resources. We have designed and implemented the EGW using P4 language and verified its operation on a small testbed using a low-end P4 target and a reference LTE protocol stack.

The fifth generation (5G) mobile communication network aims at providing high-rate, low-latency services. When a user subscribes a chain of service functions (a.k.a. service chain) from the telecom providers, a Service Level Agreement (SLA) is specified according to his requirement. Deploying service chains optimally has always been a big issue. Several previous works have presented various strategies of service-chain deployment for optimizing either latency or computational resources; however, over-optimization of latency or computational resource is not necessarily equivalent to improvement on quality of experience. Therefore, in this paper, we formally formulate this problem of optimizing quality of experience with the queuing theory and mixed-integer linear programming. In addition, we propose an efficient algorithm named “QoE-driven Service-Chain Deployment with Latency Prediction” for deploying a service chain for a user in practice. According to the experiments, our algorithm reduces > 99% rejections and > 99% waiting time, notably elevating the quality of experience for users.

Vehicular Cloud and autonomous vehicles require a scalable and reliable mobile communication network. LTE and Dedicated Short Range Communication (DSRC) have been trying to fit for such role, yet neither can satisfy all requirement due to inherent architectural limitations. Fortunately the fifth generation mobile network, 5G and Mobile Edge Cloud/Computing (MEC) is around the corner, targeting ultra low packet delay, high reliability, and Gigabit level wireless bandwidth. This paper introduces a unique vehicular MEC architecture where instead of simply off-loading application service to the edge servers on MEC, vehicular communication packets are routed through the MEC network. We discuss in detail how it accommodates vehicle to vehicle (V2V) and vehicle to infrastructure (V2I) communication with high scalability and guaranteed low packet delay. We also provide an in depth analysis of the pros and cons of our MEC vehicle network design, and address the mobility management issue on edge cloud. Applying distributed mobility management (DMM) operations we are able to make edge cloud IP handoff seamless and transparent. Proof of concept simulations are conducted using NS3.

Enforcing network policies is critical for service deployments over software-defined networks (SDN). Most existing studies suggest proactively compiling policies into flow entries in the data plane and updating the installed entries when necessary. With a growing amount of applications, taking a proactive approach may overflow underlying switch memory. Meanwhile, certain policies can be frequently updated. Such updates may propagate across configurations in the network, leading to a long time for correctness validation. To improve both the scalability and the flexibility of SDN policy enforcement, we advocate reactively deploying network policies in the data plane. To this end, we propose a network-wide policy enforcement framework named BigMaC. BigMaC advertises a neat policy model for network managers to specify various network policies as rules. It then caches the rules as flow entries in the switches reactively on demand. One major challenge for the BigMaC design is to guarantee the consistency of defined policies and cached entries in the network. To maintain consistency with efficient table usage and simple updates, we group rules into buckets and perform rule caching in the unit of buckets. With trace-driven simulations, we verify that BigMaC can significantly save table space and reduce update complexity compared to prior proposals.

Scalability and reliability are among the main concerns in large-scale Software Defined Networking (SDN) application scenarios. A common approach is to use multiple distributed controllers, each managing one static partition of the network. In this paper, we show that dynamic mapping can improve efficiency in managing traffic load variations. We then propose BalCon (Balanced Controller): an algorithmic solution designed to tackle and reduce the load imbalance among SDN controllers through proper SDN switch migrations. Simulations demonstrate that BalCon is lightweight from the computational point of view and reduces the load imbalance among SDN controllers (expressed as variance) by 40% by migrating only a small number of switches. We also built a realistic prototype of SDN controller, BalConController, based on the open-source SDN framework RYU.

Emerging commercial live content broadcasting platforms are facing great challenges to accommodate large scale dynamic viewer populations. Existing solutions constantly suffer from balancing the cost of deploying at the edge close to the viewers and the quality of content delivery. We propose LiveJack, a novel network service to allow CDN servers to seamlessly leverage ISP edge cloud resources. LiveJack can elastically scale the serving capacity of CDN servers by integrating Virtual Media Functions (VMF) in the edge cloud to accommodate flash crowds for very popular contents. LiveJack introduces minor application layer changes for streaming service providers and is completely transparent to end users. We have prototyped LiveJack in both LAN and WAN environments. Evaluations demonstrate that LiveJack can increase CDN server capacity by more than six times, and can effectively accommodate highly dynamic workloads with an improved service quality.

Power-efficient Data Center Networks (DCNs) have been proposed to save power of DCNs using OpenFlow. In these DCNs, the OpenFlow controller adaptively turns on and off links and OpenFlow switches to form a minimum-power subnet that satisfies traffic demand. As the subnet changes, flows are scheduled dynamically to routes composed of active switches and links. However, existing flow scheduling schemes could cause undesired results: (1) power inefficiency: due to unbalanced traffic allocation on active routes, extra switches and links may be activated to cater to bursty traffic surges on congested routes, and (2) Quality of Service (QoS) fluctuation: because of the limited flow entry processing ability, switches cannot timely install/delete/update flow entries to properly schedule flows. In this paper, we propose AggreFlow, a dynamic flow scheduling scheme that achieves power efficiency in DCNs and improved QoS using two techniques: Flow-set Routing and Lazy Rerouting. Flow-set Routing achieves load balancing and reduces the number of entry installment on switches by routing flows in a coarse-grained flow-set fashion. Lazy Rerouting maintains load balancing and spreads rerouting operations over a relatively long period of time, reducing the burstiness of entry installment/deletion/update on switches. We built a NS3 based fat-tree network simulation platform to evaluate AggreFlow's performance. The simulation results show AggreFlow reduces power consumption by about 18%, achieves load balancing and improved QoS (i.e., low packet loss rate and reducing the number of processing entries for flow scheduling by 98%), compared with baseline schemes.

Packet classification is one of the major challenges today in designing high-speed routers and firewalls, as it involves sophisticated multi-dimensional searching. Ternary content addressable memory (TCAM) has been widely used to implement packet classification, thanks to its parallel search capability and constant processing speed. However, TCAMs have limitations of high cost and high power consumption, which ignite the desire to reduce TCAM usage. Recently, many works have been presented on this subject due to two opportunities. One is the well-known range expansion problem for packet classifiers to be stored in TCAM entries. The other is that there often exists redundancy among rules. In this paper, we propose a novel technique called Block Permutation (BP) to compress the packet classification rules stored in TCAMs. Unlike previous schemes that compress classifiers by converting the original classifiers to semantically equivalent classifiers, the BP technique innovatively finds semantically nonequivalent classifiers to achieve compression by performing block-based permutations on the rules represented in Boolean Space. We have developed an efficient heuristic approach to find permutations for compression and have designed its hardware implementation by using a field-programmable gate array (FPGA) to preprocess incoming packets. Our experiments with ClassBench classifiers and Internet Service Provider (ISP) real-life classifiers show that the proposed BP technique can significantly reduce 31.88% TCAM entries on average, in addition to the reduction contributed by other state-of-the-art schemes.

This paper proposes a three-stage buffered Clos-network switch (TSBCS) architecture along with a novel batch scheduling (BS) mechanism. We found that TSBCS/BS can be mapped to a “fat” combined input-crosspoint queued (CICQ) switch. Consequently, the well-studied CICQ scheduling algorithms can be directly applied in TSBCS. Moreover, BS drastically reduces the time complexity of TSBCS scheduling when compared with ordinary CICQ switches of the same number of switch ports, which enables us to build a larger-capacity switch with reasonable scheduling complexity. We further show that TSBCS/BS can achieve 100 percent throughput under any admissible traffic if a stable CICQ scheduling algorithm is used. Direct cell forwarding schemes are proposed to overcome the performance drawback of BS under light traffic loads. With extensive simulations, we show that the performance of TSBCS/BS is comparable to that of output-queued switches and the latter are usually considered as theoretical optimal.

As service providers have started deploying SDN in their networks, traditional IP routers are gradually upgraded to SDN enabled switches. In other words, the network will have traditional IP routers and SDN switches coexisting, and it is called a hybrid SDN network. With such a network, we take advantage of SDN and propose an approach to guarantee traffic reachability in the presence of any single link failure. By redirecting traffic on the failed link to SDN switches through pre-configured IP tunnels, the proposed approach is able to react to the failures very fast. With the help of coordination among SDN switches, we are also able to explore multiple backup paths for the failure recovery. This allows the proposed approach to avoid potential congestion in the post-recovery network by choosing proper backup paths. Simulation results show that our proposed scheme requires only a very few number of SDN switches in the hybrid SDN network to achieve fast recovery and guarantee 100% reachability from any single link failure. It also shows that the proposed approach is able to better load-balance the post-recovery network comparing to IP Fast Reroute and shortest path re-calculation.

Intradomain traffic engineering (TE) has become an indispensable tool for Internet service providers (ISPs) to optimize network performance and utilize network resources efficiently. Various explicit routing TE methods were recently proposed and have been able to achieve high network performance. However, explicit routing has high complexity and requires large ternary content addressable memories (TCAMs) in the routers. Moreover, it is costly to deploy explicit routing in IP networks. In this paper, we present an approach, called generalized destination-based multipath routing (GDMR), to achieve the same high performance as explicit routing. The main contribution of this paper is that we prove that an arbitrary explicit routing can be converted to a loop-free destination-based routing without any performance penalty for a given traffic matrix. We present a systematic approach including a heuristic algorithm to realize GDMR. Extensive evaluation demonstrates the effectiveness and robustness of GDMR.

Classical traffic engineering (TE) methods calculate the optimal routing based on a single traffic matrix. However, they are unable to handle unexpected traffic changes. Thus, it is of interest to find a good routing configuration to accommodate multiple possible traffic scenarios. There are two major approaches to achieve load balancing for multiple traffic matrices: destination-based routing and explicit routing. It has been shown that explicit routing performs better than destination-based routing for multiple traffic matrices. However, explicit routing has high complexity and requires large Ternary Content Addressable Memory (TCAM) in the routers. Thus, it is power hungry and unscalable. This paper presents an approach called hybrid routing to achieve load balancing for multiple traffic matrices with low complexity and good scalability. Our basic idea is to complement destination-based routing with a small number of explicit routing forwarding entries to take advantage of both two routing approaches. Hybrid routing greatly reduces the number of forwarding entries compared with pure explicit routing. This has great value for practice in that the scheme requires very small TCAM to implement. Hybrid routing is very suitable for implementation using SDN. A heuristic algorithm is developed to obtain the near-optimal hybrid routing configuration. Extensive evaluation demonstrates the effectiveness of hybrid routing. The results show that hybrid routing achieves near-optimal load balancing compared with pure explicit routing. In particular, hybrid routing saves at least 84.6% TCAM resources in all practical networks used in our evaluation.

Classical TE methods calculate the optimal routing based on a known traffic matrix. However, they are unable to handle unexpected traffic changes. Thus, various methods were proposed in recent years, such as online dynamic TE and robust static routing TE. However, online dynamic TE requires additional overhead on routers for information dissemination and suffers from the transient disruptions during routing protocol convergence, while using one robust static routing to accommodate a wide range of traffic scenarios is unable to ensure near optimality of performance for each individual traffic scenario. This paper presents an approach called dynamic hybrid routing (DHR) to achieve load balancing for a wide range of traffic scenarios. Our basic idea is to configure several routing policies in advance and then dynamically rebalance traffic by applying different preconfigured routing policy to react to traffic fluctuations. Each routing policy composes of a common basic destination-based routing and a few complementary explicit routing forwarding entries for a small set of selected ingress/egress node pairs. We design a method to find the near-optimal dynamic hybrid routing configuration. Extensive evaluation demonstrates the effectiveness of DHR. We show that DHR achieves nearoptimal load balancing and thus obtain about at least 96% throughput compared to optimal routing for each individual traffic scenario with very low overhead.

The thirteen articles in this special section explore the technology of deep packet inspection (DPI). DPI examines the content in packet payloads to search for signatures of network applications, signs of malicious activities, and leaks of sensitive information, rather than just examine packet headers for information such as IP addresses and port numbers. The inspection provides network devices with rich information of application protocol messages in packet payloads, and enables them to make intelligent decisions in packet processing based on the information. The papers are organized into the following four sections: (1) Scalable Algorithms and Architectures for DPI, (2) Network Traffic Analysis with DPI, (3) Network Protocol Identification with DPI, and (4) Network Security Analysis with DPI.

Many applications (e.g., cluster based storage and MapReduce) in modern data centers require a high fan-in, many-to-one type of data communication (known as TCP incast), which could cause severe incast congestion in switches and result in TCP goodput collapse, substantially degrading the application performance. The root cause of such a collapse is the long idle period of the Retransmission Timeout (RTO) that is triggered at one or more senders by packet losses in congested switches. In this paper we develop a packet labelling scheme PLATO, which improves the loss detection capabilities of NewReno using an innovative packet labelling system. Packets carrying this special label are preferentially enqueued, at the switch. This allows TCP to detect packet loss using three duplicate acknowledgements, instead of the time expensive RTO; thus avoiding the goodput collapse. PLATO makes minor modifications to NewReno and does not alter its congestion control mechanism. The implementation and simulations have been done in Network Simulator 3 (NS3). PLATO's performance is significantly better than NewReno as well as state-of-art incast solutions Incast Control TCP (ICTCP) and Data Center TCP (DCTCP). We also show that TCP PLATO can be implemented using commodity switches with Weighted Random Early Detection (WRED) function.

The articles i nthis special issue focus on switching and routing applications for scalable and energy efficient networking.

Deterministic finite automatons (DFAs) and nondeterministic finite automatons (NFAs) are two typical automatons used in the network intrusion detection system. Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. In this paper, we propose a new automaton representation of regular expressions, called tunable finite automaton (TFA), to deal with the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. Simulation results based on regular expression rule sets from Snort and Bro show that, with only two concurrent active states, a TFA can achieve significant reductions in the number of states and memory usage, e.g., a 98% reduction in the number of states and a 95% reduction in memory space.

On-chip photonic waveguides have been proposed as a feasible replacement for the long interconnects that cause speed and power bottlenecks. Along with recent advancements in nanophotonic technologies, we believe that combining on-chip waveguides with high-radix Network on Chip (NoC) topologies is a promising way to improve NoC performance. In this paper, we propose the BufferLess phOtonic ClOs Network (BLOCON) to exploit silicon photonics. We propose a scheduling algorithm named Sustained and Informed Dual Round-Robin Matching (SIDRRM) to solve the output contention problem, a path allocation scheme named Distributed and Informed Path Allocation (DIPA) to solve the Clos network routing problem, and a methodology to achieve an optimal off-chip laser-power budget. In the simulation results, we show that with SIDRRM and DIPA, BLOCON improves the delay and on-chip power performance of the compared electrical and photonic NoC architectures over synthetic traffic patterns and SPLASH-2 traces.

The emergence of new network applications, such as the network intrusion detection system and packet-level accounting, requires packet classification to report all matched rules instead of only the best matched rule. Although several schemes have been proposed recently to address the multimatch packet classification problem, most of them require either huge memory or expensive ternary content addressable memory (TCAM) to store the intermediate data structure, or they suffer from steep performance degradation under certain types of classifiers. In this paper, we decompose the operation of multimatch packet classification from the complicated multidimensional search to several single-dimensional searches, and present an asynchronous pipeline architecture based on a signature tree structure to combine the intermediate results returned from single-dimensional searches. By spreading edges of the signature tree across multiple hash tables at different stages, the pipeline can achieve a high throughput via the interstage parallel access to hash tables. To exploit further intrastage parallelism, two edge-grouping algorithms are designed to evenly divide the edges associated with each stage into multiple work-conserving hash tables. To avoid collisions involved in hash table lookup, a hybrid perfect hash table construction scheme is proposed. Extensive simulation using realistic classifiers and traffic traces shows that the proposed pipeline architecture outperforms HyperCuts and B2PC schemes in classification speed by at least one order of magnitude, while having a similar storage requirement. Particularly, with different types of classifiers of 4K rules, the proposed pipeline architecture is able to achieve a throughput between 26.8 and 93.1 Gb/s using perfect hash tables.

Enterprise data centers (EDCs) are critical infrastructure to large enterprises, government agencies, research institutions, etc. They are used to support a variety of off-the-shelf and customized services. EDCs are different from cloud data centers (CDCs) in two major aspects. Firstly, an EDC is usually built over time and consists of old and new equipment. Secondly, the type of services and applications in EDCs are quite different from those in CDCs. Therefore, we expect that the traffic characteristics in EDCs would also be different from those in CDCs. While most existing data center measurements were from CDCs, we performed extensive traffic measurement and analysis in an EDC that provided multiple services to over a million users. We present the data center architecture, measurement methodology, measurement results, and analysis. The results include traffic matrix, traffic distribution, flow characteristics, and TCP characteristics. Our research reveals that the traffic characteristics in the EDC are indeed quite different from the reported results in CDCs. For example, the traffic matrix tends to be sparse rather than all-to-all. Based on the analysis we provide a few guidelines for EDC design, optimization, and anomaly detection. As the first most extensive study on EDC traffic, our work provides valuable information to future EDC design and implementation, and also helps researchers develop insights into the differences and similarities between EDCs and CDCs.

In this paper, we extend our previous work of StablePlus, a stable scheduling algorithm for single-stage packet switches, to bufferless three-stage Clos-network switches. StablePlus is based on an existing stable distributed scheduling algorithm, called DISQUO. We further improve the switching performance by incorporating a heuristic scheduling algorithm after the DISQUO scheduling. In a three-stage Clos-network switch, DISQUO is first used to solve the output contention which generates a stable matching between the input and output ports, then Karol's algorithm is used to find the feasible internal paths for the matched input and output pairs. However, the latter requires multiple mini-cycles to complete the path-finding task. Worse is that the number of mini-cycles increases as the switch size does, limiting the Clos-network to a small implementable size. By replacing the Hamiltonian Walk in DISQUO with time-division multiplexing (TDM) scheme, we show that the number of required mini-cycles for Karol's algorithm can be reduced to only two, independent of the switch size. Moreover, with the help of a parallel hardware approach, we can implement packet scheduling in O(1) time complexity. To support high data rates, e.g., 100 Gbps, we can also make the scheduling work on a frame basis. We prove that StablePlus can achieve 100% throughput under any admissible traffic, and by simulations we show that it also has good delay performance.

An important challenge of running large-scale cloud services in a geo-distributed cloud system is to minimize the overall operating cost. The operating cost of such a system includes two major components: electricity cost and wide-area-network (WAN) communication cost. While the WAN communication cost is minimized when all virtual machines (VMs) are placed in one datacenter, the high workload at one location requires extra power for cooling facility and results in worse power usage effectiveness (PUE). In this paper, we develop a model to capture the intrinsic trade-off between electricity and WAN communication costs, and formulate the optimal VM placement problem, which is NP-hard due to its binary and quadratic nature. While exhaustive search is not feasible for large-scale scenarios, heuristics which only minimize one of the two cost terms yield less optimized results. We propose a cost-aware two-phase metaheuristic algorithm, Cut-and-Search, that approximates the best trade-off point between the two cost terms. We evaluate Cut-and-Search by simulating it over multiple cloud service patterns. The results show that the operating cost has great potential of improvement via optimal VM placement. Cut-and-Search achieves a highly optimized trade-off point within reasonable computation time, and outperforms random placement by 50%, and the partial-optimizing heuristics by 10-20%.

A single-stage buck-type AC-DC converter is proposed for medical implants to achieve high efficiency. The proposed structure combines two traditional stages of the three-stage power path for medical implants and eliminates a MOSFET and a filter capacitor to improve the efficiency. The proposed circuit converts 40 Vppcoil voltage into a DC output voltage of 4.2 V. The stability analysis of the circuit is also presented. Load currents between 1 mA to 100 mA are supported. The efficiency of the proposed circuit is 81.9%.

Saving power in datacenter networks has become a pressing issue. While in operation, ElasticTree and CARPO can save power consumed by a fat-tree network by using sleep mode where some components such as ports and switches are turned off when traffic demand in the network is relatively moderate. In this paper, we propose a new approach by exploring the design stage of a datacenter network and focus on how to choose the right switch size that can potentially save the most power during the expected operation of the network. We also consider speed scaling where the power of a switch can be varied by adjusting its processing rate according to its traffic demand. We use analysis and simulation to investigate the power-saving performance of different switch sizes, power-saving modes and traffic demand patterns. Our findings with sleep mode reveal that deploying a large number of small switches is more power-efficient than a small number of large switches when the traffic demand is relatively moderate or when servers exchanging traffic are in close proximity. With speed scaling, the reverse is generally true.

One of the challenging problems for multi-stage buffered switching is the performance degradation due to the saturation tree congestion inside the switch when traffic destined for some output ports exceeds their link capacity (i.e., hotspots) and blocks other traffic destined for non-overloaded output ports. In previous work [18], we have proposed HOPE, an effective congestion control scheme, in the 3-stage Clos Network on Chip (NOC). HOPE proactively regulates traffic destined for each output by estimating the number of their backlogged packets in the network and applying a simple stop-and-go mechanism to prevent hotspot traffic from jamming the internal links between the stages. The effectiveness of HOPE in NOC has motivated us to apply it in the multistage buffered switches. Different from an NOC, where Switch Modules (SMs) are all on the single chip, the SMs in a multi-stage buffered switch are separated from each other for a distance up to 100 m. This significantly increases the hardware complexity of HOPE. In this paper, we address the implementation challenges when applying HOPE in the 3-stage Clos network switch. In particular, we propose a scalable traffic measurement mechanism to approximate the backlogged traffic for each output port by taking advantage of the property of Clos network that traffic is evenly distributed among central SMs. We also design an efficient messaging system to notify input sources upon congestion status updates. Simulation results with different traffic patterns show that HOPE can isolate hotspot traffic from non-hotspot traffic, achieve max-min fairness among different traffic types, and provide low latency for non-hotspot traffic and high throughput for hotspot traffic.

In this paper, we propose a simple module-level matching scheme for memory-space-memory Clos-network switches to avoid complex path-allocation algorithms in bufferless Clos networks, as well as cell out-of-order and saturation-tree problems in buffered Clos networks. We show that the module-level matching scheme can achieve 100% throughput.We propose static and dynamic dispatching cell schemes in addition to the module-level matching to improve the delay performance. The static cell dispatching scheme requires no additional scheduling; while the dynamic cell dispatching scheme is more adaptive to the traffic than the static one, thus can achieve better delay performance under non-uniform traffic loads. However, the wiring complexity of the scheduler for dynamic cell dispatching is high. Thus, the grouped dynamic cell dispatching scheme is proposed as a trade-off between the complexity and performance. In practice, embedded memory size is restricted, thus the queue length limitation in each switch module is also considered in this paper. We propose an efficient scheme to prevent queues to overflow in this situation which makes our work more practical.

Security is critical to data centers, especially multi-tenant data centers that host a variety of applications in a single facility. Conventional schemes place security devices (middleboxes) at a few choke points (e.g., core routers) and rely on routing policy to guarantee middlebox traversal. Coupling routing and security services together complicates operation and troubleshooting since routing and security are operated by different teams. When a data center scales, the security system needs upgrade accordingly. However, the current approaches are not flexible and incur high cost. Observing that rich computing resources are already available in data centers, we are interested in using a large number of software middleboxes to achieve scalability and cost efficiency. We present Hybrid Security Architecture (HSA), a design to decouple security services from routing and to allow the integration of hardware and software middleboxes in a complementary way. HSA is more cost-effective and flexible compared to the conventional schemes that solely use hardware middleboxes. It allows topology and routing changes with minimal impact to security services, and vice versa. In particular, HSA does not require modification to switches and routers. This paper explains the framework of HSA, describes the key techniques, presents a testbed to validate the design, and discusses future research directions.

Equal-Cost Multipath (ECMP) routing has been widely adopted to perform load balancing. With ECMP, a router can maintain multiple next hops for a destination IP prefix. The most common method used by such routers is to split traffic with per-flow basis evenly among those next hops. This approach, although simple, cannot achieve optimal load balancing. In this paper we study the optimal configuration of weighted ECMP, where traffic splitting among the available paths is based on a set of pre-determined ratios. The contribution of this paper is two-fold. First, we develop a model to obtain the split ratios such that the overall network end-to-end delay is optimized. This is important because better delay performance is a result of better bandwidth allocation and has a direct impact on application, while most existing work tries to minimize the traffic load on the most utilized link. Second, we prove that the problem can be first solved by using a simple flow-based routing model and then converting the results to apply to IP networks, where destination-based forwarding is used. We present a heuristic algorithm to find the near-optimal weight configurations and demonstrate the effectiveness of the algorithm using computer simulations.

Packet classification is one of the major challenges in designing high-speed routers and firewalls as it involves sophisticated multi-dimensional searching. Ternary Content Addressable Memory (TCAM) has been widely used to implement packet classification thanks to its parallel search capability and constant processing speed. However, TCAM-based packet classification has the well-known range expansion problem, resulting in a huge waste of TCAM entries. In this paper, we propose a novel technique called Block Permutation (BP) to compress the packet classification rules stored in TCAMs. The compression is achieved by performing block-based permutations on the rules represented in Boolean Space. We develop an efficient heuristic approach to find the permutations for compression and design its hardware implementation. Experiments on ClassBench classifiers and ISP classifiers show that the proposed BP technique can reduce TCAM entries by 53.99% on average.

Incast applications have grown in popularity with the advancement of data center technology. It is found that the TCP incast may suffer from the throughput collapse problem, as a consequence of TCP retransmission timeouts when the bottleneck buffer is overwhelmed and causes the packet losses. This is critical to the Quality of Service of cloud computing applications. While some previous literature has proposed solutions, we still see the problem not completely solved. In this paper, we investigate the three root causes for the poor performance of TCP incast flows and propose three solutions, one for each at the beginning, the middle and the end of a TCP connection. The three solutions are: admission control to TCP flows so that the flow population would not exceed the network's capacity; retransmission based on timestamp to detect loss of retransmitted packets; and reiterated FIN packets to keep the TCP connection active until the the termination of a session is acknowledged. The orchestration of these solutions prevents the throughput collapse. The main idea of these solutions is to ensure all the on-going TCP incast flows can maintain the self-clocking, thus eliminates the need to resort to retransmission timeout for recovery. We evaluate these solutions and find them work well in preventing the retransmission timeout of TCP incast flows, hence also preventing the throughput collapse.

Multipath Switching systems (MPS) are intensely used in state-of-the-art core routers to provide terabit or even petabit switching capacity. One of the most intractable issues in designing MPS is how to load balance traffic across its multiple paths while not disturbing the intraflow packet orders. Previous packet-based solutions either suffer from delay penalties or lead to O(N^2 ) hardware complexity, hence do not scale. Flow-based hashing algorithms also perform badly due to the heavy-tailed flow-size distribution. In this paper, we develop a novel scheme, namely, Flow Slice (FS) that cuts off each flow into flow slices at every intraflow interval larger than a slicing threshold and balances the load on a finer granularity. Based on the studies of tens of real Internet traces, we show that setting a slicing threshold of 1-4 {\rm ms}, the FS scheme achieves comparative load-balancing performance to the optimal one. It also limits the probability of out-of-order packets to a negligible level (10^{ - 6}) on three popular MPSes at the cost of little hardware complexity and an internal speedup up to two. These results are proven by theoretical analyses and also validated through trace-driven prototype simulations.

Regular expressions (RegExes) are widely used, yet their inherent complexity often limits the total number of RegExes that can be detected using a single chip for a reasonable throughput. This limit on the number of RegExes impairs the scalability of today's RegEx detection systems. The scalability of existing schemes is generally limited by the traditional detection paradigm based on per-character-state processing and state transition detection. The main focus of existing schemes is on optimizing the number of states and the required transitions, but not on optimizing the suboptimal character-based detection method. Furthermore, the potential benefits of allowing out-of-sequence detection, instead of detecting components of a RegEx in the order of appearance, have not been explored. Lastly, the existing schemes do not provide ways to adapt to the evolving RegExes. In this paper, we propose Lookahead Finite Automata (LaFA) to perform scalable RegEx detection. LaFA requires less memory due to these three contributions: 1) providing specialized and optimized detection modules to increase resource utilization; 2) systematically reordering the RegEx detection sequence to reduce the number of concurrent operations; 3) sharing states among automata for different RegExes to reduce resource requirements. Here, we demonstrate that LaFA requires an order of magnitude less memory compared to today's state-of-the-art RegEx detection systems. Using LaFA, a single-commodity field programmable gate array (FPGA) chip can accommodate up to 25 000 (25 k) RegExes. Based on the throughput of our LaFA prototype on FPGA, we estimate that a 34-Gb/s throughput can be achieved.

It is becoming apparent that the next-generation IP route lookup architecture needs to achieve speeds of 100 Gb/s and beyond while supporting IPv4 and IPv6 with fast real-time updates to accommodate ever-growing routing tables. Some of the proposed multibit-trie-based schemes, such as TreeBitmap, have been used in today's high-end routers. However, their large data structures often require multiple external memory accesses for each route lookup. A pipelining technique is widely used to achieve high-speed lookup with the cost of using many external memory chips. Pipelining also often leads to poor memory load-balancing. In this paper, we propose a new IP route lookup architecture called FlashTrie that overcomes the shortcomings of the multibit-trie-based approaches. We use a hash-based membership query to limit off-chip memory accesses per lookup and to balance memory utilization among the memory modules. By compacting the data structure size, the lookup depth of each level can be increased. We also develop a new data structure called Prefix-Compressed Trie that reduces the size of a bitmap by more than 80%. Our simulation and implementation results show that FlashTrie can achieve 80-Gb/s worst-case throughput while simultaneously supporting 2 M prefixes for IPv4 and 318 k prefixes for IPv6 with one lookup engine and two Double-Data-Rate (DDR3) SDRAM chips. When implementing five lookup engines on a state-of-the-art field programmable gate array (FPGA) chip and using 10 DDR3 memory chips, we expect FlashTrie to achieve 1-Gpps (packet per second) throughput, equivalent to 400 Gb/s for IPv4 and 600 Gb/s for IPv6. FlashTrie also supports incremental real-time updates.

Aho-Corasick (AC) automaton is widely used for multi-string matching in today's Network Intrusion Detection System (NIDS). With fast-growing rule sets, implementing AC automaton with a small memory without sacrificing its performance has remained challenging in NIDS design. In this paper, we propose a multi-dimensional progressive perfect hashing algorithm named P2-Hashing, which allows transitions of an AC automaton to be placed in a compact hash table without any collision. P2-Hashing is based on the observation that a hash key of each transition consists of two dimensions, namely a source state ID and an input character. When placing a transition in a hash table and causing a collision, we can change the value of a dimension of the hash key to rehash the transition to a new location of the hash table. For a given AC automaton, P2-Hashing first divides all the transitions into many small sets based on the two-dimensional values of the hash keys, and then places the sets of transitions progressively into the hash table until all are placed. Hash collisions that occurred during the insertion of a transition will only affect the transitions in the same set. The proposed P2-Hashing has many unique properties, including fast hash index generation and zero memory overhead, which are very suitable for the AC automaton operation. The feasibility and performance of P2-Hashing are investigated through simulations on the full Snort (6.4k rules) and Clam AV (54k rules) rule sets, each of which is first converted to a single AC automaton. Simulation results show that P2-Hashing can successfully construct the perfect hash table even when the load factor of the hash table is as high as 0.91.

The recent literature on data center networks often propose the use of centralized control server to manage resources or for coordination. These controllers are always a single omniscient device. While we see no problems in practice yet as it works for small scale networks, there is a scalability concern. This paper proposes the idea of devolved controllers, namely, a number of controllers that each with only limited information about the network, but they together can replace a omniscient controller. Thus it permits the controllers' workload to scale up. We use dynamic flow reroute as an example, to study how we can build a network with devolved controllers, how to configure them, how they operate, and especially how they provide resilience. We show that these devolved controllers can remove the scalability concern and provide redundancy to each other; externally, they are as easy to use as a single omniscient controller. We describe how these controllers are prepared and used to prove that devolved controllers is feasible idea, and provide a precursor to a new direction on the control aspect of networking.

This paper proposes a practical stable packet scheduling algorithm for input-queued switches, called StablePlus, which combines a stable matching with a heuristic matching. It not only achieves 100% throughput under any admissible traffic but also has good delay performance. StablePlus can be implemented with today's technology for high line rates, e.g., 100Gbps, and a relatively large input-queued switch, e.g., a few hundred ports.

Hotspot congestion control is one of the most challenging issues when designing a high-throughput low-latency network on the chip (NOC). When a destination node is overloaded, it starts pushing back the packets destined for it, which in turns blocks the packets destined for other nodes. How to detect the occurrence(s) of hotspot and notify all source nodes to regulate their traffic to the hotspot node(s) can be quite complex because of potentially high volume of information to be collected and the non-negligible latency between the detection point of congestion and the source nodes. In this paper, we propose an effective end-to-end flow control scheme, called HOPE (HOtspot PrEvention), to resolve the hotspot congestion problem for the Clos network on the chip (CNOC). Specifically, HOPE regulates the injected traffic rate proactively by estimating the number of packets inside the switch network destined for each destination and applying a simple stop-and-go protocol to prevent hotspot traffic from jamming the internal links of the network. We evaluate HOPE's overall performance and the required hardware. Extensive simulation results based on both static and dynamic hotspot traffic patterns confirm that HOPE can effectively regulate hotspot flows and improve system performance. Our hardware analysis shows that HOPE has very small logic overhead.

On-chip photonic waveguides have been proposed as a feasible replacement for the long interconnects that cause speed and power bottlenecks. Along with recent advancements in nanophotonic technologies, we believe that combining on-chip waveguides with high-radix Network on Chip (NoC) topologies is a promising way to improve NoC performance. In this paper, we propose the BLOCON (BufferLess phOtonic ClOs Network) to exploit silicon photonics. We propose a scheduling algorithm named Sustained and Informed Dual Round-Robin Matching (SIDRRM) to solve the output contention problem, and a path allocation scheme named Distributed and Informed Path Allocation (DIPA) to solve the Clos network routing problem. In the simulation results, we show that with SIDRRM and DIPA, BLOCON improves the delay and power performance of the compared electrical and photonic NoC architectures over synthetic traffic patterns and SPLASH-2 traces.

Many high-radix network-on-chip (NoC) topologies have been proposed to improve network performance with an ever-growing number of processing elements (PEs) on a chip. We believe high-radix Clos network-on-chip (CNoC) is the most promising with its low average hop counts and good load-balancing characteristics. In this paper, we propose: 1) a high-radix router architecture with virtual output queue (VOQ) buffer structure and packet mode dual round-robin matching (PDRRM) scheduling algorithm to achieve high speed and high throughput in CNoC; 2) the design of hierarchical round-robin arbiter for high-radix high-speed NoC routers; and 3) a heuristic floor-planning algorithm to minimize the power consumption caused by the long wires. Experimental results show that the throughput of a 64-node three-stage CNoC under uniform traffic increases from 62% to 78% by replacing the baseline virtual channel routers with PDRRM VOQ routers. We also compared the delay, power, and area performance of the 64-node CNoC with other NoC topologies under various synthetic traffic patterns and SPLASH-2 benchmark traces. The simulation results show that in general CNoC improves the throughput, low-load delay, and energy efficiency over the compared NoC topologies.

Recently, major Internet carriers and vendors successfully tested high-speed backbone networks at 100-Gbps line speed to support rapid growth of the Internet traffic demands. In addition, traffic is getting more concentrated to points such as data centers, and demand for protecting such high-speed networks from attack traffic is increasing. Deep Packet Inspection (DPI) with Regular Expression (RegEx) detection is the de facto defense mechanism agains network intrusions. However, current RegEx detection systems cannot keep up with the upcoming high-speed line rate. The RegExes consist of three types of components, exact strings, character classes (CC), and repetitions. Exact string and repetition matching have been widely studied by RegEx research community for better performance. Yet, although more than 55% of RegExes in Snort signature set contain at least one CC, hardware based solutions that focus on CC detection is limited.

Packet classification is widely used in various network security and operation applications. Two of the main challenges are the increasing number of classification rules, amount of traffic and network line speed. In this poster, we investigate an approximation algorithm for selecting the top-N most frequently matched subset of rules from the original ruleset. Through simulations, we show that our approaches the optimal while runs in seconds, allowing online adaptation to changing traffic patterns.

Failure recovery in IP networks is critical to high-quality service provisioning. In IP over wavelength division multiplexing (WDM) networks, a fiber carries multiple IP logical links. When a fiber fails, all the logical links it carries are disconnected simultaneously. This is called a shared risk link group (SRLG) failure. Recovery from SRLG failures using route recalculation could lead to long service disruption. In this paper, we present a scheme called multi-section shortest path first (MSSPF) that achieves ultra fast recovery from SRLG failures. MSSPF performs all the recovery related calculations in advance. On the detection of an SRLG failure, the affected IP packets are detoured to their destinations through pre-calculated paths to avoid failed links. We prove that MSSPF guarantees 100% recovery from SRLG failures and causes no permanent loops. In particular, the scheme has low complexity and can be implemented in today's networks running link-state routing protocols, e.g., open shortest path first (OSPF). The performance of our scheme is validated with a variety of practical and randomly generated topologies.

It is becoming apparent that the next generation IP route lookup architecture needs to achieve speeds of 100-Gbps and beyond while supporting both IPv4 and IPv6 with fast real-time updates to accommodate ever-growing routing tables. Some of the proposed multibit-trie based schemes, such as Tree Bitmap, have been used in today's high-end routers. However, their large data structure often requires multiple external memory accesses for each route lookup. A pipelining technique is widely used to achieve high-speed lookup with a cost of using many external memory chips. Pipelining also often leads to poor memory load-balancing. In this paper, we propose a new IP route lookup architecture called FlashTrie that overcomes the shortcomings of the multibit-trie based approach. We use a hash-based membership query to limit off-chip memory accesses per lookup to one and to balance memory utilization among the memory modules. We also develop a new data structure called Prefix-Compressed Trie that reduces the size of a bitmap by more than 80%. Our simulation and implementation results show that FlashTrie can achieve 160-Gbps worst-case throughput while simultaneously supporting 2-M prefixes for IPv4 and 279-k prefixes for IPv6 using one FPGA chip and four DDR3 SDRAM chips. FlashTrie also supports incremental real-time updates.

Many high-radix Network-on-Chip (NOC) topologies have been proposed to improve network performance with an ever-growing number of processing elements (PEs) on a chip. We believe Clos Network-on-Chip (CNOC) is the most promising with its low average hop counts and good load-balancing characteristics. In this paper, we propose (1) a high-radix router architecture with Virtual Output Queue (VOQ) buffer structure and Packet Mode Dual Round-Robin Matching (PDRRM) scheduling algorithm to achieve high speed and high throughput in CNOC, (2) a heuristic floor-planning algorithm to minimize the power consumption caused by the long wires. Experimental results show that the throughput of a 64-node 3-stage CNOC under uniform traffic increases from 62% to 78% by replacing the baseline routers with PDRRM VOQ routers. We also compared CNOC with other NOC topologies, and found that using the new design techniques, CNOC has the highest throughput, lowest zero-load latency, and best power efficiency.

Most all-optical switching paradigms assume that different wavelengths are switched independently, which limits scalability. In optical cell switching (OCS), time is divided into time slots of fixed size by time-division multiplexing, and the wavelengths in a time slot are all bundled. Thus, each OCS switch (OCX) has a single switching plane and performs mere time-space switching. In OCS, each OCX requires optical slot synchronizers (OSYNs) at all inputs for the arrival slots to be aligned, so that cells can be simultaneously forwarded. In a recent OCS paradigm -not-aligned OCS-, the OSYNs and the alignment process are no longer required. Cell shifting still takes place inside the OCXs for minimizing the gaps between cells, but it is not necessary to align them to a reference time. Not-aligned OCS has clear advantages over aligned OCS: the total number of fiber delay loops (FDLs) and the hardware cost are reduced, and the number of switching operations is also lower. Moreover, cell arrival time to the switch is not critical, and the network becomes simpler and more flexible. In this paper, we propose a new distributed resource scheduling algorithm for not-aligned OCS networks, which takes connection blocking probability to reasonable values for practical loads.

Crosspoint buffered switches are emerging as the focus of research in high-speed routers. They have simpler scheduling algorithms and achieve better performance than bufferless crossbar switches. Crosspoint buffered switches have a buffer at each crosspoint. A cell is first delivered to a crosspoint buffer, and then transferred to the output port. With a speedup of 2, a crosspoint buffered switch has previously been proved to provide 100% throughput. In this paper, we propose two 100% throughput scheduling algorithms without speedup for crosspoint buffered switches, called SQUISH and SQUID. We prove that both schemes can achieve 100% throughput for any admissible Bernoulli traffic, with the minimum required crosspoint buffer size being as small as a single cell buffer. Both schemes have a low time complexity ofO(logN), whereNis the switch size. Simulation results show a delay performance comparable to output-queued switches. We also present a novel queuing model that models crosspoint buffered switches under uniform traffic.

Although Regular Expressions (RegExes) have been widely used in network security applications, their inherent complexity often limits the total number of RegExes that can be detected using a single chip for a reasonable throughput. This limit on the number of RegExes impairs the scalability of today's RegEx detection systems. The scalability of existing schemes is generally limited by the traditional per character state processing and state transition detection paradigm. The main focus of existing schemes is in optimizing the number of states and the required transitions, but not the suboptimal character-based detection method. Furthermore, the potential benefits of reduced number of operations and states using out-of-sequence detection methods have not been explored. In this paper, we propose Looka-head Finite Automata (LaFA) to perform scalable RegEx detection using very small amount of memory. LaFA's memory requirement is very small due to the following three areas of effort described in this paper: (1) Different parts of a RegEx, namely RegEx components, are detected using different detectors, each of which is specialized and optimized for the detection of a certain RegEx component. (2) We systematically reorder the RegEx component detection sequence, which provides us with new possibilities for memory optimization. (3) Many redundant states in classical finite automata are identified and eliminated in LaFA. Our simulations show that LaFA requires an order of magnitude less memory compared to today's state-of-the-art RegEx detection systems. A single commodity Field Programmable Gate Array (FPGA) chip can accommodate up to twenty-five thousand (25k) RegExes. Based on the throughput of our LaFA prototype on FPGA, we estimated that a 34-Gbps throughput can be achieved.

The emergence of new network applications like network intrusion detection system, packet-level accounting, and load-balancing requires packet classification to report all matched rules, instead of only the best matched rule. Although several schemes have been proposed recently to address the multi-match packet classification problem, most of them require either huge memory or expensive Ternary Content Addressable Memory (TCAM) to store the intermediate data structure, or suffer from steep performance degradation under certain types of classifiers. In this paper, we decompose the operation of multi-match packet classification from the complicated multi-dimensional search to several single-dimensional searches, and present an asynchronous pipeline architecture based on a signature tree structure to combine the intermediate results returned from single-dimensional searches. By spreading edges of the signature tree in multiple hash tables at different stages of the pipeline, the pipeline can achieve a high throughput via the inter-stage parallel access to hash tables. To exploit further intra-stage parallelism, two edge-grouping algorithms are designed to evenly divide the edges associated with each stage into multiple work-conserving hash tables with minimum overhead. Extensive simulation using realistic classifiers and traffic traces shows that the proposed pipeline architecture outperforms HyperCut and B2PC schemes in classification speed by at least one order of magnitude, while with a similar storage requirement. Particularly, with different types of classifiers of 4K rules, the proposed pipeline architecture is able to achieve a throughput between 19.5 Gbps and 91 Gbps.

One of the major threats to cyber security is the distributed denial-of-service (DDoS) attack. In this paper, we focus on three kinds of sophisticated DDoS attacks that seriously cripple the current DDoS defense systems and have not been solved yet. In fast adaptive attacks (FAAs), attackers adaptively generate attacking traffic based on the feedback from a victim in round trip time (RTT). Almost all proposed rules-based filtering schemes cannot effectively defend against FAAs, since they need a relatively long time (compared to RTT) to update filtering rules. In adaptive attacks with statistical filtering rules scanning (AAS), attackers circumvent the defense system by discovering the statistical filtering rules of the defense system and then generating flooding traffic to mimic nominal traffic. In low rate TCP attacks (LRAs), attackers send periodic attack pulses to overflow a router's buffer and force the legitimate TCP flow to a low throughput while staying under the radar with a very low average rate. In this paper, we propose a leaky-bucket (LB) based highly robust DDoS defense system, called RateGuard. It can react to FAAs and LRAs by rate-limiting excessive traffic in real-time according to the victim's nominal traffic profile. Moreover, by associating an LB with each joint attribute value, the huge space required for possible joint attribute values makes it almost impossible for attackers to scan the victim's nominal traffic profiles and, thus, makes it highly robust to cope with AAS and other sophisticated attacks.

We propose a fast reroute scheme for the single link failure protection of IP multicast network. A multicast network connects nodes as a spanning tree, which is vulnerable to link failures. Our scheme uses ring topologies to ensure a backup path always exists to any single link failure and only a few nodes in the neighborhood of the failed link have to react to the failure. Compare to other solutions, we have four advantages: (1) The multicast tree can be arbitrary. (2) There is only a minimal disruption and there would be no packet loss. (3) Failure protection is available to a wider set of network topologies. (4) Only a small number of multicast nodes are involved and the number of spare links used are also small.

Failure recovery using IP fast reroute (IPFRR) has gained much attention recently. The basic idea is to find backup paths and configure the routing tables in advance. After a failure is detected, the pre-determined backup paths are used immediately to forward the affected packets. Since the calculation and configuration are performed in advance, the recovery can be completed very quickly. IPFFR is considered as a promising approach to enhance the survivability of IP networks. While single failure recovery has been extensively researched, using IPFRR for double-link failure recovery remains as a great challenge. We propose a solution for this issue called Efficient SCan for Alternate Paths for double-link failure recovery (ESCAP-DL). ESCAP-DL guarantees 100% coverage from both single and double-link failures and has the advantages of low complexity and resource requirement. The scheme resumes packet forwarding immediately after failures are detected and does not require failure advertising throughout the network.

Packet switches with optical fabrics can potentially scale to higher capacities. It is also potentially possible to improve their reliability, and reduce both their footprint and power consumption. A well-known alternative for implementing hardwired switches is Arrayed Waveguide Grating (AWG). Ideally, AWG insertion losses do not depend on the number of input-output ports, meaning that scalability is theoretically infinite. However, accurate second-order assessment has demonstrated that in-band crosstalk exponentially increases the power penalty, limiting the realistic useful size of AWG commercial devices to about 10-15 ports (13-18 dB). On the other hand, the in-band crosstalk at AWG outputs depends on the connection pattern set by the scheduling algorithm and this port count limitation is calculated for worst-case scenarios. In this paper, we show that distributed schedulers with predetermined connection patterns can be used to avoid these harmful arrangements. We also show that the probability of worst-case patterns is very low, allowing us to set a more realistic port limit for general centralized schedulers and very small losses. With these results, we calculate more realistic port count limits for both scheduler types.

The load-balanced (LB) switch proposed by C.S. Chang et al. consists of two stages. First, a load-balancing stage converts arriving packets into uniform traffic. Then, a forwarding stage transfers packets from the line-cards to their final output destination. Load-balanced switches do not need a centralized scheduler and can achieve 100% throughput for a broad class of traffic distributions. However, load-balanced switches may cause packets at the output port to be out of sequence. Several schemes have been proposed to tackle the out of- sequence problem of the load-balanced switch. They are either too complex to implement, or introduce a large additional delay. In this paper, we present a practical load-balanced switch, called the Byte-Focal switch, which uses packet-by-packet scheduling to significantly improve the delay performance over switches of comparable complexity. We prove that the queues at the input need only finite buffering, and that the overall switch is stable under any traffic matrix. Our analysis shows that the average queuing delay is roughly linear with the switch size N, and although the worst case resequencing delay is N2, the average resequencing delay is much smaller. This means that we can reduce the required resequencing buffer size significantly.

Network applications often require large data storage resources, fast queries, and frequent updates. Hash tables support these operations with low costs, yet they cannot provide worst-case guarantees because of hash collisions. Also, the widely used, low-cost Dynamic Random Access Memory (DRAM) cannot suitably accommodate hash tables because DRAMs provide full bandwidth only if accessed in bursts, whereas hash tables require random access. In this paper, we propose a hash co-processor to support hash tables on DRAMs. The co-processor provides a load-balancing method to reduce the impact of hash collisions on the worst-case behavior by moving multiple keys within the hash table in constant time. This leads to a balanced distribution of keys in the hash table despite the collisions. Furthermore, the coprocessor guarantees the full DRAM bandwidth is always utilized by defining all fundamental hash table operations, namely insert, query, and delete, in terms of burst accesses. In the worst case, the query, delete, and insert operations take one, two, and three burst accesses, respectively. The proposed architecture reduces hash overflows by 35% compared to a naive hash table and for each key uses 6.42 bits of on-chip memory.

Today's network line rates reach speeds of 40 Gbps and are anticipated to reach 100 Gbps in the near future. These high speeds make Deep Packet Inspection (DPI) in Network Intrusion Detection and Prevention Systems (NIDPSs) very challenging. The DPI examines each incoming packet byte-by- byte and matches them against a set of predefined malicious signatures. One way to achieve high-speed DPI is to store all the signatures on high-speed on-chip memory. However, on-chip memory is limited and space-efficient data structures are needed to leverage precious on-chip memory efficiently. A hash table addressed by a Minimal Perfect Hash Function (MPHF) is such a high-speed, space efficient data structure. In this paper, we describe a highly memory-efficient MPHF, which requires 3.5 bits per key to facilitate access to the key in on-chip memory while allowing us to perform the expensive exact match operation only once. The proposed MPHF also has a low construction time.

Network intrusion detection and prevention systems (NIDPSs) are critical for network security. The deep packet inspection (DPI) operation consumes a significant amount of resources in NIDPS. This is because to detect malicious activity DPI searches a database of signatures for each byte of every packet. In this paper, we develop a highly space-efficient data structure for hardware realization of minimal perfect hash functions (MPHFs). This data structure is simple to construct, requires 7 n bits to represent the MPHF for a set of n keys and allows high-speed DPI.

One of the major threats to cyber security is the distributed denial-of-service (DDoS) attack. In our previous projects, PacketScore, ALPi, and other statistical filtering-based approaches defend DDoS attacks via fine-grain comparisons between the measured current traffic profile and the victim's nominal profile. These schemes can tackle virtually all kinds of DDoS attacks, even never-before-seen attack types, due to the underlying statistics-based adaptive differentiation. The viability of those aforementioned statistical filtering defense systems is based on the premise that attackers do not know the victim's nominal traffic profile and, thus, cannot fake legitimate traffic. However, a sophisticated DDoS attacker might circumvent the defense system by discovering the statistical filtering rules and then controlling zombies to generate flooding traffic according to these discovered rules. This type of sophisticated attack seriously threatens the current Internet and has not yet been solved. In this paper, we propose a principal components analysis (PCA)-based DDoS defense system, which extracts nominal traffic characteristics by analyzing intrinsic dependency across multiple attribute values. The PCA-based scheme differentiates attacking packets from legitimate ones by checking if the current traffic volume of the associated attribute value violates the intrinsic dependency of nominal traffic. The correlation among different attributes makes it more difficult for the attacker to accurately discover the statistic filtering rules and, thus, makes it highly robust to cope with new and more sophisticated attacks.

Multi-Path Switching systems (MPS) are intensively used in the state-of-the-art core routers. One of the most intractable issues is how to load-balance traffic across its multiple paths while not disturbing the intra-flow packet orders. In this paper, based on the studies of tens of real Internet traces, we develop a novel scheme, namely Flow-Slice (FS), which cuts off each flow into flow-slices at every intra-flow interval larger than a slicing threshold set to 1ms 4ms and balances the load on the finer granularity. Through theoretical analyses and comprehensive trace-driven simulations, we show that FS achieves impressive load-balancing performance with little hardware cost while limiting the packet out-of-order chances to a negligible level (below 10 -6).

In this paper, we propose DATALITE, a Distributed Architecture for Traffic Analysis via LIght-weight Traffic digEst, which introduces a set of new distributed algorithms and protocols to support general Traffic Measurement and Analysis (TMA) functions for large-scale, 10Gbps+ packet-switched networks. We formulate the network-wide traffic measurement/ analysis problem as a series of set-cardinality-determination (SCD) problems. By leveraging recent advances in probabilistic distinct sample counting techniques, the set-cardinalities, and thus, the network-wide traffic measurements of interest can be computed in a distributed manner via the exchange of extremely light-weight traffic digests (TD’s) amongst the network nodes. A TD for N packets only requires O(loglog N) bits of memory storage.

Failure recovery in IP networks is critical to high quality service provisioning. The main challenge is how to achieve fast recovery without introducing high complexity and resource usage. Today’s networks mainly use route recalculation and lower layer protection. However, route recalculation could take as long as seconds to complete; while lower layer protection usually requires considerable bandwidth redundancy. We present two fast rerouting algorithms to achieve recovery from single-link and single-node failures, respectively. The idea is to calculated backup paths in advance. When a failure is detected, the affected packets are immediately forwarded through backup paths to shorten the service disruption. This paper answers the following questions: 1. How to find backup paths? 2. How to coordinate routers during the rerouting without explicit signaling? 3. How to realize distributed implementation? The schemes react to failures very fast because there are no calculations on the fly. They are also cost efficient because no bandwidth reservation is required. Our schemes guarantee 100% failure recovery without any assumption on the primary paths. Simulations show that our schemes yield comparable performance to shortest path route recalculation. This work illuminates the possibility of using pure IP layer solutions to build highly survivable yet cost-efficient networks.

Network Intrusion Detection and Prevention Systems (NIDPSs) are vital in the fight against network intrusions. NIDPSs search for certain malicious content in network traffic (i.e., signatures). Comparing all traffic to these signatures is a challenge for high-speed networks. In this paper, we present the implementation of a 10-Gbps hardware NIDPS and related design issues. This goal of signature detection at high-speed is achieved using a single FPGA, without any external memory. We also implemented and tested a proof-of-concept system with 1-Gbps traffic. A database to store and a Web server to display the intrusion alerts from the NIDPS were also developed for this system.

Bloom Filters (BFs) are fundamental building blocks in various network security applications, where packets from high-speed links are processed using state-of-the-art hardware- based systems. In this paper, we propose Aggregated Bloom Filters (ABFs) to increase the throughput and scalability of BFs. The proposed ABF has two methods to improve average speed and scalability. The first method leverages the query mechanism for hardware BFs. We optimize queries by removing redundant hash calculations and memory accesses. First, to remove redundancy, the hash functions for each query are calculated sequentially. As soon as we have a no match in any of the hash results, the query is immediately abandoned. We then aggregate multiple queries and query a BF with all of these queries in parallel, which maximizes the throughput of the BF. The second method addresses scalability issues regarding the on-chip memory resources. In most applications multiple BFs are required to store many sets with different numbers of elements. These sets may also be too small for the unit memory on-chip. So, most of the memory is left unused, causing low memory utilization. The second method aggregates small distributed BFs to a single BF allowing better on-chip memory utilization. For the application of Network Intrusion Detection and Prevention Systems (NIDPSs), our proposed ABF shows seven-fold improvement in the average query throughput and four times less memory usage.

Failure recovery in IP networks is critical to high quality service provisioning. One of the challenges is how to achieve fast recovery without introducing high complexity and resource usage. Today's main approaches are route recalculation and lower layer protection, where recalculation could take a long time to complete; while protection usually requires considerable bandwidth redundancy. IP fast rerouting achieves ultra fast failure recovery by calculating alternate paths in advance. When a failure is detected, the affected packets are immediately forwarded through alternate paths to shorten the service disruption. We present an algorithm called Efficient SCan for Alternate Paths (ESCAP) to achieve fast rerouting. The algorithm guarantees 100% recovery of single-link and single-node failures. In particular, it supports generic multi- path routing (where a router maintains multiple paths to a single destination) and does not require the paths to have equal cost. The implementation of ESCAP has low complexity and does not introduce explicit signaling between routers. Simulations show that our scheme yields comparable performance to shortest path route recalculation. This work illuminates the possibility of using pure IP layer solutions to enhance the Internet survivability.

Deep packet inspection (DPI) is often used in network intrusion detection and prevention systems (NIDPS), where incoming packet payloads are compared against known attack signatures. Processing every single byte in the incoming packet payload has a very stringent time constraint, e.g., 200 ps for a 40-Gbps line. Traditional DPI systems either need a large memory space or use special memory such as ternary content addressable memory (TCAM), limiting parallelism, or yielding high cost/power consumption. In this paper, we present a highspeed, single-chip DPI scheme that is scalable and configurable through memory updates. The scheme is based on a novel data structure called TriBiCa (trie bitmap content analyzer), which provides minimal perfect hashing functionality. It uses a trie structure with a hash function performed at each layer. Branching is determined by the hashing results with an objective to evenly partition attack signatures into multiple groups at each layer. During a query, as an input traverses the trie, an address to a table in the memory that stores all attack signatures is formed and is used to access the signature for an exact match. Due to the small space required, multiple copies of TriBiCa can be implemented on a single chip to perform pipelining and parallelism simultaneously, thus achieving high throughput. We have designed the TriBiCa on a modest FPGA chip, Xilinx Virtex II Pro, achieving 10-Gbps throughput without using any external memory. A proof-of-concept design is implemented and tested with 1-Gbps packet streams. By using today's state-of-the-art FPGAs, a throughput of 40 Gbps is believed to be achievable.

Virtual Output Queuing is widely used by highspeed packet switches to overcome head-of-line blocking. This is done by means of matching algorithms. In fixed-length VOQ switches, variable-length IP packets are segmented into fixed- length cells at the inputs. When a cell is transferred to its destination output, it will stay in the reassembly buffer and wait for the other cells of the same packet before the entire packet can depart the system. The delay a packet suffers in the system includes the waiting time in the VOQ, the widely studied cell delay, and the waiting time at the output reassembly buffer, the reassembly delay often ignored in many papers. Among all existing matching algorithms, Maximum Weight Matching (MWM) has the lowest average cell delay. In this paper, we investigate the average packet delay, one of the key performance measure for an input buffered packet switch. A new class of matching algorithms, PDA-MWM, is defined and proved to be stable under all admissible traffic. Three PDA-MWM matching algorithms are studied by simulation. We show that, in order to achieve low packet delay, there is a tradeoff between the cell delay performance and the reassembly delay performance. If both of them are carefully considered, a matching scheme can greatly reduce the packet delay as compared to MWM.

Distributed denial-of-service (DDoS) attacks pose a significant threat to the Internet. Most solutions proposed to-date face scalability problems as the size and speed of the network increase, with no widespread DDoS solution deployed in the industry. PacketScore has been proposed as a proactive DDoS defense scheme, which detects DDoS attacks, differentiates attack packets from legitimate ones with the use of packet scoring (where the score of a packet is calculated based on attribute values it possesses), and discards packets whose scores are lower than a dynamic threshold. In this paper, we propose ALPi, a new scheme which extends the packet scoring concept with reduced implementation complexity and enhanced performance. More specifically, a leaky-bucket overflow control scheme simplifies the score computation, and facilitates high-speed implementation. An attribute-value-variation scoring scheme analyzes the deviations of the current traffic attribute values, and increases the accuracy of detecting and differentiating attacks. An enhanced control-theoretic packet discarding method allows both schemes to be more adaptive to challenging attacks such as those with ever-changing signatures and intensities. When combined together, the proposed extensions not only greatly reduce the memory requirement and implementation complexity but also substantially improve the accuracies in attack detection and packet differentiation. This makes ALPi an attractive DDoS defense system amenable for high-speed hardware implementation.

Distributed denial-of-service (DDoS) attacks are a critical threat to the Internet. This paper introduces a DDoS defense scheme that supports automated online attack characterizations and accurate attack packet discarding based on statistical processing. The key idea is to prioritize a packet based on a score which estimates its legitimacy given the attribute values it carries. Once the score of a packet is computed, this scheme performs score-based selective packet discarding where the dropping threshold is dynamically adjusted based on the score distribution of recent incoming packets and the current level of system overload. This paper describes the design and evaluation of automated attack characterizations, selective packet discarding, and an overload control process. Special considerations are made to ensure that the scheme is amenable to high-speed hardware implementation through scorebook generation and pipeline processing. A simulation study indicates that packetscore is very effective in blocking several different attack types under many different conditions.

It is now a fact that manual defenses against worm epidemics are not practical. Recently, various automatic worm identification methods are proposed to be deployed at high-speed network nodes to respond in time to fast infection rates of worms. Unfortunately, these methods can easily be evaded by fragmentation of the worm packets. The straightforward defragmentation method is not applicable for these high-speed nodes, due to its high storage (memory) requirement. In this paper, this problem, namely the multi-packet signature detection problem is addressed using a defragmentation-free, space-efficient solution. A new data structure - prefix bloom filters - along with a new heuristic, called the chain heuristic is proposed to significantly reduce the storage requirement of the problem, so that multi-packet signature detection becomes feasible for high-speed network nodes.

Optical cell switching (OCS) is a new flexible all-optical switching paradigm. An OCS consists of cell edge routers (CER) and core switches (OCX). The CER is the interface between the electrical domain and the optical domain, while the OCX is the all optical packet switch without opto-electro-optical (OEO) conversion. In our previous research we have proposed a low complexity and highly scalable switch architecture for the OCX with several high performance scheduling algorithms. In this paper, we focus on the design of the CER. To maximize the optical bandwidth utilization and minimize the packet delay within the OCS, most of OCS intelligence and functionalities are build in the CER. To ensure the performance and the quality of the OCS network, we propose two practical and scalable switch architectures and corresponding efficient scheduling algorithms for ingress and egress CERs accordingly. We show by simulations that with the proposed scheduling algorithms both CERs can achieve /spl sim/100% throughput. Additionally, the complexity of both scheduling algorithms at two routers is only O(log(N)).

Input-buffered switches have been widely considered for implementing feasible packet switches. However, their matching process may not be time-efficient for switches with high-speed ports. Buffered crossbars (BXs) are an alternative to relax timing for packet switches with high-speed ports and to provide high-performance switching. BX switches were originally considered expensive, as the memory amount required in the crosspoints (XPs) is proportional to the square of the number of ports (O(N/sup 2/)). This limitation is now less stringent with the advances on chip-fabrication techniques, and when considering small crosspoint (XP) buffer sizes. In this paper, we study a combined input-crosspoint buffered packet switch, named CIXB, with virtual output queues (VOQs) at the inputs, and arbitration based on round-robin selection. We show that the CIXB switch achieves 100% throughput under uniform traffic, and high performance under nonuniform traffic, using one-cell XP buffer size and no speedup.

A network coexistence methodology is investigated for robust coexistence of an arbitrary set of non-collaborative networks. It is shown that maximizing the energy efficiency of each node is the key to the capacity maximization for the coexisting networks. Unlike existing pairwise coexisting schemes, a two level distributed algorithm is proposed without resorting to any knowledge of the physical layer and MAC layer protocols of interfering networks. The coexistence scheme is formulated as an N-person noncooperative power-controlled coexistence game (NPCG) whose convergence and optimality properties are discussed from a game theory view point. One interesting property of the game is that the Nash equilibrium of the game is on the Pareto frontier, i.e., a social optimal of the distributed networks.

Optical packets may arrive at an optical switch in an uncoordinated fashion. Therefore, fiber delay lines (FDL) are needed to buffer packets when contention occurs. There have been several optical-buffered switch architectures and FDL assignment algorithms proposed in the literature. However, most of them either have high implementation complexity, or fail to schedule departure time for delayed packets. In this paper, we study the scheduling algorithms for the single-stage shared-FDL optical packet switch. We propose two new FDL assignment algorithms: the sequential FDL assignment (SEFA) algorithm and the multi-cell FDL assignment (MUFA) algorithm. Our algorithms can make resource reservation so as to schedule departure time for packets. Owing to FDL and/or output-port conflicts, the packets that fail to be scheduled are discarded before entering the switch. We show by simulation that with these algorithms, the optical-buffered switch can achieve a loss rate of /spl sim/10/sup -7/ even at the load of 0.9.

Distributed denial of service (DDoS) attack is a critical threat to the Internet. Recently we have proposed the PacketScore scheme, a DDoS defense architecture that supports automated attack detection, on-line attack characterization and attack blocking. Its key idea is to use a statistics-based packet scoring mechanism to distinguish between legitimate and non-legitimate packets and discard packets based on the packet scores. In order for such an approach to work, we need to perform on-line traffic characterizations, and compare such characterizations with the nominal profiles (generated from past history or off-line analysis). The threshold used for the score-based selective packet discard decision is dynamically adjusted based on the score distribution of recent incoming packets. In our previous paper [Kim et al. 2004], we discuss how our proposed system performs in different attack scenarios. In this paper, we first give a brief review of the PacketScore approach and further elaborate on the transient performance under varying attack types and intensities, which may be exploited in more sophisticated attacks. We then show that PacketScore is well capable of blocking such sophisticated attacks by simply adjusting the measurement window time scale to closely track the attack profile.

The scalability of Clos-network switches makes them an alternative to single-stages switches for implementing large-size packet switches. This paper introduces a cell dispatching scheme, called Maximum Weight Matching Dispatching (MWMD) scheme, for buffered Clos-network switches. The MWMD scheme is based on a maximum weight matching algorithm for input-buffered switches. This paper shows that, with request queues in the buffered Clos-network architecture, the MWMD scheme is able to achieve a 100% throughput for independent admissible traffic, without allocating any buffers in the second stage and without expanding the internal bandwidth. As a practical scheme, a maximal oldest-cell-first matching dispatching (MOMD) scheme is also introduced. MOMD shows that using a finite number of iterations in the dispatching scheme, the throughout under unbalanced traffic pattern can be high.

Distributed denial of service (DDoS) attack is a critical threat to the Internet. Currently, most ISPs merely rely on manual detection of DDoS attacks after which offline fine-grain traffic analysis is performed and new filtering rules are installed manually to the routers. The need of human intervention results in poor response time and fails to protect the victim before severe damages are realized. The expressiveness of existing filtering rules is also too limited and rigid when compared to the ever-evolving characteristics of the attacking packets. Recently, we have proposed a DDoS defense architecture that supports distributed detection and automated on-line attack characterization. We focus on the design and evaluation of the automated attack characterization, selective packet discarding and overload control portion of the proposed architecture. Our key idea is to prioritize packets based on a per-packet score which estimates the legitimacy of a packet given the attribute values it carries. Special considerations are made to ensure that the scheme is amenable to high-speed hardware implementation. Once the score of a packet is computed, we perform score-based selective packet discarding where the dropping threshold is dynamically adjusted based on (1) the score distribution of recent incoming packets and (2) the current level of overload of the system.

Packet classification plays an important role in next-generation Internet routers in providing various services such as packet filtering, policy routing, traffic policing, and load balancing. In this paper, we propose an original field-level trie classification (FLTC) scheme that accommodates classifier (rule database) with multiple fields specified in different forms (prefix and range). The FLTC achieves a high classification speed with reasonable storage. It is also highly scalable regarding the size and the number of fields of classifiers.

This paper presents a new packet scheduling scheme, called frame-based exhaustive matching (FEM), to efficiently resolve the contention in a 3-stage Clos-network photonic switch. Using extended frames to aggregate cells from different incoming lines, the extended frame relaxes the stringent arbitration time constraint at the ultrafast port speed achievable in the photonic switch fabric. We also evaluate and analyze system performances, including throughput and packet delay, under various traffic conditions. At the expense of a moderate internal speedup of 1.5, throughput close to 100% under various traffic conditions can be achieved in a 3-stage Clos-network switch without expansion.

Virtual output queue (VOQ) architecture is commonly used for avoiding head-of-line blocking in input-queued switches. Many algorithms have been developed for transferring the cells from the VOQs to the output ports. Traditional iterative algorithms such as iSLIP and DRRM, achieve 100% throughput under uniform traffic. but under non-uniform traffic, throughput drops significantly. Recently, a new paradigm of exhaustive matching (EM) has been introduced for handling non-uniform traffic while preserving the complexity of traditional iterative algorithms. In EM, a VOQ is served continuously until it becomes empty. Only the input ports that have finished serving a VOQ look for a new match. This strategy produces very good throughput and delay performance in uniform and non-uniform traffic. However under some traffic patterns, there is a starvation problem when a VOQ occupies an output port for an extended period of time. This problem can be eliminated by providing a priority service for a VOQ that has waited an excessively long time. The resulting algorithm, prioritized EM (PEM), eliminates starvation and achieves very high throughput for many traffic patterns.

This paper presents a new petabit photonic packet switch (P/sup 3/S) architecture that is highly scalable both in dimension and capacity while maintaining high system performances. Using a new multidimensional photonic multiplexing scheme that includes space, time, wavelength, and subcarrier domains, we propose a photonic switch fabric based on a 3-stage Clos network to provide scalable large-dimension photonic interconnections with nanosecond reconfiguration speed. Packet buffering is implemented electronically at the input and output port controllers, allowing the central photonic switch fabric to transport high-speed optical signals without electrical-to-optical conversion. Optical time division multiplexing (OTDM) technology further scales port speed beyond electronic speed up to 160 Gbits/s to minimize the fiber connections. To solve output contention, we propose a new arbitration scheme, called frame-based exhaustive matching (FEM), using extended frames to aggregate cells from different incoming lines. The extended frame relaxes the stringent arbitration time constraint at a 160 Gbit/s port speed. Based on the FEM scheme in the proposed architecture, a 6400 /spl times/ 6400 switch with a total capacity of 1.024 petabit/s can be achieved with throughput close to 100% under various traffic conditions.

We present a hardware solution that can reliably block most of the malicious TCP traffic at the edge routers while passing the legitimate TCP traffic during a distributed denial-of-service (DDoS) attack on the Internet. By allocating bandwidths separately for TCP, the TCP portion of the bandwidth can be protected. In a simulation study, the filter successfully blocked 99.9% of the attack traffic while legitimate traffic showed nearly identical performance as in the non-attacked condition. This filtering is transparent to the hosts or routers and a filtering device can be easily attached to router ports.

This paper presents a new petabit photonic packet switch architecture, called PetaStar. Using a new multidimensional photonic multiplexing scheme that includes space, time, wavelength, and subcarrier domains, PetaStar is based on a three-stage Clos-network photonic switch fabric to provide scalable large-dimension switch interconnections with nanosecond reconfiguration speed. Packet buffering is implemented electronically at the input and output port controllers, allowing the central photonic switch fabric to transport high-speed optical signals without electrical-to-optical conversion. Optical time-division multiplexing technology further scales port speed beyond electronic speed up to 160 Gb/s to minimize the fiber connections. To solve output port contention and internal blocking in the three-stage Clos-network switch, we present a new matching scheme, called c-MAC, a concurrent matching algorithm for Clos-network switches. It is highly distributed such that the input-output matching and routing-path finding are concurrently performed by scheduling modules. One feasible architecture for the c-MAC scheme, where a crosspoint switch is used to provide the interconnections between the arbitration modules, is also proposed. With the c-MAC scheme, and an internal speedup of 1.5, PetaStar with a switch size of 6400 × 6400 and total capacity of 1.024 petabit/s can be achieved at a throughput close to 100% under various traffic conditions.

In high-speed and high-capacity packet switches, system reliability is critical to avoid loss of huge amounts of information and retransmission of traffic. We propose a series of concurrent fault-detection mechanisms for a multiple-plane crossbar-based packet switch. Our switch model, called the m+z model, has m active planes and z spare planes. This switch has distributed arbiters on each plane. The spare planes, used for substitution of faulty active ones, are also used in the fault-detection mechanism, thus providing fault detection and fault location for all switching planes. Our detection schemes are able to detect a single fault quickly without increasing transmission overhead. The proposed schemes can be used for switches with different numbers of active planes and a small number of spare planes.

Virtual Output Queuing is widely used by fixed-length high-speed switches to overcome head-of-line blocking. This is done by means of matching algorithms. Maximum matching algorithms have good performance, but their implementation complexity is quite high. Maximal matching algorithms need speedup to guarantee good performance. Iterative algorithms (such as PIM and iSLIP) use multiple iterations to converge on a maximal match. The Dual Round-Robin Matching (DRRM) scheme has performance similar to iSLIP and lower implementation complexity. The objective of matching algorithms is to reduce the matching overhead for each time slot. The Exhaustive Service Dual Round-Robin Matching (EDRRM) algorithm amortizes the cost of a match over multiple time slots. While EDRRM suffers from a throughput below 100% for small switch sizes, it is conjectured to achieve an asymptotic 100% throughput under uniform traffic. Simulations show that it achieves high throughput under nonuniform traffic. Its delay performance is not sensitive to traffic burstiness, switch size and packet length. In an EDRRM switch cells belonging to the same packet are transferred to the output continuously, which leads to good packet delay performance and simplifies the implementation of packet reassembly. In this paper we analyze the performance of an EDRRM switch by using an exhaustive service random polling system model. This was used to predict the performance of switches too large to be simulated within a reasonable run time.

This paper proposes a pipeline-based concurrent round-robin dispatching scheme, called PCRRD, for Clos-network switches. Our previously proposed concurrent round-robin dispatching (CRRD) scheme provides 100% throughput under uniform traffic by using simple round-robin arbiters, but it has the strict timing constraint that the dispatching scheduling has to be completed within one cell time slot. This is a bottleneck in building high-performance switching systems. To relax the strict timing constraint of CRRD, we propose to use more than one scheduler engine, up to P, so called subschedulers. Each subscheduler is allowed to take more than one time slot for dispatching. Every time slot, one out of P subschedulers provides the dispatching result. The subschedulers adopt our original CRRD algorithm. We show that PCRRD preserves 100% throughput under uniform traffic of our original CRRD algorithm, while ensuring the cell-sequence order. Since the constraint of the scheduling timing is dramatically relaxed, it is suitable for high-performance switching systems even when the switch size increases and port speed is high (e.g., 40 Gbit/s).

A Clos-network switch architecture is attractive because of its scalability. Previously proposed implementable dispatching schemes from the first stage to the second stage, such as random dispatching (RD), are not able to achieve high throughput unless the internal bandwidth is expanded. This paper presents two round-robin-based dispatching schemes to overcome the throughput limitation of the RD scheme. First, we introduce a concurrent round-robin dispatching (CRRD) scheme for the Clos-network switch. The CRRD scheme provides high switch throughput without expanding internal bandwidth. CRRD implementation is very simple because only simple round-robin arbiters are adopted. We show via simulation that CRRD achieves 100% throughput under uniform traffic. When the offered load reaches 1.0, the pointers of round-robin arbiters at the first- and second-stage modules are completely desynchronized and contention is avoided. Second, we introduce a concurrent master-slave round-robin dispatching (CMSD) scheme as an improved version of CRRD to make it more scalable. CMSD uses hierarchical round-robin arbitration. We show that CMSD preserves the advantages of CRRD, reduces the scheduling time by 30% or more when arbitration time is significant and has a dramatically reduced number of crosspoints of the interconnection wires between round-robin arbiters in the dispatching scheduler with a ratio of 1//spl radic/N, where N is the switch size. This makes CMSD easier to implement than CRRD when the switch size becomes large.

This paper proposes an innovative pipeline-based maximal-sized matching scheduling approach, called PMM, for input-buffered switches. It dramatically relaxes the timing constraint for arbitration with a maximal matching scheme. In the PMM approach, arbitration operates in a pipelined manner, where K subschedulers are used. Each subscheduler is allowed to take more than one time slot for its matching. Every time slot, one of them provides the matching result. The subscheduler can adopt a pre-existing efficient maximal matching algorithm such as iSLIP and DRRM. PMM maximizes the efficiency of the adopted arbitration scheme by allowing sufficient time for a number of iterations. We show that PMM preserves 100% throughput under uniform traffic and fairness for best-effort traffic of the pre-existing algorithm.

In high-speed and high-capacity packet switches, system reliability is critical to avoid the loss of a huge amount of information and to avoid re-transmission of traffic. We propose a series of concurrent fault-detection mechanisms for a multiple-plane crossbar-based packet switch. Our switch model, called the m + z model, has m active planes and z spare planes. This switch has distributed arbiters on each plane. The spare planes, used for substitution of faulty active ones, are also used in the fault detection mechanism, thus providing sufficient data redundancy for fault detection and location. Our detection scheme is able to detect a single fault in one time slot without increasing transmission overhead. The proposed schemes can be used for switches with different numbers of active planes and the number of spare planes needed for fault detection is small.

We propose a novel architecture, a combined input-crosspoint-output buffered (CIXOB-k, where k is the size of the crosspoint buffer) Switch. CIXOB-k architecture provides 100% throughput under uniform and unbalanced traffic. It also provides timing relaxation and scalability. CIXOB-k is based on a switch with combined input-crosspoint buffering (CIXB-k) and round-robin arbitration. CIXB-k has a better performance than a non-buffered crossbar that uses iSLIP arbitration scheme. CIXOB-k uses a small speedup to provide 100% throughput under unbalanced traffic. We analyze the effect of the crosspoint buffer size and the switch size under uniform and unbalanced traffic for CIXB-k. We also describe solutions for relaxing the crosspoint memory amount and scalability for a CIXOB-k switch with a large number of ports.

A Clos-network switch architecture is attractive because of its scalability. Previously proposed implementable dispatching schemes from the first stage to the second stage, such as random dispatching, are not able to achieve a high throughput unless the internal bandwidth is expanded. This paper proposes a concurrent round-robin dispatching (CRRD) scheme for a Clos-network switch, to overcome the throughput limitation of the random dispatching scheme. The CRRD scheme provides high switch throughput without expanding internal bandwidth. CRRD implementation is very simple because only simple roundrobin arbiters are adopted. In CRRD, the round-robin arbiters concurrently perform the matching between requesting cells and output links in each first-stage module to dispatch the cells to available second-stage modules. We show that CRRD achieves 100% throughput under uniform traffic. When the offered load reaches 1.0, the pointers of roundrobin arbiters at the first-stage and second-stage modules are effectively desynchronized and contention is avoided. key words: Packet switch, Clos-network switch, dispatching, arbitration, throughput

The dual round-robin matching (DRRM) switch has a scalable, low complexity architecture which allows for an aggregate bandwidth exceeding 1 Tb/s using current CMOS technology. In this paper we prove that the DRRM switch can achieve 100% throughput under i.i.d. and uniform traffic. The DRRM is the first practical matching scheme for which this property has been proved. The performance of the DRRM switch is then studied and compared with the iSLIP switch. The delay performance under uniform traffic and the hot-spot throughput of DRRM is better than that of iSLIP, while the throughput of iSLIP under some nonuniform traffic scenarios is slightly higher than that of DRRM. Since throughput drops below 100%, under nonuniform traffic, we also examine some variations of the DRRM matching scheme for nonuniform traffic.

Congestion control for reliable multicast for large multicast groups has been a challenging issue for widespread deployment of reliable multicast services. We propose a receiver-driven window congestion control scheme with dynamic grouping for reliable multicast. The main objective is to improve multicast throughput performance and to solve the well-known "drop-to-zero" problem, i.e., to prevent a slow receiver from slowing down faster receivers in the same multicast group. For this purpose, we modify the window scheme and combine it with a new dynamic grouping scheme for local recovery to achieve high-throughput performance. The basic idea is two-fold. First, the sender can tune its window size according to the fastest receiver in a virtual group instead of the slowest receiver by taking advantage of the local recovery. Second, the sender can explicitly ask a worst-case group (WCG), which can be recorded in a simple list in cache or memory, to merge with others or unsubscribe from the multicast group. The proposed strategy is shown to be still TCP-friendly and scalable while eliminating the "drop-to-zero" problem. Some key related issues are also discussed.

Input-output buffering with a moderate speedup has been widely considered as the most feasible solution for large-capacity switches. We propose a new terabit/sec packet switch and call it the Saturn (Switch At Terabit Using dual Round-robiN) switch. It uses a simple dual round-robin arbitration scheme to schedule packet and achieves high throughput and low statistical delay bound. It employs a bit-sliced crossbar fabric to switch packets at 10 Gbit/s at inputs and outputs, and adopts a novel token-tunneling technique to arbitrate contending packets at high speed (e.g,, within 10 ns), thus achieving a switch capacity of more than one terabit/sec by existing electronic technology.

CIOB (combined input-output buffered) switches with a moderate speedup have been widely considered as the most feasible solution for large-capacity switches. In this paper, we adopt the hierarchical link sharing (HLS) algorithm in non-blocking CIOB switches to guarantee delay bound that is independent of the switch size. We also propose a feasible architecture to implement the HLS algorithm in the switch, which can accommodate the packet carried over a 10 Gbit/s line without a speedup requirement. Furthermore, we design a new serial comparator to find minimum time-stamp values.

This paper presents a network node architecture and several traffic management mechanisms that are capable of achieving QoS provisioning for the guaranteed service (GS), the controlled-load (CL) service, and the best-effort (BE) service under IETF integrated services (IntServ) paradigm. Our architecture offers the attractive feature of in-sequence delivery for all packets, albeit some of which may be out-of-profile. Simulation results show that, once admitted into the network, our architecture and traffic management algorithms provide hard performance guarantees to GS flows under all conditions, consistent (or soft) performance to CL flows under both light load and heavy load conditions, and minimal negative impact to in-profile GS, CL and BE traffic should there be any out-of-profile behavior from some flows.

We present an end-to-end approach to generalize the classical theory of rate distortion (R-D) optimized mode selection for point-to-point video communication. We introduce a notion of global distortion by taking into consideration of both the path characteristics and the receiver behavior, in addition to the source behavior. We derive, for the first time, a set of accurate global distortion metrics for any packetization scheme. Equipped with the global distortion metrics, we design an R-D optimized mode selection algorithm to provide the best trade-off between compression efficiency and error resilience. As an application, we integrate our theory with point-to-point MPEG-4 video conferencing over the Internet. Simulation results conclusively demonstrate that our end-to-end approach offers superior performance over the classical approach for Internet video conferencing.

This paper proposes an adaptive quality-of-service (QoS) control to increase the robustness of MPEG-4 video communication over wireless channels. More specifically, the proposed adaptive QoS control consists of optimal mode selection and delay-constrained hybrid automatic repeat request (ARQ). The optimal mode selection is employed to provide QoS support on the compression layer while delay-constrained hybrid ARQ is used to provide QoS support on the link layer. Simulation results show that the proposed adaptive QoS control achieves satisfactory quality for MPEG-4 video under dynamically changing wireless channel conditions and utilizes network resources efficiently.

Rate-distortion (R-D) optimized mode selection is a fundamental problem for video communication over packet-switched networks. The classical R-D optimized mode selection only considers quantization distortion at the source. Such an approach is unable to achieve global optimality under the error-prone environment since it does not consider the packetization behavior at the source, the transport path characteristics, and receiver behavior. This paper presents an end-to-end approach to generalize the classical theory of R-D optimized mode selection for point-to-point video communication. We introduce a notion of global distortion by taking into consideration both the path characteristics (i.e., packet loss) and the receiver behavior (i.e., the error concealment scheme), in addition to the source behavior (i.e., quantization distortion and packetization). We derive, for the first time, a set of accurate global distortion metrics for any packetization scheme. Equipped with the global distortion metrics, we design an R-D optimized mode selection algorithm to provide the best tradeoff between compression efficiency and error resilience. The theory developed in this paper is general and is applicable to many video coding standards, including H.261/263 and MPEG-1/2/4. As an application, we integrate our theory with point-to-point MPEG-4 video conferencing over the Internet, where a feedback mechanism is employed to convey the path characteristics (estimated at the receiver) and receiver behavior (error concealment scheme) to the source. Simulation results are discussed.

With the success of the Internet and flexibility of MPEG-4, transporting MPEG-4 video over the Internet is expected to be an important component of many multimedia applications in the near future. Video applications typically have delay and loss requirements, which cannot be adequately supported by the current Internet. Thus, it is a challenging problem to design an efficient MPEG-4 video delivery system that can maximize the perceptual quality while achieving high resource utilization. This paper addresses this problem by presenting an end-to-end architecture for transporting MPEG-4 video over the Internet. We present a framework for transporting MPEG-4 video, which includes source rate adaptation, packetization, feedback control, and error control. The main contributions of this paper are: (1) a feedback control algorithm based on the Real Time Protocol (RTP) and the Real Time Control Protocol (RTCP); (2) an adaptive source-encoding algorithm for MPEG-4 video which is able to adjust the output rate of MPEG-4 video to the desired rate; and (3) an efficient and robust packetization algorithm for MPEG video bit-streams at the sync layer for Internet transport. Simulation results show that our end-to-end transport architecture achieves good perceptual picture quality for MPEG-4 video under low bit-rate and varying network conditions and efficiently utilizes network resources.

This paper presents an implementation architecture based on per flow queueing that is capable of achieving QoS provisioning for future integrated services networks consisting of the guaranteed service (GS), the controlled-load (CL), and the best-effort (BE) service classes. We propose several novel traffic management mechanisms, including adaptive rate allocation for controlled-load (ARC), a hybrid model-based and measurement-based admission control algorithm for GS and CL flows, and a quasi-pushout plus (QPO+) packet discarding mechanism. Simulation results show that our architecture and algorithms provide hard QoS guarantees to GS flows under all conditions, consistent (soft) QoS to CL flows under both light and heavy load conditions, and effective control of negative impact from non-conforming CL flows. Our architecture and algorithms also resolve several issues associated with the traditional class-based approach.

Provision of quality-of-service (QoS) guarantees is an important and challenging issue in the design of asynchronous transfer mode (ATM) networks. call admission control (CAC) is an integral part of the challenge and is closely related to other aspects of network designs such as traffic characterization and QoS specification. Since the usage parameter control (UPC) parameters are the only standardized traffic characterization, developing efficient CAC schemes based on UPC parameters is significant for the implementation of CAC on ATM switches. We develop a CAC algorithm called TAP (derived from tagged probability) as well as two other CAC algorithms using the UPC parameters. These CAC algorithms are based on our observation that the loss-probability-to-overflow-probability ratio tends to decrease as the number of sources increases. By introducing the loss-probability-to-overflow-probability ratio K, we find that this ratio sheds light on increasing resource utilization while still guaranteeing QoS. Analysis, simulation, and numerical results have shown that the TAP algorithm is simple and efficient.

The key to the success of the next generation IP networks to provide good services relies on the deployment of high performance routers to do fast IP routing lookups. In this paper, we propose a new algorithm for fast IP lookups using a so-called two-trie structure. The two-trie structure provides the advantages in that less memory space is required for representing a routing table than the standard trie while it still provides fast IP lookups. Based on the simulation result, the memory space can be saved around 27% over the standard trie while a lookup operation takes 1.6 memory accesses in the average case and 8 memory accesses in the worst case. Also, the structure is not based on any assumptions about the distribution of the prefix lengths in routing tables. Thus, increasing the lengths from 32 to 128 bit (from IPv4 to IPv6) does not affect the main structure.

The implementation of packet-fair queuing (PFQ) schedulers, which aim at approximating the generalized processor sharing (GPS) policy, is a central issue for providing multimedia services with various quality-of-service (QoS) requirements in packet-switching networks. In the PFQ scheduler, packets are usually time stamped with a value based on some algorithm and are transmitted with an increasing order of the time-stamp values. One of the most challenging issues is to search for the smallest time-stamp value among hundreds of thousands of sessions. In this paper, we propose a novel RAM-based searching engine (RSE) to speed up the searching process by using the concept of hierarchical searching with a tree data structure. The time for searching the smallest time stamp is independent of the number of sessions in the system and is only bounded by the memory accesses needed. The RSE can be implemented with commercial memory and field programmable gate array (FPGA) chips in a cost-effective manner. With the extension of the RSE, we propose a two-dimensional (2-D) RSE architecture to implement a general shaper-scheduler. Other challenging issues, such as time-stamp overflow and aging, are also addressed in the paper.

Meeting quality of service (QoS) requirements for various services in ATM networks has been very challenging to network designers. Various control techniques at either the call or cell level have been proposed. In this paper, we deal with cell transmission scheduling and discarding at the output buffers of an ATM switch. We propose a generalized priority queue manager (GPQM) that uses per-virtual-connection queueing to support multiple QoS requirements and achieve fairness in both cell transmission and discarding. It achieves the ultimate goal of guaranteeing the QoS requirement for each connection. The GPQM adopts the earliest due date (EDD) and self-clocked fair queueing (SCFQ) schemes for scheduling cell transmission and a new self-calibrating pushout (SCP) scheme for discarding cells. The GPQM's performance in cell loss rate and delay is presented. An implementation architecture for the GPQM is also proposed, which is facilitated by a new VLSI chip called the priority content-addressable memory (PCAM) chip.

Describes a new architecture for a multicast ATM switch scalable from a few tens to a few thousands of input ports. The switch, called the Abacus switch, has a nonblocking switch fabric followed by small switch modules at the output ports. It has buffers at input and output ports. Cell replication, cell routing, output contention resolution, and cell addressing are all performed in a distributed way so that it can be scaled up to thousands of input and output ports. A novel algorithm has been proposed to resolve output port contention while achieving input buffers sharing, fairness among the input ports, and call splitting for multicasting. The channel-grouping mechanism is also adopted in the switch to reduce the hardware complexity and improve the switch's throughput, while the cell sequence integrity is preserved. The switch can also handle multiple priority traffic by routing cells according to their priority levels. The performance study of the Abacus switch in throughput, average cell delay, and cell loss rate is presented. A key ASIC chip for building the Abacus switch, called the ARC (ATM routing and concentration) chip, contains a two-dimensional array (32/spl times/32) of switch elements that are arranged in a crossbar structure. It provides the flexibility of configuring the chip into different group sizes to accommodate different ATM switch sizes. The ARC chip has been designed and fabricated using 0.8 /spl mu/m CMOS technology and tested to operate correctly at 240 MHz.

Proposes and analyzes a recursive modular architecture for implementing a large-scale multicast output buffered ATM switch (MOBAS). A multicast knockout principle, an extension of the generalized knockout principle, is applied in constructing the MOBAS in order to reduce the hardware complexity (e.g., the number of switch elements and interconnection wires) by almost one order of magnitude. In the proposed switch architecture, four major functions of designing a multicast switch: cell replication, cell routing, cell contention resolution, and cell addressing, are all performed distributively so that a large switch size is achievable. The architecture of the MOBAS has a regular and uniform structure and, thus, has the advantages of: (1) easy expansion due to the modular structure, (2) high integration density for VLSI implementation, (3) relaxed synchronization for data and clock signals, and (4) building the center switch fabric (i.e., the multicast grouping network) with a single type of chip. A two-stage structure of the multicast output buffered ATM switch (MOBAS) is described. The performance of the switch fabric in cell loss probability is analyzed, and the numerical results are shown. The authors show that a switch designed to meet the performance requirement for unicast calls will also satisfy multicast calls' performance. A 16/spl times/16 ATM crosspoint switch chip based on the proposed architecture has been implemented using CMOS 2-/spl mu/m technology and tested to operate correctly.>

The asynchronous transfer mode (ATM) technique has been widely accepted as a flexible and effective scheme to transport various traffic over the future broadband network. To fully utilize network resources while still providing satisfactory quality of service (QOS) to all network users, prioritizing the user's traffic according to their service requirements becomes necessary. During call setup or service provisioning, each service can be assigned a service class determined by a delay priority and a loss priority. A queue manager in ATM network nodes will schedule ATM cells departing and discarding sequence based on their delay and loss priorities. Most queue management schemes proposed so far only consider either one of these two priority types. The queue manager handles multiple delay and loss priorities simultaneously. Moreover, a cell discarding strategy, called push-out, that allows the buffer to be completely shared by all service classes, has been adopted in the queue manager. We propose a practical architecture to implement the queue manager by using available VLSI sequencer chips.

This paper develops a queueing model of a buffer that collects cells for reassembly into packets for a protocol layer above the asynchronous transfer mode (ATM) layer. Whenever the buffer fills with all packets incomplete, a packet must be sacrificed to make room for others. The queueing model estimates the equilibrium fraction of packets sacrificed under one algorithm for selecting the packet to be sacrificed. The paper also uses simulation to compare three sacrifice algorithms. The model's predicted packet loss probabilities bound from above the loss probabilities in the simulations of the different algorithms. Applications to sizing the buffer for a prescribed loss probability are given.

In the paper, the fault detection, fault location, and reconfiguration schemes for a large-scale multicast output buffered ATM switch (MOBAS) are proposed. The architecture of the MOBAS has a regular and uniform structure and, thus, has the advantages of: (1) easy expansion due to the modular structure, (2) high integration density for VLSI implementation, (3) relaxed synchronization for data and clock signals, and (4) building the center switch fabric with a single type of chip. It is difficult to achieve fault tolerance in binary self-routing networks without adding additional switching planes, stages, or switching elements in order to have multiple paths due to their characteristics of a unique routing path between any input and output pair. However, since the MOBAS intrinsically has multiple paths between any input and output, it is inherently robust for faults without need to add any additional switching elements. The fault-tolerance of the MOBAS is shown through the performance analysis of the MOBAS under various fault conditions.>

Chao and Choe (1993) proposed a recursive modular architecture for implementing a large-scale multicast output buffered ATM switch (MOBAS). Four major functions of designing a multicast switch: cell replication, cell routing, cell contention resolution, and cell addressing, are all performed distributedly in the MOBAS, which allows the switch to grow. The architecture of the MOBAS has a regular and uniform structure and, thus, has the advantages of: (1) easy expansion due to the modular structure, (2) high integration density for VLSI implementation, (3) relaxed synchronization for data and clock signals, and (4) building the center switch fabric with a single type of chip. Multicast knockout principle, an extension of generalized knockout principle, is applied to construct the entire switch fabric so as to reduce the hardware complexity (e.g., the number of switch elements and interconnection wires) by almost one order of magnitude. In the present paper, the authors analyze a two-stage MOBAS in its cell loss rate and present some numerical results. They show that a switch that is designed, based on the multicast knockout principle, to meet the performance requirement for unicast calls will also satisfy the performance requirement for multicast calls.>

It is desirable to interconnect different computer hosts and local area networks (LANs) through the asynchronous transfer mode (ATM) network via broadband terminal adaptors (BTAs). The BTA must have a sufficiently large buffer, called a virtual channel queue (VCQ), to temporarily store multiple, partially received packets from different virtual channels. The buffer requirement of a shared-memory VCQ is studied for different packet loss probabilities and virtual channel numbers. Two different architectures for implementing the shared-memory VCQ are compared. The second architecture with multiple linked queues in the shared-memory requires less memory and has better scalability to accommodate a large number of virtual channels and is adopted in the analysis. Several possible error conditions, such as shared-memory overflow, the received packet exceeding its maximum length, and the corruption of the pointer in the logical queue, are discussed. Corresponding solutions are proposed in the VCQ designs.>

The authors develop a queuing model of a buffer that collects cells for reassembly into packets for a protocol layer above the asynchronous transfer mode (ATM) layer. Whenever the buffer fills with all packets incomplete, a packet must be sacrificed to make room for others. The queuing model estimates the equilibrium fraction of packets sacrificed. Applications to sizing the buffer for a prescribed loss probability are given.>

The asynchronous transfer mode (ATM) technique provides a standardized and flexible scheme to transport and switch traffic effectively for different services. To provide satisfactory quality of service (QOS) to all users on the network, it is necessary to control the user's traffic so that network resources can be efficiently and fairly utilized by all the users while still meeting the individual QOS requirement. In this paper, we propose to control the user's traffic at two places in the network: at the user-network interface (UNI) by a traffic shaper or a traffic enforcer, and at the network-node interface (NNI) by a traffic regulator and a traffic scheduler. The traffic shaper/enforcer adopted in our work contains a buffer to delay and shape the violating cells that do not comply with some agreed-upon traffic parameters. The traffic regulator regulates cells at each network node to avoid long bursts being formed which may increase the network congestion probability. A traffic scheduler that follows the traffic regulator schedules the cells' departure sequences based on their delay priorites. We have proposed a general, feasible architecture to implement the traffic shaper, regulator, and scheduler, at various places in the network. A key component, the Sequencer chip, which contains 150k CMOS transistors, has been implemented to realize the architecture.

The author presents four architecture designs for queue management in asynchronous transfer mode (ATM) networks and compares their implementation feasibility and hardware complexity. The author introduces the concept of assigning a departure sequence number to every cell in the queue so that the effect of long-burst traffic on other cells is avoided. A novel architecture to implement the queue management is proposed. It applies the concepts of fully distributed and highly parallel processing to schedule the cells' sending or discarding sequence. To support the architecture, a VLSI chip (called Sequencer), which contains about 150 K CMOS transistors, has been designed in a regular structure such that the queue size and the number of priority levels can grow flexibly.>

The author proposes a recursive modular architecture for a very large scale asynchronous transfer mode (ATM) switch. By extending the concept of the original knockout switch, the cell filtering and contention resolution functions are distributed over many small switch elements, which are arranged in a crossbar structure. The output ports of a switch fabric are partitioned into a number of groups by a novel grouping network to permit sharing of the routing paths in the same group. This partitioning and sharing concept is applied recursively to construct the entire switch elements. The technique of channel grouping for trunk circuits can be incorporated in the proposed ATM switch to improve the cell loss/delay performance while the cells' sequences are retained. A prototype circuit for the key switch element has been designed, and it has been shown that more than 4000 of the switch elements can be integrated into a VLSI chip with existing CMOS 1- mu m technology.>

The authors describe the architecture of an experimental research prototype application specific integrated circuit (ASIC) designed to serve as a generic building block of the future broadband integrated services digital network (B-ISDN). The chip performs common asynchronous transfer mode (ATM) layer functions such as cell assembly and cell disassembly. A new media access control (MAC) protocol developed for a broadband customer premises network is also integrated in the chip. The chip interfaces to the B-ISDN through a synchronous optical network (SONET) synchronous transmission signal-3c (STS-3c) framer chip. The ATM layer chip has been designed using 1.2 mu m CMOS technology with a die area of 5.4*5.4 mm/sup 2/ and approximately 27000 transistors. Experimental results are described. At the user network interface, the chip can be used to implement broadband terminal adaptors and the network termination. At the broadband local exchange, the chip can be used in the implementation of ATM statistical multiplexers, ATM switch port controllers, etc.>

Dynamic time-division multiplexing (DTDM) is a flexible network transport technique capable of handling both continuous and bursty traffic effectively. By using three different multiplexing architectures in the network, DTDM permits graceful evolution of the existing circuit switching network into a flexible broadband packet communications network supporting integrated voice, data, and video traffic. The first multiplexing stage uses a packet assembler to multiplex different broadband services into a common DTDM-format serial bit stream. The second multiplexing stage uses a statistical packet multiplexer to concentrate network traffic for more efficient use of transmission facilities. The third multiplexing stage uses a synchronous time-division multiplexer for high-speed point-to-point transparent transmission. The multiplexer uses a simple tributary synchronization scheme based on positive and negative block justification, which combines the concept of controlled-slip and bit-stuffing techniques while maintaining information integrity. A generic CMOS LSI chip has been designed for use in the three-stage multiplexing system.>