A relay device transmits a frame received from any of a plurality of external devices that are connected via a plurality of communication lines. The external device is connected to one of the communication lines and to another one of the communication lines by searching a relay information table for specifying a relay destination of the frame. In the relay information table, information for identifying a frame type is stored in association with relay destination identifying information for identifying a communication line serving as a relay destination of a frame. The relay information table is partitioned into a plurality of sub-tables in accordance with priority based on the type identifying information or the relay destination identifying information. The relay device searches the sub-tables in descending order of priority using the type identifying information contained in the frame received from the external device as a search key specifying the relay destination.