An on-vehicle relay device that is connected to a first on-vehicle device and a second on-vehicle device via an on-vehicle network, and relays a message transmitted from the first on-vehicle device to the second on-vehicle device, includes a processor configured to receive a permission request for transmission of a first message from the first on-vehicle device, determine whether the total of the usage rate of the bandwidth of the on-vehicle network used by at least one message already permitted to be transmitted via the on-vehicle network, and the usage rate of the bandwidth of the on-vehicle network used by the first message is equal to or smaller than a predetermined threshold value, and send a reply that permits transmission of the first message, to the first on-vehicle device, when the sum is equal to or smaller than the predetermined threshold value.