Repository : ssh://git@diktynna/doc
On branches: backup-redmine/2020-08-16,master
commit 20a0ea2cdf115f1bf8ec0f5a21469b449f50d911 Author: Sven Eckelmann sven@narfation.org Date: Sun Aug 16 23:54:11 2020 +0200
doc: Drop old GSOC pages
Signed-off-by: Sven Eckelmann sven@narfation.org
20a0ea2cdf115f1bf8ec0f5a21469b449f50d911 open-mesh/Gsoc2010-ideas.textile | 91 -------------------------- open-mesh/Gsoc2011-ideas.textile | 131 ------------------------------------- open-mesh/Gsoc2011-roadmap.textile | 15 ----- open-mesh/Gsoc2012-ideas.textile | 9 --- 4 files changed, 246 deletions(-)
diff --git a/open-mesh/Gsoc2010-ideas.textile b/open-mesh/Gsoc2010-ideas.textile deleted file mode 100644 index f27ed34..0000000 --- a/open-mesh/Gsoc2010-ideas.textile +++ /dev/null @@ -1,91 +0,0 @@ -h1. Gsoc2010 ideas - -h2. Requirements for students - -* Excited interest in Mesh networking technologies -* Routing and networking knowledge in general -* Programming language: C - -h2. Recommended and/or useful - -These things are not a prerequisite but might be very useful and/or have to be learned during the GSoC anyway. -* [[Linux kernel coding style]] -* Reading the documentation of the algorithms: https://git.open-mesh.org/?p=batman-adv-doc.git https://tools.ietf.org/html/draft-wunderlich-openmesh-manet-routing-00 (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 (especially with how to handle and avoid memory management/race conditions/deadlocks) -* monitoring packet flow (using tcpdump / wireshark + wireshark batman-adv dissector) - - -h2. Ideas - - - -h3. link layer fragmentation / compression - -*Brief description:* Introducing link-layer fragmentation and header compression to offer alternative packet overhead solutions. - -Due to the packet encapsulation performed on each and every payload packet going through the mesh a small overhead is introduced. This overhead (24 bytes at the moment) must be dealt with by the admins deploying the batman-adv mesh. The most common solution is to increase the maximum packet size on all mesh interfaces to maintain the standard MTU of 1500 bytes on all client devices. While this works in most cases it does not work for everyone. Some devices / drivers don't support or allow bigger packets. Alternatively, each client has to reduce its MTU to 1476 bytes which is often not manageable. This project shall address the issue by either compressing the payload packets (e.g. VJ compression) and/or implement a lightweight link layer fragmentation and/or develop another solution. - - -h3. forward error correction - -*Brief description:* Forward error correction to avoid retransmissions in the mesh network. - -Wireless networks rely on a lossy transport medium - even under optimal conditions packets get lost and have to be retransmitted. This comes at an even greater cost since the air is a shared medium (only one participant can transmit data at any given time) retransmissions have a severe impact on the network's performance. In addition to the packets which have to travel over several hops towards their destination, higher layer protocols (e.g. TCP) expect ACK packets to travel back over the chain of connected mesh nodes otherwise the transmission starts anew. This project aims to avoid retransmissions by implementing a packet forward correction for the batman-adv payload packets. A parity packet would be injected into the packet flow which allows the receiving batman-adv node to calculate & deliver the lost packet without further retransmissions. The parity packet rate can by dynamically adjusted depending on the link quality towards the final destination. - - -h3. B.A.T.M.A.N. protocol overhead reduction - -*Brief description:* Split the currently used OGM packets into two separate types to reduce the amount of packets flooded in the neighborhood. - -The traffic B.A.T.M.A.N. IV generates to discover the best path through the network is quite low compared to other protocols, but especially when B.A.T.M.A.N. has many single hop neighbors which rebroadcast each others OGMs we see room for improvements. The project shall optimize the flooding algorithm by splitting the originator message into two different message types. The OGM will remain but only be used to flood the TQ throughout the network. The new message type (a name needs to be found) will contain the link qualities of the single hop neighbors only. This message won't be rebroadcasted and just reaches the local neighborhood. These local message can be sent much more often than the global TQ messages and thus reduce the traffic [nearly just create a linear growth of traffic with more nodes in the local neighborhood instead of a squared amount]. - - -h3. B.A.T.M.A.N. protocol convergence speed - -*Brief description:* Implement a fast changing environment detection algorithm to let mobile nodes adapt to their new surroundings faster. - -Fast moving nodes always have the problem of adjusting their routing information in time. They can choose to send more routing information, so that their environment can adjust to them but stationary nodes won't do the same and increase the mobile node's adaption time greatly. However, when a B.A.T.M.A.N. node detects that its local environment changed quickly, it will enter the starvation mode. In this mode the node will actively try to confirm a working route as fast as possible by sending a "batman ping" to its new neighbors. Each B.A.T.M.A.N. neighbor will try to forward the message to its destination, once arrived there it will travel back. If the mobile node receives the reply it can change its route towards the new neighbor without waiting for normal OGM flooding as the route has been verified. The goal of this project is to implement the starving mode together with the "batman ping". - - -h3. Optimize multicast performance - -*Brief description:* Avoid broadcasting multicast traffic to nodes not belonging to a certain multicast group. - -Multicast packets would have a great advantage especially in wireless mesh networks: The number of recipients of multicast packets (i.e. for zeroconf service announcements or audio/video streams) is a lot higher then with unicast packets. batman-adv currently handles multicast packets the same way as broadcast packets, they simply get flooded through the mesh network. Instead, those packets should be flooded on a subgraph containing the nodes of a certain multicast group and other connecting nodes only. - - -h3. Dynamic OGM 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. - - -h3. More batctl ping/traceroute options - -*Brief description:* Add useful options for administrating a mesh network to batctl. - -batctl is the nicer frontend for configuration and debugging batman-adv. There are still some options that could be added like showing the MTU of hops with traceroute along a path to make it easier to spot MTU issues. Or outgoing interface selection to be able to manually probe the way and quality of an alternative path. Feature proposals that make the administration of a complex mesh network more easy are welcome. - - -h3. Live VIS in map - -*Brief description:* Building tools that visualize the dot output of the vis server with additional gps coordinates on a map. - -With every new technology, a bridge to non-technical people should be provided as well. batman-adv is being used in routers of every-day users, that do not have an insight in the B.A.T.M.A.N. routing protocol itself, nevertheless a good visualization can widely increase the acceptance of a new technology and get young people interested in it. batman-adv has a built in vis-server which produces a raw dot-file when activated. With the help of graphviz-tools, those dot-files can be rendered as graphs which are still more interesting for 'technical' people. It would be great to have a tool that maps the information provided by the dot-output and additional geo coordinates in Google-Maps or OpenStreetMap (!OpenLayers) in realtime. Then 'normal' people could find out and solve dead zones without technical support all on their own without having to use fancy command line tools. This feature would be useful for anyone administrating (parts of) a mesh network. - - -h3. Multiple interfaces per node support in Mesh3D - -*Brief description:* Adapting Mesh3D to handle the new visualization format features from current batman-adv. - -Mesh 3D is an application written in C and maintained by one of the batman-developers which is able draw a 3 dimensional graph from batman's vis output in dot-format. The latest additions in batman-adv's vis output that now features a differentiated visualization, in that interface connections between nodes are now being shown separately. This new format feature has not been ported to Mesh3D yet. Also a concept for visualizing overlapping links in Mesh3D would probably have to be planed (adding transparency to Mesh3D for instance). - - -h3. Multiple switch ports for redundancy - -*Brief description:* Allow multiple bridge uplinks to wired networks - -It is often desired to have multiple uplinks to a (wired) switched network where the B.A.T.M.A.N. protocol is not used. This may be a data center or a core network where multiple or redundant connections are needed. However if the Mesh network device and Ethernet device are bridged on multiple nodes, bridge loops are created. Traditional measures like (R)STP don't help in this situation as they may disable the (good) Ethernet Links. A solution should be developed where we can use multiple (redundant) uplinks to the same core switch network while effectively avoiding switch loops. \ No newline at end of file diff --git a/open-mesh/Gsoc2011-ideas.textile b/open-mesh/Gsoc2011-ideas.textile deleted file mode 100644 index 7d68a72..0000000 --- a/open-mesh/Gsoc2011-ideas.textile +++ /dev/null @@ -1,131 +0,0 @@ -h1. Google Summer of Code 2011 - Ideas - - - -h2. batman-adv - -h3. Categories + Usecases to improve - -* Increasing Robustness -* Improving Mobility / Convergence Speed -* Improving Indoor performance -* Improving [[VoIP]] group multicast performance -* Improving nomadic scenarios (circular + chain topology) - - -h3. Specific Tasks - -h4. 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. - - -h4. 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 [[batman-adv:bcast-hidden-node|here]] for a more detailed description of the problem and a solution proposal. - - -h4. 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" / "Or prioritized queues could be introduced. - - -h4. 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. - - -h4. 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. - - -h4. 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 aceesing 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. - - -h4. 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":https://tools.ietf.org/html/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. - - -h4. 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":https://en.wikipedia.org/wiki/Multipoint_relay mechanisms. - - -h4. 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. - - -h4. 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 [[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. - - -h4. 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. - - -h3. 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?":https://en.wikipedia.org/wiki/Linear_network_coding -* Packet signing: Add a signing mechanism to identify OGM's sender and drop malicious nodes -* built-in bandwidth test tool ? - - -h2. 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?) - - -h2. misc - -* multiple interface support in Mesh 3D -* ap51flash GUI; ap51flash multi-flash on single interface -* Android/Maemo/Meego porting + _maintenance_! -* Cooperative work with Pidgin persons? (video/audio/file-transfer/bonjour in pidgin and improving its + batman-adv's combined performance in a mesh network?) \ No newline at end of file diff --git a/open-mesh/Gsoc2011-roadmap.textile b/open-mesh/Gsoc2011-roadmap.textile deleted file mode 100644 index 453e7ce..0000000 --- a/open-mesh/Gsoc2011-roadmap.textile +++ /dev/null @@ -1,15 +0,0 @@ -h1. Google Summer of Code 2011 - Roadmap - -h2. Linus - -* Document NDP-OGM integration -* Document reactive OGM protocol -* Rename NDP -* Adding changes discussed at WBMv4 to NDP -* Rewrite proactive OGM protocol -* Implement reactive OGM protocol (simple) -* Testing -* Reviewing, add feedback -* ... -* (NDP EWMA) -* (reactive OGM protocol, more generic) \ No newline at end of file diff --git a/open-mesh/Gsoc2012-ideas.textile b/open-mesh/Gsoc2012-ideas.textile deleted file mode 100644 index 69bcfc1..0000000 --- a/open-mesh/Gsoc2012-ideas.textile +++ /dev/null @@ -1,9 +0,0 @@ -h1. Gsoc2012-ideas - -We have a page with several ideas/research proposals that you can check ([[ResearchProposals]]). -Feel free to pick one of them and contact us on the mailing-list to discuss about it! - -last years: - -* [[Gsoc2011-ideas]] -* [[Gsoc2010-ideas]] \ No newline at end of file