Unit 3

The Media Access Control (MAC) sublayer in a computer

network is a crucial component of the Data Link Layer (Layer
2) in the OSI model. It's responsible for managing access to
the physical transmission medium, enabling multiple devices
to share a network connection. Specifically, the MAC sublayer
handles tasks like addressing frames, controlling access to
the medium, and encapsulating data packets for transmission
over the physical layer.

Key Functions of the MAC Sublayer Addressing:

The MAC sublayer assigns unique addresses (MAC addresses) to
network devices, allowing data to be routed to the correct
destination.
Medium Access Control:
It regulates how devices gain access to the shared transmission
medium, preventing collisions and ensuring efficient data transfer.
Framing:
The MAC sublayer encapsulates data packets received from the
Logical Link Control (LLC) sublayer into frames suitable for
transmission over the physical medium.
Data Link Layer:
The MAC sublayer works in conjunction with the LLC sublayer to
form the complete Data Link Layer.
Physical Layer Interface:
The MAC sublayer acts as an interface between the LLC sublayer
and the physical layer, handling the complexities of physical link
control.

Importance of the MAC Sublayer:

Efficient Resource Sharing
By managing access to the shared medium, the MAC sublayer allows
multiple devices to communicate over the same network without
interference.
Reliable Data Transmission
The MAC sublayer helps ensure reliable data transmission by
handling addressing, framing, and error detection/correction.
Network Interoperability
By standardizing communication protocols at the MAC level, the
MAC sublayer enables different network devices and software to
communicate effectively.
Examples of MAC Protocols:
Ethernet:
A widely used MAC protocol for wired networks, employing Carrier
Sense Multiple Access with Collision Detection (CSMA/CD).
Wi-Fi (IEEE 802.11):
A popular MAC protocol for wireless networks, using Carrier Sense
Multiple Access with Collision Avoidance (CSMA/CA).
In essence, the MAC sublayer is the "traffic controller" of the
Data Link Layer, ensuring that data can be transmitted reliably
and efficiently over a shared communication medium.
Core Functions of the MAC Sublayer
Frame Delimiting & Recognition
Encapsulates data into frames, adding necessary headers
and trailers for synchronization and error detection.
Addressing
Assigns unique MAC addresses to devices, facilitating
accurate data delivery within a network segment.
Error Detection
Employs mechanisms like Cyclic Redundancy Check (CRC)
to detect errors in transmitted frames.
Access Control
Determines how devices access the shared medium,
employing protocols to prevent collisions and ensure fair
usage.
Transparent Data Transfer
Transfers data between the Logical Link Control (LLC)
sublayer and the physical layer, maintaining data integrity and
order

Back-off Algorithm for CSMA/CD

Back-off algorithm is a collision resolution mechanism
which is used in random access MAC protocols (CSMA/CD).
This algorithm is generally used in Ethernet to schedule re-
transmissions after collisions. If a collision takes place
between 2 stations, they may restart transmission as soon
as they can after the collision. This will always lead to
another collision and form an infinite loop of collisions
leading to a deadlock. To prevent such scenario back-off
algorithm is used. Let us consider a scenario of 2 stations A
and B transmitting some data:
Example -Case-1 : Suppose 2 stations A and B start
transmitting data (Packet 1) at the same time then, collision
occurs. So, the collision number n for both their data (Packet
1) = 1. Now, both the station randomly pick an integer from
the set K i.e. {0, 1}.

 When both A and B choose K = 0 –> Waiting time for A

= 0 * T slot = 0 Waiting time for B = 0 * T slot = 0 Therefore,
both stations will transmit at the same time and hence
collision occurs.
 When A chooses K = 0 and B chooses K = 1 –>
Waiting time for A = 0 * T slot = 0 Waiting time for B = 1 *
T slot = T slot Therefore, A transmits the packet and B waits
for time T slot for transmitting and hence A wins.
 When A chooses K = 1 and B chooses K = 0 –>
Waiting time for A = 1 * T slot = T slot Waiting time for B = 0
* T slot = 0 Therefore, B transmits the packet and A waits
for time T slot for transmitting and hence B wins.
 When both A and B choose K = 1 –> Waiting time for A
= 1 * T slot = T slot Waiting time for B = 1 * T slot =
 T slot Therefore, both will wait for the same time T slot and
then transmit. Hence, a collision occurs.

Advantage

 Collision probability decreases exponentially.

 Improves network performance: Back-off algorithm

reduces the number of collisions and retransmissions,
thus improving the overall network performance.

 Increases channel utilization : By reducing the number

of collisions, back-off algorithm increases the channel
utilization, leading to better use of network resources.

 Reduces delays: By reducing the number of collisions,

