GEMS Arts and Science College

UNIT III  NETWORKING AND

INTERNETWORKING DEVICES
 SYLLABUS o Two or more devices connected for the
o Network layer purpose of sharing data or resources can form
o Networking and Internetworking devices a network.
 Repeaters o Two issues with LAN
 Bridges  A LAN may need to cover more distance
 Routers than its media can handle effectively.
 Gateways
 A device called repeater or
o Logical addressing
regenerator is inserted into the
 IPv4 & IPv6 addresses
network to increase the coverable
 Network Address Translation(NAT)
distance.
o Internet Protocols
 Number of stations may be too great for
o Internetworking
efficient frame delivery or management of
o Datagram
the network, and the network may need to
o Transition from IPv4 to IPv6
be subdivided
o Address Mapping
 A device called bridge is inserted for
o Error Reporting and multicasting
traffic management.
o Delivery
o When two or more separate networks are
o Forwarding
connected for exchanging data or resources,
o Routing algorithms
they become an internetwork.
 Distance vector routing
 Linking a number of LANs into an internet
 Link state routing
requires additional internetworking devices
 Multicast routing protocols
called routers and gateways.
o Networking and internetworking devices are
divided into four categories:
 Bridges
 Repeaters
 Routers
 Gateways
Fig:

[email protected] Page 1
 GEMS Arts and Science College

o Signals that carry information within a

o Each of these four device types interacts with network can travel a fixed distance before
protocols at different layers of the OSI model. attenuation endangers the integrity of the
 Repeaters act only upon the electrical data.
components of a signal and are therefore o A repeater installed on a link receives the
active only at physical layer. signal before it becomes too weak or
 Bridges utilize addressing protocols and corrupted, regenerates the original bit
can effect flow control of a single LAN; pattern, and puts the refreshed copy back
they are most active at the data link layer. onto the link.
 Routers provide links between two o A repeater allows us to extend only the
separate but same type LANs and are most physical length of a network.
active at the network layer. Fig:
 Gateways provide translation service
between incompatible LANs or
applications and are active in all of the
layers.
Fig:

o It is not an amplifier
 An amplifier cannot discriminate between
the intended signal and noise; it amplifies
equally fed onto it.
 A repeater does not amplify the signal; it
 REPEATERS regenerates it.
o A repeater or regenerator is an electronic o The location of a repeater on a link is vital.
device that operates on only the physical A repeater must be placed so that a signal
layer of the OSI model. reaches it before any noise changes the
Fig: meaning of any of its bits.
Fig:

[email protected] Page 2
 GEMS Arts and Science College

 BRIDGES
o Bridges operate in both the physical and the
data link layers of the OSI reference model.
FIG:

 Types of Bridges
o Simple bridge
 These are the most primitive and least
expensive bridge.
 It links two segments and contains a table
o Bridges can divide a large network into that lists addresses of all the stations
smaller segments include in each of them.
FIG:  These addresses must be entered manually.
 It is straight forward and inexpensive to
manufacture; Installation and maintenance
of simple bridges are time-consuming and
potentially more trouble than the cost
savings are worth.
o Multiport bridge
 A multiport can be used to connect more
than two LANs.

o Unlike repeater, bridges contain logic that

allows them to keep the traffic for each
segment separate.
o Bridges can also provide security through
the partitioning of traffic.
o A bridge operates at the data link layer
giving it access to the physical addresses of
all stations connected to it. o Transparent bridge
 when a frame enters a bridge, the bridge  Transparent bridge builds its table of
not only regenerates the signal, but checks station addresses on its own as it perform
the address of the destination and forwards its bridge functions
the new copy only to the segment to which o There many issues to be considered when
the address belongs. bridges connecting different LANs:
FIG:  Frames sent by different LANs have
different formats.

[email protected] Page 3
 GEMS Arts and Science College

 The size of the data that can be

encapsulated in a frame varies from
protocol to protocol.
 Different protocols use different data rate.
 The bit orders of addresses in different
