DATA-LINK LAYER.ppt

Data Link Layer Design Issues
Error Detection and Correction
Elementary Data Link Protocols
Sliding Window Protocols

1. The Data Link Layer
Dr.T.Thendral, Assistant Professor,
SRCW

2. OBJECTIVE
•Data Link Layer Design Issues
•Error Detection and Correction
•Elementary Data Link Protocols
•Sliding Window Protocols
Dr.T.Thendral, Assistant Professor,
SRCW

3. Data Link Layer Design Issues
Dr.T.Thendral, Assistant Professor,
SRCW

4. Functions of the Data Link Layer
•Provide service interface to the network layer
•Dealing with transmission errors
•Regulating data flow
•Slow receivers not swamped by fast senders
Dr.T.Thendral, Assistant Professor,
SRCW

5. Functions of the Data Link Layer
Relationship between packets and frames.
Dr.T.Thendral, Assistant Professor,
SRCW

6. Services Provided to Network Layer
(a) Virtual Communication
(b) Actual Communication
Reference
Dr.T.Thendral, Assistant Professor,
SRCW

7. The data link layer can be designed to
offer various services
Three reasonable possibilities are
Unacknowledged connectionless service
Acknowledged connectionless service
Acknowledged connection-oriented
service
Dr.T.Thendral, Assistant Professor,
SRCW

8. Theroutingcodefrequentlywantsthe
jobdonerightwithreliableservice
Itdoesnotwanttobebotheredtoo
oftenwithpacketsthatgotlostonthe
way
Datalinkprotocol,showninthedotted
rectangle,tomake unreliable
communicationlineslookperfector,at
least,fairlygood
Dr.T.Thendral, Assistant Professor,
SRCW

9. Services Provided to Network Layer
Reference
Dr.T.Thendral, Assistant Professor,
SRCW

10. Framing
Toprovideservicetothenetworklayer,thedatalinklayermust
usetheserviceprovidedtoitbythephysicallayer
Thenumberofbitsreceivedmaybelessthan,equalto,ormore
than140thenumberofbitstransmitted,andtheymayhave
differentvalues.
Itisuptothedatalinklayertodetectand,ifnecessary,correct
errors
Sinceitistooriskytocountontimingtomarkthestartandendof
eachframe
FourMethods:
1.Charactercount
2.Flagbyteswithbytestuffing
3.Startingandendingflags,withbitstuffing
4.Physicallayercodingviolations
Dr.T.Thendral, Assistant Professor,
SRCW

11. Framing
A character stream. (a)Without errors. (b)With one error.
Character count
Dr.T.Thendral, Assistant Professor,
SRCW

12. •Thesecondframingmethodgetsaroundtheproblemof
resynchronizationafteranerrorbyhavingeachframestart
andendwithspecialbytes
•Recentyearsmostprotocolshaveusedthesamebyte,
calledaflagbyte,asboththestartingandendingdelimiter,
asFLAG.
•Ifthereceivereverlosessynchronization,itcanjustsearch
fortheflagbytetofindtheendofthecurrentframe
•Twoconsecutiveflagbytesindicatetheendofoneframeand
startofthenextone.
Flagbyteswithbytestuffing
Dr.T.Thendral, Assistant Professor,
SRCW

13. Framing
(a)A frame delimited by flag bytes.
(b)Four examples of byte sequences before and after stuffing.
ESCAPE BYTE (ESC)
FlagbyteswithBYTEstuffing
Dr.T.Thendral, Assistant Professor,
SRCW

14. a)Each frame begins and ends with a special bit pattern, 01111110 (in
fact, a flag byte).
b)Whenever the sender's data link layer encounters five consecutive
1s in the data, it automatically stuffs a 0 bit into the outgoing bit
stream
Startingandendingflags,withBITstuffing
Dr.T.Thendral, Assistant Professor,
SRCW

15. Framing
Bit stuffing
(a)The original data.
(b)The data as they appear on the line.
(c)The data as they are stored in receiver’s memory after destuffing.
Dr.T.Thendral, Assistant Professor,
SRCW

16. Error Detection and Correction
Error-Detecting Codes
•Parity bit
•Checksum
•https://www.youtube.com/watch?v=dbGJcinMJKM&t=0s
•Cyclic Redundancy Check Codes –CRC codes
•https://www.youtube.com/watch?v=PzNLmP5q8Ag
Error-Correcting Codes
•Hamming code
•https://www.youtube.com/watch?v=UNe3tF00gFQ
Dr.T.Thendral, Assistant Professor,
SRCW

17. Hamming Distance
•Some codes words are valid; others are invalid
•Hamming distance between two code words is number of bits
that must be flipped to change from one to the other
•If Hamming distance is d then d single bit errors needed to change one
word to the other
•Hamming distance of a code is the minimum Hamming
distance between two valid code words
•Detecting one single-bit error requires a distance 2 code; how
does this generalize?
•Correcting one single-bit error requires a distance 3 code; how
does this generalize?
Dr.T.Thendral, Assistant Professor,
SRCW

