15CS46 - Data communication or computer networks 1_Module-3.ppt

Data Communication

1. ErrorDetectionandCorrection,Data
linkcontrol
Module-3
1

2. Datacanbecorruptedduringtransmission.
Forreliablecommunication,errorsmustbedetectedand
corrected.
Types of Error
Single-Bit Error
Burst Error
2

3. In a single-bit error, only one bit of a given data unit is
changed from 1 to 0 or from 0 to 1.
3

4. A burst error means that 2 or more bits in the
data unit have changed from 1 to 0 or from 0 to 1.
A burst error does not necessarily mean that the
errors occur in consecutive bits. The length of the burst is
measured from the first corrupted bit to the last corrupted
bit
4

5. Redundancy
Todetectorcorrecterrorsweneedtosend
redundantbitswithdata.
Theseredundantbitsareaddedbysenderand
removedbyreceiver.
Errordetectionusestheconceptofredundancy,
whichmeansaddingextrabitsfordetectingerrorsatthe
destination.
5

6. Redundancy
6

7. Detection Vs Correction
ErrorDetection:Processofobservingwhethererror
hasoccurredornot.Wearenoteveninterestedinthe
numberoferrors
Correction:Thecorrectionoferrorsismoredifficult
thanthedetection.Findingexactnumberofbitsthat
arecorruptedandtheirlocation.Thenumberoferrors
andsizeofthemessageareimportant
7

8. Forward Error correction
And Retransmission
Therearetwomethodsoferrorcorrection
Forwarderrorcorrection:Itistheprocessinwhichthe
receivertriestoguessthemessagebyusingredundant
bits.
Correctionbyretransmission:Itisatechniquein
whichthereceiverdetectstheoccurrenceofanerrorand
asksthesendertoresendthemessage.
8

9. Coding
Redundancy is achieved through various coding
scheme.
The sender adds redundant bits through a process
that creates a relationship b/w the redundant bits and
the actual data bits
The receiver checks the relationship b/w two sets
of bits to detect or correct the errors
Block coding and Convolution coding
9

10. Structure of encoder and decoder
10

11. Modular Arithmetic
•Only limited range of integers are used.
•Upper limit N is used-Modulus.
•Allowed integers are 0 to N-1
•In addition and subtraction –carry is ignored
•This operation is similar to XOR operation.
1 0 1 0
1 1 0 0
XOR 0 1 1 0
11

12. Block Coding
•Message is divided into blocks, each of kbits called
data words.
•r–redundant bits are added to each block to make
length n=k+r
•The resulting n-bit blocks are called code words.
12

13. Error Detection
Conditions:
•Thereceiverhaslistofvalidcodewords
•Theoriginalcodewordhaschangedtoaninvalidcodewords.
•Indetection,thereceiverneedstoknowonlythatthereceived
codewordisinvalid
13

14. Example
•Data wordsCode words
00 000
01 011
10 101
11 110
Assume sender encodes the data words 01 as 011 and
sends it to receiver, receiver received data 111. find
out error
14

15. Consider the following cases
1.The receiver receives 011. it is valid codeword. The
receiver extracts the data word 01 from it
2.The code word is corrupted during transmission and
111 is received. This is not a valid code word and it is
discarded
3.The code word is corrupted during transmission and
000 is received. This is a valid code word. The
receiver incorrectly extracts the data word 00
15

16. •An error-detecting code can detect only the
types of errors for which it is designed; other
types of errors may remain undetected.
16

17. Error Correction
•The receiver needs to find the original code word sent.
•We need more redundant bits for error correction than
for error detection
17

18. Table for error correction
Data words Codeword
00 00000
01 01011
10 10101
11 11110
The data word is 01. the sender create the code word
01011. the code word is corrupted during transmission and
01001 is received.
First, the receiver finds that the received code word is not
in the table. This means error has occurred.
18

