M3-CN-Ktunotes - Tutorial Work -Module 3- Computer Networks -B.Tech-CSE-Semester 6 PDF

Preview

Summary

Tutorial Work -Module 3- Computer Networks -B.Tech-CSE-Semester 6...

Description

MODULE 3 Network layer – Routing – Shortest path routing, Flooding, Distance Vector Routing, Link State Routing, RIP, OSPF, Routing for mobile hosts.

NETWORK LAYER

SA C

The network Layer controls the operation of the subnet. The main aim of this layer is to deliver packets from source to destination across multiple links (networks). If two computers (system) are connected on the same link, then there is no need for a network layer. It routes the signal through different channels to the other end and acts as a network controller. It also divides the outgoing messages into packets and to assemble incoming packets into messages for higher levels. FUNCTIONS OF NETWORK LAYER

1.It translates logical network address into physical address. Concerned with circuit, message or packet switching. 2.Routers and gateways operate in the network layer. Mechanism is provided by Network Layer for routing the packets to final destination. 3.Connection services are provided including network layer flow control, network layer error control and packet sequence control. 4.Breaks larger packets into small packets.

ROUTING Routing is the process of moving packets across a network from one host to an another. It is usually performed by dedicated devices called routers.

SA C

Packets are the fundamental unit of information transport in all modern computer networks, and increasingly in other communications networks as well. They are transmitted over packet switched networks, which are networks on which each message (i.e., data that is transmitted) is cut up into a set of small segments prior to transmission. Each packet is then transmitted individually and can follow the same path or a different path to the common destination. Once all of the packets have arrived at the destination, they are automatically reassembled to recreate the original message. Routing is a key feature of the Internet and it, together with a great deal of deliberate redundancy of high capacity transmission lines (e.g., optical fibre cable and microwave), is a key factor in the robustness (i.e., resistance to equipment failure) of the Internet. Each intermediary router performs routing by passing along the message to the next router. Part of this process involves analysing self-configuring routing tables to determine the best (i.e., optimal) path. Routing is sometimes confused with bridging, which performs a somewhat similar function. The main difference is that the latter occurs at a lower level of the OSI (open systems interconnect) model and is thus more of a hardware function; the former occurs at a higher level where the software component is more important, and thus it can perform more complex analysis to determine the optimal path for each packet. Routing is also used by circuit switched networks, in which a dedicated circuit is established for the duration of the transmission of each message. The dominant circuit switched network is the public switched telephone network (PSTN), which is the worldwide collection of

interconnected public telephone networks that was designed primarily for voice traffic. The main function of the network layer is routing packets from the source machine to the destination machine. In most networks, packets will require multiple hops to make the journey. The only notable exception is for broadcast networks, but even here routing is an issue if the source and destination are not on the same network segment. The algorithms that choose the routes and the data structures that they use are a major area of network layer design. The routing algorithm is that part of the network layer software responsible for deciding which output line an incoming packet should be transmitted on. If the network uses datagrams internally, this decision must be made anew for every arriving data packet since the best route may have changed since last time.

SHORTEST PATH

SA C

Shortest path routing refers to the process of finding paths through a network that have a minimum of distance or other cost metric. Routing of data packets on the Internet is an example involving millions of routers in a complex, worldwide, multilevel network. Optimum routing on the Internet has a major impact on performance and cost. The main limitations of simple shortest-path routing have to do with real-world problems that occur in large networks. We can't just keep adding nodes to a huge routing table at each and every node. As shown in Figure 2, the time to build (or re-build) a table increases as the square of the number of nodes. Also, as nodes are added, the number of failing links, changes in topology, and other events that trigger re-builds throughout the network - these events will occur more frequently. The general algorithm is: 1. Initialize the array smallestWeight so that smallestWeight[u] = weights[vertex, u]. 2. Set smallestWeight[vertex] = 0. 3. Find the vertex, v, that is closest to vertex for which the shortest path has not been determined. 4. Mark v as the (next) vertex for which the smallest weight is found.

5. For each vertex w in G, such that the shortest path from vertex to w has not been determined and an edge (v, w) exists, if the weight of the path to w via v is smaller than its current weight, update the weight of w to the weight of v + the weight of the edge (v, w). Because there are n vertices, repeat Steps 3 through 5, n — 1 times.

SA C