back-off algorithm reduces the waiting time between
transmission attempts, resulting in lower delays.

 Fairness: The back-off algorithm ensures that all nodes

in the network have an equal chance to access the
channel, which promotes fairness in the distribution of
network resources.

 Adaptability: The back-off algorithm is adaptable to

changing network conditions. When the network is busy, it
increases the waiting time before retransmission
attempts, and when the network is idle, it reduces the
waiting time, thus ensuring efficient use of network
resources.
 Scalability: The back-off algorithm is scalable, as it can
be used in networks of any size, from small local
networks to large wide-area networks.

 Energy Efficiency: By reducing the number of collisions

and retransmissions, the back-off algorithm reduces the
energy consumption of network nodes, which is
particularly important in battery-powered devices such as
mobile phones and IoT devices.

 Robustness: The back-off algorithm is robust, as it can

handle a high number of nodes trying to access the
channel simultaneously without causing the network to
crash or degrade in performance.

Disadvantages –
 Capture effect: Station who wins ones keeps on
winning.

 Works only for 2 stations or hosts.

 Increased overhead : Back-off algorithm adds additional

overhead to the network due to the need to wait for a
random time before retransmitting a packet.

 Complexity : Back-off algorithm is a complex algorithm

that requires a high level of implementation complexity.

 Vulnerability to attacks : Back-off algorithm is

vulnerable to certain attacks, such as denial-of-service
(DoS) attacks, where an attacker can manipulate the
 random time intervals to cause the network to stop
functioning.

 Limited Performance: While the back-off algorithm can

improve network performance in low- to medium-load
scenarios, it may not be effective in high-load scenarios
where the number of nodes trying to access the network
is very high.

 Inefficient in Time-Sensitive Applications: The back-off

algorithm may not be suitable for time-sensitive
applications, such as real-time video streaming or voice
over IP (VoIP), where even a slight delay can cause
significant problems.

 Limited Scalability: While the back-off algorithm can be

used in networks of any size, it may become less effective
in larger networks where the number of nodes trying to
access the channel simultaneously is very high.

 Sensitivity to Distance and Interference: The back-off

algorithm is sensitive to distance and interference, as
nodes that are physically closer to each other may have a
higher probability of colliding and may require longer
random waiting times.
CDMA (Code Division Multiple Access) and CSMA
(Carrier Sense Multiple Access)
CDMA (Code Division Multiple Access) and CSMA (Carrier
Sense Multiple Access) are distinct multiple access
techniques used in wireless communication and
networking. CDMA uses a unique code assigned to each user
to transmit data simultaneously on the same frequency, while
CSMA relies on devices listening for a free channel before
transmitting, thus reducing collisions.

Key Differences:
Channel Sharing:
CDMA allows multiple users to transmit simultaneously by using
different codes on the same channel, while CSMA uses a single
channel with a mechanism to avoid simultaneous transmissions.
Collision Handling:
CDMA inherently handles collisions by allowing multiple signals to
exist on the channel, with the receiver filtering the desired signal
based on the assigned code. CSMA uses carrier sensing to avoid
collisions by listening for an idle channel before transmission,
according to Wikipedia.
Centralization:
CDMA is generally a more centralized approach, as it requires a
controller to assign codes to users. CSMA is more decentralized and
relies on devices listening to the channel and avoiding transmissions
when it is busy.
Data Rate:
CDMA can offer higher data rates, especially in newer standards like
CDMA2000 and W-CDMA, while CSMA's data rate depends on the
network's capabilities.

CDMA:
Simultaneous transmission using different codes on the same
channel, suitable for cellular networks.
CSMA:
Devices listen before transmitting to avoid collisions, commonly used
in wireless LANs (e.g., Wi-Fi).
ALOHA
ALOHA is a fundamental multiple access protocol in computer
networking that allows multiple terminals to share a
communication channel without causing interference or
collisions. It was developed at the University of Hawaii and is
used in various wireless communication systems. ALOHA is a
random access protocol, meaning terminals transmit data
independently without prior coordination, potentially leading to
collisions.
Key Concepts:
Random Access:
ALOHA is a random access protocol, meaning terminals transmit
data at any time without checking if the channel is busy..
Collision Handling:
If multiple terminals transmit at the same time, a collision occurs, and
the frames are destroyed.
Pure ALOHA:
In pure ALOHA, terminals can transmit whenever they have data,
regardless of whether the channel is busy.
Slotted ALOHA:
Slotted ALOHA divides time into slots, and terminals can only
transmit at the beginning of a slot, reducing the likelihood of
collisions.
Data Link Layer:
ALOHA operates at the data-link layer of the OSI model.
Throughput:
The efficiency of ALOHA is measured by its throughput, which is the
percentage of successfully transmitted frames.
Types of ALOHA:
Pure ALOHA:
pure ALOHA is a simpler version where terminals transmit whenever
they have data.
Slotted ALOHA:
Slotted ALOHA divides time into slots, and terminals can only
transmit at the beginning of a slot, reducing the likelihood of
collisions.
History and Significance:
University of Hawaii: The ALOHA network was developed at the
University of Hawaii in the early 1970s to connect computers on
different islands.
Early Computer Networking: ALOHA was one of the earliest
computer networking designs.
Wireless Communication: ALOHA principles are still used in various
wireless communication systems, including satellite communication,

Rules of ALOHA in Computer Network

1. At any time, any station can transmit data to a channel.
2. Collisions and data frames may be lost during data transmission over
multiple stations.
3. There is no need for carrier sensing.
4. Aloha has no collision detection because the acknowledgment of the
frames exists.
5. It necessitates data retransmission after a random amount of time.
Protocol Flow Chart for ALOHA
 Unit 4
The network layer
The network layer in computer networking is responsible for
routing data packets between different networks, using
addressing schemes like IP addresses to identify and locate
destination devices. It's the third layer in the OSI model and
the second layer in the TCP/IP model, facilitating
communication between devices on distinct networks.
Here's a more detailed explanation:

Key Responsibilities:
Routing:
The network layer determines the best path for data packets to travel
from the source to the destination, considering factors like network
congestion and link availability.
Addressing:
It assigns logical addresses (IP addresses) to devices, enabling them
to be identified and located across the network.
Fragmentation and Reassembly:
The network layer breaks down large data segments into smaller
packets for efficient transmission and reassembles them at the
destination.
Packet Forwarding:
It handles the forwarding of packets between different network
segments and through routers.
 In the OSI Model:
 The network layer sits between the transport layer (which handles
end-to-end communication) and the data link layer (which deals with
physical connections between devices on the same network).
 It's responsible for providing the logical addressing and routing
services that are needed for communication between devices across
different networks.

In the TCP/IP Model:

 The network layer is the second layer of the TCP/IP model, also
known as the internet layer.
 It's responsible for providing the means to deliver data from any host
on any network to any other host, regardless of the network's physical
structure.

Bellman–Ford Algorithm

Given a weighted graph with V vertices and E edges, along

with a source vertex src, the task is to compute the shortest
distances from the source to all other vertices. If a vertex is
unreachable from the source, its distance should be marked
as 108. In the presence of a negative weight cycle, return -
1 to signify that shortest path calculations are not feasible.
Examples:
Input: V = 5, edges = [[0, 1, 5], [1, 2, 1], [1, 3, 2], [2, 4, 1], [4,
3, -1]], src = 0

Output: [0, 5, 6, 6, 7]
Explanation: Shortest Paths:
For 0 to 1 minimum distance will be 5. By following path 0 →
1
For 0 to 2 minimum distance will be 6. By following path 0 →
1→2
For 0 to 3 minimum distance will be 6. By following path 0 →
1→2→4→3
For 0 to 4 minimum distance will be 7. By following path 0 →
1→2→4
Input: V = 4, edges = [[0, 1, 4], [1, 2, -6], [2, 3, 5], [3, 1, -2]],
src = 0

Output: [-1]
Explanation: The graph contains a negative weight cycle
formed by the path 1 → 2 → 3 → 1, where the total weight of
the cycle is negative.

Introduction to Dijkstra's Shortest

Path Algorithm
Dijkstra’s algorithm is a popular algorithm for solving
single-source shortest path problems having non-negative
edge weight in the graphs i.e., it is to find the shortest
distance between two vertices on a graph. It was conceived
by Dutch computer scientist Edsger W. Dijkstra in 1956.

Steps-
[Link] algorithm maintains a set of visited vertices and a set
of unvisited vertices.
[Link] starts at the source vertex and iteratively selects the
unvisited vertex with the smallest tentative distance from the
source.
3. It then visits the neighbors of this vertex and updates their
tentative distances if a shorter path is found.
[Link] process continues until the destination vertex is
reached, or all reachable vertices have been visited.

Algorithm for Dijkstra's Algorithm

1. Mark the source node with a current distance of 0 and the
rest with infinity.
2. Set the non-visited node with the smallest current
distance as the current node.
3. For each neighbor, N of the current node adds the current
distance of the adjacent node with the weight of the edge
connecting 0->1. If it is smaller than the current distance
of Node, set it as the new current distance of N.
4. Mark the current node 1 as visited.
5. Go to step 2 if there are any nodes are unvisited.

