Veermata Jijabai Technological Institute, Mumbai

Electrical Department

DCAN Lab Journal

Group Members:
Advait Talele (171060009)
Saurabh Gawade (171060033)
Yash Patil (171060051)
Mahesh vhatkar (171060087)

1
 INDEX

Sr. Practical Name Page

No. No.
1. Bit Stuffing 3
2. Bit Destuffing 6
3. Cyclic Redundancy Check(CRC) 8
4. Bellman Ford Algorithm 14
5. Connecting networks using routers 20
6. Implement Dijkstra’s shortest path algorithm 23
7. Connecting VLANs using switch 29

2
 Experiment No. 1

Aim: To Perform bits stuffing of the input signals

Resources/ Equipments required: Software: Scilab.
Theory:

Data link layer is responsible for something called Framing, which is the division of stream
of bits from network layer into manageable units (called frames). Frames could be of fixed size or
variable size. In variable-size framing, we need a way to define the end of the frame and the
beginning of the next frame.
Bit stuffing is the insertion of non information bits into data. Note that stuffed bits should
not be confused with overhead bits. Overhead bits are non-data bits that are necessary for
transmission (usually as part of headers, checksums etc.).

3
Applications of Bit Stuffing –
1. synchronize several channels before multiplexing
2. rate-match two single channels to each other
3. run length limited coding

Disadvantages of Bit Stuffing –

The code rate is unpredictable; it depends on the data being transmitted.

Purpose of Bit Stuffing

In Data Link layer, the stream of bits from the physical layer is divided into data frames. The
data frames can be of fixed length or variable length. In variable - length framing, the size of
each frame to be transmitted may be different. So, a pattern of bits is used as a delimiter to mark
the end of one frame and the beginning of the next frame. However, if the pattern occurs in the
message, then mechanisms needs to be incorporated so that this situation is avoided.
The two common approaches are −
• Byte - Stuffing − A byte is stuffed in the message to differentiate from the delimiter.
This is also called character-oriented framing.
• Bit - Stuffing − A pattern of bits of arbitrary length is stuffed in the message to
differentiate from the delimiter. This is also called bit - oriented framing.

Procedure:
Bit stuffing is the insertion of one or more bits into a transmission unit as a way to
provide signaling information to a receiver. The receiver knows how to detect and remove or
disregard the stuffed bits. ... The receiving end removes the stuffed bits and restores
the bit stream to its original sequence.
Whenever a 0 bit is followed by five consecutive 1bits in the message, an extra
0 bit is stuffed at the end of the five 1s. When the receiver receives the message, it removes
the stuffed 0s after each sequence of five 1s. The un-stuffed message is then sent to the upper
layers.
In a data link frame, the delimiting flag sequence generally contains six or more
consecutive 1s. In order to differentiate the message from the flag in case of the same sequence,
a single bit is stuffed in the message.Whenever a 0 bit is followed by five consecutive 1bits in
the message, an extra 0 bit is stuffed at the end of the five 1s.

4
Bit Stuffing Code-

clc
clear
close()
b1s = input("Please enter Bit stream: ")
n = length(b1s)
bstuf = b1s
count = 0
j=1
for i=1:n
if b1s(i) == 1 then
count = count+1
else
count = 0
end
bstuf(j) = b1s(i)

if count == 5 then
j = j+1
bstuf(j) = 0
count = 0
end
j = j+1
end
disp(bstuf)
Output Result :

Conclusion:
In the above experiment we learned how we can Perform bits stuffing of the input
signals. Bit stuffing is the insertion of one or more bits into a transmission unit as a way to
provide signaling information to a receiver.

5
 Experiment No. 2

Aim: To Perform the destuffing of the input signals.

Resources/ Equipments required: Software: Scilab.
Theory:
Data link layer is responsible for something called Framing, which is the division of stream
of bits from network layer into manageable units (called frames). Frames could be of fixed size or
variable size. In variable-size framing, we need a way to define the end of the frame and the
beginning of the next frame.
Bit stuffing is the insertion of non information bits into data. Note that stuffed bits should
not be confused with overhead bits. Overhead bits are non-data bits that are necessary for
transmission (usually as part of headers, checksums etc.).