The idea is to build a graph of the subnet with each node of the graph representing a router and each are of the graph representing a link. To choose a route between a given pair of routers, the algorithm just finds the shortest path between them on the graph. Consider a graph of the subnet, with each node of the graph representing a router and each arc of the graph representing a communication line. To choose a route between a given pair of routers, the algorithm just finds the shortest path between them on the graph. One way of measuring path length is the number of hops. In the above figure, the paths ABC and ABE are equally long. Another metric is the geographic distance in which case ABC is clearly much longer than ABE. Many other metrics are also possible besides hops and physical distance. With this graph labelling, the shortest path is the fastest path, rather than the path with the fewest arcs or kilometres. The labels on the arcs could be computed as a function of the distance, bandwidth, average traffic, communication cost, and other factors. Several algorithms for computing the shortest path between two nodes of a graph are known. This one is due to Dijkstra (1959). Each node is labelled (in parentheses) with its distance from the source node along the best-known path. Initially, no paths are known, so all nodes are labelled with infinity. As the algorithm proceeds and paths are found, the labels may change, reflecting better paths. A label may be either tentative or permanent. Initially, all labels are tentative. When it is discovered that a label represents the shortest possible path from the source to that node, it is made permanent and never changed thereafter. To illustrate how the labelling algorithm works, consider the weighted, undirected graph where the weights represent, for example, distance. To find the shortest path from A to D, we start out by marking node A as permanent, indicated by a filled-in circle. Then we examine, in turn, each of the nodes adjacent to A (the working node), relabelling each one with the distance to A. Whenever a node is relabelled, we also label

SA C

it with the node from which the probe was made so that we can reconstruct the final path later. Having examined each of the nodes adjacent to A, we examine all the tentatively labelled nodes in the whole graph and make the one with the smallest label permanent. This one becomes the new working node. We now start at B and examine all nodes adjacent to it. If the sum of the label on B and the distance from B to the node being considered is less than the label on that node, we have a shorter path, so the node is relabelled. After all the nodes adjacent to the working node have been inspected and the tentative labels changed if possible, the entire graph is searched for the tentatively-labelled node with the smallest value. This node is made permanent and becomes the working node for the next round.

We now start at B and examine all nodes adjacent to it. If the sum of the label on B and the distance from B to the node being considered is less than the label on that node, we have a shorter path, so the node is relabelled. After all the nodes adjacent to the working node have been inspected and the tentative labels changed if possible, the entire graph is searched for the tentatively labelled node with the smallest value. This node is made permanent and becomes the working node for the next round. Figure shows the first six steps of the algorithm. To see why the algorithm works, look at Fig. (c). At this point we have just made E permanent. Suppose that there was a shorter path than ABE,

say AXYZE (for some X and Y). There are two possibilities: either node Z has already been made permanent, or it has not been. If it has, then E has already been probed (on the round following the one when Z was made permanent), so the AXYZE path has not escaped our attention and thus cannot be a shorter path. Now consider the case where Z is still tentatively labelled. If the label at Z is greater than or equal to that at E, then AXYZE cannot be a shorter path than ABE. If the label is less than that of E, then Z and not E will become permanent first, allowing E to be probed from Z.

FLOODING

SA C

Flooding is the static routing algorithm. In this algorithm, every incoming packet is sent on all outgoing lines except the line on which it has arrived One major problem of this algorithm is that it generates a large number of duplicate packets on the network. Several measures are takes to stop the duplication of packets. These are: 1.) One solution is to include a hop counter in the header of each packet. This counter is decremented at each hop along the path. When this counter reaches zero the packet is discarded. Ideally, the hop counter should become zero at the destination hop, indicating that there are no more intermediate hops and destination is reached. This requires the knowledge of exact number of hops from a source to destination. 2.) Another technique is to keep the track of the packed that have been flooded, to avoid sending them a second time. For this, the source router put a sequence number in each packet it receives from its hosts. Each router then needs a list per source router telling which sequence numbers originating at that source have already been seen. If an incoming packet is on the list, it is not flooded. 3). Another solution is to use selective flooding. In selective flooding the routers do not send every incoming packet out on every output line. Instead packet is sent only on those lines which are approximately going in the right direction

Flooding is a simple computer network routing algorithm in which every incoming packet is sent through every outgoing link except the one it arrived on. Flooding is used in bridging and in systems such as Usenet and peerto-peer file sharing and as part of some routing protocols, including OSPF, DVMRP, and those used in ad-hoc wireless networks (WANETs). ADVANTAGES:

• If a packet can be delivered, it will (probably multiple times). • Since flooding naturally utilizes every path through the network, it will also use the shortest path. • This algorithm is very simple to implement. DISADVANTAGES:

SA C

• Flooding can be costly in terms of wasted bandwidth. While a message may only have one destination it has to be sent to every host. In the case of a ping flood or a denial of service attack, ×it can be harmful to the reliability of a computer network. • Messages can become duplicated in the network further increasing the load on the networks bandwidth as well as requiring an increase in processing complexity to disregard duplicate messages.

There are several variants of flooding algorithms. Most work roughly as follows: 1.Each node acts as both a transmitter and a receiver. 2.Each node tries to forward every message to every one of its neighbours except the source node. This results in every message eventually being delivered to all reachable parts of the network.

