Current congestion control algorithms ignore the application-layer delay, where the untransmitted data waiting at source nodes degrades the delay performance of services. Moreover, differentiated priorities are necessary for the application services with various delay requirements, especially for mission-critical services. Different from the existing works only considering the network delay, in this paper, by adding the flow queueing delay at source nodes, we formulate the network utility maximization (NUM) problem with additional deterministic service delay constraints. We propose a general TCP-based two-timescale congestion window control (TCWC) framework with delay-aware priority to enhance traditional algorithms. Specifically, to handle the obstacle of new delay constraints, we transform them to the time-average stability of virtual queues. By solving the new NUM problem via Lyapunov optimization, we design a short-term congestion window adjustment strategy in each time slot. To further guarantee the service delay, we apply extreme value theory (EVT) to evaluate the priorities of different flows, and determine the long-term control of window update rates. We deploy the proposed framework in three classic algorithms including NewReno, Vegas and DCTCP. In addition, simulation results show that our TCWC framework can significantly reduce the average service delay and provide deterministic guarantees compared with time-aware TCP congestion control algorithms such as TIMELY and BBRv2.

To ensure fair bandwidth allocation for diverse application flows from data centers, effective bandwidth management in switches is critical. Modern switches often adopt shared memory architectures to enhance efficiency. Fair queuing mechanisms can achieve fair bandwidth allocation in switches. However, the state-of-the-art fair queuing mechanisms in shared memory switches suffer from excessive packet drops, leading to suboptimal network utilization. In this paper, we propose Dynamic Fair Queuing (DFQ), a novel mechanism that leverages a limited number of priority queues to achieve both high network utilization and fair bandwidth allocation. DFQ is based on two key novel ideas. First, DFQ presents dynamic admission thresholds to manage packet enqueuing by monitoring the accumulated arrived packet bits and the remaining buffer of the queues in real time. Second, DFQ employs queue splitting and merging to maximize the utilization of the shared memory pool while guaranteeing fairness. Simulation results demonstrate that DFQ significantly improves throughput, fairness, and network utilization, while reducing flow completion time by up to 44.1%.

In data center networks, cross-host collective communications (CC) for LLM training often suffer from ECMP's hash-based randomness which funnels flows onto overlapping spine-leaf links, creating hotspots, rank stragglers, and degraded CC efficiency. A promising yet underexplored approach is to plan cross-host paths ahead during CC initialization. This leverages host-side steering, exploiting ECMP hash linearity via lightweight packet-header modification. Assigning cross-host paths to minimize link overlap and balance load is NP-complete for large-scale networks. To address this, we propose PathPlanner, a centralized service that heuristically selects near-optimal paths with minimal spine-leaf overlaps, generates multiple valid source ports via the host-side steering, and distributes them to workers. By cycling through these ports, each flow traverses the intended path without modifying software logics. High-fidelity SimAI simulations with realistic LLM workloads demonstrate that PathPlanner significantly reduces link overlap and straggler effects, cutting CC primitive flow completion times by up to 44.7 % and execution times by up to 21.35 %. In 32-rank Mixtral training, it shortens per-iteration runtimes by 1.6–2.1s, yielding estimated cumulative savings of 2.65-3.52 days over a complete training run.

The parameter size of modern large language models (LLMs) can be scaled up to the trillion-level via the sparsely-activated Mixture-of-Experts (MoE) technique to avoid excessive increase of the computational costs. To further improve training efficiency, pipelining computation and communication has become a promising solution for distributed MoE training. However, existing work primarily focuses on scheduling tasks within the MoE layer, such as expert computing and all-to-all (A2A) communication, while neglecting other key operations including multi-head attention (MHA) computing, gating, and all-reduce communication. In this paper, we propose FlowMoE, a scalable framework for scheduling multi-type task pipelines. First, FlowMoE constructs a unified pipeline to consistently scheduling MHA computing, gating, expert computing, and A2A communication. Second, FlowMoE introduces a tensor chunk-based priority scheduling mechanism to overlap the all-reduce communication with all computing tasks. We implement FlowMoE as an adaptive and generic framework atop PyTorch. Extensive experiments with 675 typical MoE layers and four real-world MoE models across two GPU clusters demonstrate that our proposed FlowMoE framework outperforms state-of-the-art MoE training frameworks, reducing training time by14%-57%, energy consumption by 10%-39%, and memory usage by 7%-32%. FlowMoE’s code is anonymously available at https://anonymous.4open.science/r/FlowMoE.

