Re: [riot-devel] FIB redesign

[Martin]

Hi again,

I included the FIB to `RIOT/net/sixlowpan/ip` replacing 
`ip_get_next_hop()` by the FIB one.

Additionally I edited RPL to feed/update the FIB with the preferred parent.
(I set `23` arbitrary for the protocol ID and 0 for the interface.)

Best regards,
Martin

[1] 
https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/network_layer/fib/fib.c#L354


On 19.11.2014 09:59, Martin wrote:

Hi all,

> a significant question is of course how to deal with competing 
routing protocols
Form my understanding we have two distinct directions we can choose to 
approach the problem:


1. We strictly push it away from the FIB, i.e. only allowing to have 
unique entries for each global prefix.
pro: no handling needed here, the process, e.g. routing protocol, 
adding next hops to the FIB must care about this.
con: we loose the possibility to take link/topology/interface 
capabilities into account to forward a packet


2. We allow competing entries and apply (sort of) policies to always 
return a unambiguous next hop from the FIB.
pro: we are able to direct data and control plane flows, taking 
the routing protocol capabilities into account.
con: to have a preference on one FIB entry over another competing 
entry, requires a valuing weighting
and decision mechanism. This creates overhead and lowers 
the lookup/response time on next hop requests.


> Typically, these routing protocols split horizon according to IP 
address ranges
Using a separation on IP address ranges would shift the problem away 
from the FIB to the RIB.
This approach is definitely useful on non-moving routers with an 
organized and static hierarchy and a good argument for following 1.


But I think in some IoT scenarios with moving routers, this approach 
might have a poor performance

when the connected networks between the IoT routers periodically change.

> how does the FIB decide which next hop to choose if more than 
routing protocol made an entry pointing to it?
I've built in [1] to the FIB to provide an entry point to handle such 
conflicts.



Best Regards,
Martin

[1] 
https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/network_layer/fib/fib.c#L260


On 19.11.2014 00:47, Thomas C. Schmidt wrote:

Hi Martine,

a FIB always only provides unique forwarding rules. So there are no 
priorities attached to FIB entries. Priorities of routes may occur in 
RIBs associated with routing protocols ... and a significant question 
is of course how to deal with competing routing protocols that feed 
the FIB. (Typically, these routing protocols split horizon according 
to IP address ranges.)


Still, a routing protocol either overrides FIB entries or it doesn't.

Cheers,

Thomas

On 18.11.2014 21:56, Martine Lenders wrote:

Hi,
it's me again, dumping my latest brainstorm into the thread :D.

Don't we need some kind of priorities for the routing protocols, 
too? Or

how does the FIB decide which next hop to choose if more than routing
protocol made an entry pointing to it?

Cheers,
Martine

2014-11-17 8:05 GMT+01:00 Martin mailto:martin.landsm...@haw-hamburg.de>>:

Hi Martine,

>... Except you mean the routing protocol by this.
yes, the `prot_id` is the actual used (running) protocol, i.e. RPL.
This identifier must be unique for the running RIOT on the node,
i.e. arbitrary but fixed for the lifetime.

The "binding" of FIB table entries to a specific (running) protocol
is necessary only for updates on them.

Probably `kernel_pid_t` for the would be a waste of one byte for
each FIB table entry.
I will keep it `uint8_t` for now, but test a bit with 
`kernel_pid_t`.



Best regards,
Martin


On 15.11.2014 02:03, Martine Lenders wrote:

Hi Martin,

2014-11-14 15:23 GMT+01:00 Martin mailto:martin.landsm...@haw-hamburg.de>>:

Hi Martine,

I will change the interface and protocol IDs to
`kernel_type_t` as you suggested.
For the FIB handling perspective this seems also to be the
best (and easiest) way to have the IDs unique on one 
RIOT/node.



For protocol IDs I suggest `netdev_proto_t` [1]. Except you mean
the routing protocol by this. It aims, at least regarding my
design, to be the RIOT-global identifier for all network protocol
RIOT supports.

Cheers,
Martine

[1]
https://github.com/RIOT-OS/RIOT/blob/038beb0f99215207c09fd862ac7712982cedb3ef/drivers/include/netdev/base.h#L57 




___
devel mailing list
devel@riot-os.org  
http://lists.riot-os.org/mailman/listinfo/devel



___
devel mailing list
devel@riot-os.org 
http://lists.riot-os.org/mailman/listinfo/devel






___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel


__

Re: [riot-devel] FIB redesign

[Martin]

Hi all,

> a significant question is of course how to deal with competing 
routing protocols
Form my understanding we have two distinct directions we can choose to 
approach the problem:


1. We strictly push it away from the FIB, i.e. only allowing to have 
unique entries for each global prefix.
pro: no handling needed here, the process, e.g. routing protocol, 
adding next hops to the FIB must care about this.
con: we loose the possibility to take link/topology/interface 
capabilities into account to forward a packet