DISTANCE VECTOR ROUTING Modern computer networks generally use dynamic routing technique

SA C

rather than static routing technique. There are two dynamic routing in particular, distance vector routing and link state routing. A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass, one router counts as one hop. Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route. To determine the best route across a network router on which a distance-vector protocol is implemented exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information. Distance-vector routing protocols also require that a router informs its neighbours of network topology changes periodically. Distance-vector routing protocols use the Bellman–Ford algorithm and Ford–Fulkerson algorithm to calculate the best route. Another way of calculating the best route across a network is based on link cost, and is implemented through link-state routing protocols. Distance Vector Algorithm –

Each router maintains a table (vector), giving the best-known distance to each destination and the outgoing line to get there. 1.A router transmits its distance vector to each of its neighbours in a routing packet. 2.Each router receives and saves the most recently received distance vector from each of its neighbours. 3.A router recalculates its distance vector when: It receives a distance vector from a neighbour containing different information than before. It discovers that a link to a neighbour has gone down. The DV calculation is based on minimizing the cost to each destination Distance vector routing operates by having each router

SA C

maintain a table giving the best-known distance to each destination and which line to use to get there. These tables are updated by exchanging information with the neighbours. In distance vector routing, each router maintains a routing table indexed by, and containing one entry for each router in the subnet. This entry contains two parts, the preferred outgoing line to use for that destination, and an estimate of the time or distance to that destination.

From the above figure find the routing table for each node.

Routing table N1,

for

Destination

Cost

Next hope

N1

0

N1

N2

1

N2

N3

Infinity

N4

Infinity

N5

Infinity

Routing table for N2, Destination

Cost

Next hope

N1

1

N1

N2

0

N2

N3

6

N3

N4

Infinity

N5

3

N5

Destination

Cost

Next hope

N1

Infinity

N2

6

N3

0

SA C

Routing table for N3,

N4

2

N4

N5

Infinity

N5

N2 N3

Routing table for N4, Destination

Cost

Next hope

N1

Infinity

N2

Infinity

N3

2

N3

N4

0

N4

4

N5

N5

Routing table for N5, Destination

Cost

Next hope

N1

Infinity

N2

3

N3

Infinity

N4

4

N4

N5

.0

N5

N2

N2 share to N1.Update each routing table.

N1

0

N2

1

N3

7

N4

8

N5

4

Updated table for N2, N1

1

N2

0

N3

6

N4

7

N5

3

Updated table for N3, N1

7

SA C

Updated table for N1,

N2

6

N3

0

N4

2

N5

6

Updated table forN4, N1

8

N2

7

N3

2

N4

0

N5

4

N1

4

N2

3

N3

6

N4

4

N5

0

SA C

Updated table for N5,

This is the procedure included in the distance vector routing.

Advantages of Distance Vector routing

• It is simpler to configure and maintain than link state routing. Distance vector works in theory but has a serious drawback in practice. ➢ React rapidly to good news when a router comes up. ➢ Though it finally converges to correct result, it takes long time when where is a bad news. ➢ There are several attempts to solve the problem, but none is perfect. ➢ It does not take line bandwidth into account.

➢ ➢ ➢ ➢

It took too long to converge. It is slower to converge than link state. It is at risk from the count-to-infinity problem. It creates more traffic than link state since a hop count change must be propagated to all routers and processed on each router. Hop count updates take place on a periodic basis, even if there are no changes in the network topology, so bandwidth-wasting broadcasts still occur. ➢ For larger networks, distance vector routing results in larger routing tables than link state since each router must know about all other routers. This can also lead to congestion on WAN links.

THE COUNT TO INFINITY PROBLEM

The main problem faced by distance vector routing is the count-toinfinity problem.

SA C

Distance vector routing works in theory but has a serious drawback in practice. Although it converges to the correct answer, it may do so slowly. In particular it reacts rapidly to good news, but leisurely to bad news. To see how fast the good news propagates, consider the five-node subnet.

From this figure, it should be clear why bad news travels slowly, no router ever has a value more than one higher than the minimum of all its neighbours. Gradually, all the routers work their way up to infinity, but the number of exchanges required depends on the numerical value used for infinity. For this reason, it is wise to set infinity to the longest path plus 1.if the metric is time delay, there is no well-defined upper bound, so a high value is needed to prevent a path with a long delay from being treated as down. Not entirely surprisingly, this problem is known as count to infinity problem. The solution to count to infinity problem is the, split horizon hack. The split horizon

SA C

The split horizon works the same way as distance vector routing, except that the distance to X is not reported on the line that packet for X are sent on (actually, it is reported as infinity). Initially both A and B have a distance ...