Some Popular Routing Protocols In Ad Hoc Networks

research on networks and communications in general and in the study of ad hoc networks in particular.

1.5. Summary of Chapter 1

An ad hoc network is a collection of mobile nodes that are capable of self-connection and self-organization to form a network without the need for underlying network infrastructure devices to act as intermediaries to receive/transmit signals and forward data. Each network node acts as both an end device and a router to find paths and forward data to other network nodes.

With the advantages of high flexibility and not requiring existing network infrastructure, ad hoc networks have the potential to be applied in many areas serving human life such as in military communication networks, natural disaster warning, transportation, commerce, entertainment, education, etc.

Maybe you are interested!

• Qos Assurance Methods for Multimedia Communications zt2i3t4l5ee zt2a3gs zt2a3ge zc2o3n4t5e6n7ts low. The EF PHB requires a sufficiently large number of output ports to provide low delay, low loss, and low jitter. EF PHBs can be implemented if the output port's bandwidth is sufficiently large, combined with small buffer sizes and other network resources dedicated to EF packets, to allow the router's service rate for EF packets on an output port to exceed the arrival rate λ of packets at that port. This means that packets with PHB EF are considered with a pre-allocated amount of output bandwidth and a priority that ensures minimum loss, minimum delay and minimum jitter before being put into operation. PHB EF is suitable for channel simulation, leased line simulation, and real-time services such as voice, video without compromising on high loss, delay and jitter values. Figure 2.10 Example of EF installation Figure 2.10 shows an example of an EF PHB implementation. This is a simple priority queue scheduling technique. At the edges of the DS domain, EF packet traffic is prioritized according to the values ​​agreed upon by the SLA. The EF queue in the figure needs to output packets at a rate higher than the packet arrival rate λ. To provide an EF PHB over an end-to-end DS domain, bandwidth at the output ports of the core routers needs to be allocated in advance to ensure the requirement μ > λ. This can be done by a pre-configured provisioning process. In the figure, EF packets are placed in the priority queue (the upper queue). With such a length, the queue can operate with μ > λ. Since EF was primarily used for real-time services such as voice and video, and since real-time services use UDP instead of TCP, RED is generally not suitable for EF queues because applications using UDP will not respond to random packet drop and RED will strip unnecessary packets. 2.2.4.2 Assured Forwarding (AF) PHB PHB AF is defined by RFC 2597. The purpose of PHB AF is to deliver packets reliably and therefore delay and jitter are considered less important than packet loss. PHB AF is suitable for non-real-time services such as applications using TCP. PHB AF first defines four classes: AF1, AF2, AF3, AF4. For each of these AF classes, packets are then classified into three subclasses with three distinct priority levels. Table 2.8 shows the four AF classes and 12 AF subclasses and the DSCP values ​​for the 12 AF subclasses defined by RFC 2597. RFC 2597 also allows for more than three separate priority levels to be added for internal use. However, these separate priority levels will only have internal significance. PHB Class PHB Subclass Package type DSCP AF4 AF41 Short 100010 AF42 Medium 100100 AF43 High 100110 AF3 AF31 Short 011010 AF32 Medium 011100 AF33 High 011110 AF2 AF21 Short 010010 AF22 Medium 010100 AF23 High 010110 AF1 AF11 Short 001010 AF12 Medium 001100 AF13 High 001110 Table 2.8 AF DSCPs The AF PHB ensures that packets are forwarded with a high probability of delivery to the destination within the bounds of the rate agreed upon in an SLA. If AF traffic at an ingress port exceeds the pre-priority rate, which is considered non-compliant or “out of profile”, the excess packets will not be delivered to the destination with the same probability as the packets belonging to the defined traffic or “in profile” packets. When there is network congestion, the out of profile packets are dropped before the in profile packets are dropped. When service levels are defined using AF classes, different quantity and quality between AF classes can be realized by allocating different amounts of bandwidth and buffer space to the four AF classes. Unlike EF, most AF traffic is non-real-time traffic using TCP, and the RED queue management strategy is an AQM (Adaptive Queue Management) strategy suitable for use in AF PHBs. The four AF PHB layers can be implemented as four separate queues. The output port bandwidth is divided into four AF queues. For each AF queue, packets are marked with three “colors” corresponding to three separate priority levels. In addition to the 32 DSCP 1 groups defined in Table 2.8, 21 DSCPs have been standardized as follows: one for PHB EF, 12 for PHB AF, and 8 for CSCP. There are 11 DSCP 1 groups still available for other standards. 2.2.5.Example of Differentiated Services We will look at an example of the Differentiated Service model and mechanism of operation. The architecture of Differentiated Service consists of two basic sets of functions: Edge functions: include packet classification and traffic conditioning. At the inbound edge of the network, incoming packets are marked. In particular, the DS field in the packet header is set to a certain value. For example, in Figure 2.12, packets sent from H1 to H3 are marked at R1, while packets from H2 to H4 are marked at R2. The labels on the received packets identify the service class to which they belong. Different traffic classes receive different services in the core network. The RFC definition uses the term behavior aggregate rather than the term traffic class. After being marked, a packet can be forwarded immediately into the network, delayed for a period of time before being forwarded, or dropped. We will see that there are many factors that affect how a packet is marked, and whether it is forwarded immediately, delayed, or dropped. Figure 2.12 DiffServ Example Core functionality: When a DS-marked packet arrives at a Diffservcapable router, the packet is forwarded to the next router based on Per-hop behavior is associated with packet classes. Per-hop behavior affects router buffers and the bandwidth shared between competing classes. An important principle of the Differentiated Service architecture is that a router's per-hop behavior is based only on the packet's marking or the class to which it belongs. Therefore, if packets sent from H1 to H3 as shown in the figure receive the same marking as packets from H2 to H4, then the network routers treat the packets exactly the same, regardless of whether the packet originated from H1 or H2. For example, R3 does not distinguish between packets from h1 and H2 when forwarding packets to R4. Therefore, the Differentiated Service architecture avoids the need to maintain router state about separate source-destination pairs, which is important for network scalability. Chapter Conclusion Chapter 2 has presented and clarified two main models of deploying and installing quality of service in IP networks. While the traditional best-effort model has many disadvantages, later models such as IntServ and DiffServ have partly solved the problems that best-effort could not solve. IntServ follows the direction of ensuring quality of service for each separate flow, it is built similar to the circuit switching model with the use of the RSVP resource reservation protocol. IntSer is suitable for services that require fixed bandwidth that is not shared such as VoIP services, multicast TV services. However, IntSer has disadvantages such as using a lot of network resources, low scalability and lack of flexibility. DiffServ was born with the idea of ​​solving the disadvantages of the IntServ model. DiffServ follows the direction of ensuring quality based on the principle of hop-by-hop behavior based on the priority of marked packets. The policy for different types of traffic is decided by the administrator and can be changed according to reality, so it is very flexible. DiffServ makes better use of network resources, avoiding idle bandwidth and processing capacity on routers. In addition, the DifServ model can be deployed on many independent domains, so the ability to expand the network becomes easy. Chapter 3: METHODS TO ENSURE QoS FOR MULTIMEDIA COMMUNICATIONS In packet-switched networks, different packet flows often have to share the transmission medium all the way to the destination station. To ensure the fair and efficient allocation of bandwidth to flows, appropriate serving mechanisms are required at network nodes, especially at gateways or routers, where many different data flows often pass through. The scheduler is responsible for serving packets of the selected flow and deciding which packet will be served next. Here, a flow is understood as a set of packets belonging to the same priority class, or originating from the same source, or having the same source and destination addresses, etc. In normal state when there is no congestion, packets will be sent as soon as they are delivered. In case of congestion, if QoS assurance methods are not applied, prolonged congestion can cause packet drops, affecting service quality. In some cases, congestion is prolonged and widespread in the network, which can easily lead to the network being "frozen", or many packets being dropped, seriously affecting service quality. Therefore, in this chapter, in sections 3.2 and 3.3, we introduce some typical network traffic load monitoring techniques to predict and prevent congestion before it occurs through the measure of dropping (removing) packets early when there are signs of impending congestion. 3.1. DropTail method DropTail is a simple, traditional queue management method based on FIFO mechanism. All incoming packets are placed in the queue, when the queue is full, the later packets are dropped. Due to its simplicity and ease of implementation, DropTail has been used for many years on Internet router systems. However, this algorithm has the following disadvantages: − Cannot avoid the phenomenon of “Lock out”: Occurs when 1 or several traffic streams monopolize the queue, making packets of other connections unable to pass through the router. This phenomenon greatly affects reliable transmission protocols such as TCP. According to the anti-congestion algorithm, when locked out, the TCP connection stream will reduce the window size and reduce the packet transmission speed exponentially. − Can cause Global Synchronization: This is the result of a severe “Lock out” phenomenon. Some neighboring routers have their queues monopolized by a number of connections, causing a series of other TCP connections to be unable to pass through and simultaneously reducing the transmission speed. After those monopolized connections are temporarily suspended, Once the queue is cleared, it takes a considerable amount of time for TCP connections to return to their original speed. − Full Queue phenomenon: Data transmitted on the Internet often has an explosion, packets arriving at the router are often in clusters rather than in turn. Therefore, the operating mechanism of DropTail makes the queue easily full for a long period of time, leading to the average delay time of large packets. To avoid this phenomenon, with DropTail, the only way is to increase the router's buffer, this method is very expensive and ineffective. − No QoS guarantee: With the DropTail mechanism, there is no way to prioritize important packets to be transmitted through the router earlier when all are in the queue. Meanwhile, with multimedia communication, ensuring connection and stable speed is extremely important and the DropTail algorithm cannot satisfy. The problem of choosing the buffer size of the routers in the network is to “absorb” short bursts of traffic without causing too much queuing delay. This is necessary in bursty data transmission. The queue size determines the size of the packet bursts (traffic spikes) that we want to be able to transmit without being dropped at the routers. In IP-based application networks, packet dropping is an important mechanism for indirectly reporting congestion to end stations. A solution that prevents router queues from filling up while reducing the packet drop rate is called dynamic queue management. 3.2. Random elimination method – RED 3.2.1 Overview RED (Random Early Detection of congestion; Random Early Drop) is one of the first AQM algorithms proposed in 1993 by Sally Floyd and Van Jacobson, two scientists at the Lawrence Berkeley Laboratory of the University of California, USA. Due to its outstanding advantages compared to previous queue management algorithms, RED has been widely installed and deployed on the Internet. The most fundamental point of their work is that the most effective place to detect congestion and react to it is at the gateway or router. Source entities (senders) can also do this by estimating end-to-end delay, throughput variability, or the rate of packet retransmissions due to drop. However, the sender and receiver view of a particular connection cannot tell which gateways on the network are congested, and cannot distinguish between propagation delay and queuing delay. Only the gateway has a true view of the state of the queue, the link share of the connections passing through it at any given time, and the quality of service requirements of the traffic flows. The RED gateway monitors the average queue length, which detects early signs of impending congestion (average queue length exceeding a predetermined threshold) and reacts appropriately in one of two ways: − Drop incoming packets with a certain probability, to indirectly inform the source of congestion, the source needs to reduce the transmission rate to keep the queue from filling up, maintaining the ability to absorb incoming traffic spikes. − Mark “congestion” with a certain probability in the ECN field in the header of TCP packets to notify the source (the receiving entity will copy this bit into the acknowledgement packet). Figure 3. 1 RED algorithm The main goal of RED is to avoid congestion by keeping the average queue size within a sufficiently small and stable region, which also means keeping the queuing delay sufficiently small and stable. Achieving this goal also helps: avoid global synchronization, not resist bursty traffic flows (i.e. flows with low average throughput but high volatility), and maintain an upper bound on the average queue size even in the absence of cooperation from transport layer protocols. To achieve the above goals, RED gateways must do the following: − The first is to detect congestion early and react appropriately to keep the average queue size small enough to keep the network operating in the low latency, high throughput region, while still allowing the queue size to fluctuate within a certain range to absorb short-term fluctuations. As discussed above, the gateway is the most appropriate place to detect congestion and is also the most appropriate place to decide which specific connection to report congestion to. − The second thing is to notify the source of congestion. This is done by marking and notifying the source to reduce traffic. Normally the RED gateway will randomly drop packets. However, if congestion If congestion is detected before the queue is full, it should be combined with packet marking to signal congestion. The RED gateway has two options: drop or mark; where marking is done by marking the ECN field of the packet with a certain probability, to signal the source to reduce the traffic entering the network. − An important goal that RED gateways need to achieve is to avoid global synchronization and not to resist traffic flows that have a sudden characteristic. Global synchronization occurs when all connections simultaneously reduce their transmission window size, leading to a severe drop in throughput at the same time. On the other hand, Drop Tail or Random Drop strategies are very sensitive to sudden flows; that is, the gateway queue will often overflow when packets from these flows arrive. To avoid these two phenomena, gateways can use special algorithms to detect congestion and decide which connections will be notified of congestion at the gateway. The RED gateway randomly selects incoming packets to mark; with this method, the probability of marking a packet from a particular connection is proportional to the connection's shared bandwidth at the gateway. − Another goal is to control the average queue size even without cooperation from the source entities. This can be done by dropping packets when the average size exceeds an upper threshold (instead of marking it). This approach is necessary in cases where most connections have transmission times that are less than the round-trip time, or where the source entities are not able to reduce traffic in response to marking or dropping packets (such as UDP flows). 3.2.2 Algorithm This section describes the algorithm for RED gateways. RED gateways calculate the average queue size using a low-pass filter. This average queue size is compared with two thresholds: minth and maxth. When the average queue size is less than the lower threshold, no incoming packets are marked or dropped; when the average queue size is greater than the upper threshold, all incoming packets are dropped. When the average queue size is between minth and maxth, each incoming packet is marked or dropped with a probability pa, where pa is a function of the average queue size avg; the probability of marking or dropping a packet for a particular connection is proportional to the bandwidth share of that connection at the gateway. The general algorithm for a RED gateway is described as follows: [5] For each packet arrival Caculate the average queue size avg If minth ≤ avg < maxth div.maincontent .s1 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 15pt; } div.maincontent .s2 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 15pt; } div.maincontent .p { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; margin:0pt; } div.maincontent p { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; margin:0pt; } div.maincontent .s3 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s4 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s5 { color: black; font-family:"Times New Roman", serif; font-style: italic; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s6 { color: black; font-family:"Times New Roman", serif; font-style: italic; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s7 { color: black; font-family:Wingdings; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s8 { color: black; font-family:Arial, sans-serif; font-style: italic; font-weight: bold; text-decoration: none; font-size: 15pt; } div.maincontent .s9 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s10 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; vertical-align: 6pt; } div.maincontent .s11 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 13pt; } div.maincontent .s12 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10pt; } div.maincontent .s13 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-d
• The impact of financial structure on the performance of commercial banks - 1
• Factors Affecting Business Performance of Meiko Trading and Construction Company Limited
• Business Performance of the Company in the Period 2009–2011 Table 2.1. Business Results of Viet Holiday Travel Company
• Management Status of Tcm Results Evaluation Through NCBH Form Table 2.9: Current Status of Evaluation of Professional Team Performance Results Through Form

