A gateway device (100, 130) being configured to be connected to an internal network to which are connected one or more internal terminal devices, and being configured to be connected to an external network (120, 140) to which are connected a plurality of relay devices (101, 102, 131, 132) to each of which are connected one or more external terminal devices (111, 112), and having a connection relation table being configured to indicate, in each record, an external terminal device and a relay device to which the external terminal device is connected, the gateway device comprising: a table updating unit (4, 2) being configured to, each time a communication packet whose destination is any one of the external terminal devices is received from the internal network, being configured to refer to the connection relation table, and being configured to transmit by broadcasting or multicasting to the external network an investigation packet being configured to be used for investigating a relay device to which a destination external terminal device is connected when a record on the destination external terminal device of the communication packet does not exist in the connection relation table, being configured to receive from the relay device to which the destination external terminal device is connected a connection notification packet being configured to be used for notifying that the destination external terminal device is connected to the relay device, and being configured to update the connection relation table based on the connection notification packet received; a re-notification request unit being configured to, when the connection relation table is erased, transmit by broadcasting or multicasting to the external network a re-notification request packet being configured to be used for requesting the relay device that has transmitted the connection notification packet to re-notify of the external terminal device that has been notified in the connection notification packet; and a table restoration unit being configured to receive from the relay device that has transmitted the connection notification packet a re-notification response packet being configured to be used for re-notifying of the external terminal device that has been notified in the connection notification packet, and being configured to restore the connection relation table based on the re-notification response packet received. a table updating unit (4, 2) being configured to, each time a communication packet whose destination is any one of the external terminal devices is received from the internal network, being configured to refer to the connection relation table, and being configured to transmit by broadcasting or multicasting to the external network an investigation packet being configured to be used for investigating a relay device to which a destination external terminal device is connected when a record on the destination external terminal device of the communication packet does not exist in the connection relation table, being configured to receive from the relay device to which the destination external terminal device is connected a connection notification packet being configured to be used for notifying that the destination external terminal device is connected to the relay device, and being configured to update the connection relation table based on the connection notification packet received; a re-notification request unit being configured to, when the connection relation table is erased, transmit by broadcasting or multicasting to the external network a re-notification request packet being configured to be used for requesting the relay device that has transmitted the connection notification packet to re-notify of the external terminal device that has been notified in the connection notification packet; and a table restoration unit being configured to receive from the relay device that has transmitted the connection notification packet a re-notification response packet being configured to be used for re-notifying of the external terminal device that has been notified in the connection notification packet, and being configured to restore the connection relation table based on the re-notification response packet received.