1. 17 Mar, 2013 2 commits
  2. 15 Mar, 2013 9 commits
  3. 14 Mar, 2013 23 commits
  4. 13 Mar, 2013 6 commits
    • Martin Hundebøll's avatar
      batman-adv: network coding - receive coded packets and decode them · 2df5278b
      Martin Hundebøll authored
      When receiving a network coded packet, the decoding buffer is searched
      for a packet to use for decoding. The source, destination, and crc32 from
      the coded packet is used to identify the wanted packet. The decoded
      packet is passed to the usual unicast receiver function, as had it never
      been network coded.
      Signed-off-by: default avatarMartin Hundebøll <martin@hundeboll.net>
      Signed-off-by: default avatarMarek Lindner <lindner_marek@yahoo.de>
      Signed-off-by: default avatarAntonio Quartulli <ordex@autistici.org>
      2df5278b
    • Martin Hundebøll's avatar
      batman-adv: network coding - save overheard and tx packets for decoding · 612d2b4f
      Martin Hundebøll authored
      To be able to decode a network coded packet, a node must already know
      one of the two coded packets. This is done by buffering skbs before
      transmission and buffering packets sniffed with promiscuous mode from
      other hosts.
      
      Packets are kept in a buffer similar to the one with forward-skbs: A
      hash table, where each entry, which corresponds to a src-dst pair, has a
      linked list packets.
      Signed-off-by: default avatarMartin Hundebøll <martin@hundeboll.net>
      Signed-off-by: default avatarMarek Lindner <lindner_marek@yahoo.de>
      Signed-off-by: default avatarAntonio Quartulli <ordex@autistici.org>
      612d2b4f
    • Martin Hundebøll's avatar
      batman-adv: network coding - code and transmit packets if possible · 3c12de9a
      Martin Hundebøll authored
      Before adding forward-skbs to the coding buffer, the buffer is searched
      for a potential coding opportunity. If one is found, the two packets are
      network coded and transmitted right away. If not, the forward-skb is
      added to the buffer.
      
      Network coded packets are transmitted with information about the two
      receivers and the two coded packets. The first receiver is given by the
      MAC header, while the second is given in the payload/bat-header. The
      second receiver uses promiscuous mode to receive the packet and check
      the second destination.
      Signed-off-by: default avatarMartin Hundebøll <martin@hundeboll.net>
      Signed-off-by: default avatarMarek Lindner <lindner_marek@yahoo.de>
      Signed-off-by: default avatarAntonio Quartulli <ordex@autistici.org>
      3c12de9a
    • Martin Hundebøll's avatar
      batman-adv: network coding - buffer unicast packets before forward · 95332477
      Martin Hundebøll authored
      Two be able to network code two packets, one packet must be buffered
      until the next is available. This is done in a "coding buffer", which is
      essentially a hash table with lists of packets. Each entry in the hash
      table corresponds to a specific src-dst pair, which has a linked list of
      packets that are buffered.
      
      This patch adds skbs to the buffer just before forwarding them. The
      buffer is traversed every 10 ms, where timed skbs are removed from the
      buffer and transmitted. To allow experiments with the network coding
      scheme, the timeout is tunable through a file in debugfs.
      Signed-off-by: default avatarMartin Hundebøll <martin@hundeboll.net>
      Signed-off-by: default avatarMarek Lindner <lindner_marek@yahoo.de>
      Signed-off-by: default avatarAntonio Quartulli <ordex@autistici.org>
      95332477
    • Martin Hundebøll's avatar
      batman-adv: network coding - detect coding nodes and remove these after timeout · d56b1705
      Martin Hundebøll authored
      To use network coding efficiently, a relay must know when neighbor nodes
      are likely to have enough information to be able to decode a network
      coded packet. This is detected by using OGMs from batman-adv to discover
      when one neighbor is in range of another neighbor. The relay check the
      TLL to detect when an OGM is forwarded from one neighbor by another
      neighbor, and thereby knows that the two neighbors are in range and thus
      overhear packets sent by each other.
      
      This information is saved in the orig_node struct to be used when
      searching for coding opportunities. Two lists are added to the
      orig_node struct: One for neighbors that can hear the orig_node
      (outgoing nc_nodes) and one for neighbors that the orig_node can hear
      (incoming nc_nodes).
      
      Information about nc_nodes is kept for 10 seconds and is available
      through debugfs in batman_adv/nc_nodes to use when debugging network
      coding.
      Signed-off-by: default avatarMartin Hundebøll <martin@hundeboll.net>
      Signed-off-by: default avatarMarek Lindner <lindner_marek@yahoo.de>
      Signed-off-by: default avatarAntonio Quartulli <ordex@autistici.org>
      d56b1705
    • Martin Hundebøll's avatar
      batman-adv: network coding - add the initial infrastructure code · d353d8d4
      Martin Hundebøll authored
      Network coding exploits the 802.11 shared medium to allow multiple
      packets to be sent in a single transmission. In brief, a relay can XOR
      two packets, and send the coded packet to two destinations. The
      receivers can decode one of the original packets by XOR'ing the coded
      packet with the other original packet. This will lead to increased
      throughput in topologies where two packets cross one relay.
      
      In a simple topology with three nodes, it takes four transmissions
      without network coding to get one packet from Node A to Node B and one
      from Node B to Node A:
      
       1.  Node A  ---- p1 --->  Node R                Node B
       2.  Node A                Node R  <--- p2 ----  Node B
       3.  Node A  <--- p2 ----  Node R                Node B
       4.  Node A                Node R  ---- p1 --->  Node B
      
      With network coding, the relay only needs one transmission, which saves
      us one slot of valuable airtime:
      
       1.  Node A  ---- p1 --->  Node R                Node B
       2.  Node A                Node R  <--- p2 ----  Node B
       3.  Node A  <- p1 x p2 -  Node R  - p1 x p2 ->  Node B
      
      The same principle holds for a topology including five nodes. Here the
      packets from Node A and Node B are overheard by Node C and Node D,
      respectively. This allows Node R to send a network coded packet to save
      one transmission:
      
         Node A                  Node B
      
          |     \              /    |
          |      p1          p2     |
          |       \          /      |
          p1       > Node R <       p2
          |                         |
          |         /      \        |
          |    p1 x p2    p1 x p2   |
          v       /          \      v
                 /            \
         Node C <              > Node D
      
      More information is available on the open-mesh.org wiki[1].
      
      This patch adds the initial code to support network coding in
      batman-adv. It sets up a worker thread to do house keeping and adds a
      sysfs file to enable/disable network coding. The feature is disabled by
      default, as it requires a wifi-driver with working promiscuous mode, and
      also because it adds a small delay at each hop.
      
      [1] http://www.open-mesh.org/projects/batman-adv/wiki/CatwomanSigned-off-by: default avatarMartin Hundebøll <martin@hundeboll.net>
      Signed-off-by: default avatarMarek Lindner <lindner_marek@yahoo.de>
      Signed-off-by: default avatarAntonio Quartulli <ordex@autistici.org>
      d353d8d4