A relay device includes: an input buffer for receiving data units, each of which includes a header, to which multiple pieces of destination information have been added, and data associated with the header; multiple virtual channels for storing data units, each of the multiple virtual channels storing a data unit in accordance with the destination information; a destination comparing section for determining the order of allocation of virtual channels at a relay device on the receiving end with respect to the data units that are stored on the multiple virtual channels by seeing if their destinations are the same; and an output section for outputting the stored data units preferentially through one of the virtual channels that has already allocated at the relay device on the receiving end.