Routing Optimization in Networks

Routing Optimization in Networks

Suchitha.S Professor and Head Department of MCA Adarsh College Bangalore, India

Dr. B. G. Prashanthi

Asst. Professor and Research Scholar Department of MCA(VTU)

Dayananda Sagar College of Engineering Bangalore, India

Abstract Networks are used for transferring different kinds of data. There are many issues are present regarding networks. Routing is one of the basic issue present in networks . Route is one which links source system to destination system. Network routing protocols computes the route from one end to another end by using parameters like current traffic, network topology etc. Routing optimization problems on networks consist of finding paths between nodes of the networks in an efficient way. The performance of the network can be improved when routing optimization is used. Many solutions for the problems have proved to be useful for many real world applications. This paper presents the general idea of routing and its optimization in networks and associated work done in the field of routing optimization. It also deals with various schemes, working of algorithms like link state and distance vector, protocols, metric used for routing and its optimization.

Keywords Optimization, routing algorithm, router .

1. INTRODUCTION

   We can compare networking system to traffic system. To make it simple we use layer systems. When we want to send packets from source to destination it requires proper routing. In traffic engineering routing optimization can be used to find the proper and best path so the performance of the network can be improved.

   Selection of proper and the best path can be done with the process of routing. Routing means forwarding traffic in the network. Routing concept can be used for various kinds of networks. The various types includes the telephone network which uses the concept of circuit switching, electronic data networks which uses the packet switching concept and transportation networks.

   When packet switching network is used, intermediate nodes are used for packet forwarding from source to destination. Network hardware devices such as switches, gateways, router are considered as intermediate nodes. Forwarding of packets can be done by checking the entries present in the routing tables, which maintains a list of the various routes. For multiple alternative paths, multipath scheme of routing can be used .

   Static routing is used for small networks where routing tables are configured manually. For large and complex networks where changes are rapid, making manual updation of routing table is unfeasible. This problem can be solved by using dynamic routing.

   In dynamic routing, based on information carried by routing protocols routing tables are constructed automatically.

2. ROUTING SCHEMES There are many routing schemes are available.

   • In Unicast, message is delivered to a single specific node. Most of the traffic on internet and intranets called as unicast data or unicast traffic and routing is called unicast routing. In this routing the destination node is known before only so the router checks the routing table entry and forward the packet. It is the simplest routing and the dominant form of message delivery on the Internet.

   • In Anycast, message is delivered to anyone out of a group of nodes. When multiple hosts have same logical address this forwarding mechanism is used. The packet is sent to the host which is nearest in routing topology. Usually it is done with the help of DNS server.

   • In Multicast, message is delivered to group of nodes which belong to a specific group. Multicast routing can be compared with broadcast routing. In multicast routing, packet is sent to nodes which belong to some group. But in Broadcast routing, packet is sent to all the nodes.

   • In Geocast, information is passed based on geographic location.

   • In Broadcast, all the nodes which are connected in the network gets the message . Broadcast domains are created by the router and message can be forwarded to all the nodes which are connected in the network.

3. WORKING OF ROUTING ALGORITHMS There are many routing algorithms exist. To find the proper path from one system to another, router can use routing algorithms. It considers many parameters like packet communication cost, time delay, number of hops to determine the best route.

   The two types of algorithms used are

   • Algorithms based on global routing

   • Algorithms based on decentralized routing

   Each router has complete information about the other routers which are present in the network in global routing and it also has the information regarding the network traffic . LS (link state) algorithms is the other name for global routing algorithm.

   In decentralized routing algorithms, each router does not know regarding each and every router which is present. Whichever routers are connected directly regarding that information is maintained by router. Distance vector algorithm (DV) comes under this category.

   1. Steps for LS algorithms

      • When a router starts working, it should identify the routers that are physically connected. It should get the IP addresses of the routers which are connected. First it sends a HELLO packet over the network. Whichever router receives this packet replies with sending IP address.

      • Next is to find delay time. To do this , routers send ECHO packets over the networks. Whichever router receives this packet replies with an ECHO reply packet. This gives round trip time. Router can find delay time by dividing round trip time by two. Transmission and processing time both include in this which is the time taken to reach the destination system, processing and sending reply back.

      *This step broadcast its information over the network. In this step, using broadcasting information is passed to other routers and receive the other routers information.

      All routers share their information with each other. So every router has the information regarding network status.

      *In this step, efficient route can be identified by using any proper algorithm between the two system. Shortest path algorithm by Dijkstra is one of the algorithm to identify the efficient path between the nodes. Starting graph of the network system should be drawn based on data collected from other routers. The graph drawn specifies the routers location and their connection links between the nodes of the network.

      Each node is assigned with a weight which is a number value. This weight is a based on average traffic, time delay parameter, hop counts between the systems. If multiple links are available among the nodes, link with the lowest weight is selected by the router.

   2. Algorithm DV

      Bellman-ford routing is the other name for this algorithm. In these algorithms routing table is maintained. Routing table shows the routes between the nodes. Information about other routers should be maintained by each router in both LS and DV algorithms.

      When the network is very huge, the number of routers are also more and handling routing table becomes very difficult. To solve this problem hierarchical routing can be used.

