Upon receipt of a change request to change a path in a first communication and including a label assigned to a path after change and information of a transfer destination after change, a relay apparatus stores the label assigned to the path after change in association with the information of the transfer destination after change into a first storage unit. The relay apparatus then updates a second storage unit so as to change a first label assigned to a path before change in the first communication to the label assigned to the path after change. Upon determining that response messages for a request message transferred on the path before change have been received without omission with respect to the first communication, the relay apparatus deletes the first label assigned to the path before change and information of a transfer destination corresponding to the first label from the first storage unit.