Destuffing is the reverse of stuffing. In a data link frame, the delimiting flag sequence
generally contains six or more consecutive 1s. In order to differentiate the message from the flag
in case of the same sequence, a single bit is stuffed in the message. Whenever a 0 bit is followed
by five consecutive 1bits in the message, an extra 0 bit is stuffed at the end of the five 1s. When
the receiver receives the message, it removes the stuffed 0s after each sequence of five 1s. The
un-stuffed message is then sent to the upper layers.

Procedure:

In order to differentiate the message from the flag in case of the same sequence, a single
bit is stuffed in the message. Whenever a 0 bit is followed by five consecutive 1bits in the
message, an extra 0 bit is stuffed at the end of the five 1s .When the receiver receives the
message, it removes the stuffed 0s after each sequence of five 1s. The un-stuffed message is then
sent to the upper layers.
When the receiver receives the message, it removes the stuffed 0s after each sequence of
five 1s. The un-stuffed message is then sent to the upper layers.

6
Bit Destuffing code-
clc;
clear;
close;
m1=input('Please type a message bits: ');
c1=0;
c0=0;
stuffcount=0;
[x y]=size(m1)
disp(y)
for i=1:y

for j=i:i+5
if m1(i)==1
c1=c1+1;
else
c0=c0+1;
end
end
if(c1==6||c0==6)
disp([m1(i:i+4) m1(i+6:y)])
break
end

end
Output Result :

Conclusion: In the above experiment we learned how we can Perform bits destuffing of the
input signals. Destuffing is the reverse of stuffing. When the receiver receives the message, it
removes the stuffed 0s after each sequence of five 1s.

7
 Experiment 03
Aim: To study and perform Cyclic Redundancy Check
Software used : Repl.com (Online C++ compiler )

Theory:

Cyclic redundancy check (CRC)

● Unlike the checksum scheme, which is based on addition, CRC is based on binary
division.
● In CRC, a sequence of redundant bits, called cyclic redundancy check bits, are appended
to the end of the data unit so that the resulting data unit becomes exactly divisible by a
second, predetermined binary number.
● At the destination, the incoming data unit is divided by the same number. If at this step
there is no remainder, the data unit is assumed to be correct and is therefore accepted.
● A remainder indicates that the data unit has been damaged in transit and therefore must be
rejected.

Receiver Side (Check if there are errors introduced in transmission)

8
Procedure :-
Step-01: Calculation Of CRC At Sender Side-
At sender side,

● A string of n 0’s is appended to the data unit to be transmitted.

● Here, n is one less than the number of bits in the CRC generator.

● Binary division is performed of the resultant string with the CRC generator.

● After division, the remainder so obtained is called CRC.

● It may be noted that CRC also consists of n bits.

Step-02: Appending CRC To Data Unit

At sender side,

● The CRC is obtained after the binary division.

● The string of n 0’s appended to the data unit earlier is replaced by the CRC remainder.

Step-03: Transmission To Receiver-

● The newly formed code word (Original data + CRC) is transmitted to the receiver.

Step-04: Checking at Receiver Side-

At receiver side,

● The transmitted codeword is received.

● The received codeword is divided with the same CRC generator.

● On division, the remainder so obtained is checked.

9
Result :-
Code:

#include<iostream>

using namespace std;

void division(int temp[],int gen[],int n,int r)

for(int i=0;i<n;i++)

if (gen[0]==temp[i])

for(int j=0,k=i;j<r+1;j++,k++)

if(!(temp[k]^gen[j]))

temp[k]=0;

else

temp[k]=1;

} }}

int main()

{int n,r,message[50],gen[50],temp[50];

cout<<"At Sender's End "<<endl;

cout<<"Enter the number of message bits : ";

cin>>n;

cout<<"Enter the number of generator bits : ";

cin>>r;

cout<<"Enter the message : ";

10
for(int i=0;i<n;i++)

cin>>message[i];

cout<<"Enter the generator : ";

for(int i=0;i<r;i++)

cin>>gen[i];

r--;

for(int i=0;i<r;i++)

message[n+i] = 0;

for(int i=0;i<n+r;i++)

temp[i] = message[i];

division(temp,gen,n,r);

cout<<"CRC : ";

for(int i=0;i<r;i++)

cout<<temp[n+i]<<" ";

message[n+i] = temp[n+i];

cout<<endl<<"Transmitted Message : ";

for(int i=0;i<n+r;i++)

coût<<message[i]<<" ";

cout<<endl<<endl<<"At Receiver's End "<<endl;

cout<<"Enter the received message : ";

for(int i=0;i<n+r;i++)

cin>>message[i];

11
 for(int i=0;i<n+r;i++)

temp[i] = message[i];

division(temp,gen,n,r);

for(int i=0;i<r;i++)

if(temp[n+i])

cout<<"Error detected in received message.";

return 0;

} }