2. We allow competing entries and apply (sort of) policies to always 
return a unambiguous next hop from the FIB.
pro: we are able to direct data and control plane flows, taking the 
routing protocol capabilities into account.
con: to have a preference on one FIB entry over another competing 
entry, requires a valuing weighting
and decision mechanism. This creates overhead and lowers 
the lookup/response time on next hop requests.


> Typically, these routing protocols split horizon according to IP 
address ranges
Using a separation on IP address ranges would shift the problem away 
from the FIB to the RIB.
This approach is definitely useful on non-moving routers with an 
organized and static hierarchy and a good argument for following 1.


But I think in some IoT scenarios with moving routers, this approach 
might have a poor performance

when the connected networks between the IoT routers periodically change.

> how does the FIB decide which next hop to choose if more than routing 
protocol made an entry pointing to it?
I've built in [1] to the FIB to provide an entry point to handle such 
conflicts.



Best Regards,
Martin

[1] 
https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/network_layer/fib/fib.c#L260


On 19.11.2014 00:47, Thomas C. Schmidt wrote:

Hi Martine,

a FIB always only provides unique forwarding rules. So there are no 
priorities attached to FIB entries. Priorities of routes may occur in 
RIBs associated with routing protocols ... and a significant question 
is of course how to deal with competing routing protocols that feed 
the FIB. (Typically, these routing protocols split horizon according 
to IP address ranges.)


Still, a routing protocol either overrides FIB entries or it doesn't.

Cheers,

Thomas

On 18.11.2014 21:56, Martine Lenders wrote:

Hi,
it's me again, dumping my latest brainstorm into the thread :D.

Don't we need some kind of priorities for the routing protocols, too? Or
how does the FIB decide which next hop to choose if more than routing
protocol made an entry pointing to it?

Cheers,
Martine

2014-11-17 8:05 GMT+01:00 Martin mailto:martin.landsm...@haw-hamburg.de>>:

Hi Martine,

>... Except you mean the routing protocol by this.
yes, the `prot_id` is the actual used (running) protocol, i.e. RPL.
This identifier must be unique for the running RIOT on the node,
i.e. arbitrary but fixed for the lifetime.

The "binding" of FIB table entries to a specific (running) protocol
is necessary only for updates on them.

Probably `kernel_pid_t` for the would be a waste of one byte for
each FIB table entry.
I will keep it `uint8_t` for now, but test a bit with 
`kernel_pid_t`.



Best regards,
Martin


On 15.11.2014 02:03, Martine Lenders wrote:

Hi Martin,

2014-11-14 15:23 GMT+01:00 Martin mailto:martin.landsm...@haw-hamburg.de>>:

Hi Martine,

I will change the interface and protocol IDs to
`kernel_type_t` as you suggested.
For the FIB handling perspective this seems also to be the
best (and easiest) way to have the IDs unique on one RIOT/node.


For protocol IDs I suggest `netdev_proto_t` [1]. Except you mean
the routing protocol by this. It aims, at least regarding my
design, to be the RIOT-global identifier for all network protocol
RIOT supports.

Cheers,
Martine

[1]
https://github.com/RIOT-OS/RIOT/blob/038beb0f99215207c09fd862ac7712982cedb3ef/drivers/include/netdev/base.h#L57


___
devel mailing list
devel@riot-os.org  
http://lists.riot-os.org/mailman/listinfo/devel



___
devel mailing list
devel@riot-os.org 
http://lists.riot-os.org/mailman/listinfo/devel






___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Thomas C. Schmidt]

Hi Martine,

a FIB always only provides unique forwarding rules. So there are no 
priorities attached to FIB entries. Priorities of routes may occur in 
RIBs associated with routing protocols ... and a significant question is 
of course how to deal with competing routing protocols that feed the 
FIB. (Typically, these routing protocols split horizon according to IP 
address ranges.)


Still, a routing protocol either overrides FIB entries or it doesn't.

Cheers,

Thomas

On 18.11.2014 21:56, Martine Lenders wrote:

Hi,
it's me again, dumping my latest brainstorm into the thread :D.

Don't we need some kind of priorities for the routing protocols, too? Or
how does the FIB decide which next hop to choose if more than routing
protocol made an entry pointing to it?

Cheers,
Martine

2014-11-17 8:05 GMT+01:00 Martin mailto:martin.landsm...@haw-hamburg.de>>:

Hi Martine,

>... Except you mean the routing protocol by this.
yes, the `prot_id` is the actual used (running) protocol, i.e. RPL.
This identifier must be unique for the running RIOT on the node,
i.e. arbitrary but fixed for the lifetime.

The "binding" of FIB table entries to a specific (running) protocol
is necessary only for updates on them.