Deterministic demand of mission-critical applications is essential in edge computing systems for realizing Industry 4.0. However, the conventional average-based network slicing schemes incur unexpected long-tail delay, resulting in the failure to meet strict deterministic delay guarantee. To resolve this issue, in this paper, we construct a two-scale TNS-Net architecture for the URLLC slice under the network slicing paradigm, aiming to meet deterministic end-to-end (E2E) delay requirements of multiple users with minimal resource usage. We consider multi-access edge computing (MEC) and model it as a many-to-one cascade queue, which includes the offloading queues at the user equipments (UEs) and a computation queue at the server. To analyze the delay performance, we decompose the offloading process into transmission and vacation periods, and employ the weighted approximation to address the multi-UE coupling in the computation process to derive the closed-form approximate E2E delay distribution. Based on the derived delay distribution, we propose an iterative two-scale network slicing (TNS) algorithm to guarantee deterministic delay, and construct a TNS-based deep-unfolding neural network, called TNS-Net, to improve the solution in presence of inaccurate channel statistics. Moreover, for the training of TNS-Net with deterministic delay as the network input, we apply extreme value theory (EVT) to analyze the distribution characteristic of delay bound violation. Finally, simulation results demonstrate that our theoretical analysis provides a relatively accurate estimate and the proposed TNS-Net ensures better delay guarantee with lower resource consumption.

Split Federated Learning (SFL) improves scalability of Split Learning (SL) by enabling parallel computing of the learning tasks on multiple clients. However, state-of-the-art SFL schemes neglect the effects of heterogeneity in the clients’ computation and communication performance as well as the computation time for the tasks offloaded to the cloud server. In this paper, we propose a fine-grained parallelization framework, called PipeSFL, to accelerate SFL on heterogeneous clients. PipeSFL is based on two key novel ideas. First, we design a server-side priority scheduling mechanism to minimize per-iteration time. Second, we propose a hybrid training mode to reduce per-round time, which employs asynchronous training within rounds and synchronous training between rounds. We theoretically prove the optimality of the proposed priority scheduling mechanism within one round and analyze the total time per round for PipeSFL, SFL and SL. We implement PipeSFL on PyTorch. Extensive experiments on seven 64-client clusters with different heterogeneity demonstrate that at training speed, PipeSFL achieves up to 1.65x and 1.93x speedup compared to EPSL and SFL, respectively. At energy consumption, PipeSFL saves up to 30.8% and 43.4% of the energy consumed within each training round compared to EPSL and SFL, respectively.

The increasing size of datasets and model parameters has led to the widespread adoption of distributed machine learning (DML). However, the communication costs of DML tasks are significantly impacted by the routing mechanisms in data center networks (DCNs). Existing routing schemes towards DCNs cannot provide performance guarantees for the dynamic flows in DML tasks, while specialized optimal routing designs for DML tasks have limitations on the node assignments. In this work, We propose a CoTA (Core-based Task Aware) mechanism for DML tasks that decouples node assignments from routing decisions, with near-optimal performance guarantees. To optimize routing for communication traffic in DML, we develop a mathematical model to obtain the optimal results for arbitrary node allocation. Based on the optimization problem, we design a 2-approximation algorithm using the Minimum Flows Priority (MFP) greedy strategy. Simulation results by NS-3 verify the performance bound of CoTA across Leaf-Spine networks of varying sizes with different DML workloads. It is shown that CoTA achieves near-optimal performance for arbitrary node assignments, outperforming existing representative mechanisms.

