Buffer management and fair scheduling for input queued switches

Switches play an important role in computer networks and input buffered switches are becoming popular because of their better scalability. The principal issues in input buffered switch design include buffer management and crossbar scheduling. A buffer management scheme specifies how an input buffer is organized, how the space is allocated to the messages and how the input block is connected to the crossbar. In this dissertation, we identify the choices for buffer management, develop a 3-D model of the switch design space and analyze the impact of three design parameters on switch performance: virtual circuit assignment, buffer allocation and intra-switch connectivity. Our studies suggest that a switch with dynamic virtual circuit allocation, full intra switch connection and combined buffer offers the best performance. We propose a novel circular buffer organization for such a switch that has less implementation complexity compared to the existing approaches.; Scheduling is more complicated for input buffered switches and most schemes in literature seek to achieve high overall throughput with hardly any regard to the issue of quality of service (QoS). In this dissertation, we present three fair scheduling schemes for singly connected switches, fully connected switches as well as switches with multicast capability. We show by simulation that the proposed schemes support fair bandwidth allocation among the message flows while maintaining high switching speed.; Decongestion policy is used to discard packets in the presence of buffer overflow. To support fair bandwidth allocation, it is crucial to determine which packets are permitted into the buffer, when to discard a packet and from which flow. This dissertation also evaluates four decongestion mechanisms and shows that fair scheduling alone cannot guarantee fair bandwidth distribution. Our results indicate that early packet discard in anticipation of congestion is necessary and per-flow based buffering is effective for protecting benign users from being adversely affected by misbehaved traffic. Buffer allocation according to bandwidth reservation is especially helpful when the input traffic is highly bursty.