LAN protocols is not the same.

 ROUTERS
o These are more sophisticated devices than
repeaters and bridges.  Routing Concepts
o They have access to network layer addresses o Least cost routing
and contain software that enables them to  It is based on efficiency: which of the
determine which of several possible paths available pathways is the cheapest or, in
between those addresses is the best for a networking terminology, the shortest?
particular transmission.  The term shortest means
 The route requiring the smallest number
of relays or hops.
 Fastest, cheapest, more reliable, more
secure or best of any other quality that
can make one particular link more
attractive than another.
 When shortest means the pathway
requiring the smallest number of relays, it
is called hop-count routing, in which every
link is considered to be of equal length and
o Routers act like stations on a network. given the value one.
 But unlike most stations, which are o Routing is classified as nonadaptive or
members of only one network, routers adaptive
have addresses o, and links to, two or more  Non adaptive routing
networks at the same time.  Once a pathway to a destination has been
o They receive packets from one connected selected, the router sends all packets for
network and pass them to a second connected that destination along that one route.
network.  Adaptive routing
 If a received packet is addresses to a node  In which, a router may select a new route
on a network of which the router is not a for each packet in response to changes in
member, the router is capable of condition and topology of the networks.
determining which of its connected
networks is the best next relay point for the
packet.

[email protected] Page 4
 GEMS Arts and Science College

 GATEWAYS These addresses are referred to as IPv4 (IP

o It operates in all seven layers of the OSI version 4) addresses.
model. o The need for more addresses,the Internet
uses 128-bit addresses that give much
greater flexibility in address allocation.
These addresses are referred to as IPv6 (IP
version 6) addresses.

 IPv4 ADDRESSES
o An IPv4 address is a 32-bit address that
uniquely and universally defines the
connection of a device (for example, a
computer or a router) to the Internet.
 They are unique in the sense that each
address defines one, and only one,
connection to the Internet. Two devices on
o It is a protocol converter. the Internet can never have the same
o A router by itself transfers, accepts and relays address at the same time.
packets only across networks using similar  The IPv4 addresses are universal in the
protocols. A gateway, on the other hand, can sense that the addressing system must be
accept a packet formatted for one protocol accepted by any host that wants to be
and convert it to a packet formatted for connected to the Internet.
another protocol.  Address Space
o An address space is the total number of
addresses used by the protocol.
o If a protocol uses N bits to define an
address, the address space is 2N because
each bit can have two different values (0 or
1) and N bits can have 2N values.
o A gateway is generally software installed o IPv4 uses 32-bit addresses, which means
within a router. that the address space is 232.
 Notations
 LOGICAL ADDRESSING There are two prevalent notations to show an
o Usually,computers communicate through 1Pv4 address:
the Internet. The packet transmitted by the o Binary Notation
sending computer may pass through several  In binary notation, the IPv4 address is
LANs or WANs before reaching the displayed as 32 bits. Each octet is often
destination computer. referred to as a byte.
o For this level of communication, we need a Eg:
global addressing scheme; we called this 01110101100101010001110100000010
logical addressing. o Dotted-Decimal Notation
o The Internet addresses are 32 bits in length;  To make the 1Pv4 address more compact
this gives us a maximum of 232 addresses. and easier to read, Internet addresses are

[email protected] Page 5
 GEMS Arts and Science College

usually written in decimal form with a

decimal point (dot) separating the bytes.
 Eg: 117.149.29.2 o One problem with classful addressing is that
each class is divided into a fixed number of
blocks with each block having a fixed size
Fig:

 Classful Addressing
o IPv4 addressing, at its inception, used the
concept of classes. This architecture is 
Class A addresses were designed for
called classful addressing. large organizations with a large number
o In classful addressing, the address space is of attached hosts or routers.
divided into five classes: A, B, C, D, and E.  Class B addresses were designed for
o Each class occupies some part of the address midsize organizations with tens of
space. thousands of attached hosts or routers.
Fig:  Class C addresses were designed for
small organizations with a small
number of attached hosts or routers.
 Class D addresses were designed for
multicasting.
 Class E addresses were reserved for
future use
o The length of the netid and hostid (in bits) is
predetermined in classful addressing.

o Mask
 a mask is a 32-bit number in which the n
leftmost bits are ls and the 32 - n
rightmost bits are 0s.
 fig:

/n: slash notation or Classless

lnterdomain Routing (CIDR) notation.
 The notation is used in classless
addressing
 The mask can help us to find the netid
and the hostid.
o Subnetting

[email protected] Page 6
 GEMS Arts and Science College

If an organization was granted a large  The first address in the block can be
block in class A or B, it could divide the found by setting the 32 - n right-most
addresses into several contiguous groups bits in the binary notation of the address
and assign each group to smaller to 0s.
networks (called subnets) or, in rare  The first address can be found by
cases, share part of the addresses with ANDing the given addresses with the
neighbors. mask.
o Supernetting
 The size of a class C block with a  The last address in the block can be
maximum number of 256 addresses did found by setting the rightmost 32 - n
not satisfy the needs of most bits to ls.
organizations.  The last address can be found by ORing
 In supernetting, an organization can the given addresses with the
combine several class C blocks to create complement of themask.
a larger range of addresses. In other
words, several networks are combined to  The number of addresses in the block
create a super-network or a supernet. can be found by using the formula 232-n.
o Address Depletion  The number of addresses can be found
by complementing the mask,
 Classless Addressing interpreting it as adecimal number, and
o To overcome address depletion adding 1 to it.
o In this scheme, there are no classes, but the o The first address is called the network
addresses are still granted in blocks. address and defines the organization
o Address Blocks network.
 In classless addressing, when an entity,
small or large, needs to be connected to
the Internet, it is granted a block (range)  Network Address Translation (NAT)
of addresses. o The number of home users and small
 The size of the block (the number of businesses that want to use the Internet is
addresses) varies based on the nature and ever increasing.
size of the entity.  Many are not happy with one address;
o To simplify the handling of addresses, the many have created small networks with
Internet authorities impose three restrictions several hosts and need an IP address for
on classless address blocks: each host.
 The addresses in a block must be  With the shortage of addresses, this is a
contiguous, one after another. serious problem.
 The number of addresses in a block must  A quick solution to this problem is
be a power of 2 (1, 2, 4, 8, ... ). called network address translation
 The first address must be evenly divisible (NAT).
by the number of addresses. o NAT enables a user to have a large set of
o A better way to define a block of addresses is addresses internally and one address, or a
to select any address in the block and the small set of addresses, externally.
mask.  The traffic inside can use the large set;
the traffic outside, the small set.
[email protected] Page 7
 GEMS Arts and Science College

o The Internet authorities have reserved o The IPv6 consist of 16 bytes, it is 128 bits
three sets of addresses as private addresses. long.
 They are unique inside the organization, o IPv6 specifies Hexa-decimal notation
but they are not unique globally. Fig:
o The site must have only one single
connection to the global Internet through a
router that runs the NAT software.
Fig:

 128 bits divided into 8 sections, each 2

bytes in length.
 Address Translation  Two bytes in hexa decimal notation
o All the outgoing packets go through the requires four hexa decimal digits., with
NAT router, which replaces the source every four digits seperated by a colon.
address in the packet with the global NAT  IPv6 addresses are very long even in hexa
address. decimal format, many of the digits are 0s.
o All incoming packets also pass through the We can abbreviate this address. The
NAT router, which replaces the destination leading zeros of a section can be omitted.
address in the packet (the NAT router Fig:
global address) with the appropriate
private address.
Fig:

o NAT router has a translation table.

o Using One IP Address:  Address Space
 translation table has only two columns: o It has a much larger address space; 2128
the private· address and the external addresses are available.
address (destination address of the o A few left most bits, called the type prefix,
packet). in each address define its category.
o Using a Pool of IP Addresses o The type prefix is variable in length, but it is
 Since the NAT router has only one global designed such that no code is identical to the
address, only one private network host can first part of any other code.
access the same external host. o Categories:
 To remove this restriction, the NAT router  Unicast addresses.
uses a pool of global addresses.  Multicast addresses
 Anycast addresses.
 IPv6 ADDRESS  Reserved Addresses
 STRUCTURE  Local Addresses

[email protected] Page 8
 GEMS Arts and Science College

 INTERNETWORKING
o The physical and data link layers of a
o Unicast Addresses network operate locally.
 A unicast address defines a single FIG:
computer.
 The packet sent to a unicast address must
be delivered to that specific computer.
o Multicast Addresses
 Multicast addresses are used to define a
group of hosts instead of just one.
 A packet sent multicast must be delivered
to each member of the group.
o Anycast Addresses
 An anycast address, like a multicast
address, also defines a group of nodes. o The network layer is responsible for host to
 However, a packet destined for an host delivery and for routing the packets
anycast address is delivered to one of the through the routers or switches.
members of the anycast group, the FIG:
nearest one.
o Reserved Addresses
 These addresses start with 8 zeros.
 Unspecified address:
 It is used when a host does not know
its own address and sends an inquiry
to find its address.
 Loopback address:
 It is used by host to test itself without
going to the network.
 Compatible address o The network layer at the source is
 It is used during the transmission from responsible for creating a packet from the
IPv4 to IPv6. data coming from another protocol.
 Mapped address  The header of the packet contains, among
 It is also used during transition. other information, the logical addresses
 Local Addresses: of the source and destination.
 These addresses are used when an  The network layer is responsible for
organization wants to use IPv6 checking its routing table to find the
protocol without being connected to routing information.
the global internet.  Fig:

[email protected] Page 9
 GEMS Arts and Science College

o Communication at the network layer in the

Internet is connectionless.
 The network layer protocol treats each
packet independently, with each packet
having no relationship to any other
packet.
 The packet in a message may or may
not travel the same path to their
destination.
 This type of service is used in the
datagram approach to packet switching.
 IPv4
o The IPv4 is the delivery mechanism used by
the TCP/IP protocols.
o It is an unreliable and connectionless
datagram protocol.
o The network layer at the destination is o It provides no error control or flow control.
responsible for address verification. o It assumes the unreliability of the underlying
 Fig layers and does its best to get a transmission
through to its destination, but with no
guarantees.
o It uses datagram approach.
 Each datagram is handled
independently, and each datagram can
follow a datagram different route to the
destination. This implies that datagrams
sent by same source to the same
destination could arrive out of order,
 Datagrams

 INTERNET AS DATAGRAM NETWORK

o The internet has chosen the datagram
approach to switching in the network layer.
o Delivery of a packet can be accomplished by o Packets in the IPv4 layer are called
using either a connection oriented or a datagrams.
connectionless network service. o It is variable length packet consisting of two
parts: header and data.
[email protected] Page 10
 GEMS Arts and Science College

o An header field contains: o This makes transmission more efficient if

 Version(VER): we use protocol with an MTU of this size.
 It defines the version of the IPv4 o For other physical networks, we must
protocol. divide the datagram to make it possible to
 Header Length(HLEN) pass through these networks. this is called
 It defines the total length of the fragmentation.
datagram header. o Fig:
 Services
 Two types of services: service type,
differentiated services.
 Total length
 It defines the total length of IPv4
datagram in bytes.
 Identification
 Used in fragmentation.  IPv6
 Flags o IPv4 has some deficiencies:
 Used in fragmentation.  Address depletion
 Fragmentation offset  The internet must accommodate real time
 Used in fragmentation. audio and video transmission.
 The internet must accommodate
 Time to live
encryption and authentication of data for
 It is designed to hold a time stamp,
some applications.
which was decremented by each
o Advantages of IPv6
visited router. The datagram
 Larger address space
discarded when the value became
 Better header format
zero.
 New options
 Protocol
 Allowance for extension
 The 8 bit field defines the higher
 Support for resource allocation.
level protocol that uses the services
 support for more security
of the IPv4 layer.
 Checksum
 Packet Format
 Error detection
Fig:
 Source address:
 Defines the IPv4 address of the
source
 Destination address
 Defines the IPv4 address of the
destination

 Datagrams
o To make the IPv4 protocol independent of
the physical network, the designers
decided to make the maximum length of
the IPv4 datagram equal to 65535.

[email protected] Page 11
 GEMS Arts and Science College

o Fig:
o Version
 The version number of IP
o Priority
 The priority of the packet with respect to
traffic congestion.
o Flow label:
 To provide a special handling for a o Dual Stack
particular flow of data.  Before migrating completely to version 6,
o Payload length: have a dual stack of protocols.
 The length of the IP datagram excluding  A station must run IPv4 and IPv6
the base header. simultaneously until all the internet uses
o Next header IPv6.
 Defining the header that follows the base
header in the datagram
o Hop limit
 8 bit.
o Source address
 Identifies that the original source of the
datagram
o Destination address
 Identifies the final destination of the
datagram.
o Tunneling
 Comparison between IPv4 and IPv6 headers
 It is a strategy used when two computers
o The header length field is eliminated in IPv6
using IPv6 wants to communicate with
because the length of the header is fixed in
each other and the packet must pass
this version.
through a region that uses IPv4.
o The service type field is eliminated in IPv6.
 To pass through this region, the packet
the priority and flow label fields together take
must have an IPv4 address.
over the function of the service type field.
 So the IPv6 packet encapsulated in an
o The total length field is eliminated in IPv6
IPv4 packet when it enters the region ,
and replaced by the payload length field.
and it leaves its capsule when it exits the
o The identification, flag, and offset fields are
region.
eliminated from the base header in IPv6. they
are include in the fragmentation extension
header.
o The TTL field is called hop limit in IPv6.
o The product field is replaced by the next
header field.
o
 Transition fromIPv4 to IPv6 o Header Translation
o Three strategies have been devised to help the  When the sender wants to use IPv6 but
transition. the receiver does not understand IPv6.

[email protected] Page 12
 GEMS Arts and Science College

 In this case, the header format must be physical address. This table is stored in
totally changed through header each machine on the network.
translation. o dynamic mapping
 The header of the IPv6 packet is o In this each time a machine knows one of
converted to an IPv4 header. the two addresses (logical or physical), it
can use a protocol to find the other one.

 Mapping Logical to Physical Address: ARP

o Sender knows the logical address of the
receiver.
o Sender needs the physical address of the
receiver.
 ADDRESS MAPPING  The host or the router sends an ARP
o A packet starting from a source host may query packet.
pass through several different physical  The packet includes the physical and IP
networks before finally reaching the addresses of the sender and the IP
destination host. address of the receiver.
o The hosts and routers are recognized at the  Because the sender does not know the
network level by their logical (IP) physical address of the receiver, the
addresses. query is broadcast over the network
o However, packets pass through physical  Fig:
networks to reach these hosts and routers.
o At the physical level, the hosts and routers
are recognized by their physical addresses.
 A physical address is a local address. Its
jurisdiction is a local network. It must
be unique locally, but is not necessarily
unique universally. It is called a
physical address because it is usually
(but not always) implemented in
hardware. o Every host or router on the network
o Delivery of a packet to a host or a router receives and processes the ARP query
requires two levels of addressing: packet, but only the intended recipient
 logical and recognizes its IP address and sends back an
 physical ARP response packet.
o We need to be able to map a logical address  The response packet contains the
to its corresponding physical address and recipient's IP and physical addresses.
vice versa.  The packet is unicast directly to the
 These can be done by using either static inquirer by using the physical address
or dynamic mapping. received in the query packet.
o Static mapping
 It involves in the creation of a table that
associates a logical address with a

[email protected] Page 13
 GEMS Arts and Science College

 Fig:  Mapping Physical to Logical Address: RARP,