Deterministic Networking (DetNet) aims to provide an end-to-end ultra-reliable data network with ultra-low latency and jitter. However, implementing DetNet in wireless networks, particularly in the air interface, still faces the challenge of guaranteeing bounded delay. This paper proposes a delay-guaranteed three-layer scheduling framework for DetNet, named Deterministic Guarantee Scheduling (DGS). The top layer calculates the amount of new data entering the queue in each scheduling period and timestamps the data to track its arrival time. Based on the remaining waiting time of each flow’s data volume, the middle layer proposes a scheduling algorithm based on urgency, prioritizing the scheduling of data volumes with the shortest remaining queuing time. The lower layer fine-tunes the scheduling results obtained by the middle layer for actual transmission. We implemented the DGS framework on the 5G-air-simulator platform. Simulation results demonstrate that DGS outperforms all other mechanisms by guaranteeing delay for a larger number of deterministic flows and achieving better throughput performance.

Optical interconnect can achieve a substantial increase in the number of nodes and switching capability for data centers, by virtue of their low power consumption and high bandwidth. In this paper, we propose a single-wavelength switch architecture based on two-stage AWGR for data centers. Then the single-wavelength design is extended to support multi-wavelength, which has higher scalability but lower hardware complexity and power consumption. We prove that the single wavelength architecture is internal strictly non-blocking. When the incoming traffic is externally blocked, a buffer allocation algorithm is designed to allocate feedforward and feedback FDL for the blocked packets. Based on the simulation results, the proposed switch can provide higher throughput, lower average latency, and a 0 out-of-order ratio compared to existing solutions.

The communication bottleneck severely constrains the scalability of distributed deep learning, and efficient communication scheduling accelerates distributed DNN training by overlapping computation and communication tasks. However, existing approaches based on tensor partitioning are not efficient and suffer from two challenges: 1) the fixed number of tensor blocks transferred in parallel can not necessarily minimize the communication overheads; 2) although the scheduling order that preferentially transmits tensor blocks close to the input layer can start forward propagation in the next iteration earlier, the shortest per-iteration time is not obtained. In this paper, we propose an efficient communication framework called US-Byte. It can schedule unequal-sized tensor blocks in a near-optimal order to minimize the training time. We build the mathematical model of US-Byte by two phases: 1) the overlap of gradient communication and backward propagation, and 2) the overlap of gradient communication and forward propagation. We theoretically derive the optimal solution for the second phase and efficiently solve the first phase with a low-complexity algorithm. We implement the US-Byte architecture on PyTorch framework. Extensive experiments on two different 8-node GPU clusters demonstrate that US-Byte can achieve up to 1.26x and 1.56x speedup compared to ByteScheduler and WFBP, respectively. We further exploit simulations of 128 GPUs to verify the potential scaling performance of US-Byte. Simulation results show that US-Byte can achieve up to 1.69x speedup compared to the state-of-the-art communication framework.

The Dijkstra algorithm has been widely used in the routing protocol design. However, the shortest path tree calculation method based on the Dijkstra algorithm fails to take advantage of the characteristics of the graph structure in topologies of satellite networks and incurs a heavy computational burden. In this paper, we propose a low-complexity and efficient algorithm for satellite routing according to the special topology and link latency distribution of LEO satellite constellations. The simulation results show that the proposed scheme achieves the same optimal performance as the Dijkstra algorithm but with much-reduced complexity. In particular, under the network scale of 60×30, the average calculation time of our algorithm is less than $\frac{1}{{10}}$ of that of the Dijkstra algorithm.

In this paper, we propose a bufferless data center network architecture (CycleDCN). CycleDCN is implemented as three-stage Clos network with arrayed wavelength grating routers (AWGRs) and tunable wavelength converters (TWCs) as the core device. Multi-wavelength routing and multi-stage structure make the routing problem of CycleDCN more complex. Based on the unique topology of CycleDCN, we propose two methods for route scheduling and wavelength assignment. One is based on integer linear programming, and the other is the heuristic algorithm based on the wavelength contention probability of each flow, which is called low contention probability first (LCF). With a centralized controller and either of the above methods, the proposed DCN architecture can achieve high scalability, high throughput, and low latency without using any optical buffer. The simulation results show that our proposed architecture can achieve about 83% throughput and less than 200ns latency at full load while accommodating thousands of ToR connections.