Probably `kernel_pid_t` for the would be a waste of one byte for
each FIB table entry.
I will keep it `uint8_t` for now, but test a bit with `kernel_pid_t`.


Best regards,
Martin


On 15.11.2014 02:03, Martine Lenders wrote:

Hi Martin,

2014-11-14 15:23 GMT+01:00 Martin mailto:martin.landsm...@haw-hamburg.de>>:

Hi Martine,

I will change the interface and protocol IDs to
`kernel_type_t` as you suggested.
For the FIB handling perspective this seems also to be the
best (and easiest) way to have the IDs unique on one RIOT/node.


For protocol IDs I suggest `netdev_proto_t` [1]. Except you mean
the routing protocol by this. It aims, at least regarding my
design, to be the RIOT-global identifier for all network protocol
RIOT supports.

Cheers,
Martine

[1]

https://github.com/RIOT-OS/RIOT/blob/038beb0f99215207c09fd862ac7712982cedb3ef/drivers/include/netdev/base.h#L57


___
devel mailing list
devel@riot-os.org  
http://lists.riot-os.org/mailman/listinfo/devel



___
devel mailing list
devel@riot-os.org 
http://lists.riot-os.org/mailman/listinfo/devel




--

Prof. Dr. Thomas C. Schmidt
° Hamburg University of Applied Sciences   Berliner Tor 7 °
° Dept. Informatik, Internet Technologies Group20099 Hamburg, Germany °
° http://www.haw-hamburg.de/inet   Fon: +49-40-42875-8452 °
° http://www.informatik.haw-hamburg.de/~schmidtFax: +49-40-42875-8409 °
___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Martine Lenders]

Hi,
it's me again, dumping my latest brainstorm into the thread :D.

Don't we need some kind of priorities for the routing protocols, too? Or
how does the FIB decide which next hop to choose if more than routing
protocol made an entry pointing to it?

Cheers,
Martine

2014-11-17 8:05 GMT+01:00 Martin :

>  Hi Martine,
>
> >... Except you mean the routing protocol by this.
> yes, the `prot_id` is the actual used (running) protocol, i.e. RPL.
> This identifier must be unique for the running RIOT on the node, i.e.
> arbitrary but fixed for the lifetime.
>
> The "binding" of FIB table entries to a specific (running) protocol is
> necessary only for updates on them.
>
> Probably `kernel_pid_t` for the would be a waste of one byte for each FIB
> table entry.
> I will keep it `uint8_t` for now, but test a bit with `kernel_pid_t`.
>
>
> Best regards,
> Martin
>
>
> On 15.11.2014 02:03, Martine Lenders wrote:
>
> Hi Martin,
>
> 2014-11-14 15:23 GMT+01:00 Martin :
>
>>  Hi Martine,
>>
>> I will change the interface and protocol IDs to `kernel_type_t` as you
>> suggested.
>> For the FIB handling perspective this seems also to be the best (and
>> easiest) way to have the IDs unique on one RIOT/node.
>>
>
>  For protocol IDs I suggest `netdev_proto_t` [1]. Except you mean the
> routing protocol by this. It aims, at least regarding my design, to be the
> RIOT-global identifier for all network protocol RIOT supports.
>
>  Cheers,
> Martine
>
>  [1]
> https://github.com/RIOT-OS/RIOT/blob/038beb0f99215207c09fd862ac7712982cedb3ef/drivers/include/netdev/base.h#L57
>
>
> ___
> devel mailing 
> listdevel@riot-os.orghttp://lists.riot-os.org/mailman/listinfo/devel
>
>
>
> ___
> devel mailing list
> devel@riot-os.org
> http://lists.riot-os.org/mailman/listinfo/devel
>
>
___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Martin]

Hi Martine,

>... Except you mean the routing protocol by this.
yes, the `prot_id` is the actual used (running) protocol, i.e. RPL.
This identifier must be unique for the running RIOT on the node, i.e. 
arbitrary but fixed for the lifetime.


The "binding" of FIB table entries to a specific (running) protocol is 
necessary only for updates on them.


Probably `kernel_pid_t` for the would be a waste of one byte for each 
FIB table entry.

I will keep it `uint8_t` for now, but test a bit with `kernel_pid_t`.


Best regards,
Martin

On 15.11.2014 02:03, Martine Lenders wrote:

Hi Martin,

2014-11-14 15:23 GMT+01:00 Martin >:


Hi Martine,

I will change the interface and protocol IDs to `kernel_type_t` as
you suggested.
For the FIB handling perspective this seems also to be the best
(and easiest) way to have the IDs unique on one RIOT/node.


For protocol IDs I suggest `netdev_proto_t` [1]. Except you mean the 
routing protocol by this. It aims, at least regarding my design, to be 
the RIOT-global identifier for all network protocol RIOT supports.


