Energy Aware Path Selection For BFF Algorithm In FISH Network

DOI : 10.17577/IJERTV2IS80033

Download Full-Text PDF Cite this Publication

Text Only Version

Energy Aware Path Selection For BFF Algorithm In FISH Network

Energy Aware Path Selection For BFF Algorithm In FISH Network

Prof. S. P. Pingat Ms. A. K. Gaikwad

Department of Computer Engineering, Department of Computer Engineering, Smt. Kashibai Navale College of Engineering Smt. Kashibai Navale College of Engineering,

University of Pune University of Pune.

ABSTRACTFundamental interconnecting structured homogenous network model has a fish shaped topology and proposes a Bypass Flow Splitting Forwarding algorithm to forward packets in network. Reset time is constant in BFF algorithm and there is no provision for optimization of energy while selecting path. Which affects the capability of BFF algorithm to make proper utilization of channel which increases packet loss ratio and controlling the transmission energy consumed for a packet to reach destination. So main objectives of proposed algorithm are :-

  1. To achieve higher link utilization using dynamic reset time which increases throughput.

  2. To increase delivery rate and avoid route failures by selecting energy efficient path in Fish network.

    Keywords:Concurrent multipath (CMP), forwarding granularity, fundamental interconnecting structure homogeneous (FISH)

    networks,BFFAlgorithm,Energy-Aware, Optimization, Path Selection Algorithm, AODV protocol.


      N fundamental interconnecting structured homogenous (FISH) network bypass flow splitting forwarding (BFF) algorithm was proposed to forward packets & makes better utilization of available bandwidth. The drawback of single path routing which can limit the packet delivery rate and fixed granularity forwarding which can lead to inefficient use of network bandwidth were investigated. A enhanced BFF algorithm is presented here with energy aware path selection in FISH network. Also constant reset time affects the performance of BFF algorithm. Because it needs updation of available bandwidth for each edge to wait for finishing of hash list refreshing process.It has effect on utilization & increases packet loss ratio. If traffic rate is less in FISH network , due to constant reset time there will

      be less utilization of edge in reverse case if actual bandwidth required is more , then there will be chances of packet loss . The Hash list providing available bandwidth for each edge is refreshed after reset time. So every edge has to wait for retrieving its available bandwidth till reset time is over. Also routing protocols with no means of optimizing energy generally uses same path for longer period. It results in exhaustion of energy at nodes. So proposed system implements dynamic reset time with energy efficient path selection in FISH network to increase delivery rate.


      1. Fish Network Model :-

        Here is the brief view of existing FISH network model.

        The link disjoint paths will become more than that in past with rapid increase both in bandwidth & links in recent years.

        Figure 1 FISH Topology

        This topology has Fish like shape. In single path routing in FISH network it uses single path to forward packets which degrades the performance of network. The destination address (DA), source address (SA),destination port (DP), and source port (SP) can consist of a flow.With the same DA, the other three can constitute eight combinations. The traditional single-path routing gets next-hop interface only through DA, which makes eight different flows forward to the same path. It is impossible for the single-path routing to provide differentiated services.

        With the same DA but different SP or DP under different application environment, the traditional single-path routing, such as open shortest path first (OSPF), makes flow-splitting characteristics impossible. With the rapid increase of Internet users, more users have more application requirements. In addition, the browsing habits of web users will produce more and more flows of the same destination. It is desirable to provide flow splitting based on the flow characteristics; however, conventional single path forwarding does not make a distinction about eight combinations. As a result, flow splitting is not possible in single-path routing.

      2. Single Path Routing In FISH Network

        Figure 2. Single Path Routing

        Besides the routing oscillation caused by misconfiguration in the control plane of BGP, we found that the unbalanced traffic will also cause the routing oscillation. With the rapid development of diverse applications, the dominant traffic has changed from traditional C/S and B/S applications such as WWW, file transfer protocol (FTP), and e-mail to other emerging applications such as online media, BitTorrent, eDonkey, Skype, PPlive, and so on.

        With respect to the enormous traffic caused by P2P and online media, they will cause routing oscillation even though there is no policy conflict and no misconfiguration in the BGP control plane. Therefore, the research on routing oscillation in FISH networks has great practical significance. Based on the FISH topology model, we add two kinds of traffic. Data transmission A, C, and E belong to the same service (such as FTP), and B, D, and F use another service (such as video conference). As shown in Fig. 2, these six data transmissions have been forwarded to the same path in the traditional single-path forwarding strategy. In Fig. 2(a), six flows are transmitted via node 3. With the increase of traffic, node 3 will cause longer delay to the forwarding; ultimately, packet loss will occur. The other two paths will not be used in a single-path technology even if they are all idle until routing decision is invoked. After the new routing decision, all these flows are then transmitted to another next- hop, such as node 5,as shown in Fig. At the same time, nodes 3 and 4 do not share or split the traffic.

        After a certain period of time, node 5 cannot handle the packets, and packet loss occurs again.

        The route will be routed again for another best path, such as node 4, shown in Fig. 2(c). If the transmission continues for a long duration, the routing state will switch and oscillate frequently among Fig. 2(a)(c). Routing oscillation wastes too much processing time of the control plane. The oscillation also leads to the increase of delay and jitter in data plane. The traditional single path cannot split the traffic. Available bandwidth cannot be used effectively and concurrently.

      3. Fixed Granularity Forwarding :-

        Figure 3 Fixed Granularity Forwarding

        According to the same topology and data transmissions shown in above, when using a fixed forwarding granularity of (DA, SA), which is shown in Fig. these data transmissions are divided into two parts. Data transmission A and B are forwarded to node 3, and other data transmissions are transmitted to node 4.It is shown in Fig. 3(a) that (DA, SA) forwarding partially solves the drawbacks of single- path. Compared to Fig. 2, it decreases traffic faced by a single next-hop device. It can use the available bandwidth of different links more effectively (but not entirely), and the ability of flow splitting is better than single-path forwarding. Furthermore, for the same topology and data transmissions, when using another fixed forwarding granularity (DA, DP), as shown in Fig. 3(b), data transmissions are divided into two parts. Transmission A, B, and D were forwarded via node 3, and C, E, and F were forwarded to the path via node 4. This strategy can solve partially the drawbacks of single-path transmission.Compared with Fig. 2, it decreasesthe traffic burden under single-hop circumstances. Compared to Fig. 3(a), it can handle the unbalanced traffic features. The ability of load balance is better than (DA, SA).


      FISH network architecture has been divided into 3 modules.

      3.1)Bypass Statistics Module 3.2)Classification Module 3.3)Bypass Forwarding Module.

        1. Bypass Statistics Module :-

          BFF Algorithm maintains bypass statistics process machine to record the network flow characteristics. Maintains BFF data structure which stores all network flow characteristics& hash index for transport layer packets.When new packet arrives to be forwarded to destination, it checks if entry is present in hash list , if not then it makes new entry in hash list.

        2. Classification Module :-

      First it calculates bandwidth of all available paths and data rate available. New forwarding ratio is calculated using Updates reset time and feedback information for bypass forwarding module. It computes and resets hash list at a certain period in order to get variable flow splitting ratio.

        1. Bypass Forwarding Module :-

          When packet arrives at PR2 bypass forwarding module executes. Which accepts feedback information from PR1 & sets bypass bits accordingly

          .it also splits data packets according to new forwarding ratio & forwards them to

          intended destination.

        2. Energy Optimization Based Path Selection

          It is a dream for all people to have a network connection anywhere at all times. It is therefore imperative to have such a dream be realized for feasible solutions to the next generation wireless networking be implemented. However, in networking there are still quite a number of important issues for instance in routing that are partially addressed or not addressed at all, e.g., scalability, network capacity, security and energy awareness . In order to address these routing issues effectively, our work concentrates on routing mechanism executed in layer-2. Such a routing mechanism is called a mesh path selection and forwarding .

        3. Energy-Aware And Efficient Routing Protocols:-

          Routing protocols with no means of optimizing energy have a tendency of using the same path for a longer period . The effect of using it for a longer period is that the energy of the nodes along the chosen path may be quickly exhausted. If the nodes energy is quickly exhausted that may result in the network being partitioned affecting the information delivery even though there might still be enough

          energy to some of the nodes. Therefore, energy should always be considered during the design of a wireless mesh routing protocol. The amount of energy that is being consumed by the network also determines how long the network can work . In this research our findings suggest that the most valuable metric for routing protocol performance under the IEEE 802.11s is energy awareness for network survivability. This consideration is more focused especially to networks that are to be deployed in rural areas. Energy-awareness routing guarantees that nodes with low energy in the network stay alive. A probability function in energy-aware routing is used as a means of choosing suboptimal paths. This technique is also dependent on the amount of energy consumed in each path in the network . The work in states that choosing the shortest path might not be the best option as it may cause an energy dissipation of nodes in that path. An alternative to the use of a minimum path, multiple paths are available to route from the source node to the intended destination node. For the network lifetime to be prolonged, one among the many available paths is used with a certain probability. To advance the energy efficiency of an energy-unaware path localized rerouting techniques were proposed and presented in . The above presented energy efficient routing protocol techniques can perform well in terms of energy conservation. To achieve that, neighborhood knowledge at nodes is required. The work presented in shows that substantial amount of resources can be consumed in dynamic networks to update and gather the information for the nodes neighbors.

        4. .Energy Aware RoutingProtocols :-

          Routing protocols use same path for a longer period if there is no provision for optimization of energy. Due this energy gets exhausted at that node and decreases information delivery rate. T

          he amount of energy that is being consumed by network also determines how long the network can work. Energy awareness routing guarantees that nodes with low energy in network stay alive. Ad hoc On-Demand Distance Vector (AODV) Routing protocol with additional energy field is used to select energy efficient path in FISH network. A probability function can be used as a means choosing sub- optimal paths in energy-aware routing.

        5. AODV/DV Protocol :-

      AODV is a reactive routing protocol, meaning that it establishes a route to a destination only on demand. In contrast, the most common routing protocols of the Internet are proactive, meaning they find routing

      paths independently of the usage of the paths.InAODV, the network is silent until a connection is needed. At that point the network node that needs a connection broadcasts a request for



      connection. Other AODV nodes forward this message, and record the node that they heard it from, creating an explosion of temporary routes back to the needy node. When a node receives such a message and already has a route to the desired node, it sends a message backwards through a temporary route to the requesting node. The needy node then begins using the route that has the least number of hops through other nodes. When a link fails, a routing error is passed back to a transmitting node, and the process repeats.The advantage of AODV is that it creates no extra traffic for communication along existing links. In AODV the source node and the intermediate nodes store the next-hop information corresponding to each flow for data packet transmission . In an on-demand routing protocol, the source node floods the RouteRequest packet in the network when a route is not available for the desired destination. It may obtain multiple routes to different destinations from a single RouteRequest. A RouteRequest carries the source identifier (SrcID), the destination identifier (DestID), the source sequence number (SrcSeqNum), the destination sequence number (DestSeqNum), the broadcast identifier (BcastID), and the time to live (TTL) field. When an intermediate node receives a RouteRequest, it either forwards it or prepares a RouteReply if it has a valid route to the destination.


      1. Energy Conserving Routing Metrics:-

        1. Residual Energy :-

          Energy status of a node is the most important

          metric to be considered while selecting a route to forward packets. Cost function used is

          = / (1)

          4.1.3. Local Routing :-

          In the work done in reactive routing algorithms are denoted as global where all nodes take part when searching for a path, at the same time the source node and the intended destination node makes the decision to conclude. For a node to take part in the route searching process gives authorization and as a result a broadcast is made to all the node about the decision making process. A criterion also exists which was designed to be used by the Local Energy- Aware Routing (LEAR) algorithm. This criterion is designed to provide a profile for the energy of the nodes where the intermediate nodes that are willing or reluctant to reply to route or to forward data traffic are defined.

          For a routing

          protocol performance to be improved it is therefore imperative to avoid exchanging control information regularly by applying the technique of shifting the accountability for reacting to changes in the energy budget of a node.

          1. 1.4 Transmssion Power Model :-

            Given a network graph, a routing algorithm basically entails searching for the best possible route where a vertex and an edge signifies a node and a wireless link respectively connecting two end nodes which are in the vicinity of each other's radio transmission range. If the transmission power of a radio in a node is adjustable, the direct transmission range is adjustable together with the intermediate nodes. An increase in the communication range occurs when the transmission power is stronger while the number of hops are being reduced (hop count) to the destination. A lot of research has been conducted on transmission power adjustment in topology control for WMNs The main objective for this approach is to make sure that the network topology is kept connected while

            Where is the cost function and energy of node i at time t.

        2. Energy Drain Rate:-

