next up previous
Next: The Relaxation Pass Up: Three-Pass Establishment Protocol Previous: The Request Pass

The Reply Pass

If the admission test of the destination succeeds, the second pass - the reply pass - is initiated. During this pass, an establish accept message is forwarded from the destination upstream. As the message travels upstream, each node calculates the feasible delay of packets on that node. By the feasible delay tex2html_wrap_inline930 on Node tex2html_wrap_inline932 , we denote the maximum cumulative delay a packet can experience on nodes upstream without missing the end-to-end delay at the destination. In other words, a packet may miss its deadline at one or more destinations if it is delayed for more than tex2html_wrap_inline930 before arriving at Node tex2html_wrap_inline932 . The feasible delay on tex2html_wrap_inline932 is defined as follows:

  

where b denotes the number of successors of tex2html_wrap_inline944 .

As the establish accept packets generated at the destinations travel up the multicast tree, they carry with them the feasible delay of the last node they traversed. Each node tex2html_wrap_inline946 waits for the messages from all its successors tex2html_wrap_inline948 before determining the local feasible delay according to Equation 3, and forwards the message with the new value to the next node upstream. At each node tex2html_wrap_inline946 , the successor with the minimum value for its feasible delay determines the direction of the critical path for the subtree with node tex2html_wrap_inline946 as root. During the reply pass, every node is informed about the direction of the critical path by comparing the feasible delay values of incoming messages. Each node tex2html_wrap_inline946 informs the next node upstream about the length tex2html_wrap_inline956 of the critical path (in numbers of links) starting at tex2html_wrap_inline946 . In summary, upon receiving the establish message from all successor nodes, the message from successor tex2html_wrap_inline960 having the entries ( tex2html_wrap_inline962 ), the node tex2html_wrap_inline946 performs the following four steps.

  1. Determine the successor on the critical path, i.e., the node tex2html_wrap_inline966 with the minimum value tex2html_wrap_inline968 .
  2. Determine the local feasible delay tex2html_wrap_inline970 .
  3. Determine the length of the critical path starting at tex2html_wrap_inline946 , tex2html_wrap_inline974 + 1.
  4. Forward the establish request message with the updated entries ( tex2html_wrap_inline976 ) to the next node upstream.
For the example depicted in Figure 2, by equation (2) we have

Let tex2html_wrap_inline978 . Then by equation (3), it follows that

We note that the link from tex2html_wrap_inline980 to tex2html_wrap_inline982 is a critical path, and tex2html_wrap_inline982 is set as critical node, tex2html_wrap_inline986 . Thus,

We note that the feasible delay tex2html_wrap_inline988 at the source node indicates how much additional delay can be introduced along the critical path of the connection without missing end-to-end deadlines at the receivers.


next up previous
Next: The Relaxation Pass Up: Three-Pass Establishment Protocol Previous: The Request Pass

Riccardo Bettati
Mon Jul 14 15:29:52 CDT 1997