Sliding Window Protocol

The sliding window is a technique for sending multiple frames at a time. It controls the data packets between the two devices where reliable and gradual delivery of data frames is needed. It is also used in TCP (Transmission Control Protocol).

In this technique, each frame has sent from the sequence number. The sequence numbers are used to find the missing data in the receiver end. The purpose of the sliding window technique is to avoid duplicate data, so it uses the sequence number.

Types of Sliding Window Protocol: Sliding window protocol has two types

1.Go-Back-N ARQ

2.Selective Repeat ARQ

1.Go-Back-N ARQ

The Go-Back-N Automatic Repeat Request protocol is also known as the Go-Back-N ARQ protocol. A sliding window method finds use in this data link layer protocol. In the event of corruption or loss of frames, all subsequent frames must be sent again.

In this protocol, the sender window size is N. The size of the receiver window is always one.

In the event of transmission of a corrupted frame, the receiver cancels it. The receiver does not accept a corrupted frame. The sender sends the correct frame again when the timer expires.

d. Accordingly, the receiver sends the acknowledgement for the 1st frame, and upon receiving that, the sender slides the window again and sends the next frame. This process keeps on happening until all the frames are sent successfully.

Gate Question :

Answer : 16

Answer: 17

2.Selective Repeat ARQ

Selective Repeat ARQ (Selective Repeat Automatic Repeat Request) is another name for Selective Repeat ARQ. A sliding window method is used in this data link layer protocol. If the frame has fewer errors, Go-Back-N ARQ works well. However, if the frame contains a lot of errors, sending the frames again will result in a lot of bandwidth loss. As a result, we employ the Selective Repeat ARQ method. 

The size of the sender window is always equal to the size of the receiver window in this protocol. The sliding window’s size is always greater than 1.

Difference between Stop and Wait, Go-Back-N, and Selective Repeat

Elementary data link protocols

Protocols in the data link layer are designed so that this layer can perform its basic functions: 

• Framing
• Error control 
• Flow control

Framing is the process of dividing bit - streams from physical layer into data frames whose size ranges from a few hundred to a few thousand bytes. 

Error control mechanisms deals with transmission errors and retransmission of corrupted and lost frames. 

Flow control regulates speed of delivery and so that a fast sender does not drown a slow receiver.

Types of Data Link Protocols

Data link protocols can be broadly divided into two categories, depending on whether the transmission channel is noiseless or noisy.

Simplex Protocol

The Simplex protocol is hypothetical protocol designed for unidirectional data transmission over an ideal channel, i.e. a channel through which transmission can never go wrong. It has distinct procedures for sender and receiver. The sender simply sends all its data available onto the channel as soon as they are available its buffer. The receiver is assumed to process all incoming data instantly. It is hypothetical since it does not handle flow control or error control.

Stop – and – Wait Protocol

Stop – and – Wait protocol is for noiseless channel too. It provides unidirectional data transmission without any error control facilities. However, it provides for flow control so that a fast sender does not drown a slow receiver. The receiver has a finite buffer size with finite processing speed. The sender can send a frame only when it has received indication from the receiver that it is available for further data processing.

Efficiency of Stop and Wait Protocol :In which the sender sends one packet and waits for the receiver to acknowledge and then it will send the next packet. In case if the acknowledgement is not received, the sender will retransmit the packet. This is the simplest one and easy to implement. but the main disadvantage is the efficiency is very low.

Where 

Tt(data) : Transmission delay for Data packet (Tt = L/BW)

Tp(data) : propagation delay for Data packet (Tp = d/v)

Tq: Queuing delay

Tpro: Processing delay

Tt(ack): Transmission delay for acknowledgment

Tp(ack) : Propagation delay for acknowledgment  

Total time taken to send one packet is given by 

Total time = Tt(data) + Tp + Tq + Tpro + Tt(ack) + Tp
Total time = Tt(data) + Tp + 0 + 0 + Tt(ack) + Tp [since Queuing delay Tq = 0 and Processing delay Tpro = 0 ]

Total time = Tt(data) + Tp + 0 + 0 + 0 + Tp [Since, Tt(ack) << Tt(data).

So we can neglect Tt(ack)]

