Subject: DVMRP graft and prune

From: Ravi Shekhar <[email-masked]>
Date: Tue, 15 Jul 1997 11:16:51 -0400 (EDT)

Hi,
    I was wondering how is the following situation taken care of
    in DVMRP version 3 (RFC 1075). Any help would be much appreciated.

        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.

        Thanks 
         - Ravi Shekhar.

---

From: Ajit Thyagarajan <[email-masked]>
Date: Tue, 15 Jul 1997 15:12:45 -0400

>    in DVMRP version 3 (RFC 1075). Any help would be much appreciated.

Just a quick clarification, DVMRP version 3 is not detailed in
RFC1075. It is described in the internet-draft
draft-ietf-idmr-dvmrp-v3-04.[ps,txt]

The situation you describe is an interesting one.  I don't think the
current draft addresses this problem and I think the current
implementation of mrouted would be susceptible to this problem.

It seems like the only way to prevent this would be to use sequence
numbers in the grafts and include these sequence numbers in the
graft-acks returned.  The downstream router must keep track of the set
of sequence nos. it sent out with the grafts; this way the downstream
router knows exactly which graft was acknowledged.  Now, if an old
graft-ack finds its way to this router, its sequence no. can be
compared to those that were sent out before accepting it.

If the same router now decided to prune the s-g, it would have to
discard invalidate the current set and when it grafts again, rebuild
the valid seq. no. space.  The current packet formats for grafts and
graft-acks will probably have to change to include the seq. nos as
well.

The only drawback is that it makes the protocol state machine just a
bit more complicated.  In addition, an implementation will have to
take into account "older" implementations that lack this capability.

Ajit

---

From: Bill Fenner <[email-masked]>
Date: Tue, 15 Jul 1997 14:30:20 PDT

Ravi,

  Indeed, DVMRPv3 (as specified in draft-ietf-idmr-dvmrp-v3-04.txt)
doesn't handle that situation.  It can easily be addressed by adding a
sequence number to the graft/graft ack messages.  Unfortunately, there
are compatability issues (mrouted <3.5 will drop a graft with
additional data, and who knows what other implementations will do), so
it's not as simple as just adding the sequence number.

  The sequence number need not identify a specific packet, e.g. the
grafts that you labelled #1 and #2 in your message could have the same
sequence number; the sequence number would only need to change when
sending a prune.

  Bill