With the rapid development of internet applications such as cloud computing and streaming media, people put higher demands on data center (DC) switching capabilities. Technology limitations of the backplane cause bottlenecks in its performance, which limits the growth rate of the communication ability of DC. The technology of waveguides based on polymer materials and waveguide connectors on the backplane has become an essential issue in the last few years. Architectures of optical interconnection remain to be explored. We propose a strictly non-blocking Clos-based optical architecture, which uses densely integrated optical waveguides to connect optical chips and achieve on-board networking. In addition, we design a Ring-Clos architecture to reduce the packet loss rate. The simulation results indicate that our design has good performance on throughput, packet loss rate, and latency.

In distributed training, workers collaboratively refine the global model parameters by pushing their updates to the Parameter Server and pulling fresher parameters for the next iteration. This introduces high communication costs for training at scale, and incurs unproductive waiting time for workers. To minimize the waiting time, existing approachesoverlap communication and computationfor deep neural networks. Yet, these techniques not only require the layer-by-layer model structures, but also need significant efforts in runtime profiling and hyperparameter tuning. To make the overlapping optimizationsimpleandgeneric, in this article, we propose a new Parameter Server framework. Our solutiondecouplesthe dependency between push and pull operations, and allows workers toeagerlypull the global parameters. This way, both push and pull operations can be easily overlapped with computations. Besides, the overlapping manner offers a different way to address the straggler problem, where the stale updates greatly retard the training process. In the new framework, with adequate information available to workers, they can explicitly modulate the learning rates for their updates. Thus, the global parameters can be less compromised by stale updates. We implement a prototype system in PyTorch and demonstrate its effectiveness on both CPU/GPU clusters. Experimental results show that our prototype saves up to 54% less time for each iteration and up to 37% fewer iterations for model convergence, achieving up to 2.86× speedup over widely-used synchronization schemes.

Data parallelism (DP) is most widely used among all the parallel methods in largescale network training but the speedup from leveraging DP begins to scale poorly as the number of devices in data parallel training grows. Therefore, model parallelism (MP) is needed for further accelerating. In this paper, an integer linear programming based tool, NetPlacer, is proposed to find optimal operation-to-device placement. Unlike existing methods using time estimation, NetPlacer discards estimating simulated execution time and uses strict memory and computing balancing constraints on the network to find a scheme with a balance between memory and computation on different devices. As far as we know, we are the first to use equipment equalization as a target for model parallel strategy optimization. A speedup of at least 20% is achieved through NetPlacer for Inception-V3 on a 2-GPU machine compared to what one single GPU alone can achieve.

The problem discussed and solved in this paper is the multi-objective routing problem for Deterministic Network. The technical requirements of resource allocation in the Deterministic Network implementation technology require us to reserve corresponding resources for deterministic flows to be transmitted in the network, which introduces a new constraint of bandwidth competition, making the existing multi-objective routing schemes unable to provide effective solutions. In order to solve this problem, we firstly establish a mathematical model and solve it with optimization methods. Then we propose a multi-objective routing scheme based on genetic algorithm. On the basis of satisfying delay and bandwidth constraints, good results are obtained. In order to test the scalability of the scheme, it was tested in network after adding packet loss constraint and the network of larger scales, which all achieved good results. By comparing the performance of our scheme with that of mathematical modeling optimization, it is found that our scheme has a significant and substantial improvement in efficiency at the cost of relaxing constraints. It is concluded that the multi-objective routing scheme based on genetic algorithm proposed in this paper is an effective scheme to solve the multi-objective problem for Deterministic Network.