Hence Total time = Tt + 2 * Tp 

We know that the Efficiency (η),

= Useful time / Total cycle time.

= Tt / (Tt + 2*Tp)

= 1 / (1+2*(Tp/Tt))

= 1 / (1+2*a) where, a = Tp / Tt 

Throughput : Number of bits send per second, which is also known as Effective Bandwidth or Bandwidth utilization.

Throughput=Length of frame/Total Cycle time

= L/(Tt + 2*Tp)

= ((L/BW)*BW)/(Tt + 2*Tp)

= Tt/(Tt + 2*Tp) * BW

= 1/(1 + 2a) * BW

Hence, Throughput = η * BW where BW : BandWidth,  L : Size of Data packet 

Factors affecting Efficiency:

n = 1/(1 + 2*(Tp/Tt)

= 1/(1 + 2*(d/v)*(BW/L))

where,

d = distance between source and receiver 

v = velocity 

Lets see an example. Example: Given,

Tt = 1ms   

Tp = 2ms   

Bandwidth = 6 Mbps

Efficiency(η) 

= 1/(1 + 2*a)

= 1/(1 + 2*(2/1))

= 1/5  

= 20 %

Throughput 

= η * BW

= (1/5) * 6 

= 1.2 Mbps

Stop – and – Wait ARQ

Stop – and – wait Automatic Repeat Request (Stop – and – Wait ARQ) is a variation of the above protocol with added error control mechanisms, appropriate for noisy channels. The sender keeps a copy of the sent frame. It then waits for a finite time to receive a positive acknowledgement from receiver. If the timer expires or a negative acknowledgement is received, the frame is retransmitted. If a positive acknowledgement is received then the next frame is sent.

Go – Back – N ARQ

Go – Back – N ARQ provides for sending multiple frames before receiving the acknowledgement for the first frame. It uses the concept of sliding window, and so is also called sliding window protocol. The frames are sequentially numbered and a finite number of frames are sent. If the acknowledgement of a frame is not received within the time period, all frames starting from that frame are retransmitted.

Selective Repeat ARQ

This protocol also provides for sending multiple frames before receiving the acknowledgement for the first frame. However, here only the lost frames are retransmitted, while the good frames are received and buffered.

Error detection and correction

Errors

When bits are transmitted over the computer network, they are subject to get corrupted due to interference and network problems. The corrupted bits leads to spurious data being received by the destination and are called errors.

Types of Errors:Errors can be of three types, namely single bit errors, multiple bit errors, and burst errors.

Error Control :Error control can be done in two ways

Error Detection: Error detection involves checking whether any error has occurred or not. The number of error bits and the type of error does not matter.

Error Correction: Error correction involves as certaining the exact number of bits that has been corrupted and the location of the corrupted bits.

For both error detection and error correction, the sender needs to send some additional bits along with the data bits. The receiver performs necessary checks based upon the additional redundant bits. If it finds that the data is free from errors, it removes the redundant bits before passing the message to the upper layers.

Error Detection Techniques

There are three main techniques for detecting errors in frames: Parity Check, Checksum, and Cyclic Redundancy Check (CRC).

Parity Check
The parity check is done by adding an extra bit, called parity bit to the data to make a number of 1s either even in case of even parity or odd in case of odd parity.While creating a frame, the sender counts the number of 1s in it and adds the parity bit in the following way

In case of even parity: If a number of 1s is even then parity bit value is 0. If the number of 1s is odd then parity bit value is 1.

In case of odd parity: If a number of 1s is odd then parity bit value is 0. If a number of 1s is even then parity bit value is 1.

On receiving a frame, the receiver counts the number of 1s in it. In case of even parity check, if the count of 1s is even, the frame is accepted, otherwise, it is rejected. A similar rule is adopted for odd parity check.

The parity check is suitable for single bit error detection only.

Checksum : In this error detection scheme, the following procedure is applied Data is divided into fixed sized frames or segments. The sender adds the segments using 1’s complement arithmetic to get the sum. It then complements the sum to get the checksum and sends it along with the data frames. The receiver adds the incoming segments along with the checksum using 1’s complement arithmetic to get the sum and then complements it. If the result is zero, the received frames are accepted; otherwise, they are discarded.

Cyclic Redundancy Check (CRC)
Cyclic Redundancy Check (CRC) involves binary division of the data bits being sent by a predetermined divisor agreed upon by the communicating system. The divisor is generated using polynomials.
Here, the sender performs binary division of the data segment by the divisor. It then appends the remainder called CRC bits to the end of the data segment. This makes the resulting data unit exactly divisible by the divisor.
The receiver divides the incoming data unit by the divisor. If there is no remainder, the data unit is assumed to be correct and is accepted. Otherwise, it is understood that the data is corrupted and is therefore rejected.

CRC Flow Diagram:

Transmitted Data:

Received Data:

2.Example - The data bit to be sent is [100100], and the polynomial equation is [x3+x2+1].

Data bit - 100100
Divisor (k) - 1101 (Using the given polynomial)
Appending Zeros - (k-1) > (4-1) > 3
Dividend - 100100000

Error Correction Techniques
Error correction techniques find out the exact number of bits that have been corrupted and as well as their locations. There are two principle ways

Backward Error Correction (Retransmission) −  If the receiver detects an error in the incoming frame, it requests the sender to retransmit the frame. It is a relatively simple technique. But it can be efficiently used only where retransmitting is not expensive as in fiber optics and the time for retransmission is low relative to the requirements of the application.

Forward Error Correction −  If the receiver detects some error in the incoming frame, it executes error-correcting code that generates the actual frame. This saves bandwidth required for retransmission. It is inevitable in real-time systems. However, if there are too many errors, the frames need to be retransmitted.

The four main error correction codes are
Hamming Codes
Binary Convolution Code
Reed – Solomon Code
Low-Density Parity-Check Code

Hamming Codes: In Computer Networks, Hamming code is used for the set of error-correction codes which may occur when the data is moved from the sender to the receiver. 

The hamming method corrects the error by finding the state at which the error has occurred.

Redundant Bits
Redundant bits are extra binary bits that are generated and added to the information-carrying bits of data transfer to ensure that no bits were lost during the data transfer. The redundancy bits are placed at certain calculated positions to eliminate the errors and the distance between the two redundancy bits is called "Hamming Distance".

Error Correction Code − This is the relationship between data bits and redundancy bits to correct a single-bit error. 

A-frame consists of M data bits and R redundant bits. Suppose the total length of the frame be N (N=M+R). An N-bit unit containing data and the check bit is often referred to as an N-bit codeword.
The following formula is used to find the number of redundant bits.
Number of single-bit errors = M + R
Number of states for no error = 1
So, the number of redundant bits (R) that represent all states (M+R+1) must satisfy −
2^𝑅 ≥ 𝑀 + 𝑅 + 1
where R = Redundant bit, and M = data bit.

Steps to find the Hamming Code −
The hamming method uses the extra parity bits to allow the identification of a single-bit error.
Step 1 − First write the bit positions starting from 1 in a binary form (1, 10, 11,100, etc.)
Step 2 − Mark all the bit positions that are powers of two as parity bits (1, 2, 4, 8, 16, 32, 64, etc.)
Step 3 − All other bit positions are for the data to be encoded using (3, 5, 6, 7, 9, 10 and 11, etc.)
Each parity bit calculates the parity for some of the bits in the code word. The position of the parity determines the sequence of bits that it alternatively checks and skips.
Position 1 − Check 1 bit, then skip 1 bit, check 1 bit and then skip 1 bit and so on (Ex − 1,3,5,7,11, etc.)
Position 2 − Check 2 bit, then skip 2 bit, check 2 bit, then skip 2 bit (Ex − 2,3,6,7,10,11,14,15, etc.)
Position 4 − Check 4 bit, then skip 4 bit, check 4 bit, then skip 4 bit (Ex − 4, 5, 6, 7, 12, 13, 14, 15, etc.)
Position 8 − Check 8 bit, then skip 8 bit, check 8 bit, then skip 8 bit (Ex − 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31).
Note − Set the parity bit 1 if the total number of 1s in the positions it checks odd or set the parity bit 0 if the total number of 1's in the positions it checks even.

Example 
Construct the even parity Hamming code word for a data byte 10001101.
The number (D7 - DO 10001101 ) of bits is 8.
The value of r is calculated as −

2^𝑅 ≥ 𝑀 + 𝑅 + 1
⇒ 2^4 ≥ 8 + 4 + 1
⇒ 16 ≥ 8 + 4 + 1 (True)

⇒ 16 ≥ 13 (True)

Therefore, the number of redundancy bits = 4 i.e P1,P2,P4,P8 parity bits are added to the data byte 10001101

Bit Postions:

1    2    3    4    5    6    7    8    9    10    11    12

P1  P2  D7  P4  D6  D5  D4  P8  D3   D2   D1   D0  

DATA LINK LAYER:Design issues

Syllabus of unit 2:

DATA LINK LAYER: Design issues, Error detection and correction, Elementary data link protocols, Sliding window protocols.

RANDOM ACCESS: ALOHA, CSMA/CD, CSMA/CA, Controlled access, Channelization, Wired LAN: IEEE Standards, Standard Ethernet, Wireless LAN:IEEE802.11, ATM: architecture,layers 

The data link layer in the OSI (Open System Interconnections) Model, is in between the physical layer and the network layer. This layer converts the raw transmission facility provided by the physical layer to a reliable and error-free link.The main functions and the design issues of this layer are

• Providing services to the network layer
• Framing
• Error Control
• Flow Control

Providing Services to the Network Layer

In the OSI Model, each layer uses the services of the layer below it and provides services to the layer above it. The data link layer uses the services offered by the physical layer.The primary function of this layer is to provide a well defined service interface to network layer above it.

Network LayerThe types of services provided can be of three types −

1.Unacknowledged connectionless service

2. Acknowledged connectionless service

3. Acknowledged connection - oriented service

Framing

The data link layer encapsulates each data packet from the network layer into frames that are then transmitted.A frame has three parts, namely −

1. Frame Header

2. Payload field that contains the data packet from network layer

3. Trailer

Error Control

The data link layer ensures error free link for data transmission. The issues it caters to with respect to error control are −

• Dealing with transmission errors
• Sending acknowledgement frames in reliable connections
• Retransmitting lost frames
• Identifying duplicate frames and deleting them
• Controlling access to shared channels in case of broadcasting

Flow Control

The data link layer regulates flow control so that a fast sender does not drown a slow receiver. When the sender sends frames at very high speeds, a slow receiver may not be able to handle it. There will be frame losses even if the transmission is error-free. 

The two common approaches for flow control are −
1. Feedback based flow control
2. Rate based flow control

Casting & Network Topology

Casting: Transmitting the data in the form of packets over the internet is called casting.

Types of Castings

The different types of casting are as follows −
Unicast − Transmitting data from one host to another host (one-one)
Broad cast − Transmitting data from one host to many host (one-all)
Multicast − Transmitting data from one host to a particular group of host (one-many).

Unicast
Transmitting data from one source host to one destination host is called a unicast. It is called as a one to one transmission.

For example − source Host IP Address 192.168.20.1 sending data to destination Host having IP Address 192.122.140.34

Packet = Data + Source Host IP + Destination Host IP

                              192.168.20.1      192.122.140.34

Broadcast
Transmitting data from one source host to all other hosts present in the same or other network is called broadcast. It is called a one to all transmission.

Broadcast is classified into two types, which are as follows −
Limited Broadcast − Transmitting data from one source host to all other hosts present in the same network is called a limited broadcast.

In Limited Broad casting if the destination address is 255.255.255.255 then the packet will be sent to all the hosts in the network.
Limited Broadcast address of any network
=255.255.255.255
= 11111111.11111111.11111111.11111111
For example − If the source IP address is 11.1.2.3 sending data to all other hosts present in the same network, then the destination address is 255.255.255.255.

Packet = Data + Source Host IP + Destination Host IP
                                 11.1.2.3              255.255.255.255

Direct Broadcast − Transmitting data from source host to all other hosts present in different networks then it is called as direct broadcast.

In direct broadcast Host ID bits are all set to 1, Network ID is the IP address where all destination hosts are present.
For example − Source IP address is 11.1.2.3  sending data to all other nodes present at different network having IP address 24.0.0.0
Therefore source address= 11.1.2.3
Destination address= 24.255.255.255

Packet = Data + Source Host IP + Destination Host IP
                                 11.1.2.3            24.255.255.255
Multicast
Transmitting data from one source host to a particular group of hosts that are interested in receiving the data is called Multicast. It is also called one to many transmissions.

For example − Sending messages on whatsapp to particular groups, video conferences, and sending email to groups of people.

Network topology:

Network topology is the layout of a network. It consists of two parts; 

physical and logical. 

The physical part describes the physical layout of a network while the logical part describes how the data flows in that network. 

Both, physical and logical parts are also known as the physical topology and the logical topology.

Physical part (topology) + Logical part (topology) = Network topology

Types Of Network Topologies:

BUS Topology

Bus topology is a network type in which every computer and network device is connected to single cable. When it has exactly two endpoints, then it is called Linear Bus topology.

    

When a computer transmits data in this topology, all computers see that data over the wire, but only that computer accepts the data to which it is addressed. It is just like an announcement that is heard by all but answered only by the person to whom the announcement is made.

For example, if in the above network, PC-A sends data to the PC-C then all computers of the network receive this data but only the PC-C accepts it. The following image shows this process.

  

If PC-C replies, only the PC-A accepts the return data. The following image shows this process.

Features of Bus Topology

1.It transmits data only in one direction.

2.Every device is connected to a single cable

Advantages of Bus Topology

1.It is cost effective.

2.Cable required is least compared to other network topology.

3.Used in small networks.

4.It is easy to understand.

5.Easy to expand joining two cables together.

Disadvantages of Bus Topology

1.Cables fails then whole network fails.

2.If network traffic is heavy or nodes are more the performance of the network decreases.

3.Cable has a limited length.

4.It is slower than the ring topology.

RING Topology

It is called ring topology because it forms a ring as each computer is connected to another computer, with the last one connected to the first. Exactly two neighbours for each device.

                            

Features of Ring Topology

1.A number of repeaters are used for Ring topology with large number of nodes, because if someone wants to send some data to the last node in the ring topology with 100 nodes, then the data will have to pass through 99 nodes to reach the 100th node. Hence to prevent data loss repeaters are used in the network.

2.The transmission is unidirectional, but it can be made bidirectional by having 2 connections between each Network Node, it is called Dual Ring Topology.

3.In Dual Ring Topology, two ring networks are formed, and data flow is in opposite direction in them. Also, if one ring fails, the second ring can act as a backup, to keep the network up.

4.Data is transferred in a sequential manner that is bit by bit. Data transmitted, has to pass through each node of-hg  the network, till the destination node.

Advantages of Ring Topology

1.Transmitting network is not affected by high traffic or by adding more nodes, as only the nodes having tokens can transmit data.

2.Cheap to install and expand

Disadvantages of Ring Topology

1.Troubleshooting is difficult in ring topology.

2.Adding or deleting the computers disturbs the network activity.

3.Failure of one computer disturbs the whole network.

STAR Topology

In this topology, all computers connect to a centralized networking device. Usually, a networking switch or a Hub (in earlier days) is used as the centralized device. Each computer in the network uses its own separate twisted pair cable to connect to the switch. Twisted pair cable uses RJ-45 connectors on both ends.

The following image shows an example of the star topology.

                                        

To transmit data, the star topology uses the same concept which the bus topology uses. It means, if you build a network using the star topology, then that network will use the bus topology to transmit the data.

Features of Star Topology

1.Every node has its own dedicated connection to the hub.

2.Hub acts as a repeater for data flow.

3.Can be used with twisted pair, Optical Fibre or coaxial cable.

Advantages of Star Topology

1.Fast performance with few nodes and low network traffic.

2.Hub can be upgraded easily.

3.Easy to troubleshoot.                                                                              

4.Easy to setup and modify.                                                                       

5.Only that node is affected which has failed, rest of the nodes can work smoothly.

Disadvantages of Star Topology

1.Cost of installation is high.

2.Expensive to use.

3.If the hub fails then the whole network is stopped because all the nodes depend on the hub.

4.Performance is based on the hub that is it depends on its capacity

MESH Topology

It is a point-to-point connection to other nodes or devices. All the network nodes are connected to each other. Mesh has n(n-1)/2 physical channels to link n devices.

                           

Required connections = n * (n-1)/2

Here, n is the number of end devices or locations.

For example, to make a fully meshed network of 4 end devices, we need 4*(4-1)/2 = 6 connections.

There are two techniques to transmit data over the Mesh topology, they are :

1.Routing

2.Flooding

MESH Topology: Routing

In routing, the nodes have a routing logic, as per the network requirements. Like routing logic to direct the data to reach the destination using the shortest distance. Or, routing logic which has information about the broken links, and it avoids those node etc. We can even have routing logic, to re-configure the failed nodes.

MESH Topology: Flooding

In flooding, the same data is transmitted to all the network nodes, hence no routing logic is required. The network is robust, and the its very unlikely to lose the data. But it leads to unwanted load over the network.

 

Types of Mesh Topology

1.Partial Mesh Topology : In this topology some of the systems are connected in the same fashion as mesh topology but some devices are only connected to two or three devices.

2.Full Mesh Topology : Each and every nodes or devices are connected to each other.

Features of Mesh Topology

1.Fully connected.

2.Robust.

3.Not flexible.

Advantages of Mesh Topology

1.Each connection can carry its own data load.

2.It is robust.

3.Fault is diagnosed easily.

4.Provides security and privacy.

Disadvantages of Mesh Topology

1.Installation and configuration is difficult.

2.Cabling cost is more.

3.Bulk wiring is required.

TREE Topology

It has a root node and all other nodes are connected to it forming a hierarchy. It is also called hierarchical topology. It should at least have three levels to the hierarchy.

                         

Features of Tree Topology

1.Ideal if workstations are located in groups.

2.Used in Wide Area Network.

Advantages of Tree Topology

1.Extension of bus and star topologies.

2.Expansion of nodes is possible and easy.

3.Easily managed and maintained.

4.Error detection is easily done.

Disadvantages of Tree Topology

1.Heavily cabled.

2.Costly.

3.If more nodes are added maintenance is difficult.

4.Central hub fails, network fails.

HYBRID Topology

This topology is a mix of two or more topologies. For example, there are two networks; one is built from the star topology and another is built from the bus topology. If we connect both networks to build a single large network, the topology of the new network will be known as the hybrid topology.

You are not restricted to the bus and star topologies. You can combine any topology with another topology. In modern network implementations, the hybrid topology is mostly used to mix the wired network with the wireless network.

The following image shows an example of the hybrid network topology.

  

Features of Hybrid Topology

•It is a combination of two or topologies

•Inherits the advantages and disadvantages of the topologies included

Advantages of Hybrid Topology

•Reliable as Error detecting and trouble shooting is easy.

•Effective.

•Scalable as size can be increased easily.

•Flexible.

Disadvantages of Hybrid Topology

•Complex in design.

•Costly

Line Configuration in Computer Networks

Line Configuration in Computer Networks

A Network is nothing but a connection made through connection links between two or more devices. Devices can be a computer, printer or any other device that is capable to send and receive data. There are two ways to connect the devices :
1.Point-to-Point connection
2.Multipoint connection

Point-To-Point Connection

It is a protocol which is used as a communication link between two devices. It is simple to establish. The most common example for Point-to-Point connection (PPP) is a computer connected by telephone line. We can connect the two devices by means of a pair of wires or using a microwave or satellite link.

Example: Point-to-Point connection between remote control and Television for changing the channels.

  

MultiPoint Connection

It is also called Multidrop configuration. In this connection two or more devices share a single link.

There are two kinds of Multipoint Connections :

If the links are used simultaneously between many devices, then it is spatially shared line configuration.

If user takes turns while using the link, then it is time shared (temporal) line configuration.