Olsr_Protocol

Addis Ababa Institute of Technology Department of Electrical and Computer Engineering ECEG-4503 Data Communication and Computer Networks Optimized link state routing protocol and the Floyd–Warshall algorithm Submitted by: Yared Zerihun Ermias Moges Getahun Melese Bekalu Gebeyaw Date: December 9, 2011 Table of Contents 1. Introduction 1 1.1. What is Optimized Link State Routing Protocol (OLSR)'3 1.2 Routing algorithms: Floyd-Warshall Algorithm3 1.3 Other MANET routing protocols 5 2. OLSR Protocol 6 2.1. Overview 6 2.2. Link and neighbor sensing7 2.2. Multipoint Relays 10 2.3. Packet Format 11 2.3.1 Protocol and Port Number12 2.3.2 Main Address12 2.3.3 Packet Header 13 2.3.4 Message Header 13 2.4 Packet Processing and Message Flooding15 2.4.1. Default Forwarding Algorithm17 2.5 HELLO Message Format and Generation18 3. Floyd-Warshall Algorithm20 3.1. Algorithm21 3.2. Analysis22 3.4. Implementations: C++, java23 4. Routing Algorithms in MANET’s 23 5. Conclusion24 6. Reference25 1. Introduction What is Optimized Link State Routing Protocol (OLSR)' In mobile ad hoc networks (MANET) various routing protocols are used, one of them is the optimized link state routing protocol (RFC3626). MANETs are rapidly deployable, self-configuring wireless links which doesn’t require or need existing network infrastructure. The mechanisms required in a MANET dictate an efficient network routing protocol should be used. The OLSR protocol was developed by INRIA (France). OLSR protocol is an optimization of the classical link state algorithm tailored to the requirements of a mobile wireless LAN. The key concept used in the protocol is that of multipoint relays (MPRs). MPRs are selected nodes which forward broadcast messages during the flooding process. This technique substantially reduces the message overhead as compared to a classical flooding mechanism, where every node retransmits each message when it receives the first copy of the message. In OLSR, link state information is generated only by nodes elected as MPRs. Thus, a second optimization is achieved by minimizing the number of control messages flooded in the network. As a third optimization, an MPR node may chose to report only links between itself and its MPR selectors. Hence, as contrary to the classic link state algorithm partial link state information is distributed in the network .This information is then used for route calculation. OLSR provides optimal routes. The Optimized Link-State Routing protocol can be divided in to three main parts: * Neighbor/link sensing * Optimized flooding/forwarding (Multipoint Relaying) * Link-State messaging and route calculation 1.2 Routing algorithms: Floyd-Warshall Algorithm In many applications there are separate nodes that need to communicate using channels. Obvious examples are telecommunications networks and local area networks. Another example is processes, or nodes, in distributed systems. Communication is dependent on the topology used to create the network, but in many cases, directly connecting every node with every other node in order to let them communicate is a Bad idea. As such we would like nodes to forward messages intended for other nodes. This process is called routing and basically means getting a message, or packet, from its starting-point to its destination. The model for representing a network is usually a graph, each node is a vertex and a communications channel is an edge. The weight of an edge represents the cost (usually delay) of forwarding a message through that particular communications channel. The purpose of routing algorithm is ;Given a topology, link costs, and a source-destination (SD) pair, determine a route from S to D so that the route has the minimum cost (i.e., is the shortest). Fig.1 Routing Summary of Graph representation * The network is represented as a graph. * Each node is represented as a vertex. * Each channel or connection between two nodes is represented as an edge. * The weight of each edge is defined as the cost of using the edge in a transmission path. This cost typically approximates the delay imposed on a message sent through the channel. Routing algorithms in the constructed space–time graph are developed using dynamic programming and shortest-path algorithm i.e. standard tools of graph theory such as the Floyd–Warshall algorithm. The Floyd-Warshall algorithm is a dynamic programming algorithm for computing the distance function, i.e. the lowest weight of any path from say, node u to v, which is infinite ∞ if no such path exists. The steps taken by the Floyd-Warshall algorithm are: * Begin with paths consisting of only one edge * Iteratively calculate paths with an added set of intermediate nodes, the subset S, until all nodes can be intermediate nodes. * At each iteration of the algorithm, add a pivot node to the set of intermediate nodes 1.3 Other MANET routing protocols To accommodate the dynamic topology of mobile ad hoc networks, an abundance of routing protocols have recently been proposed, such as OLSR , AODV , DSR , LAR , EASE , ODMRP , and many others. Classification of these routing protocols can be done in many ways, but most of these are done depending on routing strategy and network structure. According to the routing strategy the routing protocols can be categorized as Table-driven and source initiated, while depending on the network structure these are classified as flat routing, hierarchical routing and geographic position assisted routing Both the Table-driven and source initiated protocols come under the Flat routing. Fig .2 Classification of MANET routing protocols AODV and OLSR are both accepted as experimental RFCs by the IETF and they are probably the two most popular MANET routing protocols at the current time. Much research and work is being done using these protocols. 2. OLSR Protocol 2.1 Overview OLSR is a proactive routing protocol for mobile ad hoc networks. The protocol inherits the stability of a link state algorithm and has the advantage of having routes immediately available when needed due to its proactive nature. OLSR is an optimization over the classical link state protocol, tailored for mobile ad hoc networks. OLSR functionality can be divided into three main modules: Neighbor sensing, multipoint relaying and link-state flooding. As a derivate of the classical link-state algorithm, OLSR maintains state by keeping a variety of databases of information. These information repositories are updated upon processing received control messages and the information stored is used when generating such messages. | Fig.3 OLSR information repositories relation overview. | The above Figure displays an overview of the information repositories in OLSR and their relations to message processing, message generation and route calculation. OLSR minimizes the overhead from flooding of control traffic by using only selected nodes called MPRs, to retransmit control messages. This technique significantly reduces the number of retransmissions required to flood a message to all nodes in the network. Secondly, OLSR requires only partial link state to be flooded in order to provide shortest path routes. The minimal set of link state information required is that all nodes, selected as MPRs, MUST declare the links to their MPR selectors. Additional topological information, if present, MAY be utilized e.g., for redundancy purposes. OLSR MAY optimize the reactivity to topological changes by reducing the maximum time interval for periodic control message transmission. Furthermore, as OLSR continuously maintains routes to all destinations in the network, the protocol is beneficial for traffic patterns where a large subset of nodes are communicating with another large subset of nodes, and where the [source, destination] pairs are changing over time. The protocol is particularly suited for large and dense networks, as the optimization done using MPRs works well in this context. The larger and more dense a network, the more optimization can be achieved as compared to the classic link state algorithm. OLSR is designed to work in a completely distributed manner and does not depend on any central entity. The protocol does NOT REQUIRE reliable transmission of control messages: each node sends control messages periodically, and can therefore sustain a reasonable loss of some such messages. Such losses occur frequently in radio networks due to collisions or other transmission problems. Also, OLSR does not require sequenced delivery of messages. Each control message contains a sequence number which is incremented for each message. Thus the recipient of a control message can, if required, easily identify which information is more recent - even if messages have been re-ordered while in transmission. 2.2 Link and neighbor sensing To keep up-to-date information on what links exist between a node and its neighbors, the link set is maintained. The process of populating this set is denoted "link sensing". The mechanism for link sensing is the periodic exchange of HELLO messages. All nodes transmit HELLO messages on a given interval. These contain all heard-of neighbors grouped by status Each node should detect the links between itself and neighbor nodes. Uncertainties over radio propagation may make some links unidirectional. Consequently, all links MUST be checked in both directions in order to be considered valid. A "link" is described by a pair of interfaces: a local and a remote interface. For the purpose of link sensing, each neighbor node (more specifically, the link to each neighbor) has an associated status of either "symmetric" or "asymmetric". "Symmetric" indicates, that the link to that neighbor node has been verified to be bi-directional, i.e., it is possible to transmit data in both directions."Asymmetric" indicates that HELLO messages from the node have been heard (i.e., communication from the neighbor node is possible), however it is not confirmed that this node is also able to receive messages (i.e., communication to the neighbor node is not confirmed).The information, acquired through and used by the link sensing, is accumulated in the link set. In HELLO messages a node emits all information about the links to neighbors from the interface on which the HELLO is transmitted. When declaring links, the IP addresses of the actual interfaces making up the link is used. When declaring the neighbor state of neighbors not reachable on the interface on which the HELLO is transmitted, the main address of the neighbor node is used. | Fig.4 Nodes A and B runs OLSR on multiple interfaces. B uses the address of b1 as its main address. Nodes D and C runs on single interfaces (d1 and c1). | In a scenario like the one depicted in figure above, A would send the following information in its HELLO message on interface a1: * Its current link and neighbor state for d1. * Its current link and neighbor state for c1. * Its current neighbor state for the main address of node B which is b1. When building a HELLO to be transmitted on a2, node A will include the following information: * Its current neighbor state for d1. * Its current neighbor state for c1. * Its current link and neighbor state for b2. Upon receiving a HELLO from a neighbor, a node checks to see if the HELLO message contains the IP address of the interface the message was received. The link set is then updated as follows: * If no link entry exists for the tuple (originating IP, IP of received interface) then such an entry is created. The originating IP is fetched from the IP header of the received packet. Whenever a link entry is created a corresponding neighbor entry is created as well if no such entry exists. * An asymmetric timer is then updated according to the validity time received. This timer decides for how long the link entry is to be considered asymmetric if the symmetric timer times out. * If the address of the receiving interface is located in the received HELLO message, the symmetric timer is updated and the status of the link is updated if necessary. The status of the neighbor entry according to this link entry is also updated if necessary. * Finally the actual holding time for this entry is set to be the maximum of the asymmetric timer and the symmetric timer. Neighbor Detection Neighbor detection populates the neighborhood information base and concerns itself with nodes and node main addresses. The mechanism for neighbor detection is the periodic exchange of HELLO messages. A node maintains a set of neighbor tuples, based on the link tuples. This information is updated according to changes in the Link Set. The Link Set keeps the information about the links, while the Neighbor Set keeps the information about the neighbors. There is a clear association between those two sets, since a node is a neighbor of another node if and only if there is at least one link between the two nodes. 2.2 Multipoint Relays The concept of multipoint relaying is to reduce the number of duplicate retransmissions while forwarding a broadcast packet. This technique restricts the set of nodes retransmitting a packet from all nodes, to a subset of all nodes. | Fig.5 Flooding a packet in a wireless multihop network. The arrows show the way information is passed, not all transmissions. | | Fig.6 Flooding a packet in a wireless multihop network from the center node using MPRs (black). The arrows show the way information is passed, not all transmissions. | This is achieved by selecting neighbors as Multipoint relays (MPRs). Each node in the network selects a set of nodes in its symmetric 1-hop neighborhood which may retransmit its messages. This set of selected neighbor nodes is called the "Multipoint Relay" (MPR) set of that node. The neighbors of node N which are *NOT* in its MPR set, receive and process broadcast messages but do not retransmit broadcast messages received from node N. Each node selects its MPR set from among its 1-hop symmetric neighbors. This set is selected such that it covers (in terms of radio range) all symmetric strict 2-hop nodes. The MPR set of N, denoted as MPR (N), is then an arbitrary subset of the symmetric 1-hop neighborhood of N which satisfies the following condition: every node in the symmetric strict 2-hop neighborhood of N must have a symmetric link towards MPR (N). The smaller a MPR set the less control traffic overhead results from the routing protocol. Each node maintains information about the set of neighbors that have selected it as MPR. This set is called the "Multipoint Relay Selector set" (MPR selector set) of a node. A node obtains this information from periodic HELLO messages received from the neighbors. A broadcast message, intended to be diffused in the whole network, coming from any of the MPR selectors of node N is assumed to be retransmitted by node N, if N has not received it yet. This set can change over time (i.e., when a node selects another MPR-set) and is indicated by the selector nodes in their HELLO messages. 2.3 Packet Format OLSR communicates using a unified packet format for all data related to the protocol. The purpose of this is to facilitate extensibility of the protocol without breaking backwards compatibility. This also provides an easy way of piggybacking different "types" of information into a single transmission, and thus for a given implementation to optimize towards utilizing the maximal frame-size, provided by the network. These packets are embedded in UDP datagrams for transmission over the network. Each packet encapsulates one or more messages. The messages share a common header format, which enables nodes to correctly accept and (if applicable) retransmit messages of an unknown type. Messages can be flooded onto the entire network, or flooding can be limited to nodes within a diameter (in terms of number of hops) from the originator of the message. Thus transmitting a message to the neighborhood of a node is just a special case of flooding. When flooding any control message, duplicate retransmissions will be eliminated locally (i.e., each node maintains a duplicate set to prevent transmitting the same OLSR control message twice) and minimized in the entire network through the usage of MPRs as described in later sections. Furthermore, a node can examine the header of a message to obtain information on the distance (in terms of number of hops) to the originator of the message. This feature may be useful in situations where, e.g., the time information from a received control messages stored in a node depends on the distance to the originator. 2.3.1 Protocol and Port Number Packets in OLSR are communicated using UDP. Port 698 has been assigned by IANA for exclusive usage by the OLSR protocol. 2.3.2. Main Address For a node with one interface, the main address of a node, as defined in "OLSR Terminology", MUST be set to the address of that interface. 2.3.3. Packet Format The basic layout of any packet in OLSR is as follows (omitting IP and UDP headers): Fig .7 Packet format in OLSR 2.3.4 Packet Header Packet Length The length (in bytes) of the packet Packet Sequence Number The Packet Sequence Number (PSN) MUST be incremented by one each time a new OLSR packet is transmitted. A separate Packet Sequence Number is maintained for each interfaces such those packets transmitted over an interface are sequentially enumerated. The IP address of the interface over which a packet was transmitted is obtainable from the IP header of the packet. If the packet contains no messages (i.e., the Packet Length is less than or equal to the size of the packet header), the packet MUST silently be discarded. For IPv4 addresses, this implies that packets, where the Packet Length < 16 MUST silently be discarded. 2.3.5 Message Header Message Type This field indicates which type of message is to be found in the "MESSAGE" part. Message types in the range of 0-127 are reserved for messages in this document and in possible extensions. Vtime This field indicates for how long time after reception a node MUST consider the information contained in the message as valid, unless a more recent update to the information is received. The validity time is represented by its mantissa (four highest bits of Vtime field) and by its exponent (four lowest bits of Vtime field). In other words: Validity time = C*(1+a/16)* 2^b [in seconds] where a is the integer represented by the four highest bits of Vtime field and b the integer represented by the four lowest bits of Vtime field. The proposed value of the scaling factor C is specified in section 18. Message Size This gives the size of this message, counted in bytes and measured from the beginning of the "Message Type" field and until the beginning of the next "Message Type" field (or – if there are no following messages - until the end of the packet). Originator Address This field contains the main address of the node, which has originally generated this message. This field SHOULD NOT be confused with the source address from the IP header, which is changed each time to the address of the intermediate interface which is re-transmitting this message. The Originator Address field MUST *NEVER* be changed in retransmissions. Time To Live This field contains the maximum number of hops a message will be transmitted. Before a message is retransmitted, the Time To Live MUST be decremented by 1. When a node receives a message with a Time To Live equal to 0 or 1, the message MUST NOT be retransmitted under any circumstances. Normally, a node would not receive a message with a TTL of zero. Thus, by setting this field, the originator of a message can limit the flooding radius. Hop Count This field contains the number of hops a message has attained. Before a message is retransmitted, the Hop Count MUST be incremented by 1. Initially, this is set to '0' by the originator of the message. Message Sequence Number While generating a message, the "originator" node will assign a unique identification number to each message. This number is inserted into the Sequence Number field of the message. The sequence number is increased by 1 (one) for each message originating from the node. Message sequence numbers are used to ensure that a given message is not retransmitted more than once by any node. 2.4 Packet Processing and Message Flooding Upon receiving a basic packet, a node examines each of the "message headers". Based on the value of the "Message Type" field, the node can determine the fate of the message. A node may receive the same message several times. Thus, to avoid re-processing of some messages which were already received and processed, each node maintains a Duplicate Set. In this set, the node records information about the most recently received messages where duplicate processing of a message is to be avoided. For such a message, a node records a "Duplicate Tuple" (D_addr, D_seq_num, D_retransmitted, D_iface_list,D_time), where D_addr is the originator address of the message, D_seq_num is the message sequence number of the message, D_retransmitted is a boolean indicating whether the message has been already retransmitted, D_iface_list is a list of the addresses of the interfaces on which the message has been received and D_time specifies the time at which a tuple expires and *MUST* be removed. In a node, the set of Duplicate Tuples are denoted the "Duplicate set". In this section, the term"Originator Address" will be used for the main address of the node which sent the message. The term "Sender Interface Address" will be used for the sender address (given in the IP header of the packet containing the message) of the interface which sent the message. The term "Receiving Interface Address" will be used for the address of the interface of the node which received the message. Thus, upon receiving a basic packet, a node MUST perform the following tasks for each encapsulated message: 1. If the packet contains no messages (i.e., the Packet Length is less than or equal to the size of the packet header), the packet MUST silently be discarded. For IPv4 addresses, this implies that packets, where the Packet Length < 16 MUST silently be discarded. 2. If the time to live of the message is less than or equal to '0' (zero), or if the message was sent by the receiving node (i.e., the Originator Address of the message is the main address of the receiving node): the message MUST silently be dropped. 3. Processing condition: 3.1 if there exists a tuple in the duplicate set, where: D_addr == Originator Address, AND D_seq_num == Message Sequence Number then the message has already been completely processed and MUST not be processed again. 3.2 Otherwise, if the node implements the Message Type of the message, the Message MUST be processed according to the specifications for the message type. 4. Forwarding condition: 4.1 if there exists a tuple in the duplicate set, where: D_addr == Originator Address, AND D_seq_num == Message Sequence Number, AND the receiving interface (address) is in D_iface_list then the message has already been considered for forwarding and SHOULD NOT be retransmitted again. 4.2 Otherwise: 4.2.1 If the node implements the Message Type of the message, the message MUST be considered for forwarding according to the specifications for the message type. 4.2.2. Otherwise, if the node does not implement the Message Type of the message, the message SHOULD be processed according to the default forwarding algorithm described below. 2.4.1 Default Forwarding Algorithm The default forwarding algorithm is the following: 1. If the sender interface address of the message is not detected to be in the symmetric 1-hop neighborhood of the node, the forwarding algorithm MUST silently stop here (and the message MUST NOT be forwarded). 2. If there exists a tuple in the duplicate set where: D_addr == Originator Address D_seq_num == Message Sequence Number Then the message will be further considered for forwarding if and only if: D_retransmitted is false, AND the (address of the) interface which received the message is not included among the addresses in D_iface_list 3. Otherwise, if such an entry doesn't exist, the message is further considered for forwarding. If after those steps, the message is not considered for forwarding, then the processing of this section stops (i.e., steps 4 to 8 are ignored), otherwise, if it is still considered for forwarding then the following algorithm is used: 4. If the sender interfaces address is an interface address of a MPR selector of this node and if the time to live of the message is greater than '1', the message MUST be retransmitted (as described later in steps 6 to 8). 5. If an entry in the duplicate set exists, with same Originator Address, and same Message Sequence Number, the entry is updated as follows: D_time = current time + DUP_HOLD_TIME. The receiving interface (address) is added to D_iface_list. D_retransmitted is set to true if and only if the message will be retransmitted according to step 4. Otherwise an entry in the duplicate set is recorded with: D_addr = Originator Address D_seq_num = Message Sequence Number D_time = current time + DUP_HOLD_TIME. D_iface_list contains the receiving interface address. D_retransmitted is set to true if and only if the message will be retransmitted according to step 4. If, and only if, according to step 4, the message must be retransmitted then: 6. The TTL of the message is reduced by one. 7. The hop-count of the message is increased by one 8. The message is broadcast on all interfaces (Notice: The remaining fields of the message header SHOULD be left unmodified.) 2.5 HELLO Message Format To accommodate for link sensing, neighborhood detection and MPR selection signaling, as well as to accommodate for future extensions, an approach similar to the overall packet format I taken. Thus the proposed format of a HELLO message is as follows: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Htime | Willingness | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Code | Reserved | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Code | Reserved | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : : (etc.) Fig .8 HELLO message format This is sent as the data-portion of the general packet format described in section 3.4, with the "Message Type" set to HELLO_MESSAGE, the TTL field set to 1 (one) and Vtime set accordingly to the value of NEIGHB_HOLD_TIME. HELLO Message Generation This involves transmitting the Link Set, the Neighbor Set and the MPR Set. In principle, a HELLO message serves three independent tasks: * link sensing * neighbor detection * MPR selection signaling Three tasks are all are based on periodic information exchange within a nodes neighborhood, and serve the common purpose of "local topology discovery". A HELLO message is therefore generated based on the information stored in the Local Link Set, the Neighbor Set and the MPR Set from the local link information base. A node must perform link sensing on each interface, in order to detect links between the interface and neighbor interfaces. Furthermore, a node must advertise its entire symmetric 1-hop neighborhood on each interface in order to perform neighbor detection. Hence, for a given interface, a HELLO message will contain a list of links on that interface (with associated link types), as well as a list of the entire neighborhood (with an associated neighbor types). The Vtime field is set such that it corresponds to the value of the node's NEIGHB_HOLD_TIME parameter. The Htime field is set such that it corresponds to the value of the node's HELLO_INTERVAL parameter. The Willingness field is set such that it corresponds to the node's willingness to forward traffic on behalf of other nodes. A node MUST advertise the same willingness on all interfaces. 3. Floyd-Warshall Algorithm Routing protocols model the dynamics of the networks as space–time graph. Routing algorithms in the constructed space–time graph are developed using dynamic programming and shortest-path algorithm. The routing algorithm finds the best route for messages by looking ahead. The time-expanded graphs approach translates a problem of network flow over time to a classical static network flow, and standard tools of graph theory such as the Floyd–Warshall algorithm can be applied to compute the shortest path for a source destination pair. In this section we briefly discuss the Floyd-Warshall Algorithm. 3.1 Algorithm The Floyd-Warshall algorithm is a simple and widely used algorithm to compute shortest paths between all pairs of vertices in an edge weighted directed graph. It is an efficient algorithm to find all-pairs shortest paths on a graph. That is, it is guaranteed to find the shortest path between every pair of vertices in a graph. The graph may have negative weight edges, but no negative weight cycles (for then the shortest path is undefined). A negative cycle is a cycle whose edges sum to a negative value. Between any pair of vertices which form part of a negative cycle, the shortest path is not well-defined because the path can be arbitrarily negative. For numerically meaningful output, the Floyd–Warshall algorithm assumes that there are no negative cycles. Nevertheless, if there are negative cycles, the Floyd–Warshall algorithm can be used to detect them. Fig.9 The Floyd-Warshall algorithm for computing the lengths of shortest paths between all pairs of vertices in a directed graph with possibly negative edge weights. 3.2 Analysis The Floyd-Warshall algorithm outputs the correct result as long as no negative cycles exist in the input graph. In case that a negative cycle exists, computing a shortest (simple) path is an NP-hard problem and the Floyd-Warshall algorithm will not output the correct result. Rather, it will detect the presence of a negative cycle by checking that there is a negative entry in the diagonal of the matrix M (lines 8 and 9 in Fig 9). In many widely used implementations this is done as shown in Fig 9. The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with only Θ(|V|3) comparisons in a graph. This is remarkable considering that there may be up to Ω(|V|2) edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal. Consider a graph G with vertices V, each numbered 1 through N. Further consider a function shortestPath(i, j, k) that returns the shortest possible path from i to j using vertices only from the set {1,2,...,k} as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each i to each j using only vertices 1 to k + 1. There are two candidates for each of these paths: either the true shortest path only uses vertices in the set {1, ..., k}; or there exists some path that goes from i to k + 1, then from k + 1 to j that is better. We know that the best path from i to j that only uses vertices 1 through k is defined by shortest Path(i, j, k), and it is clear that if there were a better path from i to k + 1 to j, then the length of this path would be the concatenation of the shortest path from i to k + 1 (using vertices in {1, ..., k}) and the shortest path from k + 1 to j (also using vertices in {1, ..., k}). If w(i,j) is the weight of the edge between vertices i and j, we can define shortestPath(i, j, k) in terms of the following recursive formula: the base case is shortestPath(i,j,0) = w(i,j) and the recursive case is This formula is the heart of the Floyd–Warshall algorithm. The algorithm works by first computing shortestPath(i, j, k) for all (i, j) pairs for k = 1, then k = 2, etc. This process continues until k = n, and we have found the shortest path for all (i, j) pairs using any intermediate vertices. 3.4 Implementations Implementations for Floyd–Warshall algorithm are available in many programming languages. * For C++, in the boost::graph library * For Java, in the Apache commons graph library, or at Algowiki 4. Routing Algorithms in MANET’s The main goal of an ad hoc network routing algorithm is to correctly and efficiently establish a route between a pair of nodes in the network so a message can be delivered according to the expected QoS parameters. The establishment of a route should be done with minimum overhead and bandwidth consumption. In the current wired networks, there are different link state and distance vector routing protocols, which were not designed to cope with constant topology changes of mobile ad hoc environments. An ad hoc network has a dynamic nature that leads to constant changes in its network topology. As a consequence, the routing problem becomes more complex and challengeable. In general, routing algorithms for ad hoc networks may be divided into two broad classes: proactive protocols and reactive on-demand protocols. A common point of the existing algorithms is that their computations involve almost exclusively distance (or spatial) types of information. This approach can be traced all the way back to the classic Dijkstra, Bellman-Ford, and Floyd-Warshall algorithms (presented in this paper), which are driven by quantities measuring distance between nodes. However these spatial routing algorithms were designed with an assumption of static or near-static topologies, Where nodes do not move and links change at a slow rate (if at all). In a situation where all nodes are constantly moving, making therefore topology change the norm rather than the exception. In such a scenario, a routing algorithm that was driven exclusively by temporal metrics could significantly outperform spatial approaches. One such approach is using an algorithm named FRESH (FResher Encounter SearcH). 4. Conclusion Core OLSR functionality can be divided into three main modules: Neighbor and link sensing, multipoint relaying and Link-State messaging and route calculation. The most important feature of OLSR is the use of multipoint relays (MPR).In a pure link state protocol, all the links with neighbor nodes are declared and flooded in the entire network. But in the OLSR protocol this flooding of control traffic is minimized by using selected nodes, called multipoint relays, to diffuse its messages in the network. Only the multipoint relays of a node retransmit its broadcast messages. This technique significantly reduces the number of retransmissions in a flooding or broadcast procedure. Mobile ad hoc networks employ various types of routing algorithms. A common point of the algorithms is that their computations involve almost exclusively distance (or spatial) types of information. They are driven by quantities measuring distance between nodes. One common type of such algorithms is the Floyd-Warshall algorithms. Reference 1. Algorithms and protocols for wireless and mobile ad hoc networks by Azzedine Boukerche, 2009 2. Request for Comments: 3626 Optimized Link State Routing Protocol (OLSR) by T. Clausen, Ed. And P. Jacquet, Ed. Project Hipercom, INRI October 2003 3. OLSR homepage http://www.olsr.org 4. Routing Protocols in Mobile Ad-hoc Networks by Krishna Gorantala , June 15, 2006 5. The Floyd-Warshall Algorithm on Graphs with Negative Cycles by Stefan Hougardy 2010 6. Mobile Ad-Hoc Networks by Andreas Tønnesen 7. Routing algorithms by Jan Lonnberg, October 2, 2002 8. http:// en.wikipedia.org/ Floyd–Warshall algorithm