Cheers,
Martine

[1] 
https://github.com/RIOT-OS/RIOT/blob/038beb0f99215207c09fd862ac7712982cedb3ef/drivers/include/netdev/base.h#L57



___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel


___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Martine Lenders]

Hi Martin,

2014-11-14 15:23 GMT+01:00 Martin :

>  Hi Martine,
>
> I will change the interface and protocol IDs to `kernel_type_t` as you
> suggested.
> For the FIB handling perspective this seems also to be the best (and
> easiest) way to have the IDs unique on one RIOT/node.
>

For protocol IDs I suggest `netdev_proto_t` [1]. Except you mean the
routing protocol by this. It aims, at least regarding my design, to be the
RIOT-global identifier for all network protocol RIOT supports.

Cheers,
Martine

[1]
https://github.com/RIOT-OS/RIOT/blob/038beb0f99215207c09fd862ac7712982cedb3ef/drivers/include/netdev/base.h#L57
___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Martin]

Hi Martine,

I will change the interface and protocol IDs to `kernel_type_t` as you 
suggested.
For the FIB handling perspective this seems also to be the best (and 
easiest) way to have the IDs unique on one RIOT/node.


> Shouldn't 
https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/include/fib/fib.h#L119 
return the iface_id too?...

absolutely. It just slipped through somehow.

thx for your input.

Best regards,
Martin

On 14.11.2014 14:29, Martine Lenders wrote:

Hi Martin,
now that I'm in the refactoring of IPv6 I have some 
suggestions/considerations:


  * considering the current refactoring of the network stack to
PID-based identification of a network layer / protocol shouldn't
iface_id in

https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/include/fib/fib.h#L80
et.al  be of type kernel_type_t?
Interface IDs as with the current net_if module will still be
available, since they are "useful waste" from my reworked ipv6_if
implementation (they are the indices of the buffer array where I
store the (mac_pid, IP addresses) tuples), but maybe we don't want
to use those in the future publicly anymore.
… On the other hand, if we find that a single-threaded network
stack is superior to our current approach (part of my master
thesis ;-)), we might have to rethink that again, h. Sorry,
this bullet point is more loud thinking than suggesting ^^"
  * Shouldn't

https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/include/fib/fib.h#L119
return the iface_id too? The IP layer needs to now which MAC layer
it has to give the packet and this information is not encoded in
the address.

If I find more, I'll let you know

Cheers,
Martine

2014-11-06 20:45 GMT+01:00 Thomas C. Schmidt 
>:


Hi Martine & Martin,

following a personal discussion, the approach of multiple FIB
tables (per IF / protocol) is off the table, now. There will and
can be only one FIB.

Important for the next steps are discussion and conclusion about a
viable (internal) data structure for the FIB ... it seems there
are trade-offs between memory and processing constraints. Marin
shall present proposals for a thorough review discussion soon.

Cheers,

Thomas

On 05.11.2014 15:10, Landsmann, Martin wrote:

Hi all,

I started a prototype implementation [1] under consideration
of the
diagram on the wiki page [2].
- It provides a generic address handling and access
- a basic FIB table management (add, remove, update)
- collision detection for next_hops and resolving the conflict
based on
a preference table
- reactive RP signalling using `msg_send_receive()`

This prototype is not included between any RP and the
`get_next_hop()`
right now.

Best regards,
Martin

[1] git pull https://github.com/BytesGalore/RIOT add_fib
[2]

https://github.com/RIOT-OS/RIOT/wiki/Rough-sketch-of-a-possible-FIB-modularization


On 04.11.2014 11:05, Martin wrote:

Hi Martine,

thx for the input :)

> Are you planning to only consider stateless compression
(Prefix is assumed link-local) or also stateful
compression (Prefix is determined by a 4-bit context ID
[1] ...

I plan to make it more generic, e.g. allow for providing even
proprietary "solutions" for FIB table entry compression.
LOWPAN_IPHC
provides wonderful mechanisms to save bytes in
transmissions, but
there are probably (most likely) more possibilities to
save bytes on
the individual nodes RAM when maintaining a FIB table.
Eventually the FIB will "resolve" the applied compression
to provide
the type required by a `get_next_hop()` request.

>... we might want to consider to put those information
into the same data structure (so the later of my 2
suggestions above would be)

Indeed, that would by great. That's the reason I want to
outsource the
"Generic address" from the FIB table entry. These blobs
can be shared
among processes, e.g. FIB, routing protocol and ND.
Liftime invalidation and such is controlled by the
individual process.
For instance, an expired FIB table entry would mark its
internal
structure as invalid and decrease the usecount of the
"Generic address".

> Also: have you considered Mesh-under routing [5]? (Do we
have to consider this here I wonder myself? We don't have
support for it anyways, so far.) [6] states some
requirements for this.

No, I onl

Re: [riot-devel] FIB redesign

[Martine Lenders]

Hi Martin,
now that I'm in the refactoring of IPv6 I have some
suggestions/considerations:

   - considering the current refactoring of the network stack to PID-based
   identification of a network layer / protocol shouldn't iface_id in
   
https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/include/fib/fib.h#L80
   et.al be of type kernel_type_t?
   Interface IDs as with the current net_if module will still be available,
   since they are "useful waste" from my reworked ipv6_if implementation (they
   are the indices of the buffer array where I store the (mac_pid, IP
   addresses) tuples), but maybe we don't want to use those in the future
   publicly anymore.
   … On the other hand, if we find that a single-threaded network stack is
   superior to our current approach (part of my master thesis ;-)), we might
   have to rethink that again, h. Sorry, this bullet point is more loud
   thinking than suggesting ^^"
   - Shouldn't
   
