| As Internet traffic continues to double every year, the demands placed on the IP routers that deliver this traffic also increase. Traditional IP router architectures cannot scale to meet these demands, forcing architects to explore alternative designs. This thesis explores one alternative, the distributed router fabric. Distributed router fabrics are rooted in the interconnection networks used in supercomputers and their idea is simple: design the largest efficient router possible and then replicate and interconnect these routers to scale the fabric's switching capacity. This approach adopts the engineering advantages of interconnection networks, but also presents several challenges that are the focus of this thesis.; An important property of any IP router is the switching bandwidth it can provide to incoming traffic. As we show, this guaranteed line rate can be found for an arbitrary distributed fabric by solving a series of maximum-cost flow problems, significantly improving the characterization provided by previous approaches. Building on this result, we also show that maximizing the line-rate guarantee of a particular distributed fabric can be achieved by designing its routing algorithm. The optimal routing algorithm design problem can be cast as a convex program and, as a result, globally optimal routing algorithms can be efficiently determined for any fabric.; Once a packet's route through the fabric is determined, a flow-control method delivers that packet from source to destination. We show that existing fixed-size flits, or flow-control units, necessitate large control overheads and introduce variable-size flits to solve this problem. By carefully constraining amount of variation in our flit size, the hardware implementation is kept simple while overhead is greatly reduced. Long packets can also reduce the efficiency of flow control and we show that splitting these long packets into many shorter packets and then reassembling them provides higher fabric throughput. |
