3.5 Blockade State

The basic rule for creating a Resv refresh message is to merge the flowspecs of the reservation requests in place in the node, by computing their LUB. However, this rule is modified by the existence of "blockade state" resulting from ResvErr messages, to solve the KR-II problem (see Section 2.5). The blockade state also enters into the routing of ResvErr messages for Admission Control failure.

When a ResvErr message for an Admission Control failure is received, its flowspec Qe is used to create or refresh an element of local blockade state. Each element of blockade state consists of a blockade flowspec Qb taken from the flowspec of the ResvErr message, and an associated blockade timer Tb. When a blockade timer expires, the corresponding blockade state is deleted.

The granularity of blockade state depends upon the style of the ResvErr message that created it. For an explicit style, there may be a blockade state element (Qb(S),Tb(S)) for each sender S. For a wildcard style, blockade state is per previous hop P.

An element of blockade state with flowspec Qb is said to "blockade" a reservation with flowspec Qi if Qb is not (strictly) greater than Qi. For example, suppose that the LUB of two flowspecs is computed by taking the max of each of their corresponding components. Then Qb blockades Qi if for some component j, Qb[j] <= Qi[j].

Suppose that a node receives a ResvErr message from previous hop P (or, if style is explicit, sender S) as the result of an Admission Control failure upstream. Then:

1. An element of blockade state is created for P (or S) if it did not exist.

2. Qb(P) (or Qb(S)) is set equal to the flowspec Qe from the ResvErr message.

3. A corresponding blockade timer Tb(P) (or Tb(S)) is started or restarted for a time Kb*R. Here Kb is a fixed multiplier and R is the refresh interval for reservation state. Kb should be configurable.

4. If there is some local reservation state that is not blockaded (see below), an immediate reservation refresh for P (or S) is generated.

5. The ResvErr message is forwarded to next hops in the following way. If the InPlace bit is off, the ResvErr message is forwarded to all next hops for which there is reservation state. If the InPlace bit is on, the ResvErr message is forwarded only to the next hops whose Qi is blockaded by Qb.

Finally, we present the modified rule for merging flowspecs to create a reservation refresh message.

• If there are any local reservation requests Qi that are not blockaded, these are merged by computing their LUB. The blockaded reservations are ignored; this allows forwarding of a smaller reservation that has not failed and may perhaps succeed, after a larger reservation fails.

• Otherwise (all local requests Qi are blockaded), they are merged by taking the GLB (Greatest Lower Bound) of the Qi's.

  (The use of some definition of "minimum" improves performance by bracketing the failure level between the largest that succeeds and the smallest that fails. The choice of GLB in particular was made because it is simple to define and implement, and no reason is known for using a different definition of "minimum" here).

This refresh merging algorithm is applied separately to each flow (each sender or PHOP) contributing to a shared reservation (WF or SE style).

Figure 12 shows an example of the the application of blockade state for a shared reservation (WF style). There are two previous hops labeled (a) and (b), and two next hops labeled (c) and (d). The larger reservation 4B arrived from (c) first, but it failed somewhere upstream via PHOP (a), but not via PHOP (b). The figures show the final "steady state" after the smaller reservation 2B subsequently arrived from (d). This steady state is perturbed roughly every Kb*R seconds, when the blockade state times out. The next refresh then sends 4B to previous hop (a); presumably this will fail, sending a ResvErr message that will re-establish the blockade state, returning to the situation shown in the figure. At the same time, the ResvErr message will be forwarded to next hop (c) and to all receivers downstream responsible for the 4B reservations.

               Send     Blockade |   Reserve       Receive
                       State {Qb}|
                                 |   ________
        (a) <- WF(*{2B})    {4B} |  | * {4B} | WF(*{4B}) <- (c)
                                 |  |________|
                                 |
      ---------------------------|-------------------------------
                                 |
                                 |   ________
        (b) <- WF(*{4B})   (none)|  | * {2B} | WF(*{2B}) <- (d)
                                 |  |________|

                   Figure 12: Blockading with Shared Style