In one embodiment, a protocol option is implemented in which a network packet stores a maximum transmission unit size to use for sending data on a path between a sender and a recipient. The stored value is replaced if a receiver of the network packet uses a maximum transmission unit (MTU) smaller than the stored value. The option may be used in an initiation packet sent during a communication initiation handshake to allow both establishment of a communication session as well as determination of an efficient transmission unit size. The initiation packet may be sent with a do-not-fragment option set so that if a receiver does not understand the option, and the packet is too large for the receiver, then receiver will reject the packet and place the sender on notice that a conventional trial-and-error approach is required to determine an allowable MTU.