GALGOTIAS UNIVERSITY

SCHOOL OF COMPUTING SCIENCE & ENGINEERING

DATA COMMUNICATION & NETWORKING LAB

BCSE2052

Name of the Student:

Semester

Roll. No.
Batch

Submitted To

Version 1.0 Date: 01.08.2019 Drafted By: Dr. K.M Baalamurugan

 INDEX

Date of Staff
Sr. No. LIST OF EXPERIMENTS
Experiment Signature

1 To study about different physical equipment’s used for networking.

2 To study different internetworking devices in a computer network.

Analysis and study of basic networking commands (Commands like

3
ipconfig, getmac, tracert, pathping, arp, ping, netstat, finger etc.)

4 Write a program that simulates the Bit and Byte Stuffing and Unstuffing

Write a program for hamming code generation for error detection and
5
correction

6 Write and Test program for Cyclic Redundancy Check (CRC)

7 Write a Program to simulate Distance Vector Routing

8 Write a program to simulate Link State Routing

9 Write a program to simulate the stop – and - wait protocol

10 Write a program to simulate the selective repeat protocol

11 Write a program to simulate LZW compression algorithm

Installation and working of Remote Desktop and Telnet (Terminal

12
Network)
Ex. No:
To study about different physical equipment’s used for networking
Date:

AIM: To study about different physical equipment’s used for networking.

1. Learning Objective:
At the end of the session you will be able to become familiar with different types of
equipment’s and cables used in the networked lab.
2. What is a Computer Network?
Computer network means an interconnected collection of autonomous computers.
Two computes said to be connected if they are able to exchange information. The
connection needs to be done via some transmission media such as a coaxial cable,
twisted pair cable; fiber optics, microwares and communication satellite can also be
used. To interconnect the devices in the network requires some networking devices
such as a hub, a switch or a router etc. To be autonomous means a device to be able
to start or stop of its own.
3. Benefits of Computer network:
o Resource Sharing
o High Reliability
o Saving Money
4. Network Components
1 Server
Concept of a server is based on one or more personal computers to perform
specific tasks for a number of other PCs. The most common function is disk, file
and print servers.
A Disk Server provides low-level support and performs basic read/write
operation to disk sectors.
A File Sever is a higher-level support mechanism, performing such function as
lockout and dynamic allocation of space on disk. In a star topology the server is
the principal connection point. All nodes, including the server, are connected to
 a hub. This enables the server to house and administer software, fie sharing, file
saving and to allocate printers or other peripherals. In a bus topology, the server
acts like arbitrator, each node talks to the server when requesting information.
The server then locates the information on one of the connected clients and
sends it to the requesting client. Servers in any network can be an ordinary node
but having more capabilities of handling the data and having more speed.
2 Workstation
A node or stand-alone PC that is connected with network is called Workstation.
A workstation is generally a Client.
NIC (Network Interface Card): The network Interface Card (NIC) is the
interface between the PC and physical network connection. It is also called as
Network Adapter Card. The NIC is responsible for the operation that tasks place
in the physical layer of the OSI model. It is only concerned with sending and
receiving) 0s and 1s, using the IEEE 802.3 Ethernet standard.
In windows, the NIC card is identified in the network property; to use protocol
with NIC you must bind the protocol to the adapter card.
Function of NIC:
• Data Transfer
• Data Buffering
• Frame Construction
• Media Access Control
• Parallel/Serial Conversion
• Data Encoding/Decoding
• Data Transmission/Reception
3 Cables
To transmit the data the medium must exist, usually in the form of cables or
wireless media. Here are some most commonly used cable types.

a. Thick Coaxial Cables (thick net) (RG-11)

Thick coaxial cables or thick wire is known as the Ethernet standard RG-
11. This cable is mostly used as backbone cable, distributing Ethernet
signal throughout a building, an office complex or other large installation. It is used
in 10base5 Ethernet standard. The length may be up to 500 meters with a max of
five segments connected by repeaters. This gives a total distance of 2500
meters. This is called a network diameter. RG-11 cable is typically
orange; with black rings around the cable every 2.5-meter to allow taps
into the cable.
Thin coaxial cables (thin net) (RG-58)
RG-58 is typically used for wiring laboratories and offices, or another
small group of computers. The maximum length of thin wire Ethernet
segment is 185 meters, which is due to the nature of the CSMA/CD
method of operation, the cable attenuation, and the speed at which signals
propagate inside the coax.

Fig: Thin coaxial cables (thin net) (RG-58)

The length is limited to guarantee that collision is detected when machines

that are apart transmit at the same time. BNC connectors are used to
terminate each end of the cable. When many machines are connected to
the same Ethernet segment, a daisy chain approach is used. The BNC
connectors allow the network interface card to the next machine. The
machine each end of the cable must use a terminating resistor to eliminate
collision-causing reflection in the cable.
 Coaxial Cable Connectors
Coaxial connectors are needed to connect coaxial cable to devices. The
most common type of connector used today is the Bayone-Neil-
Concelman, in short, BNC connector.

The three popular types of connectors are: the BNC connector, the BNC T
connector, and the BNC terminator. The BNC connector is used to
connect the end of the cable to a device, such as a TV set. The BNC T
connector is used in Ethernet networks to branch out to a connection to a
computer or other device. The BNC terminator is used at the end of the
cable to prevent the reflection of the signal.
Applications
Ø Coaxial cable was widely used in analog telephone networks, and later
with digital telephone networks.
Ø Cable TV networks use coaxial cables (RG-59) at the network boundaries.
However, coaxial cable has largely been replaced today with fiber-optic cable due
to its higher attenuation.
Ø Traditional Ethernet LAN
• 10Base-2, or thin Ethernet, uses RG-58 coax cable with BNC
connectors.
• 10Base-5, or thick Ethernet, uses RG-11 coax cable with specialized
connectors.
b. Twisted pair cables
Twisted pair is probably the most widely used cabling system in Ethernet
in networks. Two copper wires twist around each other to form the twisted
 pair cable. Depending on category several insulated wire strands can
reside in the cable.
Twisted pair is available in two basic types
Ø Unshielded Twisted Pair (UTP)
Ø Shielded Twisted Pair (STP)

Fig: Twisted pair cables

Unshielded Twisted Pair
Mostly the UTP is used. A twisted pair segment can’t exceed 100 meters.
This limitation is the only drawback to twisted pair. Twisted pair is used
for 10/100 based Ethernet networks. UTP cables are wired as straight
through or crossover cables. Straight through cables typically connect the
computer’s networks interface can’t to be a port on the hub. Crossover
cables are used for NIC to communication and for hub-to-hub connections
when no crossover port is available.
 Category Descriptor
Contains four twisted pair and a data transmission up to 4
1 Mbps.
Used for some token ring network.
Contains four twisted pair and a data transmission up to 10
2 Mbps.
Used for some token ring network.
Contains four twisted pair and a data transmission up to 16
3 Mbps.
Used for some token ring network.
Contains four twisted pair and a data transmission up to 100
4 Mbps.
Used for some token ring network.
Category-5 cables can be purchased or crimped as either straight through or crossed.
A category-5 cable has 8 thin. Colours coded wires inside that run from one end of the
cable to the other. Ethernet networks for communication use only wires 1, 2, 3 and to
be connected in both jacks. Straight through cables are used for connecting to a hub.
Crossed cables are used for connecting a hub to another hub (there is an exception:
some hubs are a built in uplink port that is crossed internally, which allows you to
uplink hubs with a straight cable instead.) In a straight through cable wires 1, 2, 3….
and 6 at the other end. In a crossed cable, one order of the wires change from one end
to the other wire 1 becomes 3 and 2 becomes 6.
For PC 2 PC Communication without HUB (Cross Cable Connection)
Sl. No. One Site Second Site Pin Configuration
01 Orange White Green White Transmit
02 Orange Green Transmit
03 Green White Orange White Receive
04 Blue Blue Not Use
05 Blue White Blue White Ground
06 Green Green Receive
07 Brown White Brown White DTR
08 Brown Brown DTS
 PC 2 PC Communication with HUB (Simple Cable Connection)

