A communication device includes a request receiving module and a response output module. The request receiving module receives a communication start request which is output from a given communication device and passes through a relay device. The response output module outputs a response to the communication start request to the given communication device through the relay device. The relay device outputs the response to the given communication device in preference to a notification indicating a connection rejection in arbitration processing, executed by the relay device, between information to be output from the relay device in case where the request receiving module receives the communication start request while communicating with a communication device other than the given communication device.