There is provided a communication device including a score information storage unit to store score information indicating a score as an evaluated value of a communication path; a receiver unit to receive a route connection notice including current score information; a routing unit to acquire the score information stored in the score information storage unit, and select the communication path next to the communication path based on the acquired score information of the communication path; a score updating unit to add a score of the communication path selected by the routing unit to the current score of the partial communication route indicated by the current score information, and update the current score information to the added score as a new current score; and a transmission unit to transmit the route connection notice including the current score information.