The switching capability required by data centers is rapidly developing, however, the technical limitations of the optical devices have created bottlenecks in their performance. Additionally, architectures that support thousands of servers remain to be explored. With a distributed control, we present a high-radix architecture that exploits the space domain and the wavelength domain to provide high throughput, achieving fast configuration and low latency. Considering the network size, we also propose two methods for implementation. We firstly form a strictly non-blocking network under the constraint of one connection per port. To scale up the switch, wavelength division multiplexing (WDM) is utilized to interconnect more servers and achieve higher bandwidth. The simulation results indicate that the proposed architecture can scale over thirty thousand servers with throughput reaching 87% while providing low latency.

Load balance is an important issue in datacenter networks. The flowlet-based algorithms can balance the traffic with fine granularity and does not suffer the packet mis-sequencing problem. But their performances are rather limited or require extra communication overhead. In this paper, we propose a local load-aware algorithm called Dynamic Roulette Wheel (DRW). In DRW, the roulette wheel is adopted to select a new path for the flowlet according to the local load. Each source of multipath balances the traffic to all its egress links without the communication overhead. Moreover, the granularity of flowlet can be dynamically tuned from a single packet to the whole flow. Finally, the Capacity Aggregation (CA) mechanism is designed for the case of link or switch failure. We prove in theory that DRW can achieve the optimal global load balancing. The simulation results also show that DRW provides almost the best delay performance and the least packet out-of-order proportion overall among all existing flowlet switching algorithms.

Multipath networks are widely used in data centers and load balancing is one of the most important technologies to improve their performances. Due to the ever-increasing in data center network size, existing load balancing algorithms face the challenges of efficiency and scalability. In this paper, we propose a new load balancing algorithm for large-scale, multi-tier fat-tree based data center networks. Different from the conventional architectures, a multi-tier fat-tree is divided into multiple routing domains according to the topology, and the routing processes in different domains are independent. The devices outside a routing domain can only access the specific interfaces provided by this domain. It is thus very convenient for deployment and modular upgrade. We also design a distributed and data-driven feedback mechanism, with which the routing decision is based on the global load information. We prove that the new algorithm can achieve perfect load balancing in multipath networks and show that the new algorithm outperforms all other load balancing algorithms in performance.

Mobile Ad-hoc Network (MANET) is a self-configuring network that is widely used but vulnerable to the malicious jammers in practice. In this paper, we consider a jamming channel problem in MANET where a jammer intermittently interrupts the communication channels and the transmitter needs to determine which time slot to send data in order to avoid the interruption. Learning from the historical experience, a Deep Q-Network (DQN) based approach is proposed to generate transmission decisions at the transmitter. In addition, a variant of DQN, termed adaptive DQN, is introduced to cope with the change of jamming conditions. The simulation results demonstrate that the proposed scheme can learn an optimal policy to guide the transmitter to avoid jamming more quickly and efficiently than a Q-learning baseline. Moreover, the effectiveness and robustness of the adaptive DQN is also numerically verified.

The emerging cloud applications require group communications. For these applications, multicast is a better choice than unicast, because it can significantly improve the performance by eliminating the duplicated packets generated by servers. However, existing multicast schemes for datacenters are either based on IP multicast or centralized scheduling. IP multicast is inefficient for datacenters as it cannot take full advantage of the multipath property. And centralized schemes suffer from single-point failure and scalability problems. To solve these problems, we propose MiniForest, a distributed multicast framework for large-scale datacenter networks. It consists of new routing algorithms and a dynamic group management mechanism. A new address mapping solution is then designed for compatibility to existing upper-layer applications. Based on the mapping solution, we propose an efficient load balancing strategy, with which a minimal forest is constructed for all multicast trees. To study the performance of the new multicast scheme in theory, we further provide an analytical model for Clos-based datacenter networks and analyze the overloading behaviors from a new perspective. We show that the distributed scheme can be used in any size of datacenters. It has much lower complexity and better performance than centralized schemes.