Because the nodes of the network are able to move freely and randomly, the topology of the ad hoc network changes frequently, and the links and data paths in the network are frequently broken and newly formed. Therefore, the routing protocols in the ad hoc network need to be designed to suit this requirement. There are many routing strategies designed for ad hoc networks. Each strategy has different advantages and disadvantages and is used appropriately in different conditions and circumstances.

IEEE 802.11 standard is widely used standard at Physical layer and Data Link layer of wireless networks. However, CSMS/CD medium access mechanism used in IEEE 802.11 Ethernet technology is not suitable for ad hoc wireless networks because of the physical nature of wireless networks and the hidden station problem. CSMA/CA medium access mechanism in DCF of

IEEE 802.11 standard has been designed to solve technical problems at MAC layer for ad hoc networks. Conversation-based virtual carrier sensing technique using RTS, CTS, ACK packets has been presented in detail in this chapter.

Network performance is the main criteria used in the design and operation of network systems. The purpose of evaluating network performance is to compare designs to find the best design. There are three common methods commonly used to evaluate network performance: measurement evaluation, analytical modeling evaluation, and simulation evaluation. These network performance evaluation methods can be used to evaluate the performance of routing protocols in ad hoc networks.

Among the above three methods, simulation evaluation method has been used in this thesis to evaluate the impact of travel speed and data load on routing performance in ad hoc network based on using NS2 simulator.