19. The receiver uses the following strategy to guess the
correct data word
1.Compare the received code word with the first code word in
the table , the receiver decides that the first code word is not
the one that was sent because there are two different bits
2.By the same reasoning, the original code word can not be the
third or fourth in the table
3.The original code word must be the second one in the table
because this is the only one that differs from the received code
word by 1 bit. The receiver replaces 01001 with 01011 and
consult the table to find the data word 01
19

20. Hamming Distance
•Hamming distance between two words is the number
of difference between corresponding bits.
•ItcaneasilybefoundbyapplyingXORoperationon
thetwowordsandcountthenumberof1sinthe
result.
•Example:d(000,011)is2
20

21. Minimum Hamming Distance
•It is the smallest hamming distance between all possible pairs in a
set of words.
Find minimum hamming distance between code words:
00 000
01 011
10 101
11 110
d(000,011)=2; d(000,011)=2;
d(000,101)=2; d(000,110)=2
d(011,110)=2; d(101,110)=2
d
minis 2
21

22. 10.4Detection methods
22

23. Simple Parity Check Code
In this scheme , a k-bit data word is changed to an n-
bit code word where n=k+1.
This extra bit is called parity bit.
The parity bit selected to make the total number of 1‘s
in the codewordeven.
A simple parity check code is a single bit error
detecting code in which n=k+1 with d
min=2
23

24. Simple parity check code –Encoder
•The encoder uses a generator that takes a copy of a 4-
bit data word(a0,a1,a2,a3). It generates a parity bit r0
•Data word bits and the parity bit creates 5-bit
codeword
•The parity bit that is added makes the number of 1s
in the codeword even
•r0=a3+a2+a1+a1 Modulo2
24

25. Encoder and Decoder for simple parity check code
25

26. Simple parity check code –decoder
•The receiver receives a 5-bit word
•The checker performs addition on all 5 bits received.
The result is called syndrome-just 1 bit.
•The syndrome is 0 when the number of 1s in the
received codeword is even ;otherwise it is 1.
•s0=b3+b2+b1+b0+q0 modulo 2
26

27. Assume the sender sends the dataword 1011. the code word
created from this data word is 10111, which is sent to the
receiver.
1.Noerroroccurs,thereceivedcodewordis10111.thesyndromeis
0.thedatawordiscreated
2.Onesinglebiterrorchangesa1.thereceivedcodewordis10011.the
syndromeis1.nodatawordiscreated
3.Onesinglebiterrorchangesr0.thereceivedcodewordis10110.the
syndromeis1.nodatawordiscreated
4.Anerrorchangesr0andaseconderrorchangesa3.thereceivedcode
wordis00110.thesyndromeis0.thedataword0011iscreatedatthe
receiver
5.Threebitsa3,a2,a1arechangedbyerrors.Thereceivedcodewordis
01011.thesyndromeis1.thedatawordnotcreated.
Asimpleparitycheckcodecandetectanoddnumberoferrors
27

28. Calculation of row and column
parities
28

29. Single bit error
29
One

30. Two errors affects two parities
30

31. Three errors
31

32. Four Errors
32

33. Hamming Codes
•Minimum distance is 3. Expressed as C(n,k); where n=2
m
-1
•Data words : a3,a2,a1,a0 and Code words : a3,a2,a1,a0,r2,r1,ro
•r0=a2+a1+a0; r1=a3+a2+a1; r3=a1+a0+a3
•Checker in the decoder creates a 3-bit syndrome (s2s1s0); where
s0=b2+b1+b0+q0;s1=b3+b2+b1+q1;s3=b1+b0+b3+q2
Syndrome000001010011100101110111
ErrorNoneq0q1b2q2b0b3b1
33

34. Structure of Encoder and Decoder Hamming code
34

