Systems and methods of propagating maximum segment size and path maximum transmission unit of network paths between an intermediary device of a cluster with a plurality of destinations are described. A first core of a node including multiple cores and intermediary to a client and a plurality of servers may receive a response to a packet transmitted to a destination indicating that the packet has a size greater than a MTU of a network path between the node and a destination. The first core identifies the MTU of the network path and determines that the identified MTU is different than an MTU used by the first core. The first core replaces the MTU stored in an entry corresponding to the destination in a PMTU table maintained with the identified MTU. The first core transmits, to other cores of the node, the identified MTU to update each core's PMTU table.