CHAPTER 2. SOME POPULAR ROUTING PROTOCOLS IN AD HOC NETWORKS

2.1. Requirements for routing protocols and algorithms in ad hoc networks

Because ad hoc networks have many differences compared to traditional networks, routing protocols and algorithms in ad hoc networks must be designed to ensure the following technical requirements:

 The algorithm must be designed to accommodate the dynamics of the network topology and asymmetric links.

 Ability to operate in a distributed manner: a centralized approach to Ad hoc networks will fail because it will take a lot of time to gather the current state information of the network to calculate and then redistribute it to the network nodes. During that time, the network configuration may have changed a lot.

 Saving energy and network bandwidth: Since network nodes have limited energy resources, it is necessary to consider the issue of energy saving. Routing protocols can provide energy conservation requirements at network nodes when possible. Network bandwidth also needs to be considered to avoid unnecessary bandwidth waste.

 Avoid loop routing: This occurs when a small portion of packets travel around the network for a period of time. A possible solution is to use a hop counter in each packet. Each time a packet travels to a new network node, the hop counter will increase by one, and when it reaches a certain value, the packet will be discarded.

 Security: Ad hoc network routing protocols can be easily attacked in some forms such as giving incorrect routing updates or preventing packet forwarding, indirectly causing denial of service leading to packets never reaching their destination. They can also change routing information in the network, although that information is not dangerous but also wastes bandwidth and energy, which are "rare" resources in Ad hoc networks. Therefore, appropriate security methods are needed to prevent modification of protocol operations.