is the remaining

using minimal power. Transmission power control based energy efficient routing protocols are good in proving routes that uses minimal transmission power from a source to a destination node.

Energy drain rate represents the reply packet energy. Which is nothing but the energy consumed on a particular path to forward packets. An exponential weighted moving average method was used to calculate energy drain rate. For each second this method gives an approximation of the amount of energy dissipated. The fraction between residual battery power(RBP) and drain rate(DR) represents the cost function at a node as follows:-

  1. Proposed System :-

Proposed system tries to enhance BFF algorithm

w.r.t. bandwidth utilization and packet delivery rate. In existing system static reset time is used. It decreases the bandwidth utilization. If data rate decreases in network. Due to static reset time channel remains ideal until reset time elapses. And if network traffic increases suddenly ,there are chances of packet loss. Proposed system tries to solve these problems. Proposed system implements paths with

    1. Algorithm Design And Development

      1. SetUp Phase :-

        In proposed system dynamic reset time is implemented with AODV based energy efficient path selection.The proposed algorithm will result in an unbiased energy spending among nodes which also maximizes network lifespan. The AODV protocol stores set of good paths in its routing table and one good is selected among many available paths based on a probabilistic function. The connection is initiated by source node and before the request could be sent, the energy cost field is set to zero as : Cost()=0 (3)

        – source node

        – destination node

        Afterwards energy of neighbor node is calculated and added to total energy cost of path :-

        , = Cost()+Metric( , )

        utilization are discarded and low costs are added to

        forwarding denoted as FTjof .

        high cost in terms of energy dynamic reset time . So

        that whenever data traffic decreases, reset time will

        = | , (min


        ) (4)

        be increased avoiding unnecessary resetting of bypass bits. And if data traffic exceeds channel capacity, reset time gets decreased , bypass bits are reset .after small interval of time , avoiding packet loss. Proposed system considers energy factor also.While selecting path for data transmission energy efficient path selection is considered. One Hell packet is send from source to destination having energy field added using AODV protocol. It gives acknowledgement back in terms total energy utilized for transmission.

        It calculated using formula :- E=Tx+Rx+Px

        Where tx=transmission energy

        Rx= Receiving Energy Px=processing Energy

        select energy efficient path for transmission and sets bypass bits for that path. And data packets are forwarded to intended destination. Proposed system tries to improve operational time , throughput and reduces latency in FISH network.

        Where constant and min , is min energy cost in joules between node j and k.

        Afterwards energy of neighbor node is calculated and added to total energy cost of path :-

        , = Cost()+Metric( , )

      2. Adaptive Reset Time Algorithm:-

        Input: threshold, incrementValue, DecrementValue, maxResetTime, minResetTime

        Output: resetTime

        1. Calculate bandwidth

        2. If bandwidth > threshold

        3. If( (resetTime – DecrementValue)

          < minResetTime) resetTime -= DecrementValue

        4. else

        5. If( (resetTime + incrementValue)

        6. > maxResetTime ) resetTime += incrementValue

        7. Wait for 5 sec

        8. Go to line number 1