Dijkstra's Algorithm will generate the shortest path from

Node 0 to all other Nodes in the graph.
For this graph, we will assume that the weight of the
edges represents the distance between two nodes.
Initially we have:
 The Distance from the source node to itself is 0. In this
example the source node is 0.
 The distance from the source node to all other node is
unknown so we mark all of them as infinity.
Example: 0 -> 0, 1-> ∞,2-> ∞,3-> ∞,4-> ∞,5-> ∞,6-> ∞.
 we'll also have an array of unvisited elements that will
keep track of unvisited or unmarked Nodes.
 Algorithm will complete when all the nodes marked as
visited and the distance between them added to the path.
Unvisited Nodes:- 0 1 2 3 4 5 6.

Step 1: Start from Node 0 and mark Node as visited as you

can check in below image visited Node is marked red.
Step 2: Check for adjacent Nodes, Now we have to choices
(Either choose Node1 with distance 2 or either choose Node
2 with distance 6 ) and choose Node with minimum distance.
In this step Node 1 is Minimum distance adjacent Node, so
marked it as visited and add up the distance.
Distance: Node 0 -> Node 1 = 2

Step 3: Then Move Forward and check for adjacent Node

which is Node 3, so marked it as visited and add up the
distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7
Step 4: Again we have two choices for adjacent Nodes
(Either we can choose Node 4 with distance 10 or either we
can choose Node 5 with distance 15) so choose Node with
minimum distance. In this step Node 4 is Minimum distance
adjacent Node, so marked it as visited and add up the
distance.
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 +
10 = 17

Step 5: Again, Move Forward and check for adjacent Node

which is Node 6, so marked it as visited and add up the
distance, Now the distance will be:
Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node
6 = 2 + 5 + 10 + 2 = 19

So, the Shortest Distance from the Source Vertex is 19

which is optimal one

Hierarchical Routing
Hierarchical routing protocols consist of a hierarchical
topology to organize the network and routing information.
Multiple layers and levels are introduced in a network. Each
layer may be assigned a different responsibility like
forwarding packets, maintaining routing tables, etc. HRPs
are valuable for large networks, as they provide the
capability of organizing network information and reducing the
amount of routing information that should be exchanged
between nodes. Hence, HRPs demonstrate significant
scalability and fault tolerance. This is attributed to their
hierarchical structure, which provides redundancy and
facilitates the efficient distribution of routing data throughout
the network.

Advantages of HRP
 Scalability: Hierarchical routing protocols exhibit
excellent scalability by partitioning the network into
smaller segments or areas. This division reduces the
demand for routing tables and updates on each router,
enhancing network efficiency and decreasing overall
network traffic.
 Better Traffic Control: Hierarchical routing protocols
demonstrate superior traffic management compared to
flat routing protocols. The hierarchical framework enables
more efficient traffic control, mitigating the need for
unnecessary routing updates and preventing loops in the
network.
 Easy to Manage: The organisational framework in these
protocols facilitates simplified management and
maintenance.
Disadvantages of HRP

 Complexity: Hierarchical routing protocols tend to be

more intricate compared to flat routing protocols. The
presence of additional layers and segments necessitates
more extensive configuration, posing potential challenges
in implementation.
 Latency: Latency may be introduced into the network due
to the presence of additional layers and segments. Such
delays in data transmission can pose challenges,
particularly for real-time applications.
Working of HSRP
 Each node maintains information about its neighboring
node and their link status
 The information regarding the cluster is broadcast in the
network at regular intervals.
 The job of the cluster leader is to exchange topology and
link state routing information among other cluster leaders
of neighborhood clusters.
 The exchange of link state information is carried out over
multiple hops that consist of gateway nodes and cluster-
heads.
 The path between two cluster-heads which is formed by
multiple wireless links is called virtual link.
 The link status for the virtual link(otherwise called tunnel)
is obtained from the link status parameters of the wireless
links that constitute the virtual link.
 After obtaining information from its peers, the cluster head
floods the information to the lower levels.
 Hierarchical addressing in HSR reduces routing
information compared to link-state routing.
IPv4 and IPv6
In the digital world, where billions of devices connect and
communicate, Internet Protocol (IP) Addresses play a
crucial role. These addresses are what allow devices to
identify and locate each other on a network.
Currently, there are two primary versions of Internet
Protocol in use: IPv4 and IPv6. Each version has distinct
characteristics, capabilities, and was developed to meet the
specific needs of the internet’s growth. IPv4 was the first to
be widely implemented, laying the groundwork for early
network communications.
However, as the internet grew and more devices started
connecting online, the limitations of IPv4 became clear,
leading to the creation of IPv6. This newer version was
designed to address the shortcomings of its predecessor
and to future-proof the network against an ever-increasing
demand for more addresses and improved network
efficiency.

