UNIT -3 Network Layer

 

UNIT -3

  Network Layer

• The Network Layer is the third layer of the OSI model.
• It handles the service requests from the transport layer and further forwards the service request to the data link layer.
• The network layer translates the logical addresses into physical addresses
• It determines the route from the source to the destination and also manages the traffic problems such as switching, routing and controls the congestion of data packets.
• The main role of the network layer is to move the packets from sending host to the receiving host.

The main functions performed by the network layer are:

• Routing: When a packet reaches the router's input link, the router will move the packets to the router's output link. For example, a packet from S1 to R1 must be forwarded to the next router on the path to S2.
• Logical Addressing: The data link layer implements the physical addressing and network layer implements the logical addressing. Logical addressing is also used to distinguish between source and destination system. The network layer adds a header to the packet which includes the logical addresses of both the sender and the receiver.
• Internetworking: This is the main role of the network layer that it provides the logical connection between different types of networks.
• Fragmentation: The fragmentation is a process of breaking the packets into the smallest individual data units that travel through different networks.

---

Forwarding & Routing

In Network layer, a router is used to forward the packets. Every router has a forwarding table. A router forwards a packet by examining a packet's header field and then using the header field value to index into the forwarding table. The value stored in the forwarding table corresponding to the header field value indicates the router's outgoing interface link to which the packet is to be forwarded.

For example, the router with a header field value of 0111 arrives at a router, and then router indexes this header value into the forwarding table that determines the output link interface is 2. The router forwards the packet to the interface 2. The routing algorithm determines the values that are inserted in the forwarding table. The routing algorithm can be centralized or decentralized.

Services Provided by the Network Layer

• Guaranteed delivery: This layer provides the service which guarantees that the packet will arrive at its destination.
• Guaranteed delivery with bounded delay: This service guarantees that the packet will be delivered within a specified host-to-host delay bound.
• In-Order packets: This service ensures that the packet arrives at the destination in the order in which they are sent.
• Guaranteed max jitter: This service ensures that the amount of time taken between two successive transmissions at the sender is equal to the time between their receipt at the destination.
• Security services: The network layer provides security by using a session key between the source and destination host. The network layer in the source host encrypts the payloads of datagrams being sent to the destination host. The network layer in the destination host would then decrypt the payload. In such a way, the network layer maintains the data integrity and source authentication services.

Network Addressing

• Network Addressing is one of the major responsibilities of the network layer.
• Network addresses are always logical, i.e., software-based addresses.
• A host is also known as end system that has one link to the network. The boundary between the host and link is known as an interface. Therefore, the host can have only one interface.
• A router is different from the host in that it has two or more links that connect to it. When a router forwards the datagram, then it forwards the packet to one of the links. The boundary between the router and link is known as an interface, and the router can have multiple interfaces, one for each of its links. Each interface is capable of sending and receiving the IP packets, so IP requires each interface to have an address.
• Each IP address is 32 bits long, and they are represented in the form of "dot-decimal notation" where each byte is written in the decimal form, and they are separated by the period. An IP address would look like 193.32.216.9 where 193 represents the decimal notation of first 8 bits of an address, 32 represents the decimal notation of second 8 bits of an address.

·  Let's understand through a simple example.

• In the above figure, a router has three interfaces labeled as 1, 2 & 3 and each router interface contains its own IP address.
• Each host contains its own interface and IP address.
• All the interfaces attached to the LAN 1 is having an IP address in the form of 223.1.1.xxx, and the interfaces attached to the LAN 2 and LAN 3 have an IP address in the form of 223.1.2.xxx and 223.1.3.xxx respectively.
• Each IP address consists of two parts. The first part (first three bytes in IP address) specifies the network and second part (last byte of an IP address) specifies the host in the network.

Classful Addressing

An IP address is 32-bit long. An IP address is divided into sub-classes:

• Class A
• Class B
• Class C
• Class D
• Class E

An ip address is divided into two parts:

• Network ID: It represents the number of networks.
• Host ID: It represents the number of hosts.

