[aodvv2-discuss] Re: Writing for the future <was, Appendices and RFC 5444 >
- From: Victoria Mercieca <vmercieca0@xxxxxxxxx>
- To: "aodvv2-discuss@xxxxxxxxxxxxx" <aodvv2-discuss@xxxxxxxxxxxxx>
- Date: Mon, 2 Mar 2015 16:17:12 +0000
Hi all,
Further to this, I've finished updating Appendix A (attached) to reflect
the current contents of section 8 and 9 and had a stab at updating the RFC
5444 bits too (please don't shoot me!)
A couple of things I noticed while doing this:
8.6 - should say it needs to match MsgType too, and also we could update
this section to say RteMsg not only RREQ
9.3.2 - if the current route to UnreachableAddress in the RERR is already
invalid, we can ignore and move on to the next UnreachableAddress - I put
this in the appendix pseudo-code too.
A.5.1 - it says MF = 0, but all other messages say MF = 4 because only the
msg-hop-limit field is there, which is true of this message too, should
this also be MF = 4?
Regards,
Vicky.
On Fri, Feb 27, 2015 at 10:37 PM, Victoria Mercieca <vmercieca0@xxxxxxxxx>
wrote:
> Hi Charlie,
>
> Thanks for the new version, I'll give it a read over the next day or so.
>
> Couple more comments below.
>
>
> On Fri, Feb 27, 2015 at 10:22 PM, Charlie Perkins <
> charles.perkins@xxxxxxxxxxxxx> wrote:
>
>> Hello Vicky,
>>
>> It would be a sin to mandate use of the RFC 5444 parser in order
>> to build AODVv2. On the other hand, it would be a sin to make it
>> difficult to use the RFC 5444 parser.
>>
>> Then maybe it should stay there. It will be valuable for implementors who
> are not going to use a RFC5444 parser.
>
>
>> Regarding the pseudo-code, well, some people really like having
>> pseudo-code, and to others it doesn't matter. I thought that Stan's
>> object mainly revolved around making a bigger target for criticism
>> from people looking for that sort of thing.
>>
>> I guess the pseudo-code could stay there too for the people that would
> prefer it to the descriptions in Sections 8 and 9. It does pretty much
> duplicate whats already been said, but if there's value in it being
> expressed in this way I don't have any real objection.
>
> Regards,
> Vicky.
>
> Regards,
>> Charlie P.
>>
>>
>> On 2/27/2015 2:09 PM, Victoria Mercieca wrote:
>>
>> Hi all,
>>
>> As I was looking at it, the pseudo-code stuff seemed to overlap a lot
>> with what we have in sections 8 and 9.
>>
>> The RFC 5444 stuff - if we are handing our Data Elements to a RFC5444
>> implementation and we don't actually create the RFC5444 message ourselves,
>> I don't know that we need to include it. If there might be AODVv2
>> implementations that attempt to create the RFC5444 message directly, it
>> would be useful.
>>
>> Regards,
>> Vicky.
>>
>>
>> On Fri, Feb 27, 2015 at 9:54 PM, Charlie Perkins <
>> charles.perkins@xxxxxxxxxxxxx> wrote:
>>
>>> Hello Stan and all,
>>>
>>> There are two appendix sections. One shows example RFC 5444 formats.
>>> The other shows some pseudocode. These are independent of each other.
>>>
>>> I hear your frustration about RFC 5444 discussions in the past. But
>>> please
>>> consider that we are writing this specification for future implementers,
>>> not as a rebuttal to ongoing RFC 5444 discussions and recriminations.
>>>
>>> From *that* standpoint, I think the case for inclusion is very clear.
>>> The
>>> downside is that we might make mistakes. But, if we DO make mistakes,
>>> that only makes the case for inclusion even stronger! Because, if WE
>>> make
>>> those mistakes, then future implementers are even MORE likely to make
>>> those mistakes.
>>>
>>> Of course our jobs as editors will be easier if we delete text. I don't
>>> view
>>> that as the highest priority for decision making, however.
>>>
>>> Please consider this when making your decision.
>>>
>>> Regards,
>>> Charlie P.
>>>
>>>
>>>
>>> On 2/27/2015 1:46 PM, Stan Ratliff wrote:
>>>
>>> Charlie,
>>>
>>> Catching up on the recent email, I now see 3 "votes" to remove the
>>> 5444 discussions in the appendices - granted, I may be overstating Vicky's
>>> position, but...
>>>
>>> So, that leaves 3 votes to pull it out, 1 to keep it (yours), and "1
>>> in the wind" (Lotte, but then it's late in Germany)... ;-)
>>>
>>> What I'm proposing is that we only wait for consensus in the Editorial
>>> team before posting to the list - I'd assume Monday at the latest.
>>> Otherwise, I'll feel obligated to follow the posting with an email stating
>>> we're discussing pulling that information out (and thereby soliciting WG
>>> input on the issue).
>>>
>>> Regards,
>>> Stan
>>>
>>>
>>> On Fri, Feb 27, 2015 at 3:42 PM, Charlie Perkins <
>>> charles.perkins@xxxxxxxxxxxxx> wrote:
>>>
>>>> Hello Stan,
>>>>
>>>> Please read to the end of this email...
>>>>
>>>> I did mean to submit the current revision as an Internet Draft.
>>>> It includes almost all of the issue resolutions. We need to have it
>>>> out there so we can point out to people the issue resolutions in
>>>> the draft. Jiazi already complained about this.
>>>>
>>>> Are you really set against this? If so, how else can we have a
>>>> reasonable discussion on the mailing list about the many and
>>>> pervasive changes to the draft? Draft ...-06 has some errors that
>>>> need to be corrected ASAP. I am O.K. to make draft ...-07 today
>>>> and draft ...-08 next week, including mailing list discussion about
>>>> draft ...-07...
>>>>
>>>> Did you look at the "Changes" section in the recent intermediate
>>>> revisions?
>>>>
>>>> I fear that if we can't have the mailing list discussion about the
>>>> issue resolutions, we will miss our deadline. If, on the other hand,
>>>> we can have the discussion, there is a chance that the draft would
>>>> be ready for Last Call by Dallas.
>>>>
>>>> I don't mean it will be perfect. I mean that we can represent that
>>>> we have taken action to resolve the issues.
>>>>
>>>> Regards,
>>>> Charlie P.
>>>>
>>>>
>>>>
>>>> On 2/27/2015 12:19 PM, Stan Ratliff wrote:
>>>>
>>>> Charlie,
>>>>
>>>> When you say "put this version out", do you mean post it to the MANET
>>>> list? Or, just "discuss amongst ourselves"? I would agree with the latter,
>>>> but not the former.
>>>>
>>>> Regards,
>>>> Stan
>>>>
>>>> On Fri, Feb 27, 2015 at 3:15 PM, Charlie Perkins <
>>>> charles.perkins@xxxxxxxxxxxxx> wrote:
>>>>
>>>>> Hello Stan,
>>>>>
>>>>> Oh, O.K. -- I did misunderstand...
>>>>>
>>>>> By the way, I think we agreed to have another teleconference next
>>>>> Thursday morning. The plan currently is to put out this revision
>>>>> today,
>>>>> so we can discuss whether the existing issues have been resolved.
>>>>> Then we will make another revision (...08) before the draft deadline.
>>>>>
>>>>> Regards,
>>>>> Charlie P.
>>>>>
>>>>>
>>>>> On 2/27/2015 12:08 PM, Stan Ratliff wrote:
>>>>>
>>>>> Charlie,
>>>>>
>>>>> Umm, no. You misunderstand. I'm calling for consensus *amongst the
>>>>> author team*. From the way I read this thread, there's already some amount
>>>>> of push-back from Vicky, and myself.
>>>>>
>>>>> I await the responses from the other members of the team.
>>>>>
>>>>> Regards,
>>>>> Stan
>>>>>
>>>>>
>>>>> On Fri, Feb 27, 2015 at 2:54 PM, Charlie Perkins <
>>>>> charles.perkins@xxxxxxxxxxxxx> wrote:
>>>>>
>>>>>> Hello Stan,
>>>>>>
>>>>>> Well, I certainly get how you feel about this. Nevertheless, I would
>>>>>> really like to keep those appendices around. Let's see if anyone
>>>>>> actually
>>>>>> does make the complaint that you are suggesting. We can take out the
>>>>>> appendices very easily, but once they are out, it would be very hard
>>>>>> to
>>>>>> get them back in...
>>>>>>
>>>>>> Regards,
>>>>>> Charlie P.
>>>>>>
>>>>>>
>>>>>> On 2/27/2015 11:14 AM, Stan Ratliff wrote:
>>>>>>
>>>>>> Sorry for the double-post on this topic. I saw another item that I
>>>>>> want to comment on. text inline.
>>>>>>
>>>>>> On Fri, Feb 27, 2015 at 1:09 PM, Charlie Perkins <
>>>>>> charles.perkins@xxxxxxxxxxxxx> wrote:
>>>>>>
>>>>>>> Hello Vicky,
>>>>>>>
>>>>>>> One comment below...
>>>>>>>
>>>>>>> On 2/27/2015 8:02 AM, Victoria Mercieca wrote:
>>>>>>>
>>>>>>>> Hi Charlie,
>>>>>>>>
>>>>>>>
>>>>>>> <.... editorial comments all done with microscopic wordsmithing in
>>>>>>>> a couple of places... >
>>>>>>>>
>>>>>>>>
>>>>>>> Appendices:
>>>>>>>> I started looking at updating the appendix A algorithms but I'm not
>>>>>>>> sure there's much point - this stuff seems to be in section 8 and
>>>>>>>> section 9
>>>>>>>> in the main body of the draft now, and I'm not sure if we should be
>>>>>>>> instructing how to construct the RFC5444 messages? I've attached my
>>>>>>>> early
>>>>>>>> work on this and I put some comments between <>, it might be worth
>>>>>>>> merging
>>>>>>>> anything thats not already in sections 8 or 9 and removing appendix A?
>>>>>>>>
>>>>>>>
>>>>>>> I spent a long time on those appendices, and it seems like a lot of
>>>>>>> people might benefit from actually seeing how the RFC 5444 headers
>>>>>>> look in real life.
>>>>>>
>>>>>>
>>>>>> Place my vote FIRMLY in the camp that says "remove any and all
>>>>>> instruction, tables, appendicies, etc. that attempt to divine the
>>>>>> rationale
>>>>>> behind the cluster-@!#!@ that is RFC 5444.
>>>>>>
>>>>>> There have been literally HUNDREDS, if not THOUSANDS, of emails and
>>>>>> discussions that whirl and whine around the notion that "... the AODVv2
>>>>>> authors either don't know, or are attempting to bastardize, that
>>>>>> WONDERFUL,
>>>>>> MAJESTIC, EASY-TO-READ-AND-UNDERSTAND, piece of BRILLIANCE that is RFC
>>>>>> 5444!"
>>>>>>
>>>>>> In the current hyper-heated political environment we find ourselves
>>>>>> in, I'd MUCH rather take any and all possible ammunition away from the
>>>>>> opposing camp - notwithstanding the facts that (a) you spent a lot of
>>>>>> time
>>>>>> on the appendices, and (b) frankly, I like the way they look. At this
>>>>>> point, I'd rather not (even inadvertently) hand the anti-AODVv2 camp a
>>>>>> hand
>>>>>> grenade they can use to blow us up with...
>>>>>>
>>>>>> Regards,
>>>>>> Stan
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>> Plus, from comments received at the time, it was
>>>>>>> clear that there are many ways to get it wrong. Even recently, I was
>>>>>>> using "Tail" instead of "Mid" -- and nobody caught that for well over
>>>>>>> a year.
>>>>>>>
>>>>>>> This leads me to think that there is a lot of value in that
>>>>>>> non-normative
>>>>>>> pseudocode, and I don't think it hurts anything to have it there.
>>>>>>>
>>>>>>>
>>>>>>> Regards,
>>>>>>> Charlie P.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>
Appendix A. Example Algorithms for AODVv2 Protocol Operations
The following subsections show example algorithms for protocol
operations required by AODVv2, including RREQ, RREP, RERR, and
RREP_Ack.
Processing for RREQ, RREP, and RERR messages follows the following
general outline:
1. Receive incoming message.
2. Update route table as appropriate.
3. Respond as needed, often regenerating the incoming message with
updated information.
Once the route table has been updated, the information contained
there is known to be the most recent available information for any
fields in the outgoing message. For this reason, the algorithms are
written as if outgoing message field values are assigned from the
route table information, even though it is often equally appropriate
to use fields from the incoming message.
AODVv2_algorithms:
o Process_Routing_Info
o Fetch_Route_Table_Entry
o Update_Route_Table_Entry
o Create_Route_Table_Entry
o LoopFree
o Update_Rte_Msg_Table
o Generate_RREQ
o Receive_RREQ
o Regenerate_RREQ
o Timeout_RREQ
o Generate_RREP
o Receive_RREP
o Regenerate_RREP
o Generate_RERR
o Receive_RERR
o Regenerate_RERR
o Generate_RREP_Ack
o Receive_RREP_Ack
o Timeout_RREP_Ack
The following lists indicate the meaning of the field names used in
subsequent sections to describe processing for the above algorithms.
RteMsg parameters, where rteMsg can be inRREQ, outRREQ, inRREP or
outRREP:
rteMsg.hopLimit
rteMsg.hopCount
rteMsg.ackReq (RREP only, optional)
rteMsg.metricType (optional)
rteMsg.origAddr
rteMsg.targAddr
rteMsg.origPrefixLen (optional)
rteMsg.targPrefixLen (optional)
rteMsg.origSeqNum (RREQ only)
rteMsg.targSeqNum (optional in RREQ)
rteMsg.metric
rteMsg.validityTime
rteMsg.nbrIP
AdvRte has the following properties as described in Section 8.1:
AdvRte.Address = OrigAddr (in a RREQ) or TargAddr (in a RREP)
AdvRte.PrefixLength = PrefixLength for OrigAddr (in a RREQ)
or TargAddr (in a RREP), or if not present, the maximum address
length for the address family of AdvRte.Address
AdvRte.SeqNum = SeqNum for OrigAddr (in a RREQ) or for TargAddr
(in a RREP)
AdvRte.MetricType = RteMsg.MetricType, if present, else
DEFAULT_METRIC_TYPE
AdvRte.Metric = RteMsg.Metric
AdvRte.Cost = AdvRte.Metric + Cost(L) according to the indicated
MetricType, where L is the link from the advertising router
AdvRte.ValidityTime = ValidityTime in the RteMsg, if present
AdvRte.NextHopIP = IP source of the RteMsg
AdvRte.NextHopIntf = interface the RteMsg was received on
AdvRte.HopCount = value from RteMsg header
AdvRte.HopLimit = value from RteMsg header
AdvRte.AckReq = true/false whether present in RteMsg (optional
in RREP)
A route table entry has properties as described in Section 6.1:
Route.Address
Route.PrefixLength
Route.SeqNum
Route.NextHop
Route.NextHopInterface
Route.LastUsed
Route.LastSeqNum
Route.ExpirationTime
Route.MetricType
Route.Metric
Route.State
Route.Timed
Route.Precursors (optional)
A.1. Subroutines for AODVv2 Route Operations
A.1.1 Process_Routing_Info
/* Compare incoming route information to stored route, maybe use */
/* linkMetric: either Cost(inRREQ.netif) or (inRREP.netif) */
Process_Routing_Info (advRte)
{
rte := Fetch_Route_Table_Entry (advRte);
if (NULL == rte)
{
rte := Create_Route_Table_Entry(advRte);
return rte;
}
if (!LoopFree(advRte, rte))
{ /* incoming route cannot be guaranteed loop free */
return null;
}
/* rule from 8.1 */
if (
(AdvRte.SeqNum > Route.SeqNum) /* stored route is stale */
OR
((AdvRte.SeqNum == Route.SeqNum) /* same SeqNum */
AND
[((Route.State == Invalid)) /* advRte can repair stored */
OR
(AdvRte.Cost < Route.Metric)])) /* advRte is better */
{
Update_Route_Table_Entry (rte, advRte);
}
return rte;
}
A.1.2 Fetch_Route_Table_Entry
/* lookup a route table entry matching an advertised route */
Fetch_Route_Table_Entry (advRte)
{
foreach (rteTableEntry in rteTable)
{
if (rteTableEntry.Address == advRte.Address AND
rteTableEntry.MetricType == advRte.MetricType)
return rteTableEntry;
}
return null;
}
/* lookup a route table entry matching address and metric type */
Fetch_Route_Table_Entry (destination, metricType)
{
foreach (rteTableEntry in rteTable)
{
if (rteTableEntry.Address == destination AND
rteTableEntry.MetricType == MetricType)
return rteTableEntry;
}
return null;
}
A.1.3 Update_Route_Table_Entry
/* update a route table entry using AdvRte in a received RteMsg */
Update_Route_Table_Entry (rte, advRte);
{
rte.SeqNum = advRte.SeqNum;
rte.NextHop = advRte.NextHopIp;
rte.NextHopInterface = advRte.NextHopIntf;
rte.LastUsed = Current_Time;
rte.LastSeqNum = Current_Time;
if (validityTime)
{
rte.ExpirationTime = Current_Time + advRte.validityTime;
rte.Timed = true;
}
else
{
rte.Timed = false;
rte.ExpirationTime = MAXTIME;
}
rte.Metric = advRte.Cost;
if (rte.State == Invalid)
rte.State = Idle;
}
A.1.4 Create_Route_Table_Entry
/* Create a route table entry from address and prefix length */
Create_Route_Table_Entry(address, prefixLength, seqNum, metricType)
{
rte = allocate_memory();
rte.Address = address;
rte.PrefixLength = prefixLength;
rte.SeqNum = seqNum;
rte.MetricType = metricType;
}
/* Create a route table entry from the advertised route */
Create_Route_Table_Entry(advRte)
{
rte = allocate_memory();
rte.Address = advRte.Address;
if (advRte.PrefixLength)
rte.PrefixLength = advRte.PrefixLength;
else
rte.PrefixLength = maxPrefixLenForAddressFamily;
rte.SeqNum = advRte.SeqNum;
rte.NextHop = advRte.NextHopIp;
rte.NextHopInterface = advRte.NextHopIntf;
rte.LastUsed := Current_Time
rte.LastSeqnum := Current_Time
if (validityTime)
{
rte.ExpirationTime = Current_Time + advRte.ValidityTime;
rte.Timed = true;
}
else
{
rte.Timed = false;
rte.ExpirationTime = MAXTIME;
}
rte.MetricType := advRte.MetricType;
rte.Metric := advRte.Metric;
rte.State = Idle;
}
A.1.5 LoopFree
/* return TRUE if the route R2 is LoopFree compared to R1 */
LoopFree(advRte, rte)
{
if (advRte.Cost < rte.Cost)
return true;
else
return false;
}
A.1.5 Fetch_Rte_Msg_Table_Entry
/* find an entry in the RteMsg table matching the given message's
msg-type, OrigAddr, TargAddr, MetricType */
Fetch_Rte_Msg_Table_Entry(rteMsg)
{
foreach (entry in RteMsgTable)
{
if (entry.msg-type == rteMsg.msg-type AND
entry.OrigAddr == rteMsg.OrigAddr AND
entry.TargAddr == rteMsg.TargAddr AND
entry.MetricType == rteMsg.MetricType)
{
return entry;
}
}
return NULL;
}
A.1.7 Update_Rte_Msg_Table
/* update the multicast route message suppression table based
on the received RteMsg, return true if it was created or
the SeqNum was updated (i.e. it needs to be regenerated) */
Update_Rte_Msg_Table(rteMsg)
{
/* search for a comparable entry */
entry = Fetch_Rte_Msg_Table_Entry(rteMsg)
/* if there is none, create one (see 6.5 and 8.6) */
if (entry == NULL)
{
entry.MessageType := rteMsg.msg_type
entry.OrigAddr := rteMsg.OrigAddr
entry.TargAddr := rteMsg.TargAddr
entry.OrigSeqNum := rteMsg.OrigSeqNum (if present)
entry.TargSeqNum := rteMsg.TargSeqNum (if present)
entry.MetricType := rteMsg.MetricType (if present) or
DEFAULT_METRIC_TYPE
entry.Timestamp := Current_Time
return true;
}
/* if current entry is stale */
if ((rteMsg.msg-type == RREQ
AND entry.OrigSeqNum < rteMsg.OrigSeqNum)
OR
(rteMsg.msg-type == RREP
AND entry.TargSeqNum < rteMsg.TargSeqNum))
{
entry.OrigSeqNum := rteMsg.OrigSeqNum (if present)
entry.TargSeqNum := rteMsg.TargSeqNum (if present)
entry.Timestamp := Current_Time
return true;
}
/* if received rteMsg is stale */
if ((rteMsg.msg-type == RREQ
AND entry.OrigSeqNum > rteMsg.OrigSeqNum)
OR
(rteMsg.msg-type == RREP
AND entry.TargSeqNum > rteMsg.TargSeqNum))
{
entry.Timestamp := Current_Time
return false;
}
/* if same SeqNum but rteMsg has lower metric */
if (entry.Metric > rteMsg.Metric)
entry.Metric := rteMsg.Metric
entry.Timestamp := Current_Time
return false;
}
A.2. Example Algorithms for AODVv2 RREQ Operations
A.2.1. Generate_RREQ
Generate_RREQ
{
/* Increment sequence number */
mySeqNum := (1 + mySeqNum) /* from nonvolatile storage */
/* Marshall parameters */
outRREQ.hopLimit := MAX_HOPCOUNT /* RFC 5444 */
outRREQ.hopCount := (if included) 0
outRREQ.metricType := if not DEFAULT_METRIC_TYPE, metric type needed by
application
outRREQ.origAddr := IP address of Router Client which generated the
packet to be forwarded
outRREQ.targAddr := destination IP address in the packet to be forwarded
outRREQ.origPrefixLen := if included, the prefix length associated with
the Router Client
outRREQ.origSeqNum := mySeqNum
outRREQ.targSeqNum := if known from route table, target sequence number
outRREQ.metric := 0 (default) or MIN_METRIC(outRREQ.metricType)
outRREQ.validityTime := if included, the validity time for route to
OrigAddr
/* Build RFC 5444 message header fields */
msg-type = RREQ (message is of type RREQ)
MF (Message Flags) = 4 (only msg-hop-limit field is present)
MAL (Message Address Length) = 3 for IPv4, 15 for IPv6
msg-size = NN (octets - counting MsgHdr, AddrBlk, and AddrTLVs)
msg-hop-limit := outRREQ.hopLimit
/* msg-hop-count := outRREQ.hopCount (if including, see Message
Flags) */
msg.tlvs-length := 0
if (outRREQ.metricType != DEFAULT_METRIC_TYPE)
{ /* Build MetricType Message TLV */
metricMsgTlv.value := outRREQ.metricType
msg.tlvs-length += metricMsgTlv total length
}
/* Build Address Blk */
num-addr := 2
AddrBlk := outRREQ.origAddr and outRREQ.targAddr addresses using prefix
length information from outRREQ.origPrefixLen if necessary
/* Include each available Sequence Number in appropriate Address Block
TLV */
/* OrigSeqNum Address Block TLV */
origSeqNumAddrBlkTlv.value := outRREQ.origSeqNum
origSeqNumAddrBlkTlv.thassingleindex := 1
origSeqNumAddrBlkTlv.index-start := 0
/* TargSeqNum Address Block TLV */
if (outRREQ.targSeqNum != NULL)
{
targSeqNumAddrBlkTlv.value := outRREQ.targSeqNum
targSeqNumAddrBlkTlv.thassingleindex := 1
targSeqNumAddrBlkTlv.index-start := 1
}
/* Build Metric Address Block TLV */
metricAddrBlkTlv.value := outRREQ.metric
metricAddrBlkTlv.thassingleindex := 1
metricAddrBlkTlv.index-start := 0
if (outRREQ.validityTime is required)
{
/* Build VALIDITY_TIME Address Block TLV */
VALIDITY_TIMEAddrBlkTlv.value := outRREQ.validityTime
VALIDITY_TIMEAddrBlkTlv.thassingleindex := 1
VALIDITY_TIMEAddrBlkTlv.index-start := 0
}
/* multicast RFC 5444 message to LL-MANET-Routers */
}
A.2.2. Receive_RREQ
Receive_RREQ (inRREQ)
{
if (inRREQ.nbrIP present in blacklist) {
if (blacklist_expiration_time < current_time)
return; /* don't process or regenerate RREQ... */
else
remove nbrIP from blacklist;
}
if (inRREQ does not contain msg_hop_limit, OrigAddr, TargAddr,
OrigSeqNum, OrigAddrMetric)
return;
if (inRREQ.origAddr and inRREQ.targAddr are not valid routable and
unicast addresses)
return;
if (inRREQ.metricType is present but an unknown value)
return;
if (inRREQ.metric > MAX_METRIC[inRREQ.metricType] - Cost(Link)
return;
/* Extract inRREQ values */
advRte.Address = inRREQ.origAddr
advRte.PrefixLength = inRREQ.origPrefixLen (if present), or the
maximum address length for the address family of advRte.Address
advRte.SeqNum = inRREQ.origSeqNum
advRte.MetricType = inRREQ.metricType (if present), else
DEFAULT_METRIC_TYPE
advRte.Metric = inRREQ.metric
advRte.Cost = inRREQ.metric + Cost(L) according to the indicated
MetricType, where L is the link from the advertising router
advRte.ValidityTime = inRREQ.validityTime (if present)
advRte.NextHopIP = inRREQ.nbrIP
advRte.NextHopIntf = interface the RteMsg was received on
advRte.HopCount = inRREQ.hopCount
advRte.HopLimit = inRREQ.hopLimit
rte = Process_Routing_Info (advRte)
/* update the RteMsgTable and determine if the RREQ needs to be
regenerated */
regenerate = Update_Rte_Msg_Table(inRREQ)
if (inRREQ.targAddr is in Router Client list)
Generate_RREP(inRREQ, rte)
else if (regenerate)
Regenerate_RREQ(inRREQ, rte)
}
A.2.3. Regenerate_RREQ
Regenerate_RREQ (inRREQ, rte) /* called from receive_RREQ(), rte is the
route to OrigAddr */
{
outRREQ.hopLimit := inRREQ.hopLimit - 1
if (outRREQ.hopLimit == 0)
return; /* don't regenerate */
if (inRREQ.hopCount exists)
{
if (inRREQ.hopCount >= MAX_HOPCOUNT)
return; /* don't regenerate */
outRREQ.hopCount := inRREQ.hopCount + 1
}
/* Marshall parameters */
outRREQ.metricType := rte.MetricType
outRREQ.origAddr := rte.Address
outRREQ.targAddr := inRREQ.targAddr
outRREQ.origPrefixLen := rte.PrefixLength (if not equal to address length)
outRREQ.origSeqNum := rte.SeqNum
outRREQ.targSeqNum := inRREQ.targSeqNum /* if present */
outRREQ.metric := rte.Metric
outRREQ.validityTime := rte.ValidityTime or length of time
HandlingRtr wishes to advertise route to OrigAddr
/* Build RFC 5444 message header fields */
msg-type = RREQ (message is of type RREQ)
MF (Message Flags) = 4 (only msg-hop-limit field is present)
MAL (Message Address Length) = 3 for IPv4, 15 for IPv6
msg-size = NN (octets - counting MsgHdr, AddrBlk, and AddrTLVs)
msg-hop-limit := outRREQ.hopLimit
/* msg_hop_count := outRREQ.hopCount (if including, see Message
Flags) */
msg.tlvs-length := 0
if (outRREQ.metricType != DEFAULT_METRIC_TYPE)
{ /* Build MetricType Message TLV */
metricMsgTlv.value := outRREQ.metricType
msg.tlvs-length += metricMsgTlv total length
}
/* Build Address Block */
num-addr := 2
AddrBlk := outRREQ.origAddr and outRREQ.targAddr addresses using prefix
length information from outRREQ.origPrefixLen if necessary
/* Include each available Sequence Number in appropriate Address Block
TLV */
/* OrigSeqNum Address Block TLV */
origSeqNumAddrBlkTlv.value := outRREQ.origSeqNum
origSeqNumAddrBlkTlv.thassingleindex := 1
origSeqNumAddrBlkTlv.index-start := 0
/* TargSeqNum Address Block TLV */
if (outRREQ.targSeqNum != NULL) {
targSeqNumAddrBlkTlv.value := outRREQ.targSeqNum
targSeqNumAddrBlkTlv.thassingleindex := 1
targSeqNumAddrBlkTlv.index-start := 1
}
/* Build Metric Address Block TLV */
metricAddrBlkTlv.value = outRREQ.metric
metricAddrBlkTlv.thassingleindex := 1
metricAddrBlkTlv.index-start := 1
if (outRREQ.validityTime is required)
{
/* Build VALIDITY_TIME Address Block TLV */
VALIDITY_TIMEAddrBlkTlv.value = outRREQ.validityTime
VALIDITY_TIMEAddrBlkTlv.thassingleindex := 1
VALIDITY_TIMEAddrBlkTlv.index-start := 0
}
/* multicast RFC 5444 message to LL-MANET-Routers, or if inRREQ was
unicast the message can be unicast to the next hop on the route to TargAddr, if
known */
}
A.3. Example Algorithms for AODVv2 RREP Operations
A.3.1. Generate_RREP
Generate_RREP(inRREQ, rte)
{
/* Increment Sequence Number */
mySeqNum := (1 + mySeqNum) /* from nonvolatile storage */
/* Marshall parameters */
outRREP.hopLimit := inRREQ.hopCount
outRREP.hopCount := 0
/* Include the AckReq when:
- previous RREP does not seem to enable any data flow, OR
- when RREQ is received from same OrigAddr after RREP was
unicast to rte.nextHop
*/
outRREP.ackReq := true or false whether to include
if (rte.metricType != DEFAULT_METRIC_TYPE)
outRREP.metricType := rte.metricType
outRREP.origAddr := rte.Address
outRREP.targAddr := inRREQ.targAddr
outRREP.targPrefixLen := rte.PrefixLength (if not equal to address length)
outRREP.targSeqNum := mySeqNum
outRREP.metric := 0 (default) or MIN_METRIC(rte.metricType)
outRREP.validityTime := (if included) the validity time for route to
TargAddr
/* Build RFC 5444 message header fields */
msg-type = RREP (message is of type RREP)
MF (Message Flags) = 4 (only msg-hop-limit field is present)
MAL (Message Address Length) = 3 for IPv4, 15 for IPv6
msg-size = NN (octets - counting MsgHdr, AddrBlk, and AddrTLVs)
msg-hop-limit := outRREP.hopLimit
msg.tlvs-length := 0
if (outRREP.ackReq is required)
{ /* Build AckReq Message TLV */
msg.tlvs-length += ackReqMsgTlv total length
}
if (outRREP.metricType != DEFAULT_METRIC_TYPE)
{ /* Build MetricType Message TLV */
metricMsgTlv.value := outRREP.metricType
msg.tlvs-length += metricMsgTlv total length
}
/* Build Address Block */
num-addr := 2
AddrBlk := outRREP.origAddr and outRREP.targAddr addresses using prefix
length information from outRREP.targPrefixLen if necessary
/* TargSeqNum Address Block TLV */
targSeqNumAddrBlkTlv.value := outRREP.targSeqNum
targSeqNumAddrBlkTlv.thassingleindex := 1
targSeqNumAddrBlkTlv.index-start := 1
/* Build Metric Address Block TLV containing TargAddr metric */
metricAddrBlkTlv.value = outRREP.metric
metricAddrBlkTlv.thassingleindex := 1
metricAddrBlkTlv.index-start := 1
if (outRREP.validityTime is required)
{
/* Build VALIDITY_TIME Address Block TLV */
VALIDITY_TIMEAddrBlkTlv.value = outRREP.validityTime
VALIDITY_TIMEAddrBlkTlv.thassingleindex := 1
VALIDITY_TIMEAddrBlkTlv.index-start := 0
}
/* unicast RFC 5444 message to rte[OrigAddr].NextHop */
}
A.3.2. Receive_RREP
Receive_RREP (inRREP)
{
if (inRREP.nbrIP present in blacklist) {
if (blacklist_expiration_time < current_time)
return; /* don't process or regenerate RREQ... */
else
remove nbrIP from blacklist;
}
if (inRREP does not contain msg_hop_limit, OrigAddr, TargAddr,
TargSeqNum, TargAddrMetric)
return;
if (inRREP.origAddr and inRREQ.targAddr are not valid routable and
unicast addresses)
return;
if (inRREP.metricType is present but an unknown value)
return;
if (inRREP.metric > MAX_METRIC[MetricType] - Cost(Link)
return;
/* Extract inRREP values */
advRte.Address = inRREP.targAddr
advRte.PrefixLength = inRREP.targPrefixLen (if present), or the
maximum address length for the address family of advRte.Address
advRte.SeqNum = inRREP.targSeqNum
advRte.MetricType = inRREP.metricType (if present), else
DEFAULT_METRIC_TYPE
advRte.Metric = inRREP.metric
advRte.Cost = inRREP.metric + Cost(L) according to the indicated
MetricType, where L is the link from the advertising router
advRte.ValidityTime = inRREP.validityTime (if present)
advRte.NextHopIP = inRREP.nbrIP
advRte.NextHopIntf = interface the RteMsg was received on
advRte.HopCount = inRREP.hopCount
advRte.HopLimit = inRREP.hopLimit (if included)
rte := Process_Routing_Info (advRte)
if (inRREP includes AckReq data element)
Generate_RREP_Ack(inRREP)
/* update the RteMsgTable and determine if the RREP needs to be
regenerated */
regenerate = Update_Rte_Msg_Table(inRREP)
if (inRREP.targAddr is in the Router Client list)
/* start to use the route */
send_buffered_packets(rte)
else if (regenerate)
Regenerate_RREP(inRREP, rte)
}
A.3.3. Regenerate_RREP
Regenerate_RREP(inRREP, rte)
{
if (rte == NULL)
{
Generate_RERR(inRREP)
return;
}
outRREP.hopLimit := inRREP.hopLimit - 1
if (outRREP.hopLimit == 0) /* don't regenerate */
return;
if (inRREP.hopCount exists)
{
if (inRREP.hopCount >= MAX_HOPCOUNT)
return; /* don't regenerate */
outRREP.hopCount := inRREP.hopCount + 1
}
/* Marshall parameters */
/* Include the AckReq when:
- previous RREP does not seem to enable any data flow, OR
- when RREQ is received from same OrigAddr after RREP was
unicast to rte.nextHop
*/
outRREP.ackReq := true or false whether to include
if (rte.metricType != DEFAULT_METRIC_TYPE)
outRREP.metricType := rte.metricType
outRREP.origAddr := inRREP.origAddr
outRREP.targAddr := rte.Address
outRREP.targPrefixLen := rte.PrefixLength (if not equal to address
length)
outRREP.targSeqNum := rte.SeqNum
outRREP.metric := rte.Metric
outRREP.validityTime := (if included) the validity time for route to
TargAddr
outRREP.nextHop := rte.nextHop
/* Build RFC 5444 message header fields */
msg-type = RREP (message is of type RREP)
MF (Message Flags) = 4 (only msg-hop-limit field is present)
MAL (Message Address Length) = 3 for IPv4, 15 for IPv6
msg-size = NN (octets - counting MsgHdr, AddrBlk, and AddrTLVs)
msg-hop-limit := outRREP.hopLimit
msg.tlvs-length := 0
if (outRREP.ackReq is required)
{ /* Build AckReq Message TLV */
msg.tlvs-length += ackReqMsgTlv total length
}
if (outRREP.metricType != DEFAULT_METRIC_TYPE)
{ /* Build MetricType Message TLV */
metricMsgTlv.value := outRREP.metricType
msg.tlvs-length += metricMsgTlv total length
}
/* Build Address Block */
num-addr := 2
AddrBlk := {outRREP.origAddr and outRREP.targAddr addresses} using prefix
length information from outRREP.targPrefixLen if necessary
/* TargSeqNum Address Block TLV */
targSeqNumAddrBlkTlv.value := outRREP.targSeqNum
targSeqNumAddrBlkTlv.thassingleindex := 1
targSeqNumAddrBlkTlv.index-start := 1
/* Build Metric Address Block TLV containing TargAddr metric */
metricAddrBlkTlv.value = outRREP.metric
metricAddrBlkTlv.thassingleindex := 1
metricAddrBlkTlv.index-start := 1
if (outRREP.validityTime is required)
{
/* Build VALIDITY_TIME Address Block TLV */
VALIDITY_TIMEAddrBlkTlv.value = outRREP.validityTime
VALIDITY_TIMEAddrBlkTlv.thassingleindex := 1
VALIDITY_TIMEAddrBlkTlv.index-start := 0
}
/* unicast RFC 5444 message to rte[OrigAddr].NextHop */
}
A.4. Example Algorithms for AODVv2 RERR Operations
RERR message parameters, where RERR can be inRERR or outRERR:
RERR.hopLimit := the maximum number of hops this RERR can traverse
RERR.pktSource := source IP of unforwardable packet (if present)
RERR.metricType := metric type for routes to unreachable destinations
RERR.unreachableAddressList[] := addresses of unreachable destinations
RERR.prefixLengthList[] := prefix lengths of unreachable destinations
RERR.seqNumList[] := sequence numbers for unreachable destinations
RERR.intf := the interface on which the RERR was received
A.4.1. Generate_RERR
There are two parts to this function, based on whether it was triggered
by an undeliverable packet or a broken link to neighboring AODVv2 router
Generate_RERR(triggerPkt, brokenLinkNbrIp)
{
if (triggerPkt != NULL)
error_type = undeliverable_packet;
else if (brokenLinkNbrIp != NULL)
error_type = broken_link;
switch (error_type)
{
case (broken_link):
/* a RERR will be required for each MetricType */
foreach metric type in use
{
num-broken-addr = 0
precursors[] := NULL
outRERR.hopLimit := MAX_HOPCOUNT
outRERR.metricType = the metric type for this loop
/* find routes which are now Invalid */
foreach (rte in route table)
{
if (brokenLinkNbrIp == rte.nextHop AND rte.MetricType ==
outRERR.metricType AND
(rte.State == Active OR (rte.State == Idle AND
ENABLE_IDLE_IN_RERR)))
{
rte.State := Invalid;
precursors += rte.Precursors (if any)
outRERR.unreachableAddressList[num-broken-addr] := rte.Address
outRERR.prefixLengthList[num-broken-addr] := rte.PrefixLength
outRERR.seqNumList[num-broken-addr] := rte.SeqNum
num-broken-addr := num-broken-addr + 1
}
}
if (num-broken-addr)
/* build and send RFC5444 message as below, then
repeat loop for other MetricTypes */
}
case (undeliverable_packet):
num-broken-addr=1
outRERR.hopLimit := MAX_HOPCOUNT
outRERR.pktSource := triggerPkt.srcIP or triggerPkt.targAddr if
packet was a RREP
/* optional to include outRERR.metricType */
outRERR.unreachableAddressList[0] := triggerPkt.destIP or
triggerPkt.origAddr if packet was a RREP
}
/* Build RFC 5444 message header fields */
msg-type = RERR (message is of type RERR)
MF (Message Flags) =4 (only msg-hop-limit field is present)
MAL (Message Address Length) = 3 for IPv4, 15 for IPv6
msg-size = NN (octets - counting MsgHdr, AddrBlk, and AddrTLVs)
msg-hop-limit := outRERR.hopLimit;
msg.tlvs-length = 0;
if (triggerPkt != NULL)
{ /* Build PktSource Message TLV */
pktSourceMessageTlv.value = outRERR.pktSource
msg.tlvs-length += pktSourceMessageTlv total length
}
if (outRERR.metricType != DEFAULT_METRIC_TYPE)
{ /* Build MetricType Message TLV */
metricMsgTlv.value := outRRER.metricType
msg.tlvs-length += metricMsgTlv total length
}
/* The remaining steps should add address, prefix length and sequence
number information for each UnreachableAddress, while conforming to the allowed
MTU. If the MTU is reached, a new message MUST be created */
/* Build Address Block */
num-addr := num-broken-addr;
AddrBlk := outRERR.unreachableAddressList[] using prefix length
information from outRERR.prefixLengthList[] if necessary
/* Add SeqNum Address Block TLV including index values */
seqNumAddrBlkTLV := outRERR.seqNumList[]
if (broken_link)
/* unicast to precursors found, or multicast RFC 5444 message to
LL-MANET-Routers */
else if (undeliverable_packet)
/* unicast RFC 5444 message to rte[outRERR.pktSource].NextHop */
}
A.4.2. Receive_RERR
Receive_RERR (inRERR)
{
if (inRERR does not contain msg_hop_limit and at least one
UnreachableAddress)
return;
if (inRERR.metricType is present but an unknown value)
return;
/* Extract inRERR values and copy relevant UnreachableAddresses and their
prefix lengths and sequence numbers to the outRERR */
num-broken-addr = 0;
precursors[] := NULL;
foreach (unreachableAddress in inRERR.unreachableAddressList)
{
if (unreachableAddress is not valid routable and unicast address)
continue;
/* find a matching route table entry, assume DEFAULT_METRIC_TYPE if no
MetricType included */
rte = Fetch_Route_Table_Entry(unreachableAddress,
inRERR.metricType)
if (rte == NULL)
continue;
if (rte.NextHop != inRERR.nbrIP OR rte.NextHopInterface !=
inRERR.intf)
continue;
if (unreachableAddress SeqNum entry (if known) < rte.SeqNum)
continue;
if (rte.State == Invalid) /* ignore routes if already invalid */
continue;
/* keep a note of all precursors of newly Invalid routes */
precursors += rte.Precursors (if any)
/* assume prefix length is address length if not included */
if (rte.PrefixLength != unreachableAddress prefixLength entry)
{
/* create a new route with unreachableAddress information */
invalidRte = Create_Route_Table_Entry(unreachableAddress,
unreachableAddress
prefixLength entry,
unreachableAddress seqNum entry,
inRERR.metricType)
invalidRte.State := Invalid
if (rte.PrefixLength > unreachableAddress prefixLength entry)
expunge_route(rte);
rte = invalidRte;
}
else if (rte.PrefixLength == unreachableAddress prefixLength
entry)
rte.State = Invalid;
outRERR.unreachableAddressList[num-broken-addr] := rte.Address
outRERR.prefixLengthList[num-broken-addr] := rte.PrefixLength
outRERR.seqNumList[num-broken-addr] := rte.SeqNum
num-broken-addr := num-broken-addr + 1
}
if (num-broken-addr)
Regenerate_RERR(outRERR, inRERR, precursors)
}
A.4.3. Regenerate_RERR
Regenerate_RERR (outRERR, inRERR, precursors)
{
/* Marshal parameters */
outRERR.hopLimit := inRERR.hopLimit - 1
if (outRERR.hopLimit == 0) /* don't regenerate */
return;
outRERR.pktSource := inRERR.pktSource (if included)
outRERR.metricType = inRERR.MetricType (if included) or
DEFAULT_METRIC_TYPE
/* UnreachableAddressList[], SeqNumList[], and PrefixLengthList[] are
already up-to-date */
/* Build RFC 5444 message header fields */
msg-type = RERR (message is of type RERR)
MF (Message Flags) = 4 (only msg-hop-limit field is present)
MAL (Message Address Length) = 3 for IPv4, 15 for IPv6
msg-size = NN (octets - counting MsgHdr, AddrBlk, and AddrTLVs)
msg-hop-limit := outRERR.hopLimit;
msg.tlvs-length := 0
if (outRERR.pktSource != NULL)
{
/* Build PktSource Message TLV */
pktSourceMessageTlv.value = outRERR.pktSource
msg.tlvs-length += pktSourceMessageTlv total length
}
if (outRERR.metricType != DEFAULT_METRIC_TYPE)
{
/* Build MetricType Message TLV */
metricMsgTlv.value := outRRER.metricType
msg.tlvs-length += metricMsgTlv total length
}
/* Build Address Block */
num-addr := num-broken-addr;
AddrBlk := outRERR.unreachableAddressList[] using prefix length
information from outRERR.prefixLengthList[] if necessary
/* Add SeqNum AddressBlock TLV including index values */
seqNumAddrTLV := outRERR.seqNumList[]
if (outRERR.pktSource != NULL) {
/* unicast RFC 5444 message to outRERR.pktSource */
} else if (number of precursors == 1) {
/* unicast RFC 5444 message to precursors[0] */
} else if (number of precursors > 1) {
/* unicast RFC 5444 message to all precursors, or multicast RFC 5444
message to RERR_PRECURSORS if preferable */
} else {
/* multicast RFC 5444 message to LL-MANET-Routers */
}
}
A.5. Example Algorithms for AODVv2 RREP_Ack Operations
A.5.1. Generate_RREP_Ack
Generate_RREP_Ack(inRREP)
{
/* assign RFC 5444 fields */
msgtype := RREP_Ack
MF (Message Flags) := 0
MAL (Message Address Length) := 3 for IPv4, 15 for IPv6
msg-hop-limit := 1;
msg-size := 5
/* unicast RFC 5444 message to inRREP.nbrIP */
}
A.5.2. Receive_RREP_Ack
Receive_RREP_Ack(inRREP_Ack)
{
/* cancel timeout event for the node sending RREP_Ack */
}
A.5.3. Timeout_RREP_Ack
Timeout_RREP_Ack(outRREP)
{
/* insert unresponsive node into blacklist */
}
Other related posts:
