Unit 4 PPT NL

UNIT 4-UNIT IV NETWORK LAYER:
Introduction- Virtual Circuit and Datagram

Networks- What‘s Inside a Router- The Internet
Protocol (IP): IPv4 and IPv6, Addressing,
Forwarding, Fragmentation and Reassembly in
the InternetChallenges of IPv6- Routing
Algorithms- Routing in the Internet- Broadcast
and Multicast Routing
NETWORK LAYER
TOPICS TO BE COVERED:
• The network layer is also one of the most complex layers in the protocol stack.
• Two broad approaches towards structuring network-layer packet delivery—the datagram and the virtual-circuit
model.
• Addressing plays in delivering a packet to its destination host.
• Forwarding and Routing functions of the network layer
• Forwarding involves the transfer of a packet from an incoming link to an outgoing link within a single router.
• Routing involves all of a network’s routers, whose collective interactions via routing protocols determine the paths
that packets take on their trips from source to destination node.
• packet forwarding-we’ll look “inside” a router—at its hardware architecture and organization.
• Internet Protocol (IP),network-layer addressing and the IPv4 datagram format
• explore network address translation (NAT), datagram fragmentation, the Internet Control Message Protocol (ICMP),
and IPv6.
• job of a routing algorithm is to determine good paths (equivalently, routes) from senders to receivers.
• classes of algorithms- link-state and distance vector algorithms
• Internet’s intra-autonomous system routing protocols (RIP, OSPF, and IS-IS) and its inter-autonomous system
routing protocol, BGP.
3 PARTS TO BE COVERED:
PART 1: Network-layer functions and services

PART 2: Forwarding
PART 3:Routing
Simple network with two hosts, H1 and H2, and several routers
Simple network with two hosts, H1 and H2, and several routers
• Simple network with two hosts, H1 and H2, and several routers on the path
between H1 and H2.
• Suppose that H1 is sending information to H2, and consider the role of the
network layer in these hosts and in the intervening routers.
1. The network layer in H1 takes segments from the transport layer in H1,
encapsulates each segment into a datagram (that is, a network-layer
packet), and then sends the datagrams to its nearby router, R1.
2. At the receiving host, H2, the network layer receives the datagrams from its
nearby router R2, extracts the transport-layer segments, and delivers the
segments up to the transport layer at H2.
• The primary role of the routers is to forward datagrams from input links to
output links.
• Routers do not run application- and transport-layer protocols
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.
2. 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.
3. Internetworking: This is the main role of the network layer that it provides
the logical connection between different types of networks.
4. Fragmentation: The fragmentation is a process of breaking the packets into
the smallest individual data units that travel through different networks.
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.
• Each host contains its own interface and IP address.
• 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.
IP address:
• IP address is an address having information about how to reach a
specific host, especially outside the LAN. An IP address is a 32 bit
unique address having an address space of 2^32.
• Generally, there are two notations in which IP address is written,
dotted decimal notation and hexadecimal notation.
• Dotted Decimal Notation:
Hexadecimal Notation:
1 )128.11.3.31 in hexadecimal is: 80.0B.03.1F
128%16=8(quotient) and remainder :0 Therefore 128---> 80
11%16=0 (quotient) and remainder:11 which is c. Therefore 11--> 0B
3%16=0 (quotient) and remainder : 3 Therefore 3--> 03
31%16=1(quotient) and remainder : 15 which is F. Therefore 31-->1F
2)The IP address 192.168. 1.1 can be represented in hexadecimal as

C0. A8. 01.01.
Some points to be noted about dotted decimal
notation:
• The value of any segment (byte) is between 0 and 255 (both
included).
• There are no zeroes preceding the value in any segment (054 is
wrong, 54 is correct).
• Note: IP addresses are globally managed by Internet Assigned
Numbers Authority(IANA) and regional Internet registries(RIR).
• Note: While finding the total number of host IP addresses, 2 IP
addresses are not counted and are therefore, decreased from the
total count because the first IP address of any network is the network
number and whereas the last IP address is reserved for broadcast IP.
Classful Addressing
• Classful addressing is an early method of IP address allocation in which the IP address
space is divided into five different classes (A, B, C, D, and E) to accommodate networks of
different sizes. It is based on the first few bits of an IP address, which determine the class
and, consequently, the network size and address range.
• An IP address is 32-bit long. An IP address is divided into sub-classes:
1. Class A
2. Class B
3. Class C
4. Class D
5. Class E
An ip address is divided into two parts:
A. Network ID: It represents the number of networks.
B. Host ID: It represents the number of hosts.
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^7 = 128 network address
The total number of hosts in Class A = 2^24 - 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^14 = 16384 network address
• The total number of hosts in Class B = 2^16 - 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.
• 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^21 = 2097152 network address
• The total number of hosts = 2^8 - 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:
1. The Host ID must be unique within any network.
2. 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.
3. 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:
1. The network ID cannot start with 127 as 127 is used by Class A.
2. 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.
3. 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 HOST ID No.of No.of Range
bits bits networks hosts per
network
A 0 8 24 2^7 2^24 0.0.0.0 to 127.255.255.255
B 10 16 16 2^14 2^16 128.0.0.0 to 191.255.255.255
C 110 24 8 2^21 2^8 192.0.0.0 to 223.255.255.255
D 1110 NOT NOT NOT NOT 224.0.0.0 to 239.255.255.255

DEFINED DEFINED DEFINED DEFINED
E 1111 NOT NOT NOT NOT 240.0.0.0 to 255.255.255.255

DEFINED DEFINED DEFINED DEFINED
class A
• IP address belonging to class A are assigned to the networks that contain a large
number of hosts.
• The higher order bit of the first octet in class A is always set to 0. The remaining 7
bits in first octet are used to determine network ID. The 24 bits of host ID are used
to determine the host in any network. The default subnet mask for class A is
255.x.x.x.
• Therefore, class A has a total of:
• 2^7-2= 126 network ID(Here 2 address is subracted because 0.0.0.0 and 127.x.y.z
are special address. )
• 2^24 – 2 = 16,777,214 host ID
• IP addresses belonging to class A ranges from 1.x.x.x – 126.x.x.x
Class B:
IP address belonging to class B are assigned to the networks that ranges from medium-
sized to large-sized networks.
• The higher order bits of the first octet of IP addresses of class B are always set to 10.
The remaining 14 bits are used to determine network ID. The 16 bits of host ID is used
to determine the host in any network. The default sub-net mask for class B is
255.255.x.x. Class B has a total of:
• 2^14 = 16384 network address
• 2^16 – 2 = 65534 host address
• IP addresses belonging to class B ranges from 128.0.x.x – 191.255.x.x.
Class C:
IP address belonging to class C are assigned to small-sized networks.
• The higher order bits of the first octet of IP addresses of class C are always set to 110.
The remaining 21 bits are used to determine network ID. The 8 bits of host ID is used to
determine the host in any network. The default sub-net mask for class C is
255.255.255.x. Class C has a total of:
• 2^21 = 2097152 network address
• 2^8 – 2 = 254 host address
• IP addresses belonging to class C ranges from 192.0.0.x – 223.255.255.x.
Class D:
• IP address belonging to class D are reserved for multi-casting. The
higher order bits of the first octet of IP addresses belonging to class D
are always set to 1110. The remaining bits are for the address that
interested hosts recognize.
• Class D does not posses any sub-net mask. IP addresses belonging to
class D ranges from 224.0.0.0 – 239.255.255.255.
Class E:
• IP addresses belonging to class E are reserved for experimental and

research purposes. IP addresses of class E ranges from 240.0.0.0 –
255.255.255.254. This class doesn’t have any sub-net mask. The
higher order bits of first octet of class E are always set to 1111.
Range of special IP addresses:
• 169.254.0.0 – 169.254.0.16 : Link local addresses

• 127.0.0.0 – 127.0.0.8 : Loop-back addresses
• 0.0.0.0 – 0.0.0.8 : used to communicate within the current network.
Rules for assigning Host ID:
• Host ID’s are used to identify a host within a network. The host ID are
assigned based on the following rules:
• Within any network, the host ID must be unique to that network.

• Host ID in which all bits are set to 0 cannot be assigned because this
host ID is used to represent the network ID of the IP address.
• Host ID in which all bits are set to 1 cannot be assigned because this
host ID is reserved as a broadcast address to send packets to all the
hosts present on that particular network.
Rules for assigning Network ID:
• Hosts that are located on the same physical network are identified by the
network ID, as all host on the same physical network is assigned the same
network ID. The network ID is assigned based on the following rules:
• The network ID cannot start with 127 because 127 belongs to class A address
and is reserved for internal loop-back functions.
• All bits of network ID set to 1 are reserved for use as an IP broadcast address
and therefore, cannot be used.
• All bits of network ID set to 0 are used to denote a specific host on the local
network and are not routed and therefore, aren’t used.
Summary of Classful addressing :
Problems with Classful Addressing:
• Classful addressing was inefficient because it assigned large blocks of
addresses regardless of the actual network size. This led to wasted addresses
and inefficient usage of the IP address space. To address this, Classless Inter-
Domain Routing (CIDR) was introduced, allowing more flexible allocation of IP
addresses.
• The problem with this classful addressing method is that millions of class A
address are wasted, many of the class B address are wasted, whereas, number
of addresses available in class C is so small that it cannot cater the needs of
organizations.
• Class D addresses are used for multicast routing and are therefore available as
a single block only. Class E addresses are reserved.
• Since there are these problems, Classful networking was replaced by Classless
Inter-Domain Routing (CIDR) in 1993.
Classless Inter Domain Routing (CIDR)
• which is also known as Classless addressing. In the Classful addressing
the no of Hosts within a network always remains the same depending
upon the class of the Network.
• Class A network contains 2^24 Hosts,

• Class B network contains 2^16 Hosts,
• Class C network contains 2^8 Hosts
• Now, let’s suppose an Organization requires 2^14 hosts, then it must
have to purchase a Class B network. In this case, 49152 Hosts will be
wasted. This is the major drawback of Classful Addressing.
• In order to reduce the wastage of IP addresses a new concept of
Classless Inter-Domain Routing is introduced. Now a days IANA is
using this technique to provide the IP addresses. Whenever any user
asks for IP addresses, IANA is going to assign that many IP addresses
to the User.
• Representation: It is as also a 32-bit address, which includes a special number which represents the
number of bits that are present in the Block Id.
• a.b.c.d/n
• Where, n is number of bits that are present in Block Id / Network Id.
• Example:
• 20.10.50.100/20
Rules for forming CIDR Blocks:
1.All IP addresses must be contiguous.
2.Block size must be the power of 2 (2n).
• If the size of the block is the power of 2, then it will be easy to divide the Network. Finding out the
Block Id is very easy if the block size is of the power of 2.
• Example:
• If the Block size is 25 then, Host Id will contain 5 bits and Network will contain 32 – 5 = 27 bits.
3.First IP address of the Block must be evenly divisible by the size of the block.
in simple words, the least significant part should always start with zeroes in Host
Id. Since all the least significant bits of Host Id is zero, then we can use it as
Block Id part.
Example:
Check whether 100.1.2.32 to 100.1.2.47 is a valid IP address block or not?
1. All the IP addresses are contiguous.
2. Total number of IP addresses in the Block = 16 = 2^4.
3. 1st IP address: 100.1.2.00100000
Since, Host Id will contains last 4 bits and all the least significant 4 bits
are zero. Hence, first IP address is evenly divisible by the size of the block.
All the three rules are followed by this Block. Hence, it is a valid IP address
block.
IPV4 ADDRESSES
• The identifier used in the IP layer of the TCP/IP protocol suite to identify the
connec_x0002_tion of each device to the Internet is called the Internet
address or IP address.
• An IPv4 address is a 32-bit address that uniquely and universally defines the
connection of a host or a router to the Internet.
• The IP address is the address of the connection, not the host or the router,
because if the device is moved to another network, the IP address may be
changed.
• IPv4 addresses are unique in the sense that each address defines one, and
only one,connection to the Internet. If a device has two connections to the
Internet, via two networks, it has two IPv4 addresses.
IPV4-Address Space
• An address space is the total number of addresses used by the protocol.
• If a protocol uses b bits to define an address, the address space is 2b
• because each bit can have two different values (0 or 1).
• IPv4 uses 32-bit addresses, which means that the address space is 2^32 or
4,294,967,296(more than 4 billion devices could be connected to the Internet)
• Notation
• There are three common notations to show an IPv4 address: binary notation (base 2),
dotted-decimal notation (base 256), and hexadecimal notation (base 16). In binary
notation, an IPv4 address is displayed as 32 bits.
• Each hexadecimal digit is equivalent to four bits. This means that a 32-bit address has 8
hexadecimal digits. This notation is often used in network programming.
Hierarchy in Addressing
• In a postal network, the postal address (mailing address) includes the
country, state, city, street, house number, and the name of the mail
recipient. Similarly, a telephone number is divided into the country
code, area code, local exchange, and the connection.
• A 32-bit IPv4 address is also hierarchical, but divided only into two
parts. The first part of the address, called the prefix, defines the
network; the second part of the address, called the suffix, defines the
node.
• Classful Addressing
• When the Internet started, an IPv4 address was designed with a fixed-length prefix, but to
accommodate both small and large networks, three fixed-length prefixes were designed instead of
one (n = 8, n = 16, and n = 24). The whole address space was divided into five classes (class A, B, C, D,
and E)This scheme is referred to as classful addressing.
• In class A, the network length is 8 bits, but since the first bit, which is 0, defines the class, we can
have only seven bits as the network identifier. This means there are only 2^7 = 128 networks in the
world that can have a class A address.
• In class B, the network length is 16 bits, but since the first two bits, which are (10)2, define the
class, we can have only 14 bits as the network identifier. This means there are only 2^14 = 16,384
networks in the world that can have a class B address.
• All addresses that start with (110)2 belong to class C. In class C, the network length is 24 bits, but
since three bits define the class, we can have only 21 bits as the network identifier. This means
there are 2^21 = 2,097,152 networks in the world that can have a class C address.
• Class D is not divided into prefix and suffix. It is used for multicast addresses. All addresses that
start with 1111 in binary belong to class E. As in Class D, Class E is not divided into prefix and
suffix and is used as reserve.
Address DepletionThe reason that classful addressing has become obsolete is address depletion.
Since the addresses were not distributed properly, the Internet was faced with the problem of
the addresses being rapidly used up, resulting in no more addresses available for organizations
and individuals that needed to be connected to the Internet.
Address Depletion
• Let us think about class A. This class can be assigned to only 128 organizations
in the world, but each organization needs to have a single network (seen by
the rest of the world) with 16,777,216 nodes (computers in this single
network). Since there may be only a few organizations that are this large, most
of the addresses in this class were wasted (unused).
• Class B addresses were designed for midsize organizations, but many of the
addresses in this class also remained unused.
• Class C addresses have a completely different flaw in design. The number of
addresses that can be used in each network (256) was so small that most
companies were not comfortable using a block in this address class.
• Class E addresses were almost never used, wasting the whole class.
Subnetting and Supernetting
• To alleviate address depletion, two strategies were proposed(subnetting and supernetting)
In subnetting, a class A or class B block is divided into several subnets. Each subnet has a larger prefix length than
the original network.
• For example, if a network in class A is divided into four subnets, each subnet has a prefix of nsub = 10. At the same
time, if all of the addresses in a network are not used, subnetting allows the addresses to be divided among several
organizations.
• This idea did not work because most large organizations were not happy about dividing the block and giving some
of the unused addresses to smaller organizations.
• While subnetting was devised to divide a large block into smaller ones, supernetting was devised to combine
several class C blocks into a larger block to be attractive to organizations that need more than the 256 addresses
available in a class C block. Thisidea did not work either because it makes the routing of packets more difficult.
• Advantage of Classful Addressing
• Although classful addressing had several problems and became obsolete, it had one advantage:
• Given an address, we can easily find the class of the address and, since the prefix length for each class is fixed, we
can find the prefix length immediately.
• In other words, the prefix length in classful addressing is inherent in the address; no extra information is needed to
extract the prefix and the suffix.
Classless Addressing
• Subnetting and supernetting in classful addressing did not really solve
the address depletion problem.
• With the growth of the Internet, it was clear that a larger address
space was needed as a long-term solution.
• The larger address space, however, requires that the length of IP
addresses also be increased, which means the format of the IP
packets needs to be changed.
• Although the long-range solution has already been devised and is
called IPv6 (discussed later), a short-term solution was also devised to
use the same address space but to change the distribution of
addresses to provide a fair share to each organization.
• The short-term solution still uses IPv4 addresses, but it is called
classless addressing. In other words, the class privilege was removed
from the distribution to compensate for the address depletion.
• There was another motivation for classless addressing. During the 1990s, Internet Service
Providers (ISPs) came into prominence.
• An ISP is an organization that provides Internet access for individuals, small businesses, and
midsize organizations that do not want to create an Internet site and become involved in
providing Internet services (such as electronic mail) for their employees.
• An ISP can provide these services.
• An ISP is granted a large range of addresses and then subdivides the addresses (in groups of 1, 2,
4, 8, 16, and so on), giving a range of addresses to a household or a small business. The customers
are connected via a dial-up modem, DSL, or cable modem to the ISP. However, each customer
needs some IPv4 addresses.
• In 1996, the Internet authorities announced a new architecture called classless addressing. In
classless addressing, variable-length blocks are used that belong to no classes. We can have a
block of 1 address, 2 addresses, 4 addresses, 128 addresses, and so on.
• In classless addressing, the whole address space is divided into variable length blocks. The prefix
in an address defines the block (network); the suffix defines the node (device). Theoretically, we
can have a block of 2^0, 2^1 , 2^2, ..., 2^32 addresses.
• One of the restrictions, as we discuss later, is that the number of addresses in a block needs to be
a power of 2. An organization can be granted one block of addresses.
Unlike classful addressing, the prefix length in classless addressing is variable. We
can have a prefix length that ranges from 0 to 32. The size of the network is inversely
proportional to the length of the prefix. A small prefix means a larger network; a
large prefix means a smaller network. classful addressing is a special case of classless
addressing.
Prefix Length: Slash Notation
• The first question that we need to answer in classless addressing is
how to find the pre_x0002_fix length if an address is given. Since the
prefix length is not inherent in the address, we need to separately
give the length of the prefix.
• In this case, the prefix length, n, is added to the address, separated by
a slash.
• The notation is informally referred to as slash notation and formally
as classless interdomain routing or CIDR (pronounced cider) strategy.
Extracting Information from an Address
• Given any address in the block, we normally like to know three pieces
of information about the block to which the address belongs:
• The number of addresses, the first address in the block, and the last
address. Since the value of prefix length, n, is given, we can easily find
these three pieces of information, as shown in Figure.
1. The number of addresses in the block is found as N = 2^32−n
2. To find the first address, we keep the n leftmost bits and set the
(32 − n) rightmost bits all to 0s.
3. To find the last address, we keep the n leftmost bits and set the
(32 − n) rightmost bits all to 1s.
Example-A classless address is given as 167.199.170.82/27. We can find
the above three pieces of information
• The number of addresses in the network is 2^(32 − n) = 2^5= 32

addresses.
Find the first and last addresses in the block
Method 1((GIVEN ADDRESS: 167.199.170.82/27 )
SOLUTION:
• The first address can be found by keeping the first 27 bits and
changing the rest of the bits to 0s.
• Address: 167.199.170.82/27 10100111 11000111 10101010 01010010
• First address: 167.199.170.64/27 10100111 11000111 10101010 01000000
• The last address can be found by keeping the first 27 bits and changing the rest
of the bits to 1s.
• Address: 167.199.170.82/27 10100111 11000111 10101010 01011111
• Last address: 167.199.170.95/27 10100111 11000111 10101010 01011111
Method 2:Address Mask:
• The address mask is a 32-bit number in which the n leftmost bits are set to 1s and the rest of the bits (32 − n) are set
to 0s. A computer can easily find the address mask because it is the complement of (2^ (32 − n − 1)).
• The default mask in different classes are :
• Class A – 255.0.0.0
• Class B – 255.255.0.0
• Class C – 255.255.255.0
• The reason for defining a mask in this way is that it can be used by a computer program to extract the information in
a block, using the three bit-wise operations NOT, AND, and OR.
• 1. The number of addresses in the block N = NOT (mask) + 1.
• 2. The first address in the block = (Any address in the block) AND (mask).
• 3. The last address in the block = (Any address in the block) OR [(NOT (mask)].
Example:The mask in dotted-decimal notation is 256.256.256.224. The AND, OR, and NOT operations can be applied
to individual bytes using calculators and applets at the book website.
Number of addresses in the block: N = NOT (mask) + 1= 0.0.0.31 + 1 = 32 addresses
First address: First = (address) AND (mask) = 167.199.170.82
Last address: Last = (address) OR (NOT mask) = 167.199.170.255
Special Addresses( this-host address, limited-broadcast address, loopback address, private
addresses, and multicast addresses.)
This-host Address
• The only address in the block 0.0.0.0/32 is called the this-host
address. It is used whenever a host needs to send an IP datagram but
it does not know its own address to use as the source address.
Limited-broadcast Address
• The only address in the block 255.255.255.255/32 is called the
limited-broadcast address. It is used whenever a router or a host
needs to send a datagram to all devices in a network. The routers in
the network, however, block the packet having this address as the
destination; the packet cannot travel outside the network.
Special Addresses( this-host address, limited-broadcast address, loopback address, private
addresses, and multicast addresses.)
Loopback Address
• The block 127.0.0.0/8 is called the loopback address. A packet with one of the
addresses in this block as the destination address never leaves the host; it will
remain in the host. Any address in the block is used to test a piece of software
in the machine.
• For example, we can write a client and a server program in which one of the
addresses in the block is used as the server address. We can test the programs
using the same host to see if they work before running them on different
computers.
Private Addresses
• Four blocks are assigned as private addresses: 10.0.0.0/8, 172.16.0.0/12,
192.168.0.0/16, and 169.254.0.0/16.
Multicast Addresses
• The block 224.0.0.0/4 is reserved for multicast addresses.
IPV4
• The network layer is the third layer (from bottom) in the OSI Model.
• The network layer is concerned with the delivery of a packet across multiple
networks.
• The network layer is considered the backbone of the OSI Model.
• It selects and manages the best logical path for data transfer between nodes.
• This layer contains hardware devices such as routers, bridges, firewalls, and
switches, but it actually creates a logical image of the most efficient
communication route and implements it with a physical medium.
• Network layer protocols exist in every host or router. The router examines the
header fields of all the IP packets that pass through it.
• Internet Protocol and Netware IPX/SPX are the most common protocols
associated with the network layer.
IPV4 HEADER FORMAT
• VERSION: Version of the IP protocol (4 bits), which is 4 for IPv4
• HLEN: IP header length (4 bits), which is the number of 32 bit words in the header. The minimum value for
this field is 5 and the maximum is 15.
• Type of service: Low Delay, High Throughput, Reliability (8 bits)
• Total Length: Length of header + Data (16 bits), which has a minimum value 20 bytes and the maximum is
65,535 bytes.
• Identification: Unique Packet Id for identifying the group of fragments of a single IP datagram (16 bits)
• Flags: 3 flags of 1 bit each : reserved bit (must be zero), do not fragment flag, more fragments flag (same
order)
• Fragment Offset: Represents the number of Data Bytes ahead of the particular fragment in the particular
Datagram. Specified in terms of number of 8 bytes, which has the maximum value of 65,528 bytes.
• Time to live: Datagram’s lifetime (8 bits), It prevents the datagram to loop through the network by restricting
the number of Hops taken by a Packet before delivering to the Destination.
• Protocol: Name of the protocol to which the data is to be passed (8 bits)
• Header Checksum: 16 bits header checksum for checking errors in the datagram header
• Source IP address: 32 bits IP address of the sender
• Destination IP address: 32 bits IP address of the receiver
• Option: Optional information such as source route, record route. Used by the Network administrator to
check whether a path is working or not. Due to the presence of options, the size of the datagram header can
be of variable length (20 bytes to 60 bytes).
Internet Protocol version 6 (IPv6) Header
• IP version 6 is the new version of Internet Protocol, which is way
better than IP version 4 in terms of complexity and efficiency.
IPv6 Header FORMAT
• Version (4-bits) : Indicates version of Internet Protocol which contains
bit sequence 0110.
• Traffic Class (8-bits) : The Traffic Class field indicates class or priority of
IPv6 packet which is similar to Service Field in IPv4 packet. It helps
routers to handle the traffic based on priority of the packet. If
congestion occurs on router then packets with least priority will be
discarded.
• As of now only 4-bits are being used (and remaining bits are under
research), in which 0 to 7 are assigned to Congestion controlled traffic
and 8 to 15 are assigned to Uncontrolled traffic.
• Priority assignment of Congestion controlled traffic :
Differences between Virtual Circuits & Datagram Networks
Key Virtual Circuits Datagram Networks
Definition Virtual Circuit is the connection oriented service On other hand Datagram is the connection less
in which there is a implementation of resources service where no such resources are required for
like buffers, CPU, bandwidth, etc., used by the data transmission.
virtual circuit for a data transfer session.
Path In Virtual circuits as all the resources and On other hand in case Datagram network, the
bandwidth get reserved before the path is not fixed as data packets are free to
transmission, the path which is utilized or decide the path on any intermediate router on
followed by first data packet would get fixed the go by dynamically changing routing tables
and all other data packets will use the same on routers.
path and consume same resources.
Header Same path followed by all the data packets, a On other hand different headers with
common and same header is being used by all information of other data packet is being used in
the packets. Datagram network.
Differences between Virtual Circuits & Datagram Networks
Key Virtual Circuits Datagram Networks
Complexity Virtual Circuit is less complex as compared to More complex as compared to Virtual
that of Datagram network. circuit.
Reliability Due to fixed path and assurance of fixed On other hand Datagram network due to
resources, Virtual Circuits are more reliable for dynamic resource allocation and follow
data transmission as compared to Datagram dynamic path is more prone to error and is
network. less reliable than Virtual circuits.
Example and Virtual circuits are costlier in installation and Datagram network are cheaper as
Cost maintenance and are widely used by ATM compared to the Virtual Circuits and are
(Asynchronous Transfer Mode) Network, mainly used by IP network, which is used
which is used for the Telephone calls. for Data services like Internet.
Virtual Circuits:
1. It is connection-oriented, meaning that there is a reservation of resources like buffers, CPU,
bandwidth, etc. for the time in which the newly setup VC is going to be used by a data transfer
session.
2. The first sent packet reserves resources at each server along the path. Subsequent packets will
follow the same path as the first sent packet for the connection time.
3. Since all the packets are going to follow the same path, a global header is required. Only the first
packet of the connection requires a global header, the remaining packets generally don’t require
global headers.
4. Since all packets follow a specific path, packets are received in-order at the destination.
5. Virtual Circuit Switching ensures that all packets successfully reach the Destination. No packet
will be discarded due to unavailability of resources.
6. From the above points, it can be concluded that Virtual Circuits are a highly reliable method of
data transfer.
7. The issue with virtual circuits is that each time a new connection is set up, resources and extra
information have to be reserved at every router along the path, which becomes problematic if
many clients are trying to reserve a routers resources simultaneously.
8. It is used by the ATM (Asynchronous Transfer Mode) Network, specifically for Telephone calls.
Datagram Networks :
1. It is a connection-less service. There is no need for reservation of resources as there is no
dedicated path for a connection session.
2. All packets are free to use any available path. As a result, intermediate routers calculate routes
on the go due to dynamically changing routing tables on routers.
3. Since every packet is free to choose any path, all packets must be associated with a header with
proper information about the source and the upper layer data.
4. The connection-less property makes data packets reach the destination in any order, which
means that they can potentially be received out of order at the receiver’s end.
5. Datagram networks are not as reliable as Virtual Circuits.
6. The major drawback of Datagram Packet switching is that a packet can only be forwarded if
resources such as the buffer, CPU, and bandwidth are available. Otherwise, the packet will be
discarded.
7. But it is always easy and cost-efficient to implement datagram networks as there is no extra
headache of reserving resources and making a dedicated each time an application has to
communicate.
8. It is generally used by the IP network, which is used for Data services like the Internet.
Other Services-NETWORK LAYER
1. Error Control-the network layer in the Internet does not directly provide error control,
the Internet uses an auxiliary protocol, ICMP, that provides some kind of error control
if the datagram is discarded or has some unknown information in the header.
2. Flow Control-The network layer in the Internet, however, does not directly provide
any flow con_x0002_trol. The datagrams are sent by the sender when they are ready,
without any attention to the readiness of the receiver.
3. Congestion Control
4. Quality of Service-multimedia communication (in particular real-time communication
of audio and video), the quality of service (QoS) of the communication has become
more and more important.
5. Security-To provide security for a connectionless network layer, we need to have
another virtual level that changes the connectionless service to a connection-oriented
service.
NETWORK-LAYER PERFORMANCE
• The performance of a network can be measured in terms of delay, throughput, and
packet loss. Congestion control is an issue that can improve the performance.
1. Delay(Transmission Delay,Propagation Delay,Processing Delay,Queuing Delay,Total
Delay)
2. Throughput
3. Packet Loss
4. Congestion Control( open-loop congestion control (prevention) and closed-loop
congestion control (removal))
• open-loop congestion control -Retransmission Policy,Window Policy,Acknowledgment
Policy,Discarding Policy,Admission Policy)
• closed-loop congestion control-Backpressure,Choke Packet,Implicit Signaling,Explicit
Signaling)
I Delay
• The delays in a network can be divided into four types: transmission delay, propagation
delay, processing delay, and queuing delay.
A)Transmission Delay:
• A source host or a router cannot send a packet instantaneously. A sender needs to put
the bits in a packet on the line one by one. If the first bit of the packet is put on the line
at time t1 and the last bit is put on the line at time t2, transmission delay of the packet is
(t2 − t1).
Delaytr = (Packet length) / (Transmission rate).
B)Propagation Delay:
Propagation delay is the time it takes for a bit to travel from point A to point B in the
trans_x0002_mission media. The propagation delay for a packet-switched network
depends on the propagation delay of each network (LAN or WAN). The propagation delay
depends on the propagation speed of the media, which is 3 × 10^8 meters/second in a
vacuum and normally much less in a wired medium; it also depends on the distance of the
link. In other words, propagation delay is
Delaypg = (Distance) / (Propagation speed).
C)Processing Delay
• The processing delay is the time required for a router or a destination host to receive a packet
from its input port, remove the header, perform an error detection procedure, and deliver the
packet to the output port (in the case of a router) or deliver the packet to the upper-layer
protocol
Delaypr = Time required to process a packet in a router or a destination host
D)Queuing Delay
Queuing delay can normally happen in a router. The queuing delay for a packet in a router is
measured as the time a packet waits in the input queue and output queue of a router.
Delayqu = The time a packet waits in input and output queues in a router
E)Total Delay
Assuming equal delays for the sender, routers, and receiver, the total delay (source-
to_x0002_destination delay) Total delay = (n + 1) (Delaytr + Delaypg + Delaypr) + (n) (
Delayqu)
For n routers, we have (n + 1) links.
II Throughput
• Throughput at any point in a network is defined as the number of bits passing
through the point in a second, which is actually the transmission rate of data
at that point.
Throughput = minimum {TR1, TR2, . . . TRn}.
TR: Transmission rate
III Packet Loss -
Number of packets lost during transmission
The effect of packet loss on the Internet network layer is that the packet needs
to be resent, which in turn may create overflow and cause more packet loss.
IV Congestion Control
• Congestion control is a mechanism for improving performance.
• congestion at the network layer is not explicitly addressed in the Internet model.
• Congestion at the network layer is related to two issues, throughput and delay.
i. When the load is much less than the capacity of the network, the delay is at a minimum. This minimum delay is
composed of propagation delay and processing delay, both of which are negligible.
ii. However, when the load reaches the network capacity, the delay increases sharply because we now need to add the
queuing delay to the total delay.
iii. Note that the delay becomes infinite when the load is greater than the capacity.
iv. When the load is much less than the capacity of the network, the delay is at a minimum. This minimum delay is
composed of propagation delay and processing delay, both of which are negligible.
v. However, when the load reaches the network capacity, the delay increases sharply because we now need to add the
queuing delay to the total delay.
vi. Note that the delay becomes infinite when the load is greater than the capacity .
vii. When the load is below the capacity of the network, the throughput increases pro_x0002_portionally with the load. We
expect the throughput to remain constant after the load reaches the capacity, but instead the throughput declines
sharply.
viii. The reason is the discarding of packets by the routers. When the load exceeds the capacity, the queues become full and
the routers have to discard some packets. Discarding packets does not reduce the number of packets in the network
because the sources retransmit the packets, using time-out mechanisms, when the packets do not reach the
destinations.
Congestion Control
• Congestion control refers to techniques and mechanisms that can either prevent
congestion before it happens or remove congestion after it has happened. In general, we
can divide congestion control mechanisms into two broad categories: open-loop
congestion control (prevention) and closed-loop congestion control (removal).
I)Open-Loop Congestion Control
• In open-loop congestion control, policies are applied to prevent congestion before it
happens. In these mechanisms, congestion control is handled by either the source or the
destination.
A)Retransmission Policy
• Retransmission is sometimes unavoidable. If the sender feels that a sent packet is lost or
corrupted, the packet needs to be retransmitted. Retransmission in general may increase
congestion in the network. However, a good retransmission policy can prevent
congestion. The retransmission policy and the retransmission timers must be designed to
optimize efficiency and at the same time prevent congestion.
B)Window Policy
• The type of window at the sender may also affect congestion. The Selective Repeat window is
better than the Go-Back-N window for congestion control.
• In the Go-Back-N window, when the timer for a packet times out, several packets may be resent,
although some may have arrived safe and sound at the receiver. This duplication may make the
congestion worse.
• The Selective Repeat window, on the other hand, tries to send the specific packets that have been
lost or corrupted.
C)Acknowledgment Policy
• The acknowledgment policy imposed by the receiver may also affect congestion. If the receiver
does not acknowledge every packet it receives, it may slow down the sender and help prevent
congestion.
• Several approaches are used in this case. A receiver may send an acknowledgment only if it has a
packet to be sent or a special timer expires. A receiver may decide to acknowledge only N packets
at a time.
• We need to know that the acknowledgments are also part of the load in a network. Sending fewer
acknowledgments means imposing less load on the network.
Packet delay and throughput as functions of load
D)Discarding Policy
• A good discarding policy by the routers may prevent congestion and at the
same time may not harm the integrity of the transmission. For example, in
audio transmission, if the policy is to discard less sensitive packets when
congestion is likely to happen, the quality of sound is still preserved and
congestion is prevented or alleviated.
E)Admission Policy
• An admission policy, which is a quality-of-service mechanism can also
prevent congestion in virtual-circuit networks. Switches in a flow first check
the resource requirement of a flow before admitting it to the network. A
router can deny establishing a virtual-circuit connection if there is congestion
in the network or if there is a possibility of future congestion.
II)Closed-Loop Congestion Control
• Closed-loop congestion control mechanisms try to alleviate congestion after it
hap_x0002_pens. Several mechanisms have been used by different protocols.
We describe a few of them here.
A)Backpressure
• The technique of backpressure refers to a congestion control mechanism in which a
congested node stops receiving data from the immediate upstream node or nodes. This
may cause the upstream node or nodes to become congested, and they, in turn, reject
data from their upstream node or nodes, and so on. Backpressure is a node to-node
congestion control that starts with a node and propagates, in the opposite direction of
data flow, to the source. The backpressure technique can be applied only to virtual circuit
networks, in which each node knows the upstream node from which a flow of data is
coming.
B)Choke Packet
• A choke packet is a packet sent by a node to the source to inform it
of congestion. Note the difference between the backpressure and
choke-packet methods.
• In backpressure, the warning is from one node to its upstream node,
although the warning may eventually reach the source station.
• In the choke-packet method, the warning is from the router, which
has encountered congestion, directly to the source station. The
intermediate nodes through which the packet has traveled are not
warned.
C)Implicit Signaling
• In implicit signaling, there is no communication between the congested node
or nodes and the source. The source guesses that there is congestion
somewhere in the network from other symptoms.
• For example, when a source sends several packets and there is no
acknowledgment for a while, one assumption is that the network is
congested. The delay in receiving an acknowledgment is interpreted as
congestion in the network; the source should slow down.
D)Explicit Signaling
• The node that experiences congestion can explicitly send a signal to the
source or destination. The explicit-signaling method, however, is different
from the choke-packet method. In the choke-packet method, a separate
packet is used for this purpose;
• in the explicit-signaling method, the signal is included in the packets that carry
data. Explicit signaling can occur in either the forward or the backward
direction.
Dynamic Host Configuration Protocol (DHCP)
• Obtaining a Host Address: the Dynamic Host Configuration Protocol
ICMP
What is a Router?
• The router is a physical or virtual internetworking device that is designed to receive, analyze, and forward data
packets between computer networks.
• A router examines a destination IP address of a given data packet, and it uses the headers and forwarding tables to
decide the best way to transfer the packets.
• There are some popular companies that develop routers; such are Cisco, 3Com, HP, Juniper, D-Link, Nortel, etc.
• A router is used in LAN (Local Area Network) and WAN (Wide Area Network) environments. For example, it is used
in offices for connectivity, and you can also establish the connection between distant networks .
• It shares information with other routers in networking.
• It uses the routing protocol to transfer the data across a network.
• it is more expensive than other networking devices like switches and hubs.
• A router works on the third layer of the OSI model, and it is based on the IP address of a computer.
• It uses protocols such as ICMP to communicate between two or more networks.
• It is also known as an intelligent device as it can calculate the best route to pass the network packets from source
to the destination automatically.
Router
virtual router
• A virtual router is a software function or software-based framework
that performs the same functions as a physical router.
• It may be used to increase the reliability of the network by virtual
router redundancy protocol, which is done by configuring a virtual
router as a default gateway.
• A virtual router runs on commodity servers, and it is packaged with
alone or other network functions, like load balancing, firewall packet
filtering, and wide area network optimization capabilities.
How does Router work?
• A router analyzes a destination IP address of a
given packet header and compares it with the
routing table to decide the packet's next path.
• The list of routing tables provides directions
to transfer the data to a particular network
destination.
• They have a set of rules that compute the
best path to forward the data to the given IP
address.
• Routers use a modem such as a cable, fiber,
or DSL modem to allow communication
between other devices and the internet.
• Most of the routers have several ports to
connect different devices to the internet at
the same time. It uses the routing tables to
determine where to send data and from
where the traffic is coming.
Features of Router
• A router provides high-speed internet connectivity with the different types of
ports like gigabit, fast-Ethernet, and STM link port.
• It allows the users to configure the port as per their requirements in the
network.
• Routers' main components are central processing unit (CPU), flash memory,
RAM, Non-Volatile RAM, console, network, and interface card.
• Routers are capable of routing the traffic in a large networking system by
considering the sub-network as an intact network.
• Routers filter out the unwanted interference, as well as carry out the data
encapsulation and decapsulation process.
• Routers provide the redundancy as it always works in master and slave mode.
• It allows the users to connect several LAN and WAN.
Single router connects 2 LANs with internet
Networking devices- Hub, Switch, and Router(connect one computer to another)
HUB SWITCH ROUTER
used to connect computers or hardware device that also connects computers to each commonly found in homes and offices as it
other networking devices other. allows your network to communicate with
together other networks through the internet
does not use any routing table to it handles packets of data. Whenever a switch receives used to route the data packets to another
send the data to the destination a packet, it decides the device to which the packet can network instead of transmitting the data to
be sent, and sends it to that device only. the local networks only
it can identify basic errors of

networks like collisions
it can be a security risk to switch does not circulate the packet to all devices,
broadcast all information to the which means bandwidth is not shared with the
multiple ports. network
As the hub is a dumb device, it it increases the efficiency of the network.That's why Basically, a router provides more features to
does not need an IP address. switches are more preferred as compared to a hub your networks like firewall, VPN, QoS,
traffic monitoring, etc.
Hubs are cheaper than a switch

or router.
Routing table
• A routing table contains the following entities:
1. It contains an IP address of all routers which are required to decide
the way to reach the destination network.
2. It includes extrovert interface information.
3. Furthermore, it is also contained IP addresses and subnet mask of
the destination host.
Routing
• Routing is a process which is performed by layer 3 (or network layer)
devices in order to deliver the packet by choosing an optimal path
from one network to another.
• There are 3 types of routing:

1. Static routing –
3. Dynamic Routing
Static routing
• Static routing is a form of routing that occurs when a router uses a manually-configured routing entry,routes are
manually configured by a network administrator by adding in entries into a routing table.
• static routes are fixed and do not change if the network is changed or reconfigured.
Static Routing is also known as non-adaptive routing which doesn’t change routing table unless the network
administrator changes or modify them manually. Static routing does not use complex routing algorithms and It
provides high or more security than dynamic routing.
In Linux
• Router(config)#ip route [destination_network][subnet_mask][next-hop_address or exitinterface]
Advantages
1. Static routing causes very little load on the CPU of the router, and produces no traffic to other routers.
2. Static routing leaves the network administrator with full control over the routing behavior of the network.
3. Static Routing Is very easy to configure on small networks.
Disadvantages
Human error,Fault tolerance,Administrative distance and Administrative overhead
Dynamic Routing
Dynamic routing is also known as adaptive routing which change

routing table according to the change in topology.
Dynamic routing uses complex routing algorithms and it does not
provide high security like static routing.
When the network change(topology) occurs, it sends the message to
router to ensure that changes then the routes are recalculated for
sending updated routing information.
Difference between Static and Dynamic Routing:
Static Routing Dynamic Routing
In static routing routes are user defined. In dynamic routing, routes are updated according
to topology.
Static routing does not use complex routing Dynamic routing uses complex routing
algorithms. algorithms.
Static routing provides high or more security. Dynamic routing provides less security.
Static routing is manual. Dynamic routing is automated.

Static routing is implemented in small networks. Dynamic routing is implemented in large
networks.
In static routing, additional resources are not In dynamic routing, additional resources are
required. required.
In static routing, failure of link disrupts the In dynamic routing, failure of link does not
rerouting. interrupt the rerouting.
Unicast, Broadcast,Multicast, Anycast routing
It is the simplest form
of routing because the
destination is already
known. Hence the
router just has to look
up the routing table
and forward the
packet to next hop
Broadcast routing
• By default, the broadcast packets are not routed and
forwarded by the routers on any network. Routers
create broadcast domains.A broadcast message is
destined to all network devices.
• A router creates a data packet and then sends it to
each host one by one. In this case, the router creates
multiple copies of single data packet with different
destination addresses.
• All packets are sent as unicast but because they are
sent to all, it simulates as if router is broadcasting.
• This method consumes lots of bandwidth and router
must destination address of each node.
• Secondly, when router receives a packet that is to be
broadcasted, it simply floods those packets out of all
interfaces. All routers are configured in the same way.
• Reverse path forwarding is a technique-detect and
discard duplicates.
Multicast Routing
• Multicast routing is special case
of broadcast routing.
• In broadcast routing, packets are
sent to all nodes even if they do
not want it.
• But in Multicast routing, the
data is sent to only nodes which
wants to receive the packets.
• Multicast routing also uses
reverse path Forwarding
technique, to detect and discard
duplicates and loops.
Anycast Routing
• Anycast packet forwarding is a
mechanism where multiple hosts
can have same logical address.
• When a packet destined to this
logical address is received, it is sent
to the host which is nearest in
routing topology.
• Anycast routing is done with help of
DNS server. Whenever an Anycast
packet is received it is enquired with
DNS to where to send it.
• DNS provides the IP address which
is the nearest IP configured on it.
Routing Protocols and Routing Algorithms
• Unicast Routing Protocols(Distance Vector Routing Protocol RIP,Link
State Routing Protocol OSPF)
• Multicast Routing Protocols(DVMRP - Distance Vector Multicast
Routing Protocol,MOSPF - Multicast Open Shortest Path First,CBT -
Core Based Tree,PIM - Protocol independent Multicast)
• Routing Algorithms(Flooding,Shortest Path-Dijkstra's

algorithm,Bellman Ford algorithm,Floyd Warshall algorithm)
1.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:
1. 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.
2. 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.
3. Information sharing at regular intervals: Within 30 seconds, the router sends the information
to the neighboring routers.
Distance Vector Routing Algorithm
Let dx(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)+dv(y). The least cost from x to y is the
minimum of c(x,v)+dv(y) taken over all neighbors.
Let's understand through an example:
Sharing Information
• 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.
• 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:
1. Creating the Table