In the above diagram, we observe that each class have a specific range of IP addresses. The class of IP address is used to determine the number of bits used in a class and number of networks and hosts available in the class.

Class A

In Class A, an IP address is assigned to those networks that contain a large number of hosts.

• The network ID is 8 bits long.
• The host ID is 24 bits long.

In Class A, the first bit in higher order bits of the first octet is always set to 0 and the remaining 7 bits determine the network ID. The 24 bits determine the host ID in any network.

The total number of networks in Class A = 2⁷ = 128 network address

The total number of hosts in Class A = 2²⁴ - 2 = 16,777,214 host address

Class B

In Class B, an IP address is assigned to those networks that range from small-sized to large-sized networks.

• The Network ID is 16 bits long.
• The Host ID is 16 bits long.

In Class B, the higher order bits of the first octet is always set to 10, and the remaining14 bits determine the network ID. The other 16 bits determine the Host ID.

The total number of networks in Class B = 2¹⁴ = 16384 network address

The total number of hosts in Class B = 2¹⁶ - 2 = 65534 host address

Class C

In Class C, an IP address is assigned to only small-sized networks.

• The Network ID is 24 bits long.
• The host ID is 8 bits long.

In Class C, the higher order bits of the first octet is always set to 110, and the remaining 21 bits determine the network ID. The 8 bits of the host ID determine the host in a network.

The total number of networks = 2²¹ = 2097152 network address

The total number of hosts = 2⁸ - 2 = 254 host address

Class D

In Class D, an IP address is reserved for multicast addresses. It does not possess subnetting. The higher order bits of the first octet is always set to 1110, and the remaining bits determines the host ID in any network.

Class E

In Class E, an IP address is used for the future use or for the research and development purposes. It does not possess any subnetting. The higher order bits of the first octet is always set to 1111, and the remaining bits determines the host ID in any network.

---

Rules for assigning Host ID:

The Host ID is used to determine the host within any network. The Host ID is assigned based on the following rules:

• The Host ID must be unique within any network.
• The Host ID in which all the bits are set to 0 cannot be assigned as it is used to represent the network ID of the IP address.
• The Host ID in which all the bits are set to 1 cannot be assigned as it is reserved for the multicast address.

---

Rules for assigning Network ID:

If the hosts are located within the same local network, then they are assigned with the same network ID. The following are the rules for assigning Network ID:

• The network ID cannot start with 127 as 127 is used by Class A.
• The Network ID in which all the bits are set to 0 cannot be assigned as it is used to specify a particular host on the local network.
• The Network ID in which all the bits are set to 1 cannot be assigned as it is reserved for the multicast address.

---

Classful Network Architecture

Class	Higher bits	NET ID bits	HOST ID bits	No.of networks	No.of hosts per network	Range
A	0	8	24	27	224	0.0.0.0 to 127.255.255.255
B	10	16	16	214	216	128.0.0.0 to 191.255.255.255
C	110	24	8	221	28	192.0.0.0 to 223.255.255.255
D	1110	Not Defined	Not Defined	Not Defined	Not Defined	224.0.0.0 to 239.255.255.255
E	1111	Not Defined	Not Defined	Not Defined	Not Defined	240.0.0.0 to 255.255.255.255

Routing

• A Router is a process of selecting path along which the data can be transferred from source to the destination. Routing is performed by a special device known as a router.
• A Router works at the network layer in the OSI model and internet layer in TCP/IP model
• A router is a networking device that forwards the packet based on the information available in the packet header and forwarding table.
• The routing algorithms are used for routing the packets. The routing algorithm is nothing but a software responsible for deciding the optimal path through which packet can be transmitted.
• The routing protocols use the metric to determine the best path for the packet delivery. The metric is the standard of measurement such as hop count, bandwidth, delay, current load on the path, etc. used by the routing algorithm to determine the optimal path to the destination.
• The routing algorithm initializes and maintains the routing table for the process of path determination.

---

Routing Metrics and Costs

Routing metrics and costs are used for determining the best route to the destination. The factors used by the protocols to determine the shortest path, these factors are known as a metric.