35. •r0=a2+a1+a0 modulo-2
•r1=a3+a2+a1 modulo-2
•r2=a1+a0+a3 modulo-2
•s0=b2+b1+b0+q0 modulo-2
•s1=b3+b2+b1+q1 modulo-2
•s2=b1+b0+b3+q2 modulo-2
35

36. Let us trace the path of three data word from the sender
to the destination
1.The data word 0100 becomes the code word 0100011. the
code word 0100011 is received. The syndrome is 000, the
final dataword is 0100
2.The data word 0111becomes the codeword 0011001 is
received. The syndrome is 011. according to table b2 is in
error. After flipping b2, the final data word is 0111
3.The dataword 1101 becomes the code word 1101000. the
code word 0001000 is received. The syndrome is 101, which
means that b0 is in error. After flipping b0, we get 0000, the
wrong data word. This shows that our code can not correct
two errors
36

37. Cyclic Codes
•In this scheme, if a code word is cyclically shifted, the
result is another codeword
•b1=a0;b2=a1;b3=a2;b4=a3;b5=a4;b6=a5;b0=a6.
37

38. CRC generator and checker
38

39. CRC
39

40. Design
40

41. Binary division in a CRC generator
41

42. Two cases –with /without Error
42

43. A polynomial and its representation
43

44. Table 10.1 Standard polynomials
Name Polynomial Application
CRC-8 x
8
+x
2
+x+1 ATM header
CRC-10 x
10
+x
9
+x
5
+x
4
+x
2
+1 ATM AAL
ITU-16 x
16
+x
12
+x
5
+ 1 HDLC
ITU-32
x
32
+x
26
+x
23
+x
22
+x
16
+x
12
+x
11
+x
10
+ x
8
+x
7
+x
5
+x
4
+x
2
+x +1
LANs
44

45. Checksum
45

46. The sender follows these steps:
•The message is divided into 16-bit words.
•The value of the checksum word is set to 0
•All words including the checksum are added using ones
complement addition
•The sum is complemented and becomes the checksum.
•The checksum is sent with the data.
Internet checksum
the internet has been using a 16-bit checksum. The
sender calculates the checksum by following these steps.
46

47. The receiver follows these steps:
•The message (including checksum) is divided into 16-
bit words.
•All words are added using one’s complement addition
•The sum is complemented and becomes the new
checksum.
•If the value of checksum is zero, the data are accepted:
otherwise, rejected.
47

48. Example 7
Suppose the following block of 16 bits is to be sent using a
checksum of 8 bits.
10101001 00111001
The numbers are added using one’s complement
10101001
00111001
------------
Sum 11100010
Checksum 00011101
The pattern sent is 10101001 00111001 00011101
48

49. Example 8
Now suppose the receiver receives the pattern sent in Example
7 and there is no error.
10101001 00111001 00011101
When the receiver adds the three sections, it will get all 1s,
which, after complementing, is all 0s and shows that there is no
error.
10101001
00111001
00011101
Sum 11111111
Complement 00000000 means that the pattern is OK.
49

50. Example 9
Nowsupposethereisabursterroroflength5thataffects4
bits.
101011111111100100011101
Whenthereceiveraddsthethreesections,itgets
10101111
11111001
00011101
PartialSum 111000101
Carry 1
Sum 11000110
Complement 00111001thepatterniscorrupted.
50

51. Letuscalculatethechecksumforatextof8characters
(“Forouzan”).Thetextneedstobedividedinto2-byte(16-
bit)words.Forexample,Fisrepresentedas0x46andois
representedas0x6F.
51

52. Figure 10.25 Example 10.23
52

53. Data Link Control
53

54. Data link control
Functions:
>Framing
>Flow control
>Error control
> Smooth and reliable transmission of frames
54

55. •Toimplementthesesetofdatalinkprotocols
areneeded
•Protocolsaresetofrulesthatneedtobe
implementedinsoftwareandrunbythetwo
nodesinvolvedindataexchangeatthedata
linklayer.
55

