Module 5 - Network Layer PDF

MODULE 5 11/14/2024 1 11/14/2024 2  The network layer or layer 3 of the OSI (Open Systems Interconnection) model is concerned about the delivery of data packets from the source to the destination across multiple hops or links. It is the lowest layer that is co...

MODULE 5 11/14/2024 1 11/14/2024 2  The network layer or layer 3 of the OSI (Open Systems Interconnection) model is concerned about the delivery of data packets from the source to the destination across multiple hops or links. It is the lowest layer that is concerned with end − to − end transmission. Functions of Network Layer:- 1. Addressing: Maintains the address of both source and destination and performs addressing to detect various devices in the network. 2. Packeting: This is performed by Internet Protocol. The network layer converts the packets from its upper layer. 3. Routing: It is the most important functionality. The network layer chooses the most relevant and best path for the data transmission from source to destination. 4. Inter-networking: It works to deliver a logical connection across multiple devices. 11/14/2024 3 11/14/2024 4 The host sends the packet to the nearest router. This packet is stored there until it has fully arrived once the link is fully processed by verifying the checksum then it is forwarded to the next router till it reaches the destination. This mechanism is called “Store and Forward packet switching.” 11/14/2024 5 2. SERVICES PROVIDED TO THE TRANSPORT LAYER Through the network/transport layer interface, the network layer transfers its patterns services to the transport layer. These services are described below. But before providing these services to the transfer layer, the following goals must be kept in mind:- 1. Offering services must not depend on router technology. 2. The transport layer needs to be protected from the type, number, and topology of the available router. 3. The network addresses for the transport layer should use uniform numbering patterns, also at LAN and WAN connections. Based on the connections there are 2 types of services provided : Connectionless – The routing and insertion of packets into the subnet are done individually. No added setup is required. Connection-Oriented – Subnet must offer reliable service and all the packets must be transmitted over a single route. 11/14/2024 6 11/14/2024 7 In connection − oriented services, a path or route called a virtual circuit is setup between the source and the destination nodes before the transmission starts. All the packets in the message are sent along this route. Each packet contains an identifier that denotes the virtual circuit to which it belongs to. When all the packets are transmitted, the virtual circuit is terminated and the connection is released.Eg:-Telephone Line 11/14/2024 8 11/14/2024 9 THE OPTIMALITY PRINCIPLE It states that if the router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route. The purpose of a routing algorithm at a router is to decide which output line an incoming packet should go. The optimal path from a particular router to another may be the least cost path, the least distance path, the least time path, the least hops path or a combination of any of the above. 11/14/2024 10 Example Consider a network of routers, {G, H, I, J, K, L, M, N} as shown in the figure. Let the optimal route from I to K be as shown via the green path, i.e. via the route I-G-J-L-K. According to the optimality principle, the optimal path from J to K with be along the same route, i.e. J-L-K. Now, suppose we find a better route from J to K is found, say along J-M-N-K. Consequently, we will also need to update the optimal route from I to K as I-G-J- M-N-K, since the previous route ceases to be optimal in this situation. This new optimal path is shown line orange lines in the following figure − 11/14/2024 11 FLOODING Flooding is a non-adaptive routing technique following this simple method: when a data packet arrives at a router, it is sent to all the outgoing links except the one it has arrived on. For example, let us consider the network in the figure, having six routers that are connected through transmission lines. 11/14/2024 12  Using flooding technique − An incoming packet to A, will be sent to B, C and D. B will send the packet to C and E. C will send the packet to B, D and F. D will send the packet to C and F. E will send the packet to F. F will send the packet to C and E. Types of Flooding Flooding may be of three types − 11/14/2024 13  Routing Protocols UNICAST ROUTING PROTOCOLS ? Two important classes of shortest path routing algorithms, the bellman–ford algorithm(Distance Vector protocol) and dijkstra’s algorithm(Link state protocol). APPROACHES TO SHORTEST PATH ROUTING There are two basic approaches to least-cost routing in a communication network There are two basic approaches to shortest-path routing: 1. Link State Routing 2. Distance Vector Routing APPROACHES TO SHORTEST PATH ROUTING 1. Link State Routing – Each node knows the distance to its neighbors – The distance information (=link state) is broadcast to all nodes in the network – Each node calculates the routing tables independently 2. Distance Vector Routing – Each node knows the distance (=cost) to its directly connected neighbors – A node sends a list to its neighbors with the current distances to all nodes – If all nodes update their distances, the routing tables eventually converge DISTANCE VECTOR ROUTING A distance-vector routing (DVR) protocol requires that a router inform its neighbors of topology changes periodically. Historically known as the old ARPANET routing algorithm (or known as Bellman-Ford algorithm). Bellman Ford Basics – Each router maintains a Distance Vector table containing the distance between itself and ALL possible destination nodes 17  Distance Vector Algorithm – 1. A router transmits its distance vector to each of its neighbors in a routing packet. 2. Each router receives and saves the most recently received distance vector from each of its neighbors. 3. A router recalculates its distance vector when: 1. It receives a distance vector from a neighbor containing different information than before. 2. It discovers that a link to a neighbor has gone down. The DV calculation is based on minimizing the cost to each destination 18  From time-to-time, each node sends its own distance vector estimate to neighbors. When a node x receives new DV estimate from any neighbor v, it saves v’s distance vector and it updates its own DV using Bellman ford equation: Dx(y) = min { C(x,v) + Dv(y), Dx(y) } for each node y 19  Example – Consider 3-routers X, Y and Z as shown in figure. Each router have their routing table. Every routing table will contain distance to the destination nodes. 20  Consider router X , X will share it routing table to neighbors and neighbors will share it routing table to it to X and distance from node X to destination will be calculated using bellman- ford equation. As we can see that distance will be less going from X to Z when Y is intermediate node(hop) so it will be update in routing table X. 21  Finally the routing table for all – 22  Advantages of Distance Vector routing – It is simpler to configure and maintain than link state routing. Disadvantages of Distance Vector routing – It is slower to converge than link state. 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. 23 LINK STATE ROUTING Each node must 1. Discover its neighbors or Learning about the neighbors by Sending a special HELLO packet on each point-to- point line 2. Measure the delay (=cost) to its neighbors ◦ Round-trip time ◦ Traffic load ◦ Line bandwidth 3. Building link state packet 4.Broadcast a packet with this information to all other nodes 5.Compute the shortest paths to every other router BUILDING LINK STATE PACKET The broadcast can be accomplished by flooding. Each packet contains a sequence number that is incremented for each new packet sent. The shortest paths can be computed with Dijkstra’s algorithm 25 LINK STATE ROUTING: BASIC PRINCPLES 1. Each router establishes a relationship (“adjacency”) with its neighbors 2.Each router generates link state advertisements (LSAs) which are distributed to all routers LSA = (link id, state of the link, cost, neighbors of the link) 3. Each router maintains a database of all received LSAs (link state database), which describes the network has a graph with weighted edges 4. Each router uses its link state database to run a shortest path algorithm (Dijikstra’s algorithm) to produce the shortest path to each network 26 LINK STATE ROUTING: PROPERTIES Each node requires complete topology information Link state information must be flooded to all nodes Guaranteed to converge 27 OPERATION OF A LINK STATE ROUTING PROTOCOL Received Link State Dijkstra’s IP Routing LSAs Database Table Algorithm LSAs are flooded to other interfaces 28 MULTICASTING 11/14/2024 29 11/14/2024 30 11/14/2024 31 11/14/2024 32 CONGESTION CONTROL ALGORITHMS 11/14/2024 33 11/14/2024 34 11/14/2024 35 CONGESTION PREVENTION POLICIES 11/14/2024 36 11/14/2024 37  Maintain running average of queue length If avg < minth do nothing Low queuing, send packets through If avg > maxth, drop packet Protection from misbehaving sources Else mark packet in a manner proportional to queue length Notify sources of incipient congestion 11/14/2024 38 11/14/2024 39  TRANSPORT LAYER The transport Layer is the second layer in the TCP/IP model and the fourth layer in the OSI model. It is an end-to-end layer used to deliver messages to a host. It is termed an end-to-end layer because it provides a point-to-point connection rather than hop-to- hop, between the source host and destination host to deliver the services reliably. The unit of data encapsulation in the Transport Layer is a segment. Working of Transport Layer The transport layer takes services from the Application layer and provides services to the Network layer. The transport layer ensures the reliable transmission of data between systems. At the sender’s side: The transport layer receives data (message) from the Application layer and then performs Segmentation, divides the actual message into segments, adds the source and destination’s port numbers into the header of the segment, and transfers the message to the Network layer. At the receiver’s side: The transport layer receives data from the Network layer, reassembles the segmented data, reads its header, identifies the port number, and forwards the message to the appropriate port in the Application layer. 11/14/2024 40 Responsibilities of a Transport Layer The Process to Process Delivery End-to-End Connection between Hosts Multiplexing and Demultiplexing Congestion Control Data integrity and Error correction Flow control 11/14/2024 41  APPLICATION LAYER Application Layer is the topmost layer in the Open System Interconnection (OSI) model. This layer provides several ways for manipulating the data (information) which actually enables any type of user to access network with ease. This layer also makes a request to its bottom layer, which is presentation layer for receiving various types of information from it. Application Layer plays a key role in managing applications such as email, file transfer, and remote login. 11/14/2024 42 Functions of the application layer The application layer handles the following functions: ensures that the receiving device is identified, reachable and ready to accept data; when appropriate, enables authentication between devices for an extra layer of network security; makes sure necessary communication interfaces exist, such as whether there is an Ethernet or Wi-Fi interface in the sender's computer; ensures agreement at both ends on error recovery procedures, data integrity and privacy; determines protocol and data syntax rules at the application level presents the data on the receiving end to the user application. 11/14/2024 43 DIJKSTRA’S ALGORITHM: The algorithm maintains a set of visited vertices and a set of unvisited vertices. It starts at the source vertex and iteratively selects the unvisited vertex with the smallest tentative distance from the source. It then visits the neighbors of this vertex and updates their tentative distances if a shorter path is found. This process continues until the destination vertex is reached, or all reachable vertices have been visited. 11/14/2024 44 11/14/2024 45 11/14/2024 46 11/14/2024 47 11/14/2024 48 11/14/2024 49 11/14/2024 50 11/14/2024 51 Algorithm for Dijkstra’s Algorithm: 1.Mark the source node with a current distance of 0 and the rest with infinity. 2.Set the non-visited node with the smallest current distance as the current node. 3.For each neighbor, N of the current node adds the current distance of the adjacent node with the weight of the edge connecting 0->1. If it is smaller than the current distance of Node, set it as the new current distance of N. 4.Mark the current node 1 as visited. 5.Go to step 2 if there are any nodes are unvisited. 11/14/2024 52 EXTRA QUESTION-DIJKSTRAS ALGORITHM 11/14/2024 53