Error Detection and Correction

Now imagine the received data has 7th bit changed from 1 to 0.

Single-bit error

The receiver takes the transmission and recalculates four new data using the same set of bits used by the sender plus the relevant parity (r) bit for each set.

Error detection

Ø  Then it assembles the new parity values into a binary number in order of r position (r8,r4,r2,r1).

Ø  This step gives us the binary number 0111(7 in decimal) which is the precise location of the bit in error.

Ø  Once the bit is identified, the receiver can reverse its value and correct the error.

Hamming Distance

     One of the central concepts in coding for error control is the idea of the Hamming distance.

Ø  The Hamming distance between two words (of the same size) is the number of differences between the corresponding bits. The Hamming distance between two words x and y is d(x, y).

Ø  The Hamming distance can be found by applying the XOR operation on the two words and count the number of 1’s in the result.

Ø  In a set of words, the minimum Hamming distance is the smallest Hamming distance between all possible pairs. We use dmin to define the minimum Hamming distance in a coding scheme. 

Error Correction

Error Correction can be handled in two ways

1.     When an error is discovered, the receiver can have the sender to retransmit the entire data unit.

2.     A receiver can use an error correcting code, which automatically correct certain errors.

Error correcting codes are more sophisticated than error-detection codes and require more redundancy bits.

In single bit error detection only two states are sufficient.

1) error

2) no error

Two states are not enough to detect an error but not to correct it.

Redundancy Bits

Ø  To calculate the number of redundancy bit(r) required to correct a given number of data bits (m), we must find a relationship between m and r.

Ø  Add m bits of data with r bits. The length of the resulting code is m+r.

Data and Redundancy bits

Ø  If the total number of bits are m+r, then r must be able to indicate at least m+r+1 different states. r bits can indicate 2^r different states. Therefore, 2^r must be equal to or greater than m+r+1

2^r >=m+r+1

Ø  For example if the value of m is 7 the smallest r value that can satisfy this equation is 4.

 Relationship between data and redundancy bits

Number of Data Bits (m)	Number of redundancy Bits(r)	Total bits (m+r)
1	2	3
2	3	5
3	3	6
4	3	7
5	4	9
6	4	10
7	4	11

Hamming Code

R.W. Hamming provides a practical solution for the error correction.

Positioning the Redundancy Bits

For example, a seven-bit ASCII code requires four redundancy bits that can be added to the end of the data or intersperse with the original data bits. These redundancy bits are placed in positions 1, 2, 4 and 8. We refer these bits as r1, r2, r3 and r4

Position of redundancy bits in Hamming code

The combination used to calculate each of the four r values for a seven-bit data sequence are as follows

Ø  The r1 bit is calculated using all bits positions whose binary representation include a 1 in the rightmost position

Ø  r2 is calculated using all bit position with a 1 in the second position and so on

                    r1: bits 1,3,5,7,9,11

                    r2: bits 2, 3, 6, 7, 10, 11

                    r3: bits 4, 5, 6, 7

                    r4: bits 8, 9, 10, 11

Redundancy bits calculation

Calculating the r values

Ø  Place each bit of the original character in its appropriate position in the 11-bit unit.

Ø  Calculate the even parities for the various bit combination.

Ø  The parity value for each combination is the value of the corresponding r bit.

For example,

Ø  The value of r1 is calculated to provide even parity for a combination of bits 3,5,7,9 and 11.

Ø  The value of r2 is calculated to provide even parity with bits 3, 6, 7, 10 and 11.

Ø  The value of r3 is calculated to provide even parity with bits 4,5,6 and 7.

Ø  The value of r4 is calculated to provide even parity with bits 8,9,10 and 11.

Cyclic Redundancy Check

Ø  It uses small number of redundant bits to detect errors.

Ø  Divisor is calculated by the polynomial functions under two conditions

a.    It should not be divisible by x

b.   It should be divisible by x+1

8     Consider the original message as M(x) – n+1 bits

9     Divisor C(x) – K bits

10  Original sent message = M(x) + k-1 bits

Steps

Ø  Append k-1 zeros with M(x) – P(x)

Ø  Divide P(x) by C(x)

Ø  Subtract the remainder from T(x)

Ø  Subtraction is made by making XOR operation

Eg:     100100 by 1101

CS2302-COMPUTERNETWORKS Unit 1

UNIT I

Network architecture – layers – Physical links – Channel Access on links – Hybrid multiple access techniques – Issues in the data link layer – Framing – Error correction and detection – Link-level flow control

Introduction

Computer Network: Definition

          Collection of autonomous computers interconnected by single technology.

Connectivity

          Connectivity occurs between two computers through physical medium like coaxial cable or an optical fiber.

                             Physical Medium – Link

                             Computers  -        Nodes

          When a physical link occurs between a pair of nodes then it is referred as point-to-point.

          When more than two nodes share a single physical link then it is referred as Multiple access.

    Data communication between the nodes is done by forwarding the data from one link to another. The systematic way of organizing these forwarding nodes form a switched network.

Two common types of switched network are

Ø  Circuit switched – e.g. Telephone System