https://github.com/BytesGalore/RIOT/blob/add_fib/sys/net/include/fib/fib.h#L119
   return the iface_id too? The IP layer needs to now which MAC layer it has
   to give the packet and this information is not encoded in the address.

If I find more, I'll let you know

Cheers,
Martine

2014-11-06 20:45 GMT+01:00 Thomas C. Schmidt <
schm...@informatik.haw-hamburg.de>:

> Hi Martine & Martin,
>
> following a personal discussion, the approach of multiple FIB tables (per
> IF / protocol) is off the table, now. There will and can be only one FIB.
>
> Important for the next steps are discussion and conclusion about a viable
> (internal) data structure for the FIB ... it seems there are trade-offs
> between memory and processing constraints. Marin shall present proposals
> for a thorough review discussion soon.
>
> Cheers,
>
> Thomas
>
> On 05.11.2014 15:10, Landsmann, Martin wrote:
>
>> Hi all,
>>
>> I started a prototype implementation [1] under consideration of the
>> diagram on the wiki page [2].
>> - It provides a generic address handling and access
>> - a basic FIB table management (add, remove, update)
>> - collision detection for next_hops and resolving the conflict based on
>> a preference table
>> - reactive RP signalling using `msg_send_receive()`
>>
>> This prototype is not included between any RP and the `get_next_hop()`
>> right now.
>>
>> Best regards,
>> Martin
>>
>> [1] git pull https://github.com/BytesGalore/RIOT add_fib
>> [2]
>> https://github.com/RIOT-OS/RIOT/wiki/Rough-sketch-of-a-
>> possible-FIB-modularization
>>
>>
>> On 04.11.2014 11:05, Martin wrote:
>>
>>> Hi Martine,
>>>
>>> thx for the input :)
>>>
>>> > Are you planning to only consider stateless compression (Prefix is
>>> assumed link-local) or also stateful compression (Prefix is determined by a
>>> 4-bit context ID [1] ...
>>>
>>> I plan to make it more generic, e.g. allow for providing even
>>> proprietary "solutions" for FIB table entry compression. LOWPAN_IPHC
>>> provides wonderful mechanisms to save bytes in transmissions, but
>>> there are probably (most likely) more possibilities to save bytes on
>>> the individual nodes RAM when maintaining a FIB table.
>>> Eventually the FIB will "resolve" the applied compression to provide
>>> the type required by a `get_next_hop()` request.
>>>
>>> >... we might want to consider to put those information into the same
>>> data structure (so the later of my 2 suggestions above would be)
>>>
>>> Indeed, that would by great. That's the reason I want to outsource the
>>> "Generic address" from the FIB table entry. These blobs can be shared
>>> among processes, e.g. FIB, routing protocol and ND.
>>> Liftime invalidation and such is controlled by the individual process.
>>> For instance, an expired FIB table entry would mark its internal
>>> structure as invalid and decrease the usecount of the "Generic address".
>>>
>>> > Also: have you considered Mesh-under routing [5]? (Do we have to
>>> consider this here I wonder myself? We don't have support for it anyways,
>>> so far.) [6] states some requirements for this.
>>>
>>> No, I only considered to "play" at the network layer level for now.
>>> But I will have a look.
>>>
>>>
>>> Best Regards,
>>> Martin
>>>
>>> Hi,
>>> I finally came to it to read your suggestions, too. Regarding the fact
>>> that you keep 6LoWPAN header compression in mind, too: Are you
>>> planning to only consider stateless compression (Prefix is assumed
>>> link-local) or also stateful compression (Prefix is determined by a
>>> 4-bit context ID [1], disseminated through the PAN via the context
>>> identifier option in RS [2]). Since Neighbor Cache [3], Prefix
>>> Information [4], Forwarding information, and Context Information are
>>> all very related, and we may want to save memory, we might want to
>>> consider to put those information into the same data structure (so the
>>> later of my 2 suggestions above would be). Keep in mind though, that
>>> both Prefix Information Base and Context information Base have their
>>> own lifecycles (see

Re: [riot-devel] FIB redesign

[Thomas C. Schmidt]

Hi Martine & Martin,

following a personal discussion, the approach of multiple FIB tables 
(per IF / protocol) is off the table, now. There will and can be only 
one FIB.


Important for the next steps are discussion and conclusion about a 
viable (internal) data structure for the FIB ... it seems there are 
trade-offs between memory and processing constraints. Marin shall 
present proposals for a thorough review discussion soon.


Cheers,

Thomas

On 05.11.2014 15:10, Landsmann, Martin wrote:

Hi all,

I started a prototype implementation [1] under consideration of the
diagram on the wiki page [2].
- It provides a generic address handling and access
- a basic FIB table management (add, remove, update)
- collision detection for next_hops and resolving the conflict based on
a preference table
- reactive RP signalling using `msg_send_receive()`

This prototype is not included between any RP and the `get_next_hop()`
right now.

Best regards,
Martin

[1] git pull https://github.com/BytesGalore/RIOT add_fib
[2]
https://github.com/RIOT-OS/RIOT/wiki/Rough-sketch-of-a-possible-FIB-modularization


On 04.11.2014 11:05, Martin wrote:

Hi Martine,

thx for the input :)

> Are you planning to only consider stateless compression (Prefix is assumed 
link-local) or also stateful compression (Prefix is determined by a 4-bit context 
ID [1] ...

I plan to make it more generic, e.g. allow for providing even
proprietary "solutions" for FIB table entry compression. LOWPAN_IPHC
provides wonderful mechanisms to save bytes in transmissions, but
there are probably (most likely) more possibilities to save bytes on
the individual nodes RAM when maintaining a FIB table.
Eventually the FIB will "resolve" the applied compression to provide
the type required by a `get_next_hop()` request.

>... we might want to consider to put those information into the same data 
structure (so the later of my 2 suggestions above would be)

Indeed, that would by great. That's the reason I want to outsource the
"Generic address" from the FIB table entry. These blobs can be shared
among processes, e.g. FIB, routing protocol and ND.
Liftime invalidation and such is controlled by the individual process.
For instance, an expired FIB table entry would mark its internal
structure as invalid and decrease the usecount of the "Generic address".

> Also: have you considered Mesh-under routing [5]? (Do we have to consider 
this here I wonder myself? We don't have support for it anyways, so far.) [6] 
states some requirements for this.

No, I only considered to "play" at the network layer level for now.
But I will have a look.


Best Regards,
Martin

Hi,
I finally came to it to read your suggestions, too. Regarding the fact
that you keep 6LoWPAN header compression in mind, too: Are you
planning to only consider stateless compression (Prefix is assumed
link-local) or also stateful compression (Prefix is determined by a
4-bit context ID [1], disseminated through the PAN via the context
identifier option in RS [2]). Since Neighbor Cache [3], Prefix
Information [4], Forwarding information, and Context Information are
all very related, and we may want to save memory, we might want to
consider to put those information into the same data structure (so the
later of my 2 suggestions above would be). Keep in mind though, that
both Prefix Information Base and Context information Base have their
own lifecycles (see regarding RFCs).

Also: have you considered Mesh-under routing [5]? (Do we have to
consider this here I wonder myself? We don't have support for it
anyways, so far.) [6] states some requirements for this.

Hope this was more helpful, than confusing ;-).

Cheers,
Martine

[1] https://tools.ietf.org/html/rfc6282#section-3.1.2
[2] https://tools.ietf.org/html/rfc6775#section-4.2
[3] http://tools.ietf.org/html/rfc4861#section-5.1
[4] https://tools.ietf.org/html/rfc4861#section-4.6.2
[5] https://tools.ietf.org/html/rfc4944#section-11
[6] http://tools.ietf.org/html/rfc6606


___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel




--

Prof. Dr. Thomas C. Schmidt
° Hamburg University of Applied Sciences   Berliner Tor 7 °
° Dept. Informatik, Internet Technologies Group20099 Hamburg, Germany °
° http://www.haw-hamburg.de/inet   Fon: +49-40-42875-8452 °
° http://www.informatik.haw-hamburg.de/~schmidtFax: +49-40-42875-8409 °
___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Martin]

Hi all,

I started a prototype implementation [1] under consideration of the 
diagram on the wiki page [2].

- It provides a generic address handling and access
- a basic FIB table management (add, remove, update)
- collision detection for next_hops and resolving the conflict based on 
a preference table

- reactive RP signalling using `msg_send_receive()`

This prototype is not included between any RP and the `get_next_hop()` 
right now.


Best regards,
Martin

[1] git pull https://github.com/BytesGalore/RIOT add_fib
[2] 
https://github.com/RIOT-OS/RIOT/wiki/Rough-sketch-of-a-possible-FIB-modularization



On 04.11.2014 11:05, Martin wrote:

Hi Martine,

thx for the input :)