Sl. No. One Site Second Site Pin Configuration

01 Orange White Orange White Transmit
02 Orange Green Transmit
03 Green White Orange White Receive
04 Blue Blue Not Use
05 Blue White Blue White Ground
06 Green Green Receive
07 Brown White Brown White DTR
08 Brown Brown DTS
For One Cable in Two PC Communication through HUB

(Simple Cable Connection)

First Connection

Sl. No. One Site Second Site Pin Configuration

01 Orange White Green White Transmit
02 Orange Orange Transmit
03 Green White Green White Receive
04 Green Green Receive

Second Connection:

Sl. No. One Site Second Site Pin Configuration

01 Blue Green White Transmit
02 Blue White Orange Transmit
03 Brown White e Green White Receive
04 Brown Green Receive

Shielded Twisted Pair It is 150Ω cable containing additional shielding that protects
signals against electromagnetic Interference (EMI) produced by electric motors power
lines etc. It is primarily used in Token Ring Network & where UTP cable would
provide insufficient protection against interface. Wires within cables are encased in a
metallic sheath that is conductive as copper in wires. This sheath when properly
grounded converts it ambient noise into current, like antenna. This current is carried to
wires within where it creates an equal and opposite current flowing in twisted pair thus
getting cancelled and no noise signal is resulted.
Unshielded Twisted-Pair Connector
The most common Unshielded Twisted-Pair connector is RJ45. RJ stands for
registered jack. Inside the Ethernet cable, there are 8 color coded wires, with all eight
pins used as conductors. These wires are twisted into 4 pairs and each pair has a
common color theme. RJ45 specifies the physical male and female connectors as well
as the pin assignments of the wires. RJ45 uses 8P8C modular connector, which stands
for 8 Position 8 Contact. It is a keyed connector which means that the connector can be
inserted only in a single way. RJ45 is used almost exclusively to refer to Ethernet-type
computer connectors.
Characteristics of twisted pair cable
1 Requires amplifiers every 5-6 km for analog signals
2 Requires repeaters every 2-3 km for digital signals
3 Attenuation is a strong function of frequency
4 Susceptible to interference and noise
Applications
1 Used in telephone lines to provide voice and data channels.
2 The local loop –the line connecting the subscriber to the central telephone
office- commonly consists of UTP cables.
3 DSL lines are also UTP cables.
4 LANs such as, 10Base-T and 100Base-T use UTP cables.

Fig: Unshielded Twisted-Pair Connector

Fiber Optic
Fiber Optic relies on pulsed as light to carry information. Two types of plastic or glass
with different physical properties are used (the inner core and the outer cladding) to
allow a beam of light to reflect off the boundary between the core and cladding. Some
fiber optic cables allow many different paths other allow one single mode. They are
called multimode and single mode fibers. A popular multimode fiber has core/cladding
dimensions of 62.5/125 nanometers.

Fiber Optic cable connector

Ex. No:
To study different internetworking devices in a computer network
Date:

Aim: To study different internetworking devices in a computer network.

Learning Objective: At the end of the session you will be able to be familiar with
different types of internetworking devices and their functions.
A Repeater is a purely electrical device that extends maximum distance a LAN cable
can span by Amplifying signals passing through it. A Repeater connects two segments
and broadcasts packets between them. Since signal loss is a factor in the maximum
length of a segment, a Repeater is used to amplify the signal and extend the usable
length.

Repeaters

A common Ethernet rule is that no more than four repeaters may be used to join
segments together. This is a physical limitation designed to keep collision detection
working properly. Repeaters operate at layer 1 (Physical layer) of the OSI model.
BRIDGES
The networks bridge provides an inexpensive and easy way to connect network
segments. A bridge provides Amplification function of a repeater plus, ability to select
filter packets based on their addresses. When network grows in size, it is often
necessary to partition it in to smaller group of nodes to help isolate traffic
and improve performance. One way to do this is to use bridge, the operation of it is to
keep one segment traffic to that side and other side will cross the bridge. The bridge
learns which packets should cross it as it is used.

Bridged network
ROUTERS
A router is a device that connects two LANs together to form an inter-network. A
router is the basic building block of the Internet. Each router connects two or more
networks together by providing an interface for an Ethernet network and ring network
to which it is connected.

Routers
The router examines each packet of information to detection weather the packet must
be translated form on one network to another network performing a function similar to
a bridge. Unlike a ridge, a router can connect network that use
different technologies, addressing methods, media type, frame format and speeds. A
router is a special purpose device designed to interconnect networks. Such that three
networks can be connected using two routers. Routers maintain routing tables in their
memories to store information about the physical connection on he network; the router
examines each packet of data, checks the routing table and then forwards the packet if
necessary. Every other router in the path (between any state destinations) performs a
similar procedure. Note that a router does not maintain any state information about the
packets; it simply moves them along the network. Routers are operated at layer
3(network) of OSI model.
GATEWAYS
A gateway is node in a network that serves as an entrance to another network. In
enterprises, the gateway node often acts as a proxy server and a firewall. The gateway
is also associated with both a switch, which provides the actual path for the packet in
and out of the gateway. It is also known as a computer system located on earth that
switches data signals and voice signals between satellites and terrestrial networks. A
gateway can operate at any layer of the OSI or TCP/IP reference model. The hub of a
gateway, also called a protocol converter, is much more complex than that of a router
or switch. Typically a gateway must convert from one protocol stack to another. E.g. a
gateway may connect a TCP/IP network to an IPX. /SPX network. A Circuit Level
Gateway function provided by Application level gateway products enables trusted
users on private network to access Internet services with all security of a proxy server.
An Application Level Gateway provide much stricter form of security that packet
filters, but they are designed to regulate access only for a particular application.
HUBS
Hubs are also called concentrators; expand one Ethernet connection into many. For
example, a four-port hub connects up to four machines via UTP cables. The hub
provides a star connection for the four ports. Many hubs contains a single BNC
connectors as well to connect the hub to existing 10base2 network wiring, the hub can
also be connected via one of its ports. One pot is desired to operate
in either straight through or crossover mode, selected by a switch on the hub. Hubs that
can connect in this fashion are called stackable hubs. A hub is similar to a repeater,
expect it broadcasts data received by any port to all other ports on the hub. Most hubs
contain a small amount of intelligence as well. Examining received packets and
checking them for integrity. If a bad packet arrives or the hub determines that a port is
unreliable. It will shut down the line under the error condition is appears. The hub also
acts like a repeater. Because of its slight delay when processing a packet, the numbers
of hubs that may be connected in a series are limited.

There are three types of HUB passive hub, active hub and intelligent hub. The
Passive hubs do not process data signals with only purpose to combine the signal from
several networks cables segments. All devices attached to the passive hub receive another
packets that pass through the hub .Hub does not clear up or amplify the signals, on the
contrary absorbs a small part of the signals that is why the distance between a hub and a
computer should not be more than half of the permissible distance between two
computers. Passive hubs have limited functionality so are inexpensive and easy to
configure. It has four ports with four BNC (British Naval Connectors) female connectors
to configure networks station or terminated with a 93 Ω BNC Terminator. The active
hubs incorporate electronic components that amplify and cleanup the signals, that flaw
between devices on the network. The process of cleaning up signal is called “signal
regeneration”. The benefits of signals regeneration are:
Ø A network is more robust i.e. less sensitive errors.
Ø Distance between devices can be increased.
Active hubs cost is considerable more than passive hub (active hub function impart as
multi port repeaters). Intelligent hubs are enhanced active hubs the following functions
add intelligence to a hub. Intelligent Hubs are units have form of integrated
management capability.
Hub Management A hub supports networks network management protocols that
enable the hub to send packets to central network console. Theses protocols enable
network console to manage or control hub.
Switching hubs
Switching hubs include circuitry that quickly routes signals between ports on the hub.
Insured of repeating a packet to all ports on the hub, it repeats a packet only to the port
that connects to the destination computer for the packet.
SWITCHES
It is similar to a bridge, with some important enhancement. First, as witch may have
multiple ports, thus directing packets to several different segments further partitioning
and isolating network traffic in as way similar to router. For example, if 8-port n way
switch is there it can route packets from any input to any output.

Some or all of incoming packet is called store and forward, which stores the received
packet before examining it to for error before retransmitting. Bad packets are not
forwarded. A switch typically has auto-sensing 10/100 mbps ports and will just the
speed of each port accordingly; furthermore, a managed switch supports SNMP for
further control over network traffic. Switches operated at layer 2 (Data Link) of OSI
model.
Experiment No : 3
Analysis and study of basic networking commands. (Commands like ipconfig,
Title
getmac, tracert, pathping, arp, ping, netstat, finger etc.)

Objective To Understand Basic Networking Commands Used in Windows and Linux.

Knowledge of Windows and Linux.
Pre-requisite
Algorithm / ipconfig
ipconfig [down |delete]
Theory
ethereal to launch ethereal
tcpdump –i tool to capture and analyze packets
netstat –w [seconds] –I [interface] display network settings and
statistics udpmt –p [port] –s [bytes] target_host it creates UDP traffic
udptarget –p [port] it’s able to receive UDP traffic
tcpmt –p [port] –s [bytes] target_host it creates TCP
traffic tcptarget –p [port] it’s able to receive TCP traffic
ARP, switching and VLANs
arp –a it shows the current ARP table
arp –s to add an entry in the table
arp –a –d to delete all the entries in the ARP table
telnet 192.168.0.254 to access the switch from a host in its subnetwork
sh ru or show running-configuration to see the current configurations
configure terminal to enter in configuration mode
exit in order to go to the lower configuration mode
vlan n it creates a VLAN with ID n
no vlan N it deletes the VLAN with ID N
untagged Y it adds the port Y to the VLAN N
ifconfig vlan0 create it creates vlan0 interface
ifconfig vlan0 vlan ID vlandev em0 it associates vlan0 interface on top of em0, and set the
tags to ID
ifconfig vlan0
to turn on the virtual interface
tagged Y it adds to the port Y the support of tagged frames for the current VLAN
Routing
netstat –rnf inet it displays the routing tables of IPv4
sysctl net.inet.ip.forwarding=1 to enable packets forwarding (to turn a host into a router)
route add|delete [-net|-host] (ex. route add 192.168.20.0/24 192.168.30.4) to add a route
route flush it removes all the routes
route add -net 0.0.0.0 192.168.10.2 to add a default route routed -Pripv2 –Pno_rdisc
–d [-s|-q] to execute routed daemon with RIPv2 protocol, without ICMP auto-
discovery, in foreground, in supply or in quiet mode route add 224.0.0.0/4 127.0.0.1
it defines the route used from RIPv2
rtquery –n to query the RIP daemon on a specific host (manually update the routing table)
UDP/TCP
socklab udp it executes socklab with udp protocol
sock it creates a udp socket, it’s equivalent to type sock udp and bind
sendto emission of data packets
recvfrom it receives data from socket
socklab tcp it executes socklab with tcp protocol
passive it create a socket in passive mode, it’s equivalent to sock tcp, bind, listen
accept it accepts an incoming connection (it can be done before or after creating the
incoming connection)
active it create a socket in active mode
connect <hostname><port #> these two commands are equivalent to sock tcp, bind,
connect
close it closes the connection
read <byte #> to read bytes on the socket
write (ex. write ciao, ex. write #10) to write “ciao” or to write 10 bytes on the socket
NAT/Firewall
ipnat –f file_name it writes filtering rules into file_name
ipnat –l it gives the list of active rules ipnat –C –F it re-
initialize the rules table
map em0 192.168.1.0/24 -> 195.221.227.57/32 portmap tcp/udp
20000:50000 ipf –f file_name it writes filtering rules into file_name ipf –F –a
it resets the rule table
ipmon log_file in proto icmp all it allows to display the specified traffic
 ipfstat –I it grants access to a few information on filtered packets, as well as active filtering
rules
[block/pass] [in/out] proto [icmp/tcp/udp] from [any/192.168.0.1/24] port=22 to
[any/192.168.1.1/24] port=80

Sample
Output

Post Lab
Assignment
(If Any)
Experiment No : 4

Title Write a program that simulates the Bit and Byte Stuffing and Unstuffing.

Objective Implement bit stuffing and de-stuffing

Pre-requisite Knowledge of functions of physical layer and data Link layer

Algorithm / for(i=0;i<strlen(str);i++){
2. count=0;
Theory 3. //the following code search the six ones in given string
4. for(j=i;j<=(i+5);j++){
5. if(str[j]=='1'){
6. count++;
7. }
8. }
9. //if there is six ones then following code execute to bit stuffing after five ones
10. if(count==6){
11. nl=strlen(str)+2;
12. for(;nl>=(i+5);nl--){
13. str[nl]=str[nl-1];
14. }
15. str[i+5]='0';
16. i=i+7;
17. }
18. }
#include
#include
#include
main()
{
int ch;
clrscr();
do
{
printf("\n********************:");
printf("\n1.BIT STUFFING:");
printf("\n2.BYTE STUFFING:");
printf("\n3.EXIT:");
printf("\n*********************");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:bit();
break;
case 2:character();
break;
case 3:exit(0);
}
}while(ch!=3);
getch();
}
bit()
{
FILE *fp,*fp1;
char ch;
int i;
if((fp=fopen("source.txt","w"))==NULL)
{
printf("\nError in opening the file");
exit(0);
}
printf("\nEnter data to send press 'e' to end :\n");
i=0;
while(1)
{
scanf("%c",&ch);
if(ch=='e')
break;
if(ch=='1')
i++;
else
i=0;
putc(ch,fp);
if(i==5)
{
putc('0',fp);
i=0;
}
}
fclose(fp);
i=0;
fp=fopen("source.txt","r");
fp1=fopen(
fclose(fp);
if((fp=fopen("Input.txt","r"))==NULL)
{
printf("\nInput.txt file opening problem...");
exit(0);
}
if((fp1=fopen("csource.txt","w"))==NULL)
{
printf("\ncsource.txt file opening problem...");
exit(0);
}
fputs(" DLE STX ",fp1);
while((ch=getc(fp))!=EOF)
{
if(ch=='D')
{
c[0]=getc(fp);
c[1]=getc(fp);
if(c[0]=='L'&&c[1]=='E')
fputs("DLE",fp1);
putc(ch,fp1);
putc(c[0],fp1);
putc(c[1],fp1);
}
else
putc(ch,fp1);
}
fputs(" DLE ETX ",fp1);
fclose(fp);
fclose(fp1);
if((fp=fopen("csource.txt","r"))==NULL)
{
printf("\ncsource.txt file opening problem...");
exit(0);
}
if((fp1=fopen("cdest.txt","w"))==NULL)
{
printf("\ncdest.txt file opening problem...");
exit(0);
}
beg=ftell(fp);
beg+=9;
fseek(fp,-0L,2);
end=ftell(fp);
end-=9;
fclose(fp);
printf("\nData after stuffing ");
fp=fopen("csource.txt","r");
while((ch=getc(fp))!=EOF)
putc(ch,stdout);
fclose(fp);
printf("\n");
printf("\nThe data after destuffing");
fp=fopen("csource.txt","r");
fgets(j,9,fp);
while(beg<=end)
{
ch=getc(fp);
if(ch=='D')
{
c[0]=getc(fp);
c[1]=getc(fp);
if(c[0]=='L'&&c[1]=='E')
{
fgets(k,4,fp);
beg+=4;
}
else
{
putc(ch,fp1);
putc(c[0],fp1);
putc(c[1],fp1);
putc(ch,stdout);
putc(c[0],stdout);
putc(c[1],stdout);
}
}
else
{
putc(ch,fp1);
putc(ch,stdout);
}
beg++;
}
fclose(fp);
fclose(fp1);
}
Sample OUTPUT
Output ********************
1.BIT STUFFING:
2.CHARACTER STUFFING:
3.EXIT:
*********************
Enter your choice:1
Enter data to send press 'e' to end :
11100000111111111101e
DATA AFTER STUFFING
1110000011111011111001
DATA AFTER UNSTUFFING
11100000111111111101
********************:
1.BIT STUFFING:
2.CHARACTER STUFFING:
3.EXIT:
*********************
Enter your choice:2
Enter data to send at end put '}':
This is DLE idle DLE program}
Data after stuffing
DLE STX This is DLEDLE idle DLEDLE program DLE ETX
The data after destuffing
This is idle program
********************:
1.BIT STUFFING:
2.BYTE STUFFING:
3.EXIT:
*********************
Enter your choice:3
Post Lab
Assignment
(If Any)

Write a program for hamming code generation for error detection and
Title
Objectiv
correction Implement Hamming Code
e
Knowledge of working of Data link Layer error correction and detection method
Pre-
requisite
Theory:
Hamming codes are used for detecting and correcting single bit errors in transmitted data.
This requires
that 3 parity bits (check bits) be transmitted with every 4 data bits. The algorithm is called A (7,
4) code,
because it requires seven bits to encode 4 bits of data.
Example
Verification Parity Bit Bit Strin
0+0+0+0 = 0 0 000
0+0+1+1 = 0 1 001
0+1+0+1 = 0 1 010
0+1+1+0 = 0 0 011
1+0+0+1 = 0 1 100
1+0+1+0 = 0 0 101
1+0+1+0 = 0 0 110
1+1+1+1 = 0 1 111
Parity types

Even: - Even number of 1’s is present, i.e. the modulo 2 sum of the bits is 0.

Odd: - Odd number of 1’s is present, i.e. the modulo 2 sum of the bits is 1.

Given data bits d1, d2, d3 and D4, A (7, 4) Hamming code may define parity bits p1, p2 and
p3 as,

P1=D2+D3+D4

P2=D1+D3+D4

P3=d1+D2+D4

There are 4 equations for a parity bit that may be used in Hamming codes,

P4=D1+D2+D3

Valid Hamming codes may use any 3 of the above 4 parity bit definitions. Valid Hamming
codes may also place the parity bits in any location within the block of 7 data and parity bits.

One method for transferring 4 bits of data into a 7 bit Hamming code word is to use a 4x7
generate
matrix [G] defined to be the 1x4 vector [d1 d2 d3 d4].

It’s possible to create a 4x7 generator matrix [G] such that the product modulo 2 of d and [g] (d[G]) is
the desired 1x7 Hamming code word.

For example each data bits can be represented with in a column vector as follows.

0 0 0
0 0 1
D4 D3 D2
0 1 0
1 0 0
And represent each parity bit with a column vector continuing a 1 in the row corresponding to each data
bit included in the computation and a zero in all other rows.
1 1
1 0
P3 P2
0 1
1 1
And
0 0 0 1 1 1 0
0 0 1 0 1 0 1
0 1 0 0 0 1 1 G
1 0 0 0 1 1 1
D4 D3 D2 D1 P3 P2 P1

Encoding
The process to encode the data value 1010 using the Hamming code defined by the G matrix is as
follows
0 0 0 1 1 1 0
0 0 1 0 1 0 1
0 1 0 0 0 1 1
1 0 0 0 1 1 1

[1010]
1 0+0+1+0 (1*0)+ (0*1)+ (1*1)+ (0*1)
0 1+0+1+0 (1*1)+ (0*0)+ (1*1)+ (0*1)
1 1+0+0+0 (1*1)+ (0*1)+ (1*0)+ (0*1)
1 = 1+0+0+0 = (1*1)+ (0*0)+ (1*0)+ (0*0)
0 0+0+0+0 (1*0)+ (0*1)+ (1*0)+ (0*0)
1 0+0+1+0 (1*0)+ (0*0)+ (1*1)+ (0*0)
0 0+0+0+0 (1*0)+ (0*0)+ (1*0)+ (0*1)
Therefore 1010 encodes into 1011010. Equivalent Hamming codes represented by different generator
matrices will produce different results.
Decoding
The first step is to check the parity bits to determine if there is an error. Arithmetically, parity may be
checked as follows: -
P1 = D2+D3+D4 = 0+1+1 = 0
P2 = D1+D3+D4 = 1+1+1 = 1
P3 = D1+D2+D4 = 1+0+1 = 0
Parity may also be validated by using matrix operation. A 3x7 parity check matrix [H] may be
s
constructed such that row 1 contains 1 in the position of the first parity bits and all the data bits that are
included in its parity calculation. Using this, matrix [H] may be defined as follows

1 1 1 0 0
1 1 0 1 0
1 0 1 1 1
3rd Parity
2nd Parity
st
1 Parity
Multiplying the 3x7 matrix [H] by a 7x1 matrix representing the encoded data produces a 3x1 matrix
called the Syndrome.
If the syndrome is all 0’s the encoded data is error free. If the syndrome has a non-zero value, flipping
the encoded bit that is in the position of the column matching the syndrome will result in a valid code
word.
Ex:
Suppose the data received is 1011011,
Then

1
0
1 (1*1)+(0*0)+(0*1)+(0*1)+(1*0)+(1*1)+(1*1) 1 1 1 1 0 0
1 = (0*1)+(1*0)+(0*1)+(1*1)+(0*0)+(1*1)+(1*1) = 1 1 1 0 1 0
1 (0*1)+(0*0)+(1*1)+(1*1)+(1*0)+(0*1)+(1*1) 0 1 0 1 1 1
1
1

Looking back at the matrix [H] the 7th column is all 1s so the 7th bit is the bit that has an error.
Program

#include<stdlib.h>

#include<stdio.h>

char data[5];

int encoded[8], edata[7], syndrome[3];

int hmatrix[3][7]= { 1,0,0,0,1,1,1,

0,1,0,1,0,1,1,

0,0,1,1,1,0,1};

char gmatrix[4][8]={ "0111000", "1010100", "1100010", "1110001"};

int main()

int i,j;

system("clear");

printf("Hamming Code --- Encoding\n");

printf("Enter 4 bit data : ");

scanf("%s",data);

printf("Generator Matrix\n");

for(i=0;i<4;i++)

printf("\t %s \n",gmatrix[i]);

printf("Encoded Data : ");

for(i=0;i<7;i++)

for(j=0;j<4;j++)

encoded[i]+=((data[j]- '0')*(gmatrix[j][i]- '0'));

encoded[i]=encoded[i]%2;
printf("%d",encoded[i]);

printf("\nHamming code --- Decoding\n");

printf("Enter Encoded bits as received : ");

for(i=0;i<7;i++)

scanf("%d",&edata[i]);

for(i=0;i<3;i++)

for(j=0;j<7;j++)

syndrome[i]=syndrome[i]+(edata[j]*hmatrix[i][j]);

syndrome[i]=syndrome[i]%2;

for(j=0;j<7;j++)

if ((syndrome[0]==hmatrix[0][j])&&(syndrome[1]==hmatrix[1][j])&&

(syndrome[2]==hmatrix[2][j]))

break;

if(j==7)

printf("Data is error free!!\n");

else {

printf("Error received at bit number %d of the data\n",j+1);

edata[j]=!edata[j];

printf("The Correct data Should be : ");

for(i=0;i<7;i++) printf(" %d ",edata[i]);

}
}

Output
Hamming Code --- Encoding
Enter 4 bit data : 1 0 1 0
Generator Matrix
0111000
1010100
1100010
1110001
Encoded Data : 1 0 1 1 0 1 0
Hamming code --- Decoding
Enter Encoded bits as received : 1 0 1 1 0 1 1
Error received at bit number 7 of the data
The Correct data Should be : 1 0 1 1 0 1 0

Hamming Code --- Encoding

Enter 4 bit data : 1 0 1 0
Generator Matrix
0111000
1010100
1100010
1110001
Encoded Data : 1 0 1 1 0 1 0
Hamming code --- Decoding
Enter Encoded bits as received : 1 0 1 1 0 1 0
Data is error free!!
 Experiment No : 6

Implement cyclic redundancy check CRC

Title
To learn CRC
Objective
Knowledge of working of Data link Layer error correction and detection method
Pre-requisite
Theory
It does error checking via polynomial division. In general, a bit string
bn-1bn-2bn-3…b2b1b0
As
bn-1Xn-1 + bn-2 Xn-2 + bn-3 Xn-3 + …b2 X2 + b1 X1 + b0
Ex: -
10010101110
As
X10 + X7+ X5+ X3+ X2+ X1
All computations are done in modulo 2
Algorithm
S s
1. Given a bit string, append 0 to the end of it (the number of 0 is the same as the degree of the
generator polynomial) let B(x) be the polynomial corresponding to B.
2. Divide B(x) by some agreed on polynomial G(x) (generator polynomial) and determine the
remainder R(x). This division is to be done using Modulo 2 Division.
3. Define T(x) = B(x) –R(x)
(T(x)/G(x) => remainder 0)
4. Transmit T, the bit string corresponding to T(x).
5. Let T’represent the bit stream the receiver gets and T’(x) the associated polynomial. The receiver
divides T1(x) by G(x). If there is a 0 remainder, the receiver concludes T = T’ and no error occurred
otherwise, the receiver concludes an error occurred and requires a retransmission.

Program

#include<stdio.h>

#include<string.h>

#include<conio.h>
#define N strlen(g)

char t[128], cs[128], g[]="10001000000100001";

int a, e, c;

void xor() {

for(c=1;c<N;c++) cs[c]=((cs[c]==g[c])?'0':'1');

void crc() {

for(e=0;e<N;e++) cs[e]=t[e];

do {

if(cs[0]=='1') xor();

for(c=0;c<N-1;c++) cs[c]=cs[c+1];

cs[c]=t[e++];

}while(e<=a+N-1);

void main() {

clrscr();

printf("\nEnter poly : "); scanf("%s",t);

printf("\nGenerating Polynomial is : %s",g);

a=strlen(t);

for(e=a;e<a+N-1;e++) t[e]='0';

printf("\nModified t[u] is : %s",t);

crc();

printf("\nChecksum is : %s",cs);

for(e=a;e<a+N-1;e++) t[e]=cs[e-a];
printf("\nFinal Codeword is : %s",t);

printf("\nTest Error detection 0(yes) 1(no) ? : ");

scanf("%d",&e);

if(e==0) {

printf("Enter position where error is to inserted : ");

scanf("%d",&e);

t[e]=(t[e]=='0')?'1':'0';

printf("Errorneous data : %s\n",t);

crc();

for (e=0;(e<N-1)&&(cs[e]!='1');e++);

if(e<N-1) printf("Error detected.");

else printf("No Error Detected.");

getch();

Output:
Enter poly : 1011101
Generating Polynomial is : 10001000000100001
Modified t[u] is : 10111010000000000000000
Checksum is : 1000101101011000
Final Codeword is : 10111011000101101011000
Test Error detection 0(yes) 1(no) ? : 0
Enter position where you want to insert error : 3
Errorneous data : 10101011000101101011000
Error detected.

Enter poly : 1011101

Generating Polynomial is : 10001000000100001
Modified t[u] is : 10111010000000000000000
Checksum is : 1000101101011000
Final Codeword is : 10111011000101101011000
Test Error detection 0(yes) 1(no) ? : 1
No Error Detected.
 Title

Write a Program to simulate Distance vector routing

Objective Implementation of Distance Vector Routing

Pre-requisite Knowledge of Windows and Linux.

Routing algorithm is a part of network layer software which is responsible for deciding
which output line an incoming packet should be transmitted on. If the subnet uses datagram
internally, this decision must be made anew for every arriving data packet since the best
route may have changed since last time. If the subnet uses virtual circuits internally, routing
decisions are made only when a new established route is being set up. The latter case is
sometimes called session routing, because a rout remains in force for an entire user session
(e.g., login session at a terminal or a file).
Routing algorithms can be grouped into two major classes: adaptive and nonadaptive.
Nonadaptive algorithms do not base their routing decisions on measurement or estimates of
current traffic and topology. Instead, the choice of route to use to get from I to J (for all I and
J) is compute in advance, offline, and downloaded to the routers when the network ids
booted. This procedure is sometime called static routing.
Adaptive algorithms, in contrast, change their routing decisions to reflect changes in the
topology, and usually the traffic as well. Adaptive algorithms differ in where they get
information (e.g., locally, from adjacent routers, or from all routers), when they change the
routes (e.g., every ∆T sec, when the load changes, or when the topology changes), and what
metric is used for optimization (e.g., distance, number of hops, or estimated transit time).
Two algorithms in particular, distance vector routing and link state routing are the most
popular. Distance vector routing algorithms operate by having each router maintain a table
(i.e., vector) giving the best known distance to each destination and which line to get there.
These tables are updated by exchanging information with the neighbors.
The distance vector routing algorithm is sometimes called by other names, including the
distributed Bellman-Ford routing algorithm and the Ford-Fulkerson algorithm, after the
researchers who developed it (Bellman, 1957; and Ford and Fulkerson, 1962). It was the
original ARPANET routing algorithm and was also used in the Internet under the RIP and in
early versions of DECnet and Novell’s IPX. AppleTalk and Cisco routers use improved
distance vector protocols.
In distance vector routing, each router maintains a routing table indexed by, and containing
one entry for, each router in subnet. This entry contains two parts: the preferred out going line
to use for that destination, and an estimate of the time or distance to that destination. The
metric used might be number of hops, time delay in milliseconds, total number of packets
queued along the path, or something similar.

Program

#include<stdio.h>
struct node
{
unsigned dist[20];
unsigned from[20];
}rt[10];
int main()
{
int costmat[20][20];
int nodes,i,j,k,count=0;
printf("\nEnter the number of nodes : ");
scanf("%d",&nodes);//Enter the nodes
printf("\nEnter the cost matrix :\n");
for(i=0;i<nodes;i++)
{
for(j=0;j<nodes;j++)
{
scanf("%d",&costmat[i][j]);
costmat[i][i]=0;
rt[i].dist[j]=costmat[i][j];//initialise the distance equal to cost
matrix rt[i].from[j]=j;
}
}
do
{
 count=0;
for(i=0;i<nodes;i++)//We choose arbitary vertex k and we calculate the
direct distance from the node i to k using the cost matrix
//and add the distance from k to node j
for(j=0;j<nodes;j++)
for(k=0;k<nodes;k++)
if(rt[i].dist[j]>costmat[i][k]+rt[k].dist[j])
{//We calculate the minimum distance
rt[i].dist[j]=rt[i].dist[k]+rt[k].dist[j];
rt[i].from[j]=k;
count++;
}
}while(count!=0);
for(i=0;i<nodes;i++)
{
printf("\n\n For router %d\n",i+1);
for(j=0;j<nodes;j++)
{
printf("\t\nnode %d via %d Distance %d ",j+1,rt[i].from[j]+1,rt[i].dist[j]);
}
}
printf("\n\n");
getch();
}
/*
Output:
Enter the number of nodes :
3
Enter the cost matrix :
027
201
710
For router 1
node 1 via 1 Distance 0
node 2 via 2 Distance 2
node 3 via 3 Distance 3
For router 2
node 1 via 1 Distance 2
node 2 via 2 Distance 0
node 3 via 3 Distance 1
For router 3
node 1 via 1 Distance 3
node 2 via 2 Distance 1
node 3 via 3 Distance 0
*/
Experiment No : 8

Title Write a program to simulate Link state routing.

Simulate Link state routing.
Objective

Pre-requisite Knowledge of functions of Network layers

Algorithm/ 1. Create cost matrix C[ ][ ] from adjacency matrix adj[ ][ ]. C[i][j] is the cost of going from
vertex i to vertex j. If there is no edge between vertices i and j then C[i][j] is infinity.
Theory
2. Array visited[ ] is initialized to zero.
for(i=0;i<n;i++)
visited[i]=0;
3. If the vertex 0 is the source vertex then visited[0] is marked as 1.
4. Create the distance matrix, by storing the cost of vertices from vertex no. 0 to n-1 from
the source vertex 0.
for(i=1;i<n;i++)
distance[i]=cost[0][i];
Initially, distance of source vertex is taken as 0. i.e. distance[0]=0;
5. for(i=1;i<n;i++)
– Choose a vertex w, such that distance[w] is minimum and visited[w] is 0.
Mark visited[w] as 1.
– Recalculate the shortest distance of remaining vertices from the source.
– Only, the vertices not marked as 1 in array visited[ ] should be considered
for recalculation of distance. i.e. for each vertex v
if(visited[v]==0)
distance[v]=min(distance[v],
distance[w]+cost[w][v])

Program #include<stdio.h>

#include<conio.h>

#define INFINITY 9999

#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnode);

int main()

int G[MAX][MAX],i,j,n,u;

printf("Enter no. of vertices:");

scanf("%d",&n);

printf("\nEnter the adjacency matrix:\n");

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

for(j=0;j<n;j++)

scanf("%d",&G[i][j]);

printf("\nEnter the starting node:");

scanf("%d",&u);

dijkstra(G,n,u);

return 0;

void dijkstra(int G[MAX][MAX],int n,int startnode)

int cost[MAX][MAX],distance[MAX],pred[MAX];

int visited[MAX],count,mindistance,nextnode,i,j;

//pred[] stores the predecessor of each node

//count gives the number of nodes seen so far

//create the cost matrix

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

for(j=0;j<n;j++)

if(G[i][j]==0)
 cost[i][j]=INFINITY;

else

cost[i][j]=G[i][j];

//initialize pred[],distance[] and visited[]

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

distance[i]=cost[startnode][i];

pred[i]=startnode;

visited[i]=0;

distance[startnode]=0;

visited[startnode]=1;

count=1;

while(count<n-1)

mindistance=INFINITY;

//nextnode gives the node at minimum distance

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

if(distance[i]<mindistance&&!visited[i])

mindistance=distance[i];

nextnode=i;

}
 //check if a better path exists through nextnode

visited[nextnode]=1;

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

if(!visited[i])

if(mindistance+cost[nextnode][i]<distance[i])

distance[i]=mindistance+cost[nextnode][i];

pred[i]=nextnode;

count++;

//print the path and distance of each node

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

if(i!=startnode)

printf("\nDistance of node%d=%d",i,distance[i]);

printf("\nPath=%d",i);

j=i;

do

j=pred[j];

printf("<-%d",j);

}while(j!=startnode);

}
 }

