A method is provided in one embodiment and includes receiving at a network element an encapsulated packet and determining whether both an ECMP/LAG Existing (“ele”) flag and an Entropy Label Capability (“elc”) flag are set for an egress node of the packet in a Label Distribution Protocol (“LDP”) database of the network element. If both the ele and elc flags are set for the egress node of the packet in the LDP database, the method further includes determining whether the network element is an ingress node for the packet and, if the network element is the ingress node for the packet, pushing an Entropy Label (“EL”) and an Entropy Label Indicator (“ELI”) onto an MPLS stack of the packet.