2.2. DSDV routing protocol

2.2.1. Overview of DSDV routing protocol

The DSDV routing protocol [6] is a typical distance vector “path-ahead” routing protocol. It not only solves the routing problem for ad hoc networks but also describes how to implement routing functions at Layer 2. Packets are transmitted between stations in a network using routing tables stored at each station. Each routing table at each station is a list of possible destinations from that station and the number of hops that must be passed to reach each destination. Each row in the routing table is assigned a sequence number, which is first established by the destination station. To maintain the consistency of routing tables when the network topology changes dynamically, each station must periodically send and receive updates or immediately send updates when it detects a change. Since the problem of storing any form of synchronous time information on the machines does not arise here, the phase relationship of update times between mobile stations is also not taken into account. In distance vector routing algorithms,

Each station uses packets broadcast from other stations to determine which stations it can reach and the number of hops required to reach the desired station. The problem here is to assign sequence numbers to a path, not to assign distance measurements to a path. The packets transmitted will contain either a Layer 2 (MAC) address or a Layer 3 (Network) address.

2.2.2. Routing table and route advertisement information

Routing information in DSDV is provided by broadcasting or multicasting packets. These packets are transmitted periodically and are supplemented when changes in the network topology are detected, such as when stations move within a network. Data on the first path arrival time and the best path arrival time for each destination station are stored. A decision on the delay between two routing advertisements is made on the basis of this data to reduce the variability in the routing tables. The delay between two advertisements may be arbitrary to reduce the number of advertised routes already in the routing tables with the same sequence number.