Ø  Packet switched – e.g. Postal System

Packet Switched Network

          In this network nodes send discrete blocks of data to each other. These blocks can be called as packet or message.

Store and forward strategy:

          This network follows this technique. It means “Each node receives a complete packets over the link, stores in internal memory and then forwards to next node”.

Circuit Switched Network

          It first establishes a circuit across the links and allows source node to send stream of bits across this circuit to the destination node

The representation of network is given by cloud symbol

Cloud represents the network

Nodes inside the cloud (Switches) – Implement the network

Nodes outside the cloud (host) -        Use the network

Internetwork

Set of independent network are interconnected to form inter network or internet. Node that is connected to two or more network is called router or gateway. It is responsible for forwarding data between the networks.

Addressing

          The final requirement is that each node must be able to say which of the other node it wants to communicate with.

          This is done by assigning address to each node. when a source node wants to deliver message to destination node, it specifies the address of destination node.

          Switches and Routers use this address to decide how to forward the message. This process based on address is called Routing.

          Unicast – sending message to single node.

          Broadcast – Sending message to all the nodes on the network.

          Multicast – Sending message to some subnet not to all.

Resource Sharing

          Pblm: How do several hosts share the same link when they all want to use it at the same time?

Sol: Multiplexing – System resources are shared among multiple users

Methods:

1.   Synchronous Time Division Multiplexing(STDM)

Divide time into equal sized quanta

2.   Frequency Division Multiplexing(FDM)

Transmit each flow at different frequency

                        3. Statistical Multiplexing

First two methods are limited in 2 ways

Ø  If one flow does not have data to send then its time quantum remains idle, even the other flow has data to transmit.

Ø  No of flows are fixed and known ahead of time, it cannot be resized.

 Statistical methods combine the ideas of both STDM and FDM

Ø  Data from each flow is transmitted on demand so no idle quantum

Ø  It defines upper bound on size of data and it is referred as packet.

Common communication patterns

                   Communication between a pair of processes is done by request / reply basis. The process which sends request is referred as client and the one which honors the request is referred as server.

          This can be done using channels. Two types of channels are

Ø  Request / Reply channels

Ø  Message stream Channels

Reliability

          To get the reliable network, it is necessary to find how network fails.

          Three classes of failures

Ø  Bit error

Ø  Packet loss

Ø  Physical link and node failure

Network Architecture

          Networks do not remain fixed at single point in time, but it must evolve to accommodate changes based on the technologies on which they are based and demands made by application programmer.

          Network architecture guides the design and implementation of network. Two commonly used architecture are

Ø  OSI Architecture

Ø  Internet or TCP/IP architecture

Layering and Protocols

          When the system gets complex, the system designer introduces another level of abstraction. It defines unifying model with important aspects of the system, encapsulated this model in interface objects and hide it from users

          In network, abstraction leads to layering. Layering provides two nice features.

Ø  It decomposes the problem of building a network into more manageable components. Rather than implementing a monolithic piece of software that does everything implement several layers, each of which solves one part of the problem.

Ø  It provides more modular design. To add some new service, it is enough to modify the functionality at one layer, reusing the functions provided at all the other layers.

Protocols

A protocol is a set of rules that governs data communication. It defines what is communicated, how it is communicated, and when it is communicated. The key elements of a protocol are syntax, semantics and timing.

Each protocol defines two different interfaces.

Ø  Service interface - to the other objects on the same computer that want to use its communication services. This service interface defines the operations that local objects can perform on the protocol.

Ø  Peer interface - to its counterpart (peer) on another machine. It also defines the form and meaning of messages exchanged between protocol peers to implement the communication service.

Except at the hardware level, peer to peer communication is indirect.

We can represent these protocols as protocol graph. Nodes of the graph correspond to protocols, and the edges represent a depends-on relation.

 For example, the file access program on host 1 wants to send a message to its peer on host 2 using the communication service offered by protocol RRP. In this case, the file application asks RRP to send the message on its behalf. To communicate with its peer, RRP then invokes the services of HHP, which in turn transmits the message to its peer on the other machine. Once the message has arrived at protocol HHP on host 2, HHP passes the message up to RRP, which in turn delivers the message to the file application. In this particular case, the application is said to employ the services of the protocol stack RRP/HHP.

Encapsulation

         

          Control information must be added with the data to instruct the peer how to handle with the received message. It will be added into the header or trailer.

Header - Small data structure from few bytes to few kilobytes attached to the front of message.

Trailer – Information will be added at the end of the message

Payload or message body – Data send by the program

In this case data is encapsulated with new message created by

protocol at each level.In this example HHP encapsulates RRP’s message by attaching a header of its own. Then HHP sends the message to its peer over some network, and then when the message arrives at the destination host, it is processed in the opposite order.

Multiplexing and De-Multiplexing

The fundamental idea of packet switching is to multiplex multiple flows of data over a single physical link. This can be achieved by adding identifier to the header message. It is known as demultiplexing or demux key. It gives the address to which it has to communicate.

The messages are demultiplexed at the destination side. In some cases same demux key is used on both sides and in some cases different keys are used.