18. Parity Schemes
•Parity bits: choose a rule
•Even parity –each codeword has even number of 1’s
•Odd parity –each codeword has odd number of 1’s
•Always transmit according to the rule
•On receipt, if rule is violated, word is invalid
•Can also do “vertical parity” over whole block to achieve
single-bit error correction
Dr.T.Thendral, Assistant Professor,
SRCW

19. CRC Schemes
•CRC –Cyclic Redundancy Check or polynomial code
•Consider bits of a message to be coefficients of a polynomial
M(x)
•1011 –1x
3
+ 0x
2
+ 1x
1
+ 1x
0
•Of course real messages will be much longer and hence of higher degree
•Agree on a small-degree generator polynomial G(x) of degree r
•Note: G(x) has r digits to the right of the leading 1, hence r+1 total
•Divide x
r
M(x)by G(x)using modulo 2 division(no carries or
borrows) getting the remainder polynomial R(x)
•Transmit T(x)= x
r
M(x)-R(x); note that this has remainder 0
when divided by G(x)
•Receiver rejects frame if the remainder it computers is not 0
Dr.T.Thendral, Assistant Professor,
SRCW

20. Error-Detecting Codes
Calculation of the polynomial code checksum.
Dr.T.Thendral, Assistant Professor,
SRCW

21. CRC Properties
•Easily computed with feedback shift register hardware
•Detects any single-bit error
•Proper choice of G(x) gives detection of any two bit errors
•Proper choice of G(x) gives detection of any odd number of bit
errors
•Detects any burst error of length <= r; Why?
•Received message is T(x)+E(x) for some error polynomial E(x)
•If E(x) represents a burst of length <= r then it can be written as x
i
(F(x))
where the degree of F(x)is < r
•If G(x)has an x
0
term it can’t divide x
i
and no degree rpolynomial
divides a polynomial of degree < r
Dr.T.Thendral, Assistant Professor,
SRCW

22. Elementary Data-link Protocols
a)https://www.youtube.com/watch?v=v5zT-tp9P_I
b)Elementary Data Link Protocols
c)Physicallayer,datalinklayer,andnetworklayerareindependent
processesthatcommunicatebypassingmessagesbackandforth
d)Inmanycases,thephysicalanddatalinklayerprocesseswillbe
runningonaprocessorinsideaspecialnetworkI/Ochipandthe
networklayercodewillberunningonthemainCPU
Dr.T.Thendral, Assistant Professor,
SRCW

23. a)The data link layer has a number of specific functions it can carry
out. These functions include
b)1. Providing a well-defined service interface to the network layer.
c)2. Dealing with transmission errors.
d)3. Regulating the flow of data so that slow receivers are not
swamped by fast senders.
Dr.T.Thendral, Assistant Professor,
SRCW

24. Elementary Data Link Protocols
•An Unrestricted Simplex Protocol
•No buffer limits, no errors
•A Simplex Stop-and-Wait Protocol
•Add buffer limits
•A Simplex Protocol for a Noisy Channel
•Add channel errors
Dr.T.Thendral, Assistant Professor,
SRCW

25. Protocol Definitions
Continued 
Some definitions needed in the protocols to follow.
These are located in the file protocol.h.
Fivedatastructuresaredefinedthere:boolean,
seq_nr,packet,frame_kind,andframe
Dr.T.Thendral, Assistant Professor,
SRCW

26. Protocol
Definitions
(ctd.)
Some definitions
needed in the
protocols to follow.
These are located in
the file protocol.h.
Dr.T.Thendral, Assistant Professor,
SRCW

27. •Aframeiscomposedoffourfields:kind,seq,ack,andinfo,thefirst
threeofwhichcontaincontrolinformationandthelastofwhich
maycontainactualdatatobetransferred.
Dr.T.Thendral, Assistant Professor,
SRCW

28. An Unrestricted Simplex Protocol
•Asaninitialexamplewewillconsideraprotocolthatisassimpleas
itcanbe.
•Dataaretransmittedinonedirectiononly.
•Boththetransmittingandreceivingnetworklayersarealways
ready.
•Processingtimecanbeignored.Infinitebufferspaceisavailable.
•Andbestofall,thecommunicationchannelbetweenthedatalink
layersneverdamagesorlosesframes.
•Nosequencenumbersoracknowledgementsareusedhere,so
MAX_SEQisnotneeded.
•Theonlyeventtypepossibleisframe_arrival(i.e.,thearrivalofan
undamagedframe)
Dr.T.Thendral, Assistant Professor,
SRCW

29. Unrestricted
Simplex
Protocol
Dr.T.Thendral, Assistant Professor,
SRCW

30. A Simplex Stop-and-Wait Protocol
•Thecommunicationchannelisstillassumedtobeerrorfree
however,andthedatatrafficisstillsimplex.
•Themainproblemwehavetodealwithhereishowtopreventthe
senderfromfloodingthereceiverwithdatafasterthanthelatteris
abletoprocessthem
•Protocolsinwhichthesendersendsoneframeandthenwaitsforan
acknowledgementbeforeproceedingarecalledstop-and-wait
•Theonlydifferencebetweenreceiver1andreceiver2isthatafter
deliveringapackettothenetworklayer,receiver2sendsan
acknowledgementframebacktothesenderbeforeenteringthewait
loopagain.
Dr.T.Thendral, Assistant Professor,
SRCW

