Path Discovery Mechanism/FWT: Difference between revisions

From OLPC
Jump to navigation Jump to search
(New page: Every XO is capable of keeping up to 64 paths in its forwarding table. An entry on the forwarding table consists of the following fields. {| border = '1' |+ '''Table 1''' - FWT fields ! ...)
 
No edit summary
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
<noinclude>{{Google Translations}}{{TOCright}}</noinclude>
[[Category:Network]]

Every XO is capable of keeping up to 64 paths in its forwarding table. An entry on the forwarding table consists of the following fields.
Every XO is capable of keeping up to 64 paths in its forwarding table. An entry on the forwarding table consists of the following fields.


Line 34: Line 37:
|}
|}


* DA or Destination address is the target for the path, while RA will be the next hop in this path. In single hop paths, i.e. paths to direct neighbors they will be the same.
* ''DA'' or Destination address is the target for the path, while ''RA'' will be the next hop in this path. In single hop paths, i.e. paths to direct neighbors they will be the same.


* [http://wiki.laptop.org/go/Path_Discovery_Mechanism:Metrics Metric] will be the sum of all the costs associated to the PREQs that were successfully transmitted, hop-by-hop, from the current node to the destination (DA). Possible values for a mesh with no more than 5 hops can be seen [http://wiki.laptop.org/go/Path_Discovery_Mechanism:Metrics#Airtime_versus_Path_Length here].
* [http://wiki.laptop.org/go/Path_Discovery_Mechanism:Metrics Metric] will be the sum of all the costs associated to the PREQs that were successfully transmitted, hop-by-hop, from the current node to the destination (DA). Possible values for a mesh with no more than 5 hops can be seen [http://wiki.laptop.org/go/Path_Discovery_Mechanism:Metrics#Airtime_versus_Path_Length here].
Line 40: Line 43:
* Routes are marked invalid when MPs detect that the next hop is unreachable. Invalid routes are deleted only when FWT table is full and the XO wants to insert a new route. Note that valid routes can be expired or not expired. A time stamp is associated to every frame added to the forwarding table. This time stamp is provided by the Wireless Module and it is started every time the XO is booted. A route will be considered valid if:
* Routes are marked invalid when MPs detect that the next hop is unreachable. Invalid routes are deleted only when FWT table is full and the XO wants to insert a new route. Note that valid routes can be expired or not expired. A time stamp is associated to every frame added to the forwarding table. This time stamp is provided by the Wireless Module and it is started every time the XO is booted. A route will be considered valid if:


Entry Expiration < Current Time + Route Expiration Time
Current Time <= Entry Expiration + Route Expiration Time


* The Route Expiration Time is configurable and currently defaults to 10 seconds.
* The Route Expiration Time is configurable and currently defaults to 10 seconds.


* Every path has a direction (Dir). A direct (forward) path will be marked with one, reverse paths will be marked with zero in the Dir field.
* Every path has a direction (''Dir''). A direct (forward) path will be marked with one, reverse paths will be marked with zero in the Dir field.


* The ''Rate'' in which this node will transmit to the next hop – the RA.
* The Rate in which this node will transmit to the next hop – the RA – is derived by using a mesh rate adaptation algorithm based on a Packet Error Rate (PER) algorithm. Details of the implementation are property of Marvell Technology Group. The basic idea is to lower the data rate every time a number of successive transmissions fail (no ack is received) and, likewise, raise the rate, if possible, when a given number of consecutive transmissions succeed.


* The Source Sequence Number (SSN) and the Destination Sequence Number (DSN) are used to avoid path loops.
* The Source Sequence Number (''SSN'') and the Destination Sequence Number (''DSN'') are used to avoid path loops.


* Hop Count is the number of hops to the destination (DA) while TTL keeps the number of hops to the Source in reverse routes.
* ''Hop Count'' is the number of hops to the destination (DA) while ''TTL'' keeps the number of hops to the Source in reverse routes.


* The field Sleepmode is currently unused, since there is currently no support to mesh power saving mode.
* The field ''Sleepmode'' is currently unused, since there is currently no support to mesh power saving mode.


* The SNR value is also not used by the firmware, and is derived when the path is learned and only updated every when the path expires.
* The ''SNR'' value is also not used by the firmware, and is derived when the path is learned and only updated every when the path expires.


* Finally, the Precursor is the predecessor in a direct path, thus it is the one to which the node will send an Path Error frame (PERR) in case it fails to forward data frames to the next hop (RA).
* Finally, the ''Precursor'' is the predecessor in a direct path, thus it is the one to which the node will send an Path Error frame (PERR) in case it fails to forward data frames to the next hop (RA).

Latest revision as of 02:24, 2 September 2009

Every XO is capable of keeping up to 64 paths in its forwarding table. An entry on the forwarding table consists of the following fields.

Table 1 - FWT fields
Entry Meaning
DA Destination MAC Address: the node this path entry is for.
RA Receiver MAC address: the next hop for this path.
Valid If the route is valid or not
Metric The total cost for the path
Dir Direction (1 for forward path, 0 for reverse path)
Rate Data rate used to transmit to the next hop (RA)
SSN Source Sequence Number (time at the RA for reverse routes. Default is 0)
DSN Destination Sequence Number (time at the DA for direct routes. Default is 0)
Hopcount Hop count (currently unused, default is 0)
TTL Time to live, as usual in hops (Only used in reverse entries)
Expiration Entry expiration (in ticks, where a tick is 1024us, or approximately 1ms. default is 0 which means never expires)
Sleepmode RA's sleep mode (currently unused, default is 0)
SNR SNR in the link to RA (currently unused, default is 0)
Precursor Predecessor’s MAC in direct routes
  • DA or Destination address is the target for the path, while RA will be the next hop in this path. In single hop paths, i.e. paths to direct neighbors they will be the same.
  • Metric will be the sum of all the costs associated to the PREQs that were successfully transmitted, hop-by-hop, from the current node to the destination (DA). Possible values for a mesh with no more than 5 hops can be seen here.
  • Routes are marked invalid when MPs detect that the next hop is unreachable. Invalid routes are deleted only when FWT table is full and the XO wants to insert a new route. Note that valid routes can be expired or not expired. A time stamp is associated to every frame added to the forwarding table. This time stamp is provided by the Wireless Module and it is started every time the XO is booted. A route will be considered valid if:
Current Time <= Entry Expiration + Route Expiration Time 
  • The Route Expiration Time is configurable and currently defaults to 10 seconds.
  • Every path has a direction (Dir). A direct (forward) path will be marked with one, reverse paths will be marked with zero in the Dir field.
  • The Rate in which this node will transmit to the next hop – the RA.
  • The Source Sequence Number (SSN) and the Destination Sequence Number (DSN) are used to avoid path loops.
  • Hop Count is the number of hops to the destination (DA) while TTL keeps the number of hops to the Source in reverse routes.
  • The field Sleepmode is currently unused, since there is currently no support to mesh power saving mode.
  • The SNR value is also not used by the firmware, and is derived when the path is learned and only updated every when the path expires.
  • Finally, the Precursor is the predecessor in a direct path, thus it is the one to which the node will send an Path Error frame (PERR) in case it fails to forward data frames to the next hop (RA).