Subject: DVMRP graft and prune sequencing

From: Ravi Shekhar <[email-masked]>
Date: Thu, 7 Aug 1997 11:36:27 -0400 (EDT)

Hi,
    I posted a DVMRP graft and prune problem couple of weeks ago.  
    (Please find the mail enclosed at the end). 
     One way to solve this problem is to use sequence numbers in the GRAFT 
    and GRAFT-ACK messages in the next version of DVMRP (say v4) [as also 
    suggested by Ajit and Bill].

    But this would only work for two routers, both of which are running 
    DVMRP version 4. As pointed out earlier, it would still be a problem 
    with routers running DVMRP version 3 (for one they might simply reject 
    longer GRAFT messages and second that they wouldnt honour the sequence 
    numbers anyways).

    In which case, it seems, the only alternative is to send periodic GRAFT 
    messages.
    The behaviour of these "periodic GRAFT messages" can be defined to work 
    with the existing behaviour of DVMRPv3 and at the same time to decrease 
    the link-bandwidth/router-bandwidth consumption. 

    I have been thinking of the following way. 
    I would appreciate any comments on this. 

    Following four cases arise with the DVMRPv3/DVMRPv4 routers being
    upstream/downstream routers. (The source and group of all the messages 
    concerned here is <S, G> pair. Version of the DVMRP being run by a 
    router can be deduced from the PROBE messages exchanged by the routers).

    1. Both upstream and downstream routers are running DVMRPv4.
       The new message formats for GRAFT and GRAFT-ACK with sequence 
       numbers should do the trick.

    2. Both the routers are running DVMRPv3. There seems to be no viable
       solution other than possibly decreasing the PRUNE-TIMEOUT period.

    3. The downstream router is runnning DVMRPv4 and the upstream router 
       is running DVMRPv3. 

         In this case, the status of GRAFT can be checked after every 
       GRAFT-INTERVAL (lets say 30 secs) time.
         If no DATA or GRAFT-ACK message is received for an <S. G> pair during 
       a given interval, a GRAFT message is sent upstream at the end of that
       interval.
         If any DATA is received or a GRAFT-ACK is received (possibly for the 
       GRAFT sent at the end of previous interval) for an <S, G> pair during an 
       interval, GRAFT message is not sent upstream at the end of the interval. 
       This saves the upstream router from getting hosed by the processing 
       of GRAFTS received from downstream routers if there is any data traffic 
       for this <S, G> pair.

         The status of GRAFT can be checked for some duration of time, lets
       say GRAFT-STATUS-CHECK-TIME seconds, at the gap of every GRAFT-INTERVAL 
       seconds after the first GRAFT message is sent. Although, for all 
       practical purposes, a few (10 to 20) graft interval(GRAFT-INTERVAL secs)
       time should suffice as the value of GRAFT-STATUS-CHECK-TIME, the upper 
       limit on GRAFT-STATUS-CHECK-TIME should be PRUNE-TIMEOUT period. After 
       this time duration, monitoring of graft status can be stopped because by 
       then the upstream router must have purged any PRUNE for the <S, G> pair
       received from the downstream router. 
         A binary exponential back-off policy can also be applied to the value 
       of GRAFT-INTERVAL for this duration of time.

       The above approach has following advantages:

     * Unlike the approach of making PRUNE timeout smaller, this approach 
       involves only the routers which are interested in receiving messages
       for a given <S, G> pair. That is to say it prevents the vices of 
       "flooding" (caused by decreasing PRUNE-TIMEOUT) which would involve 
       all the multi-cast routers in the world!!

     * GRAFT messages are not sent upstream if there is any data traffic.
       This gives the upstream router the needed CPU cycles for forwarding
       DATA. Sending GRAFT after every GRAFT-INTERVAL time could result in
       overkilling the upstream router with GRAFT message processing.

     * The computation required to update GRAFT status in the downstream router
       at the arrival of DATA could be as simple as clearing a flag at the 
       start of the interval and setting the flag at the arrival of first DATA 
       during that interval. It does not require any timer-queue maintainence 
       and hence should not have any considerable effect on the fast-path data 
       traffic. (The SG lookup would anyways be required for forwarding the
       data).

     * Last and the most important, it will work with the existing DVMRPv3
       routers (DVMRP v3 specification requires an upstream router to send
       a GRAFT-ACK for each GRAFT message received even if nothing needs to
       be done for that GRAFT message).

    4. The last possibility is that of downstream router running DVMRPv3 
       and upstream router running DVMRPv4. 
       Again it seems that the only way is to decrease the PRUNE-TIMEOUT 
       period of the DVMRPv3 downstream router.

       If there are any better suggestions, please let me know.

    Thanks ..
     - Ravi Shekhar.
------------
Problem:
>        Here is a situation in which it looks like that upstream 
>        and downstream routers are in different state causing the 
>        downstream router to not receive any packets for prune
>        timeout. 
>
>        S1 is the source and G1 is the group of concern here for
>        all grafts and prunes. Assuming that the time scale is 
>        increasing downwards:
>
>
>            Downstream Router                        Upstream Router
>         _____________________________________________________________
>
>            Graft(#1) for (S1, G1)
>                o--------------------------------------->o
>                .
>                .
>                .                               Graft ACK(#1) for (S1, G1)
>                .                               +--------o
>                .                               |
>            TIME-OUT                            |
>            Retransmit Graft(#2) for (S1, G1)   |
>                o--------------------------------------->o
>                                                |
>                                                |
>                o<------------------------------+
>
>                                                
>                                                Graft ACK(#2) for (S1, G1)
>                                                +--------o
>                                                |
>            PRUNE for (S1, G1)                  |
>                o--------------------------------------->o
>                                                |
>                                                |
>                                                |
>            GRAFT(#3) for (S1, G1) lost         |
>                o------------------>X           |
>                                                |
>                                                |
>                                                |
>                o<------------------------------+
>
>
>
>        Let me try to put it in words.
>            
>            - Downstream router initially sends a graft(#1). 
>            - Upstream router generates the ACK(#1).
>            - ACK does not reach the downstream router before it times 
>                out for ACK(#1) and sends another graft(#2).
>            - Downstream router now receives ACK(#1) and deduces that graft 
>                has succeded.
>            - Upstream router in the meanwhile gets graft(#2) and generates
>                ACK(#2) thinking that first ACK might have been lost.
>            - Downstream router sends a PRUNE for (S1, G1).
>            - Upstream router receives it and prunes downstream router from it.
>            - Downstream router now generates a graft(#3) next. But this graft
>                is lost on the way.
>            - The ACK(#2) generated earlier reaches downstream router now.
>
>        At this point downstream router will think that its last graft(#3) has
> 
>        been acknowledged (although it was ACK of graft(#2)). Whereas upstream
> 
>        router last got a PRUNE from downstream router so it will keep it 
>        pruned. 
>            Hence now downstream router will receive no messages for next two
>        hours for this source, group.
---------