31. Simplex
Stop-and-
Wait
Protocol
Dr.T.Thendral, Assistant Professor,
SRCW

32. A Simplex Protocol for a Noisy
Channel
•Nowletusconsiderthenormalsituationofacommunication
channelthatmakeserrors.
•Framesmaybeeitherdamagedorlostcompletely.
•Considerthefollowingscenario:
•1.InnetworklayerpacketiscorrectlyreceivedatBandpassedto
thenetworklayeronB
•BsendsanacknowledgementframebacktoA.
•2.Theacknowledgementframegetslostcompletely.
•3.ThedatalinklayeronAeventuallytimesout.Nothaving
receivedanacknowledgement,it(incorrectly)assumesthatitsdata
framewaslostordamagedandsendstheframecontainingpacket1
again.
•4.TheduplicateframealsoarrivesatthedatalinklayeronB.In
otherwords,theprotocolwillfail.
Dr.T.Thendral, Assistant Professor,
SRCW

33. A Simplex Protocol for a Noisy Channel
A positive acknowledgement with retransmission protocol.
Continued 
Dr.T.Thendral, Assistant Professor,
SRCW

34. A Simplex Protocol for a Noisy Channel (ctd.)
A positive acknowledgement with retransmission protocol.
Dr.T.Thendral, Assistant Professor,
SRCW

35. Sliding Window Protocols
•Inthepreviousprotocols,dataframesweretransmittedinone
directiononly.Inmostpracticalsituations,thereisaneedfor
transmittingdatainbothdirections
•Onewayofachievingfull-duplexdatatransmissionistohavetwo
separatecommunicationchannelsanduseeachoneforsimplexdata
traffic
Dr.T.Thendral, Assistant Professor,
SRCW

36. Sliding Window Protocols
•Why?
•Efficiency –bandwidth*delay product
•Efficiency –when errors occur
•A One-Bit Sliding Window Protocol
•A Protocol Using Go Back N
•A Protocol Using Selective Repeat
Dr.T.Thendral, Assistant Professor,
SRCW

37. Sliding Window Protocols
A sliding window of size 1, with a 3-bit sequence number
•Initially
•After the first frame has been sent
•After the first frame has been received
•After the first acknowledgement has been received
Dr.T.Thendral, Assistant Professor,
SRCW

38. A One-Bit Sliding Window Protocol
Continued 
Dr.T.Thendral, Assistant Professor,
SRCW

39. A One-Bit Sliding Window Protocol (ctd.)
Dr.T.Thendral, Assistant Professor,
SRCW

40. A One-Bit Sliding Window Protocol (2)
Two scenarios for protocol 4. (a)Normal case. (b)Abnormal
case. The notation is (seq, ack, packet number). An asterisk
indicates where a network layer accepts a packet.
Dr.T.Thendral, Assistant Professor,
SRCW

41. A Protocol Using Go Back N
Pipelining and error recovery. Effect on an error when
(a)Receiver’s window size is 1.
(b)Receiver’s window size is large.Dr.T.Thendral, Assistant Professor,
SRCW

42. •Frames0and1arecorrectlyreceivedandacknowledged.
•Frame2,however,isdamagedorlost.
•Thesender,unawareofthisproblem,continuestosendframesuntil
thetimerforframe2expires.
•Thenitbacksuptoframe2andstartsalloverwithit,sending2,3,
4,etc.alloveragain.
Dr.T.Thendral, Assistant Professor,
SRCW

43. Sliding
Window
Protocol
Using Go
Back N
Continued 
Dr.T.Thendral, Assistant Professor,
SRCW

44. Sliding Window Protocol Using Go Back N
Continued 
Dr.T.Thendral, Assistant Professor,
SRCW

45. Sliding Window Protocol Using Go Back N
Continued 
Dr.T.Thendral, Assistant Professor,
SRCW

46. Sliding Window Protocol Using Go Back N
Dr.T.Thendral, Assistant Professor,
SRCW

47. Sliding Window Protocol Using Go Back N (2)
Simulation of multiple timers in software.
Dr.T.Thendral, Assistant Professor,
SRCW

48. A Sliding Window Protocol Using Selective Repeat
Continued 
Dr.T.Thendral, Assistant Professor,
SRCW

49. Continued 
A Sliding Window Protocol Using Selective Repeat (2)
Dr.T.Thendral, Assistant Professor,
SRCW

50. A Sliding Window Protocol Using Selective Repeat (3)
Continued 
Dr.T.Thendral, Assistant Professor,
SRCW

51. A Sliding Window Protocol Using Selective Repeat (4)
Dr.T.Thendral, Assistant Professor,
SRCW

52. A Sliding Window Protocol Using Selective Repeat (5)
(a)Initial situation with a window size seven.
(b)After seven frames sent and received, but not acknowledged.
(c)Initial situation with a window size of four.
(d)After four frames sent and received, but not acknowledged.
Dr.T.Thendral, Assistant Professor,
SRCW