Ideas GSoC 2013

Aus wiki.freifunk.net
Wechseln zu: Navigation, Suche

B.A.T.M.A.N.

batman-adv

Useful Skills:
- Linux kernel coding style
- Reading the documentation of the algorithms: batman-adv-doc batman-rfc-draft (used in the 'old' batmand)
- Being able to use virtual machines for debugging (i.e. qemu)
- Being able to install a mesh network with OpenWRT and batman-adv
- Kernel coding experiences (locking, memory handling, sk_buffs, ...)
- monitoring packet flow (using tcpdump / wireshark + wireshark-batman-adv dissector

Categories + Usecases to improve

* Increasing Robustness
* Improving Mobility / Convergence Speed
* Improving Indoor performance
* Improving VoIP group multicast performance
* Improving nomadic scenarios (circular + chain topology)

Specific Tasks

Dynamic OGM+NDP intervals

Brief description: A batman-adv node shall select originator interval rates according to the dense and dynamics in its closer environment.

Depending on the usage scenario, people can adjust the bandwidth being used for batman-adv's route finding algorithms. Usually people were advised to increase the originator interval if the mesh network is small but needs fast route refresh rates or to decrease it if the mesh network is mostly a static setup with a lot of nodes. It would be great if a batman-adv node could determine the dynamics of the mesh network it is currently participating in on its own so that this option would not have to be administrated from a person anymore. For instance in combination with the 'B.A.T.M.A.N. protocol overhead reduction' project, the local broadcasts could be automatically increased if there are not that many direct neighbors.

OGM/NDP Hidden Node Problem Avoidance

Brief description: Implement a suitable solution against hidden node broadcast packet problem.

Especially in indoor scenarios where corners and thick walls are involved, hidden nodes can be a severe problem. Usually activating RTS/CTS is a common way of solving this problem at least to some degree. However, RTS/CTS can only be applied for unicast packets. Therefore a node sending a lot of data packets to another one, even with RTS/CTS those packets will interfere with BATMAN's broadcast packets (e.g. NDP packets or OGMs). The effect is, that the transmit quality of a node sending NDP packets which does not see the data packet transmission will greatly decrease.

A suitable solution shall be implemented. This might be based on time slots, multiple interfaces or channel switching and might be implemented within batman-adv or an extra module. See here for a more detailed description of the problem and a solution proposal.

OGM/NDP Congestion Avoidance

Brief description: Implement a congestion avoidance mechanism for batman-adv's routing control packets against congestion caused by high data transfer rates.

In case of a mesh network congested due to e.g. a lot of UDP packets, the packet loss rate of batman's OGMs or NDP packets increases severely, as neither OGMs/NDP nor UDP have a congestion control mechanism. For one thing, lost OGMs lead to a high degradation of batman's convergence speed. For another, lost NDP packets lead to route flipping; in the worst case some of these chosen routes are not usable. batman-adv has the advantage of being able to control the whole packet, both data and control packets, within the mesh network. Therefore time spaces for OGMs/NDP packets could be allocated, as already described in "OGM/NDP Hidden Node Problem Avoidance" / [1]. Or prioritized queues could be introduced.

B.A.T.M.A.N. Routing Framework

Brief description: Separate B.A.T.M.A.N. routing algorithm from routing infrastructure in batman-adv.

Many features in batman-adv are routing algorithm independent: Link layer routing, link layer fragmentation, multicast optimizations, NDP, interface bonding. To allow other routing algorithms to use this already well tested infrastructure, the B.A.T.M.A.N. routing algorithm shall be separated more clearly from the routing infrastructure. Ultimately, other routing protocols shall be able to control the kernel space mesh routing infrastructure from userspace.

Improve Throughput Bonding

Brief description: Improve performance gain of the throughput bonding mode.

The current bonding mode implementation simply sends a data packet in a round robin fashion to the interfaces available for bonding. However, the throughput gain seems to be only about 66% instead of doubling the throughput in case of TCP, even if there is no other interference involved. This seems to be the case due to a heavy reordering issue. Furthermore, the interface with the lowest capacity is a bottleneck for the throughput bonding performance: In case of one interface of 1MBit/s throughput and five more with 2MBit/s throughput, the actual throughput will be just 6x 1MBit/s. However in mixed wireless and wired networks, it might be desirable to accumulate the throughput of a Gigabit-Ethernet interface and a 802.11g interface. Therefore checks for links' capacities (detect full queues etc.) to gain performance of IF1 + IF2 + ... instead of min(IF1, IF2, ...) shall be implemented. If an interface is busy, it shall be skipped in this round robin cycle. Furthermore simple per hop pre-ordering on batman-adv's layer shall be implemented to increase the TCP performance.

Unit Test Infrastructure

Brief description: Create a flexible unit test infrastructure to increase batman-adv's stability.

As batman-adv resides in the Linux kernel any crash in batman-adv has severe consequences for the whole system. For instance a deadlock or accessing invalid memory in batman-adv will freeze the whole system. Typically most embedded routers have a watchdog to restart the device automatically in such situations. However in critical usage scenarios, a reboot of the device might not be tolerable. Therefore a unit test infrastructure shall be created which for one thing tests and verifies single functions and functionalities within the batman-adv code base. And for another it shall stress test the complete software for different virtualized, static and dynamic topologies.

IPv6 Stateless Autoconf Gateway Solution

Brief description: Implement a gateway solution for IPv6 stateless autoconfiguration

batman-adv operates on layer 2, therefore intelligent layer 3 gateway handling is not straightforward. batman-adv currently supports intelligent gateway handling for DHCP (both IPv4 and IPv6), in that it forwards any DHCP discovery or request packet to the best (according to batman's metric) gateway available only, via unicast. However, this is not doable for IPv6 stateless autoconfiguration, as usually not the client is not actively requesting an IP address, but the router is advertising it's gateway capabilities periodically. However, such a stateless configuration is usually more desirable than a stateful configuration as in DHCP in dynamic mesh networks as it allows smoother transitions between subnets and is not as prone to packet loss. Therefore a solution for IPv6 Stateless autoconfiguration shall be implemented. This may be done by exploiting the router preference fields in the router advertisement messages, RFC4191, and/or by limiting the range of router advertisements with the help of batman-adv's broadcast packet's TTL field or by introducing a new TQ limit field. A TQ limit field could be dynamically adapted to minimze the overhead of such router advertisements in case of many gateways but ensuring the availability of the best/closest of all gateways in the mesh network.

Improve Broadcast Data Performance

Brief description: Optimize the flooding of broadcast data to reduce overhead and increase its packet delivery ratio.

So far broadcast data packets are flooded through the whole mesh network. As broadcast packets do not have an ARQ mechanism to reduce packet losses like unicast data transfer has, batman-adv (re)transmits broadcast packets on each hop by default. In dense topologies this can introduce unnecessary overhead, in sparse topologies the packet delivery ratio might be too low. Therefore a smarter mechanism than classic flooding shall be implemented to improve batman-adv's performance for broadcast data packets. This may done taking link qualities in the local neighborhood into account and adjusting the number of rebroadcasts dynamically. Or by introducing MPR-like mechanisms.

Reduce ARP (/ND) latency and overhead

Brief description: Reduce ARP latency and overhead by implementing an ARP cache.

batman-adv operates on the link layer, therefore any network protocol (e.g. IPv4/6) needs to perform an MAC address lookup for any IP address through the mesh network first. As ARP packets are broadcast packets, batman-adv simply floods them through the whole mesh network. This can create quite some overhead in large scale mesh networks or high latencies in case of mesh networks with poor links. Therefore an ARP cache shall be implemented on each node so that they could answer ARP requests directly to any host on their segment instead of flooding it through the whole mesh again. Something similiar may be implemented for IPv6's Neighbor Discovery (ND) mechanism.

Dead node fast path switching/invalidating

Brief description: Improve batman-adv to respond quicker to node/link failures and avoid packet drops in case of link failures.

When a node notices the breakdown of a neighbor (see [wiki:routing_scenarios#Convergencespeed routing scenarios] to get an idea about the conditions), this node could send any data packet, which it would usually send over this neighbor to either its second best hop if available (which does not always have to be the case due to OGM forwarding policies). Or it could send the packet back to the next hop towards the source again. With the help of sequence numbers, any node on the 'backtracking' path (the backtracking path can be different from the usual path in case of asymmetric links) could notice that a path became invalid very quickly.

Link layer FEC/ARQ/Fragmentation module

Brief description: Create a kernel module that can be added onto an interface which performs link layer optimizations (FEC, ARQ, Fragmentation, ...).

The ARQ and FEC mechanisms provided in 802.11 for unicast data packets is mainly optimized for one hop scenarios only. While the packet delivery ratio on one hop might be fine, it might not be usable for multiple hops in a mesh network. Therefore a link-layer kernel module shall be implemented which performs Forward Error Correction and Automatic Repeat reQuest with dynamic parametrizations, to achieve a certain, configured target packet delivery ratio. Furthermore, the fragmentation from batman-adv could be moved to this link layer module, too. Such a module would then provide a virtual interface which batman-adv would use instead of the actual wifi/ethernet interfaces.

Further Tasks

* Link quality / Packet delivery ratio measurement improvements
 -> weighted/exponential moving average
 -> testing / performance measurements of / improving NDP, find and improve "performance bottlenecks"
* Multicast Optimization Algorithm enhancements
 -> implement reactive tracker packet mode
 -> decrease latency of reactive tracker packet mode: attaching small data packets to tracker packet, if MTU fits (otherwise broadcast) in react. mode? ...?
 -> ultimately, make proactive tracker mode obsolete
 -> optimize number of rebroadcasts (we have the info about the number of next hop nodes)
 -> don't send tracker packets if <= 1 destination or > 50% of all nodes are destinations
 -> Enhance HNA, host network announcements, improvement scheme to also support MCAs, multicast announcements
 -> ...
* Further HNA roaming improvements
* Network Coding?
* Packet signing: Add a signing mechanism to identify OGM's sender and drop malicious nodes
* built-in bandwidth test tool ?

batctl

* Enhance live link quality monitoring: bisect -> dot-files -> graphs -> to (live) video? (+ adding horst tool information, wifi interface stats?)
* Add further info to batman-adv vis servers/clients for debugging networks
* bisect, include initial state
* live vis in map (HTML5 + Openstreetmap?)

misc

* multiple interface support in Mesh 3D
* ap51flash GUI; ap51flash multi-flash on single interface
* !Android/Maemo/Meego porting + _maintenance_!
* Cooperative work with Pidgin guys? (video/audio/file-transfer/bonjour in pidgin and improving its + batman-adv's combined performance in a mesh network?)


Funkfeuer

misc

  • port LXC to the ulibC: currently the lightweight virtualization LXC needs eGlibc on openwrt. However, eGlibc is quite heavy weight. The standard libc in openwrt is ulibC. This project aims at porting LXC to uLibC


OLSR

General description

OLSR (www.olsr.org) is the first and one of the major deployed mesh routing daemons in wireless community networks all over the planet! It still performs very stable in practice and it scales nicely. It is widely deployed throughout the world.

The following is a list of potential topics for OLSR mesh programing projects:

routing socket support in BSD

Update the bsd-routing-specific parts of olsrd which are quite outdated, and miss many features that where only implemented for the liux netlink (which is quite similar to the bsd routing socket)

Usefull skills C programming with sockets, strong TCP/IP knowledge , *BSD System programmer knowledge
Type of work Coding
Level from Beginner 1-5 Professional: 4

smart-gw support in BSD

Port the automatic gateway tunnel code to *BSD systems. This involves intricate knowledge (or the strong desire to learn ) BSD routing and socket code. You can get inspired from the Linux IP-IP tunnel code.

Usefull skills C programming with sockets, strong TCP/IP knowledge , *BSD System programmer knowledge
Type of work Coding
Level from Beginner 1-5 Professional: 4

SNMP Plugin for OLSR

SNMP plugin for OLSR. Very often a routing daemon must be accessible via SNMP. This is still missing in OLSR. There are example implementations available. See for example: http://sourceforge.net/projects/olsrd-snmpd. However this implementation was against an old version of OLSR.


Usefull skills C programming with sockets, strong TCP/IP knowledge , good SNMP knowledge
Type of work Coding
Level from Beginner 1-5 Professional: 4

central logging plugin

central logging plugin: we already have a debuginfo plugin but this needs to be enhanced to allow logging of important statistics and routing decisions to a central logging server or database. Once it is possible to log OLSR information to this central DB, this will help developers to understand why certain routing problems appeared. Take the time to review how this could be interwoven with the node databases that exist (cf. http://wiki.freifunk.net/Ideas#Define_a_common_node_database_schema) and think and discuss how this can be integrated there.

Usefull skills C programming with sockets, strong TCP/IP knowledge , some SQL knowledge
Type of work Coding
Level from Beginner 1-5 Professional: 3

port OLSR to Windows with IPv6 support

IPv6 support under Windows XP and Windows 7 is new terrain for OLSR.org. Since OLSR very portable but none of the core developers uses Windows a lot, the ports to Windows are always not so well maintained.

Usefull skills C programming with sockets in windows (Winsock Library), strong TCP/IP knowledge , IPv6 programming knowledge
Type of work Coding
Level from Beginner 1-5 Professional: 3


new routing metrics for OLSR

This is a fun project because it involves testing with real world equipment and building and measuring with real world mesh Wi-Fi routers. Implement a different routing metric which reacts better to the properties of Wi-Fi (packetloss, channel assignments, etc). Deploy it in a test network and compare routing metrics. Document your results. OLSR already contains a few sample metrics so the process of writing a new metric is well understood. But we found no nice, cross platform approach to support different Wi-Fi cards, operating systems etc in a cross platform way. Most layer 2 info such as signal strength is highly dependant on the actual Wi-Fi driver and card. In this project this does not matter, but you should know that you need to use identical hardware, otherwise you might have non comparable results. Take a look at the work being done at the IETF (DLEP in the MANET WG): http://tools.ietf.org/html/draft-sratliff-manet-dlep-00

Usefull skills C programming with sockets, strong TCP/IP knowledge , fun with hands-on
Type of work Coding
Level from Beginner 1-5 Professional: 3

MPR Algorithm

Make MPR work again: the MPR algorithm ("multipoint relay") is the "O" ("optimized link state routing") in OLSR. However, due to modifications of the Dijkstra algorithm implementation , MPR was effectively switched off. This means that the current -stable tree of OLSR floods messages too far. This reduced the available airtime and bandwidth in the air. This was already fixed in the development (-master) branch but needs to be backported to -stable. Fixing this requires you to obtain a deep understanding of link state routing protocols (Dikjstra etc)

Usefull skills C programming with sockets, strong TCP/IP knowledge , Good knowledge of datastructures and Dijkstra algorithm.
Type of work Coding
Level from Beginner 1-5 Professional: 4-5

Multi-tree OBAMP implementation in OLSR

In GSoC 2009 Saverio Proto ported the OBAMP protocol for overlay multicast in C, as a plugin of the OLSR routing protocol. The current implementation creates a multicast distribution tree among all the OBAMP node in the mesh network.

The plugin can be extended creating one multicast tree for every multimedia stream broadcasted into the network, creating basically different OBAMP groups. This optimizes data distribution and strongly reduces bandwidth waste.

Usefull skills C programming with sockets, strong TCP/IP knowledge
Type of work Coding
Level from Beginner 1-5 Professional: 4 Semi-professional

References:

OLSR plugin for Freimap

The idea is to create a plugin for OLSR to enable the node to interact directly with Freimap to form a single channel for communication of all necessary informations (connected clients, status, number of interfaces and routes, state of the link, etc ...) and if necessary query the others active plugins to retrieve the required information (eg http_info plugin, dot_draw plugin, etc).

Usefull skills Linux
Type of work Coding, Networking
Level from Beginner 1-5 Professional: 3 Advanced

Reference:

Topology visualization / B.A.T.M.A.N and olsrd routing decision recovery for freimap

Freimap Screenshot - an olsr topology

  • In order to better display traffic flows in freimap, they should be drawn along the actual route the packets take. This information can be computed theoretically using knowledge of the routing algorithm, the topology and the routing metrics at a specific point in time. This might be compared to actual bandwith metrics of a given link to validate the model.
Useful Skills: Java, Mathematics, Vizualization
Type of Work: Research, Java/Implementation
Level from Beginner
1-5 Professional:
3 Advanced

Babel

http://www.pps.jussieu.fr/~jch/software/babel/ , https://tools.ietf.org/rfc/rfc6126.txt

  • Port Babel to Quagga. Since Babel is designed to be portable (all the system dependencies are cleanly encapsulated in a single file), this should not be too difficult.
  • Port Babel to NS2. More difficult than the above, since NS2 is a mess.
  • Visualisation software for mesh networks. Both BabelDraw and Bab el-web are somewhat unsatisfactory; hopefully we can make a piece of software that's pretty, useful, and can serve as a basis for a multi-protocol monitor (i.e. be able to work equally well with Babel, OLSR and BATMAN).


wlan slovenija

Freifunk is acting as an umbrella organization also for wlan slovenija open wireless network. List of ideas proposed by this network (and mentored by its mentors) can be found here. More information about wlan slovenija participation in the GSoC is here.


Guifi.net

  • GSoC ideas here (Spanish only at the moment)

Wireless adhoc filesharing application (alternative to AirDrop)

I'm hoping to develop filesharing application that auto discover and maintain nodes in wireless network. It will use fisheye state routing for large file transfering and for small file sharing it will use OSLR. It may have optional method like torrent to share a file within the wireless network. It will also have a method to avoid congestions. Otherthan that this would be KDE/Gnome (hope to transport to windows/mac platform too) dekstop application. Even sticky notes and tomby notes could be shared through this. I know C/java/python. So willing to adopt any language the mentor is familiar with. But my preferance is with python.

I am the author of this idea and I'm looking for a mentor for this project. My email is lolitha88@gmail.com. Thank you for your kind co-operation.

CNML Explorer

My proposal is developing a desktop application to manage CNML files. It will be useful for people that administer zones, workers that install Guifi.net nodes... etc.

CNML files offer a lot of possibilities that are not being exploited actually. It can also be used for statistics, data visualization, which will help people in their studies, or thesis about libre networks.

This application will load a CNML file and show its contents in friendly windows. Users will be able to filter nodes or zones by name, coordinates or hardware used.

  • The whole proposal is available here.
  • More about CNML here

--Pablog 22:57, 20. Mär. 2012 (CET)

Semantic Backend for community networks

My proposal wants to improve the backend information model of community networks.

This would provide better ways to organize, share and use the information and align their infrastructure to the principles of open data. The main part is to port CNML based in XML to an ontology (RDF/OWL/Turtle) that could be loaded into a triplestore.

Check out the detailed proposal here.

-- Gblucas

BGP/Quagga plugin for bmx6 (& qMp fw integration)

Brief description:

  1. Implement a general bmx6-quagga plugin to import/export/redistribute routes (Main task in terms of expertise and time)
  2. Plugin integration it into qMp firmware (use case)

Background: Currently the vast majority of the guifi.net nodes are based on closed technologies (mainly Mikrotik). qMp is an effort of some guifi.net folks to provide a free alternative for the community. the OpenWrt based qMp firmware is already quite stable and complete and some guifi.net communities have already started using it.

The Problem:

The qMp firmware is using bmx6 as its main mesh routing protocol to auto configure multihop IPv4 and IPv6 connectivity between nodes in a mesh network cloud.

Currently, routing beyond the borders of the mesh clouds is achieved by manually configuring mesh-gw-nodes to statically announce the full IP range used by guifi.net via bmx6-hna/gw/tunnel announcements within the mesh cloud and, in the other direction, announce the sub-IP range used by the mesh cloud as a static route via BGP to other guifi.net nodes.

Whats missing, but highly desired, is an auto-configuration software solution to:

  • allow announcement of small (node-specific) prefixes
  • adapt to the dynamic nature of mesh networks (appearing and disappearing networks)
  • enable intra cloud routing

The Tasks:

  • Implement a bmx6-quagga plugin so that bmx6 can automatically exchange routes and metrics with BGP/Quagga.
  • Implement filtering rules to let bmx6 automatically select the to-be-announced routes based on a given policy.
  • Test the implemented functionality in a virtual network environment (like clownix.net).
  • Integrate the bmx6-quagga plugin in current qMp firmware.
  • Ideally: Test the enhanced qMp version in a GW-node of a real-live qMp-based mesh cloud.
  • Document the implementation and the configuration.

Requirements / Useful Skills:

  • Experience with typical community mesh-network characteristics.
  • Experience with BGP concepts and configuration (import/export/redistribute) in large community networks (like guifi.net).
  • General experience with development of embedded software systems and OpenWrt in particular.
  • Advanced Linux, routing, and C-Coding.
  • Willingness to gain experience with guifi.net and qMp node configuration.

Guifi.net integration for qMp system

Currently QMP is a working system, that can be used to easy deploy a Mesh Network but there are several missing features. One of them is the integration with the Guifi.net Network Community. It can also be used as a template for the integration of other Network Communities like Freifunk, Funkfeuer, AWMN, etc.

Guifi.net is using a web portal to administrate the nodes/links/owners/etc. The idea is that user register his node inside Guifi.net portal. From the qMp system, the user only needs to configure the node id (from the web site), and automatically all the information is downloaded and applied (IP, Name, Position, etc.).

http://qmp.cat http://guifi.net

Other Ideas

Add support for PGP encryption to Jitsi

http://jitsi.org/ is a promising IM software with builtin support for audio/video calls and conferences, desktop share, remote control, ecc.

In wireless communities is often needed to exchange ssh login information via chat, Jitsi supports OTR encryption so it can encrypt the chat texts but it cannot ensure that the other person is really who he/she claims to be, so PGP encryption would solve this problem, assumed that the people using it have an estabilished web of trust and have already authenticated and signed their keys.

Since Jitsi is pluggable, this feature could be added as an additional plugin.

Technologies: Java, OpenPGP

Mobile application for Wireless Community Networks

Description: The goal of the app is to offer users an easy way to share Internet connections potentially over several using mesh protocols. Other features of the app are maps with information about wireless community nodes and a wlan hotspot database aggregation. Users will be able to inform other users of the app about open wireless hotspots and provide access data. The app will offer information about community activities through twitter and identi.ca gateways. Lastly the app should be able to help newcomers planning new networks and provide services to collect data important for network planning. The app will help gathering information (coordinates, direction,..) from GPS and compass hardware present in almost every mobile system and the information gathered from a mapserver system containing the database of all the nodes, to easily find and then point a node where we want to connect all in an augmented reality system. To do so the application will exchange information with a mapserver both to obtain information of the nodes and also to insert his own position in to the database. The app wants also let know to as much people as possibile about wireless community through the app store system that this devices have built-in.

Technologies

Java, Objective-C, Phonegap, Google Maps API, MySQL, SOAP


Peer to peer sharebox based on Shark Framework

Shark, an acronym for Shared Knowledge, is a framework to develop peer to peer applications without the need for servers. The goal of the application is to offer a peer to peer service similar to dropbox services. The initial target are PC users, but implementations on smart phones will follow. Access to the application would be preferably by web interface. Encryption of transmitted data is a prerequisite.

Links: http://sharksystem.net

Technologies

Web technologies, HTML5, Tomcat, Servlets, JSP, Linux, Windows, MacOSX, Encryption


See also