BOOTP, and DHCP
o There are occasions in which a host knows
its physical address, but needs to know its
logical address. This may happen in two
cases:
 A diskless station is just booted. The
station can find its physical address by
o STEPS: checking its interface, but it does not
1. The sender knows the IP address of know its IP address.
the target.  An organization does not have enough IP
2. IP asks ARP to create an ARP addresses to assign to each station; it
request message, filling in the sender needs to assign IP addresses on demand.
physical address, the sender IP address, o RARP
and the target IP address. The target  Reverse Address Resolution Protocol
physical address field is filled with 0s. (RARP) finds the logical address for a
3. The message is passed to the data machine that knows only its physical
link layer where it is encapsulated in a address.
frame by using the physical address of the o BOOTP
sender as the source address and the  The Bootstrap Protocol (BOOTP) is a
physical broadcast address as the client/server protocol designed to provide
destination address. physical address to logical address
4. Every host or router receives the mapping.
frame. Because the frame contains a o DHCP
broadcast destination address, all stations  The Dynamic Host Configuration Protocol
remove the message and pass it to ARP. (DHCP) has been devised to provide static
All machines except the one targeted drop and dynamic address allocation that can be
the packet. The target machine recognizes manual or automatic.
its IP address.
 ICMP
5. The target machine replies with an o The Internet Control Message Protocol
ARP reply message that contains its (ICMP) has been designed to compensate for
physical address. The message is unicast. the two deficiencies of IP.
6. The sender receives the reply  The IP protocol has no error-reporting
message. It now knows the physical or error-correcting mechanism.
address of the target machine.  The IP protocol also lacks a mechanism
7. The IP datagram, which carries for host and management queries.
data for the target machine, is now  Types of Messages
encapsulated in a frame and is unicast to o ICMP messages are divided into two broad
the destination. categories:
 error-reporting messages
 query messages.

[email protected] Page 14
 GEMS Arts and Science College

o The error-reporting messages report problems  To get update the address of the host,
that a router or a host (destination) may it sends an redirection message
encounter when it processes an IP packet.
o The query messages, which occur in pairs,  IGMP
help a host or a network manager get specific o Some processes sometimes need to send the
information from a router or another host. same message to a large number of receivers
o ICMP always reports error messages to the simultaneously. This is called multicasting,
original source. which is a one-to-many communication.
o Five types of errors are handled: o The Internet Group Management Protocol
 destination unreachable (IGMP) is one of the necessary, but not
 When a router cannot route a datagram sufficient, protocols that is involved in
or a host cannot deliver a datagram, the multicasting.
datagram is discarded and the router or o IGMP is not a multicasting routing protocol;
the host sends a destination- it is a protocol that manages group
unreachable message back to the source membership.
host that initiated the datagram. o The IGMP protocol gives the multicast
 source quench routers information about the membership
 When a router or host discards a status of hosts (routers) connected to the
datagram due to congestion, it sends a network.
source-quench message to the sender of
the datagram.
 time exceeded
 The time-exceeded message is
generated in two cases:
1. If there are errors in one or more
routing tables, a packet can travel in  DELIVERY
a loop or a cycle, going from one o Delivery refers to the way a packet is
router to the next or visiting a series handled by the underlying networks under
of routers endlessly. the control of the network layer.
2. When the time-to-live value reaches o The delivery of a packet to its final
0, after decrementing, the router destination is accomplished by using two
discards the datagram. different methods of delivery:
 Direct delivery: if the final destination
 parameter problems of the packet is a host connected to the
 If a router or the destination host same physical network as the deliverer.
discovers an ambiguous or missing
value in any field of the datagram, it
discards the datagram and sends a
parameter-problem message back to
the source.
 Redirection
 The hosts usually use static routing.
 The router update its table
dynamically.
[email protected] Page 15
 GEMS Arts and Science College

about the complete route (route

method).

 Network-Specific Method Versus Host-

Specific Method:
Instead of having an entry for every
desti-nation host connected to the same
physical network (host-specific method),
we haveonly one entry that defines the
address of the destination network itself.
 Default Method

