In general, techniques are described for performing a graceful restart for a computing network utilizing downstream on demand (DOD) label distribution. In one example, a method is provided that includes establishing a communication session for Label Distribution Protocol (LDP) that uses a downstream on demand label distribution mechanism for distributing labels. A first label mapping message is exchanged between two routers that defines at least a first label to be applied by an upstream router when forwarding one or more of the data packets to a destination. When the communication session fails, a forwarding state comprising the first label is preserved, and one or more data packets are forwarded based on the first label. The communication session is gracefully restarted. Once the communication session is reestablished, a second label mapping message is exchanged between the routers.