56. Framing
•Datatransmissioninphysicallayermeansmovingbitsin
theformofasignal
•Thedatalinklayerneedstopackbitsintoframes.
•Eachframesmustbedistinguishable
•Framingseparatesamessagefromonesourcetoa
destinationorfromothermessagestootherdestinations,
byaddingasenderaddressandadestinationaddress.
56

57. Frame types: Fixed size, Variable size
Fixed size
•No need for defining boundaries
•Size itself is the delimiter:
•Ex: ATM network frame
Variable size
•Need to define the end of the frame and the beginning of
the next.
57

58. Character Oriented protocols
•Datatobecarriedare8-bitcharactersfromacoding
system-ASCII
•Theheadernormallycarriesthesourceand
destinationaddressesandotherinformation
•Thetrailercarrieserrordetectionorerrorcorrection
redundantbits,arealsomultipleof8-bits.
•1-byteFlagisaddedatthebeginningandendofa
frame. 58

59. Character-orientedprotocol,stuffing,un-stuffing
59

60. The flag type
•Bytestuffingstrategyisused
–Aspecialbyteisaddedtothedatasectionofthe
framewhenthereisacharacterwiththesame
patternasflag.
–Thisbyteiscalledescapecharacter(ESC)
–WheneverthereceiverencounterstheESC
character;itremovesitfromdatasectionandtreats
thenextcharacterasdata
60

61. Bit-oriented protocols
•Thedatasectionofaframeisasequenceofbitstobe
interpretedbytheupperlayerastext,graphic,audio,
video,etc.
•Inadditiontoheader,delimiterisusedtoseparateone
framefromtheother
•Usuallythepatternflag01111110usedasthe
delimiter.
61

62. •Iftheflagpatternappearsinthedata,weneedto
informthereceiverthatthisisnottheendofthe
frame
•Wedothisbystuffing1singlebittopreventthe
patternfromlookinglikeaflag.Thestrategyiscalled
bitstuffing
•Inbitstuffing,ifa0andfiveconsecutive1bitsare
encountered,anextra0isadded.Thisextrastuffed
bitisremovedfromthedatabythereceiver
62

63. Flow and error control
•Flowcontrolreferstoasetofproceduresusedto
restricttheamountofdatathatthesendercansend
beforewaitingforacknowledgment.
•Errorcontrolinthedatalinklayerisbasedon
automaticrepeatrequest,whichistheretransmission
ofdata.
63

64. •Connectionless Protocol
•Inaconnectionlessprotocol,framesaresentfromonenodeto
thenextwithoutanyrelationshipbetweentheframes;each
frameisindependent.
•Theframesarenotnumberedandthereisnosenseofordering.
•Mostofthedata-linkprotocolsforLANsareconnectionless
protocols.
•Connection-Oriented Protocol
•In a connection-oriented protocol, a logical connection should
first be established between the two nodes (setup phase).
•the frames are numbered and sent in order.
•Ex: wired in LANs, Point to point protocols , Wireless LANs and
wired WANs
64

65. Protocols
•Noiseless Channel:
–Simplest,
–Stop and Wait
•Noisy Channel:
–Stop and Wait ARQ,
–Go-Back N ARQ,
–Selective Repeat ARQ
* ARQ: Automatic Repeat Request
65

66. Assumptions, Terminologies
•Data frames travel from one node(sender) to another
node (receiver)
•Some special frames are used: Acknowledgement and
Negative Acknowledgement frames
•These flow in the opposite direction for flow and
error control purposes
•Data flow in only one direction
•Piggybacking: ACK and NAK is included in the data
frames.
66

67. Noiseless channels-Simplest Protocol
•Ithasnoflowcontrolorerrorcontrol.
•ItisaUni-directionalprotocol.
•Atsenderside:getsdata,makesframe,sends
•Atreceiverside:receivesdata,extractsdata,
deliversdatatoN/Wlayer
67