In fat-tree data center networks, routing a packet from its source to destination includes two phases, upstream (i.e. from source to watershed switch) and downstream (i.e. from watershed switch to destination). The throughput/non-blocking performance of networks hinges much on the effects of two phases above. In this paper, we propose a new routing algorithm called Global Round Robin (GRR) for fat-tree data center networks. In the upstream of GRR, each packet is sent to a toppest switch based on the GRR relationship between its source and toppest switches. Then the packet can arrive at a toppest switch in a single time slot without any blocking and buffering en route. In the downstream of GRR, the packet is routed to its destination using self-routing. The simulation results show that GRR provides the best delay/throughput performance among the existing routing algorithms for data center networks.

Multicast becomes essential in data center networks, since more and more applications require group communication. The existing multicast scheduling algorithms in data center are Internet-based or centralized, which are either not efficient or not scalable. In this paper, we propose a Distributed and Dynamic Multicast (DDM) solution for fat-tree data center networks. It includes multicast initialization, routing algorithm and load-balancing policy. As DDM does not need the central controller, it is more scalable and much simpler. Moreover, each host can dynamically join in or quit from an existing multicast group without suspending the live traffic in this group. Our simulation results show that DDM provides the better delay/throughput performance than the existing centralized multicast scheduling algorithm.

An efficient iterative scheduling algorithm for input-queued switches, called round robin with longest queue first (RR/LQF), is proposed in this paper. RR/LQF consists of three phases: report, grant, and accept. In each phase, only a single-bit message per port is sent for reporting a packet arrival, granting an input for packet sending, or accepting a grant. In both the grant and accept phases, scheduling priority is given to the preferred input-output pairs first and the longest virtual output queuing (VOQ) next. The notion of the preferred input-output pair is to keep a global RR schedule among all the inputs and the outputs. By serving the preferred input-output pairs first, the match size tends to be maximized. By serving the longest VOQ next, the match weight is also boosted. When RR/LQF is executed for a single iteration (i.e., RR/LQF-1), we show by simulations that RR/LQF-1 outperforms all the existing single-bit-single-iteration scheduling algorithms. When RR/LQF is executed up to N iterations (i.e., RR/LQF-N), we prove that under any admissible traffic pattern, RR/LQF-N is stable with a speedup of 2-1/N, where N is the switch size. To the best of our knowledge, this is the first work showing that an iterative scheduling algorithm is stable with a speedup less than 2. We then generalize RR/LQF to become a class of algorithms that have the same speedup bound of 2-1/N. Efforts are then made to further reduce the implementation complexity of RR/LQF. To this end, the pipelined RR/LQF and RR/RR, a simpler variant of RR/LQF, are proposed.

An efficient iterative scheduling algorithm for input-queued switches, called Round Robin with Longest Queue First (RR/LQF), is proposed in this paper. RR/LQF only needs a single bit for request, grant and accept messages respectively. The scheduling priority is given to the preferred input/output pairs first. Each single-bit request is actually an indication of a new packet arrival at the specific VOQ. Based on them, each output keeps track of the size of N VOQs destined to it. In the granting phase, if the preferred input's VOQ is empty, an output port j grants the (non-preferred) input that has the longest VOQ (among N VOQs destined to output j). In the accepting phase, if the preferred VOQ is not empty, input port accepts it directly. Otherwise, an input port i accepts the grant received by the long VOQ (among input i). When RR/LQF is executed for a single iteration, we show that RR/LQF outperforms SRR [15] in all simulations conducted. When RR/LQF is executed (up to N iterations) until finding the maximal size matching in input-queued switches, we prove that RR/LQF is stable with a speedup of 2-1/N, where N is the switch size. To the best of our knowledge, this is the first work showing that an iterative scheduling algorithm for input-queued switches can achieve a speedup requirement less than 2. Though the improvement is just 1/N we successfully tighten the speedup bound.

The feedback-based two-stage switch is scalable as it is configured by a predetermined and periodic joint sequence of configurations [1]. Its major problem is that the average packet delay is high under light traffic load. In this paper, we improve the performance of feedback-based switch while still ensuring in-order packet delivery and close to 100% throughput. We first show that the different sequences of configurations may endow a feedback-based switch with different delay performance. We propose to devise a tailor-made sequence of configurations for the estimated traffic pattern. The optimal joint sequences that can produce the lowest average packet delay is formulated as an ILP (Integer Linear Programming) problem. The simulation results demonstrate that the optimal joint sequence can cut down the average packet delay up to 50%. Even under random uniform traffic, 14% performance improvement can be obtained. Last but not least, we also design a fast suboptimal algorithm for the practical implementation.