Sample Enter no. of vertices:3

Output
Enter the adjacency matrix:

1101

1000

1111

Enter the starting node:1

Distance of node0=1

Path=0<-1

Distance of node2=2

Path=2<-0<-1

Post Lab
Assignment
(If Any)

Title Write a program to simulate the stop- and-wait protocol.

Objectiv simulate the stop- and-wait protocol
e

Pre- Knowledge of functions of physical layer and data Link layer

requisite
Algorith Step 1: Start the program.
m/
Theor Step 2: Generate a random that gives the total number of frames to be
y transmitted.

Step 3: Transmit the first frame.

Step 4: Receive the acknowledgement for the first frame.

Step 5: Transmit the next frame

Step 6: Find the remaining frames to be sent.

 Step 7: If an acknowledgement is not received for a particular frame retransmit
that frame alone again.

Step 8: Repeat the steps 5 to 7 till the number of remaining frames to be send
becomes zero.

Step 9: Stop the program.

Progra #include<stdio.h>
m
#include<conio.h>
#include<stdlib.h>
void main()
{
int i,j,noframes,x,x1=10,x2;
clrscr();
for(i=0;i<200;i++)
rand();
noframes=rand()/200;
i=1;
j=1;
noframes = noframes / 8;

Sample
Output
printf("\ printf("\nsending frame %d",i);
n srand(x1++);
number
of x = rand()%10;
frames
}
is
%d",no printf("\nack for frame %d",j);
frames)
; noframes-=1;

getch(); i++;