2. Updating the Table
1.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.
• A sends its routing table to B, F
& E.
• B sends its routing table to A &
C.
• C sends its routing table to B &
D.
• D sends its routing table to E &
C.
• E sends its routing table to A &
D.
• F sends its routing table to A.
2.Updating the Table
• When A receives a routing table

from B, then it uses its After adjustment, A then combines this
information to update the table. table with its own table to create a
combined 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.
• 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:
2.Link State Routing
• Link state routing is a technique in which each router shares the knowledge of its neighborhood with every other router in the
internetwork.
• The three keys to understand the Link State Routing algorithm:
• Knowledge about the neighborhood: Instead of sending its routing table, a router sends the information about its neighborhood only. A
router broadcast its identities and cost of the directly attached links to other routers.
• Flooding: Each router sends the information to every other router on the internetwork except its neighbors. This process is known as
Flooding. Every router that receives the packet sends the copies to all its neighbors. Finally, each and every router receives a copy of the
same information.
• Information sharing: A router sends the information to every other router only when the change occurs in the information.
Link State Routing has two phases:
1.Reliable Flooding
• Initial state: Each node knows the cost of its neighbors.
• Final state: Each node knows the entire graph.
2.Route Calculation
• Each node uses Dijkstra's algorithm on the graph to calculate the optimal routes to all nodes.
• The Link state routing algorithm is also known as Dijkstra's algorithm which is used to find the shortest path from one node to every other
node in the network.
• The Dijkstra's algorithm is an iterative, and it has the property that after kth iteration of the algorithm, the least cost paths are well known
for k destination nodes.
Let's describe some notations:
• c( i , j): Link cost from node i to node j. If i and j nodes are not directly
linked, then c(i , j) = ∞.
• D(v): It defines the cost of the path from source code to destination v
that has the least cost currently.
• P(v): It defines the previous node (neighbor of v) along with current
least cost path from source to v.
• N: It is the total number of nodes available in the network.
Let's understand through an example:
Step 1:
• The first step is an initialization step. The currently known least cost
path from A to its directly attached neighbors, B, C, D are 2,5,1
respectively. The cost from A to B is set to 2, from A to D is set to 1
and from A to C is set to 5. The cost from A to E and F are set to
infinity as they are not directly linked to A.
Step N D(B),P(B) D(C),P(C) D(D),P(D) D(E),P(E) D(F),P(F)
1 A 2,A 5,A 1,A ∞ ∞
Step 2:
• In the above table, we observe that vertex D contains the least cost path in step 1. Therefore, it is added in N. Now, we need to determine a
least-cost path through D vertex.
• a) Calculating shortest path from A to B
• v = B, w = D
• D(B) = min( D(B) , D(D) + c(D,B) )
• = min( 2, 1+2) = min( 2, 3)
• The minimum value is 2. Therefore, the currently shortest path from A to B is 2.
• b) Calculating shortest path from A to C
• v = C, w = D
• D(B) = min( D(C) , D(D) + c(D,C) )
• = min( 5, 1+3) = min( 5, 4)
• The minimum value is 4. Therefore, the currently shortest path from A to C is 4.</p>
• c) Calculating shortest path from A to E
• v = E, w = D
• D(B) = min( D(E) , D(D) + c(D,E) )
• = min( ∞, 1+1) = min(∞, 2)
• The minimum value is 2. Therefore, the currently shortest path from A to E is 2.
1 A 2,A 5,A 1,A ∞ ∞
2 AD 2,A 4,D 2,D ∞
Step 3:
• In the above table, we observe that both E and B have the least cost path in step 2. Let's consider the E vertex. Now, we det ermine the least cost path
of remaining vertices through E.
• a) Calculating the shortest path from A to B.
• v = B, w = E
• D(B) = min( D(B) , D(E) + c(E,B) )
• = min( 2 , 2+ ∞ ) = min( 2, ∞)
• The minimum value is 2. Therefore, the currently shortest path from A to B is 2.
• b) Calculating the shortest path from A to C.
• v = C, w = E
• D(B) = min( D(C) , D(E) + c(E,C) )
• = min( 4 , 2+1 ) = min( 4,3)
• The minimum value is 3. Therefore, the currently shortest path from A to C is 3.
• c) Calculating the shortest path from A to F.
• v = F, w = E
• D(B) = min( D(F) , D(E) + c(E,F) )
• = min( ∞ , 2+2 ) = min(∞ ,4)
• The minimum value is 4. Therefore, the currently shortest path from A to F is 4.
1 A 2,A 5,A 1,A ∞ ∞
2 AD 2,A 4,D 2,D ∞
3 ADE 2,A 3,E 4,E
• Step 4:
• In the above table, we observe that B vertex has the least cost path in step 3. Therefore,
it is added in N. Now, we determine the least cost path of remaining vertices through B.
• a) Calculating the shortest path from A to C.
• v = C, w = B
• D(B) = min( D(C) , D(B) + c(B,C) )
• = min( 3 , 2+3 ) = min( 3,5)
• The minimum value is 3. Therefore, the currently shortest path from A to C is 3.
• b) Calculating the shortest path from A to F.
• v = F, w = B
• D(B) = min( D(F) , D(B) + c(B,F) )
• = min( 4, ∞) = min(4, ∞)
1 A 2,A 5,A 1,A ∞ ∞
2 AD 2,A 4,D 2,D ∞
3 ADE 2,A 3,E 4,E
4 ADEB 3,E 4,E
• Step 5:
• In the above table, we observe that C vertex has the least cost path in step 4. Therefore, it is
added in N. Now, we determine the least cost path of remaining vertices through C.
• a) Calculating the shortest path from A to F.
• v = F, w = C
• D(B) = min( D(F) , D(C) + c(C,F) )
• = min( 4, 3+5)
• = min(4,8)
1 A 2,A 5,A 1,A ∞ ∞
2 AD 2,A 4,D 2,D ∞
3 ADE 2,A 3,E 4,E
4 ADEB 3,E 4,E
5 ADEBC 4,E
Final table:
1 A 2,A 5,A 1,A ∞ ∞
2 AD 2,A 4,D 2,D ∞
3 ADE 2,A 3,E 4,E
4 ADEB 3,E 4,E
5 ADEBC 4,E
6 ADEBCF
Disadvantage:
Heavy traffic is created in Line state routing due to Flooding. Flooding can cause an infinite looping, this
problem can be solved by using Time-to-leave field
1.Distance Vector Routing(Example protocol:RIP)
• The network uses a Distance Vector Routing protocol. Once the
routes have stabilized, the distance vectors at different nodes are as
following.
• N1: (0, 1, 7, 8, 4)
• N2: (1, 0, 6, 7, 3)
• N3: (7, 6, 0, 2, 6)
• N4: (8, 7, 2, 0, 4)
• N5: (4, 3, 6, 4, 0)
• Each distance vector is the distance of the best known path at the instance to
nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric
and the cost is identical in both directions. In each round, all nodes exchange
their distance vectors with their respective neighbors. Then all nodes update
their distance vectors. In between two rounds, any change in cost of a link will
cause the two incident nodes to change only that entry in their distance
vectors. 52. The cost of link N2-N3 reduces to 2(in both directions). After the
next round of updates, what will be the new distance vector at node, N3.
• (A) (3, 2, 0, 2, 5)
• (B) (3, 2, 0, 2, 6)
• (C) (7, 2, 0, 2, 5)
• (D) (7, 2, 0, 2, 6)
CREATING ROUTING TABLE
• SAME SOURCE AND SAME DESTINATION=0
• A TO B AND B TO A IS SAME THAT IS BIDIRECTIONAL
• IF 2 ROUTERS ARE INDIRECT ASSIGN INFINITE COST
Roing table for N1
N1 N1 N2 N3 N4 N5
N1 0 1 - - -
N2 1
N3
N4
N5
N1 N1 N2 N3 N4 N5 N2 N1 N2 N3 N4 N5
N1 0 1 - - - N1 1
N2 1 N2 1 0 6 - 3
N3 N3 6
N4 N4
N5 N5 3
N3 N1 N2 N3 N4 N5 N5 N1 N2 N3 N4 N5
N4 N1 N2 N3 N4 N5
N1
N1 N1
N2 6
N2 N2 1 0 6 - 3
N3 - 6 0 2 -
N3 2 N3 6
N4 2 N4 4
N4 - - 2 0 4
N5 N5 4 N5 - 3 - 4 0
• AFTER EVERY PERIOD OF TIME EACH ROUTER GETS INFORMATION
FROM ITS NEIGHBOURS.
• THEN CALCULETE SHORTEST ROUTE AND UPDATE ITS OWN TABLE.
• THEN SEND UPDATED TABLE TO ITS NEIGHBOURS

