1	Ad Hoc Networks Routing Presents: Pedro Villanueva eduardov79@yahoo.com
2	Outline Presentation OLSR – Technical Description Research Target
3	PART I PRESENTATION
4	Computer Networks System for exchanging information (e.g. messages) among two or more hosts. The information is passed over a single or multiple links.
5	Ad Hoc Networks 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
6	Ad Hoc Networks (2) 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
7	Ad Hoc Applications Soldiers on the battlefield Laptop networks in conference room Emergency disaster relief networks
8	Routing 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.
9	Routing (2) 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 )
10	Routing (3) 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)
11	Distance Vector Protocols The routers exchange their routing tables. They say: “For me the network looks like…”
12	Distance Vector Protocols (2) 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
13	Link State Protocols The routers flood, the availability of links to their neighbors. They say: “My neighbors are…”
14	Link State Protocols (2) 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
15	OSPF Protocol 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
16	OLSR Protocol 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)
17	OLSR Protocol (2) MPR nodes are chosen in such a way that every 2-Hop neighbor can be reached by the MPRs
18	PART II OLSR – Technical Description
19	Terminology 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
20	Terminology (2) Nodes Neighbor 2-Hop neighbor Strict 2-Hop neighbor Multipoint relay (MPR) Multipoint relay selector (MPRS)
21	Terminology (3) Link Type Asymmetric Symmetric Link Status Down Up Good quality Medium quality Poor quality
22	Terminology (4) 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
23	OLSR Packets 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
24	OLSR Message Types
25	Packets forwarding 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
26	Information Repositories 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)
27	Multiple Interfaces 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
28	Hello messages Generated per each node on each interface Advertises the entire 1-hop neighbourhood Willingness to carry and forward traffic (MPR)
29	Hello messages (2) 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
30	Link Sensing Populates the Link Set Based on the exchange of Hello messages Detects links with neighbors Each link can be symmetric or asymmetric
31	Neighbor detection 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
32	MPR computation 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)
33	MPR computation (2) 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
34	MPR computation (3) 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.
35	Topology discovery 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
36	Topology discovery (2) 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
37	Routing Table 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.
38	Routing Table (2) Calculated using a shortest path algorithm Assuming existence of:
39	Node configuration 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
40	Non OLSR-interfaces 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
41	Non OLSR-interfaces (2) Gateways broadcast external network address and network mask Information is stored in the Association Set HNA messages are similar to TC messages
42	Part III RESEARCH TARGETS
43	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
44	Relax MPR Mechanism 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
45	Multiple-Paths to destination 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
46	Multiple-Paths to destination (2) OS forwarding mechanism will make use of multiple paths when required
47	Extend OLSR messages 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
48	Extend OLSR messages (2) The node-specific information might include: Remaining battery Available buffer space The link-specific information might include: Bandwidth available Error rate Signal strength
49	Ad Hoc Networks Routing Presented by: Pedro Villanueva eduardov79@yahoo.com