We describe qHTFair, a switch scheduler that supports classes of service for networks on chips. The scheduler extends the HTFair scheduler, which is an improved version of the HyperTransport scheduling protocol. qHTFair is intended for on-chip interconnects with a daisy chain topology. With our extension, the interconnect can be divided into several classes or channels, each with its own bandwidth allocation. Bandwidth allocations are defined as ratios of channel bandwidths. Ratios can have arbitrary values and be set up dynamically.

In this paper, we present a flexible network on-chip topology: NR-Mesh (Nearest neighbor Mesh). The topology gives an end node the choice to inject a message through different neighboring routers, thereby reducing hop count and saving latency. At the receiver side, a message may be delivered to the end node through different routers, thus reducing hop count further and increasing flexibility when routing messages. This flexibility allows for maximizing network components to be in switch off mode, thus enabling power aware routing algorithms. Additional benefits are reduced congestion/contention levels in the network, support for efficient broadcast operations, savings in power consumption, and partial fault-tolerance. Our second contribution is a power management technique for the adaptive routing. This technique turns router ports and their attached links on and off depending on traffic conditions. The power management technique is able to achieve significant power savings when there is low traffic in the network. We further compare the new topology with the 2D-Mesh, using either deterministic or adaptive routing. When compared with the 2D-Mesh using deterministic routing, executing real applications in a full system simulation platform, the NR-Mesh topology using adaptive routing is able to obtain significant savings, 7% of reduction in execution time and 75% in energy consumption at the network on average for a 16-Node CMP System. Similar numbers are achieved for a 32-Node CMP system.

Many papers on emulations of Generalized Processor Sharing (GPS) have been published. The algorithms and their implementations are often very complex and/or generate a bursty output. In this paper, we present a simple two-priority scheduler that can be easily implemented in hardware, making it especially interesting for Networks on Chips (NoCs), and other applications dealing with stringent resource constraints.

Previous work has proposed the Dynamic Switch Buffer Management (DSBM) scheme, a promising approach for improving the scalability of switch ingress memories. In this paper, we extend these results by adding increased backlog awareness into the latter. In particular, we propose using a novel combination of two backlog-aware algorithms: BA-DSBM to map incoming packets to the switch's ingress buffers and the Backlog-Aware Wrapped Wavefront Arbiter (BA-WWFA) to set the configuration of the switch fabric. We then simulate these algorithms under a variety of load intensities and types. These simulations suggest that adding backlog-awareness into the DSBM scheme leads to significant performance enhancements, particularly as the switch is "stressed" by asymmetric or heavy loading. Our algorithms, therefore, mitigate some of the design tradeoffs made in this novel, highly-scalable switch design.

To avoid head of line blocking in switches, virtual output queues (VOQs) are commonly used. However, the number of VOQs grows quadratically with the number of ports, making this approach impractical for large switches. In this paper, we propose dynamic switch buffer management (DSBM) to tackle this problem. Similar to DBBM, it saves memory by reducing the number of buffers. Our scheme significantly improves the performance by dynamically assigning the incoming cells to the least occupied buffers.

A novel architecture was proposed in [1] to address scalability issues in large, high speed packet switches. The architecture proposed in [1], namely OBIG (output buffers with input groups), distributes the switch fabric across multiple chips, which communicate via high speed interconnects enabled by proximity communication (PC), a recently developed circuit technology [2]. An OBIG switch aggregates multiple input flows inside the switch fabric, thereby significantly reducing the amount of memory required for internal buffers, vis-a-vis a conventional buffered crossbar, which has buffers at every crosspoint. Thus, the OBIG architecture is promising for realizing terabit switches with hundreds of ports. This paper studies packet scheduling algorithms which help realize the potential of OBIG-like switch architectures. The emphasis here is on designing backlog aware scheduling algorithms, while ensuring desirable traits such as low computational complexity and scalability. The efficacy of the proposed scheduling algorithms with respect to performance metrics such as average delay and fairness is demonstrated via simulations under a variety of scenarios.

