An egress device of a network tunnel is configured to receive fragmented packets over a tunnel interface when the network tunnel is defined using information that is not present in all of the fragmented packets. For example, an egress device includes an interface to receive packets associated with the network tunnel, at least some of the packets being fragmented packets that are fragments of tunnel encapsulated packets. Some of the fragmented packets include network layer information associated with a network layer header of an original unfragmented tunnel encapsulated packet and do not include transport layer information associated with a transport layer header of the original unfragmented tunnel encapsulated packet. A forwarding engine of the egress device uses a multi-stage chained lookup to determine whether packets conform to tunnel definitions for the network tunnel that define the network tunnel by specifying both network layer information and transport layer information required for the packets.