Supervisor: Kaisa Sere
Download 298.62 Kb.
|
- Navigate this page:
- 3.1 The Routing Problem
- 3.2 Proactive and Reactive Protocols
3AD HOC ROUTING PROTOCOLSDesigning an optimized routing protocol for an ad hoc network is one of the most challenging tasks in computer science. When designing a centralized program, one only has to take into account the inner timings of the program, while in a distributed system the different copies of the program interact through more or less reliable links. These links introduce delays or losses in the communication flow, which adds to the non-determinism, and unforeseen situations can emerge. Network protocols use timers to deduce things about the state of the communication flow. For instance, a protocol can have a timer that "guesses" when a message is lost. This temporal problem is difficult to assess, as too long or short timeout periods will result in unwanted behavior. When we then add the possibility of mobility to this equation, we will have to deal with yet another uncertainty, the spatial factor. One can never be sure that a computer that was just within the radio range is there a second later. So, when an unguided transmission medium is used, the protocol designer’s job will be even more difficult. In packet switched networks for instance, a failure or disappearance of a node can put a great deal of strain on another node that has to be equipped with hardware and logic to deal with this situation. In this chapter we will categorize ad hoc routing protocols and talk in depth about a few protocols currently being considered as standards by the IETF10. 3.1 The Routing ProblemAd hoc routing protocols perform the same task as routing protocols in fixed networks. In fixed Internet for instance, a host can only communicate with directly connected hosts, on the same subnet. The same applies to ad hoc nodes - they can only communicate with directly connected neighbors, that is, if a routing protocol is not provided. An analogy can be made between Internet, which connects distant networks, and ad hoc network protocols, which connects distant hosts. The routing protocol is a piece of software that utilizes the links to neighbors, provided by the data link11 layer to disseminate information about the current topology of the network. When nodes know the topology of the network, they can instruct an intermediate node to deliver its packet to a node that is not a neighbor of the source of the packet. Routing protocols generally solve the problem of discovering the topology by letting nodes gather information about its neighbors (i.e. link metric cost and neighbor ID) and then sending this information to the neighbors and they in turn pass it on. For fixed networks there are mainly two classes of routing protocols: links state and distance vector. Link state type protocols solve the routing problem by requiring that every node gathers information about the links to their neighbors, consisting of the cost to traverse the link and the ID of the neighbor. This information is then relayed in a Links State Packet (LSP) throughout the network so that every node receives information about every node’s links to their neighbors. Based on this information, a shortest path algorithm can be run, which calculates the shortest path to every destination node and will thus be aware of the next node towards that destination, also called the nexthop. Nodes running distance vector protocols also initially send information about their neighbors initially. The difference here is that the whole routing table is sent to the neighbors (initially containing only neighbors). When a node receives the routing table of another node it first checks whether there is any, to the receiving node unknown destinations mentioned in the received routing table and copies theses to its own. Secondly, it compares the distances for destinations in its own table, to those in the received table. If a shorter route is found via another neighbor (nexthop), the routing table entry concerning the destination is updated to the shorter route. Route entries essentially contain a nexthop (direction of the vector) and a distance for every destination. After routing information has converged (updating is done infrequently), every node on the shortest routes, can forward a data packet in the right direction when requested to do so. When a node updates its routing table, it also sends the updated version (contains multiple hop routes at this time) to its neighbors. It is a well known fact that message loops can occur in distance vector protocols, but despite engineered remedies12 these cannot be eradicated completely. 3.2 Proactive and Reactive ProtocolsThe protocols in the above section are designed for fixed networks where changes in the topology rarely happen. This allows for so-called “proactive” (also called table-driven) protocols where a change in the topology is propagated globally to inform every node in the network instantly. In ad hoc networks may not be an optimal strategy because routes might be maintained unnecessarily. The nodes in an ad hoc network are mobile and if these move at a high speed, the whole network would constantly forward control packets in order to have an up-to-date picture of the topology, reducing available bandwidth13 that could be used for data packets. The advantage of having up-to-date information at all time might not be necessary since it is unlikely that every node needs to communicate with every other node. Therefore, routing protocols for ad hoc network have been developed that discover routes on an on-demand basis. These protocols are called “reactive”. Although possible, in ad hoc protocols it is more important to differentiate between reactive and proactive, rather than link state and distance vector type protocols. Finally, it can be said that ad hoc routing protocols have to minimize message complexity (amount of relayed messages) at the expense of having up-to-date routing data, extending delays. In the following sections we shall see how different protocols try to optimize this trade-off. Download 298.62 Kb. Share with your friends:
|