> Are you planning to only consider stateless compression (Prefix is 
assumed link-local) or also stateful compression (Prefix is determined 
by a 4-bit context ID [1] ...


I plan to make it more generic, e.g. allow for providing even 
proprietary "solutions" for FIB table entry compression. LOWPAN_IPHC 
provides wonderful mechanisms to save bytes in transmissions, but 
there are probably (most likely) more possibilities to save bytes on 
the individual nodes RAM when maintaining a FIB table.
Eventually the FIB will "resolve" the applied compression to provide 
the type required by a `get_next_hop()` request.


>... we might want to consider to put those information into the same 
data structure (so the later of my 2 suggestions above would be)


Indeed, that would by great. That's the reason I want to outsource the 
"Generic address" from the FIB table entry. These blobs can be shared 
among processes, e.g. FIB, routing protocol and ND.

Liftime invalidation and such is controlled by the individual process.
For instance, an expired FIB table entry would mark its internal 
structure as invalid and decrease the usecount of the "Generic address".


> Also: have you considered Mesh-under routing [5]? (Do we have to 
consider this here I wonder myself? We don't have support for it 
anyways, so far.) [6] states some requirements for this.


No, I only considered to "play" at the network layer level for now. 
But I will have a look.



Best Regards,
Martin

Hi,
I finally came to it to read your suggestions, too. Regarding the fact 
that you keep 6LoWPAN header compression in mind, too: Are you 
planning to only consider stateless compression (Prefix is assumed 
link-local) or also stateful compression (Prefix is determined by a 
4-bit context ID [1], disseminated through the PAN via the context 
identifier option in RS [2]). Since Neighbor Cache [3], Prefix 
Information [4], Forwarding information, and Context Information are 
all very related, and we may want to save memory, we might want to 
consider to put those information into the same data structure (so the 
later of my 2 suggestions above would be). Keep in mind though, that 
both Prefix Information Base and Context information Base have their 
own lifecycles (see regarding RFCs).


Also: have you considered Mesh-under routing [5]? (Do we have to 
consider this here I wonder myself? We don't have support for it 
anyways, so far.) [6] states some requirements for this.


Hope this was more helpful, than confusing ;-).