N1 N1 N2 N3 N4 N5 N2 N1 N2 N3 N4 N5
N1 0 1 - - - N1 0 1
N2 1 0 6 - 3 N2 1 0 6 - 3
N3 - 6 N3 - 6 2 -
N4 - N4 2 4
N5 3 N5 - 3 - 4 0
N3 N1 N2 N3 N4 N5 N5 N1 N2 N3 N4 N5
N4 N1 N2 N3 N4 N5
N1 1
N1 N1
N2 1 0 6 - 3
N2 3 N2 1 0 6 - 3
N3 6 0 2
N3 2 N3 6 2
N4 - - 2 0 4 N4 - - 2 0 4
N4 - - 2 0 4
N5 3 4 N5 - 3 - 4 0 N5 - 3 - 4 0
N1 N1 N2 N3 N4 N5 N2 N1 N2 N3 N4 N5
N1 0 1 7 7 4 N1 0 1 7 7 4
N2 1 0 6 7 3 N2 1 0 6 7 3
N3 7 6 0 2 6 N3 7 6 0 2 6
N4 8 7 2 0 4 N4 8 7 2 0 4
N5 4 3 6 4 0 N5 4 3 6 4 0
N3 N1 N2 N3 N4 N5 N5 N1 N2 N3 N4 N5
N4 N1 N2 N3 N4 N5
N1 0 1 7 7 4
N1 0 1 7 7 4 N1 0 1 7 7 4
N2 1 0 6 7 3
N2 1 0 6 7 3 N2 1 0 6 7 3
N3 7 6 0 2 6
N3 7 6 0 2 6 N3 7 6 0 2 6
N4 8 7 2 0 4 N4 8 7 2 0 4
N4 8 7 2 0 4
N5 4 3 6 4 0 N5 4 3 6 4 0 N5 4 3 6 4 0
Assume that the network in Figure uses distance-vector routing with the
forwarding table as shown for each node.
2.Link State Routing(Dijkstras algorithm)
• Find shortest path from one node to every other node in the network.
2 phases:
1. Reliable Flooding
Each node knows cost of its neighbours
Each node knows entire graph
2. Route Calculation
Each node uses Dijkstras algorithm to calculate optimal path.
Use Link state to build the routing table with
Dijkstras algorithm
STEP 1:Each node knows cost of its neighbours
NODE A COST
NODE COST NODE COST NODE COST
B C D
B 3 A 3 A 2 A 5
C 2 D 1 D 2 B 1
D 5 E 4 F 1 C 2
E 3
NODE COST
NODE COST
E
F
B 4
C 1
D 3
E 2
F 2
Dijkstras algorithm
Dijkstra’s Algorithm ( ) repeat
{ {
Tree={root} find a node w with D[w] minimum among
for(y = 1 to N) all nodes not in the Tree
{ Tree = Tree U { w}
if(y is the root) for(every node x,which is a neighbour of w
D[y] = 0 and not in the Tree))
else if(y is a neighbour) {
D[y] = c[root][y] D[x]=min{D[x],(D[w]+c[w][x])
else }
D[y] = ∞ } until(all nodes included in the Tree)
} }/ /End of Dijkstra
STEP 2:Each node uses Dijkstras to calculate
optimal path
ITERATI TREE NODES
ON B C D E F
INITIAL {A} 3 2 5
1’ST {A,C} 3 - 4 3
2ND {A,B,C} - - 4 7 3
3RD {A,B,C,F} - - 4 5 -
4TH {A,B,C,D,F} - - - 5 -
5TH {A,B,C,D,E,F} - - - - -
OUTPUT
ITERA TREE NODES
TION B C D E F
INITI {A} 3 2 5
AL
1’ST {A,C} 3 - 4 3
2ND {A,B, - - 4 7 3
C}
3RD {A,B, - - 4 5 -
C,F}
4TH {A,B, - - - 5 -
C,D,F}
5TH {A,B, - - - - -
C,D,E,
F}
Use Dijkstra’s algorithm to find the shortest path tree and the
forwarding table for node A in the Figure
3.Path vector routing algorithm(Spanning Trees)
• Both link-state and distance-vector routing are based on the least-cost goal.
• The least-cost goal,applied by LS or DV routing, does not allow a sender to apply specific
policies to the route a packet may take.
• Goal:to allow the packet to reach its destination more efficiently without assigning costs
to the route.
• Path-vector routing does not have the drawbacks of LS or DV routing as described above
because it is not based on least-cost routing.
• The best route is determined by the source using the policy it imposes on the route. In
other words, the source can control the path. Although path-vector routing is not
actually used in an internet, and is mostly designed to route a packet between ISPs,
Spanning Trees
• In path-vector routing, the path from a source to all destinations is
also determined by the best spanning tree.
• The best spanning tree, however, is not the least-cost tree; it is the
tree determined by the source when it imposes its own policy. If there
is more than one route to a destination, the source can choose the
route that meets its policy best.
• A source may apply several policies at the same time.
1. One of the common policies uses the minimum number of nodes to
be visited (something similar to least-cost).
2. Another common policy is to avoid some nodes as the middle node
in a route.
Spanning trees in path-vector routing
• Path-vector routing, like distance-vector routing, is an asynchronous and
distributed routing algorithm.
• The spanning trees are made, gradually and asynchronously, by each node.
• When a node is booted, it creates a path vector based on the information it
can obtain about its immediate neighbor.
• A node sends greeting messages to its immediate neighbors to collect these
pieces of information.
• Each node, after the creation of the initial path vector, sends it to all its
immediate neighbors.
• Each node, when it receives a path vector from a neighbor, updates its path
vector using an equation similar to the Bellman-Ford, but applying its own
policy instead of looking for the least cost. We can define this equation as
• Path(x, y) = best {Path(x, y), [(x + Path(v, y)]} for all v’s in the internet.
• Path vectors made at booting • Updating path vectors
time
Path-Vector Algorithm
Path_Vector_Routing ( ) // Update
{ repeat (forever)
{
// Initialization
wait (for a vector Pathw from a neighbor w)
for (y = 1 to N)
for (y = 1 to N)
{
{
if (y is myself) if (Pathw includes myself)
Path[y] = myself discard the path // Avoid any loop
else if (y is a neighbor) else
Path[y] = myself + neighbor node Path[y] = best {Path[y], (myself + Pathw[y])}
else }
If (there is a change in the vector)
Path[y] = empty
Send vector {Path[1], Path[2], …, Path[y]} to all neighbors
}
}
Send vector {Path[1], Path[2], …, Path[y]} to all
} // End of Path Vector
neighbors
Multicast Addresses
• When we send a unicast packet to a destination, the source address of the packet defines the
sender and the destination address of the packet defines the receiver of the packet. In multicast
communication, the sender is only one, but the receiver is many, sometimes thousands or
millions spread all over the world.
• It should be clear that we cannot include the addresses of all recipients in the packet. The
destination address of a packet, as described in the Internet Protocol (IP) should be only one. For
this reason we need multicast addresses. A multicast address defines a group of recipients, not a
single one.
• In other words, a multicast address is an identifier for a group. If a new group is formed with
some active members, an authority can assign an unused multicast address to this group to
uniquely define it.
• This means that the source address of a packet in multicast communication can be a unicast
address that uniquely defines the sender, but the destination address can be the multicast
address that defines a group. In this way, a host, which is a member of n groups, actually has (n +
1) addresses: one unicast address that is used for source or destination address in unicast
communication and n multicast addresses that are used only for destination addresses to receive
messages sent to a group.
A multicast address in binary
INTRADOMAIN MULTICAST PROTOCOLS
• Two are extensions of unicast routing protocols (RIP and OSPF), using the source-based
tree approach;
• The third is an independent protocol which is becoming more and more popular. It can
be used in two modes,employing either the source-based tree approach or the shared-
group tree approach.
1.Source-Based Tree Approach
• In the source-based tree approach to multicasting, each router needs to create a
separate tree for each source-group combination. In other words, if there are m groups
and n sources in the internet, a router needs to create (m × n) routing trees.
2.Group-Shared Tree Approach
• In the group-shared tree approach, we designate a router to act as the phony source for
each group. The designated router, which is called the core router or the rendezvous
point router, acts as the representative for the group. Any source that has a packet to
send to a member of that group sends it to the core center (unicast communication) and
the core center is responsible for multicasting.
INTRADOMAIN MULTICAST PROTOCOLS
3Protocols Designed to provide multicast communication inside an
autonomous system-
1.Multicast Distance Vector (DVMRP)-Distance Vector Multicast
Routing Protocol (DVMRP)
• Reverse Path Forwarding (RPF)
• Reverse Path Broadcasting (RPB)
• Reverse Path Multicasting (RPM)
2.Multicast Link State (MOSPF)-Multicast Open Shortest Path First
(MOSPF)
3.Protocol Independent Multicast (PIM)
Protocol Independent Multicast-Dense Mode (PIM-DM)
Protocol Independent Multicast-Sparse Mode (PIM-SM)
1)Multicast Distance Vector (DVMRP)-Distance
Vector Multicast Routing Protocol
• DVMRP is the extension of the Routing Information Protocol (RIP) which is used in
unicast routing.
• It uses the source based tree approach to multicasting.
• Each router in this protocol that receives a multicast packet to be forwarded implicitly
creates a source-based multicast tree in three steps:
• 1. The router uses an algorithm called reverse path forwarding (RPF) to simulate
creating part of the optimal source-based tree between the source and itself.
• 2. The router uses an algorithm called reverse path broadcasting (RPB) to create a
broadcast (spanning) tree whose root is the router itself and whose leaves are all
networks in the internet.
• 3. The router uses an algorithm called reverse path multicasting (RPM) to create a
multicast tree by cutting some branches of the tree that end in networks with no
member in the group.
A)Reverse Path Forwarding (RPF)
• Forces the router to forward a multicast packet from one specific interface: the one which has come through the
short_x0002_est path from the source to the router.
• How can a router know which interface is in this path if the router does not have a shortest-path tree rooted at the
source? The router uses the first property of the shortest-path tree we discussed in unicast routing, which says that
the shortest path from A to B is also the shortest path from B to A.
• The router does not know the shortest path from the source to itself, but it can find which is the next router in the
shortest path from itself to the source (reverse path).
• The router simply consults its unicast forwarding table, pretending that it wants to send a packet to the source; the
forwarding table gives the next router and the interface the message that the packet should be sent out in this
reverse direction.
• The router uses this information to accept a multicast packet only if it arrives from this interface. This is needed to
prevent looping.
• In multicasting, a packet may arrive at the same router that has forwarded it. If the router does not drop all arrived
packets except the one, multiple copies of the packet will be circulating in the internet. Of course, the router may
add a tag to the packet when it arrives the first time and discard packets that arrive with the same tag, but the RPF
strategy is simpler.
B)Reverse Path Broadcasting (RPB)
• The RPF algorithm helps a router to forward only one copy received from a source and drop the rest.
• However, when we think about broadcasting in the second step, we need to remember that destinations are all the networks (LANs) in the
internet.
• To be efficient,we need to prevent each network from receiving more than one copy of the packet.
• If a network is connected to more than one router, it may receive a copy of the packet from each router.
• RPF cannot help here, because a network does not have the intelligence to apply the RPF algorithm; we need to allow only one of the
routers attached to a network to pass the packet to the network.
• One way to do so is to designate only one router as the parent of a network related to a specific source. When a router that is not the
parent of the attached network receives a multicast packet, it simply drops the packet.
• There are several ways that the parent of the network related to a network can be selected; one way is to select the router that has the
shortest path to the source (using the unicast forward_x0002_ing table, again in the reverse direction).
• If there is a tie in this case, the router with the smaller IP address can be selected. The reader may have noticed that reverse path
broadcasting (RPB) actually creates a broadcast tree from the graph that has been cre_x0002_ated by the RPF algorithm. RPB has cut those
branches of the tree that cause cycles in the graph.
• If we use the shortest path criteria for choosing the parent router, we have actually created a shortest-path broadcast tree. In other words,
after this step, we have a shortest-path tree with the source as the root and all networks (LANs) as the leaves.
• Every packet started from the source reaches all LANs in the internet travelling the shortest path. Figure 21.11 shows how RPB can avoid
duplicate reception in a network by assigning a designated parent router, R1, for network N.
RPF versus RPB
C)Reverse Path Multicasting (RPM)
• As you may have noticed, RPB does not multicast the packet, it broadcasts it. This is not efficient. To increase
efficiency, the multicast packet must reach only those networks that have active members for that particular group.
This is called reverse path multicasting (RPM).
• To change the broadcast shortest-path tree to a multicast shortest-path tree, each router needs to prune (make
inactive) the interfaces that do not reach a network with active members corresponding to a particular source-
group combination.
• This step can be done bottom-up, from the leaves to the root. At the leaf level, the routers connected to the
network collect the membership information using the IGMP protocol discussed before.
• The parent router of the network can then disseminate this information upward using the reverse shortest-path
tree from the router to the source, the same way as the distance vector messages are passed from one neighbor to
another.
• When a router receives all of these membership-related messages, it knows which interfaces need to be pruned. Of
course, since these packets are disseminated periodically, if a new member is added to some networks, all routers
are informed and can change the status of their interfaces accordingly. Joining and leaving is continuously applied.
RPB versus RPM
2)Multicast Link State (MOSPF)
• Extension of the Open Shortest Path First (OSPF) protocol, which is used in
unicast routing.
• It also uses the source based tree approach to multicasting. If the internet is
running a unicast link-state routing algorithm, the idea can be extended to
provide a multicast link-state routing algorithm.
• Recall that in unicast link-state routing, each router in the internet has a link-
state database (LSDB) that can be used to create a shortest-path tree.
• To extend unicasting to multicasting, each router needs to have another
database, as with the case of unicast distance-vector routing, to show which
interface has an active member in a particular group.
Now a router goes through the following steps to forward a
multicast packet received from source S and to be sent to destination G (a group of
recipients):
• 1. The router uses the Dijkstra algorithm to create a shortest-path tree with S as the root and all destinations in the
internet as the leaves. Note that this shortest-path tree is different from the one the router normally uses for
unicast forwarding, in which the root of the tree is the router itself. In this case, the root of the tree is the source of
the packet defined in the source address of the packet.
• The router is capable of creating this tree because it has the LSDB, the whole topology of the internet; the Dijkstra
algorithm can be used to create a tree with any root, no matter which router is using it. The point we need to
remember is that the shortest-path tree created this way depends on the specific source. For each source we need
to create adifferent tree.
• 2. The router finds itself in the shortest-path tree created in the first step. In other words, the router creates a
shortest-path subtree with itself as the root of the subtree.
• 3. The shortest-path subtree is actually a broadcast subtree with the router as the root and all networks as the
leaves. The router now uses a strategy similar to the one we describe in the case of DVMRP to prune the broadcast
tree and to change it to a multicast tree. The IGMP protocol is used to find the information at the leaf level.
• MOSPF has added a new type of link state update packet that floods the member_x0002_ship to all routers. The
router can use the information it receives in this way andprune the broadcast tree to make the multicast tree.
• 4. The router can now forward the received packet out of only those interfaces that correspond to the branches of
the multicast tree. We need to make certain that a copy of the multicast packet reaches all networks that have
active members of the group and that it does not reach those networks that do not.
Example of tree formation in MOSPF
3)Protocol Independent Multicast (PIM)
• Common protocol that needs a unicast routing protocol for its operation, but the unicast protocol can be either a
distance-vector protocol or a link-state protocol.
• In other words, PIM needs to use the forwarding table of a unicast routing protocol to find the next router in a path
to the destination, but it does not matter how the forwarding table is created.
• PIM has another interesting feature: it can work in two different modes: dense and sparse.
• The term dense here means that the number of active members of a group in the internet is large; the probability
that a router has a member in a group is high.
• This may happen, for example, in a popular teleconference that has a lot of members.
• The term sparse, on the other hand, means that only a few routers in the internet have active members in the
group; the probability that a router has a member of the group is low. This may happen, for example, in a very
technical teleconference where a number of members are spread somewhere in the internet. When the protocol is
working in the dense mode, it is referred to as PIM-DM; when it is working in the sparse mode, it is referred to as
PIM_x0002_SM.
3A)Protocol Independent Multicast-Dense Mode (PIM-DM)
• When the number of routers with attached members is large relative to the number of routers in the
internet, PIM works in the dense mode and is called PIM-DM.
• In this mode, the protocol uses a source-based tree approach and is similar to DVMRP, but simpler.
• PIM-DM uses only two strategies described in DVMRP: RPF and RPM. But unlike DVMRP, forwarding of a
packet is not suspended awaiting pruning of the first subtree. Let us explain the two steps used in PIM-DM
to clear the matter.
• 1.A router that has received a multicast packet from the source S destined for the group G first uses the RPF
strategy to avoid receiving a duplicate of the packet. It consults the forwarding table of the underlying
unicast protocol to find the next router if it wants to send a message to the source S (in the reverse
direction). If the packet has not arrived from the next router in the reverse direction, it drops the packet and
sends a prune message in that direction to prevent receiving future packets related to (S, G).
• 2. If the packet in the first step has arrived from the next router in the reverse direction,the receiving router
forwards the packet from all its interfaces except the one fromwhich the packet has arrived and the interface
from which it has already received a prune message related to (S, G). Note that this is actually a broadcasting
instead of a multicasting if the packet is the first packet from the source S to group G.
• However,each router downstream that receives an unwanted packet sends a prune message to the router
upstream, and eventually the broadcasting is changed to multicasting. Note that DVMRP behaves differently:
it requires that the prune messages (which are part of DV packets) arrive and the tree is pruned before
sending any message through unpruned interfaces. PIM-DM does not care about this precaution because it
assumes that most routers have an interest in the group (the idea of the dense mode).
Idea behind PIM-DM-(The first packet is broadcast to all networks, which have or do not
have members. After a prune message arrives from a router with no member, the second
packet is only multicast.)
3B)Protocol Independent Multicast-Sparse Mode
(PIM-SM)
• When the number of routers with attached members is small relative to the number of routers in
the internet, PIM works in the sparse mode and is called PIM-SM. In this environment, the use of
a protocol that broadcasts the packets until the tree is pruned is not justified; PIM-SM uses a
group-shared tree approach to multicasting.
• The core router in PIM-SM is called the rendezvous point (RP). Multicast communication is
achieved in two steps. Any router that has a multicast packet to send to a group of destinations
first encapsulates the multicast packet in a unicast packet (tunneling) and sends it to the RP. The
RP then decapsulates the unicast packet and sends the multicast packet to its destination.
• PIM-SM uses a complex algorithm to select one router among all routers in the internet as the RP
for a specific group. This means that if we have m active groups, we need m RPs, although a
router may serve more than one group. After the RP for each group is selected, each router
creates a database and stores the group identifier and the IP address of the RP for tunneling
multicast packets to it.
• PIM-SM uses a spanning multicast tree rooted at the RP with leaves pointing to
designated routers connected to each network with an active member. A very interesting
point in PIM-SM is the formation of the multicast tree for a group.
• The idea is that each router helps to create the tree. The router should know the unique
interface from which it should accept a multicast packet destined for a group (what was
achieved by RPF in DVMRP).
• The router should also know the interface or interfaces from which it should send out a
multicast packet destined for a group (what was achieved by RPM in DVMRP). To avoid
delivering more than one copy of the same packet to a network through several routers
(what was achieved by RPB in DVMRP), PIM-SM requires that only designated routers
send PIM-SM messages, as we will see shortly.
• To create a multicast tree rooted at the RP, PIM-SM uses join and prune messages.
Idea behind PIM-SM-( shows the operation of join and prune messages in PIM-SM. First, three
networks join group G1 and form a multicast tree. Later, one of the networks leaves the
group and the tree is pruned)
• The join message is used to add possible new branches to the tree; the prune mes_x0002_sage is used to cut
branches that are not needed.
• When a designated router finds out that a network has a new member in the corresponding group (via IGMP), it
sends a join message in a unicast packet destined for the RP.
• The packet travels through the unicast shortest-path tree to reach the RP. Any router in the path receives and
forwards the packet, but at the same time, the router adds two pieces of information to its multicast forwarding
table.
• The number of the interface through which the join message has arrived is marked (if not already marked) as one
of the interfaces through which the multicast packet destined for the group should be sent out in the future.
• The router also adds a count to the number of join messages received here, as we discuss shortly. The number of
the interface through which the join message was sent to the RP is marked (if not already marked) as the only
interface through which the multicast packet destined for the same group should be received.
• In this way, the first join message sent by a designated router creates a path from the RP to one of the networks
with group members.
• To avoid sending multicast packets to networks with no members, PIM-SM uses the prune message. Each
designated router that finds out (via IGMP) that there is no active member in its network, sends a prune message
to the RP.
• When a router receives a prune message, it decrements the join count for the interface through which the
message has arrived and forwards it to the next router.
• When the join count for an interface reaches zero, that interface is not part of the multicast tree anymore.
INTERDOMAIN MULTICAST PROTOCOLS
• Multicast Border Gateway Protocol (MBGP)-MBGP provides two paths between ASs: one for
unicasting and one for multicasting. Information about multicasting is exchanged between border
routers in different ASs. MBGP is a shared-group multicast routing protocol in which one router in
each AS is chosen as the rendezvous point (RP).
• The problem with MBGP protocol is that it is difficult to inform an RP about the sources of groups
in other ASs.
• The Multicast Source Discovery Protocol (MSDP) is a new suggested protocol that assigns a
source representative router in each AS to inform all RPs about the existence of sources in that AS.
• Another protocol that is Border Gateway Multicast Protocol (BGMP)-which allows construction of
shared group trees with a single root in one of the ASs. In other words, for each group, there is only
one shared tree, with leaves in different ASs, but the root is located in one of the ASs. The two
problems, of course, are how to designate an AS as the root of the tree and how to inform all
sources about the location of the root to tunnel their multicast packets to.
IGMP-Internet Group Management Protocol
• collecting information about group membership
• defined at the network layer;IGMP messages, like ICMP messages, are encapsulated in an IP
datagram.
• Messages-There are only two types of messages in IGMP version 3, query and report messages.A
query message is periodically sent by a router to all hosts attached to it to ask them to report
their interests about membership in groups. A report message is sent by a host as a response to a
query message.
• IGMP operation
I )Query Message
• The query message is sent by a router to all hosts in each interface to collect information about
their membership. There are three versions of query messages, as described below:
• a. A general query message is sent about membership in any group. It is encapsulated in a
datagram with the destination address 224.0.0.1 (all hosts and routers). Note that all routers
attached to the same network receive this message to inform them that this message is already sent
and that they should refrain from resending it.
• b. A group-specific query message is sent from a router to ask about the membership related to a
specific group. This is sent when a router does not receive a response about a specific group and
wants to be sure that there is no active member of that group in the network.
• The group identifier (multicast address) is mentioned in the message. The message is encapsulated
in a datagram with the destination address set to the corresponding multicast address. Although all
hosts receive this message, those not interested drop it.
• c. A source-and-group-specific query message is sent from a router to ask about the membership
related to a specific group when the message comes from a specific source or sources. Again the
message is sent when the router does not hear about a specific group related to a specific host or
hosts. The message is encapsulated in a datagram with the destination address set to the
corresponding multicast address. Although all hosts receive this message, those not interested drop
it.
II )Report Message
• A report message is sent by a host as a response to a query message. The
message contains a list of records in which each record gives the identifier of
the corresponding group (multicast address) and the addresses of all sources
that the host is interested in receiving messages from (inclusion).
• The record can also mention the source addresses from which the host does
not desire to receive a group message (exclusion). The message is
encapsulated in a datagram with the multicast address 224.0.0.22 (multicast
address assigned to IGMPv3). In IGMPv3, if a host needs to join a group, it
waits until it receives a query message and then sends a report message.
• If a host needs to leave a group, it does not respond to a query message. If no
other host responds to the corresponding message, the group is purged from
the router database.
Propagation of Membership Information
• After a router has collected membership information from the hosts
and other routers at its own level in the tree, it can propagate it to
the router located in a higher level of the tree.
• Finally, the router at the tree root can get the membership
information to build the multicast tree.
• The process, however, is more complex than what we can explain in
one paragraph. Interested readers can check the book website for the
complete description of this protocol.
Encapsulation
• The IGMP message is encapsulated in an IP datagram with the value of
the protocol field set to 2 and the TTL field set to 1. The destination IP
address of the datagram, however, depends on the type of message,
as shown in Table
• Destination IP Addresses
ICMPv4
• The IPv4 has no error-reporting or error-correcting mechanism. What happens if something goes
wrong?
• What happens if a router must discard a datagram because it cannot find a route to the final
destination, or because the time-to-live field has a zero value?
• What happens if the final destination host must discard the received fragments of a datagram
because it has not received all fragments within a predetermined time limit?
• These are examples of situations where an error has occurred and the IP protocol has no built-in
mechanism to notify the original host.
• The IP protocol also lacks a mechanism for host and management queries. A host sometimes needs
to determine if a router or another host is alive. And sometimes a network manager needs
information from another host or router.
• The Internet Control Message Protocol version 4 (ICMPv4) has been designed to compensate for
the above two deficiencies. It is a companion to the IP protocol.
• ICMP itself is a network-layer protocol. However, its messages are not passed directly to the data-
link layer as would be expected. Instead, the messages are first encapsulated inside IP datagrams
before going to the lower layer. When an IP datagram encapsulates an ICMP message, the value of
the protocol field in the IP datagram is set to 1 to indicate that the IP payroll is an ICMP message.
ICMPV4 MESSAGES
• General format of ICMP messages
• ICMP messages are divided into two broad categories: error-reporting messages and query messages. The error-reporting
messages report problems that a router or a host (destination) may encounter when it processes an IP packet. The query
messages, which occur in pairs, help a host or a network manager get specific information from a router or another host.
For example, nodes can discover their neighbors.
• Also, hosts can discover and learn about routers on their network and routers can help a node redirect its messages.
• An ICMP message has an 8-byte header and a variable-size data section. Although the general format of the header is
different for each message type, the first 4 bytes are common to all. As Figure shows, the first field, ICMP type, defines the
type of the message. The code field specifies the reason for the particular message type.
• The last common field is the checksum field . The rest of the header is specific for each message type The data section in
error messages carries information for finding the original packet that had the error. In query messages, the data section
carries extra information based on the type of query.
• We give a brief description of the ICMPv4 messages here;
• 1)Error Reporting Messages-Since IP is an unreliable protocol, one of the main responsibilities of ICMP is to report some
errors that may occur during the processing of the IP datagram. ICMP does not correct errors, it simply reports them.
• Error correction is left to the higher-level protocols. Error messages are always sent to the original source because the only
information available in the datagram about the route is the source and destination IP addresses.
• ICMP uses the source IP address to send the error message to the source (originator) of the datagram. To make the error-
reporting process simple, ICMP follows some rules in reporting messages.
• First, no error message will be generated for a datagram having a multicast address or special address (such as this host or
loopback).
• Second, no ICMP error message will be generated in response to a datagram carrying an ICMP error message.
• Third, no ICMP error message will be generated for a fragmented datagram that is not the first fragment.
• Note that all error messages contain a data section that includes the IP header of the
original datagram plus the first 8 bytes of data in that datagram.
• The original datagram header is added to give the original source, which receives the
error message, information about the datagram itself.
• The 8 bytes of data are included because the first 8 bytes provide information about the
port numbers (UDP and TCP) and sequence number (TCP).
• This information is needed so the source can inform the protocols (TCP or UDP) about
the error.
• Note that all error messages contain a data section that includes the IP header of the
original datagram plus the first 8 bytes of data in that datagram. The original datagram
header is added to give the original source, which receives the error message,
informa_x0002_tion about the datagram itself.
• The 8 bytes of data are included because, the first 8 bytes provide information about the
port numbers (UDP and TCP) and sequence number (TCP). This information is needed so
the source can inform the protocols (TCP or UDP) about the error. ICMP forms an error
packet, which is then encapsulated in an IP datagram
Contents of data field for the error messages
1)Destination Unreachable
• The most widely used error message is the destination unreachable (type 3). This message uses different codes (0 to 15) to define the type
of error message and the reason why a datagram has not reached its final destination. For example, code 0 tells the source that a host is
unreachable. This may happen, for example, when we use the HTTP protocol to access a web page, but the server is down. The message
“destination host is not reachable” is created and sent back to the source.
2)Source Quench
• Another error message is called the source quench (type 4) message, which informs the sender that the network has encountered
congestion and the datagram has been dropped; the source needs to slow down sending more datagrams. In other words,
• ICMP adds a kind of congestion control mechanism to the IP protocol by using this type of message.
3)Redirection Message
• The redirection message (type 5) is used when the source uses a wrong router to send out its message. The router redirects the message to
the appropriate router, but informs the source that it needs to change its default router in the future. The IP address of the default router is
sent in the message.
• We discussed the purpose of the time-to-live (TTL) field in the IP datagram and explained that it prevents a datagram from being aimlessly
circulated in the Internet. When the TTL value becomes 0, the datagram is dropped by the visiting router and a time exceeded message
(type 11) with code 0 is sent to the source to inform it about the situation. The time-exceeded message (with code 1) can also be sent when
not all frag_x0002_ments of a datagram arrive within a predefined period of time.
• Parameter Problem
• A parameter problem message (type 12) can be sent when either there is a problem in the header of a datagram (code 0) or some options
are missing or cannot be interpreted (code 1).
Query Messages
• Interestingly, query messages in ICMP can be used independently without relation to an IP datagram.
• Of course, a query message needs to be encapsulated in a datagram, as a carrier.
• Query messages are used to probe or test the liveliness of hosts or routers in the Internet, find the one -way or the round-trip time for an IP datagram
between two devices, or even find out whether the clocks in two devices are synchronized.
• Naturally, query messages come in pairs: request and reply. The echo request (type 8) and the echo reply (type 0) pair of me ssages are used by a host
or a router to test the liveliness of another host or router.
• A host or router sends an echo request message to another host or router; if the latter is alive, it responds with an echo reply message. We shortly see
the applications of this pair in two debugging tools: ping and traceroute.
• The timestamp request (type 13) and the timestamp reply (type 14) pair of mes_x0002_sages are used to find the round -trip time between two
devices or to check whether the clocks in two devices are synchronized. The timestamp request message sends a 32 -bit number, which defines the
time the message is sent.
• The timestamp reply resends that number, but also includes two new 32-bit numbers representing the time the request was received and the time
the response was sent. If all timestamps represent Universal time, the sender can calculate the one-way and round-trip time.
Deprecated Messages
• Three pairs of messages are declared obsolete by IETF:
• 1. Information request and replay messages are not used today because their duties are done by the Address Resolution Protoco l (ARP) discussed in
Chapter 9.
• 2. Address mask request and reply messages are not used today because their duties are done by the Dynamic Host Configuration Protocol (DHCP),
discussed in Chapter 18.
• 3. Router solicitation and advertisement messages are not used today because their duties are done by the Dynamic Host Config uration Protocol
(DHCP),
Debugging Tools
• There are several tools that can be used in the Internet for debugging. We can determine the viability of a host or router. We can trace the
route of a packet. We introduce two tools that use ICMP for debugging: ping and traceroute.
• Ping
• We can use the ping program to find if a host is alive and responding. We use ping here to see how it uses ICMP packets.
• The source host sends ICMP echo-request messages; the destination, if alive, responds with ICMP echo-reply messages.
• The ping program sets the identifier field in the echo-request and echo-reply message and starts the sequence number from 0; this number
is incremented by 1 each time a new message is sent.
• Note that ping can calculate the round-trip time. It inserts the sending time in the data section of the message.
• When the packet arrives, it subtracts the arrival time from the departure time to get the round-trip time (RTT).
• Traceroute or Tracert
• The traceroute program in UNIX or tracert in Windows can be used to trace the path of a packet from a source to the destination. It can find
the IP addresses of all the routers that are visited along the path. The program is usually set to check for the maximum of 30 hops (routers)
to be visited. The number of hops in the Internet is normally less than this. Since these two programs behave differently in Unix and
Windows, we explain them separately
Use of ICMPv4 in traceroute
ICMP Checksum(In ICMP the checksum is calculated over the entire message (header and
data).
• Example of checksum calculation

• We randomly chose the identifier to be 1 and the sequence number
to be 9. The message is divided into 16-bit (2-byte) words. The words
are added and the sum is complemented. Now the sender can put
this value in the checksum field

Unit 4 PPT NL

Uploaded by

Document Informationclick to expand document information

Document Informationclick to expand document information

Copyright:

Available Formats

Unit 4 PPT NL

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 4 PPT NL

Uploaded by

Copyright:

Available Formats

UNIT 4-UNIT IV NETWORK LAYER:

Introduction- Virtual Circuit and Datagram

PART 1: Network-layer functions and services

2)The IP address 192.168. 1.1 can be represented in hexadecimal as

