One aspect of the present disclosure relates to a relay device communicating with a plurality of control devices that belong to on-vehicle networks. This relay device is provided with: a storage unit configured to store therein a plurality of update programs for simultaneous update required for the plurality of control devices, and topologies of the on-vehicle networks; an in-vehicle communication unit configured to transmit the plurality of update programs to the corresponding control devices, respectively; and a control unit configured to control the in-vehicle communication unit such that, as for control devices that belong to a plurality of on-vehicle networks that are individually connected to the relay device and are independent from each other, the plurality of update programs corresponding to the control devices are transmitted in parallel with each other.