Cheers,
Martine

[1] https://tools.ietf.org/html/rfc6282#section-3.1.2
[2] https://tools.ietf.org/html/rfc6775#section-4.2
[3] http://tools.ietf.org/html/rfc4861#section-5.1
[4] https://tools.ietf.org/html/rfc4861#section-4.6.2
[5] https://tools.ietf.org/html/rfc4944#section-11
[6] http://tools.ietf.org/html/rfc6606


___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel


___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Martin]

Hi Martine,

thx for the input :)

> Are you planning to only consider stateless compression (Prefix is 
assumed link-local) or also stateful compression (Prefix is determined 
by a 4-bit context ID [1] ...


I plan to make it more generic, e.g. allow for providing even 
proprietary "solutions" for FIB table entry compression. LOWPAN_IPHC 
provides wonderful mechanisms to save bytes in transmissions, but there 
are probably (most likely) more possibilities to save bytes on the 
individual nodes RAM when maintaining a FIB table.
Eventually the FIB will "resolve" the applied compression to provide the 
type required by a `get_next_hop()` request.


>... we might want to consider to put those information into the same 
data structure (so the later of my 2 suggestions above would be)


Indeed, that would by great. That's the reason I want to outsource the 
"Generic address" from the FIB table entry. These blobs can be shared 
among processes, e.g. FIB, routing protocol and ND.

Liftime invalidation and such is controlled by the individual process.
For instance, an expired FIB table entry would mark its internal 
structure as invalid and decrease the usecount of the "Generic address".


> Also: have you considered Mesh-under routing [5]? (Do we have to 
consider this here I wonder myself? We don't have support for it 
anyways, so far.) [6] states some requirements for this.


No, I only considered to "play" at the network layer level for now. But 
I will have a look.



Best Regards,
Martin

Hi,
I finally came to it to read your suggestions, too. Regarding the fact 
that you keep 6LoWPAN header compression in mind, too: Are you planning 
to only consider stateless compression (Prefix is assumed link-local) or 
also stateful compression (Prefix is determined by a 4-bit context ID 
[1], disseminated through the PAN via the context identifier option in 
RS [2]). Since Neighbor Cache [3], Prefix Information [4], Forwarding 
information, and Context Information are all very related, and we may 
want to save memory, we might want to consider to put those information 
into the same data structure (so the later of my 2 suggestions above 
would be). Keep in mind though, that both Prefix Information Base and 
Context information Base have their own lifecycles (see regarding RFCs).


Also: have you considered Mesh-under routing [5]? (Do we have to 
consider this here I wonder myself? We don't have support for it 
anyways, so far.) [6] states some requirements for this.


Hope this was more helpful, than confusing ;-).

