In this paper we present the Segment router, a novel router design for the interconnection networks of massively parallel computers. The design decisions of the Segment router are motivated by the need to improve the network performance when the traffic consists of messages with widely different lengths. The key novelty of the Segment router is that it provides different queueing policies for the two classes of messages it services. Short messages are stored in a centralized, dynami- cally allocated queue that guarantees storage availability for the whole packet of the short message. Long messages on the other hand are stored in small FIFO buffers associated with the input channels of the router. Thus when a long message becomes blocked, it is stored in segments in the FIFO buffers of a number of routing elements in the network. Further- more, the physical channels of the Segment router are fairly multiplexed between the two supported classes of messages without the potential for starvation. Using simulations we compare the performance of our technique to the performance of multipacket messages and networks implementing lanes. The results clearly demon- strate the performance advantages of our technique.