cout<<"No error in received Message.\nReceived Message : ";

for(int i=0;i<n;i++)

coût<<message[i]<<" ";

return 0;

Output:

12
Algorithm:

1. Input the length of message and generator at receivers end

2. Input the message bits and generator bits
3. Then make division of message bits and generator bits
4. Calculated remainder and append that remainder to message and named it is transmitted
message
5. At receiver end we make division of received bits and generator bits can calculated
remainder
6. If remainder == 0 then no error in message else there is error in message

Conclusion:-

In the above experiment we learned how CRC (Cyclic Redundancy Check) works and also
coded the algorithm using cpp with proper output.

13
 Experiment no. 04
Aim :- To study Bellman-Ford algorithm and implement the same.

Software Used :- Repl.com (Online C++ compiler ).

Theory :-

Bellman-Ford Algorithm :-

Solves the single shortest path problem in which edge weight may be negative but no
negative cycle exists. This algorithm works correctly when some of the edges of the directed
graph G may have negative weight. When there are no cycles of negative weight, then we can
find out the shortest path between source and destination. It is slower than Dijkstra's Algorithm
but more versatile, as it is capable of handling some of the negative weight edges.

This algorithm detects the negative cycle in a graph and reports their existence.

Based on the "Principle of Relaxation" in which more accurate values gradually recovered an
approximation to the proper distance by until eventually reaching the optimum solution.

Given a weighted directed graph G = (V, E) with source s and weight function w: E → R, the
Bellman-Ford algorithm returns a Boolean value indicating whether or not there is a negative
weight cycle that is attainable from the source. If there is such a cycle, the algorithm produces
the shortest paths and their weights. The algorithm returns TRUE if and only if a graph contains
no negative - weight cycles that are reachable from the source.

14
Applications in routing

A distributed variant of the Bellman–Ford algorithm is used in distance-vector routing

protocols, for example the Routing Information Protocol (RIP). The algorithm is
distributed because it involves a number of nodes (routers) within an Autonomous system
(AS), a collection of IP networks typically owned by an ISP. It consists of the following
steps:

1. Each node calculates the distances between itself and all other nodes within the
AS and stores this information as a table.
2. Each node sends its table to all neighboring nodes.
3. When a node receives distance tables from its neighbors, it calculates the shortest
routes to all other nodes and updates its own table to reflect any changes.
The main disadvantages of the Bellman–Ford algorithm in this setting are as follows:
● It does not scale well.
● Changes in network topology are not reflected quickly since updates are spread node-
by-node.
● Count to infinity if link or node failures render a node unreachable from some set of
other nodes, those nodes may spend forever gradually increasing their estimates of
the distance to it, and in the meantime there may be routing loops.

Procedure :-

Following are the detailed steps.

Input: Graph and a source vertex src

Output: Shortest distance to all vertices from src. If there is a negative weight cycle, then
shortest distances are not calculated, negative weight cycle is reported.

1) This step initializes distances from the source to all vertices as infinite and distance to the
source itself as 0. Create an array dist[] of size |V| with all values as infinite except dist[src]
where src is the source vertex.

15
2) This step calculates shortest distances. Do following |V|-1 times where |V| is the number of
vertices in a given graph.

…..a) Do following for each edge u-v

………………If dist[v] > dist[u] + weight of edge uv, then update dist[v]

………………….dist[v] = dist[u] + weight of edge uv

3) This step reports if there is a negative weight cycle in the graph. Do following for each edge
u-v

……If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight cycle”

The idea of step 3 is, step 2 guarantees the shortest distances if the graph doesn’t contain a
negative weight cycle. If we iterate through all edges one more time and get a shorter path for
any vertex, then there is a negative weight cycle

Result :-

Code:-

#include<bits/stdc++.h>

using namespace std;

void BellmanFord(int graph[][3],int V,int E,int src)

