When the reply message reaches the source node, the relaxation pass is initiated by sending a relaxation message downstream to all destinations. When sent by a node to a successor , this message contains the cumulative delay after relaxation on all nodes on the path from the source to . During the relaxation pan, each node reduces the priorities assigned to each outgoing link, and thus increases the local delay on each link. The amount by which the priorities can be reduced on a node depends on the reduce for and the feasible delays on the successor nodes.
When a node receives a relaxation message, it calculates a target value, , for the local delay after relaxation for each outgoing link. This value is a fraction of the slack available for transmission in the subtree starting at Node after relaxation on upstream nodes. For each successor node , the value for the slack on the corresponding outgoing link is defined as
The target value for the local delay on that link is then determined by the next formula:
For each successor node , the lowest priority level on the outgoing link of is determined for which the local delay does not exceed . Let be the resulting delay. Node first finalizes the priority assignment and then forwards the relaxation message to each successor node with the updated value for the cumulative delay up to after relaxation, where
The formula 4 tries to distribute the available slack equally ones the nodes of the critical path of the subtree starting at node . In Chapter 4, we will investigate what the effects of varying this basic allocation scheme are. Specifically, we will generalize the scheme from using an equal distribution to using geometrical distribution, by introducing a relaxation factor . By choosing appropriate , the relaxed amount of delay is distributed as follows:
The formula in 4, therefore becomes
We note that for , the allocations are identical to the one defined in formula 4.