o Forwarding Process

 Indirect Delivery: if the destination host

is not on the same network as the
deliverer, the packet is deliv-ered
indirectly.  ROUTING
o Routing refers to the way routing tables are
created to help in forwarding.
o A host or a router has a routing table with
an entry for each destination, or a
combination of destinations, to route IP
packets.
o The routing table can be either static or
dynamic.
 A static routing table contains
information entered manually. The
administrator enters the route for each
destination into the table.
 A dynamic routing table is updated
 FORWARDING periodically by using one of the dynamic
o Forwarding refers to the way a packet is routing protocols such as RIP, OSPF, or
delivered to the next station. BGP.
 Forwarding Techniques o an internet is divided into autonomous
o Several techniques can make the size of the systems.
routing table manageable and also handle  An autonomous system (AS) is a group
issues such as security. of networks and routers under the
 Next-Hop Method Versus Route Method: authority of a single administration.
The routing table holds only the address  Routing inside an autonomous system is
of the next hop instead of information referred to as intradomain routing.

[email protected] Page 16
 GEMS Arts and Science College

 Routing between autonomous systems is

referred to as interdomain routing.

 Initialization
o At the beginning, Each node can know
onlythe distance between itself and its
immediate neighbors, those directly
connected to it.
o The distance for any entry that is not a
neighbor is marked as infinite (unreachable).

o Routing Information Protocol (RIP) is an

implementation of the distance vector
protocol.
o Open Shortest Path First (OSPF) is an  Sharing
implementation of the link state protocol. o The whole idea of distance vector routing is
o Border Gateway Protocol (BGP) is an the sharing of information between
implementation of the path vector protocol. neighbors.
o In distance vector routing, each node shares
its routing table with its immediate
 DISTANCE VECTORROUTING neighbors periodically and when there is a
o In distance vector routing, the least-cost change.
route between any two nodes is the route  Updating
with minimum distance. o When a node receives a two-column table
o In this protocol, as the name implies, each from a neighbor, it needs to update its
node maintains a vector (table) of minimum rout-ing table. Updating takes three steps:
distances to every node.  The receiving node needs to add the
cost between itself and the sending node
to each value in the second column.
 The receiving node needs to add the
name of the sending node to each row

[email protected] Page 17
 GEMS Arts and Science College

as the third column if the receiving node 2. Dissemination of LSPs to every other
uses information from any row. The router, called flooding, in an efficient and
sending node is the next node in the reliable way.
route. 3. Formation of a shortest path tree for each
 The receiving node needs to compare node.
each row of its old table with the 4. Calculation of a routing table based on
corresponding row of the modified the shortest path tree.
version of the received table.  Creation of Link State Packet (LSP)
 If the next-node entry is different, o LSPs are generated on two occasions:
the receiving node chooses the row  When there is a change in the topology
with the smaller cost. of the domain.
 If the next-node entry is the same,  On a periodic basis.
the receiving node chooses the new  Flooding of LSPs
row. o After a node has prepared an LSP, it must
be disseminated to all other nodes, not
only to its neighbors.
 Formation of Shortest Path Tree: Dijkstra
Algorithm

Example:
.

o The Routing Information Protocol (RIP)

is an intradomain routing protocol used
inside an autonomous system.

 LINK STATE ROUTNG

o In link state routing, if each node in the
domain has the entire topology of the domain
the list of nodes and links, how they are
connected including the type, cost (metric),
and condition of the links (up or down)-the
node can use Dijkstra's algorithm to build a
routing table.
o In link state routing, four sets of actions are
required to ensure that each node has the
routing table showing the least-cost node to
every other node.
1. Creation of the states of the links by each
node, called the link state packet (LSP).

[email protected] Page 18
 GEMS Arts and Science College

 Calculation of Routing Table from Shortest

Path Tree
o Each node uses the short-est path tree
protocol to construct its routing table.

o Open Shortest Path First or OSPF

protocol is an intradomain routing
protocol based on link state routing.

[email protected] Page 19