MODULE – 3��Network Layer

Text Book 1: Chapter 18.1, 18.3, 18.4, 19.1, 22.2, 20.1-20.3.3, 21.3.2

Communication at the network layer

Introduction to Network Layer

Introduction to Network Layer

• The figure shows that the Internet is made of many networks (or links) connected through the connecting devices.
• Internet is an internetwork, a combination of LANs and WANs.
• To better understand the role of the network layer (or the internetwork layer), we need to think about the connecting devices (routers or switches) that connect the LANs and WANs.
• As the figure shows, the network layer is involved at the source host, destination host, and all routers in the path (R2, R4, R5, and R7).

Introduction to Network Layer

• At the source (Alice): The network layer takes the packet from the transport layer, encapsulates(wrapping data with headers and trailers at each layer) it into a datagram, and sends it to the data-link layer.

​

• At the destination (Bob): The datagram is decapsulated, the packet is extracted, and passed up to the transport layer.

​

• Hosts (Alice & Bob) use all 5 TCP/IP layers, but routers mainly use network, data-link, and physical layers (sometimes transport/application for control).

​

• A router is shown with two data-link and two physical layers, since it connects one network to another.

Packetizing

• The primary duty of the network layer is packetizing—
• Encapsulating and decapsulating data to ensure secure and efficient delivery from source to destination
• The source host receives the payload from an upper-layer protocol, adds a header that contains the source and destination addresses and some other information that is required by the network-layer protocol and delivers the packet to the data-link layer. The source is not allowed to change the content of the payload unless it is too large for delivery and needs to be fragmented.

​

• The destination host receives the network-layer packet from its data-link layer, decapsulates the packet, and delivers the payload to the corresponding upper-layer protocol.

Packetizing

• If the packet is fragmented at the source or at routers along the path, the network layer is responsible for waiting until all fragments arrive, reassembling them, and delivering them to the upper-layer protocol.

​

• The routers in the path are not allowed to decapsulate the packets they received unless packets need to be fragmented.

​

• The routers are not allowed to change source and destination addresses either. They just inspect the addresses for the purpose of forwarding the packet to the next network on the path.

Routing and Forwarding

• In addition to packetizing, the network layer performs two critical duties: Routing and Forwarding.

Routing

• The network layer is responsible for routing the packet from its source to the destination.
• There will be more than one route from the source to the destination.
• The network layer is responsible for finding the best one among these possible routes.
• The network layer needs to have some specific strategies for defining the best route.
• Uses routing protocols to coordinate router knowledge and build routing tables.
• Routing protocols should run before communication begins to establish efficient paths.

Routing and Forwarding

Forwarding

​

• Routing = creating the decision-making table using protocols and strategies.�Forwarding = using that table to send packets to the correct output interface.
• The router looks at a piece of info in the packet header (like destination address or label)
• Matches it in the forwarding table → sends the packet to the right network.

​

Routing = Deciding where to go.

Forwarding = Actually sending the packet through interface.

Routing and Forwarding

Figure shows the idea of the forwarding process in a router.

This diagram shows how a router forwards packets using a forwarding table:

1. A packet with forwarding value B enters Interface 1

​

• The router looks up B in the table → it maps to Output Interface 2.

​

• The router sends the packet out of Interface 2, possibly changing the forwarding value (B → C)

​

Forwarding value identifies output interface; router sends packet accordingly.

Forwarding value is the piece of information inside a packet that the router/switch uses to decide where to send it next.

Other Services

Error Control

• Error control also can be implemented in the network layer,
• The packet in the network layer may be fragmented at each router, which makes error checking at this layer inefficient.
• The designers of the network layer, have added a checksum field to the datagram to control any corruption in the header, but not in the whole datagram.
• checksum prevent any changes or corruptions in the header of the datagram.
• 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 head.

Other services expected from the network layer

Other Services

Flow Control

• Flow control regulates the amount of data a source can send without overwhelming the receiver.
• If the upper layer at the source computer produces data faster than the upper layer at the destination computer can consume it, the receiver will be overwhelmed with data.
• To control the flow of data, the receiver needs to send some feedback to the sender to inform that it is overwhelmed with data.
• The network layer in the Internet, however, does not directly provide any flow control.
• The datagrams are sent by the sender when they are ready, without any attention to the readiness of the receiver.

Other Services

Congestion Control

• Another issue in a network-layer protocol is congestion control.
• Congestion in the network layer is a situation in which too many datagrams are present in an area of the Internet.
• Congestion may occur if the number of datagrams sent by source computers is beyond the capacity of the network or routers.
• However, as more datagrams are dropped, the situation may become worse because, due to the error control mechanism at the upper layers, the sender may send duplicates of the lost packets.
• If the congestion continues, sometimes a situation may reach a point where the system collapses and no datagrams are delivered.

Other Services

Quality of Service

• As the Internet has allowed new applications such as 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.

​

• The Internet has thrived by providing better quality of service to support these applications. However, to keep the network layer untouched, these provisions are mostly implemented in the upper layer.

Other Services

Security

• Another issue to communication at the network layer is security.
• The network layer was designed with no security provision.
• The Internet Protocol (IP) provides a connectionless service → packets are sent independently, with no built-in guarantee of delivery, order, or security.
• To add security features like authentication, integrity, and confidentiality, a virtual layer above IP is added.
• This layer is called IPSec (IP Security).

NETWORK-LAYER PERFORMANCE

• Delay
• Throughput
• Packet Loss
• Congestion Control

NETWORK-LAYER PERFORMANCE

1. Delay

​

Time taken for a packet to travel from source to destination.

​

​

NETWORK-LAYER PERFORMANCE

1. Delay

b. Propagation Delay

​

• Propagation delay is the time it takes for a bit to travel from point A to point B in the transmission 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 distance of the link.

​

​

​

NETWORK-LAYER PERFORMANCE

1. Delay

b. Propagation Delay

​

​

​

For example, if the distance of a cable link in a point-to-point WAN is 2000 meters and the propagation speed of the bits in the cable is 2 × 10⁸ meters/second, then the propagation delay is 10 microseconds.

​

NETWORK-LAYER PERFORMANCE

1. Delay

c. Processing Delay

• 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 (in the case of the destination host).

​

​

• The processing delay may be different for each packet, but normally is calculated as an average.

NETWORK-LAYER PERFORMANCE

1. Delay

d. Queuing Delay

• Time that a packet waits in input/output queues of a router.
• A router has an input queue connected to each of its input ports to store packets waiting to be processed;
• The router also has an output queue connected to each of its output ports to store packets waiting to be transmitted.
• The queuing delay for a packet in a router is measured as the time that a packet waits in the input queue and output queue of a router.

NETWORK-LAYER PERFORMANCE

1. Delay

Total Delay: Assuming equal delays for the sender, routers, and receiver, the total delay (source-to- destination delay) a packet encounters can be calculated if we know the number of routers, n, in the whole path.

​

If a packet goes from source → n routers → destination:

• Transmission Delay → Happens on every link. So, we have (n + 1) transmission delays.
• Propagation Delay → Also happens on every link. So, we have (n + 1) propagation delays.
• Processing Delay → Happens at each router and at the destination (not at the source). So, we have (n + 1) processing delays.
• Queuing Delay → Happens only at the routers (not at source or destination).So, we have n queuing delays.

NETWORK-LAYER PERFORMANCE

• 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.
• In a path with multiple links, each link may have different transmission rate.

​

NETWORK-LAYER PERFORMANCE

Throughput

• Step 1: Data enters Link1
• The source can send data at 200 kbps into Link1.
• Step 2: Data reaches Router R1 (Link2 starts)
• But Link2 can only handle 100 kbps.
• That means even if data comes at 200 kbps, only 100 kbps can pass through.
• The rest must wait in the queue at R1.
• → Now the flow rate is reduced to 100 kbps.

Step 3: Data reaches Router R2 (Link3 starts)

Link3 has a capacity of 150 kbps.

But the incoming data rate from Link2 is only 100 kbps.

Since there isn’t enough data (only 100 kbps available), Link3 also operates at 100 kbp

Step 4: Conclusion

The overall throughput of the path is 100 kbps.

Why? Because throughput is always limited by the bottleneck link (the slowest link).

Here, the bottleneck is Link2 (100 kbps).

General Formula