Simulation Time

Single Path Routing

Mulitipath routing


with DRT

Energy Efficient path

















Simulation Time

Single Path Routing

Mulitipath routing


with DRT

Energy Efficient path

















5.1.3. Path Selection Algorithm :- SelectEEPath()

  1. Get list of Path with good bandwidth P={p1,p2,..,pn}

  2. EnergyThershold=10%

  3. Each p P

    Get hops from each path H={p,p,.,hn}

  4. If(PathEnergy<EnergyThreshold)

  5. Reject p

  6. End.


An awk script is executed to obtain data from trace file. This data is used to get throughput and delay. Corresponding graphs are shown in figures. Table 1 shows the data obtained for throughput in static reset time, dynamic reset time and with energy efficient path selection. As we can observe from table there is improvement in throughput with the use of enhanced BFF algorithm in fundamental interconnecting structured homogeneous network..

Simulation Time

Single path Routing

MultiPath Routing

BFF with DRT

&Energy Efficient Path

















Table 6.1 Comparison of Throughput by various algorithms

Table 11.2 Comparison of delay for various algorithms

We can see the improvement through graph.

Figure 11.4 Comparison graph for Throughput

Figure 11.5 Comparison graph for Delay


Propose system tries for enhancement for Bypass Flow Splitting Forwarding algorithm in Fish Network using optimization of reset time along with energy optimization based path selection to improve operational time , throughput and to reduce latency. The expected results from the proposed system are :-

  1. To achieve higher lin utilization using dynamic reset time which increases throughput.

  2. To increase delivery rate and avoid route failures by selecting energy efficient path in Fish network.


1. Laiquan Han, Jinkuan Wang, Xingwei Wang, and Cuirong Wang., Bypass Flow-Splitting Forwarding in FISH Networks , IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS, VOL. 58, NO. 6, JUNE 2011.

2 .F.-C.Kuo and X. Fu, Probe-aided mulTCP: An aggregate congestion control mechanism, SIGCOMM Comput. Commun. Rev., vol. 38, no. 1

,pp. 1728, Jan. 2008.

3.L. Han, J. Wang, and C. Wang, Connection- oriented concurrent multipath forward algorithm, J. Southeast Univ. (Natural Science Edition), vol. 38, no. 9, pp. 1216, 2008, Suppl.

  1. L. Han, J. Wang, and C. Wang, A crosslayer concurrent multipath random forward algorithm, in Proc. 9th ICYCS, Zhangjiajie, China, 2008, pp. 270 275.

  2. D. Xu, M. Chiang, and J. Rexford, DEFT: Distributed exponentially weighted flow splitting, in Proc. 26th IEEE INFOCOM, May 2007, pp. 71 79.

  3. A. Kvalbein, T. Cicic, and S. Gjessing, Post- failure routing performance with routing configurations,in Proc. 26th IEEE INFOCOM , may 2007, pp98-106.

  4. S. Kandula, D. Katabi, S. Sinha, and A. Berger, Dynamic load balancing without packet reordering, SIGCOMM Comput. Commun. Rev., vol. 37, no. 2, pp. 5162, Apr. 2007.

  5. Martin M. Mhlanga, Thomas O. Olwal, Murimo B Mutanga, Mathew O. Adigun , Energy Optimization based Path Selection Algorithm for IEEE 802.11s Wireless Mesh Networks.

  6. Mhlanga, M.M. Nyandeni, T.C. Olwal, T. Ntlatlapa, N. and Adigun,M.O. Energy-Aware Path Selection Metric for IEEE 802.11s Wireless Mesh Networking, SATNAC, Proccedings, September, 2009.

  7. Joe, I A Path Selection Algorithm with Energy Efficiency for Wireless Sensor Networks 5th ACIS IntConf, 2007.

Leave a Reply