Cheers,
Martine

[1] https://tools.ietf.org/html/rfc6282#section-3.1.2
[2] https://tools.ietf.org/html/rfc6775#section-4.2
[3] http://tools.ietf.org/html/rfc4861#section-5.1
[4] https://tools.ietf.org/html/rfc4861#section-4.6.2
[5] https://tools.ietf.org/html/rfc4944#section-11
[6] http://tools.ietf.org/html/rfc6606
___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel


___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Martine Lenders]

Hi,
I finally came to it to read your suggestions, too. Regarding the fact that
you keep 6LoWPAN header compression in mind, too: Are you planning to only
consider stateless compression (Prefix is assumed link-local) or also
stateful compression (Prefix is determined by a 4-bit context ID [1],
disseminated through the PAN via the context identifier option in RS [2]).
Since Neighbor Cache [3], Prefix Information [4], Forwarding information,
and Context Information are all very related, and we may want to save
memory, we might want to consider to put those information into the same
data structure (so the later of my 2 suggestions above would be). Keep in
mind though, that both Prefix Information Base and Context information Base
have their own lifecycles (see regarding RFCs).

Also: have you considered Mesh-under routing [5]? (Do we have to consider
this here I wonder myself? We don't have support for it anyways, so far.)
[6] states some requirements for this.

Hope this was more helpful, than confusing ;-).

Cheers,
Martine

[1] https://tools.ietf.org/html/rfc6282#section-3.1.2
[2] https://tools.ietf.org/html/rfc6775#section-4.2
[3] http://tools.ietf.org/html/rfc4861#section-5.1
[4] https://tools.ietf.org/html/rfc4861#section-4.6.2
[5] https://tools.ietf.org/html/rfc4944#section-11
[6] http://tools.ietf.org/html/rfc6606
___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

Re: [riot-devel] FIB redesign

[Martin]

Hi Emmanuel, hi all,

> - the way I read it, the current content aims at some sort of list of 
requirements, and a description the current FIB design in RIOT, right?
right, somehow. It figures the problematic areas that have to be handled 
for a clean interaction as sketched in the diagram.


> - more in particular: it does not contain so far any concrete 
proposal for a FIB redesign. Am I correct?
Yes and no, the diagram at the bottom should give a conceptual overview 
how the interaction of the FIB in the RIOT context finally could be.

It does not reflect anything present RIOT.
I didn't wanted to go to much into possible implementation details, as 
long as the concept is not considered as sane.


The FIB itself will be a lightweight "interface" providing access and 
manipulation decoupling the data, i.e. FIB tables, from the routing 
protocols (or RIB).
The FIB table will provide a generalized data management/structure. I 
updated the page with a concept of a FIB table data overview.

This should allow to take advantage of non IP addressing.
The access functions as sketched from RIB and RIOT processes will 
provide a KISS and clean interface.
For instance just `add(...) remove(...)` and `update(...)` from RIB side 
and `get_next_hop(...)` from a RIOT process.
The dispatching on FIB table entries and weight of them over others on 
collisions happens behind the FIB-"wall".


If this sounds sane, I could provide some code till mid/end of this week 
reflecting the FIB tables and FIB-"wall".


Best Regards,
Martin
On 03.11.2014 15:18, Emmanuel Baccelli wrote:

Hi Martin,

thanks for the initial wiki input on the topic (i.e. 
https://github.com/RIOT-OS/RIOT/wiki/Rough-sketch-of-a-possible-FIB-modularization).


I briefly scanned though it, and I have two quick questions for starters:

- the way I read it, the current content aims at some sort of list of 
requirements, and a description the current FIB design in RIOT, right?


- more in particular: it does not contain so far any concrete proposal 
for a FIB redesign. Am I correct?


Best,

Emmanuel




___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel


___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel

[riot-devel] FIB redesign

[Emmanuel Baccelli]

Hi Martin,

thanks for the initial wiki input on the topic (i.e.
https://github.com/RIOT-OS/RIOT/wiki/Rough-sketch-of-a-possible-FIB-modularization
).

I briefly scanned though it, and I have two quick questions for starters:

- the way I read it, the current content aims at some sort of list of
requirements, and a description the current FIB design in RIOT, right?

- more in particular: it does not contain so far any concrete proposal for
a FIB redesign. Am I correct?

Best,

Emmanuel
___
devel mailing list
devel@riot-os.org
http://lists.riot-os.org/mailman/listinfo/devel