Metrics are the network variables used to determine the best route to the destination. For some protocols use the static metrics means that their value cannot be changed and for some other routing protocols use the dynamic metrics means that their value can be assigned by the system administrator.

The most common metric values are given below:

• Hop count: Hop count is defined as a metric that specifies the number of passes through internetworking devices such as a router, a packet must travel in a route to move from source to the destination. If the routing protocol considers the hop as a primary metric value, then the path with the least hop count will be considered as the best path to move from source to the destination.
• Delay: It is a time taken by the router to process, queue and transmit a datagram to an interface. The protocols use this metric to determine the delay values for all the links along the path end-to-end. The path having the lowest delay value will be considered as the best path.
• Bandwidth: The capacity of the link is known as a bandwidth of the link. The bandwidth is measured in terms of bits per second. The link that has a higher transfer rate like gigabit is preferred over the link that has the lower capacity like 56 kb. The protocol will determine the bandwidth capacity for all the links along the path, and the overall higher bandwidth will be considered as the best route.
• Load: Load refers to the degree to which the network resource such as a router or network link is busy. A Load can be calculated in a variety of ways such as CPU utilization, packets processed per second. If the traffic increases, then the load value will also be increased. The load value changes with respect to the change in the traffic.
• Reliability: Reliability is a metric factor may be composed of a fixed value. It depends on the network links, and its value is measured dynamically. Some networks go down more often than others. After network failure, some network links repaired more easily than other network links. Any reliability factor can be considered for the assignment of reliability ratings, which are generally numeric values assigned by the system administrator.

---

Types of Routing

Routing can be classified into three categories:

\\

\

• Static Routing
• Default Routing
• Dynamic Routing

Static Routing

• Static Routing is also known as Nonadaptive Routing.
• It is a technique in which the administrator manually adds the routes in a routing table.
• A Router can send the packets for the destination along the route defined by the administrator.
• In this technique, routing decisions are not made based on the condition or topology of the networks

Advantages Of Static Routing

Following are the advantages of Static Routing:

• No Overhead: It has ho overhead on the CPU usage of the router. Therefore, the cheaper router can be used to obtain static routing.
• Bandwidth: It has not bandwidth usage between the routers.
• Security: It provides security as the system administrator is allowed only to have control over the routing to a particular network.

Disadvantages of Static Routing:

Following are the disadvantages of Static Routing:

• For a large network, it becomes a very difficult task to add each route manually to the routing table.
• The system administrator should have a good knowledge of a topology as he has to add each route manually.

Default Routing

• Default Routing is a technique in which a router is configured to send all the packets to the same hop device, and it doesn't matter whether it belongs to a particular network or not. A Packet is transmitted to the device for which it is configured in default routing.
• Default Routing is used when networks deal with the single exit point.
• It is also useful when the bulk of transmission networks have to transmit the data to the same hp device.
• When a specific route is mentioned in the routing table, the router will choose the specific route rather than the default route. The default route is chosen only when a specific route is not mentioned in the routing table.

Dynamic Routing

• It is also known as Adaptive Routing.
• It is a technique in which a router adds a new route in the routing table for each packet in response to the changes in the condition or topology of the network.
• Dynamic protocols are used to discover the new routes to reach the destination.
• In Dynamic Routing, RIP and OSPF are the protocols used to discover the new routes.
• If any route goes down, then the automatic adjustment will be made to reach the destination.

The Dynamic protocol should have the following features:

• All the routers must have the same dynamic routing protocol in order to exchange the routes.
• If the router discovers any change in the condition or topology, then router broadcast this information to all other routers.

Advantages of Dynamic Routing:

• It is easier to configure.
• It is more effective in selecting the best route in response to the changes in the condition or topology.

Disadvantages of Dynamic Routing:

• It is more expensive in terms of CPU and bandwidth usage.
• It is less secure as compared to default and static routing.

Network Layer Protocols

TCP/IP supports the following protocols:

ARP