Throughput = minimum {TR₁, TR₂, …, TRₙ}`

NETWORK-LAYER PERFORMANCE

Throughput

• Throughput in Internet Backbone
• Internet backbone has very high transmission rate (Gbps range).
• Throughput usually defined as minimum transmission rate of access links.
• For example, if a server connects to the Internet via a Fast Ethernet LAN with the data rate of 100 Mbps, but a user who wants to download a file connects to the Internet via a dial-up telephone line with the data rate of 40 kbps, the throughput is 40 kbps. The bottleneck is definitely the dial-up line.

NETWORK-LAYER PERFORMANCE

Throughput

• Throughput in Shared Links
• Link between routers may be shared by several flows.
• Transmission rate is divided among flows.
• Main link TR = 600 kbps
• Shared between 3 paths → throughput = 200 kbps per path.

NETWORK-LAYER PERFORMANCE

Packet Loss

• Packet loss severely affects communication performance.
• If router is busy, new packets are stored in input buffer.
• Input buffer has limited size → may become full.
• When buffer is full → new packets are dropped.
• Lost packets must be resent, causing congestion and more loss.
• Queuing theory used to reduce buffer overflow & packet loss.

NETWORK-LAYER PERFORMANCE

Congestion Control

​

Mechanism for improving performance

• Congestion at the network layer is related to two issues, throughput and delay
• When the network load is much less than its capacity, the delay is minimal, consisting mostly of negligible propagation and processing delays.
• As the load approaches the network capacity, delay increases sharply due to the addition of queuing delay.
• Delay becomes infinite if the load exceeds the network capacity.
• When load is below capacity, throughput increases proportionally with the load.
• Throughput does not remain constant after reaching capacity; instead, it declines sharply.

​

NETWORK-LAYER PERFORMANCE

Congestion Control

• The decline in throughput is caused by packet discarding at routers when queues become full.
• Packet discarding does not reduce network packets because sources retransmit lost packets using time-out mechanisms.
• 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).

NETWORK-LAYER PERFORMANCE

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.
• list of policies that can prevent congestion.
• Retransmission Policy
• Window Policy
• Acknowledgment Policy
• Discarding Policy
• Admission Policy

NETWORK-LAYER PERFORMANCE

Open-Loop Congestion Control

​

• Retransmission Policy
• Retransmission is necessary when packets are lost or corrupted, but it can increase network congestion. Designing good retransmission policies and timers helps optimize efficiency and prevent congestion.

​

• Window Policy
• The type of sender window impacts congestion control.
• Selective Repeat is better than Go-Back-N because it retransmits only the lost or corrupted packets, reducing duplication and congestion.
• Go-Back-N resends several packets when one times out, even if some were received correctly, increasing congestion.

NETWORK-LAYER PERFORMANCE

Open-Loop Congestion Control

​

• Acknowledgment Policy
• The receiver’s strategy for sending acknowledgments affects congestion.
• Sending fewer acknowledgments can slow down the sender and help avoid congestion.
• Methods include sending an acknowledgment only when there is data to send, after a timer expires, or after receiving multiple packets at once.
• Acknowledgments contribute to network load.

​

• Discarding Policy
• Routers can prevent congestion by discarding fewer sensitive packets first during congestion, maintaining overall transmission quality (e.g., discarding less important audio packets to preserve sound quality).

​

• Admission Policy
• A quality-of-service mechanism where switches check resource requirements before admitting a flow.
• Routers can deny virtual-circuit connections if network congestion exists or might occur, preventing congestion proactively.

NETWORK-LAYER PERFORMANCE

Closed-Loop Congestion Control

• Closed-loop congestion control mechanisms try to alleviate congestion after it happens.
• Several mechanisms have been used by different protocols.
• Backpressure
• Choke Packet
• Implicit Signaling
• Explicit Signaling

NETWORK-LAYER PERFORMANCE

Closed-Loop Congestion Control

​

Backpressure

• A congestion control method where a congested node stops receiving data from its immediate upstream node(s), causing a chain reaction upstream until the source is informed to slow down.
• It works node-to-node in the opposite direction of data flow.
• Applicable only to virtual circuit networks because each node knows its upstream node.
• Helps alleviate congestion by propagating pressure backward to the source.

​

NETWORK-LAYER PERFORMANCE

Node III in the figure has more input data than it can handle. It drops some packets in its input buffer and informs node II to slow down. Node II, in turn, may be congested because it is slowing down the output flow of data. If node II is congested, it informs node I to slow down, which in turn may create congestion. If so, node I informs the source of data to slow down.

Closed-Loop Congestion Control

​

Backpressure

NETWORK-LAYER PERFORMANCE

Closed-Loop Congestion Control

Choke Packet

• A packet sent by a congested node directly to the source to notify it of congestion.
• Unlike backpressure, the warning comes directly from the congested node to the source, bypassing intermediate nodes.
• Used in IP routers via ICMP source quench messages to inform the source of congestion.

NETWORK-LAYER PERFORMANCE

Closed-Loop Congestion Control

Implicit Signaling

• The source gathers congestion without direct communication from the network based on symptoms, such as a delay or absence of acknowledgments.
• The source guesses congestion is occurring and slows down accordingly.
• Seen in TCP congestion control.

​

Explicit Signaling

• Congested nodes send explicit signals embedded within data packets to indicate congestion.
• Different from choke packets because the signal is within regular data packets, not separate control packets.
• Signals can travel forward or backward.

IPV4 ADDRESSES

• The identifier used in the TCP/IP protocol suite for each device's connection to the Internet is called an 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.
• If a device has two connections to the Internet, via two networks, it has two IPv4 addresses.

Address Space

• A protocol like IPv4 defines an address space, which is the total number of addresses used by the protocol. If a protocol uses b bits to define an address, the address space is 2^b.
• Since IPv4 uses 32-bit addresses, the address space is 2³², equating to 4,294,967,296 addresses (over four billion).
• IPv4 can support over 4.29 billion unique addresses.

IPV4 ADDRESSES

• Address Space

Notation: There are three common notations to show an IPv4 address:

• Binary Notation: Displays the IPv4 address as 32 bits, often with spaces inserted between each octet (8 bits). Each octet is referred to as a byte.
• Dotted-Decimal Notation: To make the IPv4 address more compact and easier to read, it is usually written in decimal form with a decimal point (dot) separating the byte. Each byte (octet) is only 8 bits, each number in the dotted-decimal notation is between 0 and 255.
• Hexadecimal Notation: We sometimes see an IPv4 address in hexadecimal notation. 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.

IPV4 ADDRESSES

• Address Space
• Hierarchy in Addressing
• In any communication network that involves delivery, such as a telephone network or a postal network, the addressing system is hierarchical.
• For example, a postal address includes country, state, city, street, and house number. Similarly, a telephone number includes country code, area code, and local exchange.
• 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 (connection of a device to the Internet)
• The prefix length is n bits and the suffix length is (32 − n) bits.

IPV4 ADDRESSES

IPV4 ADDRESSES

Figure shows the prefix and suffix of a 32-bit IPv4 address

Address Space

Hierarchy in Addressing

• 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).
• whole address space was divided into five classes (class A, B, C, D, and E),

IPV4 ADDRESSES

• Classful Addressing

​

Class A

• 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⁷ = 128 networks in the world that can have class A address.
• | 0 | network ID (7 bits) | host ID (24 bits) |

Class B

• Class B, the network length is 16 bits, but since the first two bits, which are (10)₂, define the class we can have only 14 bits as the network identifier.
• This means there are only 2¹⁴ =16,384 networks in the world that can have a class B address.
• | 10 | network ID (14 bits) | host ID (16 bits) |

IPV4 ADDRESSES

• Classful Addressing

​

Class C

• All addresses that start with (110)² 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.
• There are 2²¹ = 2,097,152 networks in the world that can have a class C address
• | 110 | network ID (21 bits) | host ID (8 bits) |

Class D is not divided into prefix and suffix. It is used for multicast addresses(sending data to a group of hosts at once).

Class E is not divided into prefix and suffix and is used as reserve.

• All addresses that start with 1111 in binary belong to class E.

​

IPV4 ADDRESSES

Class A

• Class A addresses were designed for large organizations with a large number of attached hosts or routers.
• In a Class A network, the first eight bits, or the first dotted decimal, is the network part of the address, with the remaining part of the address being the host part of the address. There are 128 possible Class A networks.

0.0.0.0 to 127.0.0.0

​

IPV4 ADDRESSES

Classful Addressing

Identifies the network   Identifies a specific device 

First octet: 0-127 (binary: 00000000-01111111)

Class B

• Class B addresses were designed for midsize organizations with tens of thousands of attached hosts or routers.
• In a Class B network, 2 bytes for class type and netid and 2 bytes for hosted.
• All Class B networks have their first bit set to 1 and the second bit set to 0.
• In dotted decimal notation, that makes 128.0.0.0 to 191.255.0.0 as Class B networks.
• There are 16,384 possible Class B networks.
• Example for a Class B IP address:

IPV4 ADDRESSES

Classful Addressing

135.168.24.14 First octet: 128-191 (binary: 10000000-10111111)

Class C

• Class C addresses were designed for small organizations with a small number of attached hosts or routers.
• It uses 3 bytes for class type and net id and 1 byte for hos tid.
• In a Class C network, the first two bits are set to 1, and the third bit is set to 0.
• That makes the first 24 bits of the address the network address and the remainder as the host address.
• Class C network addresses range from 192.0.0.0 to 223.255.255.0. There are over 2 million possible Class C networks.

192.168.178.1

IPV4 ADDRESSES

Classful Addressing

First octet: 192-223 (binary: 11000000-11011111)

Class D

• Class D addresses are used for multicasting applications.
• Class D addresses have their first three bits set to “1” and their fourth bit set to “0”.
• Class D addresses are 32-bit network addresses, meaning that all the values within the range of 224.0.0.0 – 239.255.255.255 are used to uniquely identify multicast groups.
• There are no host addresses within the Class D address space, since all the hosts within a group share the group’s IP address for receiver purposes, rather than individual host.

227.16.6.176

IPV4 ADDRESSES

Classful Addressing

Class E

• Class E addresses are reserved for future use, in which addresses beginning with 1111.
• Class E networks are defined by having the first four network address bits as 1.
• That encompasses addresses from 240.0.0.0 to 255.255.255.255. While this class is reserved, its usage was never defined.
• As a result, most network implementations discard these addresses as illegal or undefined. 

243.164.89.28

IPV4 ADDRESSES

Classful Addressing

IPV4 ADDRESSES

Classful Addressing

• Address Depletion : Classful addressing was discontinued because it wasted addresses, causing them to run out quickly.
• Class A, which could only be assigned to 128 organizations, provided more addresses (16.7 million per network) than most needed, resulting in wasted space.

Most organizations didn’t need millions of devices, maybe only thousands.

• Class B, for midsize organizations, also had many unused addresses.
• Class C's flaw was offering too few addresses (256 per network), making it impractical for many companies.
• Class D addresses are not for normal devices. They are used for multicast, which means sending data to a group of devices at once.
• Class E was rarely used, leading to further waste.

IPV4 ADDRESSES

Classful Addressing

• Subnetting and Supernetting

Two strategies were proposed to address depletion: subnetting and supernetting.

​

• Subnetting divides large blocks (Class A or B) into smaller subnets with longer prefixes, but it failed because large organizations didn't want to share unused addresses.

​

• Supernetting combined multiple Class C blocks to create larger blocks for organizations needing more than 256 addresses, but it made routing complicated and didn’t fully solve the problem.

IPV4 ADDRESSES

Classful Addressing

• Advantage of Classful Addressing
• 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.

IPV4 ADDRESSES

Classful Addressing

• Classless Addressing
• Subnetting and supernetting couldn’t completely solve the address shortage. As the Internet grew, a bigger address space was needed, which led to IPv6.
• Meanwhile, a short-term solution was classless addressing, which kept IPv4 but removed fixed class boundaries for fairer address distribution.
• ISPs helped by dividing large address ranges and giving smaller blocks (like 1, 2, or 4 addresses) to customers.
• Introduced in 1996, classless addressing allows variable-sized blocks, where the prefix identifies the network and the suffix identifies the device.
• Each block must have a power-of-2 number of addresses, and blocks do not overlap.

IPV4 ADDRESSES

• Classless Addressing

An ISP has the address block 192.168.0.0/24 (256 addresses).

A customer needs 64 addresses → ISP can assign 192.168.0.0/26

Another customer needs 32 addresses → ISP can assign 192.168.0.64/27

Another customer needs 16 addresses → ISP can assign 192.168.0.96/28

​

IPV4 ADDRESSES

• 192.168.0.0 → the starting address of the block.
• /26 → the prefix length, meaning the first 26 bits are the network part, and the remaining 6 bits are for hosts.

000000 → 192.168.0.0

000001 → 192.168.0.1

000010 → 192.168.0.2

...

111111 → 192.168.0.63

32 addresses

1. Number of addresses needed = 32
2. Number of host bits = log₂(32) = 5 bits (because 2⁵ = 32)
3. Prefix length = 32 − 5 = /27

So, a block of 32 addresses = /27

• Classless Addressing
• In classless addressing, the prefix length is variable, ranging from 0 to 32.
• Different blocks can have different sizes Within a block, the prefix is fixed.
• A shorter prefix indicates a larger network, while a longer prefix means a smaller network.
• Classless addressing can be applied to classful addressing by treating Class A as having a prefix of 8, Class B with a prefix of 16, and so on.

IPV4 ADDRESSES

• Prefix Length and Slash Notation (CIDR)
• In classless addressing, the prefix length (n) is added to the address, separated by a slash, known as slash notation or CIDR (Classless Inter-Domain Routing).
• For example, in 167.199.170.82/27, "27" is the prefix length. This notation is necessary since the address alone does not define the block.

IPV4 ADDRESSES

Classless Addressing

IPV4 ADDRESSES

The IPv4 header

IPV4 ADDRESSES

The IPv4 header/ IPV4 Datagram

IPV4 ADDRESSES

The IPv4 header/ IPV4 Datagram

Header:

• 20 to 60 bytes in length.
• Contains crucial fields to ensure the proper routing and handling of the packet.
• Shown in 4-byte (32-bit) sections for easy reference.
• Payload:
• Contains the data from the upper-layer protocols, such as TCP, UDP, or other transport or network protocols.

IPV4 ADDRESSES

• Version (4 bits): Indicates the IP protocol version, which is IPv4.
• Internet Header Length (4 bits): Shows the length of the IPv4 header in 32-bit words;
• Type of Service (8 bits): Defines the quality of service (QoS) for the packet, including routing priorities.
• Total Length (16 bits): Specifies the entire packet length, including header and data, in bytes.
• Identification (16 bits): Used for packet fragmentation and reassembly to group fragments.
• Flags (3 bits): Control packet fragmentation; includes "Don't Fragment" (DF) and "More Fragments" (MF) flags.
• Fragment Offset (13 bits): Indicates the position of a fragment within the original packet for correct reassembly.

IPV4 ADDRESSES

• Time to Live (TTL) (8 bits): TTL value decides how long a packet can stay in the network.
• Protocol (8 bits): Identifies the protocol used in the packet's data, such as TCP or UDP.
• Header Checksum (16 bits): Verifies the IPv4 header's integrity during transmission.
• Source IP Address (32 bits): Contains the sender's IP address.
• Destination IP Address (32 bits): Holds the recipient's IP address.
• Options: This field includes extra settings or features that can be used for special functions like routing or security.
• Padding: Extra zeros added at the end of the header to make sure its length is a multiple of 4 bytes(If the header size isn’t a multiple of 4, the data part would start at an uneven position).

IPV4 ADDRESSES

Fragmentation in IPv4:�If a packet is too large for a network (exceeds the MTU-Maximum Transmission Unit), routers can fragment it into smaller packets.

• How Fragmentation Works:�The router splits the original packet into smaller fragments, each with its own IP header. The "more fragments" flag is set, and the fragments are sent independently to the destination for reassembly.
• The destination reassembles the fragments into the original packet.
• Packet is too big: If the DF (Don't Fragment) flag is set in the packet header, routers cannot fragment the packet. If the packet is too large for a link, it will be dropped, and an ICMP "Packet Too Big" message will be sent back to the sender.

Extracting Information from an Address Block

• Given a classless address, the following three pieces of information can be extracted:

IPV4 ADDRESSES

Classless Addressing

• Number of addresses (N = 2^(32 − n)): Tells how many IP addresses are in that block.

Example: if /27, then N = 2^(32−27) = 32 addresses.

• First address: Keep the first n bits (the network part) the same.

Change the remaining bits (host part) to 0s.

This gives the starting address of the block.

• Last address: Keep the first n bits the same.

Change the remaining bits to 1s.

This gives the ending address of the block.

Extracting Information from an Address Block

• Example
• A classless address is given as 167.199.170.82/27. We can find the above three pieces of information as follows.
• The number of addresses in the network is 2^{32 − n} = 2⁵ = 32 addresses.
• First address: 167.199.170.64, -> 10100111.11000111.10101010.01000000
• Last address: 167.199.170.95, -> 10100111.11000111.10101010.01011111

​

​

IPV4 ADDRESSES

Classless Addressing

00010 → last bit = 0 → address = 167.199.170.66

167.199.170.64

IPV4 ADDRESSES

Classless Addressing

Address Mask

• Another way to find the first and last addresses in the block is to use the 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.

IPV4 ADDRESSES

Classless Addressing

Step 1: Subnet mask

• /27 → 27 network bits, 5 host bits
• In binary, the mask is:

11111111.11111111.11111111.11100000

• It separates which bits of an IP address are fixed for the network and which bits can vary for host.

Step 2: Number of addresses

• Formula: N = NOT(mask) + 1
• NOT(mask) flips all bits of the mask:

Mask: 11111111.11111111.11111111.11100000

NOT(mask): 00000000.00000000.00000000.00011111

• Convert 00011111 to decimal → 31
• Add 1 → N = block contains 32 addresses

Address Mask

IPV4 ADDRESSES

Classless Addressing

Step 4: Last address

• Formula: Any address OR NOT(mask)
• OR 167.199.170.82 with NOT(mask):

Address: 10100111.11000111.10101010.01010010

NOT(mask): 00000000.00000000.00000000.00011111

------------------------------------------------

Result: 10100111.11000111.10101010.01011111

• Convert back to decimal → 167.199.170.95

Step 3: First address

• Formula: Any address AND mask
• Take 167.199.170.82 (binary: 10100111.11000111.10101010.01010010)
• AND with mask:

Address: 10100111.11000111.10101010.01010010

Mask: 11111111.11111111.11111111.11100000

-------------------------------------------

Result: 10100111.11000111.10101010.01000000

• Convert back to decimal → 167.199.170.64

Network Address

• The first address, the network address, is particularly important because it is used in routing a packet to its destination network.
• let us assume that an internet is made of m networks and a router with m interfaces.
• When a packet arrives at the router from any source host, the router needs to know to which network the packet should be sent: from which interface the packet should be sent out.

IPV4 ADDRESSES

Network Address

• After the network address has been found, the router consults its forwarding table to find the corresponding interface from which the packet should be sent out.
• The network address is actually the identifier of the network; each network is identified by its network address.

IPV4 ADDRESSES

Block Allocation

IPV4 ADDRESSES

Block Allocation

IPV4 ADDRESSES

Subnetting

• Subnetting More levels of hierarchy can be created using subnetting.
• An organization (or an ISP) that is granted a range of addresses may divide the range into several subranges and assign each subrange to a subnetwork.
• Note that nothing stops the organization from creating more levels.
• A subnetwork can be divided into several sub-subnetworks. .

​

IPV4 ADDRESSES

Designing subnets

• The subnetworks in a network should be carefully designed to enable the routing of packets.
• We assume the total number of addresses granted to the organization is N, the prefix length is n, the assigned number of addresses to each subnetwork is N_sub, and the prefix length for each subnetwork is n_sub.

​

The steps need to be carefully followed to guarantee the proper operation of the subnetworks.

• The number of addresses in each subnetwork should be a power of 2.
• The prefix length for each subnetwork should be found using the following formula:�n_sub = 32 − log₂N_sub
• The starting address in each subnetwork should be divisible by the number of addresses in that subnetwork. This can be achieved if we first assign addresses to larger subnetworks.

​

Subnetting

IPV4 ADDRESSES

Subnetting

Example: An organization has a block starting at 14.24.74.0/24, with 256 addresses, and needs three subnetworks: one with 120, one with 60, and one with 10 addresses.

• 120 addresses: Allocate 128 addresses (nearest power of 2), with a subnet mask of /25, from 14.24.74.0 to 14.24.74.127.
• 60 addresses: Allocate 64 addresses, with a subnet mask of /26, from 14.24.74.128 to 14.24.74.191.
• 10 addresses: Allocate 16 addresses, with a subnet mask of /28, from 14.24.74.192 to 14.24.74.207.

The remaining 48 addresses are reserved, ranging from 14.24.74.208 to 14.24.74.255.

IPV4 ADDRESSES

Subnetting

IPV4 ADDRESSES

• /25 → 32 − 25 = 7 host bits → 2^7 = 128 addresses
• That’s why the 120-address subnet is allocated /25, which gives 128 addresses.

Address Aggregation

• Address aggregation, address summarization or route summarization, is a CIDR benefit. When blocks of addresses are combined to create a larger block, routing can be done based on the prefix of the larger block.
• ICANN assigns a large block of addresses to an ISP. Each ISP in turn divides its assigned block into smaller subblocks and grants the subblocks to its customers.

Example: An ISP has four smaller blocks, each serving a separate organization, but it can combine them into one larger advertised block. This consolidation streamlines routing for all incoming traffic destined for the ISP.

IPV4 ADDRESSES

Address Aggregation

IPV4 ADDRESSES

Special IPv4 Addresses

IPv4 includes addresses reserved for specific purposes:

• This-Host Address (0.0.0.0/32): Used when a host sends a datagram but doesn’t know its own IP.
• Limited-Broadcast Address (255.255.255.255/32): Sends a message to all devices within a network but cannot travel outside it.
• Loopback Address (127.0.0.0/8): Used to test software within a single host; packets with this address stay within the host.
• Private Addresses: Four ranges reserved for local use, which are not routable over the internet: 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16, and 169.254.0.0/16.
• Multicast Addresses (224.0.0.0/4): Used to send data to multiple hosts in a group.

IPV4 ADDRESSES

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

• Address assignment in an organization can be done automatically using the Dynamic Host Configuration Protocol (DHCP).
• DHCP is an application-layer program, using the client-server paradigm, that actually helps TCP/IP at the network layer.
• DHCP has found such widespread use in the Internet that it is often called a plug-and-play protocol.
• In can be used in many situations. A network manager can configure DHCP to assign permanent IP addresses to the host and routers.
• DHCP can also be configured to provide temporary, on demand, IP addresses to hosts. The second capability can provide a temporary IP address to a traveller to connect her laptop to the Internet while she is staying in the hotel.

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

How DHCP works

​

• DHCP runs at the application layer of the TCP/IP protocol stack to dynamically assign IP addresses to DHCP clients/nodes and to allocate TCP/IP configuration information to the DHCP clients. Information includes subnet mask information, default gateway, IP addresses and domain name system addresses.

​

• DHCP is based on client-server protocol in which servers manage a pool of unique IP addresses, as well as information about client configuration parameters, and assign addresses out of those address pools.

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

• When a device connects to a network and needs an IP address, it sends a DHCPDISCOVER message to the broadcast IP address (255.255.255.255), which reaches all devices on that network.

​

• A relay agent on the network, configured to communicate with the DHCP server, picks up this message and forwards it directly to the server.

​

• The DHCP server responds with an IP address offer, which the relay agent then sends back to the requesting device.

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

DHCP message format

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

DHCP message format

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

DHCP message format

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

DHCP message format

DHCP messages have a specific format, shown in Figure 18.25. The key fields in a DHCP message include:

1. Option Field: This 64-byte field DHCP include extra details: for example, IP address, subnet mask, DNS server, or gateway
2. Magic Cookie: Helps the client identify where the options section begins, so it can correctly read the message.

Options: Contains settings and parameters, divided into:

• Tag: 1 byte – tells what type of option it is.
• Length: 1 byte – shows how long the value is.
• Value: Variable length – the actual data or setting.

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

DHCP message format

The tag field’s value may vary depending on the option type. For instance, if the tag is 53, the value field specifies one of the eight DHCP message types, as seen in Figure 18.26.

​

These message types help manage the IP address assignment process, making it easier for network devices to connect dynamically to networks.

Option format

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

DHCP message format

• The tag field’s value may vary depending on the option type. For instance, if the tag is 53, the value field specifies one of the eight DHCP message types, as seen in Figure 18.26.
• These message types help manage the IP address assignment process, making it easier for network devices to connect dynamically to networks.

Option format

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

DHCP Operation

DHCP lease time is the amount of time a device is allowed to use a specific IP address from a DHCP server.

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

DHCP Operation

• DHCPDISCOVER: When a device (host) wants an IP address, it sends out a message called DHCPDISCOVER. This message is broadcasted to the network because the device doesn’t know its IP or the DHCP server’s IP. The device sends it over UDP, from port 68 (its source) to port 67 (the server’s destination), with a randomly chosen transaction ID to identify the request.

​

• DHCPOFFER: The DHCP server(s) respond with a DHCPOFFER message. This reply includes an available IP address for the device, the server’s own IP, and details about how long the IP lease will last. This message is also broadcasted so other DHCP servers can see it. The server sends it from port 67 to the device’s port 68, ensuring it reaches the correct device.

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

• DHCPREQUEST: The device (client) reviews the IP address offers it received and picks one. It then sends back a DHCPREQUEST message to the server that made the preferred offer, filling in the known details. This message is broadcast to let other DHCP servers know that their offers were declined. The client uses the new IP address as the source address, and it sends the message from port 68 to port 67.

​

• DHCPACK/DHCPNACK: The chosen server replies with a DHCPACK message to confirm the IP assignment if the IP is still available. If it’s not (for example, if it was assigned to another device in the meantime), the server sends a DHCPNACK, signaling the client to start over. This message is also broadcast, updating other servers on the outcome.

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

Two Well-Known Ports

• DHCP utilizes ports 68 and 67 to prevent conflicts with other applications. Port 68 is designated for the client, ensuring that responses are directed only to intended DHCP clients rather than to any other applications that might use a random port. This avoids confusion and ensures messages are processed correctly.

​

• Handling Multiple DHCP Clients
• In cases where multiple DHCP clients request addresses simultaneously, each message is uniquely identified by a transaction ID, preventing response mix-ups.

​

• FTP for Additional Information
• In the DHCPACK message, the server can include a file name that points to extra configuration details. The client can download this file using FTP (File Transfer Protocol) to get more information — such as DNS server addresses, boot files, or other network settings.

DHCP – DYNAMIC HOST CONFIGURATION PROTOCOL

Error Control in DHCP

​

DHCP employs two strategies:

1. It mandates UDP checksums for data integrity.

The checksum helps detect errors in data during transmission.� It checks if the message was damaged or changed while traveling through the network.

2. Clients use random timers for retransmissions to avoid congestion when multiple clients request IPs simultaneously.

​

Network Address Translation (NAT)

NAT (Network Address Translation) helps manage limited public IP addresses by allowing a network to use private IP addresses internally. When a device on this network connects to the Internet, the NAT router swaps its private IP with a single public IP address that the ISP provides. This way, the network stays hidden from the outside Internet, making it more secure.

Public IP (49.207.118.25)

Your Wi-Fi router connects all your home devices (like phone, laptop, and TV) using private IP addresses — for example:

Phone → 192.168.1.2

Laptop → 192.168.1.3

TV → 192.168.1.4

Network Address Translation (NAT)

• PC1 (192.168.1.10) sends a request to Web Server (203.0.113.50).
• The router receives it on inside interface (192.168.1.1).
• The router uses NAT to change the private source IP (192.168.1.10) → public IP (from pool), for example 203.0.113.10.
• The Web Server replies to 203.0.113.10, and the router translates it back to 192.168.1.10.
• PC1 gets the reply — communication successful

Network Address Translation (NAT)

• The Internet only sees one public IP address, given by your Internet provider.
• NAT is like a translator: when your device sends data to the Internet, NAT changes the private IP to the public IP. When data comes back, NAT sends it to the correct device inside. Many devices can share one public IP, and outsiders can’t see your private network.

Using One IP Address

​

Basic NAT configurations involve a translation table with two columns: private and external addresses. Communication must be initiated from the private network to maintain proper routing for responses

Network Address Translation (NAT)

Using a Pool of IP Addresses

​

To let many private devices connect to the internet at the same time, NAT can use a pool of public (global) IP addresses.�This means several private devices can reach the same website, but the number of active connections may depend on how many public IPs are available.

To handle many-to-many connections more efficiently, NAT also uses port numbers along with IP addresses.�Each device gets a different port number, so even if they all use the same public IP, the router can still tell which response belongs to which device.

THE IPv6 PROTOCOL

• Improved Header Format:

In the new design, options are kept separate from the main header and added only when needed.�This makes routing faster and easier, because routers don’t have to waste time checking extra, unused options.

​

New Options:

• IPv6 introduces new options for enhanced functionalities.

Protocol Extension:

• IPv6 is designed to allow future extensions to accommodate new technologies and applications.

THE IPv6 PROTOCOL

IPv6 Packet Format

• Structure: An IPv6 packet consists of a base header (40 bytes) followed by the payload, which can be up to 65,535 bytes.

​

​

The IPv4 base header size is 20 bytes.

If options are added, the header can grow up to 60 bytes

​

THE IPv6 PROTOCOL

IPv6 Packet Format

​

Base Header Fields:

1. Version (4 bits): Indicates the IP version (6 for IPv6).
2. Traffic Class (8 bits): This field marks the data based on how important it is, so the network knows which packets need faster or special handling.
3. Flow Label (20 bits): Used to identify packet flows(streaming) for Quality of Service (QoS).
4. Payload Length (2 bytes): Specifies the length of the payload/ actual data (excluding the header). The base header length is fixed.

THE IPv6 PROTOCOL

IPv6 Packet Format

​

• Next Header (8 bits): Identifies the type of header (TCP/UDP)
• Hop Limit (8 bits): Functions like the TTL field in IPv4, limiting the number of hops.
• Source Address (16 bytes): The IPv6 address of the packet's origin.
• Destination Address (16 bytes): The IPv6 address of the packet's intended recipient.

IPv6 uses 128 bits for addressing, compared to IPv4's 32-bit address space.

THE IPv6 PROTOCOL

IPv6 Packet Format

​

IPv6 datagram

Information for routing and handling the packet through the network

Actual data being transmitted

THE IPv6 PROTOCOL

IPv6 Packet Format

​

Payload Structure:

• The payload may contain zero or more extension headers and the actual data (e.g., UDP, TCP).
• Each extension header has two mandatory fields: next header and length, followed by specific option data.

Next Header (8 bits):

​

• Indicates what comes after this header
• Size of this extension header

​

• Example: Routing Header, Fragment Header,
• Authentication or Security Headers

THE IPv6 PROTOCOL

IPv6 Packet Format

​

Concept of Flow and Priority:

​

• IPv6's flow label allows it to function as a connection-oriented protocol.
• A flow(consider as a tag) is a series of packets sharing characteristics (path, resources, security).
• All packets with the flow/ same tag belong to the same flow (like a video call or online game).
• Routers can quickly recognize the flow and handle these packets faster, without checking every detail.
• This helps the network send real-time data (voice, video) smoothly.

​

​

THE IPv6 PROTOCOL

IPv6 Packet Format

​

Fragmentation and Reassembly in IPv6

In IPv6, fragmentation and reassembly of datagrams are handled differently compared to IPv4.

1. Source Fragmentation Only:

IPv6 Restriction: Only the source host is allowed to fragment packets. Routers are not permitted to perform fragmentation, which streamlines their processing and enhances routing efficiency.

2. Reassembly at Destination:

Reassembly Process: The reassembly of fragmented packets occurs at the destination host. This approach minimizes the processing load on routers, allowing them to forward packets more quickly.

THE IPv6 PROTOCOL

IPv6 Packet Format

​

Fragmentation and Reassembly in IPv6

​

3. Source Control:

• Packet Size Check: The source host can evaluate the size of the packet and decide whether to fragment it before sending. This proactive approach helps ensure that packets fit within the Maximum Transmission Unit (MTU) of the network.

​

4. Router Handling:

• MTU Checking: When a router receives a packet, it checks the packet size against the MTU of the next network segment. If the packet exceeds the MTU, the router drops it.
• Error Notification: The router sends an ICMPv6 "packet too big" message back to the source, informing it of the dropped packet and the maximum allowable size for future packets.

THE IPv6 PROTOCOL

Extension Header

An IPv6 packet consists of a base header (40 bytes) followed by optional extension headers. Up to six types of extension headers can be added to enhance functionality.

​

Types of Extension Headers

1. Hop-by-Hop Options:

​

• It allows the sender to include information that each intermediate router must process.
• Special header that carries optional data that every router along the path must check

Example: A “Router Alert” option tells the router: “Hey, pay attention to this packet for special processing”.

THE IPv6 PROTOCOL

Extension Header

2. Destination Option

• Purpose: Carries information that only the destination needs, not accessible by intermediate routers.

​

3. Source Routing

• Purpose: Combines strict and loose source routing options, allowing the source to specify the route for the packet. The packet carries a list of addresses (waypoints) that it must traverse.

​

4. Fragmentation

• Similar to IPv4, but fragmentation can only be done by the source host.

​

THE IPv6 PROTOCOL

Extension Header

5. Authentication

• Purpose: Validates the sender's identity and ensures data integrity, protecting against unauthorized alterations during transit.

6. Encrypted Security Payload (ESP)

• Purpose: Provides confidentiality and guards against eavesdropping.

THE IPv6 PROTOCOL

Comparison of Options between IPv4 and IPv6

• Padding / Empty Space

IPv4: Uses No-Operation (NOP) for 1 byte, End-of-Option (EOO) to mark the end.

IPv6: Uses Pad1 (1 byte) and PadN (multiple bytes) → simpler and more efficient.

​

• Record Route

IPv4: Can record the path the packet takes.

IPv6: Not implemented → rarely used in IPv4.

​

• Timestamp

IPv4: Can record timestamps at each router.

IPv6: Not implemented → rarely used in IPv4.

THE IPv6 PROTOCOL

Comparison of Options between IPv4 and IPv6

• Source Routing

IPv4: Loose or strict source routing in the options field.

IPv6: Source Routing Extension Header → separate extension header for specifying the route.

​

• Fragmentation

IPv4: Fragmentation fields are in the main header; routers can fragment.

IPv6: Fragmentation moved to a separate extension header; only the source can fragment.

​

• Security / Authentication

IPv4: No built-in security headers.

IPv6: Adds Authentication Header (AH) and Encrypted Security Payload (ESP) extension headers.

Chapter 20 �Unicast Routing

Unicast Routing

• Unicast routing involves directing data packets from a single source to a specific destination in a network. - point-to-point communication

​

• Need for Hierarchical Routing: The Internet consists of numerous routers and hosts, making hierarchical routing necessary for efficiency.

​

• Forwarding Tables: Routers use forwarding tables to determine the best path for packets, while source and destination hosts do not need these tables.

​

• Routing Process: Packets travel hop by hop from the source router to the destination router, selecting the optimal path along the way.

Unicast Routing

Graph Model: The Internet can be modeled as a graph where:

• Nodes represent routers.
• Edges represent network connections between routers.
• Each edge has a cost, indicating the expense of using that route.

• A tree is a set of connected nodes without any loops (cycles).
• The cost usually represents distance, associated with a link.
• A least cost tree is the tree with the smallest total link cost that still connects all the nodes.

Unicast Routing

Least-Cost Trees in Unicast Routing

​

• Definition: A least-cost tree is a structure that connects a source router to all other routers in a network, ensuring that the path from the source to any other node is the shortest possible.

​

• Path Requirements: For N routers, there are (N - 1) least-cost paths from each router to every other router, resulting in N × (N - 1) paths overall. For example, with 10 routers, this results in 90 least-cost paths.
• Structure: Each router has one least-cost tree, making a total of N least-cost trees for the entire network.

Unicast Routing

Least-Cost Trees in Unicast Routing: Properties of Least-Cost Trees:

​

Bidirectional Equivalence: The least-cost path from one router to another has the same cost in both directions, even though the sequence of routers is reversed.

• For example, if the best route from A to F is A → B → E → F with a total cost of 8, then the best route from F to A is F → E → B → A, also with a cost of 8.

​

Route Combination: To find the best route from one router to another, you can split the journey between two points.

• For example, to go from A to G, you could take A → B → E → F → G entirely in A’s route. Or, you could go A → B → E in A’s route, then switch to E → F → G in E’s route. Both routes give the same total cost.

Unicast Routing

Least-Cost Trees in Unicast Routing:

​

can be constructed using both Bellman-Ford and Dijkstra's Algorithm

• Each router (A, B, C, D, E, F, G) acts as a root of its own least-cost tree.
• The numbers (0, 2, 6, 9, etc.) show the total cost from that root to every other router.
• The arrows show which next-hop (path) is chosen for the shortest route.

ROUTING ALGORITHMS

Distance-Vector Routing

• Distance vector routing is distributed, i.e., algorithm is run on all nodes.
• Each node knows the distance (cost) to each of its directly connected neighbors.
• Nodes construct a vector (Destination, Cost, NextHop) and distributes to its neighbors.
• Nodes compute routing table of minimum distance to every other node via NextHop using information obtained from its neighbors.

ROUTING ALGORITHMS

Distance-Vector Routing

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

​

Knowledge about the whole network: Each router shares its knowledge through the entire network. The Router sends its collected knowledge about the network to its neighbors.

​

Routing only to neighbors: The router sends its knowledge about the network to only those routers which have direct links. The router sends whatever it has about the network through the ports. The information is received by the router and uses the information to update its own routing table.

​

Information sharing at regular intervals: Within 30 seconds, the router sends the information to the neighboring routers.

ROUTING ALGORITHMS

Distance-Vector Routing

• Bellman-Ford Equation The heart of distance-vector routing is the Bellman-Ford equation. This equation is used to find the least cost (shortest distance) between a source node, x, and a destination node, y, through some intermediary nodes (a, b, c, . . .).

ROUTING ALGORITHMS

• 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)} for all neighbors of x If you go from x to a neighbor v, the total cost to reach y is cost from x to v.

​

The term min₍v₎ means we consider all the neighbors of x. After going from x to a neighbor v, the total path cost to y is c(x, v) + Dᵥ(y). The least cost from x to y is the smallest of these values among all neighbors.

Distance-Vector Routing

ROUTING ALGORITHMS

Distance-Vector Routing

ROUTING ALGORITHMS

Distance-Vector Routing

• Initialize distances
• Set the distance to the source node = 0.
• Set the distance to all other nodes = ∞ (infinity).
• Relax all edges repeatedly
• For a graph with V vertices, repeat this step V - 1 times:
• For each edge (u → v) with weight w:

if distance[u] + w < distance[v]: distance[v] = distance[u] + w

• u gives a shorter path to v, update v’s distance.”
• Check for negative weight cycles
• Go through all edges one more time:
• If you can still relax any edge, then a negative weight cycle exists.�(Shortest path is undefined because you can keep going around the cycle and reduce the path forever.)

ROUTING ALGORITHMS

Bellman-Ford Equation

​

Bellman ford algorithm is a single-source shortest path algorithm.

This algorithm is used to find the shortest distance from the single vertex to all the other vertices of a weighted graph.

​

​

Initial State

Bellman-Ford Equation

• This equation helps find the least-cost path (or shortest distance) from a starting node 𝑥 to a destination node 𝑦 by looking at possible routes that pass through other nodes (like 𝑎, 𝑏, 𝑐, etc.) along the way.

Each route option has two parts:

• The cost from 𝑥 to an intermediary node (like 𝑎, 𝑏, or 𝑐).
• The least cost from that intermediary node to 𝑦.

Bellman-Ford Equation

• To find the best path, you calculate the total cost for each possible route that goes through a different intermediary node.
• For example:

​

​

• And so, on
• After calculating all these total costs, pick the smallest one. This smallest total cost is the least-cost path from x to y through the intermediary nodes.

Bellman-Ford Equation

• In distance-vector routing, normally we want to update an existing least cost with a least cost through an intermediary node, such as z, if the latter is shorter.

​

​

​

Bellman-Ford Equation

Step 1: Let the given source vertex be 0. Initialize all distances as infinite, except the distance to the source itself. Total number of vertices in the graph is 5, so all edges must be processed 4 times.� 

Bellman-Ford Equation

Step 2: Let all edges are processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). We get the following distances when all edges are processed the first time. The first row shows initial distances. The second row shows distances when edges (B, E), (D, B), (B, D) and (A, B) are processed. The third row shows distances when (A, C) is processed. The fourth row shows when (D, C), (B, C) and (E, D) are processed.  

Bellman-Ford Equation

Step 3: The first iteration guarantees to give all shortest paths which are at most 1 edge long. We get the following distances when all edges are processed second time (The last row shows final values). 

Bellman-Ford Equation

Step 4: The second iteration guarantees to give all shortest paths which are at most 2 edges long. The algorithm processes all edges 2 more times. The distances are minimized after the second iteration, so third and fourth iterations don’t update the distances.� 

Bellman-Ford

Bellman-Ford Equation

Bellman-Ford Equation

Bellman-Ford Equation

Bellman-Ford Equation

Bellman-Ford Equation

Bellman-Ford Equation

Bellman-Ford Equation

Bellman-Ford Equation

Distance-vector routing

• In distance-vector routing, when a link to a destination breaks, routers don’t notice it right away. As a result, they may keep sharing wrong information, thinking the destination is still reachable. This delay in updating causes the “count to infinity” problem, where routers slowly increase the distance value until it reaches infinity, meaning the destination is unreachable.

​

Two-Node Loop Example:�When router A’s link to destination X fails, A marks X as unreachable.�But router B doesn’t know yet and still thinks it can reach X.�So B tells A it can reach X, and A updates its table to use B as the path.�Then A tells B the same thing — this keeps repeating.�As a result, packets loop between A and B until both realize that X is truly unreachable.

Distance-vector routing

Distance-vector routing

Solutions

• Split Horizon:�A router does not send a route update back to the router from which it learned that route.�→ Helps prevent routing loops.
• Poison Reverse:�A router tells the sender that the route is unreachable (set to infinity) instead of just staying silent.�→ This quickly stops loops and speeds up route updates.

​

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.
• Features of link state routing protocols –
• Link state packet – A small packet that contains routing information.
• Link state database – To create a least-cost tree with this method, each node needs to have a complete map of the network, which means it needs to know the state of each link. The collection of states for all links is called the link-state database (LSDB).
• Shortest path first algorithm (Dijkstra algorithm) – A calculation performed on the database results in the shortest path
• Routing table – A list of known paths and interfaces.

​

Link-State Routing

In Bellman-Ford:

• A sets cost to X as ∞ (infinity).
• But its neighbor B might still think it can reach X through A (because it hasn’t yet learned A’s link is broken).B then tells A: “I can reach X through you!”
• A believes B and updates its table with B’s info.
• This causes a loop where they keep updating each other with wrong path costs. slowly increasing, known as the Count-to-Infinity Problem: That’s why Bellman-Ford “fails” (or reacts slowly) when a link fails.

​

In Dijkstra:

• Every router already knows the full topology (who is connected to whom).
• When a link breaks, a Link State Advertisement (LSA) is immediately flooded to all routers.
• Every router recalculates the shortest paths using Dijkstra’s algorithm.
• So Dijkstra updates are instant and consistent, avoiding the count-to-infinity problem.

Link-state database (LSDB).

• There is only one LSDB for the whole internet; each node needs to have a duplicate of it to be able to create the least-cost tree.
• Figure 20.8 shows an example of an LSDB for the graph in Figure 20.1. The LSDB can be represented as a two-dimensional array(matrix) in which the value of each cell defines the cost of the corresponding link.

Link-state database (LSDB).

Steps in Dijkstra’s Link-State Routing

• Neighbor Discovery – Each router finds its directly connected neighbors using “Hello” messages.
• LSP Creation – Each router prepares a Link-State Packet (LSP) listing its neighbors and link costs.
• Flooding – Each router broadcasts (floods) its LSP to all other routers in the network.
• Topology Database Formation – Every router collects all LSPs and builds a complete map of the network.
• Shortest Path Calculation – Each router runs Dijkstra’s algorithm on the map to find the best routes.

​

Link-state database (LSDB).

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 Packet

• Each node can send some greeting messages to all its immediate neighbors (those nodes to which it is connected directly) to collect two pieces of information for each neighboring node:
• The identity of the node and
• The cost of the link.
• The combination of these two pieces of information is called the LS packet (LSP); the LSP is sent out of each interface, as shown in Figure 20.9

Link State Packet

Link State Routing has two phases:

​

• Reliable Flooding

​

• Initial state: Each node knows the cost of its neighbors.

​

• Final state: Each node knows the entire graph.

​

Link State Packet

• 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.

​

Link State Packet

Notations Used:

• 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.

Link State Packet

Algorithm

• Keep a distance dist[v] to every node (∞ initially, dist[source]=0).
• Repeatedly pick the node u with the smallest dist[u] that is not yet finalized.
• For each neighbor v of u, try to relax the edge: if dist[u] + w(u,v) < dist[v] then update dist[v].
• Mark u finalized (its shortest distance is found). Repeat until all nodes finalized or queue empty.

Formation of Least-Cost Trees (Dijikstra’s Algorithm)

To create a least-cost tree for itself, using the shared LSDB, each node needs to run the famous Dijkstra Algorithm. This iterative algorithm uses the following steps:

​

1. The node chooses itself as the root of the tree, creating a tree with a single node, and sets the total cost of each node based on the information in the LSDB.

2. The node selects one node, among all nodes not in the tree, which is closest to the root, and adds this to the tree. After this node is added to the tree, the cost of all other nodes not in the tree needs to be updated because the paths may have been changed.

3. The node repeats step 2 until all nodes are added to the tree.

Dijkstra's algorithm

Dijkstra's algorithm - is a solution to the single-source shortest path problem in graph theory. 

Works on both directed and undirected graphs. However, all edges must have nonnegative weights.

​

Approach: Greedy

​

Input: Weighted graph G={E,V} and source vertex v∈V, such that all edge weights are nonnegative

Output: Lengths of shortest paths (or the shortest paths themselves) from a given source vertex v∈V to all other vertices

​

​

Dijkstra's algorithm - Pseudocode

dist[s] ←0 (distance to source vertex is zero)�for  all v ∈ V–{s}�        do  dist[v] ←∞ (set all other distances to infinity) �S←∅ (S, the set of visited vertices is initially empty) �Q←V  (Q, the queue initially contains all vertices)               �while Q ≠∅ (while the queue is not empty) �do   u ← mindistance(Q,dist) (select the element of Q with the min. distance) �      S←S∪{u} (add u to list of visited vertices) �       for all v ∈ neighbors[u] �              do  if   dist[v] > dist[u] + w(u, v) (if new shortest path found)�                         then      d[v] ←d[u] + w(u, v) (set new value of shortest path)

(if desired, add traceback code)

return dist

​

Dijkstra’s Example

Dijkstra’s Example

Dijkstra’s Example

Dijkstra’s Example

Dijkstra Animated Example

Dijkstra’s Example

Dijkstra’s Example

Dijkstra’s Example

Dijkstra’s Example

Bellman Ford vs Dijkstra’s

Path-Vector Routing

• Path-Vector Routing directs network traffic and addresses limitations in link-state and distance-vector routing.
• Example: BGP and AS
• These methods focus on finding the cheapest route, but this may not always be the priority.
• Path-Vector Routing allows the sender to control the route, avoiding specific routers or areas for security or other reasons, rather than focusing only on cost.

Path-Vector Routing

Path-Vector Routing

• Path-vector routing is a method where each node gradually learns the best paths to all destinations by talking to its neighbors.

​

• When a node starts, it creates a list of routes (a path vector) using information from its neighbors.

​

• It then shares this list with its neighbors, who update their own path lists.

​

• This process continues until all nodes know the best paths.

​

Path-Vector Routing

• This update process is similar to the Bellman-Ford algorithm, but each node can choose the best path according to its own rules, not just the shortest.
• A major feature of path-vector routing is loop prevention: if a path would bring the data back to the starting node, it is ignored to avoid routing loops.

• Bellman-Ford: new_distance = distance_to_neighbor + edge_cost → choose smaller.
• Path-vector: new_path_vector = neighbor’s path + edge_to_neighbor → choose according to node policy

Path-Vector Routing

Spanning trees

• In path-vector routing, each source node uses spanning trees to figure out the best paths to destinations.
• The “best” tree isn’t always the one with the lowest cost.
• Each source can apply its own policies to decide which paths to choose.

all possible intermediate nodes

Path-Vector Routing

• spanning trees

Path-Vector Routing

• Bellman-Ford / distance-vector: Always picks the shortest-cost path (minimum distance).
• Path-vector routing: Each node can apply its own policy (not necessarily shortest distance)

Path-Vector Routing

Path-Vector Routing

• This diagram shows the path vectors created at each node when they boot in a network with five nodes labeled A, B, C, D, and E. Each node learns paths to the other nodes by communicating with its immediate neighbors.
• Node A: Only knows about itself and its direct neighbor, B. Its path vector shows paths to A and B.
• Node B: Has information about itself and its connections to A, C, and D. Its path vector lists paths to A (through B), itself (directly), C (through B), and D (through B).

​

Path-Vector Routing

3. Node C: Knows paths to its neighbors B, D, and E, so it lists routes to B (through C), itself (directly), D (through C), and E (through C).

4. Node D: Knows paths to its neighbors B, C, and E. Its path vector lists routes to B, C, D, and E, showing how it can reach these nodes.

5. Node E: Lists paths to its neighbors C and D and itself. Its path vector shows routes to C, D, and E.

• Each node gathers and updates these paths by receiving information from its neighbors and uses these path vectors to find the best route to each destination. The arrows represent the communication between nodes for sharing path vector information.

Path-Vector Routing

1. In the first event, node C receives B’s vector, which updates its own vector. Now, C knows how to reach node A.
2. In the second event, node C receives D’s vector, but it doesn't change C’s vector.
1. After the first event, node C’s vector is stable and becomes its forwarding table.

1. For each possible destination:
• If it’s myself, record the path as just myself.
• If it’s my direct neighbor, record the path as myself plus the neighbor.
• Otherwise, the path is empty.
2. Tell all neighbors about the current paths.

�

1. Wait for a neighbor to send new path information.

2. For each destination:

• Ignore any path where myself appear in the path (prevents loops).
• Otherwise, pick the best path (either current path or a new path via that neighbor).

3. If anything changes, tell all neighbors the new paths.

�UNICAST ROUTING PROTOCOLS �

• Unicast routing protocols are used to route data from one specific source to one specific destination on the Internet. These protocols not only calculate routes but also define operational domains, message types, communication methods between routers, and how they interact with other protocols.
• Internet Structure:�The Internet now consists of multiple backbones managed by private companies, instead of a single backbone.
• Backbones: Provide global connectivity and connect at peering points for inter-backbone communication.
• Provider Networks: Rely on backbones for global access and serve Internet customers

�UNICAST ROUTING PROTOCOLS �

• Customer networks connect to provider networks for Internet services.
• Backbones, provider networks, and customer networks together form Internet Service Providers (ISPs), each offering services at different levels.

�UNICAST ROUTING PROTOCOLS �

Hierarchical routing

• Hierarchical routing,  used to manage large and complex networks efficiently by dividing them into smaller segments or regions, helping reduce the size of routing tables and make routing scalable.
• In traditional Link State (LS) and Distance Vector (DV) algorithms, every router stores information about every other router.​
• As networks grow, routing tables get too big, causing routers to need more memory and processing power, making them less efficient.​
• Hierarchical routing solves this by grouping routers into regions. Each router only needs detailed information about routes within its own region and broad information about other regions.

​

Hierarchical Routing

• Routing tables can be made smaller by using a hierarchical addressing system.
• Hosts that are close to each other should have addresses with common prefixes.
• Routers then need to look at only the prefix to decide where to send a packet.
• For very large networks, a two-level hierarchy may not be enough. In that case, addresses can be grouped into clusters, clusters into zones, zones into groups.

�UNICAST ROUTING PROTOCOLS �

Hosts that are physically or logically close in the network should have the same prefix.

Host A: 192.168.1.5

Host B: 192.168.1.8

Host C: 192.168.2.3

Hierarchical Routing

�UNICAST ROUTING PROTOCOLS �

Hierarchical Routing

Components of Hierarchical Routing:

• AS(Autonomous System)
• RIP (Routing Information Protocol)
• BGP (Border Gateway Protocol)
• MOSPF(Multicast Link State )

�UNICAST ROUTING PROTOCOLS �

Hierarchical Routing

Autonomous Systems (AS)

�UNICAST ROUTING PROTOCOLS �

• Definition: An AS is a network or group of networks managed by a single Internet Service Provider (ISP), which controls routing inside it.

​

• Identification: Each AS has a unique Autonomous System Number (ASN) — a 16-bit number assigned by ICANN.

​

• Categorization: ASs are classified based on how they connect to other ASs, not by their size

Hierarchical Routing

Autonomous Systems (ASs)

�UNICAST ROUTING PROTOCOLS �

Stub AS:

• It can send and receive its own data (for example, from its users to the internet and back).
• But it will not act as a middleman to carry or route data between two other Autonomous Systems.
• Example: Customer networks that are only the source or destination of data.

​

Multihomed AS:

• Connects to multiple ASs.
• Can send and receive data, but still does not allow transit traffic.
• Example: Customer networks using multiple ISPs, but not providing paths for other traffic.

Hierarchical Routing

Autonomous Systems (ASs)

• Transient AS: Connects to multiple ASs. Allows transit traffic, meaning it can route data between other ASs.
• Allows transit traffic, meaning it forwards data that does not originate or end in its own network.
• It routes data between other Autonomous Systems.

�UNICAST ROUTING PROTOCOLS �

Multiple networks can exist inside a single AS, but they are all managed together under one ASN.

AS 65001

├─ Network 1 → Hosts A, B, C

├─ Network 2 → Hosts D, E

└─ Network 3 → Hosts F, G, H

Routing Information Protocol

• RIP stands for Routing Information Protocol. RIP is an intra-domain routing protocol used within an autonomous system.

​

• Here, intra-domain means routing the packets in a defined domain, for example, web browsing within an institutional area.

​

• To understand the RIP protocol, our main focus is to know the structure of the packet, how many fields it contains, and how these fields determine the routing table.

• Before understanding the structure of the packet, we first look at the following points:
• RIP is based on the distance vector-based strategy, so we consider the entire structure as a graph where nodes are the routers, and the links are the networks.
• In a routing table, the first column is the destination, or we can say that it is a network address.
• The cost metric is the number of hops to reach the destination. The number of hops available in a network would be the cost. The hop count is the number of networks required to reach the destination.

Routing Information Protocol

• Before understanding the structure of the packet, we first look at the following points:

​

• In RIP, infinity is defined as 16, which means that the RIP is useful for smaller networks or small autonomous systems. The maximum number of hops that RIP can contain is 15 hops, i.e., it should not have more than 15 hops as 16 is infinity.

​

• The next column contains the address of the router to which the packet is to be sent to reach the destination.

Routing Information Protocol

• How is hop count determined?
• When the router sends the packet to the network segment, then it is counted as a single hop.

Routing Information Protocol

How is hop count determined?

• In the above figure, when the router 1 forwards the packet to the router 2 then it will count as 1 hop count.

​

• Similarly, when the router 2 forwards the packet to the router 3 then it will count as 2 hop count, and when the router 3 forwards the packet to router 4, it will count as 3 hop count.

​

• In the same way, RIP can support maximum up to 15 hops, which means that the 16 routers can be configured in a RIP..

Routing Information Protocol

• RIP Message Format
• Now, we look at the structure of the RIP message format. The message format is used to share information among different routers. The RIP contains the following fields in a message:

​

Routing Information Protocol

• Command: It is an 8-bit field that is used for request or reply. The value of the request is 1, and the value of the reply is 2.
• Version: Here, version means that which version of the protocol we are using.
• Reserved: This is a reserved field, so it is filled with zeroes.
• Family: It is a 16-bit field. As we are using the TCP/IP family.
• Network Address: It is defined as 14 bytes field. If we use the IPv4 version, then we use 4 bytes, and the other 10 bytes are all zeroes.
• Distance: The distance field specifies the hop count, i.e., the number of hops used to reach the destination.

​

​

Routing Information Protocol

• How does the RIP work?

If there are 8 routers in a network where Router 1 wants to send the data to Router 3.

If the network is configured with RIP, it will choose the route which has the least number of hops. There are three routes in the above network, i.e., Route 1, Route 2, and Route 3.

The Route 2 contains the least number of hops, i.e., 2 where Route 1 contains 3 hops, and Route 3 contains 4 hops, so RIP will choose Route 2.

Routing Information Protocol

RIP Algorithm

• RIP uses the same algorithm as distance-vector (Bellman-Ford) routing, with a few modifications for updating a router’s forwarding table:
• Instead of sending only distance vectors, a router sends the entire forwarding table in a response message.
• The receiving router adds one hop to each cost and sets the next-hop field to the address of the sending router.
• Each route received from a neighbor is called a received route, and each route already in the router’s table is called an old route.

​

Routing Information Protocol

In RIP, when a router receives a route update from a neighbor, it follows these rules to update its forwarding table:

New Route: If the received route doesn't exist in the old table, it is added.

​

Better Cost: If the received route has a lower cost (fewer hops), it is preferred.

​

Same Next-Hop: If the received route has a higher cost but the next-hop router is the same, the received route is chosen.

​

Routing Information Protocol

Number of hops from source router A to various subnets

Routing Information Protocol

• The maximum cost of a path is limited to 15, thus limiting the use of RIP to autonomous systems that are fewer than 15 hops in diameter.

​

• In RIP, routing updates are exchanged between neighbors approximately every 30 seconds using a RIP response message.

​

• Response messages are also known as RIP advertisements.

Routing Information Protocol

How RIP updates its Routing table

​

• Using this Response message, the routers exchange routing updates with their neighbors every 30 secs. If a router doesn’t hear from its neighbor every 180 secs, then that neighbor is not reachable.

​

• When this happens, RIP

→ modifies the local routing-table and

→ propagates then this information by sending advertisements to its neighbors.

Routing Information Protocol

How RIP updates its Routing table

• The response-message contains

→ list of up to 25 destination subnets within the AS and

→ sender’s distance to each of those subnets. Response-messages are also known as advertisements.

​

• Using this message, router requests info about its neighbor’s cost to a given destination.

​

• Both types of messages are sent over UDP using port# 520.

​

• The UDP segment is carried between routers in an IP datagram.

Routing Information Protocol

How RIP updates its Routing table

How RIP updates its Routing table

• The following timers are used to update the routing table:

​

• RIP Flush timer : 240 sec
• The RIP flush timer is 240 second which is almost equal to 4 min means that if the router does not receive the update within 240 seconds then the neighbor route will remove that particular route from the routing table which is a very slow process as 4 minutes is a long time to wait.

Routing Information Protocol

​

Performance of RIP (Routing Information Protocol)

• Update Messages:
• RIP sends simple update messages only to neighboring routers, reducing traffic load.
• These updates are local, and routers coordinate to avoid sending updates simultaneously.
• Convergence of Forwarding Tables:
• RIP uses the distance-vector algorithm, which may converge slowly in large networks.
• RIP limits the hop count to 15 (16 is considered unreachable), which helps maintain quick convergence within its limited domain.

Routing Information Protocol

​

Performance of RIP (Routing Information Protocol)

• Robustness:
• RIP relies on each router sharing its view of the network with its neighbors.
• Since each router's forwarding table is based on data from its neighbors, any failure or corruption in one router can spread across the network, affecting routing stability.

Routing Information Protocol

OSPF - Open Shortest Path First

• OSPF(Open Shortest Path First) is a link-state protocol that uses flooding of link-state information and a Dijkstra least-cost path algorithm.
• With OSPF, a router constructs a complete topological map of the entire autonomous system.
• The router then locally runs Dijkstra’s shortest-path algorithm to determine a shortest-path tree to all subnets, with itself as the root node.
• With OSPF, a router broadcasts routing information to all other routers in the autonomous system, not just to its neighboring routers.
• A router broadcasts link-state information whenever there is a change in a link’s state.

​

OSPF - Open Shortest Path First

• In OSPF, each area has one or more area border routers (ABRs) that handle routing to other areas(Area = a smaller part of the AS).

​

• There is one backbone area in the AS, which connects all areas. The backbone always includes all ABRs and may also have regular routers.

​

To send a packet from one area to another:

• The packet first goes to an ABR in the source area.
• It travels through the backbone to an ABR in the destination area.
• Finally, it is delivered to the destination router within that area.

​

OSPF Protocol

OSPF Protocol

Imagine a company network (AS):

• The company has 3 offices: Office A, Office B, and Office C.
• The whole company network is one AS.

​

Divide the network into areas:

• Area 0 (Backbone Area): Connects all offices.
• Area 1: Office A
• Area 2: Office B
• Area 3: Office C

​

Routers:

• Each office has routers.
• Some routers are Area Border Routers (ABRs) that connect their office (area) to the backbone.

​

How a packet travels:

• A computer in Office A wants to send data to Office C.
• The packet goes to the ABR in Area 1 (Office A).
• It travels through Area 0 (backbone).
• It reaches the ABR in Area 3 (Office C).
• Finally, it is delivered to the destination computer in Office C.

OSPF Protocol- OSPF Working Steps:�

1. Neighbor Formation: Routers on the same link establish a neighbor relationship.
2. Database Exchange: Neighbors exchange Link-State Database (LSDB) information.
3. Best Route Selection: Using the exchanged LSDB, each router calculates and adds the best route to its routing table based on SPF (Shortest Path First) algorithm.

​

A neighbor relationship in OSPF, it first establishes a Router ID (RID):

Router ID (RID): A unique identifier in the format of an IPv4 address, which distinguishes each router on the network.

Setting the RID: The router ID can be set manually by the network administrator or automatically by the router. If set automatically, the router typically selects the highest IP address on its active interfaces.

The following is the logic that the router chooses to set the router ID:

• Manually assigned: The router checks whether the router ID is manually set or not. If it manually set, then it is a router ID.

​

• If the Router ID (RID) is not set manually, OSPF chooses it automatically as follows:
• First preference: The highest IP address on an active loopback interface
• Loopback interface: A virtual interface that is always up as long as the router has at least one active interface. Its IP is stable and always reachable, which makes it ideal for OSPF RID.
• If no loopback exists: The router picks the highest IP address on an active (up) physical interface.

OSPF Protocol

OSPF Protocol - Types of links in OSPF

1. Point-to-Point Link: Connects only two routers directly, no other devices in between.
2. Transient Link: Connects multiple routers in the network.

3. Stub Link: A network with only one router connection, all traffic goes through that router.

4. Virtual Link: A backup link set by the admin when the direct connection fails; may take a longer path.

OSPF Protocol – transition states

• Down: No HELLO packet received; OSPF process hasn't started yet (not physically down).
• Init: Device has received a HELLO packet from the other router.
• 2WAY: Both routers have received HELLO packets from each other, establishing the connection.
• Exstart: Routers start the exchange, selecting master and slave based on router ID.
• Exchange: Routers send lists of database descriptions to each other.
• Loading: Routers exchange LSR (Link State Request), LSU (Link-State Update), and LSA (Link State Advertisement).
• Full: Routers complete the LSA exchange, reaching full state.

OSPF Protocol

Advanced Features of OSPF:

Security:

OSPF exchanges can be authenticated to ensure only trusted routers participate.

Two types of authentication:

• Simple Authentication: Uses the same password on each router (low security).
• MD5 Authentication: Uses MD5 hash with shared secret keys.
1. Sending Router: Computes MD5 hash, includes it in the packet, and sends it.
2. Receiving Router: Computes and compares the hash for verification.

3. Multiple Same-Cost Paths: OSPF supports load balancing by allowing multiple paths to a destination if they have the same cost.

OSPF Protocol

Advanced Features of OSPF:

Integrated Unicast and Multicast Routing:

​

• Multicast OSPF (MOSPF): Extends OSPF for multicast routing, reusing the link database and adding a multicast link-state advertisement.

​

Hierarchical Structure:

• OSPF allows areas within an Autonomous System (AS).
• Area Border Router: Manages traffic between areas.
• Backbone Area: Central area routing traffic between all other areas.

BGP(Border Gateway Protocol )

• It is an interdomain routing protocol, and it uses the path-vector routing. It is a gateway protocol that is used to exchange routing information among the autonomous system on the internet.

​

BGP(Border Gateway Protocol )

Using BGP

• Obtain Subnet Reachability Information: Gather reachability details from neighboring Autonomous Systems (ASs).
• Propagate Reachability Information: Distribute reachability data to all routers within the AS.
• Determine Optimal Routes to Subnets:
• Use reachability information to identify paths.
• Apply AS policy to select the best routes.

​

BGP(Border Gateway Protocol )

• Routers share routing information using TCP connections on port 179.

​

• Each TCP connection connects two routers from different Autonomous Systems (ASs).

​

• A BGP connection usually exists between two routers on different ASs — these routers are called BGP peers.

​

• TCP = the communication channel (like a phone line). BGP = the conversation happening over that channel

​

• The BGP session includes the TCP connection and all the BGP messages exchanged through it.

BGP(Border Gateway Protocol )

• Two types of session:

1) External BGP (eBGP) session

Is a BGP session established between two routers in different autonomous systems (AS). This session is used to exchange routing information across AS boundaries, allowing routers to communicate routes between distinct networks

2) Internal BGP (iBGP) session

An Internal BGP (iBGP) session is a BGP session established between routers within the same autonomous system (AS). Unlike eBGP, which connects different ASs, iBGP is used to exchange routing information between routers in the same AS.

BGP(Border Gateway Protocol ) - Operation of External BGP (eBGP):�

1. Point-to-Point Protocol: BGP establishes a TCP connection on port 179 between two routers.
2. BGP Peers: Routers running BGP, called peers or speakers, exchange routing information.
3. Update Messages: Key messages that announce network reachability within each AS.
4. eBGP: Allows border routers from different ASs to exchange routing information.
5. Connections: Requires a physical connection between border routers and a logical TCP session.

BGP(Border Gateway Protocol )

BGP(Border Gateway Protocol )

Update Messages in eBGP:

• Routers send update messages to inform peers about reachable networks. For example, R1 informs R5 that networks N1, N2, N3, and N4 are reachable through R1.
• R5 updates its forwarding table to route packets for these networks via R1.

Routing Table Updates:

• Routers update their forwarding tables based on received update messages. R5, for instance, will route packets to R1 for networks N1-N4.

BGP(Border Gateway Protocol )

Limitations in eBGP:

• Limited Reachability: Border routers (like R5) can only reach or route traffic to the networks of the Autonomous Systems (ASs) that they are directly connected to — not beyond them.
• Non-Border Routers: Routers within an AS that are not border routers so, lacks information about networks outside their AS.

Solution - iBGP:

• iBGP ensures complete reachability by allowing all routers within an AS, including non-border routers, to exchange routing information, enabling routing to networks in other ASs.

​

​

• eBGP connects AS-to-AS.
• iBGP shares that external routing info across all routers inside an AS.
• So yes, iBGP improves reachability inside the AS and solves the limitation of eBGP

BGP(Border Gateway Protocol )

eBGP and iBGP sessions

BGP(Border Gateway Protocol )

• BGP allows each AS to:
• Get information about which subnets are reachable from neighboring ASs.
• Share this reachability information with all routers within the AS.
• Select the best routes to subnets based on reachability info and AS policies.

Path Attributes and BGP Routes

BGP selects the best route based on path attributes. Path attributes are used to store and display information about the path in the routing table, which follows the path-vector routing approach. These attributes help BGP determine the best route.

Multicast Link State (MOSPF)

• Multicast Open Shortest Path First (MOSPF) is an extension of the Open Shortest Path First (OSPF) protocol, used for multi cast routing.

​

• Adds Multicast to OSPF: MOSPF is an extension of OSPF, designed to route multicast data.
• Within an AS, multicast routing allows data (like live video or real-time updates) to be sent efficiently to multiple routers or hosts that have joined a multicast group.

​

• Finds Group Members: It uses IGMP(Internet Group Management Protocol) to identify devices interested in specific multicast groups.

​

• Shares Membership Info: Routers share multicast group info with each other across the network.

​

Multicast Link State (MOSPF)

• Builds Shortest Paths: For each multicast group, MOSPF calculates the shortest path to deliver data efficiently.
• Dynamic Routing: Routes are created only when there’s active multicast traffic, reducing network load.
• Good for Small Networks: MOSPF works well in smaller networks but can struggle in very large ones.
• Loop-Free Delivery: It ensures data travels on loop-free paths.

​

Multicast Link State (MOSPF)

A university campus network (inside one AS) is streaming a live lecture from the main server to students in different departments who have joined the multicast group 224.1.1.1.

1. Builds Shortest Paths:�MOSPF uses OSPF’s link-state database to calculate the shortest path tree from the lecture server to all students who joined 224.1.1.1. This ensures data reaches all receivers quickly and efficiently.
2. Dynamic Routing: The multicast route is created only when the students join the group. When no one is watching, MOSPF removes the route, saving bandwidth.
3. Good for Small Networks: Since the campus network has limited routers, MOSPF easily handles the multicast traffic. But in a huge ISP network with hundreds of routers, the overhead could become large.
4. Loop-Free Delivery: The shortest path tree ensures packets follow a single, loop-free path from the server to all receivers.

Multicast Link State (MOSPF)

Multicast Link State (MOSPF)

The main intention of the whole process is to deliver packets from the source (S) to all routers that have G1 members.

If a path has no active G1 users, the router stops sending packets there (prunes it). So packets travel only where G1 is active.

(a) Active groups: Some routers have users who joined groups like G1, G2, or G3. The network shows where these group members are located.

(b) S–G1 shortest-path tree Source S starts sending data to G1 members. The shortest paths from S to all G1 receivers are built.

(c) S–G1 subtree (router view): Each router looks at only its part of the tree. It checks which paths go toward G1 members.

(d) S–G1 pruned subtree: Routers remove paths that have no G1 members. Only the branch with real G1 receivers is kept to save bandwidth.