int dis[V];

for (int i = 0; i < V; i++)

dis[i] = INT_MAX;

dis[src]=0;

for(int i=0;i<V-1;i++)

16
 {

for(int j=0;j<E;j++)

if(dis[graph[j][0]]+graph[j][2]<dis[graph[j][1]])

dis[graph[j][1]]=dis[graph[j][0]]+graph[j][2];

for(int j=0;j<E;j++)

if((dis[graph[j][0]]!=INT_MAX) &&
(dis[graph[j][0]]+graph[j][2]<dis[graph[j][1]]))

cout<<"Graph has -ve weight cycles";

cout << "Vertex Distance from Source" << endl;

for (int i = 0; i < V; i++)

cout << i << "\t\t" << dis[i] << endl;

int main()

17
{

int V;

int E;

cout<<"Enter value for vertices: ";

cin>>V;

cout<<"Enter value for edges: ";

cin>>E;

cout<<"Enter value for graphs (u,v,w)."<<endl<<" u: Value of edge at

start "<<endl<<" v: Value of edge at end"<<endl<<" w: weight of
edge"<<endl;

int graph[E][3];

for(int i=0;i<E;i++)

cout<<"Value for edge "<<i+1<<": ";

cin>>graph[i][0]>>graph[i][1]>>graph[i][2];

int src;

cout<<"Enter value of source: ";

cin>>src;

cout<<endl;

BellmanFord(graph,V,E,src);

18
Output:

Conclusion :-

In this experiment we learned Bellman-Ford Algorithm which is used to find the

minimum distance between destination node and other nodes in a graph. Also implemented
Bellman-ford algorithm using C++ language.

19
 Experiment no.5
Aim :- To connect two networks using a router.

Equipments :-

1. Routers
2. Switches
3. Connecting wires
4. PC or Laptop devices

Software Used :- Cisco Packet Tracker

Theory :-

Routers :-

A router is a networking device that forwards data packets between computer networks.
Routers perform the traffic directing functions on the Internet. Data sent through the internet,
such as a web page or email, is in the form of data packets. A packet is typically forwarded from
one router to another router through the networks that constitute an internetwork (e.g. the
Internet) until it reaches its destination node..

A router is connected to two or more data lines from different IP networks.[b] When a
data packet comes in on one of the lines, the router reads the network address information in the
packet header to determine the ultimate destination. Then, using information in its routing table
or routing policy, it directs the packet to the next network on its journey.

Switches:-

Switches are networking devices operating at layer 2 or a data link layer of the OSI
model. They connect devices in a network and use packet switching to send, receive or forward
data packets or data frames over the network.
A switch has many ports, to which computers are plugged in. When a data frame arrives
at any port of a network switch, it examines the destination address, performs necessary checks
and sends the frame to the corresponding device(s).It supports unicast, multicast as well as
broadcast communications.

20
Procedure :-

1. Select Router 2911 from router series.

2. Now select switch 2950T-24 from the list of switches.
3. Connect devices to Switch 0 using copper straight (fastEthernet ).
4. Now our one Network A is ready now assign ip addresses to devices.
5. repeat steps 1 - 4 for second Network B.
6. Now follow the command to configure both routers in the command line Interface.

Your router is now configured. Now it's time to test.

To test select Add simple PDU and click on one computer to another computer, if you get a
successful message then you have successfully configured a router and connected two different
networks.

21
Results :-

circuit :-

Output :-

Conclusion :-

In this experiment we learned about routers and switches and also successfully connected
two networks by routers using Cisco Packet Tracker.

22
 Experiment 06

Aim :- To study about Dijkstra’s algorithm and implement the same.

Software used :- Repl.com (Online compiler C++)

Theory :-

Dijkastra’s Algorithm

Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an
algorithm for finding the shortest paths between nodes in a graph, which may represent, for
example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and
published three years later.

For a given source node in the graph, the algorithm finds the shortest path between that
node and every other, 196–206 It can also be used for finding the shortest paths from a single
node to a single destination node by stopping the algorithm once the shortest path to the
destination node has been determined. For example, if the nodes of the graph represent cities and
edge path costs represent driving distances between pairs of cities connected by a direct road (for
simplicity, ignore red lights, stop signs, toll roads and other obstructions), Dijkstra's algorithm
can be used to find the shortest route between one city and all other cities. A widely used
application of the shortest path algorithm is network routing protocols, most notably IS-IS
(Intermediate System to Intermediate System) and Open Shortest Path First (OSPF). It is also
employed as a subroutine in other algorithms such as Johnson's.

23
Procedure :-

1. Created a graph having 9 vertices

2. Make a function that implements Dijkstra's single source shortest path algorithm for a
graph represented using adjacency matrix representation
3. The output array. dist[i] will hold the shortest distance from src to i
4. pSett[i] will be true if vertex i is included in shortest path tree or shortest distance from
src to i is finalized
5. Initialize all distances as INFINITE and pSet[] as false
6. Distance of source vertex from itself is always 0
7. Pick the minimum distance vertex from the set of vertices not yet processed. u is always
equal to src in the first iteration. Mark the picked vertex as processed
8. Update dist value of the adjacent vertices of the picked vertex
9. u to v, and total weight of path from src to v through u is smaller than current value of
dist[v]
10. the constructed distance array is printed

Result :-

Code:

#include <bits/stdc++.h>

#define V 9

int min_distance(int dist[], bool pset[])

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (pset[v] == false && dist[v] <= min)

24
 min = dist[v], min_index = v;

return min_index;

void printOutput(int dist[])

printf("Vertex \t\t Distance from Source\n");

for (int i = 0; i < V; i++)

printf("%d \t\t %d\n", i, dist[i]);

void dijkstra(int graph[V][V], int src)

int dist[V];

bool pset[V];

for (int i = 0; i < V; i++)

dist[i] = INT_MAX, pset[i] = false;

25
 dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

int u = min_distance(dist, pset);

pset[u] = true;

for (int v = 0; v < V; v++)

if (!pset[v] && graph[u][v] && dist[u] != INT_MAX

&& dist[u] + graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

printOutput(dist);

26
int main()

int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },

{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },

{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },

{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },

{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },

{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },

{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },

{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },

{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;

27
Output:

Conclusion :- In this experiment we have learned about the Dijkstra algorithm and successfully
implemented it using c++ language and got proper output.

28
 Experiment No.07
Aim :- To connect VLANs using switches.

Equipments :-
1. Switch
2. Devices (PC or laptop)
3. Connecting wires

Software used :- Cisco Packet Tracker.

Theory :-

VLAN :-
A virtual LAN (VLAN) is any broadcast domain that is partitioned and isolated in a
computer network at the data link layer (OSI layer 2). LAN is the abbreviation for local area
network and in this context virtual refers to a physical object recreated and altered by additional
logic. VLANs work by applying tags to network frames and handling these tags in networking
systems – creating the appearance and functionality of network traffic that is physically on a
single network but acts as if it is split between separate networks. In this way, VLANs can keep
network applications separate despite being connected to the same physical network, and without
requiring multiple sets of cabling and networking devices to be deployed.
VLANs address issues such as scalability, security, and network management. Network
architects set up VLANs to provide network segmentation. Routers between VLANs filter
broadcast traffic, enhance network security, perform address summarization, and mitigate
network congestion.

Switches:-
Switches are networking devices operating at layer 2 or a data link layer of the OSI
model. They connect devices in a network and use packet switching to send, receive or forward
data packets or data frames over the network.
A switch has many ports, to which computers are plugged in. When a data frame arrives
at any port of a network switch, it examines the destination address, performs necessary checks
and sends the frame to the corresponding device(s).It supports unicast, multicast as well as
broadcast communications.

29
Procedure :-
1. Create the network topology as shown below:

2. Create 2 VLANs on the switch: VLAN 10 and VLAN 20. You can give them custom
names.
3. Assign switch ports to the VLANs. Remember each VLAN is viewed as a separate
broadcast domain.
4. Assign static IP addresses to the four PCs which are located in the separate VLANs.
PC1 and PC2 fall in VLAN 10 while PC3 and PC4 fall in VLAN 20.
5. Configure inter-VLAN routing on the router
6. Test inter-VLAN connectivity. Here we’ll test connectivity between computers in
different VLANs . Don’t forget that its the router that enables inter-VLAN routing.

Result :-
Circuit

30
Output :-

Conclusion :-
In this experiment we have connected two VLANs using a single switch. Using Cisco Packet
tracker software .

31