Two major challenges in designing high-speed multicast switches are the expensive multicast switch fabric and the highly complicated central scheduler. While the recent load-balanced switch architecture uses simple unicast switch fabric and does not require a central scheduler, it is only good at handling unicast traffic. In this paper, we extend an existing load-balanced switch called feedback-based two-stage switch to support multicast traffic. In particular, an efficient multicast scheduling algorithm (FTMS) is designed. With FTMS, head-of-line (HOL) packet blocking at each input port is eliminated by adopting “pointer” queues. To cut down queuing delay, packet replication is carried out at middle-stage ports. As compared with other multicast scheduling algorithms, simulation results show that our FTMS always provides the highest throughput.

The feedback-based two-stage switch does not require a central scheduler and can provide close to 100% throughput [3]. But the number of crosspoints required for the two stages of switch fabric is 2N2, and the average packet delay performance (even under light traffic load) is on the order of O(N) slots, where N is the switch size. To improve the performance of feedback-based two-stage switch when N is large, we adopt the Clos network for constructing a large switch from a set of smaller feedback-based switch modules. We call it a Clos-feedback switch. The potential problem of packet mis-sequencing is solved by using application-flow based load balancing. With recursive decomposition, a Clos network can degenerate into a Benes network. We show that for a Clos-feedback switch, the number of crosspoints required is reduced to 4N(2 log2N-1) and the average packet delay is cut down to O(log2N) slots.

A general approach of designing input-queued multicast switch is to employ multicast switch fabric, where packets can be replicated inside the switch fabric. As compared with unicast switch fabric, the achievable traffic rate region of a switch can be increased, but it is still less than the admissible traffic rate region. In other words, achieving 100% throughput for any admissible multicast traffic pattern is not possible. In this paper, we first revisit the fundamental problems faced by input-queued switch in supporting multicast traffic. We then argue that multicast switch fabric is not necessary if a load-balanced approach is followed. Accordingly, an existing load-balanced two-stage switch architecture [12], consisting of unicast switch fabrics, can be adopted to provide 100% throughput for any admissible multicast traffic pattern. Since the two-stage switch requires no speedup in both switch fabric and packet buffers, we consider it a two-stage input-queued switch. It can be seen that its implementation complexity is much lower than conventional (single-stage) input-queued multicast switches. As compared with the work in [12], our approach is more systematic and we propose a more effective load balancing mechanism.

Communication overhead should be minimized when designing iterative scheduling algorithms for input-queued packet switches. In general, the overall communication overhead is a function of the number of iterations required per time slot (M) and the data bits exchanged in an input-output pair per iteration (B). In this paper, we aim at maximizing switch throughput while minimizing communication overhead. We first propose a single-iteration scheduling algorithm called Highest Rank First (HRF). In HRF, the highest priority is given to the preferred input-output pair calculated in each local port at a RR (Round Robin) order. Only when the preferred VOQ(i,j) is empty, input i sends a request with a rank number r to each output. The request from a longer VOQ carries a smaller r. Higher scheduling priority is given to the request with a smaller r. To further cut down its communication overhead to 1 bit per request, we design HRF with Request Compression (HRF/RC). The basic idea is that we transmit a single bit code in request phase. Then r can be decoded at output ports from the current and historical codes received. The overall communication overhead for HRF/RC becomes 2 bits only, i.e. 1 bit in request phase and 1 bit in grant phase. We show that HRF/RC renders a much lower hardware cost than multi-iteration algorithms and a single-iteration algorithm π-RGA [11]. Compared with other iterative algorithms with the same communication overhead (i.e. SRR [10] and 1-iteration iSLIP [6]), simulation results show that HRF/RC always produces the best delay-throughput performance.