68. •Thesendercannotsenduntilitsnetworklayerhasadata
tosend
•Thereceivercannotdeliveruntilaframearrives.
•Introducetheideaofeventsintheprotocol
•Theprocedureatthesendersiteisconstantlyrunning:no
actionuntilthereisarequestfromnetworklayer
•Theprocedureatthereceiversiteisconstantlyrunning:
noactionuntilnotificationfromphysicallayer
68

69. Simplest protocol
69

70. 70

71. Stop and Wait protocol
•Framesmustbestoredwhenreceivesframesfasterits
processingcapacity.
•Thereshouldbesomemethodtoslowdownthespeedof
sender.
•Theremustbefeedbackfromthereceivertothesender.
•Sendersendsoneframe,stopsuntilitreceives
confirmation,andthensendsnextframe.
71

72. Stop and wait protocol
72

73. Flow diagram of Simplest protocol
73

74. Noisy Channels-Stop and Wait Automatic Repeat Request
•ItaddsasimpleerrorcontrolmechanismtotheStop-and–Wait
protocol.
•Itneedstoaddredundancybitstodataframe.Whenframes
arrivesatthereceiversite,itischeckedandifitiscorrupted,itis
silentlydiscarded
•Thecorruptedandlostframesneedtoberesentinthisprotocol.
•Framesneedstobenumbered-usingsequencenumber.Sequence
numbermustbeknownsizetokeepframesizeminimum.
74

75. Sequence number
•The protocol specifies that frames need to be
numbered.
•A field is added to the data frame to hold the
sequence number of that frame
•We want to minimize the frame size, the smallest
range that provides unambiguous communication
•We want x and x+1 sequence numbers
75

76. •Sequencenumbersmustbesuitableforbothdataand
acknowledgementframes.Italsopreventsretainingof
duplicateframes.
•Numberedacknowledgmentsareneededifan
acknowledgmentisdelayedandthenextframeislost.
•Acknowledgementframealwaysannouncesnext
sequencestobereceivedfromsender.
•InStop-and–WaitARQ,theacknowledgementnumber
alwaysannouncesinmodulo2arithmeticthesequence
numberofthenextframeexpected.
76

77. 77

78. 78

79. HDLC
High Level Data Link Control (HDLC):
–It is bit-oriented protocol for communication over
point-to-point and multipoint links.
79

80. Configuration and Transfer Modes
•HDLC provides two common transfer modes that
can be used in different configurations:
–Normal Response Mode (NRM): the station
configuration is unbalanced. We have one
primary station and multiple secondary
stations. A primary station can send
commands, a secondary station can only
respond
–Asynchronous Balanced Mode(ABM): the
configuration is balanced.
80

81. NRM
NRM is used for both point-to-point and multiple point links.
81

82. ABM
The link is point-to-point and each station can function as
a primary and a secondary.
82

83. Frames
•HDLCdefinesthreetypesofframes:
–Informationframes(I-frames)
–Supervisoryframes(S-frames)
–Unnumberedframes(u-frames)
Eachtypeofframeservesasanenvelopeforthe
transmissionofadifferenttypeofmessage
I-Frame:usedtotransportuserdataandcontrol
informationrelatingtouserdata
S-Frame:usedonlytotransportcontrolinformation
U-Frame:Reservedforsystemmanagement
83

84. HDLC frame types
84

85. Fields
•Flag field:
–8-bit sequence, with bit pattern 01111110
–Identifies beginning and end of a frame
–Serves as a synchronization pattern for the receiver
•Address field:
–Contains address of the secondary station
–If primary created the frame: contains toaddress
–If secondary created the frame: contains fromaddress
–It can be one byte or several byte long depending on
network
–If the address field is only 1 byte, the last bit is always a
1. if the address is more than 1 byte, all bytes but the
last one will end with 0: only the last will end with 1
85