• In Class D, an IP address is reserved for multicast addresses. It does

• The Host ID is used to determine the host within any network.

A 0 8 24 2^7 2^24 0.0.0.0 to 127.255.255.255

B 10 16 16 2^14 2^16 128.0.0.0 to 191.255.255.255

C 110 24 8 2^21 2^8 192.0.0.0 to 223.255.255.255

D 1110 NOT NOT NOT NOT 224.0.0.0 to 239.255.255.255

E 1111 NOT NOT NOT NOT 240.0.0.0 to 255.255.255.255

• IP addresses belonging to class E are reserved for experimental and

• 169.254.0.0 – 169.254.0.16 : Link local addresses

• Within any network, the host ID must be unique to that network.

• Class A network contains 2^24 Hosts,

• The number of addresses in the network is 2^(32 − n) = 2^5= 32

it can identify basic errors of

Hubs are cheaper than a switch

• There are 3 types of routing:

Dynamic routing is also known as adaptive routing which change

Static routing is manual. Dynamic routing is automated.

• Routing Algorithms(Flooding,Shortest Path-Dijkstra's

1. Creating the Table

• When A receives a routing table

• a) Calculating the shortest path from A to F.

• THEN CALCULETE SHORTEST ROUTE AND UPDATE ITS OWN TABLE.

• THEN SEND UPDATED TABLE TO ITS NEIGHBOURS

Path[y] = myself + neighbor node Path[y] = best {Path[y], (myself + Pathw[y])}

• Example of checksum calculation

You might also like