• ARP stands for Address Resolution Protocol.
• It is used to associate an IP address with the MAC address.
• Each device on the network is recognized by the MAC address imprinted on the NIC. Therefore, we can say that devices need the MAC address for communication on a local area network. MAC address can be changed easily. For example, if the NIC on a particular machine fails, the MAC address changes but IP address does not change. ARP is used to find the MAC address of the node when an internet address is known.

Note: MAC address: The MAC address is used to identify the actual device.
IP address: It is an address used to locate a device on the network.

How ARP works

If the host wants to know the physical address of another host on its network, then it sends an ARP query packet that includes the IP address and broadcast it over the network. Every host on the network receives and processes the ARP packet, but only the intended recipient recognizes the IP address and sends back the physical address. The host holding the datagram adds the physical address to the cache memory and to the datagram header, then sends back to the sender.

Steps taken by ARP protocol

If a device wants to communicate with another device, the following steps are taken by the device:

• The device will first look at its internet list, called the ARP cache to check whether an IP address contains a matching MAC address or not. It will check the ARP cache in command prompt by using a command arp-a.

• If ARP cache is empty, then device broadcast the message to the entire network asking each device for a matching MAC address.
• The device that has the matching IP address will then respond back to the sender with its MAC address
• Once the MAC address is received by the device, then the communication can take place between two devices.
• If the device receives the MAC address, then the MAC address gets stored in the ARP cache. We can check the ARP cache in command prompt by using a command arp -a.

Note: ARP cache is used to make a network more efficient.

In the above screenshot, we observe the association of IP address to the MAC address.

\\

There are two types of ARP entries:

• Dynamic entry: It is an entry which is created automatically when the sender broadcast its message to the entire network. Dynamic entries are not permanent, and they are removed periodically.
• Static entry: It is an entry where someone manually enters the IP to MAC address association by using the ARP command utility.

---

RARP

• RARP stands for Reverse Address Resolution Protocol.
• If the host wants to know its IP address, then it broadcast the RARP query packet that contains its physical address to the entire network. A RARP server on the network recognizes the RARP packet and responds back with the host IP address.
• The protocol which is used to obtain the IP address from a server is known as Reverse Address Resolution Protocol.
• The message format of the RARP protocol is similar to the ARP protocol.
• Like ARP frame, RARP frame is sent from one machine to another encapsulated in the data portion of a frame.

---

ICMP

• ICMP stands for Internet Control Message Protocol.
• The ICMP is a network layer protocol used by hosts and routers to send the notifications of IP datagram problems back to the sender.
• ICMP uses echo test/reply to check whether the destination is reachable and responding.
• ICMP handles both control and error messages, but its main function is to report the error but not to correct them.
• An IP datagram contains the addresses of both source and destination, but it does not know the address of the previous router through which it has been passed. Due to this reason, ICMP can only send the messages to the source, but not to the immediate routers.
• ICMP protocol communicates the error messages to the sender. ICMP messages cause the errors to be returned back to the user processes.
• ICMP messages are transmitted within IP datagram.

The Format of an ICMP message

• The first field specifies the type of the message.
• The second field specifies the reason for a particular message type.
• The checksum field covers the entire ICMP message.

Error Reporting

ICMP protocol reports the error messages to the sender.

Five types of errors are handled by the ICMP protocol:

• Destination unreachable
• Source Quench
• Time Exceeded
• Parameter problems
• Redirection

• Destination unreachable: The message of "Destination Unreachable" is sent from receiver to the sender when destination cannot be reached, or packet is discarded when the destination is not reachable.
• Source Quench: The purpose of the source quench message is congestion control. The message sent from the congested router to the source host to reduce the transmission rate. ICMP will take the IP of the discarded packet and then add the source quench message to the IP datagram to inform the source host to reduce its transmission rate. The source host will reduce the transmission rate so that the router will be free from congestion.
• Time Exceeded: Time Exceeded is also known as "Time-To-Live". It is a parameter that defines how long a packet should live before it would be discarded.

There are two ways when Time Exceeded message can be generated:

Sometimes packet discarded due to some bad routing implementation, and this causes the looping issue and network congestion. Due to the looping issue, the value of TTL keeps on decrementing, and when it reaches zero, the router discards the datagram. However, when the datagram is discarded by the router, the time exceeded message will be sent by the router to the source host.