The DSDV protocol requires each mobile station to advertise its own routing table (i.e., its flows) to its neighbors. The flows in this list may change dynamically over time, so the number of advertisements that must be performed must be large enough to ensure that every mobile station can always identify other stations in the area. In addition, each mobile station must forward data packets to other stations on an as-needed basis. This forwarding makes it possible to determine

a path to the destination with the smallest number of hops. A mobile computer can exchange data with any other mobile computer in the group even if the other computer is not in direct communication range. If DSDV works at layer 2, it will work at higher layers.

All computers must cooperate to create data paths between them and broadcast the necessary data periodically, usually every few seconds. In a wireless environment, it is important that the broadcast information is limited by the transmission range of the physical medium. This is different from the situation in cabled environments where the transmission range to the destination is precisely defined. The broadcast data from each mobile computer includes its new sequence number and the following information about each new path:

 Destination address;

 Number of relay nodes to reach the destination;

 The sequence number of the information received for the destination, initially labeled with the destination.

The transmitted routing tables also contain the hardware addresses, and (if appropriate) the network addresses of the transmitting computers in the headers of the packets. The paths with the latest sequence numbers will always be given priority in forwarding decisions, but are not necessarily advertised. For paths with the same sequence number, the path with the smallest metric will be used. When transmitting routing tables, the sequence number will also be sent to all hosts.