A hybrid electro-optic router is attractive, where packet buffering and table lookup are carried out in electrical domain and switching is done optically. In this paper, we propose a load-balanced optical switch (LBOS) fabric for a hybrid router. LBOS comprises N linecards connected by an N-wavelength WDM fiber ring. Each linecard i is configured to receive on channel λi. To send a packet, it can select and transmit on an idle channel based on where the packet goes. The packet remains in the optical domain all the way from an input linecard/port to an output linecard/port. Meanwhile, the loading in the ring network is perfectly balanced by spreading the packets for different destinations to use different wavelengths, and packets for the same destination to use different time slots. With the pipelined operation of the LBOS, we show that LBOS is an optical counterpart of an efficient load-balanced electronic switch, and close-to-100% throughput can be obtained. To address the ring-fairness problem under the inadmissible traffic patterns, an efficient throughput-fair scheduler for LBOS is also devised.

A framework for designing feedback-based scheduling algorithms is proposed for elegantly solving the notorious packet missequencing problem of a load-balanced switch. Unlike existing approaches, we show that the efforts made in load balancing and keeping packets in order can complement each other. Specifically, at each middle-stage port between the two switch fabrics of a load-balanced switch, only a single-packet buffer for each virtual output queueing (VOQ) is required. Although packets belonging to the same flow pass through different middle-stage VOQs, the delays they experience at different middle-stage ports will be identical. This is made possible by properly selecting and coordinating the two sequences of switch configurations to form a joint sequence with bothstaggered symmetry propertyandin-order packet delivery property. Based on the staggered symmetry property, an efficient feedback mechanism is designed to allow the right middle-stage port occupancy vector to be delivered to the right input port at the right time. As a result, the performance of load balancing as well as the switch throughput is significantly improved. We further extend this feedback mechanism to support the multicabinet implementation of a load-balanced switch, where the propagation delay between switch linecards and switch fabrics is nonnegligible. As compared to the existing load-balanced switch architectures and scheduling algorithms, our solutions impose a modest requirement on switch hardware, but consistently yield better delay-throughput performance. Last but not least, some extensions and refinements are made to address the scalability, implementation, and fairness issues of our solutions.

A novel feedback mechanism is proposed in this paper to enhance the performance of load-balanced two-stage switches. The key idea is to properly select and coordinate the two sequences of TV deterministic configurations used by the two stages of switch fabrics, thereby forming a joint sequence with bothstaggeredsymmetrypropertyandin-orderpacketdeliveryproperty. With a single-packet-buffer-per-middle-stage VOQ, a joint sequence with both properties is first constructed. Then based on it, an efficient feedback mechanism is designed to allow the right piece of middle-stage port occupancy information to be delivered to the right input port at the right time. In each time slot, an input selects a packet for sending based on its port-based scheduling algorithm. To this end, three simple port-based scheduling algorithms, RR, LQF and EDF, are also proposed. Simulation results show that with our proposed feedback mechanism, the three scheduling algorithms gives an unbeatable delay-throughput performance under various traffic conditions.

A novel feedback-based two-stage switch architecture is presented in for solving the packet mis-sequencing problem in designing two-stage switches. With this architecture, each middle- stage port j piggybacks an N-bit VOQ occupancy vector to an output port k in each time slot. As output k and input k reside on the same line-card, input k schedules a packet for sending in the next time slot based on the N-bit feedback. In this paper, we focus on designing efficient packet scheduling algorithms for cutting down the number of feedback bits required while minimizing the negative impact to switch performance. The basic idea is to partition N VOQs at a middle-stage port into M non-overlapped sets. In each time slot, only the queue occupancies of selected sets are sent. By exploiting the otherwise wasted bandwidth in the first-stage switch, each input port is also allowed to piggyback its VOQ status to middle-stage ports. This allows each middle-stage port to intelligently select the sets of VOQs for feedback. Extensive simulation results show that among our proposed scheduling algorithms, the set-feedback scheduler provides the best performance under various traffic conditions.