| Presents: | |
| Pedro Villanueva | |
| eduardov79@yahoo.com |
| Presentation | |
| OLSR – Technical Description | |
| Research Target | |
| PRESENTATION |
| System for exchanging information (e.g. messages) among two or more hosts. | |
| The information is passed over a single or multiple links. |
| Wireless hosts (mainly standard 802.11) | |
| Communication without a fixed infrastructure | |
| Nodes behave as hosts and as routers | |
| The hosts are mainly assumed to be mobile | |
| Self-configuring network | |
| Medium range |
| Nodes inside the transmission radius of any node “S” are considered neighbors (1 hop away distance) | |
| The communication with no-neighbors is achieved in multi-hop fashion |
| Soldiers on the battlefield | |
| Laptop networks in conference room | |
| Emergency disaster relief networks |
| Mechanism for finding paths from source host to destination host. | |
| Routing Protocol: Facilitates the exchange of information to support routing between networks. | |
| Routing information is stored in “routing tables” by the routers. |
| Protocols use different metrics to find network paths. | ||
| Hop count, bandwidth, delay, path cost, load, link quality (wireless). | ||
| Routing Technologies | ||
| Flooding (the simplest) | ||
| Distance-vector routing (e.g RIP ) | ||
| Links-state routing (e.g OSPF ) | ||
| Interior Gateway Protocols | ||
| Exchange the routing information inside a single autonomous system (e.g. RIP, OSPF, IGRP, EIGRP, IS-IS) | ||
| Exterior Gateway Protocols | ||
| Exchange the routing information between separate autonomous systems (e.g. EGP, BGP) | ||
| The routers exchange their routing tables. They say: “For me the network looks like…” | |
| Advantages | ||
| Simple and efficient for small networks | ||
| The required management is minimum | ||
| Routing tables are sent only to neighboring nodes | ||
| Disadvantages | ||
| Not scalable!!! | ||
| Poor convergence properties | ||
| The exchanged routing tables might be very large | ||
| The routers flood, the availability of links to their neighbors. They say: “My neighbors are…” |
| Advantages | ||
| React quickly and in a bounded amount of time to topology changes (Faster convergence) | ||
| Exchanged information is small | ||
| More scalable than Distance-Vector | ||
| Disadvantages | ||
| Requires larger storage and CPU power to maintain the network map (more expensive to support) | ||
| Exchanged information is flooded into the network | ||
| OSPF (Open Shortest Path First) | |
| Link State, Interior Gateway Protocol | |
| Dijkstra’s algorithm is used to calculate the shortest path to any destination from a source “S” | |
| Link state database is constructed at each router | |
| Link cost is the routing metric |
| OLSR (Optimized Link State Routing Protocol) | |
| Optimizes the link state flooding mechanism | |
| Multipoint Relay (MPR) nodes achieve the optimization | |
| A set of MPR nodes is chosen by each node in the network | |
| The node’s view of the topology becomes partial | |
| Proactive Protocol (Routes immediately available) |
| MPR nodes are chosen in such a way that every 2-Hop neighbor can be reached by the MPRs | |
| OLSR – Technical Description |
| OLSR Host | ||||
| OLSR Interfaces (Each one with unique IP) | ||||
| None (It may be injected to the OLSR routing domain) | ||||
| Single | ||||
| Multiple | ||||
| Main address and Secondary addresses | ||||
| Main Address | ||||
| Node identifier | ||||
| IP address of any interface | ||||
| Nodes | ||
| Neighbor | ||
| 2-Hop neighbor | ||
| Strict 2-Hop neighbor | ||
| Multipoint relay (MPR) | ||
| Multipoint relay selector (MPRS) | ||
| Link Type | |||
| Asymmetric | |||
| Symmetric | |||
| Link Status | |||
| Down | |||
| Up | |||
| Good quality | |||
| Medium quality | |||
| Poor quality | |||
| Data Packets | ||
| Transmit user’s information from a source to a destination | ||
| The information is referred as the “payload” of the packet | ||
| Control Packets | ||
| Transmit protocol supporting data | ||
| Mostly transmitted before Data Packets | ||
| From next slide onwards referred as “Packets” only | ||
| 0 1 2 3 | |
| 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | Packet Length | Packet Sequence Number | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | Message Type | Vtime | Message Size | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | Originator Address | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | Time To Live | Hop Count | Message Sequence Number | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | | | |
| : MESSAGE : | |
| | | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| | Message Type | Vtime | Message Size | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |
| (etc.) | |
| OLSR Packet Format |
| Transmitted packets are temporally stored | ||
| Forwarding is performed on all interfaces by the MPR nodes | ||
| Unknown messages are forwarded once by the so called Default Forwarding Algorithm | ||
| If required some messages can bypass the MPRs | ||
| Nodes add jitters to avoid messages collisions | ||
| Jitter = random delay before retransmitting | ||
| Duplicate Set | ||
| Interface Association Set (interface - main address) | ||
| Link set (symmetric, asymmetric or lost) | ||
| Neighbors (symmetric, not_symmetric and willingness) | ||
| Neighbor set | ||
| 2-hop Neighbor set | ||
| MPR | ||
| MPR set | ||
| MPR Selector set | ||
| Topology set (Destination and previous hop) | ||
| OLSR interfaces are linked to main address | |
| Each node announces its multiple interfaces | |
| Multiple Interfaces Declaration (MID) messages | |
| MID messages are flooded by MPRs (TTL=255) | |
| Only Link Sensing uses this information |
| Generated per each node on each interface | |
| Advertises the entire 1-hop neighbourhood | |
| Willingness to carry and forward traffic (MPR) |
| Based on local link set, neighbour set, MPR set | ||
| Support link sensing, neighbour detection and MPR signalling | ||
| Link Types: | ||
| Unspecified, Asymmetric, Symmetric, Lost | ||
| Neighbour Types: | ||
| Symmetric, MPR, Not Neighbour | ||
| Populates the Link Set | |
| Based on the exchange of Hello messages | |
| Detects links with neighbors | |
| Each link can be symmetric or asymmetric | |
| Populates the Neighbor Set | |
| Based on status and changes of the Link set | |
| Populates the 2-hops neighbor set | |
| Populates the MPR set | |
| Populates the MPR selector set |
| MPRs optimize the classical flooding mechanism | |
| Each node selects its own MPRs from its 1-hop symmetric neighbours | |
| Through the MPRs all symmetric strict 2-hop neighbours must be reached | |
| Recalculated when symmetric neighbourhoods change (1-hop or strict 2-hop) | |
| MPRs are signalled as MPR neighbour type, inside Hello messages | |
| MPR Selector (MPRS) set is populated when any node is signalled as a MPR neighbour | |
| MPRs are computed per interface. | |
| MPR candidate nodes must have willingness different from Will_Never |
| MPR set = Ř | |
| MPR += 1-hop neighbors with willingness=Will_always | |
| MPR += 1-hop neighbors that are the only ones reaching a 2-hops neighbor | |
| Remove the 2-hop neighbors reached by the MPRs | |
| Add 1-hop nodes (to the MPR set) providing maximum reachability of 2-hop neighbors UNTIL reaching all 2-hop neighbors. |
| Information dissemination to construct routes | |
| Broadcast by MPRs only | |
| Links between an MPR and its selector set (Advertised Neighbor set) are the minimum information that must be broadcast |
| The disseminated topology view is partial | |
| The ANSN (Advertised Neighbor Sequence Number) keeps track of the most recent information. | |
| The topology information supports the routing table calculation mechanism |
| Each node maintains its own routing table | ||
| Based on the Link and Topology sets. | ||
| Recalculated (without transmitting any message) when a change is detected in either: | ||
| Link set | ||
| Neighbor set | ||
| 2-hop neighbor set | ||
| Topology set | ||
| Multiple interface association set. | ||
| Calculated using a shortest path algorithm | |
| Assuming existence of: |
| MANET nodes must be part of the same subnet | |
| Additional networks connected to the MANET must be part of distinct subnets | |
| MANET nodes connected to external networks must provide paths to them | |
| OLSR maintains the Routing Table but it DOES NOT perform packet forwarding |
| Interfaces connected to separate network | |
| External route information has to be injected into OLSR domain (MANET) | |
| It is injected by Gateway nodes broadcasting HNA (Host and Network Association) messages | |
| Gateways broadcast external network address and network mask | |
| Information is stored in the Association Set | |
| HNA messages are similar to TC messages | |
| RESEARCH TARGETS |
| Relax MPR selection mechanism to satisfy multiple path-constraints | |
| Provide multiple paths to same destination for load balancing | |
| Extend the OLSR messages to distribute node and link specific information |
| Relax the partial view of the network topology to provide enough constraint-compliant links | |
| Increase Routing Reliability | |
| Gradually and dynamically adjust the amount of topology information exchanged while maintaining flooding optimality |
| Multiple paths for any destination will be provided (when possible) | |
| Paths will be introduced in the routing table and will be ranked according to their optimality | |
| OS kernel has to be modified to allow multiple paths for same destination |
Multiple-Paths to destination (2)
| OS forwarding mechanism will make use of multiple paths when required |
| The new messages will be designed by following the OLSR-RFC specifications in order to make them compatible with any OLSR implementation | |
| The information carried by the new messages will be provided by the Data Collection group |
| The node-specific information might include: | ||
| Remaining battery | ||
| Available buffer space | ||
| The link-specific information might include: | ||
| Bandwidth available | ||
| Error rate | ||
| Signal strength | ||
| Presented by: | |
| Pedro Villanueva | |
| eduardov79@yahoo.com |