# Situation-Aware Survivable Network Design for Tactical Environments
## 3 Proposed Algorithm
### Branch Node Based Routing Algorithm  
#### 3.2.1 Branch Node Detection  
The environment of a tactical network is challenging because of the absence of infrastructure, limited network resource, mobility, and network disconnection. Therefore, a reliable network system in a tactical network is essential, and a possible solution is to build a robust end-to-end path. In this subsection, we introduce the branch node-based routing algorithm, which is modified from the ad hoc on-demand distance vector (AODV) routing algorithm to cope with the network connectivity problem. Typical routing protocols search for one path that has the best performance, whereas the proposed routing algorithm investigates several paths to find the branch node. We define the branch node as a node that duplicates the pass through when a source-destination pair discovers several end-to-end paths, as shown in Figure 3. The advantage of forwarding a packet through the path that includes the branch node is that when a connectivity problem occurs on the main path, the packet can be promptly handled with an alternative path.  
Before introducing the proposed algorithm, we briefly explain the process of constructing a path in the conventional AODV routing algorithm. At a node, after a packet is generated, it checks the destination address and the existence of a path to the destination. If there is no path, before transmitting the packet, the node has to construct a path by using control packets, such as a route request (RREQ) message and a route reply (RREP) message. Figure 4 shows the RREQ message format for the AODV model [30]. A source node broadcasts the RREQ message to investigate a path to reach the destination node. In the case of the intermediate nodes that are not the destination node and do not have a  
Figure 2: QoS data frame structure.  
path to the destination node, they re-broadcast the RREQ message and store reverse paths towards a node originating the RREQ in the route table. The destination node unicasts an RREP message in response to the RREQ message, and a forward path is set up through this process.  
As a first step to specify the branch node, we need to permit the receipt of multiple RREQ messages that have the same RREQ ID as that of the last received RREQ message. The source code in Algorithm 2 helps to forward the RREQ message, which should be originally discarded, and investigate the branch node. In addition, the destination node can reply in an RREP message to construct a forwarding path including the branch node by receiving multiple RREQ messages. Next, we modify the RREQ message format and add new fields, forwarder IP address and RREQ count, as shown in Figure 5. A forwarder IP address field is added to avoid loop formation, and the RREQ count field is for specifying the branch node. When a node receives an RREQ message with the same RREQ ID already stored, it increments the RREQ count value by 1 and re-broadcasts. If a node receives an RREQ message for which the RREQ count is more than 1, it means that this RREQ message has passed through the branch node. Then, that node stores the previous hop as a route table entry--next hop. The next hop information is used as the direction for forwarding a unicast RREP to build the end-to-end connection.