When destination host does not receive all the fragments in a certain time limit, then the received fragments are also discarded, and the destination host sends time Exceeded message to the source host.

• Parameter problems: When a router or host discovers any missing value in the IP datagram, the router discards the datagram, and the "parameter problem" message is sent back to the source host.
• Redirection: Redirection message is generated when host consists of a small routing table. When the host consists of a limited number of entries due to which it sends the datagram to a wrong router. The router that receives a datagram will forward a datagram to a correct router and also sends the "Redirection message" to the host to update its routing table.

---

IGMP

• IGMP stands for Internet Group Message Protocol.
• The IP protocol supports two types of communication:
• Unicasting: It is a communication between one sender and one receiver. Therefore, we can say that it is one-to-one communication.
• Multicasting: Sometimes the sender wants to send the same message to a large number of receivers simultaneously. This process is known as multicasting which has one-to-many communication.
• The IGMP protocol is used by the hosts and router to support multicasting.
• The IGMP protocol is used by the hosts and router to identify the hosts in a LAN that are the members of a group.

• IGMP is a part of the IP layer, and IGMP has a fixed-size message.
• The IGMP message is encapsulated within an IP datagram.

The Format of IGMP message

Where,

Type: It determines the type of IGMP message. There are three types of IGMP message: Membership Query, Membership Report and Leave Report.

Maximum Response Time: This field is used only by the Membership Query message. It determines the maximum time the host can send the Membership Report message in response to the Membership Query message.

Checksum: It determines the entire payload of the IP datagram in which IGMP message is encapsulated.

Group Address: The behavior of this field depends on the type of the message sent.

• For Membership Query, the group address is set to zero for General Query and set to multicast group address for a specific query.
• For Membership Report, the group address is set to the multicast group address.
• For Leave Group, it is set to the multicast group address.

IGMP Messages

• Membership Query message
• This message is sent by a router to all hosts on a local area network to determine the set of all the multicast groups that have been joined by the host.
• It also determines whether a specific multicast group has been joined by the hosts on a attached interface.
• The group address in the query is zero since the router expects one response from a host for every group that contains one or more members on that host.
• Membership Report message
• The host responds to the membership query message with a membership report message.
• Membership report messages can also be generated by the host when a host wants to join the multicast group without waiting for a membership query message from the router.
• Membership report messages are received by a router as well as all the hosts on an attached interface.
• Each membership report message includes the multicast address of a single group that the host wants to join.
• IGMP protocol does not care which host has joined the group or how many hosts are present in a single group. It only cares whether one or more attached hosts belong to a single multicast group.
• The membership Query message sent by a router also includes a "Maximum Response time". After receiving a membership query message and before sending the membership report message, the host waits for the random amount of time from 0 to the maximum response time. If a host observes that some other attached host has sent the "Maximum Report message", then it discards its "Maximum Report message" as it knows that the attached router already knows that one or more hosts have joined a single multicast group. This process is known as feedback suppression. It provides the performance optimization, thus avoiding the unnecessary transmission of a "Membership Report message".
• Leave Report
  When the host does not send the "Membership Report message", it means that the host has left the group. The host knows that there are no members in the group, so even when it receives the next query, it would not report the group.

 

 

 

 

 

 

 

 

 

 

 

 

Routing algorithm

• In order to transfer the packets from source to the destination, the network layer must determine the best route through which packets can be transmitted.
• Whether the network layer provides datagram service or virtual circuit service, the main job of the network layer is to provide the best route. The routing protocol provides this job.
• The routing protocol is a routing algorithm that provides the best path from the source to the destination. The best path is the path that has the "least-cost path" from source to the destination.
• Routing is the process of forwarding the packets from source to the destination but the best route to send the packets is determined by the routing algorithm.

Classification of a Routing algorithm

The Routing algorithm is divided into two categories:

• Adaptive Routing algorithm
• Non-adaptive Routing algorithm

---

Adaptive Routing algorithm

