In a router, a receiver receives a communication packet meant for a communication destination other than this router device. A calculator calculates a cost value for forwarding a communication packet to a destination by each of neighboring routers adjacent to the router. A next-router determiner selects a neighboring router as a next router based on the cost value calculated to supply the determined information and the communication packet to a transmitter, which transmits the communication packet to the destination based on the determined information. The calculator calculates the cost value based on the node degree of the neighboring routers and the number of hops of the communication packet from the neighboring routers to the destination.