One embodiment of the present invention provides a system for facilitating fragmentation of packets with hierarchically structured variable-length identifiers (HSVLIs). During operation, the system receives an interest packet with an HSVLI corresponding to a piece of content. The system then identifies a minimum path maximum transmission unit (MTU) value carried in the packet. In response to the piece of content not being stored locally, the system then determines an egress port for the packet based on the HSVLI. The system further determines an MTU associated with the egress port. Subsequently, in response to the MTU associated with the egress port being less than the minimum path MTU value carried in the packet, the system updates the minimum path MTU value in the packet to the MTU value associated with the egress port.