86. •Control field:
–1 or 2 byte segment of the frame used for flow and
error control
•Information field:
–Contains the user’s data from network layer or
management information
•FCS: (Frame check sequence)
–Used for error detection
–Can contain either a 2-or 4 byte ITU –T CRC.
86

87. Control field
•The control field determines the type of
frame and define its functionality
87

88. ControlfieldforI-frame
•Bit1:definesthetype.Ifitis0thenI
•Bit2-4:calledN(S)definesthesequencenumberofthe
frame
•Bit5:DualpurposebitP:Poll(0),Final(1)
–Pollframesentbyprimary,Finaltheframesentby
secondary.
•Bit6-8:calledN(R)correspondstothe
Acknowledgementnumber
88

89. Control field for S-frame
•S-framesareusedforflowanderrorcontrol.
Thisframedoesnothaveinformationfields.If
thefirst2bitsofthecontrolfieldis10,this
meanstheframeisanS-frame.
•Thelast3-bitscalledN(R),correspondstothe
acknowledgementnumberorNAK
•The2-bitscalledcodeisusedtodefinethetype
ofS-frameitself
89

90. •Receive ready(RR): the code subfields is 00, it is an RR
S-frame. This frame acknowledges the receipt of a safe
group of frames. The value of N(R) fields defines the
ACK number
•Receive not ready(RNR): the code subfields is 10, it is
an RNR S-frame. This frame acknowledges the receipt
of a frame or group of frames and it announces that the
receiver is busy and can not receive more frame. The
value of N(R) fields defines the ACK number
90

91. •Reject (REJ): the code subfields is 01, it is a REJ S-
frame. This is a NAK frame. It is a NAK that can be used
in Go-Back-N ARQ to improve the efficiency of the
process by informing the sender, before the sender time
expires. The value of N(R) fields defines the NCK
number
•Selective reject(SREJ): the code subfields is 11, it is an
SREJ S-frame. This is a NAK frame used in selective
reject instead of selective repeat ARQ. The value of N(R)
fields defines the NCK number
91

92. Control field for U-frames
Unnumbered frames are used to exchange
session management and control
information b/w connected devices.
U-frame codes are divided into two sections: a
two bit prefix before the P/F bit and a 3-bit
suffix after the P/F bit
92

93. Table 11.1 U-frame control command and response
Command/response Meaning
SNRM Set normal response mode
SNRME Set normal response mode (extended)
SABM Set asynchronous balanced mode
SABME Set asynchronous balanced mode (extended)
UP Unnumbered poll
UI Unnumbered information
UA Unnumbered acknowledgment
RD Request disconnect
DISC Disconnect
DM Disconnect mode
RIM Request information mode
SIM Set initialization mode
RSET Reset
XID Exchange ID
FRMR Frame reject
93

94. Point to Point Protocol
•Services:
–Defines the format of the frame to be exchanged between devices
–Defines how two devices can negotiate the establishment of the link
and exchange of data
–Defines how network layer data are encapsulated in the data link layer
–Defines how two devices can authenticate each other
–Provides multiple network layer services supporting a variety of
network layer protocols
–Provides connections over multiple links
–Provides network address configuration
•Missing :
–Does not provide flow control
–Very simple mechanism for error control
–Does not provide a sophisticated addressing mechanism
94

95. Framing
•Flag: Starts and ends with a 1-byte flag 01111110
•Address: Constant and set to 11111111
•Control: Set to constant value; 11000000
•Protocol: Defines what is being carried in the data field
•Payload field: Carries either user data or other information
•FCS: 2 or 4 byte standard CRC.
95

96. Transition phases
96

97. •Dead: In the dead phase the link is not being used
•Establish: Connection goes into this state when one of the
nodes starts the communication
•Authenticate: For authentication purpose; optional
•Network: Negotiation takes place in this phase.
•Open: Data transfer takes place
•Terminate: Connection is terminated in this phase.
97