mobility is different and each machine will decide for itself to maintain each routing line to the source machine.

Paths received by broadcast will be forwarded by the receiver to other hosts as it broadcasts its information; the receiver will increment the path length measure before broadcasting the path in case the data packets require one or more relay nodes to reach the destination.

2.2.3. Frequency of route advertising

One of the most important parameters in the selection is the interval between two broadcasts of packets containing routing information. However, when a mobile computer receives any new or modified information about a route, it is transmitted immediately. This has the effect of spreading the new routing information as quickly as possible among the mobile computers in the workspace. This rapid re-broadcasting places a new requirement on the protocols to converge as quickly as possible. The movement of a mobile computer can cause a broadcast storm, which can damage and degrade the wireless medium. Mobile computers cause link breaks as they move from one location to another. Link breaks can be detected by Layer 2 protocols or when a machine does not receive advertisements from a neighboring station for a specified period of time. A broken link is described by a measure of ∞ (i.e., any value greater than the largest possible measure). When a link to the next node is broken, any path to that node will be assigned a distance measure of ∞. When there is a change in the path

occurs, information about the modified path is included in the routing advertisement packets. The construction of the broken link description information only occurs when sequence numbers are generated by mobile stations other than the destination mobile station. The sequence numbers defined by the originating mobile stations are even numbers, and the sequence numbers generated to specify measures ∞ are odd numbers. In this way, any odd “real” sequence number can be used to replace a measure with ∞. When a node receives a measure ∞, and then has a finite-measure sequence number, it triggers the routing update advertisement to distribute important information about a destination.

In networks with a large number of mobile stations, changes may occur between periodic routing advertisements. To reduce the amount of information in these routing advertisements, two types of packets are defined. The first type carries all the information in the packet and is called the “ full ” type . The second type carries only the information that has changed since the last full routing advertisement and is called the “ supplemental ” type. By design, the information in the supplemental routing update form should fit into a single network protocol data unit (NPDU). The full routing update form usually requires many NPDUs, even for a network with a small number of mobile stations. When mobile stations are not moving, the full routing update form is transmitted. When movement is frequent and the size of the supplemental routing information is close to the size of an NPDU, the full routing update form is included in the plan. Each mobile node wants to determine which path changes are important enough to send in each additional advertisement. For example, when a stable path gives a different metric to some destination, this change is an important change.