RFC 7181
The Optimized Link State Routing Protocol Version 2
16. TC Messages
This protocol defines, and hence owns, the TC Message Type (see Section 24). Thus, as specified in [RFC5444], this protocol generates and transmits all TC messages, receives all TC messages, and is responsible for determining whether and how each TC message is to be processed (updating the Topology Information Base) and/or forwarded, according to this specification.16.1. TC Message Generation
A TC message is a message as defined in [RFC5444]. A generated TC message MUST contain the following elements as defined in [RFC5444]: o A message originator address, recording this router's originator address. This MUST use a <msg-orig-addr> element. o <msg-seq-num> element containing the message sequence number. o A <msg-hop-limit> element, containing TC_HOP_LIMIT. A router MAY use the same or different values of TC_HOP_LIMIT in its TC messages (see Section 5.4.7). o A <msg-hop-count> element, containing zero, if the message contains a TLV with either Type = VALIDITY_TIME or Type = INTERVAL_TIME (as specified in [RFC5497]) indicating more than one time value according to distance. A TC message MAY contain such a <msg-hop-count> element even if it does not need to. o A single Message TLV with Type := CONT_SEQ_NUM and Value := ANSN from the Neighbor Information Base. If the TC message is complete, then this Message TLV MUST have Type Extension := COMPLETE; otherwise, it MUST have Type Extension := INCOMPLETE. (Exception: a TC message MAY omit such a Message TLV if the TC message does not include any address objects with an associated Address Block TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY.) o A single Message TLV with Type := VALIDITY_TIME, as specified in [RFC5497]. If all TC messages are sent with the same hop limit, then this TLV MUST have a value encoding the period T_HOLD_TIME.
If TC messages are sent with different hop limits (more than one
value of TC_HOP_LIMIT), then this TLV MUST specify times that vary
with the number of hops appropriate to the chosen pattern of TC
message hop limits, as specified in [RFC5497]; these times SHOULD
be appropriate multiples of T_HOLD_TIME. The options included in
[RFC5497] for representing zero and infinite times MUST NOT be
used.
o If the TC message is complete, all network addresses that are the
N_orig_addr of a Neighbor Tuple with N_advertised = true, MUST be
represented by address objects in one or more Address Blocks. If
the TC message is incomplete, then any such address objects MAY be
included. At least one copy of each such address object that is
included MUST be associated with an Address Block TLV with Type :=
NBR_ADDR_TYPE and Value := ORIGINATOR or with Value :=
ROUTABLE_ORIG if that address object is also to be associated with
Value = ROUTABLE.
o If the TC message is complete, all routable addresses that are in
the N_neighbor_addr_list of a Neighbor Tuple with N_advertised =
true MUST be represented by address objects in one or more Address
Blocks. If the TC message is incomplete, then any such address
objects MAY be included. At least one copy of each such address
object MUST be associated with an Address Block TLV with Type =
NBR_ADDR_TYPE and Value = ROUTABLE or with Value = ROUTABLE_ORIG
if also to be associated with Value = ORIGINATOR. At least one
copy of each such address object MUST be associated with an
Address Block TLV with Type = LINK_METRIC and Type Extension =
LINK_METRIC_TYPE indicating an outgoing neighbor metric with value
equal to the corresponding N_out_metric.
o If the TC message is complete, all network addresses that are the
AL_net_addr of a Local Attached Network Tuple MUST be represented
by address objects in one or more Address Blocks. If the TC
message is incomplete, then any such address objects MAY be
included. At least one copy of each such address object MUST be
associated with an Address Block TLV with Type := GATEWAY and
Value := AN_dist. At least one copy of each such address object
MUST be associated with an Address Block TLV with Type =
LINK_METRIC and Type Extension = LINK_METRIC_TYPE indicating an
outgoing neighbor metric equal to the corresponding AL_metric.
A TC message MAY contain:
o A single Message TLV with Type := INTERVAL_TIME, as specified in
[RFC5497]. If all TC messages are sent with the same hop limit,
then this TLV MUST have a value encoding the period TC_INTERVAL.
If TC messages are sent with different hop limits, then this TLV
MUST specify times that vary with the number of hops appropriate
to the chosen pattern of TC message hop limits, as specified in
[RFC5497]; these times MUST be appropriate multiples of
TC_INTERVAL. The options included in [RFC5497] for representing
zero and infinite times MUST NOT be used.
16.2. TC Message Transmission
A router with one or more OLSRv2 interfaces, and with any Neighbor
Tuples with N_advertised = true, or with a non-empty Local Attached
Network Set MUST generate TC messages. A router that does not have
such information to advertise MUST also generate "empty" TC messages
for a period A_HOLD_TIME after it last generated a non-empty TC
message.
Complete TC messages are generated and transmitted periodically on
all OLSRv2 interfaces, with a default interval between two
consecutive TC message transmissions by the same router of
TC_INTERVAL.
TC messages MAY be generated in response to a change in the
information that they are to advertise, indicated by a change in the
ANSN in the Neighbor Information Base. In this case, a router MAY
send a complete TC message and, if so, MAY restart its TC message
schedule. Alternatively, a router MAY send an incomplete TC message
with at least the newly advertised network addresses (i.e., not
previously, but now, an N_orig_addr or in an N_neighbor_addr_list in
a Neighbor Tuple with N_advertised = true or an AL_net_addr) in its
Address Blocks, with associated Address Block TLV(s). Note that a
router cannot report removal of advertised content using an
incomplete TC message.
When sending a TC message in response to a change of advertised
network addresses, a router MUST respect a minimum interval of
TC_MIN_INTERVAL between sending TC messages (complete or incomplete)
and a maximum interval of TC_INTERVAL between sending complete TC
messages. Thus, a router MUST NOT send an incomplete TC message if
within TC_MIN_INTERVAL of the next scheduled time to send a complete
TC message.
The generation of TC messages, whether scheduled or triggered by a
change of contents, MAY be jittered as described in [RFC5148]. The
values of MAXJITTER used MUST be:
o TP_MAXJITTER for periodic TC message generation;
o TT_MAXJITTER for responsive TC message generation.
16.3. TC Message Processing
On receiving a TC message on an OLSRv2 interface, the receiving router MUST then follow the processing and forwarding procedures defined in Section 14. If the message is considered for processing (Section 14.2), then a router MUST first check if the message is invalid for processing by this router, as defined in Section 16.3.1. A router MAY make a similar check before considering a message for forwarding; it MUST check the aspects that apply to elements in the Message Header. If the TC message is not invalid, then the processing specific to TC Message Type, described in Section 16.3.2, MUST be applied. This will update its appropriate Interface Information Bases and its Router Information Base. Following this, if there are any changes in these Information Bases, then the processing in Section 17 MUST be performed.16.3.1. TC Message Discarding
A received TC message is invalid for processing by this router if the message: o Has an address length specified in the Message Header that is not equal to the length of the addresses used by this router. o Does not include a message originator address and a message sequence number. o Does not include a hop count and contains a multi-value TLV with Type = VALIDITY_TIME or Type = INTERVAL_TIME, as defined in [RFC5497]. o Does not have exactly one Message TLV with Type = VALIDITY_TIME. o Has more than one Message TLV with Type = INTERVAL_TIME. o Does not have a Message TLV with Type = CONT_SEQ_NUM and Type Extension = COMPLETE or Type Extension = INCOMPLETE and contains at least one address object associated with an Address Block TLV with Type = NBR_ADDR_TYPE or Type = GATEWAY. o Has more than one Message TLV with Type = CONT_SEQ_NUM and Type Extension = COMPLETE or Type Extension = INCOMPLETE. o Has a message originator address that is partially owned by this router.
o Includes any address object with a prefix length that is not
maximal (equal to the address length, in bits), associated with an
Address Block TLV with Type = NBR_ADDR_TYPE and Value = ORIGINATOR
or Value = ROUTABLE_ORIG.
o Includes any address object that represents a non-routable
address, associated with an Address Block TLV with Type =
NBR_ADDR_TYPE and Value = ROUTABLE or Value = ROUTABLE_ORIG.
o Includes any address object associated with an Address Block TLV
with Type = NBR_ADDR_TYPE or Type = GATEWAY that also represents
the message's originator address.
o Includes any address object (including different copies of an
address object in the same or different Address Blocks) that is
associated with an Address Block TLV with Type = NBR_ADDR_TYPE or
Type = GATEWAY that is also associated with more than one outgoing
neighbor metric using a TLV with Type = LINK_METRIC and Type
Extension = LINK_METRIC_TYPE.
o Associates any address object (including different copies of an
address object in the same or different Address Blocks) with more
than one single hop count value using one or more Address Block
TLV(s) with Type = GATEWAY.
o Associates any address object (including different copies of an
address object in the same or different Address Blocks) with
Address Block TLVs with Type = NBR_ADDR_TYPE and Type = GATEWAY.
A router MAY recognize additional reasons for identifying that a
message is invalid. An invalid message MUST be silently discarded,
without updating the router's Information Bases.
Note that a router that acts inconsistently, for example, rejecting
TC messages "at random", may cause parts of the network to not be
able to communicate with other parts of the network. It is
RECOMMENDED that such "additional reasons for identifying that a
message is invalid" be a consistent network-wide policy (e.g., as
part of a security policy), implemented on all participating routers.
16.3.2. TC Message Processing Definitions
When, according to Section 14.2, a TC message is to be "processed according to its type", this means that: o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM and Type Extension = COMPLETE, then processing according to Section 16.3.3 and then according to Section 16.3.4 is carried out. o If the TC message contains a Message TLV with Type = CONT_SEQ_NUM and Type Extension = INCOMPLETE, then only processing according to Section 16.3.3 is carried out. For the purposes of the TC message processing in Section 16.3.3 and Section 16.3.4: o "validity time" is calculated from a VALIDITY_TIME Message TLV in the TC message according to the specification in [RFC5497]. All information in the TC message has the same validity time. o "received ANSN" is defined as being the value of a Message TLV with Type = CONT_SEQ_NUM. o "associated metric value" is defined for any address in the TC message as being either the outgoing neighbor metric value indicated by a TLV with Type = LINK_METRIC and Type Extension = LINK_METRIC_TYPE that is associated with any address object in the TC message that is equal to that address or as UNKNOWN_METRIC otherwise. (Note that the rules in Section 16.3.1 make this definition unambiguous.) o Comparisons of sequence numbers are carried out as specified in Section 21.16.3.3. Initial TC Message Processing
The TC message is processed as follows: 1. The Advertising Remote Router Set is updated according to Section 16.3.3.1. If the TC message is indicated as discarded in that processing, then the following steps are not carried out. 2. The Router Topology Set is updated according to Section 16.3.3.2. 3. The Routable Address Topology Set is updated according to Section 16.3.3.3.
4. The Attached Network Set is updated according to
Section 16.3.3.4.
16.3.3.1. Populating the Advertising Remote Router Set
The router MUST update its Advertising Remote Router Set as follows:
1. If there is an Advertising Remote Router Tuple with:
* AR_orig_addr = message originator address; AND
* AR_seq_number > received ANSN,
then the TC message MUST be discarded.
2. Otherwise:
1. If there is no Advertising Remote Router Tuple such that:
+ AR_orig_addr = message originator address;
then create an Advertising Remote Router Tuple with:
+ AR_orig_addr := message originator address.
2. This Advertising Remote Router Tuple (existing or new) is
then modified as follows:
+ AR_seq_number := received ANSN;
+ AR_time := current time + validity time.
16.3.3.2. Populating the Router Topology Set
The router MUST update its Router Topology Set as follows:
1. For each address (henceforth, advertised address) that
corresponds to one or more address objects with an associated
Address Block TLV with Type = NBR_ADDR_TYPE and Value =
ORIGINATOR or Value = ROUTABLE_ORIG and that is not partially
owned by this router, perform the following processing:
1. If the associated metric is UNKNOWN_METRIC, then remove any
Router Topology Tuple such that:
+ TR_from_orig_addr = message originator address; AND
+ TR_to_orig_addr = advertised address.
2. Otherwise, if there is no Router Topology Tuple such that:
+ TR_from_orig_addr = message originator address; AND
+ TR_to_orig_addr = advertised address,
then create a new Router Topology Tuple with:
+ TR_from_orig_addr := message originator address;
+ TR_to_orig_addr := advertised address.
3. This Router Topology Tuple (existing or new) is then modified
as follows:
+ TR_seq_number := received ANSN;
+ TR_metric := associated link metric;
+ TR_time := current time + validity time.
16.3.3.3. Populating the Routable Address Topology Set
The router MUST update its Routable Address Topology Set as follows:
1. For each network address (henceforth, advertised address) that
corresponds to one or more address objects with an associated
Address Block TLV with Type = NBR_ADDR_TYPE and Value = ROUTABLE
or Value = ROUTABLE_ORIG and that is not partially owned by this
router, perform the following processing:
1. If the associated metric is UNKNOWN_METRIC, then remove any
Routable Address Topology Tuple such that:
+ TA_from_orig_addr = message originator address; AND
+ TA_dest_addr = advertised address.
2. Otherwise, if there is no Routable Address Topology Tuple
such that:
+ TA_from_orig_addr = message originator address; AND
+ TA_dest_addr = advertised address,
then create a new Routable Address Topology Tuple with:
+ TA_from_orig_addr := message originator address;
+ TA_dest_addr := advertised address.
3. This Routable Address Topology Tuple (existing or new) is
then modified as follows:
+ TA_seq_number := received ANSN;
+ TA_metric := associated link metric;
+ TA_time := current time + validity time.
16.3.3.4. Populating the Attached Network Set
The router MUST update its Attached Network Set as follows:
1. For each network address (henceforth, attached address) that
corresponds to one or more address objects with an associated
Address Block TLV with Type = GATEWAY and that is not fully owned
by this router, perform the following processing:
1. If the associated metric is UNKNOWN_METRIC, then remove any
Attached Network Tuple such that:
+ AN_net_addr = attached address; AND
+ AN_orig_addr = message originator address.
2. Otherwise, if there is no Attached Network Tuple such that:
+ AN_net_addr = attached address; AND
+ AN_orig_addr = message originator address,
then create a new Attached Network Tuple with:
+ AN_net_addr := attached address;
+ AN_orig_addr := message originator address.
3. This Attached Network Tuple (existing or new) is then
modified as follows:
+ AN_seq_number := received ANSN;
+ AN_dist := the Value of the associated GATEWAY TLV;
+ AN_metric := associated link metric;
+ AN_time := current time + validity time.
16.3.4. Completing TC Message Processing
The TC message is processed as follows:
1. The Router Topology Set is updated according to Section 16.3.4.1.
2. The Routable Address Topology Set is updated according to
Section 16.3.4.2.
3. The Attached Network Set is updated according to
Section 16.3.4.3.
16.3.4.1. Purging the Router Topology Set
The Router Topology Set MUST be updated as follows:
1. Any Router Topology Tuples with:
* TR_from_orig_addr = message originator address; AND
* TR_seq_number < received ANSN,
MUST be removed.
16.3.4.2. Purging the Routable Address Topology Set
The Routable Address Topology Set MUST be updated as follows:
1. Any Routable Address Topology Tuples with:
* TA_from_orig_addr = message originator address; AND
* TA_seq_number < received ANSN,
MUST be removed.
16.3.4.3. Purging the Attached Network Set
The Attached Network Set MUST be updated as follows: 1. Any Attached Network Tuples with: * AN_orig_addr = message originator address; AND * AN_seq_number < received ANSN, MUST be removed.17. Information Base Changes
The changes described in the following sections MUST be carried out when any Information Base changes as indicated.17.1. Originator Address Changes
If the router changes its originator address, then: 1. If there is no Originator Tuple with: * O_orig_addr = old originator address then create an Originator Tuple with: * O_orig_addr := old originator address The Originator Tuple (existing or new) with: * O_orig_addr = new originator address is then modified as follows: * O_time := current time + O_HOLD_TIME17.2. Link State Changes
The consistency of a Link Tuple MUST be maintained according to the following rules, in addition to those in [RFC6130]: o If L_status = HEARD or L_status = SYMMETRIC, then L_in_metric MUST be set (by a process outside this specification). o If L_status != SYMMETRIC, then set L_mpr_selector := false.
o If L_out_metric = UNKNOWN_METRIC, then L_status MUST NOT equal
SYMMETRIC; set L_SYM_time := EXPIRED if this would otherwise be
the case.
17.3. Neighbor State Changes
The consistency of a Neighbor Tuple MUST be maintained according to
the following rules, in addition to those in [RFC6130]:
1. If N_symmetric = true, then N_in_metric MUST equal the minimum
value of all L_in_metric of corresponding Link Tuples with
L_status = SYMMETRIC and L_in_metric != UNKNOWN_METRIC. If there
are no such Link Tuples, then N_in_metric MUST equal
UNKNOWN_METRIC.
2. If N_symmetric = true, then N_out_metric MUST equal the minimum
value of all L_out_metric of corresponding Link Tuples with
L_status = SYMMETRIC and L_out_metric != UNKNOWN_METRIC. If
there are no such Link Tuples, then N_out_metric MUST equal
UNKNOWN_METRIC.
3. If N_symmetric = false, then N_flooding_mpr, N_routing_mpr,
N_mpr_selector, and N_advertised MUST all be equal to false.
4. If N_mpr_selector = true, then N_advertised MUST be equal to
true.
5. If N_symmetric = true, N_out_metric != UNKNOWN_METRIC and
N_mpr_selector = false, then a router MAY select N_advertised =
true or N_advertised = false. The more neighbors that are
advertised, the larger TC messages become, but the more
redundancy is available for routing. A router SHOULD consider
the nature of its network in making such a decision and SHOULD
avoid unnecessary changes in advertising status, which may result
in unnecessary changes to routing.
17.4. Advertised Neighbor Changes
The router MUST increment the ANSN in the Neighbor Information Base
whenever:
1. Any Neighbor Tuple changes its N_advertised value, or any
Neighbor Tuple with N_advertised = true is removed.
2. Any Neighbor Tuple with N_advertised = true changes its
N_orig_addr or has any routable address added to or removed from
N_neighbor_addr_list.
3. Any Neighbor Tuple with N_advertised = true has N_out_metric
changed.
4. There is any change to the Local Attached Network Set.
17.5. Advertising Remote Router Tuple Expires
The Router Topology Set, the Routable Address Topology Set, and the
Attached Network Set MUST be changed when an Advertising Remote
Router Tuple expires (AR_time is reached). The following changes are
required before the Advertising Remote Router Tuple is removed:
1. All Router Topology Tuples with:
* TR_from_orig_addr = AR_orig_addr of the Advertising Remote
Router Tuple
are removed.
2. All Routable Address Topology Tuples with:
* TA_from_orig_addr = AR_orig_addr of the Advertising Remote
Router Tuple
are removed.
3. All Attached Network Tuples with:
* AN_orig_addr = AR_orig_addr of the Advertising Remote Router
Tuple
are removed.
17.6. Neighborhood Changes and MPR Updates
The sets of symmetric 1-hop neighbors selected as flooding MPRs and
routing MPRs MUST satisfy the conditions defined in Section 18. To
ensure this:
1. The set of flooding MPRs of a router MUST be recalculated if:
* A Link Tuple is added with L_status = SYMMETRIC and
L_out_metric != UNKNOWN_METRIC; OR
* A Link Tuple with L_status = SYMMETRIC and L_out_metric !=
UNKNOWN_METRIC is removed; OR
* A Link Tuple with L_status = SYMMETRIC and L_out_metric !=
UNKNOWN_METRIC changes to having L_status = HEARD, L_status =
LOST, or L_out_metric = UNKNOWN_METRIC; OR
* A Link Tuple with L_status = HEARD or L_status = LOST changes
to having L_status = SYMMETRIC and L_out_metric !=
UNKNOWN_METRIC; OR
* The flooding MPR selection process uses metric values (see
Section 18.4) and the L_out_metric of any Link Tuple with
L_status = SYMMETRIC changes; OR
* The N_will_flooding of a Neighbor Tuple with N_symmetric =
true and N_out_metric != UNKNOWN_METRIC changes from
WILL_NEVER to any other value; OR
* The N_will_flooding of a Neighbor Tuple with N_flooding_mpr =
true changes to WILL_NEVER from any other value; OR
* The N_will_flooding of a Neighbor Tuple with N_symmetric =
true, N_out_metric != UNKNOWN_METRIC, and N_flooding_mpr =
false changes to WILL_ALWAYS from any other value; OR
* A 2-Hop Tuple with N2_out_metric != UNKNOWN_METRIC is added or
removed; OR
* The N2_out_metric of any 2-Hop Tuple changes and either the
flooding MPR selection process uses metric values (see
Section 18.4) or the change is to or from UNKNOWN_METRIC.
2. Otherwise, the set of flooding MPRs of a router MAY be
recalculated if the N_will_flooding of a Neighbor Tuple with
N_symmetric = true changes in any other way; it SHOULD be
recalculated if N_flooding_mpr = false and this is an increase in
N_will_flooding or if N_flooding_mpr = true and this is a
decrease in N_will_flooding.
3. The set of routing MPRs of a router MUST be recalculated if:
* A Neighbor Tuple is added with N_symmetric = true and
N_in_metric != UNKNOWN_METRIC; OR
* A Neighbor Tuple with N_symmetric = true and N_in_metric !=
UNKNOWN_METRIC is removed; OR
* A Neighbor Tuple with N_symmetric = true and N_in_metric !=
UNKNOWN_METRIC changes to having N_symmetric = false; OR
* A Neighbor Tuple with N_symmetric = false changes to having
N_symmetric = true and N_in_metric != UNKNOWN_METRIC; OR
* The N_in_metric of any Neighbor Tuple with N_symmetric = true
changes; OR
* The N_will_routing of a Neighbor Tuple with N_symmetric = true
and N_in_metric != UNKNOWN_METRIC changes from WILL_NEVER to
any other value; OR
* The N_will_routing of a Neighbor Tuple with N_routing_mpr =
true changes to WILL_NEVER from any other value; OR
* The N_will_routing of a Neighbor Tuple with N_symmetric =
true, N_in_metric != UNKNOWN_METRIC and N_routing_mpr = false
changes to WILL_ALWAYS from any other value; OR
* A 2-Hop Tuple with N2_in_metric != UNKNOWN_METRIC is added or
removed; OR
* The N2_in_metric of any 2-Hop Tuple changes.
4. Otherwise, the set of routing MPRs of a router MAY be
recalculated if the N_will_routing of a Neighbor Tuple with
N_symmetric = true changes in any other way; it SHOULD be
recalculated if N_routing_mpr = false and this is an increase in
N_will_routing or if N_routing_mpr = true and this is a decrease
in N_will_routing.
If either set of MPRs of a router is recalculated, this MUST be as
described in Section 18.
17.7. Routing Set Updates
The Routing Set MUST be updated, as described in Section 19, when
changes in the Local Information Base, the Neighborhood Information
Base, or the Topology Information Base indicate a change (including
of any potentially used outgoing neighbor metric values) of the known
symmetric links and/or attached networks in the MANET, hence changing
the Topology Graph. It is sufficient to consider only changes that
affect at least one of:
o The Local Interface Set for an OLSRv2 interface, if the change
removes any network address in an I_local_iface_addr_list. In
this case, unless the OLSRv2 interface is removed, it may not be
necessary to do more than replace such network addresses, if used,
by an alternative network address from the same
I_local_iface_addr_list.
o The Local Attached Set, if the change removes any AL_net_addr that
is also an AN_net_addr. In this case, it may not be necessary to
do more than add Routing Tuples with R_dest_addr equal to that
AN_net_addr.
o The Link Set of any OLSRv2 interface, considering only Link Tuples
that have, or just had, L_status = SYMMETRIC and L_out_metric !=
UNKNOWN_METRIC (including removal of such Link Tuples).
o The Neighbor Set of the router, considering only Neighbor Tuples
that have, or just had, N_symmetric = true and N_out_metric !=
UNKNOWN_METRIC and do not have N_orig_addr = unknown.
o The 2-Hop Set of any OLSRv2 interface, if used in the creation of
the Routing Set and if the change affects any 2-Hop Tuples with
N2_out_metric != UNKNOWN_METRIC.
o The Router Topology Set of the router.
o The Routable Address Topology Set of the router.
o The Attached Network Set of the router.
18. Selecting MPRs
Each router MUST select, from among its willing symmetric 1-hop
neighbors, two subsets of these routers, as flooding and routing
MPRs. This selection is recorded in the router's Neighbor Set and
reported in the router's HELLO messages. Routers MAY select their
MPRs by any process that satisfies the conditions that follow, which
may, but need not, use the organization of the data described.
Routers can freely interoperate whether they use the same or
different MPR selection algorithms.
Only flooding MPRs forward control messages flooded through the
MANET, thus effecting a flooding reduction, an optimization of the
flooding mechanism, known as MPR flooding. Routing MPRs are used to
effect a topology reduction in the MANET. (If no such reduction is
required, then a router can select all of its relevant neighbors as
routing MPRs.) Consequently, while it is not essential that these
two sets of MPRs are minimal, keeping the numbers of MPRs small
ensures that the overhead of this protocol is kept to a minimum.
18.1. Overview
MPRs are selected according to the following steps, defined in the following sections: o A data structure known as a Neighbor Graph is defined. o The properties of an MPR Set derived from a Neighbor Graph are defined. Any algorithm that creates an MPR Set that satisfies these properties is a valid MPR selection algorithm. An example algorithm that creates such an MPR Set is given in Appendix B. o How to create a Neighbor Graph for each interface based on the corresponding Interface Information Base is defined, and how to combine the resulting MPR Sets to determine the router's flooding MPRs and record those in the router's Neighbor Set are described. o How to create a single Neighbor Graph based on all Interface Information Bases and the Neighbor Information Base is defined, and how to record the resulting MPR Set as the router's routing MPRs in the router's Neighbor Set is described. o A specification as to when MPRs MUST be calculated is given. When a router selects its MPRs, it MAY consider any characteristics of its neighbors that it is aware of. In particular, it SHOULD consider the willingness of the neighbor, as recorded by the corresponding N_will_flooding or N_will_routing value, as appropriate, preferring neighbors with higher values. (Note that willingness values equal to WILL_NEVER and WILL_ALWAYS are always considered, as described.) However, a router MAY consider other characteristics to have a greater significance. Each router MAY select its flooding and routing MPRs independently of each other or coordinate its selections. A router MAY make its MPR selections independently of the MPR selection by other routers, or it MAY, for example, give preference to routers that either are, or are not, already selected as MPRs by other routers.18.2. Neighbor Graph
A Neighbor Graph is a structure defined here as consisting of sets N1 and N2 and some associated metric and willingness values. Elements of set N1 represent willing symmetric 1-hop neighbors, and elements of set N2 represent addresses of a symmetric 2-hop neighbor.
A Neighbor Graph has the following properties:
o It contains two disjoint sets N1 and N2.
o For each element x in N1, there is an associated willingness value
W(x) such that WILL_NEVER < W(x) <= WILL_ALWAYS.
o For each element x in N1, there is an associated metric d1(x) > 0.
o For some elements y in N2, there is an associated metric d1(y) >
0. (Other elements y in N2 have undefined d1(y); this may be
considered to be infinite.)
o For each element x in N1, there is a subset N2(x) of elements of
N2; this subset may be empty. For each x in N1 and each y in
N2(x), there is an associated metric d2(x,y) > 0. (For other x in
N1 and y in N2, d2(x,y) is undefined and may be considered
infinite.)
o N2 is equal to the union of all the N2(x) for all x in N1, i.e.,
for each y in N2, there is at least one x in N1 such that y is in
N2(x).
It is convenient to also define:
o For each y in N2, the set N1(y) that contains x in N1 if and only
if y is in N2(x). From the final property above, N1(y) is not
empty.
o For each x in N1 and y in N2, if d2(x,y) is defined, then d(x,y)
:= d1(x)+d2(x,y); otherwise, d(x,y) is not defined. (Thus, d(x,y)
is defined if y is in N2(x) or, equivalently, if x is in N1(y).)
o For any subset S of N1 and for each y in N2, the metric d(y,S) is
the minimum value of d1(y), if defined, and of all d(x,y) for x in
N1(y) and in S. If there are no such metrics to take the minimum
value of, then d(y,S) is undefined (may be considered to be
infinite). From the final property above, d(y,N1) is defined for
all y.
18.3. MPR Properties
Given a Neighbor Graph as defined in Section 18.2, an MPR Set for
that Neighbor Graph is a subset M of the set N1 that satisfies the
following properties:
o If x in N1 has W(x) = WILL_ALWAYS, then x is in M.
o For any y in N2 that does not have a defined d1(y), there is at
least one element in M that is also in N1(y). This is equivalent
to the requirement that d(y,M) is defined.
o For any y in N2, d(y,M) = d(y,N1).
These properties reflect that the MPR Set consists of a set of
symmetric 1-hop neighbors that cover all the symmetric 2-hop
neighbors and that they do so retaining a minimum distance route
(1-hop, if present, or 2-hop) to each symmetric 2-hop neighbor.
Note that if M is an MPR Set, then so is any subset of N1 that
contains M; also note that N1 is always an MPR Set. An MPR Set may
be empty but cannot be empty if N2 contains any elements y that do
not have a defined d1(y).
18.4. Flooding MPRs
Whenever flooding MPRs are to be calculated, an implementation MUST
determine and record a set of flooding MPRs that is equivalent to one
calculated as described in this section.
The calculation of flooding MPRs need not use link metrics or,
equivalently, may use link metrics with a fixed value, here taken to
be 1. However, links with unknown metric (L_out_metric =
UNKNOWN_METRIC) MUST NOT be used even if link metrics are otherwise
not used.
Routers MAY make individual decisions as to whether to use link
metrics for the calculation of flooding MPRs. A router MUST use the
same approach to the choice of whether to use link metrics for all
links, i.e., in the cases indicated by A or B, the same choice MUST
be made in each case.
For each OLSRv2 interface (the "current interface"), define a
Neighbor Graph as defined in Section 18.2 according to the following:
o Define a reachable Link Tuple to be a Link Tuple in the Link Set
for the current interface with L_status = SYMMETRIC and
L_out_metric != UNKNOWN_METRIC.
o Define an allowed Link Tuple to be a reachable Link Tuple whose
corresponding Neighbor Tuple has N_will_flooding > WILL_NEVER.
o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set
for the current interface for which N2_out_metric !=
UNKNOWN_METRIC and there is an allowed Link Tuple with
L_neighbor_iface_addr_list = N2_neighbor_iface_addr_list.
o Define an element of N1 for each allowed Link Tuple. This then
defines the corresponding Link Tuple for each element of N1 and
the corresponding Neighbor Tuple for each element of N1, being the
Neighbor Tuple corresponding to that Link Tuple.
o For each element x in N1, define W(x) := N_will_flooding of the
corresponding Neighbor Tuple.
o For each element x in N1, define d1(x) as either:
A. L_out_metric of the corresponding Link Tuple; OR
B. 1.
o Define an element of N2 for each network address that is the
N2_2hop_addr of one or more allowed 2-Hop Tuples. This then
defines the corresponding address for each element of N2.
o For each element y in N2, if the corresponding address is in the
N_neighbor_addr_list of a Neighbor Tuple that corresponds to one
or more reachable Link Tuples, then define d1(y) as either:
A. the minimum value of the L_out_metric of those Link Tuples; OR
B. 1.
Otherwise, d1(y) is not defined. In the latter case, where d1(y)
:= 1, all such y in N2 may instead be removed from N2.
o For each element x in N1, define N2(x) as the set of elements y in
N2 whose corresponding address is the N2_2hop_addr of an allowed
2-Hop Tuple that has N2_neighbor_iface_addr_list =
L_neighbor_iface_addr_list of the Link Tuple corresponding to x.
For all such x and y, define d2(x,y) as either:
A. N2_out_metric of that 2-Hop Tuple; OR
B. 1.
It is up to an implementation to decide how to label each element of
N1 or N2. For example, an element of N1 may be labeled with one or
more addresses from the corresponding L_neighbor_iface_addr_list or
with a pointer or reference to the corresponding Link Tuple.
Using these Neighbor Graphs, flooding MPRs are selected and recorded
by:
o For each OLSRv2 interface, determine an MPR Set as specified in
Section 18.3.
o A Neighbor Tuple represents a flooding MPR and has N_flooding_mpr
:= true (otherwise, N_flooding_mpr := false) if and only if that
Neighbor Tuple corresponds to an element in an MPR Set created for
any interface as described above. That is, the overall set of
flooding MPRs is the union of the sets of flooding MPRs for all
OLSRv2 interfaces.
A router MAY select its flooding MPRs for each OLSRv2 interface
independently, or it MAY coordinate its MPR selections across its
OLSRv2 interfaces, as long as the required condition is satisfied for
each OLSRv2 interface. One such coordinated approach is to process
the OLSRv2 interfaces sequentially and, for each OLSRv2 interface,
start with flooding MPRs selected (and not removable) if the neighbor
has been already selected as an MPR for an OLSRv2 interface that has
already been processed. The algorithm specified in Appendix B can be
used in this way.
18.5. Routing MPRs
Whenever routing MPRs are to be calculated, an implementation MUST
determine and record a set of routing MPRs that is equivalent to one
calculated as described in this section.
Define a single Neighbor Graph as defined in Section 18.2 according
to the following:
o Define a reachable Neighbor Tuple to be a Neighbor Tuple with
N_symmetric = true and N_in_metric != UNKNOWN_METRIC.
o Define an allowed Neighbor Tuple to be a reachable Neighbor Tuple
with N_will_routing > WILL_NEVER.
o Define an allowed 2-Hop Tuple to be a 2-Hop Tuple in the 2-Hop Set
for any OLSRv2 interface with N2_in_metric != UNKNOWN_METRIC and
for which there is an allowed Neighbor Tuple with
N_neighbor_addr_list containing N2_neighbor_iface_addr_list.
o Define an element of N1 for each allowed Neighbor Tuple. This
then defines the corresponding Neighbor Tuple for each element of
N1.
o For each element x in N1, define W(x) := N_will_routing of the
corresponding Neighbor Tuple.
o For each element x in N1, define d1(x) := N_in_metric of the
corresponding Neighbor Tuple.
o Define an element of N2 for each network address that is the
N2_2hop_addr of one or more allowed 2-Hop Tuples. This then
defines the corresponding address for each element of N2.
o For each element y in N2, if the corresponding address is in the
N_neighbor_addr_list of a reachable Neighbor Tuple, then define
d1(y) to be the N_in_metric of that Neighbor Tuple; otherwise,
d1(y) is not defined.
o For each element x in N1, define N2(x) as the set of elements y in
N2 whose corresponding address is the N2_2hop_addr of an allowed
2-Hop Tuple that has N2_neighbor_iface_addr_list contained in
N_neighbor_addr_list of the Neighbor Tuple corresponding to x.
For all such x and y, define d2(x,y) := N2_out_metric of that
2-Hop Tuple.
It is up to an implementation to decide how to label each element of
N1 or N2. For example, an element of N1 may be labeled with one or
more addresses from the corresponding N_neighbor_addr_list or with a
pointer or reference to the corresponding Neighbor Tuple.
Using these Neighbor Graphs, routing MPRs are selected and recorded
according to the following:
o Determine an MPR Set as specified in Section 18.3.
o A Neighbor Tuple represents a routing MPR and has N_routing_mpr :=
true (otherwise, N_routing_mpr := false) if and only if that
Neighbor Tuple corresponds to an element in the MPR Set created as
described above.
18.6. Calculating MPRs
A router MUST recalculate each of its sets of MPRs whenever the
currently selected set of MPRs does not still satisfy the required
conditions. It MAY recalculate its MPRs if the current set of MPRs
is still valid but could be more efficient. Sufficient conditions to
recalculate a router's sets of MPRs are given in Section 17.6.
19. Routing Set Calculation
The Routing Set of a router is populated with Routing Tuples that represent paths from that router to all destinations in the network. These paths are calculated based on the Network Topology Graph, which is constructed from information in the Information Bases, obtained via HELLO and TC message exchange. Changes to the Routing Set do not require any messages to be transmitted. The state of the Routing Set SHOULD, however, be reflected in the IP routing table by adding and removing entries from that routing table as appropriate. Only appropriate Routing Tuples (in particular only those that represent local links or paths to routable addresses) need be reflected in the IP routing table.19.1. Network Topology Graph
The Network Topology Graph is formed from information from the router's Local Interface Set, Link Sets for OLSRv2 interfaces, Neighbor Set, Router Topology Set, Routable Address Topology Set, and Attached Network Set. The Network Topology Graph MAY also use information from the router's 2-Hop Sets for OLSRv2 interfaces. The Network Topology Graph forms the router's topological view of the network in the form of a directed graph. Each edge in that graph has a metric value. The Network Topology Graph has a "backbone" (within which minimum total metric routes will be constructed) containing the following edges: o Edges X -> Y for all possible Y, and one X per Y, such that: * Y is the N_orig_addr of a Neighbor Tuple; AND * N_orig_addr is not unknown; AND * X is in the I_local_iface_addr_list of a Local Interface Tuple; AND * There is a Link Tuple with L_status = SYMMETRIC and L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple and this Local Interface Tuple correspond to it. A network address from L_neighbor_iface_addr_list will be denoted R in this case. It SHOULD be preferred, where possible, to select R = Y and to select X from the Local Interface Tuple corresponding to the Link Tuple from which R was selected. The metric for such an edge is the corresponding N_out_metric.
o All edges W -> U such that:
* W is the TR_from_orig_addr of a Router Topology Tuple; AND
* U is the TR_to_orig_addr of the same Router Topology Tuple.
The metric of such an edge is the corresponding TR_metric.
The Network Topology Graph is further "decorated" with the following
edges. If a network address S, V, Z, or T equals a network address Y
or W, then the edge terminating in the network address S, V, Z, or T
MUST NOT be used in any path.
o Edges X -> S for all possible S, and one X per S, such that:
* S is in the N_neighbor_addr_list of a Neighbor Tuple; AND
* X is in the I_local_iface_addr_list of a Local Interface Tuple;
AND
* There is a Link Tuple with L_status = SYMMETRIC and
L_out_metric != UNKNOWN_METRIC such that this Neighbor Tuple
and this Local Interface Tuple correspond to it. A network
address from L_neighbor_iface_addr_list will be denoted R in
this case.
It SHOULD be preferred, where possible, to select R = S and to
select X from the Local Interface Tuple corresponding to the Link
Tuple from which R was selected. The metric for such an edge is
the corresponding N_out_metric.
o All edges W -> V such that:
* W is the TA_from_orig_addr of a Routable Address Topology
Tuple; AND
* V is the TA_dest_addr of the same Routable Address Topology
Tuple.
The metric for such an edge is the corresponding TA_metric.
o All edges W -> T such that:
* W is the AN_orig_addr of an Attached Network Tuple; AND
* T is the AN_net_addr of the same Attached Network Tuple.
The metric for such an edge is the corresponding AN_metric.
o (OPTIONAL) All edges Y -> Z such that:
* Z is a routable address and is the N2_2hop_addr of a 2-Hop
Tuple with N2_out_metric != UNKNOWN_METRIC; AND
* Y is the N_orig_addr of the corresponding Neighbor Tuple; AND
* This Neighbor Tuple has N_will_routing not equal to WILL_NEVER.
A path terminating with such an edge MUST NOT be used in
preference to any other path. The metric for such an edge is the
corresponding N2_out_metric.
Any part of the Topology Graph that is not connected to a local
network address X is not used. Only one selection X SHOULD be made
from each I_local_iface_addr_list, and only one selection R SHOULD be
made from any L_neighbor_iface_addr_list. All edges have a hop count
of 1, except edges W -> T that have a hop count of the corresponding
value of AN_dist.
19.2. Populating the Routing Set
The Routing Set MUST contain the shortest paths for all destinations
from all local OLSRv2 interfaces using the Network Topology Graph.
This calculation MAY use any algorithm, including any means of
choosing between paths of equal total metric. (In the case of two
paths of equal total metric but differing hop counts, the path with
the lower hop count SHOULD be used.)
Using the notation of Section 19.1, initially "backbone" paths using
only edges X -> Y and W -> U need be constructed (using a minimum
distance algorithm). Then paths using only a final edge of the other
types may be added. These MUST NOT replace backbone paths with the
same destination (and paths terminating in an edge Y -> Z SHOULD NOT
replace paths with any other form of terminating edge).
Each path will correspond to a Routing Tuple. These will be of two
types. The first type will represent single edge paths, of type X ->
S or X -> Y, by:
o R_local_iface_addr := X;
o R_next_iface_addr := R;
o R_dest_addr := S or Y;
o R_dist := 1; o R_metric := edge metric, where R is as defined in Section 19.1 for these types of edge. The second type will represent a multiple edge path, which will always have first edge of type X -> Y, and will have final edge of type W -> U, W -> V, W -> T, or Y -> Z. The Routing Tuple will be: o R_local_iface_addr := X; o R_next_iface_addr := Y; o R_dest_addr := U, V, T or Z; o R_dist := the total hop count of all edges in the path; o R_metric := the total metric of all edges in the path. Finally, Routing Tuples of the second type whose R_dest_addr is not routable MAY be discarded. An example algorithm for calculating the Routing Set of a router is given in Appendix C.20. Proposed Values for Parameters
This protocol uses all parameters defined in [RFC6130] and additional parameters defined in this specification. All but one (RX_HOLD_TIME) of these additional parameters are router parameters as defined in [RFC6130]. The proposed values of the additional parameters defined in the following sections are appropriate to the case where all parameters (including those defined in [RFC6130]) have a single value. Proposed values for parameters defined in [RFC6130] are given in that specification. The following proposed values are based on experience with [RFC3626] deployments (such as documented in [McCabe]) and are considered typical. They can be changed to accommodate different deployment requirements -- for example, a network with capacity-limited network interfaces would be expected to use greater values for message intervals, whereas a highly mobile network would be expected to use lower values for message intervals. When determining these values, the constraints specified in Section 5 MUST be respected.
Note that routers in a MANET need not all use the same set of parameters, and those parameters that are indicated as interface parameters need not be the same on all OLSRv2 interfaces of a single router.20.1. Local History Time Parameters
o O_HOLD_TIME := 30 seconds20.2. Message Interval Parameters
o TC_INTERVAL := 5 seconds o TC_MIN_INTERVAL := TC_INTERVAL/420.3. Advertised Information Validity Time Parameters
o T_HOLD_TIME := 3 x TC_INTERVAL o A_HOLD_TIME := T_HOLD_TIME20.4. Received Message Validity Time Parameters
o RX_HOLD_TIME := 30 seconds o P_HOLD_TIME := 30 seconds o F_HOLD_TIME := 30 seconds20.5. Jitter Time Parameters
o TP_MAXJITTER := HP_MAXJITTER o TT_MAXJITTER := HT_MAXJITTER o F_MAXJITTER := TT_MAXJITTER20.6. Hop Limit Parameter
o TC_HOP_LIMIT := 25520.7. Willingness Parameters
o WILL_FLOODING := WILL_DEFAULT o WILL_ROUTING := WILL_DEFAULT
21. Sequence Numbers
Sequence numbers are used in this specification for the purpose of discarding "old" information, i.e., messages received out of order. However, with a limited number of bits for representing sequence numbers, wraparound (in which the sequence number is incremented from the maximum possible value to zero) will occur. To prevent this from interfering with the operation of this protocol, the following MUST be observed when determining the ordering of sequence numbers. The term MAXVALUE designates in the following one more than the largest possible value for a sequence number. For a 16-bit sequence number (like those defined in this specification), MAXVALUE is 65536. The sequence number S1 is said to be "greater than" the sequence number S2 if: o S1 > S2 AND S1 - S2 < MAXVALUE/2, OR o S2 > S1 AND S2 - S1 > MAXVALUE/2 When sequence numbers S1 and S2 differ by MAXVALUE/2, their ordering cannot be determined. In this case, which should not occur, either ordering may be assumed. Thus, when comparing two messages, it is possible -- even in the presence of wraparound -- to determine which message contains the most recent information.22. Extensions
An extension to this protocol will need to interact with this specification and possibly also with [RFC6130]. This protocol is designed to permit such interactions, in particular: o Through accessing, and possibly extending, the information in the Information Bases. All updates to the elements specified in this specification are subject to the normative constraints specified in [RFC6130] and Appendix A. Note that the processing specified in this document ensures that these constraints are satisfied. o Through accessing an outgoing message prior to it being transmitted over any OLSRv2 interface and adding information to it as specified in [RFC5444]. This MAY include Message TLVs and/or network addresses with associated Address Block TLVs. (Network addresses without new associated TLVs SHOULD NOT be added to
messages.) This may, for example, be to allow a security
protocol, as suggested in Section 23, to add a TLV containing a
cryptographic signature to the message.
o Through accessing an incoming message and potentially discarding
it prior to processing by this protocol. This may, for example,
allow a security protocol, as suggested in Section 23, to perform
verification of message signatures and prevent processing and/or
forwarding of unverifiable messages by this protocol.
o Through accessing an incoming message after it has been completely
processed by this protocol. In particular, this may allow a
protocol that has added information, by way of inclusion of
appropriate TLVs or of network addresses associated with new TLVs,
access to such information after appropriate updates have been
recorded in the Information Bases in this protocol.
o Through requesting that a message be generated at a specific time.
In that case, message generation MUST still respect the
constraints in [RFC6130] and Section 5.4.3.
(page 84 continued on part 5)
