Communication patterns can be classified on the basis of a number of source and destination nodes participating in the communication process. The two major communication models are point‐to‐point communication and collective communication [1]. In point‐to‐point communication there is only one source and one destination for each message. In a network, as per the information handling pattern, there can be only one source–destination pair at a point in time or many such one‐to‐one message passing source–destination pairs can communicate simultaneously. A special case of point‐to‐point communication, referred to as ‘permutation routing’, can also exist where a node can be source of one message and destination for another message at any time instance. In collective communication there can be multiple sources as well as multiple destinations.
As there can be various combinations of single source or multiple sources with single destination or multiple destinations, it leads to one‐to‐all, all‐to‐one, and all‐to‐all communication modes in collective communication. The one‐to‐one combination is not considered, as this becomes point‐to‐point communication. A one‐to‐many communication pattern can be either in multicast mode or broadcast mode. In broadcast, the message is sent from the source node to all other available nodes in the network, while in multicast, the message is sent from the source node to a specific set of destination nodes. A special kind of one‐to‐many communication is known as ‘one‐to‐all scatter’ or ‘one‐to‐all personalized communication’, wherein the source node sends a different message to all the destination nodes simultaneously.
A routing algorithm creates a complete or partial digital map of the network. The digital map is generally in the form of a graph. The partial digital map contains at least the source node and its neighbors. With the digital map of the network available, the routing algorithm plans for the path from the source to the destination on the basis of one or more attributes: delivery time, distance between nodes, number of hops, available bandwidth of the links, and congestion. The cost of the path is calculated as a weighted sum of one or more of these attributes. The routing algorithm attempts to find the minimum cost path from the source to the destination. In the process of determining the minimum cost path from source to destination, the routing algorithm is run on each intermediate routing node so as to decide which interface should be used for sending the packet out of the router for each of the incoming packets received.
The routing algorithms can be categorized [1] on the basis of different criteria: location of routing decision, implementation of routing algorithm, adaptivity, minimality, and progressiveness of routing.
When a packet moves from source to destination in the network, it passes through a number of intermediate nodes. The sequence of intermediate nodes through which the packet will pass can either be predecided before transmission of the packet or can be decided during the transmission, and the decision can be taken by the source node or the intermediate node at which the packet has arrived [1]. The decision may even be taken by a central routing controller node, which dictates the path by which the packet should travel, as the controller node has the complete digital map of the network and thus can calculate the best path. Based on the various permutations of where the routing decision can be taken, the routing algorithms can be categorized, on the basis of location of routing decision, as distributed routing, source routing, hybrid routing, and centralized routing.
In distributed routing, when any intermediate routing node receives a packet from the source for sending towards the destination, the intermediate node decides on its own the next neighboring node to which the packet should be forwarded so as to enable the data packet to reach nearer to the destination. The source node also transmits the packet to its neighbor as decided by the routing algorithm running at the source node. In the case of a distributed algorithm, the packet should contain only the information about the destination address. A forwarding decision taken by a node may be based on the node’s awareness only of its nearest neighbors or its awareness about the partial or complete network. Generally, in order to decide the neighbor to which the packet should be forwarded by a node and thus placed in one of its links is not dependent on the routing done by previous nodes in the network through which the packet has passed, i.e. it is independent of the route followed up to that instance.
In source routing, the source node computes the entire path that the packet should take to reach its destination, and the information about this route is attached to the header of the packet. Any intermediate node receiving the packet decides on the next hop based on the route information available in the header of the packet. The source node may embed the entire route in the header of the packet. Each intermediate node after receiving the packet reads the header for the next‐hop information, deletes that portion of the header, and forwards it to the next intermediate node in the path. Such a form of source routing is known as strict source and record routing (SSRR). The other form of source routing is known as loose source and record routing (LSRR), where abstract path information in terms of one or more intermediate nodes is specified by the source through which the packet must travel to reach the destination. The LSRR is also loosely referred to as hybrid routing, as it is a combination of source routing and distributed routing because the source node precalculates information about some of the intermediate nodes and adds it to the header of the packet, while the exact path between these nodes is determined by the intermediate nodes using distributed routing.
Centralized routing is done by a network controller using a centralized database. The network controller has a complete view of the network and the topological changes therein, if any. However, centralized routing is less scalable than distributed routing and cannot be used for huge networks such as the Internet. Although it relieves the intermediate nodes from the burden of calculating the next hop, it also leads to slower detection of link failures and restoration of links as compared with a distributed network in which the immediate neighbor detects the failure at a much faster rate and thus can use an alternative route immediately.
Implementation of the routing algorithm can be based on a lookup table or a finite state machine. In the case of a lookup table, each routing node maintains a table, which assists the node to decide the interface through which the router should forward the packet for a particular destination. The table may be static or dynamic. Dynamic routing tables are regularly modified and updated on the basis of the changing network topology and condition, while static routing tables are stored in the routing nodes and are generally not changed on the basis of any ongoing changes in the topology or traffic pattern of the network. The routing algorithm can also be implemented using a finite state machine. The finite state machine can detect any flaw in the protocol or message sequence. The state machine can be divided into three parts – input state machine, selection state machine, and output state machine, connected sequentially and interacting with each other through the events triggered by each of them. The finite state routing machine may be in the idle state, connect state, active state, open state, or established state, depending on the exact protocol using the finite state machine for its implementation.
Routing algorithms vary in the process of adaptivity, i.e. their capability to determine a better path in the network. The ideal way to adaptivity is to select the best possible path between the source and the destination for every packet being transmitted. To achieve the best path routing, each node should have complete information about the network, which requires time to build, and good computational capability to find the best path from source to destination from the knowledge of the complete network. This can lead to computational delays and bandwidth consumption due to broadcast of routing information to neighbors. So as to determine the next‐hop node in a short time in a distributed manner at each node, the adaptivity of a routing algorithm [2] can be of the following types:
Oblivious routing algorithm. In these types of algorithm the set of routes for every source–destination pair is known to the routing node in advance. There may be a single or multiple routes between a source–destination pair. In the case of multiple routes, one of the routes is selected out of the possible routes randomly or in a cyclic order. The route information between the source–destination pair is available with the routing node before receiving the packet and the route determination does not take traffic into consideration for deciding the route. In the case of a continuous or burst of traffic between a particular source and destination pair, it avoids congestion as it forwards the packet by various available optimal routes from the set of available optimal routes between the source and the destination pair instead of the single optimum route. This process is known as ‘static load balancing’.
Deterministic routing algorithm. Deterministic routing is a special case of oblivious routing. In deterministic routing, the single ‘shortest path’ is generated between the source and the destination pair, and all the packets between the source–destination pair are transmitted by this path. The traffic information is not considered for path determination, and even if a number of optimal paths exist between the source–destination pair, only a unique path is selected among the optimal paths, based on the deterministic shortest path algorithm. Such algorithms are simple and fast with in‐order delivery of packets. The algorithm performs well in a network with uniform traffic and high reliability of links and nodes. In the case of failure of the node, the algorithm has to update its routing table and recalculate the shortest path between source–destination pairs. The routing also leads to delays in request–reply type of traffic, as the packets may use the same path.
Adaptive routing algorithm. The adaptive routing algorithm considers the network topology, its connectivity status, link status, and resource utilization before deciding the path between a source–destination pair. The connectivity status is based on factors such as path cost, edge cost, and congestion. The resource utilization and availability can be based on factors such as computational resource available with the nodes, buffer capacity of the nodes, and current available space in the buffer. The packets between a source–destination pair may be transmitted by different paths, depending on the condition of the network at that instance of time. Thus, the packets may reach the destination of an adaptive routing out of order.
The advantage of an adaptive routing is that it can adapt to conditions such as link or node failure at a much faster rate compared with oblivious routing. Adaptive routing may also have a congestion control mechanism, which may forward a packet by a path providing the best possible bandwidth at the instance of transmission. However, in adaptive routing, as the routing nodes have to calculate the best path for each packet in terms of distance as well as network condition, this may lead to delays in forwarding the packets by the routing nodes. It also consumes additional network bandwidth to share information between the routing nodes about the condition of the network. Adaptive routing is also known as ‘load‐based routing’. An ideal situation would be the load information of the entire network available at each node for calculation of the path, but this would be too computation intensive and data intensive, leading to delays. Thus, the routing nodes generally use neighborhood traffic information for local load balancing.
Based on the concept of minimizing the path from source to destination, termed ‘minimality’, the algorithms are classified into ‘greedy’ and ‘non‐greedy’ [1]. In greedy routing algorithms, the greedy approach is followed, i.e. at every intermediate node where the routing decision is made, the algorithm tries to bring the packet closer to the destination and also at that point in time the path already traversed by the packet would be one of the shortest paths between the source and the intermediate node. Deterministic and oblivious routing algorithms belong to this category of routing, which is also referred to as minimal, direct, shortest‐path, or profitable routing.
In the non‐greedy routing approach, the routing algorithm may take a decision to forward the packet on a path that may lead to taking the packet away from the destination for that routing decision, leading to an increase in the path length or cost. Such decisions may be taken by the intermediate node to perform load balancing of the network or to avoid sending the packet on a congested link, which will lead to further delays and congestion. Forwarding the packet to a region away from the destination may lead to a faster delivery from the intermediate node to the destination through the detour, as the detour route may be congestion free with a higher bandwidth. For these reasons, the non‐greedy approach of routing is also referred to as non‐minimal, indirect, non‐profitable, or optimistic routing or ‘misrouting’.
The routing algorithms can be classified, on the basis of their progressiveness, as ‘progressive routing algorithms’ and ‘backtracking routing algorithms’ [3, 4]. The progressive routing algorithm searches for the next‐hop node as a step towards the destination. The next‐hop intermediate node may be nearer to the destination, as in the case of a greedy algorithm, or relatively farther from the destination node, as in case of a non‐greedy algorithm. With an adaptive protocol, the progressive routing algorithm moves the packet to the next non‐faulty profitable link on the shortest path, or detours it in a non‐greedy protocol. With each execution of the progressive algorithm, the path traversed, the number of intermediate nodes visited, and the associated cost increase. Greedy algorithms and deterministic routing algorithms are always progressive.
A backtracking routing protocol calculates the next‐hop path on the basis of the information of the network available with it. In the case of congested links or failure of links, the routing algorithm may backtrack for further connectivity. The backtracking algorithm also ensures that a path is traversed only once, and it helps to avoid loops and deadlocks. So as to support backtracking, the history of the path traversed by the packet has to be stored, which leads to storage requirement and message overheads for intimating about the path traversed. A backtracking routing algorithm is suitable for a network with various types of fault and frequent failures, and is used in fault‐tolerant routing.
The routing algorithms have also been classified into three generations [5] based on the stages through which it has evolved in ARPANET. The first‐generation routing algorithms were the distributed adaptive algorithms, which evolved in 1969 as a version of the Bellman–Ford algorithm. To overcome the shortcomings of the first‐generation algorithms, such as non‐consideration of line speed, low accuracy, slow response to congestion, and increase in delay, the second generation of algorithms was adopted in 1979. The second‐generation algorithms were also distributed adaptive algorithms, but they used time stamping to calculate delay in the network, which was also the new criterion to decide the route. Dijkstra’s algorithm was used to compute the routing tables. However, algorithms based on link delays led to problems of swing in routed links, as all the nodes avoided the congested links and forwarded the packets to the least congested link at any instance of time, leading to congestion in the link and a slow decongestion of the prior link, which again prompted the router to swing back from the recently congested link to the recently decongested link. To overcome this problem, the third‐generation routing algorithms introduced in 1987 are based on an attempt to search for an average route to the destination rather than the best route for all destinations, as was the case with the second‐generation algorithms. This helped to dampen the routing swings and reduce the routing overheads.
2.2 Routing Strategies
A packet‐switched network is based on delivery of data packets from the source to the destination through certain routing nodes forming the route in the intermediate network. At any point in time, one or more than one route may exist between the particular source and destination, among which one is selected for packet forwarding based on a routing function. The routing function should generally possess the following characteristics [5]:
Correctness. The function should be able to determine an optimum path between the source and the destination. The destination should not be treated as unreachable if a path exists to it. In a similar manner, it should be able to route the packet to the destination and not land in an infinite loop making the destination unreachable or increasing the network congestion.
Simplicity. The function should be simple to implement. This will ensure its correctness during implementation. A simple function will lead to less computational overhead. In the case of a distributed routing decision, the function will be running at all the intermediate routing nodes. If the function is not simple and calls for extensive computation, it will lead to computational delay of the packet at each intermediate node.
Robustness. The routing function should be able to deliver the packet to the destination even in the case of link failure or congestion. It should attempt to route the packets by an alternative route without packet drop or looping in the case of a packet switching network. In the case of circuit‐switched networks, the function should be robust enough to continue routing without breaking the virtual circuit.
Stability. The function should lead to a stable routing strategy and not have frequent changes in routes. If a routing function detects link congestion, it attempts to route all the packets by some alternative route, leading to decongestion of the previous route and hence reducing the cost of packet forwarding by the previous route if congestion is a parameter in route cost. So, the function will again try to route back the packet through that ‘now decongested’ link and change the routing path. A similar situation may arise if a link frequently fails and comes up immediately thereafter. This leads to instability in routing in the case of frequent route change and may lead to looping up of packets in traversal. A routing function should attempt to increase the stability but at the same time maintain robustness of the algorithm at an optimum level.
Fairness. The fairness of the routing function should ensure that no node should ‘starve’ of bandwidth allocation for the transmission of its packets. It should attempt to provide the maximum possible bandwidth for each node. The packets with nearby source–destination should have equal probability to packets with far source–destination with a number of intermediate hops. The bandwidth of the intermediate path should also not act as a deterrent to avoid transmission between certain source–destination pairs to maintain a minimum cost or maximum throughput [6]. Fairness is generally considered to be contradictory to optimality.
Optimality. A routing function should optimize the parameters that measure the routing efficiency of a network. The function should be optimum in terms of minimum packet delay, maximum network throughput, and minimum number of hops that a packet has to traverse between source and destination. However, optimality may go against fairness in its attempt to maximize or minimize a parameter. By the optimality principle, a source–destination pair with fewer intermediate hops would be preferred to a pair with large intermediate hops, as the former would indicate better performance because the packet transmission was successful with a fewer number of total hops.
Efficiency. Each routing function adds some computational overhead as well as transmission overhead to the routing protocol. The computational overhead is caused by processing requirements in the routing nodes. The router has to decide on the next hop to forward the packet, based on certain parameters. These parameters should be calculated either once after a certain period or in real time, depending on the protocol requirement. In a similar manner, the routing function requires the routing nodes to communicate among each other or with the source or the network controller to have details about the network or the path by which the data packet should be forwarded. All these communications are done through the exchange of information across the network, which leads to network overheads associated with routing. Although a routing function should be stable and robust, at the same time these factors should be optimized with the efficiency of the routing function also in terms of communication and computational overheads.
Adaptivity. The routing function should be aware of the nodes and the paths. From the knowledge of the paths to each node, it should be aware of the redundant or alternative paths between any two nodes. With this awareness, the routing function should be able to reroute the packets by the redundant path in the case of link or node failure. It should also be able to reroute packets by another path if congestion arises in the existing path or regions. Still, the path by which the packet has been rerouted should be an optimum path at that instance of time.
Fault tolerance. The nodes or links may fail in a network. In typical networks, there can even be misbehaving nodes and faulty nodes, which may randomly perform in an improper or a faulty manner. The failed nodes and links may remain as such or recover with time. To continue routing packets in such a scenario, there should be alternative paths between source and destination, of which the best path is selected at that instance of time. Fault tolerance enhances the ‘reliability and performance’ of a network routing. The fault tolerance feature of the network may comprise one or more of the following features – fault detection, fault diagnosis, and fault accommodation. The fault detection feature is of prime importance in fault tolerance, as it leads to knowledge of the existence of a fault in the network and triggers fault diagnosis or fault accommodation. A fault can be detected in a network by various methods, such as periodic exchange of information between neighbors about the active links and system check of the entire network by each node independently. Fault diagnosis is a more complex process than fault detection, as it has computational, storage, and resource overheads, and thus fault detection and fault accommodation [7, 8] are preferred until the network deteriorates to a minimum threshold.
Deadlock freedom. The routing function should be deadlock free with minimum delay and maximum throughput, even in a huge network with changing topology and frequent faults. The routing function has to optimize between routing performance and deadlock avoidance [9, 10]. Distributive adaptive routing is prone to deadlocks, as the routing node decides on the path by which a packet should be forwarded based on the local condition of the network without global awareness of the network. This may lead to forwarding of the packet in a loop. Adaptive routing with deadlock avoidance therefore either removes the cyclic dependency in the channel dependency graph or introduces an escape path in the channel.
The routing strategy is generally based on parameters such as knowledge of the network topology, type and status of the intermediate links in the network, congestion, time delays being faced in the network, and the data load. Still, there are routing strategies that do not require any information about the network and can successfully route the packets to the destination by flooding or some other routing strategies. In the case of a centralized route controller, it receives knowledge of the network from each node in the network. However, in the case of a distributed routing scenario, various options are possible. In the case of distributed routing, each routing node may use the information locally available to it, i.e. the information related to the links directly connected to it to forward the packet to the appropriate link. Alternatively, the node may obtain information from its immediate neighbor and also gain information about all the links connected to its neighbor, and this adds to its knowledge of the link status and congestion in all the links associated with its neighbors. Still further, each routing node may exchange information related to its link to the nodes beyond its immediate neighbor. This may finally lead to a complete or a partially complete knowledge of the network topology and affect the routing decision.
The routing strategy also governs the frequency of updates received by the node to decide on the routing path. In the case of fixed routing, in which a path is predecided between the source and the destination, it does not require any update on the status of the network from any node in it. Similarly, if the routing is based on flooding, it does not require any knowledge about the network. In the case of distributed routing, where each node uses the knowledge available with it, i.e. the information of the links directly connected to it, it gets information on a real‐time basis and is always updated. In the case of distributed routing, where the routing nodes receive information from neighboring nodes or other nodes of the network, the routing strategy governs the frequency of updates that a node should receive from the other routing nodes. Adaptive routing, in which the routing path is decided on the basis of the network condition, is entirely dependent on the route updates received by the routing nodes.
Routing Metrics
A metric is a value assigned to each route by the routers for comparing the routes and finding the best among the routes. Different routing protocols use different, and sometimes multiple (hybrid) metrics: RIP uses hop count, IGRP and EIGRP use bandwidth, delay, load, and reliability, and IS‐IS and OSPF use cost and bandwidth. If there are multiple routes to the same network, cost is used for finding the shortest or the best path. Common metrics [11] used in routing protocols are:
Hop count. This is a metric that specifies the number of hops a packet must take on its route from the source to the destination.
Reliability. This is a metric defining the dependability of each network link. Some network links are more prone to errors than others, and certain links might be repaired more quickly than other links. It is usually described in terms of bit error rate or may be calculated on the basis of previous failures, leading to assigning a probability of non‐interrupted operation on each link.
Routing delay. This is the time taken for the packet to reach from source to destination. Delay can be calculated on the basis of a number of factors, such as bandwidth, router latency, queues at each router, and congestion in the network.
Load. This is a measure of the amount of traffic on the path. A heavily loaded path has busy routers. The load on a network depends on the CPU utilization and the number of packets processed. It is a dynamically changing metric. The path with the lowest load is preferred.
Bandwidth. The throughput of a network is directly proportional to the bandwidth offered by the links, if the network is not loaded. Routes with higher bandwidth are preferred.
Cost. This metric is defined by the network administrator to give preference to certain routes over others. Cost may be defined by any policy of the service provider or may depend on one of the above metrics or a hybrid of them.
2.2.1 Non‐Adaptive Algorithms
A non‐adaptive routing algorithm uses a static table to decide the route a packet should take to reach the destination. In the case of a source routing, the partial or entire route might be decided by the source node before transmission of the packet, while in distributed routing each intermediate node will decide on the next hop to forward the packet, based on the static routing table accessible to the intermediate node. Static routing is also known as ‘directory routing’, as it searches the fixed table or directory for the destination address and gets the next link from the directory. In the routing directory of any node, each destination address or a group of destination addresses are generally mapped to a unique link on the router to inform the router to forward the packet through that link. The route is determined on the basis only of the current location of the packet in the network and its intended destination. The decision regarding the route is independent of the network condition. The packet takes the same route every time if it has to go from a particular node to a destination.
When a node or a link fails in static routing, the packets forwarded to travel by that route as per the static route entries of the intermediate routers have to wait in the buffer of the intermediate nodes until the route is repaired, or the packet will be dropped in the case of limited buffer capacity or timeout. In the case of failure of any link or node in the network, the entries in the static routing table have to be deleted, added, or modified manually, which leads to delays and enhanced administrative cost. Modifying a static routing table may be possible for small networks, but making such changes for huge networks with complex topologies is generally not feasible as it leads to errors and delays.
Non‐adaptive routing is simple to implement and performs well in networks with consistent topology and traffic. The static routing table is available to the routing node at the time of boot‐up. The performance of non‐adaptive routing is poor in the case of node or link failures, as the routing is unable to decide on alternative routes. The performance also deteriorates in the case of drastic changes in the traffic volume, because a burst of traffic in one of the links may lead to traffic congestion and all the packets intending to use the path have to wait even though an alternative free path might exist. In order to find the shortest path, non‐adaptive routing creates a spanning tree from its knowledge of the entire network to decide the optimum path. Each link and node can also be assigned weights before calculating the shortest path.
Although flooding is also sometimes referred to as non‐adaptive routing, it is generally studied as a separate class of routing from non‐adaptive and adaptive routing. Still, non‐adaptive routing may be classified into two categories – flooding and random walk. Flooding can be described as a kind of non‐adaptive routing that uses sequence number, hop count, or the spanning tree to avoid looping or forwarding of similar copies of the packet. Random walk is used in a robust network with a high degree of connectivity. The packet is forwarded randomly to any of the neighboring nodes and the process is continued until the packet reaches the destination. Multipath routing may also be used which has high reliability, as multiple routes are possible from source to destination and the packet is expected to reach the destination by one of the alternative routes even if there are link failures or congestion in other routes.
2.2.2 Adaptive Algorithms
The adaptive routing technique is most commonly used in various routing algorithms for packet‐switched networks. The technique helps to locate an alternative route if the routing node detects that it has become difficult, owing to changed network conditions, to route the packet by the previously calculated path. The two factors that lead to the requirement of an alternative path are link failure and link congestion. As the technique adapts to changing network conditions, it is referred to as the adaptive algorithm.
So as to enable the network to adapt to changing network conditions, the basic requirement is information about the state of the network at all times. In the case of distributed routing, knowledge of the network is possessed by each routing node, while in the case of centralized routing it is possessed by the central network controller. If knowledge of the network is required on a real‐time basis, there has to be a continuous exchange of packets between the nodes in distributed routing and between the nodes and the network controller in centralized routing. Real‐time knowledge of the network helps to make better routing decisions, but it leads to a high exchange of information related to packets through the network and computation by the nodes. So, it is computation as well as communication intensive. In order to avoid extensive computation and communication requirements, the information is exchanged after an optimum time period so as to keep the communication and computation requirements at an optimum level and achieve a tradeoff between freshness of the information and computation and communication overheads. Another disadvantage of near‐real‐time network knowledge with the nodes is that it leads to instability of the network, as it results in frequent path changes. As soon as a routing node detects congestion in a link, it starts forwarding the packets through the relatively less congested links. This leads to congestion of the later link and decongestion of the previous link. This information would again affect the routing pattern of the node, as it will now change its packet forwarding to the initial link, which has now been decongested. Such swings lead to unstable routing and to packet loops and losses.
2.2.3 Flooding
Flooding is a routing technique in which all the routing nodes participate in routing of all the packets, irrespective of source and destination. The routing nodes neither require any information about the network topology nor share link information with their neighbors or any other node in the network. As there is no exchange of routing information, this does not lead to communication overhead. Still, this routing technique has maximum utilization of the network resources, as it floods the network with data packets. The technique uses a wave‐like transmission of data packets from source towards destination across all links. The source node sends the packet across all its interfaces to its neighbors. Each neighbor, on receiving the data packet, forwards it on to all the links except the one from which it has received the data packet. Thereafter, each intermediate node, on receipt of a data packet that is not destined for it, forwards it on to all its interfaces except the one through which it has received the data packets. For example, in Figure 2.1, if node D wants to transmit a data packet to node F, then node D sends the packet to nodes A, B, C, and E, which are its neighbors. On receiving the packet, node A forwards it to nodes B and C, as they are its neighbors, but does not send the packet to node D, as it received the packet from node D; node B forwards it to nodes A and E; node C forwards it to node A; node E forwards it to nodes B and F, and again a similar forwarding starts from each node receiving a data packet not destined for it. Thus, node F receives the packet, but even now many packets destined for it are still in transit and will keep on reaching it subsequently.
Figure 2.1 Sample network to demonstrate flooding.
To avoid receiving multiple packets at the destination and processing each of them, each node should only accept the first data packet received by it and then discard all subsequent packets received by it from other nodes. This can be achieved by attaching a unique packet identifier to each packet. As there is no central node to generate the unique identifier in the routing, the identifier is generated by the source node using a combination of the source node ID and a sequence number being maintained by it. In the case of a virtual circuit, the node identifier is generated at the source from the circuit ID and a sequence number.
In the routing technique based on flooding, multiple copies of the data packet are made by each routing node and are transmitted in the network. Each intermediate node receives one data packet from its neighbor, but transmits (n − 1) (where n is the number of neighbors of the routing node) data packets corresponding to the received data packet. This leads to the creation of a huge number of duplicate data packets moving in the network and can lead to congestion if not controlled. There are two commonly used mechanisms by which the infinite replication and transmission of packets are controlled in flooding. In the first method, each routing node maintains a list of unique packets, based on its packet identifier, forwarded by it to its neighbors. If the node receives a packet from any of its neighbors, it checks for the packet identifier in the list of packet identifiers already forwarded by it to its neighbors. If the identifier of the packet received by it matches any of the identifiers in the list, the data packet is immediately dropped or else it is forwarded to all its neighbors and an entry of it is made in the list of packets already forwarded by the node. Thus, by this technique each node forwards the packets only once along all its links. This reduces the looping of data packets as well as an uncontrolled replication of the data packets.
Another mechanism to prevent explosive increase in the number of data packets and looping of these packets is based on a hop counter. The hop count is set to a predefined value to ensure assured delivery of at least one copy of the data packet from source to destination. The diameter of the network is one such parameter to help to decide the maximum value of the hop count. In a network, the diameter is calculated by taking into account all the minimum hop counts among all the source destination pairs. The maximum value of all the minimum hop counts is known as the diameter of the network. It indicates the number of hops that would be sufficient to reach from any node in the network (source) to any other node in the network (destination) if an optimum path is taken. A hop counter is selected in the flooding technique, the value of which is set to the diameter of the network. The source adds the hop count to the packet before flooding it in the network.
Each routing node that receives the packet checks the value of the hop counter. If the value of the hop counter is 0 and the packet is not destined for it, it drops the packet or else it decrements the hop counter by one and transmits the packet to all other links. This technique ensures that the destination will definitely receive at least one data packet from the source node even if the source and destination may be the farthest separated nodes in the network. At the same time, the technique ensures that all data packets are discarded after a predefined number of hops in the network. Thus, it will stop indefinite loops as well as reduce congestion by regularly dropping packets after they reach end of life based on hop count.
The major disadvantage of flooding is the large number of data packets generated by a node running the flooding algorithm. This leads to congestion of the network. Each routing node receiving the packet has to put in computational resources for checking whether the packet is destined for it or else replicate and forward the packet to the other links. It also involves processing the packet to reduce the hop count if the technique uses the latter. The technique has computation and memory requirements to check the packet identifier and maintain the list of packet identifiers forwarded by it if applicable. The amount of generated packets increases with increase in the size of the network in terms of intermediate routing nodes or links. Thus, the congestion increases with increase in the size of the network. However, there are a few critical applications of the flooding technique that make it highly useful, robust, and reliable. Some of the advantages of the routing technique using flooding are:
Reliable delivery. The technique is very robust as it forwards the packets from source to destination by every possible route between them. Thus, even if some links are disconnected or blocked by congestion, the packet is assured to be forwarded through at least some other links. This makes it a useful protocol in critical networks like those in defense or emergency applications, which require a high reliability and robustness even if a major portion of the network in damaged or captured. An associated drawback would be that, if a portion of the network is compromised, the adversary will receive all the data packets, as every routing node receives all the data packets being transmitted through the network.
Discover best route. The technique can be used to determine the minimum hop route between the source and destination and can be used as a precursor of a fixed or adaptive routing or to establish a virtual circuit after determination of the shortest route using flooding. As the packets are replicated and forwarded through all the intermediate nodes, at least one of the packets will be the first to reach the destination. The route of this packet, first to reach the destination, can be traced back to find the minimum hop route.
Widespread communication. The technique generates a wave of data packet transmission from source in such a manner that it crosses all the routing nodes in the network. Thus, in a way it communicates with all the nodes through these packets, and this can be used to transmit various routing control information among the nodes. Flooding is used in a few routing protocols to share with all other nodes in the network the information about the links connected to a node. On receiving this information from all the other nodes in a network, every node is able to gain complete knowledge about the topology of the entire network and can thereafter decide on the least‐cost route for forwarding the data packets.
2.3 Static Shortest Path Routing Algorithms
The routing table entries are made manually in static routing. The administrator should have a detailed understanding of the network, discover the routes with respect to each router, and then enter them in the individual routers. The entries made in the static routing tables by non‐automated means are known as ‘static routes’. In static routing, the routers do not communicate with each other for exchange of network status, thus making them ‘blind’ about the changes in the network. A router, whenever it receives a packet, consults the routing table to get the next‐hop address and forwards it on to the exit link of the next‐hop address without any consideration for traffic, congestion, or link failure beyond the next hop [12, 13]. As static routing does not change its routing pattern based on the existing network environment, it is also referred to as ‘non‐adaptive routing’.
Static routing is one of the simplest routing techniques and has minimal overheads in terms of processing power, memory, and bandwidth. However, it is not suitable for networks with inconsistent traffic pattern or bursty traffic as the protocol cannot adjust to the network environment. The routing lacks any central controller as well as an information‐sharing mechanism between the nodes, making it impossible to implement any fault detection techniques in the protocol. As there is no automated fault rectification mechanism, the emergence of any fault cannot be detected by the system, and performance deteriorates.
A static routing protocol comprises a routing table and a routing algorithm. The routing table is also referred to as the routing information base (RIB). The common parameters that are entered in a routing table are the IP address of the destination network along with its subnet mask or the network ID, the next‐hop address or exit interface, and the administrative distance. The next‐hop address is the IP address of the next router in the network to which the packet should be forwarded so as to enable the packet to reach the destination. Alternatively, the interface of the router to which the next‐hop router is connected can be mentioned so as to enable the router to forward the packet to the next‐hop router through this interface. The administrative distance is used to assign weight, which is generally 0 for a directly connected next‐hop router or 1 otherwise. Default routing is used to send the packets having destination addresses for which a corresponding entry is not available in the routing table. Default routing can be done on stub networks, i.e. those having only one exit route.
Based on the principle of optimality, the routing algorithm decides the exit route for an incoming packet. A routing algorithm builds the sink tree for the router and uses it to discover the shortest path. Sink trees are built by deciding optimal routes from a tree rooted at destination. In a static shortest path routing algorithm, to send a packet from one node to another, we find the shortest path between the pair of nodes. This decision of determining the shortest path is based on the routing algorithm. One algorithm that is mainly used for this purpose is Dijkstra’s algorithm.
Static routing has its associated advantages and disadvantages. The advantages of static shortest path routing are as follows:
As the router is already informed of the routes at the time of booting, the router has no computational requirement for calculating routes, which leads to minimal CPU processing.
As there is no exchange of information related to the neighboring links and nodes between the routing nodes, there is no messaging overhead.
Static shortest path routing adds a layer of security to the network, as any malicious router coming into the network will not get any network traffic because there are no routes mentioned for it in the static routing tables of the existing routers. Besides, the administrator also has the control to forward traffic by a desired route and to certain networks only on the basis of the security policy, if any.
Static routing can be used to incorporate very complex routing policies on a relatively small network that cannot otherwise be implemented using a standard dynamic routing protocol.
Static routing is easy to configure and understand. The administrator can easily analyze the path being followed by a data packet on the basis of static routing.
Static routing is suitable for low‐capacity WAN links or links based on dial‐up connectivity, where the cost of the link is based on the time the link remains connected. It is suitable as it avoids regular exchange of routing information between nodes. A WAN link based on dial‐up connectivity configured with dynamic routing protocol may end up paying for link connectivity for a major part of the day just for regular exchange of routing information among the routers, but may be transmitting data only once throughout the day.
Default routes can be configured to forward the packet towards a network even when a specific route is not available to the destination.
The disadvantages of the static routing are as follows:
The administrator should have detailed knowledge of the network topology, links, and bandwidth. This will be guiding the entire routing based on the configurations made in the routing table.
The configuration and administration is time consuming. If a router, link, or network is added to or deleted from the network, or in the case of failure of the link or failure of the routing node, corresponding entries have to be added, deleted, or modified manually by the administrator.
Configuration is error prone because any fault in understanding the network or entering wrong entries may make a portion of the network unreachable. Configuration errors can also lead to flooding and congestion or send the packet in loops.
Owing to manual management of the routing table, it becomes impossible to manage the routing table in static mode for huge networks and inconsistent links. Thus, static routing does not scale well with the growing size of the network and makes maintenance cumbersome.
With static routing, configuring huge networks and networks with redundant links is difficult.
In static routing, adaptation to changes in the network topology, link failures, and network scalability can neither be in near‐real time nor in a dynamic manner.
Dijkstra’s Algorithm
The algorithm was proposed by the Dutch computer scientist Edsger Dijkstra. The algorithm gives the single‐source shortest path in a graph with non‐negative edge cost. The algorithm creates a sink tree to give the shortest path from a node to every other node. The step‐by‐step working of Dijkstra’s algorithm is given below:
Mark all nodes as UNVISITED. Set the start node as ACTIVE.
At the beginning of the algorithm, every node is assigned a ‘distance value’, which represents the distance of the node from the start node. Therefore, the distance value is set to zero for the start node and is set to infinity for all other nodes.
For the ACTIVE node, all its unvisited neighbors are considered and their distance from the start node is calculated. If this distance is less than the previously recorded distance (infinity in the beginning), the distance value is changed to the new, lesser value.
When all the neighbors of the ACTIVE node have been considered, they are marked as VISITED. The distance value of a VISITED node is final and minimal.
If all nodes have been VISITED, the algorithm stops. Otherwise, the UNVISITED node with the smallest distance from the start node is set as the next ACTIVE node and the algorithm is continued from step 3.
The step‐by‐step working of the algorithm can be explained on the basis of the graph shown in Figure 2.2:
Starting from the source, node A, it has three neighbors and thus three possible options to choose from – nodes 2, 3, or 6, but the neighbor with the minimum distance is node 2 with distance 8. Therefore, it is chosen, but at the same time values of 8, 10, and 15 are assigned to the three neighbors.
Next, node 2 is chosen from the queue because it has the smallest assigned value as of now. Now node 2 has four neighbors – nodes 1, 3, 4, and 7. Node 1 has already been covered, and among nodes 3, 4, and 7 the distance values are min(10, 8 + 11) for node 3, min(infinity, 8 + 16) for node 4, and min(infinity, 8 + 17) for node 7. Therefore, node 3 is chosen and is assigned the value 10.
Next, node 3 is chosen from the queue because it has the smallest assigned value as of now of the vertices left in the queue. Now node 3 has two neighbors – nodes 6 and 4. The values assigned to them are min (10 + 3, 15) for node 6 and min (10 + 12, 24) for node 4. Therefore, node 6 is chosen and is assigned a value 13.
Next, the neighbors of nodes 6 are nodes 5 and 3, out of which node 5 is chosen and assigned a value 23 on a similar basis.
Figure 2.2 A graph to explain Dijkstra’s algorithm.
Thus, we are able to find the shortest distance between nodes A and B on the basis of this algorithm.
2.4 Dynamic Shortest Path Routing Algorithms
Dynamic routing consists of two components: the routing protocol and the routing algorithm. The routing protocol is used for exchange of information among the routers about their current network status, and the routing algorithm is used for calculating the shortest path. The protocol allows continuous changes in routing decision to account for the current traffic and changing topologies. It allows routers to be continuously aware of the status of the remote networks and automatically add this knowledge to their routing tables, and allows the routing to act intelligently by avoiding network failures and congestion. In dynamic protocols, the routers exchange information whenever there is a failure or change in topologies. The routers are thus able to learn new and alternative routes and modify the shortest path in their routing tables after recalculations based on the latest network scenario. Thus, dynamic routing is more robust than static routing. Static routing allows routing tables in routers to be set up in a static manner where network routes for packets are preset. If a router on the route goes down, the destination becomes unreachable. In such cases, dynamic routing allows routing tables in the routers to change so as to enable the best alternative route available at any instance of time to be chosen as the possible routes change. Thus, the major activities and components [14] of a dynamic routing protocol are:
Having a method to discover other routers in the network.
Exchanging routing messages and maintaining up‐to‐date routing information about all other routers.
Determining optimal routes based on the information the router has, and recording this information in a route table.
Reacting to changing topologies and finding a new path if the current path fails.
The dynamic routing protocols have also been differentiated on the basis of various characteristics. The protocols have been classified [14] and described as:
classful or classless protocols
Interior Gateway or Exterior Gateway Protocol
Distance Vector or Link State Routing Protocol
Classful vs Classless Routing Protocols
Classful routing protocols were used when network addresses were allocated on the basis of classes. In classful routing, the subnet masks are not sent in the periodic messages generated by the dynamic routing protocols as the subnets are predefined on the basis of the network address. Classful routing protocols exchange routes with subnetworks within the same network if the network administrator has configured all the subnetworks in the major network with the same routing mask. Examples of classful routing are Routing Information Protocol version 1 (RIPv1) and Interior Gateway Routing Protocol (IGRP). When routes are exchanged with foreign networks, subnetwork information from this network cannot be included because the subnet mask of the other network is not known. Classful routing protocols cannot be used when a network is subnetted using different subnet masks, i.e. classful routing protocols do not support variable‐length subnet masks (VLSM), and thus IPv4 address utilization is poor.
The present‐day networks are based on Classless Interdomain Routing (CIDR), a newer scheme of IPv4 addressing. In CIDR, the subnet mask cannot be determined from the network address. Classless routing protocols support CIDR. The protocol includes the subnet mask with the network address in routing updates. Classless routing protocols support VLSM and discontinuous networks and have better IPv4 address utilization. Some of the common classless routing protocols are RIP (v2, v3, v4), EIGRP, OSPF, IS‐IS, and BGPv4.
Interior Gateway Protocol vs Exterior Gateway Protocol
Interior Gateway Protocols are used within a single autonomous system or a routing domain, which may comprise individual networks. They are used for networks under a single network administration. Each individual network also uses an IGP for shortest path determination within its own routing domains. As shown in Figure 2.3, IGPs can be further classified into distance vector and link state protocols. A major difference between distance vector and link state protocols is that routing information is stored in table form for distance vector routing and in a graph or database form for link state routing. The common Interior Gateway routing protocols are RIP, IGRP, EIGRP, OSPF, and IS‐IS.
Exterior Gateway Protocols are used among different autonomous systems having independent administrative entities. EGPs do not always search for the shortest or the cheapest path between autonomous systems. EGPs propagate ‘reachability indications’ in terms of many different attributes to measure routes and not the true metrics. The routing table contains a list of known routers, the addresses they can reach, and the metric, called the ‘distance’, associated with the path to each router. The best available route is chosen depending on this distance. A router exchanges ‘Hello’ and ‘I heard you’ messages with another router to establish a connection to enable exchange of routing information. Each router then polls its neighbor at periodic intervals, and the neighbor responds by sending its complete routing table. A path vector protocol, Border Gateway Protocol (BGP), is the typically used EGP.
Distance Vector vs Link State Routing Protocols
Distance vector routing protocols such as Bellman–Ford or Ford–Fulkerson were among the earliest dynamic routing protocols. The name ‘distance vector’ is used because the routers exchange vectors containing distance and direction information. Distance is defined in terms of a simple metric such as hop count, load, delay, bandwidth, and reliability, or a complex metric derived from a combination of the simple metrics. Direction is the next‐hop intermediate neighbor router or exit interface. The basic operating features in distance vector routing protocol are:
Routers only know their immediate neighbors and the distance or cost to reach them.
Periodically, this information is sent to all connected neighbors.
The neighboring routers compare this information with the already known information and make changes if any shorter routes are available.
After all the routers have exchanged their vectors, each router will have the best distance to each destination.
Distance vector routing protocols have a slow convergence, and hence they are used in simple and flat networks where convergence time is not a concern. A few examples of distance vector routing protocols are RIP, IGRP, and EIGRP.
Link state routing protocols are also known as shortest path first or distributed database protocols. In link state routing, each routing node makes a connectivity graph for the nodes in the network and independently calculates its shortest path to every other destination in the network. The information about the shortest paths is stored in the respective routing tables. Link state routing works best for hierarchical routing design and in networks where fast convergence is crucial. Examples of link state routing protocols are OSPF and IS‐IS. The basic operations [15] in link state routing protocols are:
Each node discovers all the neighboring nodes.
Each router thereafter generates information about itself, its directly connected links along with their state, and any directly connected neighbors.
This message is then flooded throughout the network, and each router uses this information.
The link state database thus generated at each router is used by Dijkstra’s algorithm to compute a graph of the network indicating the shortest path to each router.
Whenever there is a link failure or change in topology, link state messages are recomputed by the connected node and then flooded throughout the network.
Dynamic routing has its associated advantages and disadvantages [14]. The advantages of dynamic routing are as follows:
As the entries in the routing table are automated with protocol for discovery of nodes and links, a dynamically routed network is scalable and does not pose any problem if it grows quickly.
The protocol has a high degree of adaptability and it incorporates necessary changes in the routing path to adapt dynamically to variation in network topology with time.
Configuration complexity is independent of the network size.
Addition and deletion of nodes is easier for the administrator as it is not to be done manually as in static routing, but is taken care of by the protocol itself.
The protocol has the ability to perform load balance between multiple links.
Routing nodes can determine alternative paths in the case of failure of links or nodes.
The disadvantages of dynamic routing are as follows:
Routing information updates are exchanged between routers, which consumes a lot of bandwidth.
These protocols require more memory in the routing nodes to store their own view of the network.
The protocols put a greater load on the CPU for route determination compared with the static routing algorithm.
The route that a packet will follow cannot be known a priori. The decision concerning the shortest route is not in the hands of the network administrator as it is decided by the protocol.
The administrator should have advanced knowledge about configuration, verification, and troubleshooting.
2.5 Stochastic Routing Algorithms
In static routing, the static routing table defines the hop‐by‐hop path to be followed by a packet for a particular source–destination path. In the case of link or node failure in the path, no other alternative link can be used. As the routing is not aware of the environment of the network based on traffic, alternative routes cannot be detected even in the case of congestion. A deviation from this is dynamic routing, in which the router is aware of the network environment, link and node status, latency, bandwidth, and congestion in the network. Based on one or more of these parameters, the algorithm can route its packet by alternative routes. However, in the case of a particular link going down and coming up frequently or regular congestion and decongestion along a particular route, the algorithm leads to swings in the routing pattern. However, in both cases, static as well as dynamic routing, the packets are forwarded from source to destination only by one route, which is discovered to be the best or the shortest possible route even though there may be many other alternative routes.
These routes may not be the shortest possible route at a particular instance of time, but these might be optimal routes between the source–destination pair. The throughput of a network will increase if the packets are forwarded by all available routes on a weighted approach, i.e. more packets are forwarded by the least‐cost route and fewer packets are forwarded by the optimum‐cost routes. The route with maximum bandwidth can be used to pump in the maximum number of packets from source to destination, but at the same time the other underutilized routes between the routing node and the destination can also be used to pump in packets from the node to the destination in proportion to their bandwidth so as to reduce the overall latency of message transmission between the source–destination pair by using multiple routes.
There are several techniques for distributing the next‐hop packet into various available routes for load balancing. The simplest approach is to forward the packets by all the available routes to the destination in a round robin fashion. Alternatively, they can be forwarded in proportion to the transmission cost. However, in both cases, the routing decision is based only on the destination node and is not dependent on the source node or on the intermediate routers through which the packet has already travelled. Such a source‐invariant approach of distributing packets over a set of multiple routes has been called ‘multipath datagram routing’.
An alternative approach to multipath datagram routing is ‘per flow routing’, which also performs dynamic load balancing by routing all the packets of the same flow on the same route. Multipath datagram routing takes a decision on a per‐packet basis, and thus the packets may reach the destination out of order, while the ‘flow’ reaches the destination in order, saving the time of reassembly. Alternative routes may be selected for different flows from the routing node to the same destination. The algorithm requires regular monitoring of loads on all ports for efficient load balancing of flows using near‐equal paths based on near‐equal cost. Flow routing also leads to faster error recovery, as all the alternative routes from a node to the destination are determined before distribution of flow, and thus any link failure will lead to rerouting of the flow through an alternative route that the node is already aware of. The other major characteristics of flow routing are guaranteed bandwidth, guaranteed flow group, maximum rate traffic, TCP fairness, and high trunk utilization.
In stochastic routing [16], for any particular destination, each routing node may forward the packet to any of its neighboring nodes on the basis of a probability distribution maintained by the node. When a router receives a packet for a specific destination, it forwards the packet to any of the neighboring nodes on the basis of the probability distribution function for the destination node. Thus, all the outgoing links may receive the packets for the same destination from an intermediate node on a proportional basis. Stochastic routing is a destination‐based routing scheme. As it randomly forwards packets to different neighbors, the forwarded packet may end up in a loop. Looping of the packet in stochastic routing can be avoided by adding the information of all the visited nodes in the header of the packet, which increases the packet size as well as the processing overhead of the packet. An alternative to ensure loop freedom is to assign cost to the neighboring nodes in such a manner that only a restricted set of neighbors can be used to route the packet for a particular destination.
3 J. Duato, S. Yalamanchili, and N. Lionel. Interconnection Networks: An Engineering Approach. Morgan Kaufmann Publishers Inc., 2002.
4 M. Tsai and S. Wang. A fully adaptive routing algorithm for dynamically injured hypercubes, meshes and tori. IEEE Transactions on Parallel and Distributed Systems, 9(2):163–178, 1998.
5 W. Stallings. Data and Computer Communications. Prentice Hall of India Publication, 8th edition, 2007.
6 J. Kleinberg, Y. Rabani, and E. Tardos. Fairness in routing and load balancing. Journal of Computer and System Science, 63(1):2–20, 2001.
7 F. Xiushan and H. Chengde. A fault‐tolerant routing scheme in dynamic networks. Journal of Computer Science and Technology, 16(4):371–380, 2001.
8 M. Bhatia and A. Youssef. Performance analysis and fault tolerance of randomized routing on close networks. Telecommunication Systems, 10(1–2):157–173, 1998.
9 J. C. Sancho, A. Robles, J. Flich, P. Lopez, and J. Duato. Effective methodology for deadlock‐free minimal routing in infiniband networks. IEEE International Conference on Parallel Processing, pp. 409–418, 2002.
10 A. Jouraku, M. Koibuchi, and H. Amano. An effective design of deadlock‐free routing algorithms based on 2D turn model for irregular networks. IEEE Transactions on Parallel and Distributed Systems, 18(3):320–333, 2007.
11 J. Doyle and J. Carroll. Routing TCP/IP, Volume 2. CCIE Professional Development, CiscoPress, 2004.
12 T. Lammle. Cisco Certified Network Associate Study Guide. BPB Publishers, 4th edition, 2003.
13 L. Parziale, D. T. Britt, C. Davis, J. Forrester, W. Liu, C. Matthews, and N. Rosselot, TCP/IP Tutorial and Technical Overview. IBM Red Book, 2006.
14 R. Graziani and A. Johnson, Routing Protocols and Concepts, CCNA Exploration Companion Guide. Cisco Press, 1st edition, 2012.
15 J. Doyle and J. Carroll, Routing TCP/IP, Volume 1. CCIE Professional Development, Cisco Press, 2nd edition, 2010.
16 S. Vutukury and J. J. Garcia‐Luna‐Aceves, A simple approximation to minimum‐delay routing. ACM, 29(4):227–238, 1999.
Abbreviations/Terminologies
BGP
Border Gateway Protocol
CPU
Central Processing Unit
CIDR
Classless Interdomain Routing
EIGRP
Enhanced Interior Gateway Routing Protocol
IGP
Interior Gateway Protocol
IGRP
Interior Gateway Routing Protocol
IS‐IS
Intermediate System to Intermediate System (routing)
LSRR
Loose Source and Record Routing
OSPF
Open Shortest Path First
RIB
Routing Information Base
RIP
Routing Information Protocol
SSRR
Strict Source and Record Routing
TCP
Transmission Control Protocol
VLSM
Variable‐Length Subnet Mask
WAN
Wide Area Network
Questions
State the difference between a routing algorithm and a routing protocol.
How is point‐to‐point communication different from collective communication?
Explain the disadvantages of a greedy routing algorithm and draw a network diagram to show failure of greedy routing in it.
Describe the three generations of routing algorithms.
State the common metrics used in routing protocols.
Describe the various mechanisms that can be used to reduce the explosive increase in packets during flooding.
Mention the advantages and disadvantages of static routing and dynamic routing.
Explain the following:
source routing,
oblivious routing algorithm,
Dijkstra’s algorithm,
Interior Gateway Protocols,
stochastic routing algorithm.
Differentiate between the following
centralized routing vs distributed routing,
adaptive vs non‐adaptive routing algorithms,
distance vector vs link state routing.
State whether the following statements are true or false and give reasons for the answer:
Multipath datagram routing and per‐flow routing perform dynamic load balancing.
Interior Gateway Protocol works within the same autonomous system, while Exterior Gateway Protocol is used across various autonomous systems.
Dijkstra’s algorithm can be used for shortest path computation in a graph even with negative edge cost.
Static routing requires a central controller to build the static routes for the routers.
Adaptive routing algorithms are not of much use in a circuit‐switched network.
In the case of static routing, if a link fails, the packet waits in the intermediate node till the intermediate router gets information about the failed link and then the router changes its routing table and forwards the packet by the new determined path.
Adaptive algorithms have to deal with the problem of path swings.
An organization has ten routers in the network. It has special routing policies where certain packets have to follow some special predefined paths. The links and routers are stable, and there is rarely a change in the topology. The routing should ensure security. Static routing suits best in such a scenario.
Centralized routing is best suited for networks such as the Internet.
Strict source and record routing can be used in EGP.
Exercises
Please consider the graph in Figure 2.1, wherein a data packet has to be sent from node A to node F. Write a program/algorithm for forwarding the packet strictly using point‐to‐point communication. Similarly, write a program/algorithm for the network that uses a plain broadcast mode of communication.
Prepare a partial digital map either in the form of tables or in the form of subgraphs for each node given in Figure 2.2.
Assume that each node in a network is aware of the complete network. Use Figure 2.1 and prepare a lookup table for each node, assuming that hop count is used as a metric and the routing attempts to minimize the hop count.
Consider a network that uses flooding for routing of packets, and the diameter of the network is used as the maximum hop count. What should the maximum permissible hop count be for such a network, shown in Figure 2.1, and for the network shown in Figure 2.2.
Give a step‐by‐step working of Dijkastra’s algorithm to find the shortest path between node 6 and node 7 in Figure 2.2.
Consider the network indicated in the figure below:Give a step‐by‐step working of Dijkastra’s algorithm to find the shortest path from node X to all other nodes. Is the path discovered between node X and node Y using this algorithm actually the shortest path seen visually?
Assume that a network distributes the next‐hop packet into various available routes for load balancing in proportion to the transmission cost. Consider the network indicated in Figure 2.2 where the values shown in the links are the transmission costs. 100 data packets are to be sent from node A to node B. Calculate the number of data packets that will move from each of the links in the network. Please do a similar calculation for the network given in exercise 6 above for transmission of 100 data packets from node X to node Y.
Consider the network indicated in Figure 2.2, which uses simple flooding for data communication, where a node sends out the packet to all the links except the one from which it was received. How many copies of each data packet will be generated for transmitting a packet from node 6 to node 7. How many copies of each data packet will be generated for transmitting a packet from node 7 to node 6. Now, under the condition that each data packet is uniquely identified by an identifier and the node forwards the data packet along all its links only once, how many copies of each data packet will be generated for transmitting a packet from node 6 to node 7, and how many copies of each data packet will be generated for transmitting a packet from node 7 to node 6. Is the number of data packet copies generated equal to the number of links in the network?
Consider the network given in Figure 2.1, where 100 packets are to be transmitted from node A to node F. The two paths ABEF and ADEF are used, and equal numbers of packets are sent by the two paths. Assume that each hop takes a unit time, and the buffer of each router can accommodate 100 packets. The processing time at each router is infinitesimally small and can be assumed to be 0. Calculate the time for the first packet and the last packet to reach node F. Calculate the average waiting time in the buffer for this transmission.
Write a program/algorithm to detect routing swings in a network with adaptive routing.