We describe a novel way to implement high-radix crossbar switches. Our work is enabled by a new chip interconnect technology called proximity communication (PxC) that offers unparalleled chip IO density. First, we show how a crossbar architecture is topologically mapped onto a PxC-enabled multi-chip module (MCM). Then, we describe a first prototype implementation of a small-scale switch based on a PxC MCM. Finally, we present a performance analysis of two large-scale switch configurations with 288 ports and 1,728 ports, respectively, contrasting a 1-stage PxC-enabled switch and a multi-stage switch using conventional technology. Our simulation results show that (a) arbitration delays in a large 1-stage switch can be considerable, (b) multi-stage switches are extremely susceptible to saturation under non-uniform traffic, a problem that becomes worse for higher radices (1-stage switches, in contrast, are not affected by this problem).

Scheduling in large switches is challenging. Arbiters must operate at high rates to keep up with the high switching rates demanded by multi-gigabit-per-second link rates and short cells. Low-latency requirements of some applications also challenge the design of schedulers. In this paper, we propose the Parallel Wrapped Wave Front Arbiter with Fast Scheduler (PWWFA-FS). We analyze its performance, present simulation results, discuss its implementation, and show how this scheme can provide low latency under light load while scaling to large switches with multi-terabit-per-second throughput and hundreds of ports.

Large, fast switches require novel approaches to architecture and scheduling. In this paper, we propose theOutputBufferedSwitchwithInputGroups(OBIG). We present simulation results, discuss the implementation, and show how our architecture can be used to build single-stage (flat) switches with multi-terabit-per-second throughput and hundreds of ports.

Multicast is an efficient mechanism for delivering data to multiple receivers. However conventional multicast routing suffers from a linear scalability problem that impedes the deployment of IP multicast in the Internet. The number of forwarding states maintained in the network layer increases linearly with the number of existing multicast channels in the network. MPLS coexists with many existing network protocols and can provide scalability for how these protocols are used in today's networks. In this paper, we propose a new scalable multicast solution in MPLS networks to reduce the number of forwarding states in the network layer. In previously existing solutions, forwarding states are removed from non-branching routers on multicast trees and packets are label switched by MPLS LSPs in non-branching routers. Our new solution proposes a new algorithm for multicast tree construction and a new channel sharing scheme to further reduce the number of forwarding states in branching routers. Simulation results show that the new solution can achieve 85%-97% reduction in the number of multicast forwarding states in MPLS networks over network layer multicast schemes, and 45%-90% reduction over the existing MPLS multicast tree based multicast.

Multicast is a bandwidth efficient mechanism for delivering the same data to multiple receivers simultaneously. Layered multicast, which is suited for high-bandwidth multimedia traffic like video, may be used to differentiate between receivers of the same multimedia content based on their processing and bandwidth resources. To achieve fair bandwidth allocation in layered multicast, max-min fair allocation solutions have been proposed. However, existing solutions either use non-scalable centralized computation or require core routers to maintain per-session information. Maintaining per-session information in core routers violates the core stateless principle of DiffServ architecture, which is proposed as a scalable QoS solution in the Internet. In this paper, we propose a new scalable distributed max-min fair bandwidth allocation algorithm for DiffServ, which runs iteratively and does not maintain per-session information in core routers. The new algorithm is proved capable of achieving max-min fair bandwidth allocation. Through analysis, we show that the new algorithm complies with core stateless DiffiServ architecture to have O(1) storage complexity in core routers.

Networks are supposed to support multiple service categories that include real-time services and best-effort services. In both types of applications, it is important to differentiate between the requirements of different streams, and allow for an appropriate distribution of resources among them. Work-conserving disciplines may be implemented with the use of queue or scheduling calendars. Since calendars have finite resolutions, theoretical emission times that determine the positions of frames within the calendar slots have to be rounded to match the boundaries of the slots. The selection of a rounding method affects the performance of a work-conserving discipline. We present an efficient calendar structure and examine several rounding methods.

We investigate experimentally several routing algorithms for asynchronous deflection networks, i.e., ones that operate in an unslotted manner. We determine the impact of an extra input buffer space on the quality of routing decisions. Finally, we compare the performance of asynchronous and synchronous deflection networks.

Multicasting in deflection networks is more difficult than in store-and-forward networks, because of the difficulties in sending multiple copies of the same packet on several output ports. On the other hand, deflected packets stray from their optimal paths and may visit the multicast recipients "accidentally", not necessary in the order envisioned by the sender. We compare a number of simple multicast strategies for deflection networks based on a few simple rules and assumptions. In particular, we never buffer packets that cannot be relayed immediately.