• An adaptive routing algorithm is also known as dynamic routing algorithm.
• This algorithm makes the routing decisions based on the topology and network traffic.
• The main parameters related to this algorithm are hop count, distance and estimated transit time.

An adaptive routing algorithm can be classified into three parts:

• Centralized algorithm: It is also known as global routing algorithm as it computes the least-cost path between source and destination by using complete and global knowledge about the network. This algorithm takes the connectivity between the nodes and link cost as input, and this information is obtained before actually performing any calculation. Link state algorithm is referred to as a centralized algorithm since it is aware of the cost of each link in the network.
• Isolation algorithm: It is an algorithm that obtains the routing information by using local information rather than gathering information from other nodes.
• Distributed algorithm: It is also known as decentralized algorithm as it computes the least-cost path between source and destination in an iterative and distributed manner. In the decentralized algorithm, no node has the knowledge about the cost of all the network links. In the beginning, a node contains the information only about its own directly attached links and through an iterative process of calculation computes the least-cost path to the destination. A Distance vector algorithm is a decentralized algorithm as it never knows the complete path from source to the destination, instead it knows the direction through which the packet is to be forwarded along with the least cost path.

---

Non-Adaptive Routing algorithm

• Non Adaptive routing algorithm is also known as a static routing algorithm.
• When booting up the network, the routing information stores to the routers.
• Non Adaptive routing algorithms do not take the routing decision based on the network topology or network traffic.

The Non-Adaptive Routing algorithm is of two types:

Flooding: In case of flooding, every incoming packet is sent to all the outgoing links except the one from it has been reached. The disadvantage of flooding is that node may contain several copies of a particular packet.

Random walks: In case of random walks, a packet sent by the node to one of its neighbors randomly. An advantage of using random walks is that it uses the alternative routes very efficiently.

Differences b/w Adaptive and Non-Adaptive Routing Algorithm

Basis Of Comparison	Adaptive Routing algorithm	Non-Adaptive Routing algorithm
Define	Adaptive Routing algorithm is an algorithm that constructs the routing table based on the network conditions.	The Non-Adaptive Routing algorithm is an algorithm that constructs the static table to determine which node to send the packet.
Usage	Adaptive routing algorithm is used by dynamic routing.	The Non-Adaptive Routing algorithm is used by static routing.
Routing decision	Routing decisions are made based on topology and network traffic.	Routing decisions are the static tables.
Categorization	The types of adaptive routing algorithm, are Centralized, isolation and distributed algorithm.	The types of Non Adaptive routing algorithm are flooding and random walks.
Complexity	Adaptive Routing algorithms are more complex.	Non-Adaptive Routing algorithms are simple.

 

 

Distance Vector Routing Algorithm

• The Distance vector algorithm is iterative, asynchronous and distributed.
• Distributed: It is distributed in that each node receives information from one or more of its directly attached neighbors, performs calculation and then distributes the result back to its neighbors.
• Iterative: It is iterative in that its process continues until no more information is available to be exchanged between neighbors.
• Asynchronous: It does not require that all of its nodes operate in the lock step with each other.
• The Distance vector algorithm is a dynamic algorithm.
• It is mainly used in ARPANET, and RIP.
• Each router maintains a distance table known as Vector.

Three Keys to understand the working of Distance Vector Routing Algorithm:

• Knowledge about the whole network: Each router shares its knowledge through the entire network. The Router sends its collected knowledge about the network to its neighbors.
• Routing only to neighbors: The router sends its knowledge about the network to only those routers which have direct links. The router sends whatever it has about the network through the ports. The information is received by the router and uses the information to update its own routing table.
• Information sharing at regular intervals: Within 30 seconds, the router sends the information to the neighboring routers.

Distance Vector Routing Algorithm

Let d_x(y) be the cost of the least-cost path from node x to node y. The least costs are related by Bellman-Ford equation,

dx(y) = minv{c(x,v) + dv(y)}

Where the minv is the equation taken for all x neighbors. After traveling from x to v, if we consider the least-cost path from v to y, the path cost will be c(x,v)+d_v(y). The least cost from x to y is the minimum of c(x,v)+d_v(y) taken over all neighbors.

