Disclosed are techniques for determining a path maximum transmission unit (MTU) of a communication path connecting two or more nodes of a network. A node initiates a connection with a remote node by repeatedly transmitting increasingly-larger path MTU discovery messages until the size of a path MTU discovery message exceeds the link MTU of a link within the communication path. This results in the generation and transmission of an MTU error message back to the initiating node. The edge router linked to the initiating node generates a MTU change message in response to receiving the MTU error message and multicasts the MTU change message to all local nodes to which it is linked. The MTU change message directs the receiving nodes to update their destination caches to reflect the path MTU discovered through the use of the increasing-size path MTU discovery messages and the resulting MTU error message.