while(n j++;
oframe }
s>0)
printf("\n end of stop and wait protocol");
{
getch();
printf("
}
\nsendi
ng
frame
%d",i); No of frames is 6

srand(x Sending frame 1

1++); Acknowledgement for frame 1
x= Sending frame 2
rand()
%10; Acknowledgement for frame 2
if(x%2 Sending frame 3
== 0)
{
for
(x2=1;
x2<2;
x2++)
{
printf(
"waitin
g for
%d
second
s\n",
x2);
sleep(x
2);
}
 Acknowledgement for frame 3
Sending frame 4
Acknowledgement for frame 4
Sending frame 5
Waiting for 1 second
Retransmitting frame 5
Acknowledgement for frame 5
Sending frame 6
Waiting for 1 second
Sending frame 6
Acknowledgement for frame 6
End of stop and wait protocol

Post Lab
Assignment
(If Any)
Experiment No : 10

Title Write a program to simulate the selective repeat protocol

To simulate the selective repeat protocol
Objective

Pre-requisite Knowledge of functions of physical layer and data Link layer

Algorithm / It may be used as a protocol for the delivery and acknowledgement of message units, or it
Theory may be used as a protocol for the delivery of subdivided message sub-units.

When used as the protocol for the delivery of messages, the sending process continues to
send a number of frames specified by a window size even after a frame loss. Unlike Go-
Back-N ARQ, the receiving process will continue to accept and acknowledge frames sent
after an initial error; this is the general case of the sliding window protocol with both
transmit and receive window sizes greater than 1.

The receiver process keeps track of the sequence number of the earliest frame it has not
received, and sends that number with every acknowledgement (ACK) it sends. If a frame
from the sender does not reach the receiver, the sender continues to send subsequent
frames until it has emptied its window. The receiver continues to fill its receiving window
with the subsequent frames, replying each time with an ACK containing the sequence
number of the earliest missing frame. Once the sender has sent all the frames in its
window, it re-sends the frame number given by the ACKs, and then continues where it
left off.

The size of the sending and receiving windows must be equal, and half the maximum
sequence number (assuming that sequence numbers are numbered from 0 to n−1) to avoid
miscommunication in all cases of packets being dropped. To understand this, consider the
case when all ACKs are destroyed. If the receiving window is larger than half the
maximum sequence number, some, possibly even all, of the packets that are resent after
timeouts are duplicates that are not recognized as such. The sender moves its window for
every packet that is acknowledged.

When used as the protocol for the delivery of subdivided messages it works somewhat
differently. In non-continuous channels where messages may be variable in length,
standard ARQ or Hybrid ARQ protocols may treat the message as a single unit.
Alternately selective retransmission may be employed in conjunction with the basic ARQ
mechanism where the message is first subdivided into sub-blocks (typically of fixed
length) in a process called packet segmentation. The original variable length message is
thus represented as a concatenation of a variable number of sub-blocks. While in standard
ARQ the message as a whole is either acknowledged (ACKed) or negatively
acknowledged (NAKed), in ARQ with selective transmission the ACK response would
additionally carry a bit flag indicating the identity of each sub-block successfully
received. In ARQ with selective retransmission of sub-divided messages each
retransmission diminishes in length, needing to only contain the sub-blocks that were
linked.

In most channel models with variable length messages, the probability of error-free
reception diminishes in inverse proportion with increasing message length. In other words
it's easier to receive a short message than a longer message. Therefore standard ARQ
techniques involving variable length messages have increased difficulty delivering longer
messages, as each repeat is the full length. Selective re-transmission applied to variable
length messages completely eliminates the difficulty in delivering longer messages, as
successfully delivered sub-blocks are retained after each transmission, and the number of
outstanding sub-blocks in following transmissions diminishes. Selective Repeat is
implemented in UDP transmission.

Step 1: Start the program.

Step 2: Generate a random that gives the total number of frames to be transmitted.
Step 3: Set the size of the window.
Step 4: Generate a random number less than or equal to the size of the current window
and identify the number of frames to be transmitted at a given time.
Step 5: Transmit the frames and receive the acknowledgement for the frames sent.
Step 6: Find the remaining frames to be sent.
Step 7: Find the current window size.
Step 8: If an acknowledgement is not received for a particular frame retransmit that frame
alone again.
Step 9: Repeat the steps 4 to 8 till the number of remaining frames to be send becomes
zero.
Step 10: Stop the program.
Program #include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void main()
{ int temp1,temp2,temp3,temp4,temp5,i,winsize=8,noframes,moreframes;
char c;
int reciever(int); int simulate(int); int nack(int);
clrscr();
temp4=0,temp1=0,temp2=0,temp3=0,temp5 = 0;
for(i=0;i<200;i++)

rand();
noframes=rand()/200;
printf("\n number of frames is
%d",noframes); getch();
moreframes=noframes;
while(moreframes>=0)
{ temp1=simulate(winsize);
winsize-=temp1;
temp4+=temp1;
if(temp4 >noframes)
temp4 = noframes;
for(i=noframes - moreframes;i<=temp4;i++)
printf("\nsending frame %d",i);
getch();
temp2=reciever(temp1);
temp3+=temp2;
if(temp3 > noframes)
temp3 = noframes;
temp2 = nack(temp1);
temp5+=temp2;
if (temp5 !=0)
{
printf("\n No acknowledgement for the frame %d",temp5);
getch();
for(i=1;i<temp5;i++)
;
printf("\n Retransmitting frame %d",temp5);
getch();
}
moreframes-=temp1;
if(winsize<=0)
winsize=8;
}
printf("\n end of sliding window protocol Selective Reject");
getch();
}
int reciever(int temp1)
{ int i;
for(i=1;i<100;i++)
rand(); i=rand()
%temp1; return i;
}
int nack(int temp1)
{ int i;
for(i=1;i<100;i++)
rand(); i=rand()
%temp1; return i;
} int simulate(int winsize)
{ int temp1,i;
for(i=1;i<50;i++)
temp1=rand();
if(temp1==0)
 temp1=simulate(winsize);
Sample
i = temp1%winsize;
Output
if(i==0)
return winsize;
else
return temp1%winsize;
}

Number of frames: 55
Sending frame 1
Sending frame 2
Sending frame 3
Sending frame 4
No Acknowledgement for the frame 2
Retransmitting frame 2
Sending frame 5
Sending frame 6
No Acknowledgement for the frame 2
Retransmitting frame 2
Sending frame 3

Post Lab Sending frame 4

Assignmen No Acknowledgement for the frame 4
t (If Any)
...
Sending frame 54
Sending frame 55
End of sliding window protocol
Experiment No : 11

Title Write a program to simulate LZW compression algorithm

To simulate LZW compression algorithm
Objective

Pre-requisite Knowledge of functions of physical layer and data Link layer

Algorithm / There are two categories of compression techniques, lossy and lossless. Whilst each
uses different techniques to compress files, both have the same aim: To look for duplicate
Theory
data in the graphic (GIF for LZW) and use a much more compact data representation.
Lossless compression reduces bits by identifying and eliminating statistical redundancy. No
information is lost in lossless compression. On the other hand, Lossy compression reduces
bits by removing unnecessary or less important information. So we need Data Compression
mainly because:
Ø Uncompressed data can take up a lot of space, which is not good for limited hard
drive space and internet download speeds.
Ø While hardware gets better and cheaper, algorithms to reduce data size also helps
technology evolve.
Ø Example: One minute of uncompressed HD video can be over 1 GB. How can we
fit a two-hour film on a 25 GB Blu-ray disc?
Lossy compression methods include DCT (Discreet Cosine Transform), Vector
Quantisation and Huffman coding while Lossless compression methods include RLE (Run
Length Encoding), string-table compression, LZW (Lempel Ziff Welch) and zlib. There
Exist several compression Algorithms, but we are concentrating on LZW.
What is Lempel–Ziv–Welch (LZW) Algorithm?
The LZW algorithm is a very common compression technique. This algorithm is typically
used in GIF and optionally in PDF and TIFF. Unix’s ‘compress’ command, among other
uses. It is lossless, meaning no data is lost when compressing. The algorithm is simple to
implement and has the potential for very high throughput in hardware implementations. It
is the algorithm of the widely used Unix file compression utility compress, and is used in
the GIF image format.
The Idea relies on reoccurring patterns to save data space. LZW is the foremost technique
for general purpose data compression due to its simplicity and versatility. It is the basis of
many PC utilities that claim to “double the capacity of your hard drive”.
 How does it work?
LZW compression works by reading a sequence of symbols, grouping the symbols into
strings, and converting the strings into codes. Because the codes take up less space than the
strings they replace, we get compression. Characteristic features of LZW includes,
Ø LZW compression uses a code table, with 4096 as a common choice for the number
of table entries. Codes 0-255 in the code table are always assigned to represent single bytes from the input
file.
Ø When encoding begins the code table contains only the first 256 entries, with the
remainder of the table being blanks. Compression is achieved by using codes 256 through 4095 to
represent sequences of bytes.
Ø As the encoding continues, LZW identifies repeated sequences in the data, and adds
them to the code table.
Ø Decoding is achieved by taking each code from the compressed file and translating
it through the code table to find what character or characters it represents.

Example: ASCII code. Typically, every character is stored with 8 binary bits, allowing up
to 256 unique symbols for the data. This algorithm tries to extend the library to 9 to 12 bits
per character. The new unique symbols are made up of combinations of symbols that
occurred previously in the string. It does not always compress well, especially with short,
diverse strings. But is good for compressing redundant data, and does not have to save the
new dictionary with the data: this method can both compress and uncompress data.
Implementation
The idea of the compression algorithm is the following: as the input data is being
processed, a dictionary keeps a correspondence between the longest encountered words and
a list of code values. The words are replaced by their corresponding codes and so the input
file is compressed. Therefore, the efficiency of the algorithm increases as the number of
long, repetitive words in the input data increases.

Program #include <stdio.h>

#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
/* -------- aux stuff ---------- */
void* mem_alloc(size_t item_size, size_t n_item)
{
size_t *x = calloc(1, sizeof(size_t)*2 + n_item * item_size);
x[0] = item_size;
x[1] = n_item;
return x + 2;
}
void* mem_extend(void *m, size_t new_n)
{
size_t *x = (size_t*)m - 2;
x = realloc(x, sizeof(size_t) * 2 + *x *
new_n); if (new_n > x[1])
memset((char*)(x + 2) + x[0] * x[1], 0, x[0] * (new_n - x[1]));
x[1] = new_n;
return x + 2;
}

inline void _clear(void *m)

{
size_t *x = (size_t*)m - 2;
memset(m, 0, x[0] * x[1]);
}
#define _new(type, n) mem_alloc(sizeof(type), n)
#define _del(m) { free((size_t*)(m) - 2); m = 0; }
#define _len(m) *((size_t*)m - 1)
#define _setsize(m, n) m = mem_extend(m, n)
#define _extend(m) m = mem_extend(m, _len(m) * 2)
/* ----------- LZW stuff -------------- */
typedef uint8_t byte;
typedef uint16_t ushort;
#define M_CLR 256 /* clear table marker */
#define M_EOD 257 /* end-of-data marker */
#define M_NEW 258 /* new code index */
/* encode and decode dictionary structures.
for encoding, entry at code index is a list of indices that follow current
one, i.e. if code 97 is 'a', code 387 is 'ab', and code 1022 is 'abc', then
dict[97].next['b'] = 387, dict[387].next['c'] = 1022, etc. */
typedef struct {
ushort next[256];
} lzw_enc_t;
/* for decoding, dictionary contains index of whatever prefix index plus trailing
byte. i.e. like previous example,
dict[1022] = { c: 'c', prev: 387 },
dict[387] = { c: 'b', prev: 97 },
dict[97] = { c: 'a', prev: 0 }
the "back" element is used for temporarily chaining indices when
resolving a code to bytes
*/
typedef struct {
ushort prev, back;
byte c;
} lzw_dec_t;
byte* lzw_encode(byte *in, int max_bits)
{
int len = _len(in), bits = 9, next_shift = 512;
ushort code, c, nc, next_code = M_NEW;
lzw_enc_t *d = _new(lzw_enc_t, 512);
if (max_bits > 15) max_bits = 15;
if (max_bits < 9 ) max_bits = 12;
byte *out = _new(ushort, 4);
int out_len = 0, o_bits = 0;
uint32_t tmp = 0;
inline void write_bits(ushort x) {
 tmp = (tmp << bits) | x;
o_bits += bits;
if (_len(out) <= out_len) _extend(out);
while (o_bits >= 8) {
o_bits -= 8;
out[out_len++] = tmp >> o_bits;
tmp &= (1 << o_bits) - 1;
}
}
//write_bits(M_CLR);
for (code = *(in++); --len; ) {
c = *(in++);
if ((nc = d[code].next[c]))
code = nc;
else {
write_bits(code);
nc = d[code].next[c] = next_code++;
code = c;
}
/* next new code would be too long for current table */
if (next_code == next_shift) {
/* either reset table back to 9 bits */
if (++bits > max_bits) {
/* table clear marker must occur before bit reset */
write_bits(M_CLR);
bits = 9;
next_shift = 512;
next_code = M_NEW;
_clear(d);
} else /* or extend table */
_setsize(d, next_shift *= 2);
}
}
 write_bits(code);
write_bits(M_EOD);
if (tmp) write_bits(tmp);
_del(d);
_setsize(out, out_len);
return out;
}
byte* lzw_decode(byte *in)
{
byte *out = _new(byte, 4);
int out_len = 0;
inline void write_out(byte c)
{
while (out_len >= _len(out)) _extend(out);
out[out_len++] = c;
}
lzw_dec_t *d = _new(lzw_dec_t, 512);
int len, j, next_shift = 512, bits = 9, n_bits = 0;
ushort code, c, t, next_code = M_NEW;
uint32_t tmp = 0;
inline void get_code() {
while(n_bits < bits) {
if (len > 0) {
len --;
tmp = (tmp << 8) | *(in++);
n_bits += 8;
} else {
tmp = tmp << (bits - n_bits);
n_bits = bits;
}
}
n_bits -= bits;
code = tmp >> n_bits;
 tmp &= (1 << n_bits) - 1;
}
inline void clear_table() {
_clear(d);
for (j = 0; j < 256; j++) d[j].c = j;
next_code = M_NEW;
next_shift = 512;
bits = 9;
};
clear_table(); /* in case encoded bits didn't start with M_CLR */
for (len = _len(in); len;) {
get_code();
if (code == M_EOD) break;
if (code == M_CLR) {
clear_table();
continue;
}
if (code >= next_code) {
fprintf(stderr, "Bad sequence\n");
_del(out);
goto bail;
}
d[next_code].prev = c = code;
while (c > 255) {
t = d[c].prev; d[t].back = c; c = t;
}
d[next_code - 1].c = c;
while (d[c].back) {
write_out(d[c].c);
t = d[c].back; d[c].back = 0; c = t;
}
write_out(d[c].c);
if (++next_code >= next_shift) {
 if (++bits > 16) {
/* if input was correct, we'd have hit M_CLR before this */

fprintf(stderr, "Too many bits\n"); _del(out);

goto bail;
}
_setsize(d, next_shift *= 2);
}
}
/* might be ok, so just whine, don't be drastic */
if (code != M_EOD) fputs("Bits did not end in EOD\n", stderr);
_setsize(out, out_len);
bail: _del(d);
return out;
}
int main()
{
int i, fd = open("unixdict.txt", O_RDONLY);
if (fd == -1) {
fprintf(stderr, "Can't read file\n");
return 1;
};
struct stat st;
fstat(fd, &st);
byte *in = _new(char, st.st_size);
read(fd, in, st.st_size);
_setsize(in, st.st_size);
close(fd);
printf("input size: %d\n", _len(in));
byte *enc = lzw_encode(in, 9);
printf("encoded size: %d\n", _len(enc));
byte *dec = lzw_decode(enc);
printf("decoded size: %d\n", _len(dec));
 for (i = 0; i < _len(dec); i++)
if (dec[i] != in[i]) {
printf("bad decode at %d\n", i);
break;
}
if (i == _len(dec)) printf("Decoded ok\n");
_del(in);
_del(enc);
_del(dec);
return 0;
}
Sample
Output
Size of the file size should be reducing.
Post Lab
Assignmen
t (If Any)
Experiment No : 12

Title Installation and working of Remote Desktop and Telnet

To Installation and working of Remote Desktop and Telnet
Objective

Pre-requisite Knowledge of functions of physical layer and data Link layer

Algorithm/
You must first enable the Remote Desktop feature on your office computer so that you
Theory can control it remotely from home computer. You must be logged on as an
administrator or a member of the Administrators group to enable Remote Desktop on
your Windows XP Professional-based computer.

To setup your office computer to use Remote Desktop (only need to do it once)

1. Right click on the My Computer icon and select Properties on the menu.

2. On the Remote tab, select the Allow users to connect remotely to this
computer check box, as shown below.

3. Ensure that you have the proper permissions to connect to your computer
 remotely, and click OK.

4. Leave your computer running and connected to the company network with
Internet access. Lock your computer, and leave your office.

Note: If you're running Windows XP Service Pack 2 (SP2) and you have enabled
Remote Desktop, Windows Firewall will be automatically configured to allow Remote
Desktop connections to your computer. However, Remote Desktop will not work if
you have Windows Firewall configured to allow no exceptions. To allow exceptions in
Windows Firewall, in the control panel open the Security Center, click Windows
Firewall and uncheck Don't allow exceptions.

How to use PuTTY to start a Remote Desktop Connection?

PuTTY is a free implementation of Telnet and SSH for Win32 and Unix platforms. For
more information please visit here.

If you do not have PuTTY installed, you may download putty.exe to c:\windows

At your home PC, to build ssh tunnel and run RDC to connect your home PC to
office PC:

1. Open an Command Windows with Start -> Run... -> "cmd"

2. Run putty -L 9001:officepc:3389 gatekeeper.cs.hku.hk (where officepc is the

hostname of office PC) and login with your CS account and password

3. Run mstsc /v:localhost:9001

4. Login your officepc on the remote desktop then.

How to use ssh to start a Remote Desktop Connection?

To create a new Remote Desktop Connection:

1. Setup your SSH port forwarding as described in Access Network Services

Behind a Firewall with SSH Port Forwarding.

2. Open Remote Desktop Connection. (Click Start, point to Programs or All

Programs, point to Accessories, point to Communications, and then click Remote Desktop
Connection.)
 3. In Computer, type the computer name for your computer running Windows
XP Professional that has Remote Desktop enabled and for which you have Remote
Desktop permissions.

4. Click Connect. The Log On to Windows dialog box appears.

5. In the Log On to Windows dialog box, type your user name, password, and
domain (if required), and then click OK. The Remote Desktop window will open
and you will see the desktop settings, files, and programs that are on your office
computer. Your office computer will remain locked. Nobody will be able to work at
your office computer without a password, nor will anyone see the work you are
doing on your office computer remotely.

Note: To change your connection settings, (such as screen size, automatic logon
information, and performance options), click Options before you connect.

To log off and end the session

1. In the Remote Desktop Connection window, click Start, and then click Shut
Sample Down. The Shutdown Windows dialog box appears.
Output
2. In the drop-down menu, select Log Off <username>, and then click OK.
Post Lab
Assignmen
t (If Any) Successfully Connected two system using Telnet Connection.