4. NETWORK PROTOCOLS

   One of the network routing protocol is path vector protocol which maintains the path information that gets updated dynamically. Routing table entry consists of the next router, the route to reach the destination node and destination node

   . It is different from the distance vectr and link state routing. An example for path vector protocol is Border Gateway Protocol. The reachability of network is advertised by the autonomous system boundary routers (ASBR), which participate in path vector routing. According to policy the advertised path should be verified. In BGP, the routing table maintains the entries of autonomous systems which are

   traversed to reach the destination system. The other protocol called Exterior Gateway Protocol (EGP) does not use path vector concept.

   It has three phases:

   1. Initiation

   2. Sharing

   3. Updating

   Link state routing and Distance vector are used inside an autonomous systems. They are routing protocols used for intra-domain concept and inter-domain concept of routing cannot be implemented. Inter-domain routing can be implemented using another routing called path vector which can be compared with distance vector routing .

   In path vector routing one node should be identified as speaker node which represents the autonomous system. Advertising to the other nodes should be done based on routing table entries.

5. METRICS

   Metric is one of the important concept related to routing table. Router uses routing metrics to make decision regarding routing.

   When many routes are available metrics can be used. Available routes can be stored in routing table. The other information can be stored using topological and link databases. Routing information protocol can be considered as an example which uses hop count that is number of hops present to find the efficient path. The lowest metric is selected as default gateway. The route will directed with the lowest metric.

   Proper and efficient route can be determined by the router when many routes are available to a destination node by making use of router metric which contains number of values.

   A Metric can include these things:

   • path reliability

   • load

   • measuring link utilization

   • delay parameter

   • bandwidth parameter

   • throughput parameter

   • Maximum transmission unit

   • hop count

   The various metric forms are :

   Additive type – In additive , individual link cost should be calculated . To find the total cost sum of all individual cost can be used.

   Concave type In concave, cost for individual link should be calculated. To find the total cost minimum costs of individual links should be considered.

   Multiplicative type In multiplicative, individual cost of the link should be calculated. Total path cost can be determined as product of the individual link cost.

6. RELATED WORK

   Authors[2] have specified the routing optimization under uncertainty with deadlines. Here the optimal routing policies should be find out. From many decades we have studied routing optimization problems like shortest path problem. Authors are discussing about how uncertainty models can be used for real world problems.

   In [3] authors have discussed about different approaches of network routing. Based on this result has been generated . Swarm intelligence routing has been discussed and it has been compared with static and dynamic routing for better understanding.

   In [5] authors have discussed about NEMO (Network MObility), Architecture of NEMO, NEMO BSP, limitations of NEMO BSP , Route Optimization(RO), challenges in RO. Issues in RO like signaling, memory requirements ,header overhead, IntraRO ,deployability, location management, location transparency are also presented . Different RO schemes are presented. Authors have given the idea that future research work can be done to find performance considering network topology change for RO schemes which is related to nested mobile network. Additional signaling for various RO schemes has to be handled. Some issues related to RO handoff should be handled.Authors have suggested to add security aspect with RO.

   Authors[6] have implemented routing optimization for traffic engineering.To achieve desired performance routing optimization is very important in traffic engineering. Algorithms have classified based on multiple dimensions like unicast/multicast, intradomain/interdomain, online/offline scheme and other things. Authors have discussed regarding trafiic engineering issues.

   Authors[7] have reviewed the protocols for Mobile Ad-hoc NETworks(MANET). They have discussed regarding manet routing principles like proactive routing, reactive routing, hybrid routing . Early MANET protocols have been discussed. Ad-hoc On-demand Distance Vector (AODV) has been designed for the improvement of previous work of DSDV protocol. Security is the issue of AODV.

7. CONCLUSION

This paper specifies the concept of routing, different routing algorithms, schemes, metric used for routing optimization. The significance of routing optimization is specified. The overview of different research work in the field of routing optimization also has been specified.

REFERENCES

1. Srinivas Shakkottai and R. Srikant, Network Optimization and control,

   Foundations and TrendsR in Networking , Vol. 2, No. 3 (2007) 271

   379.

2. Patrick Jaillet, Jin Qi,Melvyn Sim,Routing optimization with deadlines under uncertainty.

3. Peter Dempsey and Alfons Schuster,Swarm intelligence for network routing optimization , Journal of telecommunications and information technology,2005.

4. Route Optimization in IP Networks, Jennifer Rexford

5. Abu Zafar M. Shahriar, Mohammed Atiquzzaman, Senior Member, IEEE, and William Ivancic,Route Optimization in Network Mobility: Solutions, Classification, Comparison, and Future Research Directions , IEEE communications surveys and tutorials, vol.12, No.1,first quarter 2010.

6. Ning wang, kin hon ho,George pavlou and michael howarth, University of surrey, An Overview of routing optimization for internet traffic engineering, IEEE communications surveys and tutorials,1st quarter 2008.

7. Alex Hinds, Michael Ngulube, Shaoying Zhu and Hussain Al-Aqrabi, A Review of Routing Protocols for Mobile Ad-Hoc NETworks (MANET),International journal of information

   and education technology,vol.3,No.1, february 2013.

8. https://en.wikipedia.org/wiki/Routing

9. https://en.wikipedia.org/wiki/Path_vector_protocol

10. https://en.wikipedia.org/wiki/Metrics_(networking)

11. http://docwiki.cisco.com/wiki/Routing_Basics

12. http://nptel.ac.in/courses/IIT- MADRAS/Computer_Networks/pdf/Lecture32_RoutingAlgorithmsDV. pdf

13. http://www.tutorialspoint.com/data_communication_ computer_network/network_layer_routing.htm

14. https://en.wikibooks.org/wiki/Communication_Networks/Routing