Figure 1. Example of the OSPF routing protocol
The revolution of the internet is based on the ability to transport data from source or origin to a destination. This revolution over the last three decades has seen unprecedented growth rate and it is expected to grow much higher especially with the emergence of smart mobile devices and internet penetration into the developing world. However, the transport of data has never been without challenges. Some of these challenges include: loss of data, collisions and delay in sending data and inefficient routing algorithms. In this work, the researcher proposes an algorithm that will not only find the shortest possible path but also able to find the most efficient path for data routing. The researcher seeks to use Dijkstra's algorithm that will be used to find the shortest path from a named source to a destination and to explore the logic behind Carrier Sense Multiple Access with Collision Detection (CSMA/CD) to investigate how busy the shortest route or path may be.
The revolution of the internet is based on the ability to transport data from source or origin to a destination. This revolution over the last three decades has seen unprecedented growth rate and it is expected to grow much higher especially with the emergence of smart mobile devices and internet penetration into the developing world.
This revolution is such that whatever the size of one's organization, be it small or big, one can take some simple steps to implement a very good and efficient network infrastructure to provide significant and substantial benefits to the organization. Benefits to the organization include improved customer service, lower cost through improved operational efficiency and accelerated growth.
The basis of this internet revolution and other networks are the routers and switches which are responsible for the transport of data from one device to another.
Router is a device that forwards data packets across internetwork computers from source to destination and it performs two basic functions: finding the optimal routing path(s) and transporting data packets from source to destination.
A network switch is a computer networking device that links network devices. The routers, switches, computers, hubs and others devices form a network. [Cisco, Building your network foundation]
There are two main types of networks: Local Area Networks (LANs) and Wide Area Networks (WANs). For many businesses, a LAN is typically used to communicate within a building or campus, and a WAN is used to connect multiple LANs, and to communicate across a region, country, or the world.
A more official definition of a LAN is a group of computers and associated devices that share a common communications line or wireless link within a small geographic area (for example, within an office building). The importance of a LAN is that it enables PCs to talk to one another, and to share printers or servers. This sharing of data and resources enables cost savings and increased productivity.
A WAN is a network that links together multiple geographically dispersed LANs, usually via high-speed phone lines. A WAN covers a relatively broad geographic area (for example, communications between two countries) and often uses transmission facilities provided by telephone or cable companies [Cisco, Building your network foundation].
Most routing algorithms tend to find the shortest path from source to a destination; however the shortest path may not necessarily be the most efficient. It may have higher data packets, hence creating congestion and collision as a result data packets may be lost and not to the appropriate destination, hence the need for a more efficient routing algorithm.
This research work seeks to design an algorithm to:
The authors seek to adopt the Dijkstra's algorithm that will enable us find the shortest path from a named source to a destination.
They also explore the logic behind Carrier Sense Multiple Access with Collision detection (CSMA/CD) to investigate how busy the shortest route or path may be. An algorithm is therefore designed based on the Dijkstra's algorithm and the idea behind CSMA/CD that determine the most efficient route from a source to a destination.
Routers and Switches have played important roles since the emergence of computer networks and will continue to be an integral part of computer networks since they do not work in isolation; however, their implementation is based on the Transmission Control Protocol (TCP/IP) and the Open Systems Interconnection (OSI) models.
Switch as a network device forwards and filter OSI layer 2 datagrams between ports based on the MAC (Media Access Control) address. Most switches are active in the sense that they electrically amplify the signal as it moves from one device to another and they memorize addressing of computers and forward frames to the correct location directly. It normally has numerous ports, facilitating a star topology for devices and cascading additional switches.
Routers forward packets from one network to another by processing information found in the packets on the layer 3 of the OSI model. This processing is done in conjunction with the routing table which is used to determine what interface to forward the packets to. They are able to perform all this functions through the design of the algorithms that they use.
Garcia-Luna-Aceves proposed a family of innovative routing algorithms [3], which computed shortest paths using diffusing computations based on the idea presented in [6]. Diffusing computations is a computation that takes place over a set of networked machines. Dijkstra proposed method [6] for detecting the termination of the computation. DUAL provides loop-free operation at every instant throughout a route computation. This allows routers involved in a topology change to synchronize at the same time, while not involving routers that are unaffected by the change. DUAL is currently used by EIGRP [4], which is a Cisco proprietary routing protocol.
Loop-free Path-finding Routing named LPA by Garcia-Luna-Aceves [8]. This algorithm eliminates the temporary formation of routing table loops during a topology change more efficiently than DUAL. A routing table loop is a path which is specified by the routers' routing tables at a specific time (usually during a topology change), which causes a packet to visit the same node more than once before reaching its destination.
Open Shortest Path First (OSPF) [9] is a link state routing protocol. It is a mature proactive routing protocol widely used in today's wired networks. The basic idea in OSPF is to keep an identical topology database in all routers so that they can build routing tables locally. Routing tables are constructed based on shortest path trees [9]. Because of the properties of the shortest path tree, a route provided by OSPF is loop-free and always the shortest one. OSPF continuously maintains routes to all possible destinations. Hence, it is beneficial for networks with traffic patterns where a large number of hosts in one subnet always communicate with hosts in other subnets. (This is a common advantage of proactive protocols.) OSPF is a complex routing algorithm. Another disadvantage of OSPF is the large overhead of control packets needed to maintain the link state database.
An OSPF network is divided into several indexed areas. Area IDs are manually assigned to all subnets. Each area includes routers in one or more subnets, together with associated network interfaces. Every area maintains one copy of the link state database in that area. Area 0 is always assigned to the backbone network. Two areas are connected to each other when they share edge routers. Non-backbone areas have to attach to the backbone network. A separate copy of OSPF runs in each area. Hence, gateway routers with multiple interfaces in multiple areas run multiple copies of OSPF. There are two major operations in OSPF, determining adjacency and synchronizing the link state database. Five types of route control packets are used to support these two operations :(i) hello packets, (ii) database description packets, (iii) link state request packets, (iv) link state update packets, and (v) link state acknowledgement packets.
Figure 1 illustrates a network using the OSPF routing protocol. Three routers, A, B and C, belong to Subnet I. Routers C and D are in Subnet II. Assume that Subnet I is configured to be the backbone network, so it is Area 0. Assume that Subnet II is defined as Area 1. The bring-up adjacency operation uses hello packets to detect and maintain adjacency between routers. In our example, Router B sends a hello packet to its neighboring router, Router A. Router A adds the Router ID of B (there is a unique ID for each router) into its hello message and broadcasts it. When Router B receives the hello message originated from A, it detects that its ID is in the recently-heard ID list of A.
Figure 1. Example of the OSPF routing protocol
This implies a two-way connection between Routers A and B. Similar procedures happen between other pairs of neighboring routers in this example network.
After two hosts set up two-way communications with each other, entries in the link state database are exchanged and synchronized by database description packets, link state request packets, and link state update packets. A link state acknowledgement packet is used to acknowledge received packets. In this stage, a master router is selected from these two routers. The master router is responsible for setting the sequence numbers during the following procedures. Each router first briefly declares all records in its link state database. If a record received from a neighbor router is more recent than the corresponding record in its own database, the full copy of that record is requested. Similar operations occur between other pairs of neighboring routers. Thus, the databases of neighbor routers can be synchronized.
In a broadcast network, i.e. with a physical network that supports broadcast, a designated router is selected in each subnet. The designated router broadcasts the ID list of all routers in the same subnet. Other routers only broadcast the ID of their designated router. Therefore, a router can determine all routers in the same subnet by the ID of its designated router and the ID list generated by that designated router. For example, assume Router B is the designated router in Subnet I. Router B is responsible for broadcasting the list of router IDs in Subnet I, say Routers A, B and C. Routers A and C only broadcast their designated router ID, Router B.
Note that Router C has two interfaces in two areas. It is the edge router between Areas 0 and 1. Router C is responsible for exchanging link state information between the two areas. For example, in Area 0, Router C is the advertisement router for the information originated in Area 1, even if some of the links are not connected to Router C. If, later, one of these links is used to form a path, Router C is the gateway to reach this selected link. The role of Router C in Area 1 is similar. After a router synchronizes its link state database with neighbors, it starts to calculate the shortest path tree. A shortest path algorithm, named Dijkstra's algorithm [5], is used at each router. Routing entries are built based on the computed shortest path tree. Routers broadcast link state changes, such as new links found or broken links detected, to all their known neighbors. Shortest path trees are rebuilt if necessary.
The Ad hoc On-demand Distance Vector (AODV) routing protocol [PBD02] is a reactive MANET routing protocol. Similar to DSR, AODV broadcasts a route request to discover a route in a reactive mode. The difference is that in AODV, a field of the number of hops is used in the route record, instead of a list of intermediate router addresses. Each intermediate router sets up a temporary reverse link in the process of a route discovery. This link points to the router that forwarded the request. Hence, the reply messages can find their way back to the initiator when a route is discovered. When intermediate routers receive the reply, they can also set up corresponding forward routing entries. To prevent old routing information being used as a reply to the latest request, a destination sequence number is used in the route discovery packet and the route reply packet. A higher sequence number implies a more recent route request. Route maintenance in AODV is similar to that in DSR [2]. One advantage of AODV is that AODV is loop-free due to the destination sequence numbers associated with routes. The algorithm avoids the Bellman-Ford "count to infinity" problem [PBD02]. Therefore, it offers quick convergence when the ad hoc network topology changes which, typically, occurs when a node moves in the network [PBD02].Similar to DSR, poor scalability is a disadvantage of AODV [3].
We use the example topology shown in Figure 2 to illustrate the discovery procedure of AODV. Note that Routers A and C are disconnected from each other while both of them connect to B. When Router A starts a route discovery to C, a route request is broadcast. The request packet contains the requested destination sequence number, which is 1 greater than the one currently kept at A. For example, assume that the destination sequence number for C at A is 0x00000000, then the destination sequence number in the route discovery packet is 0x00000001. The intermediate routers reply to the source if they know the route to that destination with the same or higher destination sequence number. We assume that B does not have a record for a route to C. Therefore, B first sets up a temporary link pointing back to A. In the second step, it increases the number of hops by 1 and rebroadcasts the request. When C receives that request, it creates a new destination sequence number. A route reply with that new sequence number is sent by C.
The initiator and all intermediate routers build routing entries associated with this new sequence number when they receive the reply. The number of hop values can be used to find a shorter path if a router receives two replies with the same destination sequence number. AODV uses a similar scheme as DSR to handle unreliable transmission of control messages.
The Temporally-Ordered Routing Algorithm (TORA) is "an adaptive routing protocol for multihop networks" [PC01]. TORA is a distributed algorithm so that routers only need to maintain knowledge about their neighbors. TORA also maintains states on a per-destination basis like other distance-vector algorithms. It uses a mix of reactive and proactive routing. Sources initiate route requests in a reactive mode. At the same time, selected destinations may start proactive operations to build traditional routing tables. Usually, routes to these destinations may be consistently or frequently required, such as routes to gateways or servers. TORA supports multiple path routing. It is said that TORA minimizes the communication overhead associated with adapting to network topology changes [PC01]. The reason is that TORA keeps multiple paths and it does not need to discover a new route when the network topology changes unless all routes in the local route cache fail. Hence, the tradeoff is that since multiple paths are used, routes may not always be the shortest ones.
TORA uses the concept of height associated with a certain destination to describe the routing metric used by routers. Like water flows in pipes, routers with higher heights may forward packet flows to neighbors with lower heights. Note that since heights for routers are associated with particular destinations, the paths to forward packets are also associated with the corresponding destinations. In networks using TORA, an independent copy of TORA runs for each possible destination. So for different destinations, routers may have different heights and links can have different directions. In the following paragraphs when we discuss the operation of TORA, we assume that it is a copy of TORA with respect to a certain destination.
TORA assigns directions to all links according to the heights of their neighboring routers in terms of upstream or downstream. A link is an upstream link for the "lower" neighboring router. At the same time, it is also a downstream link for the "higher" neighboring router. An upstream link for a router implies that data flows to the corresponding destination can only come into this router via that link. A downstream link for a router means data flows can only leave this router to the neighboring router via this link.
Routers A and C have higher heights than the other routers. The destination router has the lowest height among all routers. The link between Routers A and B is a downstream link for A and is an upstream link for B. Note that Router C has a higher height than B although C is one hop away from the destination. This is because the height assignment algorithm used in TORA does not always favor the shortest path.
The Dynamic Source Routing (DSR) [10] protocol is a distance-vector routing protocol for MANETs. When a node generates a packet to a certain destination and it does not have a known route to that destination, this node starts a route discovery procedure. Therefore, DSR is a reactive protocol. One advantage of DSR is that no periodic routing packets are required. DSR also has the capability to handle unidirectional links. Since DSR discovers routes on-demand, it may have poor performance in terms of control overhead in networks with high mobility and heavy traffic loads. Scalability is said to be another disadvantage of DSR [3], because DSR relies on blind broadcasts to discover routes. There are two main operations in DSR, route discovery and route maintenance.
Figure 2 shows a simple example for DSR. Routers A, B, and C form a MANET. Routers A and C are disconnected, while both of them connect to router B. Assume that at the beginning, the route caches that memorize previous routes in the routers are empty. When Router A wants to send a packet to Router C, it broadcasts a route request to start the corresponding route discovery procedure. Router B receives the request since it is within the radio range of A. Router C is the destination in the request and B does not have a route entry to C in its cache at this time. Hence, Router B appends its own ID to the list of intermediate router IDs in the request and rebroadcasts it. When C receives the broadcast route request message originated by B, it determines that the destination ID matches its own ID. Thus, the route from A to C is found. To help the initiator and all intermediate routers construct proper routing entries, Router C sends a reply back to A using source routing if links are bi-directional. This procedure is feasible because all intermediate routers are in the ID list of the corresponding route request. Intermediate routers construct proper routing tables when they receive the reply originated from C.
Figure 2. Example of DSR and AODV routing protocol
Thus, a route from A to C is built.
During the route discovery procedure, routers maintain ID lists of the recently seen requests to avoid repeatedly processing the same route request. Requests are discarded if they were processed recently since they are assumed to be duplicates. If a router receives a request and detects that the request contains its own ID in the list of intermediate routers, this router discards the request to avoid loops.
The route maintenance procedure is used when routes become invalid due to the unpredictable movement of routers. Each router monitors the links that it uses to forward packets. Once a link is down, a route error packet is immediately sent to the initiator of the associated route. Therefore, the invalid route is quickly discarded [2].
To handle unreliable transmissions of control messages, DSR either relies on the underlying MAC protocol to provide guaranteed delivery or it retransmits control messages for a certain number of times. Since DSR is a reactive protocol, it cannot tell whether a destination is unreachable or the route request is lost. Therefore, it suffers more overhead if the underlying MAC layer does not support guaranteed delivery. This is a common problem for reactive routing protocols because when no reply message is heard, routers with a reactive routing protocol cannot tell the difference between the case of a transmission error and the case of unreachable nodes. Reactive routing protocols try to use extra acknowledgements or a small number of retransmissions to solve this problem and, thus, introduce more overhead. Proactive routing protocols periodically broadcast control messages and remove local routing entries if they time out. Hence, they do not have this problem. But, of course, the periodically broadcast control messages contribute to overhead.
The proposed algorithm is to exploit the Djiksta's algorithm and Carrier Sense Multiple Access with Collision Detection (CSMA/CD) to find the shortest and the most efficient path from a source to a destination.
Djiktra's algorithm finds the shortest path between a named source and a destination through the following steps:
The CSMA/CD works through the following steps:
Main procedure
When collision is detected
The combined Djikstra's algorithm and Carrier Sense Multiple Access Collision Detection (CSMA/CD) seeks to find the shortest and more reliable and efficient data routing algorithm. The comparisons of the three algorithm is shown in Table 1.
Table 1. Shows the comparisons of the three algorithms
Below is the algorithm
Then
a's distance = k's distance + distance (k, a)
Else
a's distance = a's old distance
Djikstra's algorithm was used to find the shortest path between a named source and a destination whiles Carrier Sense Multiple Access with Collision Detection (CSMA/CD) was used to detect and control collision; theoretical analysis of the proposed algorithm shows that the proposed system does not only find the shortest path between a named source and a destination but also finds the most efficient route since the shortest path may not necessarily be efficient due to congestion.
The researcher reckoned only theoretical implementation of this algorithm, therefore future works of any person or group of persons should consider the practical implementation of this algorithm.