What is IPv4
IPv4, or Internet Protocol version 4, is the original
addressing system of the Internet, introduced in 1983. It
uses a 32-bit address scheme, which theoretically allows for
over 4 billion unique addresses (2^32). IPv4 addresses are
typically displayed in decimal format, divided into four octets
separated by dots. For example, [Link] is a common
IPv4 address you might find in a home network.

IPv4 Address Format

IPv4 Address Format is a 32-bit Address that comprises
binary digits separated by a dot (.).
 Unit 5
Transport Layer
The transport Layer is the second layer in the TCP/IP
model and the fourth layer in the OSI model. It is an end-to-
end layer used to deliver messages to a host. It is termed an
end-to-end layer because it provides a point-to-point
connection rather than hop-to-hop, between the source host
and destination host to deliver the services reliably. The unit
of data encapsulation in the Transport Layer is a segment.
Working of Transport Layer
The transport layer takes services from the Application
layer and provides services to the Network layer.
The transport layer ensures the reliable transmission of
data between systems.
Understanding protocols like TCP and UDP is crucial. If
you’re aiming for a deeper understanding of transport layer
protocols.
At the sender’s side: The transport layer receives data
(message) from the Application layer and then performs
Segmentation, divides the actual message into segments,
adds the source and destination’s port numbers into the
header of the segment, and transfers the message to the
Network layer.
At the receiver’s side: The transport layer receives data
from the Network layer, reassembles the segmented data,
reads its header, identifies the port number, and forwards
the message to the appropriate port in the Application layer.

Responsibilities of a Transport Layer

 The Process to Process Delivery
 End-to-End Connection between Hosts
 Multiplexing and Demultiplexing
 Congestion Control
 Data integrity and Error correction
 Flow control
1. The Process to Process Delivery
While Data Link Layer requires the MAC address (48 bits
address contained inside the Network Interface Card of
every host machine) of source-destination hosts to correctly
deliver a frame and the Network layer requires the IP
address for appropriate routing of packets, in a similar way
Transport Layer requires a Port number to correctly deliver
the segments of data to the correct process amongst the
multiple processes running on a particular host. A port
number is a 16-bit address used to identify any client-server
program uniquely.
2. End-to-end Connection between Hosts
The transport layer is also responsible for creating the end-
to-end Connection between hosts for which it mainly uses
TCP and UDP. TCP is a secure, connection-orientated
protocol that uses a handshake protocol to establish a robust
connection between two end hosts. TCP ensures the reliable
delivery of messages and is used in various applications.
UDP, on the other hand, is a stateless and unreliable
protocol that ensures best-effort delivery. It is suitable for
applications that have little concern with flow or error control
and requires sending the bulk of data like video
conferencing. It is often used in multicasting protocols.
3. Multiplexing and Demultiplexing
Multiplexing(many to one) is when data is acquired from
several processes from the sender and merged into one
packet along with headers and sent as a single packet.
Multiplexing allows the simultaneous use of different
processes over a network that is running on a host.
The processes are differentiated by their port numbers.
Similarly, Demultiplexing(one to many) is required at the
receiver side when the message is distributed into different
processes. Transport receives the segments of data from the
network layer distributes and delivers it to the appropriate
process running on the receiver’s machine.

4. Congestion Control
Congestion is a situation in which too many sources over a
network attempt to send data and the router buffers start
overflowing due to which loss of packets occurs. As a result,
the retransmission of packets from the sources increases the
congestion further. In this situation, the Transport layer
provides Congestion Control in different ways. It uses open-
loop congestion control to prevent congestion and closed-
loop congestion control to remove the congestion in a
network once it occurred. TCP provides AIMD – additive
increases multiplicative decrease and leaky bucket
technique for congestion control.
5. Data integrity and Error Correction
The transport layer checks for errors in the messages
coming from the application layer by using error detection
codes, and computing checksums, it checks whether the
received data is not corrupted and uses the ACK and NACK
services to inform the sender if the data has arrived or not
and checks for the integrity of data.

6. Flow Control
The transport layer provides a flow control mechanism
between the adjacent layers of the TCP/IP model. TCP also
prevents data loss due to a fast sender and slow receiver by
imposing some flow control techniques. It uses the method
of sliding window protocol which is accomplished by the
receiver by sending a window back to the sender informing
the size of data it can receive.