With the Distance Vector Routing algorithm, the node x contains the following routing information:

• For each neighbor v, the cost c(x,v) is the path cost from x to directly attached neighbor, v.
• The distance vector x, i.e., D_x = [ D_x(y) : y in N ], containing its cost to all destinations, y, in N.
• The distance vector of each of its neighbors, i.e., D_v = [ D_v(y) : y in N ] for each neighbor v of x.

Distance vector routing is an asynchronous algorithm in which node x sends the copy of its distance vector to all its neighbors. When node x receives the new distance vector from one of its neighboring vector, v, it saves the distance vector of v and uses the Bellman-Ford equation to update its own distance vector. The equation is given below:

dx(y) = minv{ c(x,v) + dv(y)}     for each node y in N

The node x has updated its own distance vector table by using the above equation and sends its updated table to all its neighbors so that they can update their own distance vectors.

Algorithm

At each node x,

Initialization

for all destinations y in N:

Dx(y) = c(x,y)     // If y is not a neighbor then c(x,y) = ∞

for each neighbor w

Dw(y) = ?     for all destination y in N.

for each neighbor w

send distance vector Dx = [ Dx(y)  : y in N ] to w

loop

  wait(until I receive any distance vector from some neighbor w)

  for each y in N:

  Dx(y) = minv{c(x,v)+Dv(y)}

If Dx(y) is changed for any destination y

Send distance vector Dx = [ Dx(y) : y in N ] to all neighbors

forever

Note: In Distance vector algorithm, node x update its table when it either see any cost change in one directly linked nodes or receives any vector update from some neighbor.

Let's understand through an example:

Sharing Information

• In the above figure, each cloud represents the network, and the number inside the cloud represents the network ID.
• All the LANs are connected by routers, and they are represented in boxes labeled as A, B, C, D, E, F.
• Distance vector routing algorithm simplifies the routing process by assuming the cost of every link is one unit. Therefore, the efficiency of transmission can be measured by the number of links to reach the destination.
• In Distance vector routing, the cost is based on hop count.

In the above figure, we observe that the router sends the knowledge to the immediate neighbors. The neighbors add this knowledge to their own knowledge and sends the updated table to their own neighbors. In this way, routers get its own information plus the new information about the neighbors.

Routing Table

Two process occurs:

• Creating the Table
• Updating the Table

Creating the Table

Initially, the routing table is created for each router that contains atleast three types of information such as Network ID, the cost and the next hop.

• NET ID: The Network ID defines the final destination of the packet.
• Cost: The cost is the number of hops that packet must take to get there.
• Next hop: It is the router to which the packet must be delivered.

• In the above figure, the original routing tables are shown of all the routers. In a routing table, the first column represents the network ID, the second column represents the cost of the link, and the third column is empty.
• These routing tables are sent to all the neighbors.

For Example:

1.    A sends its routing table to B, F & E.  

2.    B sends its routing table to A & C.  

3.    C sends its routing table to B & D.  

4.    D sends its routing table to E & C.  

5.    E sends its routing table to A & D.  

6.    F sends its routing table to A.  

Updating the Table

• When A receives a routing table from B, then it uses its information to update the table.
• The routing table of B shows how the packets can move to the networks 1 and 4.
• The B is a neighbor to the A router, the packets from A to B can reach in one hop. So, 1 is added to all the costs given in the B's table and the sum will be the cost to reach a particular network.

• After adjustment, A then combines this table with its own table to create a combined table.

• The combined table may contain some duplicate data. In the above figure, the combined table of router A contains the duplicate data, so it keeps only those data which has the lowest cost. For example, A can send the data to network 1 in two ways. The first, which uses no next router, so it costs one hop. The second requires two hops (A to B, then B to Network 1). The first option has the lowest cost, therefore it is kept and the second one is dropped.

• The process of creating the routing table continues for all routers. Every router receives the information from the neighbors, and update the routing table.

Final routing tables of all the routers are given below: