Subject: Re: [Ospf-wireless-design] DT Direction...

From: "Madhavi W. Chandra" <[email-masked]>
Date: Tue, 5 Oct 2004 11:37:38 -0400

Hi Phillip,

Sorry for the late response. It's great that you are implementing our
draft! I consulted with our software engineer Pratap who implemented
this portion of our design.  Please see inline...much of this is
feedback from Pratap.

On Fri, Sep 24, 2004 at 12:54:20PM -0700, Spagnolo, Phillip A wrote:
> Here are few comments on differential hellos from implementing Cisco's
> draft.
> 
> I would call the differential hellos a moderately hard piece.  From my
> experience, it is harder than optimized flooding.  But, I wouldn't rule
> it out do to implementation, after it is completed it can work well.  My

Yes, there are new components or terms added to the Hello process.
Thus, it may look complicated.  According to Pratap, "I don't think 
it really is as complicated as it sounds."  In any case, this is
subjective.  As you say, it can work well...thus, let's look at the
objective issues below.

> biggest question about differential hellos is adding a non-periodic
> component to the hello process.

Not sure what you mean here...  

It is up to the implementation when a change is sent. For example, a
change can trigger a Hello or you can send all the changes once at the
end of the Hello-interval.  Note that this is not like a route change
where we need to worry about how fast we notify neighbors.
 
> A few of the changes necessary (not inclusive):
> -state machine (Differential hellos require a somewhat complicated state
> machine and processing of the TLVs.  You cannot process the hello
> message in order of the TLVs, you must keep all TLVs in memory before
> determining what should be done with the packet.)

Actually, there is no real change to neighbor state machine.  However,
there is a new state machine added for hello processing. The logic can
be simplified to something like this:

- Receive Incremental Hello
    if SCS is same, ignore
    if SCS is SCS+1,
       if incomplete-bit is set, send request and ignore the hello
       if incomplete-bit not set,
           Process each TLV
    else
       Send request

- Receive Hello with response bit set,
    Process all the TLVs

When you receive a Hello, you have the whole Hello in the buffer
pool memory...which is all you need to process TLVs.  After OSPF
processes the Hello, it gets rid of that memory.  You don't need to
save the TLVs into seperate memory before processing them.

> -sequence # (Increment for any state change)

If you are sending all changes within the Hello-interval, then you
need to only increment the SCS once for all changes before sending the
Hello.

> -Active neighbors (only send in initial hello after new neighbor)
> -Drop neighbors (require keeping history of dropped neighbors for 4
> *dead interval, clear drop neighbor if renewed)

For this part, you need to maintain a separate list and a timer...for
persistant sending.  Note that with the introduction of the
incomplete-bit, persistent sending of TLVs is flexible.  Meaning, any
TLV can be sent persistently using this bit if that TLV is deemed
'more' important (to avoid request/reply)...or sent only once...in
which case you wouldn't need the separate list and timer. 

> -Relays added (similar to neighbors)
> -Relay deleted  (similar to neighbors)

The relay list is saved in memory.  Upon calculation of the relay
set, the deltas are sent in the Hello (either immediately...or at the
expiration of Hello-interval)....and the new relay list is saved.  The
details of what information must be saved in the 'interim' depends on
when the Hello is sent (immediately or after Hello-interval).

> -Partial state (must make checks of how many items in hello changed from
> previous state and set flag if partial info)

The incomplete-bit was added to provide flexibility in persistently
sending information...and accuracy.  It allows the receiver to be sure
in identifying if anything changed from previous Hello, *without*
having to save the previous Hello.  

For example, let's say we have SCS 10 for a neighbor and we then
receive a Hello with SCS 11.  The logic now is simple.  If the bit is
set, it means that this is persistent information...and the original
SCS 11 was lost...so the receiver can request.  If this bit is NOT
set, it means that this is the original SCS 11 packet...so process it
and save SCS 11 for the neighbor.  Now, let's say that a Hello with
SCS 11 with the incomplete bit set is received.  The receiver knows that
this is just persistent info...and it already has the info...so no
processing needed.  So, there is no need to see how many things
changed from previous Hello.

Hope this helps!

Regards,
Madhavi

> -Graceful restart (has to be changed due to partial info)
> 
> Phil
> 
> > -----Original Message-----
> > From: Henderson, Thomas R 
> > Sent: Friday, September 24, 2004 8:39 AM
> > To: Spagnolo, Phillip A
> > Subject: FW: [Ospf-wireless-design] DT Direction...
> > 
> > 
> > can you comment on how easy/hard it was to implement the
> > differential hello piece, and if hard, what was hard about
> > it?
> > 
> > -----Original Message-----
> > From: Abhay Roy [mailto:[email-masked]] 
> > Sent: Thursday, September 23, 2004 11:53 PM
> > To: Acee Lindem
> > Cc: [email-masked]
> > Subject: Re: [Ospf-wireless-design] DT Direction...
> > 
> > 
> > Acee,
> > 
> > Yes I agree that flooding is where the biggest gains can be made. 
> > So of course we need to start from there. But the "every little 
> > bit helps" logic is very valid too ;) And in fact it has been 
> > brought up by some of the customers we are talking to.
> > 
> > I also pointed earlier that we are proposing to overload Hello 
> > with (possibly) a lot of new information. So an attempt to 
> > condense this information using a seq# (incremental) approach 
> > seems appealing in theory. I would like to suggest that we wait to 
> > see some simulation/measurement numbers before ruling it out.
> > 
> > Regards,
> > -Roy-
> > 
> > On 09/22/04-0400 at 6:17pm, Acee Lindem writes:
> > 
> > > I believe everybody agrees that flooding needs to be 
> > optimised but is
> > > it really a a forgone conclusion that we need to optimise hellos
> > > and database exchange? I know that there was one vote for optimising
> > > hello since "every little bit helps".  However, as OSPF WG 
> > co-chair and
> > > steward of the protocol, I see one of my main roles as 
> > questioning whether or 
> > > not the existing mechanisms need to be changed. 
> > > Also, if flooding is dominant and database exchange is a 
> > factor, why wouldn't 
> > > we want to focus on reducing the amount of information? I 
> > don't have a 
> > > proposal for this but I've wondered why nobody has
> > > gone down this path. 
> > > Thanks,
> > > Acee 
> > > ----- Original Message ----- From: "Madhavi W. Chandra" 
> > <[email-masked]>
> > > To: <[email-masked]>
> > > Sent: Wednesday, September 01, 2004 12:22 PM
> > > Subject: [Ospf-wireless-design] DT Direction...
> > >
> > >
> > >> Hi All,
> > >> 
> > >> I put together a brief outline as a suggested direction 
> > for our Design
> > >> Team.  For credibility and effectiveness of the DT, I 
> > think we need to
> > >> have focused direction and timelines.  Basically, we 
> > shouldn't try to
> > >> solve everything under the sun for OSPF-MANET...and we 
> > shouldn't drag
> > >> this on to the point that know one will care...including 
> > us the DT! :)
> > >> 
> > >> Please see attached.  I also put in there the generic requirements
> > >> that we (Cisco) have gotten from customers that lead to our design
> > >> proposals. (Due to NDAs, I cannot share specifics.)
> > >> 
> > >>> From what I understand, the problem statement is more an 
> > agreement,
> > >> and not a formal draft.  So, we should be able to reach that in a
> > >> couple of weeks.
> > >> 
> > >> Thanks!
> > >> -Madhavi
> > >> 
> > >
> > >
> > > 
> > --------------------------------------------------------------
> > ------------------
> > >
> > >
> > >> _______________________________________________
> > >> Ospf-wireless-design mailing list
> > >> [email-masked]
> > >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> > >> 
> > >
> > > _______________________________________________
> > > Ospf-wireless-design mailing list
> > > [email-masked]
> > > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> > >
> > 
> > _______________________________________________
> > Ospf-wireless-design mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> > 
> 
> _______________________________________________
> Ospf-wireless-design mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

---

From: "Spagnolo, Phillip A" <[email-masked]>
Date: Thu, 7 Oct 2004 08:30:49 -0700

Hi Madhavi,
Thanks for your response, and thanks for talking with Pratap.  My e-mail
was designed to give some insight into how hard/easy the differential
hello piece was to implement.  I agree that the difficulty in
implementing differential hellos is subjective and I don't claim to be
an expert implementer.  However, the complexity of differential hellos
is definitely greater than the current hello scheme. But once again, I
don't propose that complexity in this case is a reason to discard
differential hellos.

Here is a response to your comments:

My comment that a non-periodic component is added to the hello process
comes in two parts.  First, you are now sending additional "unicast
hellos" in the form of requests.  A unicast request cannot be used to
say hello to everyone.  Second, answers MAY be sent immediately per
implementers choice.

I didn't mean a change is made to the neighbor state machine.  I meant
the state machine for processing a differential hello has many case.  I
will expand on your state machine below.  The basic concept is easy the
details give you more cases.

- Receive Hello

    if L-bit and I-bit are set process diff hello
    if new neighbor in neighbor list add new neighbor

    Process TLVs
    if R-bit set in SCS TLV
        send unicast answer

    if SCS is same
        if neigh state >= 2-way
            refresh neigh expiration timer
        if relay selector for neighbor
            refresh mpr expiration timer
    else if A-bit set in SCS TLV
        if self contained in drop neighbor TLV
            do nothing - return
        set neighbor SCS number equal to value in SCS TLV
        if (self contained in neighbor list)
            refresh neigh expiration timer
            if self in relay selector TLV
                add to mpr list
            else if neighbor in relay selector list
                remove mpr from selector list            
    else if neigh state >= 2way 
       if SCS is SCS+1,
           if incomplete-bit is set
               send unicast request - return
           else
               if hello neighbor list size > 0
                   increment neighbor scs

               //drop TLV processing
               if self in drop neighbor TLV
                   move neighbor to state one-way
               else if self not in drop neighbor TLV 
                   increment neighbor SCS
               //relay selector TLV processing
               if relay selector TLV not empty
                   increment neighbor SCS
                   if self dropped in mpr list
                       remove mpr from selector list
                   else if self added in mpr list
                       add to mpr list
                   else if neighbor already a selector
                       refresh mpr expiration timer
               else if neighbor already a selector
                   refresh mpr expiration timer
               //process other TLVs

               if neighbor scs not incremented
                   send unicast request
       else
           Send unicast request

> 
> When you receive a Hello, you have the whole Hello in the buffer pool 
> memory...which is all you need to process TLVs.
> After OSPF processes the Hello, it gets rid of that memory.  
> You don't need to save the TLVs into separate memory before 
> processing them.
> 

> Hello.

I agree, that is what I meant.  Sorry for my unclear statement.

> persistent sending.  Note that with the introduction of the 

I again agree.  So does that mean section 2.3.4.2 bullet 4 is a MAY send
hello for RouterDeadInterval?

> The relay list is saved in memory.  Upon calculation of the relay set,

> the deltas are sent in the Hello (either immediately...or at the 

> when the Hello is sent (immediately or after Hello-interval).

Does this mean you MAY send a hello every time you change a relay?  I
would again say this leads to aperiodic hellos.

> > -Partial state (must make checks of how many items in hello changed 
> > from previous state and set flag if partial info)
> 

> receive a Hello with SCS 11.  The logic now is simple.
> If the bit is set, it means that this is persistent 
> information...and the original SCS 11 was lost...so the 
> receiver can request.  If this bit is NOT set, it means that 
> this is the original SCS 11 packet...so process it and save 
> SCS 11 for the neighbor.  Now, let's say that a Hello with 
> SCS 11 with the incomplete bit set is received.  The receiver 
> knows that this is just persistent info...and it already has 
> the info...so no processing needed.  So, there is no need to 
> see how many things changed from previous Hello.
> 

I understand the goal of having the N-bit, and it seems useful for this
case.  I was simply saying that the sender must determine if the hello
it sends contains partial or full state change.  

Thanks,
Phil