Computer Networks Unit 2 UNIT II DATA-LINK LAYER & MEDIA ACCESS

by
Dr. S. Selvaganesan
[email protected]
CS8591 Computer Networks
UNIT II
DATA-LINK
LAYER & MEDIA
ACCESS

CS8591 COMPUTER NETWORKS -Syllabus

CS8591 COMPUTER NETWORKS -Books

UNIT II
DATA-LINK LAYER & MEDIA
ACCESS 9
Introduction–Link-LayerAddressing–
DLCServices–Data-LinkLayerProtocols
–HDLC–PPP-MediaAccessControl-
WiredLANs:Ethernet-WirelessLANs–
Introduction–IEEE802.11,Bluetooth–
ConnectingDevices.

DataLinkLayer
Thedatalinklayerisresponsibleformovingframesfromonehop
(node)tothenext.
Data Link Layer

FunctionsofDataLinkLayer
1.Framing:Itdividesthestreamofbitsreceivedfromnetworklayerinto
manageabledataunitscalledframes.
2.PhysicalAddressing:Itaddsaheadertotheframetodefinethesender
andreceiveroftheframe.
3.FlowControl:Thedatalinklayerimposesaflowcontrolmechanismto
avoidoverwhelmingthereceiver.
4.ErrorControl
•Itaddsreliabilitybyaddingmechanismstodetectandretransmit
damagedorlostframes.
•Italsousesamechanismtorecognizeduplicateframesbyaddingthe
trailertotheendoftheframe
5.AccessControl
•Itdetermineswhichdevicehascontroloverthelinkatanygiven
timewhentwoormoredevicesareconnectedtothesamelink.
Data Link Layer

Sub-layersofDataLinkLayer
1.LogicalLinkControl(LLC)Layer
•TheLogicalLinkControl(LLC)layerisoneoftwosub-layers
thatmakeuptheDataLinkLayeroftheOSImodel.
•TheLogicalLinkControllayercontrolsframe
synchronization,flowcontrolanderrorchecking.
2.MediaAccessControl(MAC)Layer
•TheMediaAccessControlLayerisoneoftwosub-layersthat
makeuptheDataLinkLayeroftheOSImodel.
•TheMAClayerisresponsibleformovingdatapacketstoand
fromoneNetworkInterfaceCard(NIC)toanotheracrossa
sharedchannel.
Data Link Layer

2.8
Figure: Relationshipof layers and addresses in TCP/IP

Physical Addressing

Network Adapter

Link-Layer Addressing
AddressResolutionProtocol
TheAddressResolutionProtocol(ARP)isusedtoassociate
alogicaladdresswithaphysicaladdress.
Onatypicalphysicalnetwork,suchasaLAN,eachdevice
onalinkisidentifiedbyaphysicalorstationaddress,
usuallyimprintedonthenetworkinterfacecard(NIC).
ARPisusedtofindthephysicaladdressofthenodewhen
itsInternetaddressisknown.
ReverseAddressResolutionProtocol
The Reverse Address Resolution
Protocol(RARP)allowsahosttodiscoveritsInternet
addresswhenitknowsonlyitsphysicaladdress.
Itisusedwhenacomputerisconnectedtoanetworkforthe
firsttimeorwhenadisklesscomputerisbooted.

Thetwomainfunctionsofthedatalink
layeraredatalinkcontrolandmedia
accesscontrol.
1.DataLinkControlfunctionsinclude
framing,flowanderrorcontrol,and
software-implementedprotocolsthat
providesmoothandreliable
transmissionofframesbetweennodes.
2.MediaAccessControl
Data Link Layer

Link Layer Services
Framing
Framinginthedatalinklayerseparatesamessagefromone
sourcetoadestination,orfromothermessagestoother
destinations,byaddingasenderaddressandadestination
address.
Thedestinationaddressdefineswherethepacketistogo;the
senderaddresshelpstherecipientacknowledgethereceipt.
Althoughthewholemessagecouldbepackedinoneframe,
thatisnotnormallydone.
Onereasonisthataframecanbeverylarge,makingflowanderror
controlveryinefficient.
Whenamessageiscarriedinoneverylargeframe,evena
single-biterrorwouldrequiretheretransmissionofthewhole
message.Whenamessageisdividedintosmallerframes,a
single-biterroraffectsonlythatsmallframe.

Link Layer Services
Fixed-SizeFraming
Framescanbeoffixedorvariablesize.
Infixed-sizeframing,thereisnoneedfor
definingtheboundariesoftheframes;the
sizeitselfcanbeusedasadelimiter.
Anexampleofthistypeofframingisthe
ATMwide-areanetwork,whichuses
framesoffixedsizecalledcells.

Link Layer Services
Variable-SizeFraming
Variable-sizeframingisprevalentinlocal
areanetworks.
Invariable-sizeframing,weneedawayto
definetheendoftheframeandthe
beginningofthenext.
Historically,twoapproacheswereusedfor
thispurpose:acharacter-orientedapproach
andabit-orientedapproach.

Link Layer Services
Framing
Totransmitframesoverthenode,itis
necessarytomentionstartandendofeach
frame.Therearetwotechniquestosolve
thisframe.
1.Byte-orientedProtocols(Character-
orientedProtocols)
2.Bit-orientedProtocols
3.Clock-basedFraming

Link Layer Services
FRAMING
Byte-orientedProtocols(Character-oriented
Protocols)
Eachframeistobeviewedasacollectionofbytes
(characters)ratherthanacollectionofbits.
Suchabyte-orientedapproachisexemplifiedbythe
BinarySynchronousCommunication(BISYNC)
ProtocolandtheDigitalDataCommunication
MessageProtocol(DDCMP).
ThemorerecentandwidelyusedPoint-to-Point
Protocol(PPP)providesanotherexampleofthis
approach.

Link Layer Services
FRAMING
Byte-orientedProtocols
SentinelApproach
TheBISYNCprotocolillustratesthesentinelapproachtoframing.
Itsframeformatisshowninthefigure.
ThebeginningofaframeisdenotedbysendingaspecialSYN
(synchronization)character.
Thedataportionoftheframeisthencontainedbetweenspecial
sentinelcharacters:STX(startoftext)andETX(endoftext).
TheSOH(startofheader)fieldservesmuchthesamepurposeas
theSTXfield.
TheframeformatalsoincludesafieldlabeledCRC(Cyclic
RedundancyCheck)thatisusedtodetecttransmissionerrors.

Link Layer Services

Link Layer Services
FRAMING-Byte-orientedProtocols
SentinelApproach
TheproblemwiththesentinelapproachisthattheETX
charactermightappearinthedataportionoftheframe.
BISYNCovercomesthisproblemby“escaping”theETX
characterbyprecedingitwithDLE(DataLinkEscape)
characterwheneveritappearsinthebodyofaframe;
TheDLEcharacterisalsoescaped(byprecedingitwithanin
extraDLE)intheframebody.Thisapproachiscalled
Characterstuffing.

Link Layer Services
Characterstuffing.

Link Layer Services
FRAMING-Byte-orientedProtocols
Point-to-PointProtocol
TheformatofPPPframeisgiveninfigure.
Theflagfieldhas01111110asstartingsequence.
Theaddressandcontrolfieldusuallycontaindefaultvalues.
Theprotocolisusedfordemultiplexing.
Theframepayloadsizecanbenegotiated,butitis1500bytesbydefault.
Thechecksumfieldiseither2(bydefault)or4byteslong.
ThePPPframeformatisunusualinthatseveralofthefieldsizesare
negotiatedratherthanfixed.
NegotiationisconductedbyaprotocolcalledLCP(LinkControl
Protocol).
LCPsendscontrolmessageencapsulatedinPPPframes–suchmessages
aredenotedbyanLCPidentifierinthePPPprotocol.

PPP

Link Layer Services
FRAMING-Byte-orientedProtocols
Byte-countingApproach
Thenumberofbytescontainedinaframecanbeincludedasafieldinthe
frameheader.DDCMPprotocolisusedforthisapproachasshownin
figure.
CLASSfield:Therearethreeclassesofmessage:Data,Control,and
Maintenance.
COUNTfieldspecifieshowmanybytesarecontainedintheframe’sbody.
Sometimes,countfieldwillbecorruptedduringtransmission,sothe
receiverwillaccumulateasmanybytesasthebadCOUNTfieldindicates
andthenusetheerrordetectionfieldtodeterminethattheframeisbad.
ThereceiverwillthenwaituntilitseesthenextSYNcharactertostart
collectingthebytesthatmakeupthenextframe.Thisissometimescalled
aframingerror.

Link Layer Services
Bit-orientedProtocols
HDLC
Inbit-orientedprotocols,framesareviewedasacollectionofbits.High-levelDataLinkControl
(HDLC)protocolisused.TheformatisshowninFigure.
HDLCdenotesboththebeginningandendofaframewiththedistinguishedbitsequence01111
110.
Thissequencemightappearanywhereinthebodyoftheframe,itcanbeavoidedbybitstuffing.
Onthesendingside,anytimefiveconsecutive1shavebeentransmittedfromthebodyofthe
message,thesenderinsertsa0beforetransmittingthenextbit.
Onthereceivingside,fiveconsecutive1sarrive,thereceivermakesitsdecisionbasedonthenext
bititsees.
Ifthenextbitisa0,itmusthavebeenstuffed,andsothereceiverremovesit.
Ifthenextbitisa1,thenoneofthetwothingsistrue
(i)Eitherthisistheend-of-framemarker
(ii)Anerrorhasbeenintroducedintothebitstream.
Bylookingatthenextbit,thereceivercandistinguishbetweenthesetwocases:
(i)Ifitseesa0(i.e.,thelasteightbitsithaslookedatare01111110),thenitistheend-of-frame
marker.
(ii)Ifitseesa1(i.e.,thelasteightbitsithaslooksatare01111111),thentheremusthavebeen
anerrorandthewholeframeisdiscarded.

HDLC
Toprovidetheflexibilitynecessarytosupportallthe
optionspossibleinthemodesandconfigurations,
HDLCdefinesthreetypesofframes:Information
frames(I-frames),supervisoryframes(S-frames),
andunnumberedframes(U-frames).Eachtypeof
frameservesasanenvelopeforthetransmissionofa
differenttypeofmessage.
I-framesareusedtotransportuserdataandcontrol
informationrelatingtouserdata(piggybacking).S-
framesareusedonlytotransportcontrolinformation.
U-framesarereservedforsystemmanagement.
InformationcarriedbyU-framesisintendedfor
managingthelinkitself.

HDLC
FrameFormat
EachframeinHDLCmaycontainuptosixfields,asshownin
thefollowingfigure,abeginningflagfield,anaddressfield,a
controlfield,aninformationfield,aframechecksequence
(FCS)field,andanendingflagfield.Inmultiple-frame
transmissions,theendingflagofoneframecanserveasthe
beginningflagofthenextframe.

HDLC

Byte-oriented Protocols and
Bit-oriented Protocols

Link Layer Services
Clock-basedFraming(SONET)
TheClock-BasedFramingapproachisexemplifiedbytheSynchronousOptical
Network(SONET)standard.
SONETisthedominantstandardforlongdistancetransmissionofdataoveroptical
networks.
AnSTS-1frameisusedinthismethod.TheframeformatofSTS-1isshownin
figure.
Itisarrangedasninerowsof90byteseach,andthefirst3bytesofeachroware
overhead,withtherestbeingavailablefordatathatisbeingtransmittedoverthelink.
Thefirst2bytesoftheframecontainaspecialbitpattern,andthesebytescanenable
thereceivertodeterminewheretheframestarts.
Thereceiverlooksforthespecialbitpatternconsistently,onceinevery810bytes,
sinceeachframeis9×90=810byteslong.

Link Layer Services
Clock-basedFraming(SONET)
TheSTS-NframeisconsistingofSTS-1frame,wherethebytesfromtheseframesare
interleaved.Thatis,abytefromthefirstframeistransmitted,andthenabytefromthe
secondframeistransmitted,andsoon.
PayloadfromtheseSTS-1framescanbelinkedtogethertoformalargerSTS-N
payload,suchalinkisdenotedSTS-3c.
Figure: Three STS-1 frames multiplexed onto one
STS-3c frame

Error Detection and Correction
Datacanbecorruptedduringtransmission.Forreliable
communication,errorsmustbedetectedandcorrected.
Typesoferrors
1.Single-bitError
2.BurstError

Error Detection and Correction
Single-bitError
Inasingle-biterror,onlyonebitinthedataunithas
changed.
0ischangedtoa1ora1toa0.
E.g. Data rate: 1 Mbps = 1 ×10
6
bps; Possibility = 1/ 10
6

Error Detection and Correction
BurstError
Abursterrormeansthat2ormorebitsinthedataunithave
changed.
Figureshowstheeffectofabursterroronadataunit.
Thelengthofburstismeasuredfromthefirstcorruptedtothe
lastcorruptedbit.Somebitsmaynothavebeencorrupted.
E.g.,Datarate=1Kbps;noise=1/100sec;
No.ofbitsaffected=1×10
3
×1/100

Error Detection and Correction
Redundancy
Oneerrordetectionmechanismwouldsendeverydataunittwice.
Thereceivingdevicewouldthenbeabletodoabit-for-bit
comparisonbetweenthetwoversionsofdata.Anydiscrepancy
wouldindicateanerror.
Ifanyerrorfound,thenecessarycorrectionmechanismshouldtake
place.
Disadvantage:
1.Transmissiontimeisdouble.
2.Timetakenforbit-for-bitcomparisonishigh.
Toovercomethisdrawback,insteadofrepeatingtheentiredata
stream,ashortergroupofbitsmaybeappendedtotheendofeach
unit.Thistechniqueiscalledredundancy.
Becausetheextrabitsareredundanttotheinformation;theyare
discardedassoonastheaccuracyofthetransmissionhasbeen
determined.

Figure: Redundancy

Error Detection and Correction
TypesofRedundancyCheck
Four types of redundancy checks are common in data communications.
1.Vertical Redundancy Check (VRC)
2.Longitudinal Redundancy Check (LRC)
3.Cyclic Redundancy Check (CRC)
4.Checksum

Figure: Vertical Redundancy Check (VRC)
•Mostcommonandleastexpensive
mechanismforerrordetection.
•VRCisalsocalledParityCheck.
•Inthistechnique,aredundantbit,
calledparitybit,isappendedto
everydataunitsothatthetotal
numberof1sinthedataunit
becomeseven.
•Somesystemsmayuseoddparity
checking.
•Itcandetectonlysinglebiterror.
1.Vertical Redundancy Check (VRC)
Error Detection and Correction

Figure: Longitudinal Redundancy Check (LRC)
•InLRC,ablockofbitsisorganizedinatable(rowsandcolumns).
•Forexample,insteadofsendingablockof32bits,dataunitisarranged
inatablemadeoffourrowsandeightcolumns.
•Checktheparitybitforeachcolumnandcreateanewrowofeight
bitswhichareparitybitsforthewholeblock.
•Originaldatawitheightparitybitsaretransferredtothereceiver.
2. Longitudinal Redundancy Check (LRC)
Error Detection and Correction

Figure: Cyclic Redundancy Check (CRC)
•UnlikeVRCandLRC,CRC
methodisworkingbasedonbinary
division.
•InCRC,insteadofaddingbits
togethertoachieveadesiredparity,
asequenceofredundantbits,called
theCRCortheCRCremainder,is
appendedtotheendofadataunitso
thattheresultingdataunitbecomes
exactlydivisiblebyasecond,
predeterminedbinarynumber.
•TheredundancybitsusedbyCRC
arederivedbydividingthedataunit
byapredetermineddivisor;the
remainderistheCRC.
3. Cyclic Redundancy Check (CRC)
Error Detection and Correction

Error Detection and Correction
CRC generator uses modulo-2
division.
•CRCcheckerfunctionsexactlylike
theCRCgenerator.
•Afterreceivingthedataappendedwith
theCRC,thecheckerdoesthesame
modulo-2division.
•Iftheremainderisall0’s,theCRCis
droppedand thedataaccepted.
Otherwise,thedatawillbediscarded(it
shouldberesentbythesender).

Figure: Check sum generator and checker
•Theerrordetectionmethodusedbythehigher-layerprotocolsiscalled
checksum.
•LikeVRC,LRCandCRC,Checksumisbasedontheconceptof
redundancy.
4. Checksum
Error Detection and Correction

•AttheSender(ChecksumGenerator)
•Theunitisdividedintoksections,eachofnbits.
•Allsectionsareaddedtogetherusingone’scomplementtogetthesum.
•Thesumiscomplementedandbecomesthechecksum.
•Thechecksumissentwiththedata
•AttheReceiver(ChecksumChecker)
•Theunitisdividedintoksections,eachofnbits.
•Allsectionsareaddedtogetherusingone’scomplementtogetthesum.
•Thesumiscomplemented.
•Iftheresultiszero,thedataareaccepted:otherwise,theyarerejected.
•Performance
•Thechecksumdetectsallerrorsinvolvinganoddnumberofbits.
•Itdetectsmosterrorsinvolvinganevennumberofbits.
•Ifoneormorebitsofasegmentaredamagedandthecorrespondingbitorbits
ofoppositevalueinasecondsegmentarealsodamaged,thesumsofthose
columnswillnotchangeandthereceiverwillnotdetectaproblem.
Error Detection and Correction

Error Detection and Correction
Checksum

Flowcontrolisasetofproceduresthattellsthesenderhow
muchdataitcantransmitbeforeitmustwaitforan
acknowledgementfromthereceiver.
Anyreceivingdevicehasalimitedspeedatwhichitcan
processincomingdataandalimitedamountofmemoryto
storetheincomingdata.
Incomingdatamustbecheckedandprocessedbeforetheycan
beused.
Therateofsuchprocessingisslowerthantherateof
transmission.
Forthisreason,eachreceivingdevicehasablockofmemory,
calledabuffer,reservedforstoringincomingdatauntilthey
areprocessed.
Ifthebufferbeginstofillup,thereceivermustbeabletotell
thesendertohalttransmissionuntilitisonceagainableto
receive.
Flow Control

Flowcontrolistechniquethatatransmittingentitydoesnot
conquerareceivingentitywithdata.
Twofunctionalmechanismsareacknowledgmentand
timeouts.
Aftergettingeachframe,thereceiverwillsendACKto
sender.
IfthesenderdoesnotreceiveACKuptoreasonable
amountoftime,theitretransmittheoriginalframe;waiting
forreasonableamountoftimeiscalledtimeout.
Thegeneralstrategyofusingacknowledgmentsand
timeoutstoimplementreliabledeliveryissometimescalled
automaticrepeatrequest(ARQ).
Thetwoflowcontrolmechanismsare:
StopandWaitFlowControl
SlidingWindowFlowControl
Flow Control

Piggybacking

Flow Control
Stop-and-WaitARQ
ThesimplestARQschemeisthestop-and-waitalgorithm.
Aftertransmittingoneframe,thesenderwaitsforan
acknowledgmentbeforetransmittingthenextframe.
Iftheacknowledgmentdoesnotarriveafteracertainperiodof
time,thesendertimesoutandretransmittheoriginalframe.

Stop-and-Wait ARQ
The main drawback of the stop-and-wait algorithm is that it allows the
sender to have only one outstanding frame on the link at a time.

Stop-and-Wait ARQ

Go-Back-N ARQ

Selective Repeat Windows ARQ

Flow Control
Thesendercantransmitseveralframesbeforeneeding
anacknowledgement.
Framescanbesentonerightafteranothermeaningthat
thelinkcancarryseveralframesatonceandits
capacitycanbeusedefficiently.
Thereceiveracknowledgesonlysomeoftheframes,
usingasingleACKtoconfirmthereceiptofmultiple
dataframes.
Slidingwindowreferstoimaginaryboxesatboththe
senderandthereceiver.
Windowcanholdframesateitherendandprovidesthe
upperlimitonthenumberofframesthatcanbe
transmittedbeforerequiringanacknowledgement.
Framesarenumberedmodulo-nwhichmeanstheyare
numberfrom0ton-1.
E.g.,Ifn=8,theframesarenumbered
0,1,2,3,4,5,6,7,i.e.,thesizeofthewindowisn-1
WhenthereceiversendsACK,itincludesthenumber
ofthenextframeitexpectstoreceive.
WhenthesenderseesanACKwiththenumber5,it
knowsthatallframesupthroughnumber4havebeen
received.
Sliding
Window

Sliding Window
Theslidingwindowalgorithmworksasfollows.
Firstsenderassignsasequencenumber,denoted
SeqNumtoeachframe.
Thesendermaintainsthreevariables:
sendwindowsize(SWS),givestheupperboundon
thenumberofoutstanding(unacknowledged)frames
thatthesendercantransmit;
lastacknowledgmentreceived(LAR);
lastframesent(LFS);
Thesenderalsomaintainsthefollowinginvariant:
LFS–LAR≤SWS
Figure: Sliding window on
sender

Sliding Window
Thereceivermaintainsthreevariables:
receivewindowsize(RWS),givestheupperboundon
thenumberofout-of-orderframesthatthereceiveris
willingtoaccept;
LAFdenotesthesequencenumberofthelargest
acceptableframe;
LFRdenotesthesequencenumberofthelargest
framereceived;
Thereceiveralsomaintainsthefollowinginvariant:
LAF–LFR≤RWS
Figure: Sliding window on
receiver

Sliding Window
Theslidingwindowalgorithmworksasfollows.
Firstsenderassignsasequencenumber,denoted
SeqNumtoeachframe.
Thesendermaintainsthreevariables:
sendwindowsize(SWS),givestheupper
boundonthenumberofoutstanding
(unacknowledged)framesthatthesendercan
transmit;
lastacknowledgmentreceived(LAR);
lastframesent(LFS);
Thesenderalsomaintainsthefollowinginvariant:
LFS–LAR≤SWS
Thereceivermaintainsthreevariables:
receivewindowsize(RWS),givestheupper
boundonthenumberofout-of-orderframes
thatthereceiveriswillingtoaccept;
LAFdenotesthesequencenumberofthe
largestacceptableframe;
LFRdenotesthesequencenumberofthe
largestframereceived;
Thereceiveralsomaintainsthefollowinginvariant:
LAF–LFR≤RWS
Figure: Sliding window on
sender
Figure: Sliding window on
receiver

Media Access Control
Thetwomainfunctionofthedatalinklayer
areDataLinkControlandMediaAccess
Control.
Thedatalinklayerdealswiththedesignand
proceduresforcommunicationbetweentwo
adjacentnodes:node-to-nodecommunication.
Thesecondfunctionofthedatalinklayeris
mediaaccesscontrol,orhowtosharethelink.

Media Access Control
Whennodesorstationsareconnectedandusea
commonlink,calledamultipointorbroadcast
link,weneedamultiple-accessprotocolto
coordinateaccesstothelink.
Theuppersub-layeroftheDLLthatis
responsibleforflowanderrorcontroliscalledthe
LogicalLinkControl(LLC)layer.
Thelowersub-layeroftheDLLthatismostly
responsibleformultipleaccessresolutioniscalled
theMediaAccessControl(MAC)layer.

Media Access Control
Manyformalprotocolshavebeenrevisedto
handleaccesstoasharedlinks;
Wecategorizethemintothreegroups:

Media Access Control
RANDOMACCESSorCONTENTION METHOD
Inrandomaccess,nostationissuperiortoanotherstation.
Nostationisassignedthecontroloveranother.
Astationthathasdatatosendusesaproceduredefinedby
theprotocoltomakeadecisiononwhetherornottosend.
Thisdecisiondependsonthestateofthemedium(idleorbusy).
Twofeaturesofrandomaccessare:
1)Thereisnoscheduledtimeforastationtotransmit.
Transmissionisrandomamongthestations.Thatiswhy
thesemethodsarecalledRandomAccess.
2)Norulesspecifywhichstationshouldsendnext.Stations
competewithoneanothertoaccessthemedium.Thatiswhy
thesemethodsarealsocalledContentionMethods.

Media Access Control
RANDOMACCESSorCONTENTION METHOD
Inrandomaccess,eachstationhastherighttothemedium
withoutbeingcontrolledbyanyotherstation.
Ifmorethanonestationtriestosend,thereisanaccess
conflict(collision)andtheframeswillbeeitherdestroyedor
modified.
Toavoidaccessconflictortoresolveitwhenithappens,
eachstationfollowsaprocedurethatanswersthefollowing
questions:
1)Whencanthestationaccessthemedium?
2)Whatcanthestationdoifthemediumisbusy?
3)Howcanthestationdeterminethesuccessorfailureofthe
transmission?
4)Whatcanthestationdoifthereisanaccessconflict?

Media Access Control
RANDOMACCESSorCONTENTION METHOD
TherandomaccessmethodevolvedfromALOHAprotocol
whichusedaverysimpleprocedurecalledmultipleaccess
(MA).
Themethodwasimprovedwiththeadditionofprocedure
thatforcesthestationtosensethemediumbefore
transmitting.ThiswascalledCarrierSenseMultipleAccess
(CSMA).Thismethodlaterevolvedintotwoparallel
methods:
i.CarrierSenseMultipleAccesswithcollisiondetection
(CSMA/CD);CSMA/CDtellsthestationwhattodowhena
collisionisdetected.
ii.CarrierSenseMultipleAccesswithcollisionavoidance
(CSMA/CA);CSMA/CAtriestoavoidthecollision.

RANDOM ACCESS orCONTENTION METHOD
ALOHA
ALOHA,theearliestrandomaccessmethodwas
developedattheUniversityofHawaiiin1970.
Itwasdesignedforaradio(wireless)LAN,butitcan
beusedonanysharedmedium.
PureALOHA
TheoriginalALOHAprotocoliscalledpure
ALOHA.
Theideaisthateachstationsendsaframewhenever
ithasaframetosend.Whenthechannelisshared,
thereisthepossibilityofcollisionbetweenframes
fromdifferentstation.
Media Access Control

PureALOHA
RANDOM ACCESS orCONTENTION METHOD
Media Access Control

PureALOHA
Inthefigure,therearefour
stationsthatcontendwithone
anotherforaccesstotheshared
channel.
Eachstationsendstwoframes;
thereareatotalofeightframes
onthesharedmedium.
Someoftheseframescollide
becausemultipleframesarein
contentionforthesharedchannel.
Onlytwoframessurvive:frame
1.1andframe3.2.
ThepureALOHAprotocolrelies
onacknowledgmentsfromthe
receiver.
Iftheacknowledgmentdoesnot
arriveafteratime-outperiod,the
stationassumesthattheframe(or
acknowledgment)hasbeen
destroyedandresendstheframe.
RANDOM ACCESS orCONTENTION
METHOD
Media Access Control

RANDOM ACCESS orCONTENTION METHOD
Media Access Control

ProcedureforpureALOHAprotocol
ACollisioninvolvestwoormore
stations.
Ifallthesestationstrytoresend
theirframesafterthetime-out,the
frameswillcollideagain.
PureALOHAdictatesthatwhen
thetime-outperiodpasses,each
stationwaitsarandomamountof
timebeforeresendingitsframe.
Therandomnesswillhelpavoid
morecollisions.Thistimeiscalled
theBack-offtimeT
B.
PureALOHAhasa2
nd
methodto
preventcongestingthechannel
withretransmittedframes.Aftera
maximum number of
retransmissionattempts,K
max’s
stationmustgiveupandtrylater.
RANDOM ACCESS orCONTENTION
METHOD
Media Access Control

Vulnerable time
RANDOM ACCESS orCONTENTION METHOD
Media Access Control

Vulnerabletime
Thelengthoftimeinwhichthereisa
possibilityofcollisionisthe
vulnerabletime.
Weassumethatthestationssendfixed-
lengthframeswitheachframetaking
T
frsecondstosend.
PureALOHAvulnerabletime=2×T
fr
ThethroughputforpureALOHAis
S=G×e
-2G
whereG=averagenumberofframes
generatedbythesystemduringone
frametransmission.
Themaximumthroughput
S
max=0.184whenG=½
RANDOM ACCESS orCONTENTION METHOD
Media Access Control

Slotted ALOHA
RANDOM ACCESS orCONTENTION METHOD
Media Access Control

•SlottedALOHAwasinventedtoimprovetheefficiencyofpureALOHA.
•InslottedALOHA,wedividethetimeintoslotsofT
frsecondsandforcethestationtosend
onlyatthebeginningofthetimeslot.
•Becauseastationisallowedtosendonlyatthebeginningofthesynchronizedtimeslot,ifa
stationmissesthismoment,itmustwaituntilthebeginningofthenexttimeslot.The
vulnerabletimeisnowreducedtoone-half,equaltoT
fr.
•SlottedALOHAvulnerabletime=T
fr
•Throughput:Itcanbeprovedthattheaveragenumberofsuccessfultransmissionsforslotted
ALOHAis
S=G×e
-G
Themaximumthroughput
S
max=0.368whenG=1
Slotted ALOHA
RANDOM ACCESS orCONTENTION METHOD
Media Access Control

Carrier Sense Multiple Access (CSMA)
Media Access Control

Media Access Control
Carrier Sense Multiple Access (CSMA)
CSMAisbasedontheprinciple
‘Sensebeforetransmit’or‘listen
beforetalk’.
CSMAcanreducethepossibilityof
collision,butitcannoteliminateit.
ThereasonforthisisshowninFigure
–Spaceandtimemodelofthe
collisioninCSMA.
Stationsareconnectedtoashared
channel(usuallyadedicatedmedium).
Thepossibilityofcollisionstillexistsbecauseofpropagationdelay;Whenastationsendsa
frame,itstilltakestime(althoughveryshort)forthefirstbittoreacheverystationandfor
everystationtosenseit.Inotherwords,astationmaysensethemediumandfinditidle,
onlybecausethefirstbitsentbyanotherstationhasnotyetbeenreceived.

VulnerableTimeforCSMA
Carrier Sense Multiple Access (CSMA)
Media Access Control

VulnerableTimeforCSMA
•ThevulnerabletimeforCSMAisthepropagationtimeT
p.Thisisthetimeneeded
forasignaltopropagatefromoneendofthemediumtotheother.
•Whenastationsendsaframe,andanyotherstationtriestosendaframeduring
thistime,acollisionwillresult.
•Butifthefirstbitoftheframereachestheendofthemedium,everystationwill
alreadyhaveheardthebitandwillrefrainfromsending.
•Inthefigure,theleftmoststationAsendsaframeattimet
1,whichreachestherightmost
stationDattinet
1+T
p.Thegreyareashowsthevulnerableareaintimeandspace.
Carrier Sense Multiple Access (CSMA)
Media Access Control

PersistenceMethods
•Whatshouldastationdoifthechannelisbusy?What
shouldastationdoifthechannelisidle?
•Threemethodshavebeendevisedtoanswerthese
questions:
1.1-persistentmethod
2.non-persistentmethod
3.p-persistentmethod
Carrier Sense Multiple Access (CSMA)
Media Access Control

PersistenceMethods
•Figureshowsthebehaviorofthreepersistencemethodswhena
stationfindsachannelbusy.
1-persistent
•Simpleandstraightforward.
•Inthismethods,afterthestationfindsthelineidle,itsendsits
frameimmediately(withprobability1).
•Thismethodhasthehighestchanceofcollisionbecausetwoor
morestationsmayfindtheidleandsendtheirframes
immediately.
Media Access Control
Carrier Sense Multiple Access (CSMA)

Non-persistent
•Inthismethods,astationthathasaframetosendsensestheline.
•Ifthelineisidle,itsendsimmediately.
•Ifthelineisnotidle,itwaitsarandomamountoftimeandthensensesthe
lineagain.
•Thenon-persistentapproachreducesthechanceofcollision.Becauseit
isunlikelythattwoormorestationswillwaitthesameamountoftime
andretrytosendsimultaneously.
•However,thismethodreducestheefficiencyofthenetworkbecausethe
mediumremainsidlewhentheremaybestationswithframestosend.
Media Access Control
Carrier Sense Multiple Access (CSMA)

Media Access Control
Carrier Sense Multiple Access (CSMA)

•CSMA/CDaugmentsthealgorithmtohandlethe
collision.
•Inthismethod,astationmonitorsthemediumafterit
sendsaframetoseeifthetransmissionwassuccessful.
Ifso,thestationisfinished.
•If,however,thereiscollision,theframeissentagain.
Carrier Sense Multiple Access with Collision
Detection (CSMA/CD)
Media Access Control

•Procedure
•Weneedtosensethechannelbeforewestartsendingthe
framebyusingoneofthepersistentprocesses.
•Transmissionandcollisiondetectionisacontinuous
process.
•Wedonotsendtheentireframe(bitbybit).
•Bysendingashortjammingsignal,wecanenforcethe
collision,incase,otherstationshavenotyetsensedthe
collision.
Carrier Sense Multiple Access with
Collision Detection (CSMA/CD)
Media Access Control

Carrier Sense Multiple Access with
Collision Detection (CSMA/CD)

•CSMA/CAwasinventedtoavoidcollisionsonwireless
networks.
•CollisionsareavoidedthroughtheuseofCSMA/CA’s
threestrategies:
1.InterframeSpace(IFS)
2.ContentionWindow
3.Acknowledgment
Carrier Sense Multiple Access with
Collision Avoidance (CSMA/CA)
Media Access Control

1.InterframeSpace(IFS)
•Whenanidlechannelisfound,thestationdoesnotsend
immediately.
•Itwaitsforaperiodoftimecalledtheinterframespace
orIFS.
•Eventhoughthechannelmayappearidlewhenitis
sensed,adistantstationmayhavealreadystarted
transmitting.Thedistantstation’ssignalhasnotyet
reachedthisstation.
Carrier Sense Multiple Access with
Collision Detection (CSMA/CA)
Media Access Control

2.ContentionWindow
•Thecontentionwindowisanamountoftimedivided
intoslots.
•Astationthatisreadytosendchoosesarandomnumber
ofslotasitswaittime.
•Thestationneedstosensethechannelaftereachtime
slot.
•However,ifthestationfindsthechannelbusy,itdoes
notrestarttheprocess;itjuststopsthetimerandrestarts
itwhenthechannelissensedasidle.Thisgivespriority
tothestationwiththelongestwaitingtime.
Carrier Sense Multiple Access with
Collision Detection (CSMA/CA)
Media Access Control

3.Acknowledgment
•Withalltheseprecautions,therestillmaybeacollision
resultingindestroyeddata,andthedatamaybe
corruptedduringthetransmission.
•Thepositiveacknowledgmentandthetime-outtimercan
helpguaranteethatthereceiverhasreceivedtheframe.
Carrier Sense Multiple Access with
Collision Detection (CSMA/CA)
Media Access Control

Media Access Control
Manyformalprotocolshavebeenrevisedtohandle
accesstoasharedlinks;
Wecategorizethemintothreegroups:

•Incontrolledaccess,thestationsconsultoneanotherto
findwhichstationhastherighttosend.
•Astationcannotsendunlessithasbeenauthorizedby
otherstations.
•Threepopularcontrolled-accessmethods:
1.Reservation
2.Polling
3.TokenPassing
Media Access Control
CONTROLLED ACCESS

1.Reservation
•Inthereservationmethod,astationneedstomakea
reservationbeforesendingdata.
•Timedividedintointervals.
•Ineachinterval,areservationframeprecedesthedataframes
sentinthatinterval.
•Thisfigureshowsasituationwithfivestationsandfive-mini
slotreservationframe.Inthefirstinterval,onlystations1,3
and4havemadereservations.Inthesecondinterval,only
station1hasmadeareservation.
CONTROLLED ACCESS

2.Polling
•Hereonedeviceisdesignatedasaprimarystationandtheotherdevicesare
secondarystations.Alldataexchangesmustbemadethroughtheprimary
device.
•Theprimarydevicecontrolslink;thesecondarydevicesfollowitsinstructions.
•Theprimarydeviceistheinitiatorofasession.
•Iftheprimarywantstoreceivedata,itasksthesecondaryiftheyhave
anythingtosend;thisiscalledpollfunction.
•Iftheprimarywantstosenddata,ittellsthesecondarytogetreadytoreceive;
thisiscalledselectfunction.
CONTROLLED ACCESS

3.TokenPassing
•Inthetoken-passingmethod,thestationsinanetworkare
organizedinalogicalring.
•Foreachstation,thereisapredecessorandasuccessor.
CONTROLLED ACCESS

•Channelizationisamulti-accessmethodinwhichthe
availablebandwidthofalinkissharedintime,
frequency,orthroughcodebetweendifferentstations.
•Threechannelizationprotocolsareused.Theyare
1.Frequency-DivisionMultipleAccess(FDMA)
2.Time-DivisionMultipleAccess(TDMA)
3.Code-DivisionMultipleAccess(CDMA)
CHANNELIZATION

CHANNELIZATION

1.Frequency-DivisionMultipleAccess(FDMA)
•Theavailablebandwidthisdividedintofrequency
bands.
•Eachstationisallocatedabandtosenditsdata.
•Eachbandisreservedforaspecificstation,andit
belongstothestationallthetime.
•Eachstationalsousesaband-passfiltertoconfinethe
transmitterfrequencies.
•Topreventstationinterferences,theallocatedbandsare
separatedfromoneanotherbysmallguardbands.
•FDMAspecifiespredeterminedfrequencybandforthe
entireperiodofcommunication.
CHANNELIZATION

1.Frequency-DivisionMultipleAccess(FDMA)
CHANNELIZATION

2.Time-DivisionMultipleAccess(TDMA)
•Thestationssharethebandwidthofthechannelintime.
•Eachstationisallocatedatimeslotduringwhichitcansend
data.
•Eachstationtransmitsitsdatainassignedtimeslot.
•ThemainproblemwithTDMAliesinachieving
synchronizationbetweenthedifferentstations.
•Eachstationneedstoknowthebeginningofitsslotandthe
locationofitsslot.
•Thisisdifficultbecauseofpropagationdelaysintroducedin
thesystemifthestationsarespreadoveralargeare.
•Tocompensateforthedelays,wecaninsertguardtimes.
Synchronizationisnormallyaccomplishedbyhavingsome
synchronizationbitsatthebeginningofeachbit.
CHANNELIZATION

2.Time-DivisionMultipleAccess(TDMA)
CHANNELIZATION

3.Code-DivisionMultipleAccess(CDMA)
•CDMAdiffersfromFDMAbecauseonlyonechannel
occupiestheentirebandwidthofthelink.
•ItdiffersfromTDMAbecauseallstationscansenddata
simultaneously;thereisnotime-sharing.
•InCDMA,onechannelcarriesalltransmissions
simultaneously.
CHANNELIZATION

•ALANcanbeusedasanisolatednetworktoconnect
computersinanorganizationforsharingresources.
•MostoftheLANstodayarelinkedtoaWideAreaNetwork
(WAN)ortheInternet.
•TheLANmarkethasbeenseveraltechnologiessuchas
Ethernet
TokenRing
TokenBus
FDDI
ATMLAN
ETHERNET (IEEE 802.3)

•EthernetisabasebandLANspecificationinventedin
1970sbyXeroxCorporationthatoperatesat10Mbps
usingCSMA/CDtorunovercoaxialcable.
•ThetermisnowoftenusedtorefertoallCSMA/CD
LANs.
ETHERNET (IEEE 802.3)

•In1985,theComputerSocietyoftheIEEEstartedaproject,
calledProject802,tosetstandardstoenable
intercommunicationamongequipmentsfromvarietyof
manufacturers.
•TheStandardwasadoptedbyAmericanNationalStandards
Institute(ANSI).
•In1987,theInternationalOrganizationforStandardization
(ISO)alsoapproveditasaninternationalstandardunderthe
designationISO8802.
•IEEE802.3specificationwasdevelopedbasedontheoriginal
EthernetTechnology,jointlybyDigitalEquipment
Corporation,IntelCorporationandXeroxCorporation.
•EthernetiscompatiblewithIEEE802.3.
•EthernetandIEEE802.3areusuallyimplementedineitheran
interfacecardorincircuitryonaprimarycircuitboard.
ETHERNET (IEEE 802.3)

ETHERNET (IEEE 802.3)
Ethernet Network Interface Card

IEEESTANDARDS
ETHERNET (IEEE 802.3)

IEEESTANDARDS
•Therelationshipofthe802StandardtothetraditionlOSImodel
isshowninthebelowfigure.
•TheIEEEhassubdividedthedatalinklayerintotwosublayers.
(i)LogicalLinkControl(LLC)(ii)MediaAccessControl
(MAC).
ETHERNET (IEEE 802.3)

IEEESTANDARDS
•LogicalLinkControl(LLC)
•InIEEEProject802,flowcontrol,errorcontrol,and
partofframingdutiesarecollectedintoasublayer
calledthelogicallinkcontrol.
•FramingishandledinbothLLCsublayerandMAC
sublayer.
•TheLLCprovidesasingledatalinkcontrolprotocolfor
allIEEELANs,buttheMACsublayerprovides
differentprotocolsfordifferentLANs.
•AsingleLLCprotocolcanprovideinterconnectivity
betweendifferentLANsbecauseitmakestheMAC
sublayertrransparent.
ETHERNET (IEEE 802.3)

IEEESTANDARDS
•MediaAccessControl(MAC)
•IEEEProject802hascreatedasublayer,called
MediaAccessControlthatdefinesthespecific
accessmethodforeachLAN.
•Forexample,itdefinesCSMA/CDasthemedia
accessmethodforEthernetLANsandthetoken
passingmethodforTokenRingandTokenBus
LANs.
•Apartoftheframingfunctionisalsohandledbythe
MAClayer.
ETHERNET (IEEE 802.3)

IEEESTANDARDS
•MACSublayer
•InstandardEthernet,theMACsublayer
governstheoperationoftheaccessmethod.
•Italsoframesthedatareceivedfromthe
upperlayerandpassesthemtothephysical
layer.
ETHERNET (IEEE 802.3)

Figure: Ethernet (802.3) Frame Format
IEEE 802.3

Figure:
Ethernet (802.3) Frame Format
•Preamble:Eachframestartswithapreambleof7bytes,eachbyte
containingbit10101010usedtosynchronizereceiver’sclockto
sender’s.
•SFD:Thisfieldcontainingabytesequence10101011denotesthe
startofframe.
•Addresses:DestinationAddress(DA)fieldis6bytesandcontains
physicaladdressofthedestinationstation.Sourceaddress(SA)field
isalso6bytesandcontainsthephysicaladdressofthesenderofthe
packet.
•Length:Thelengthindicatesthenumberofbytesofdatathat
followsthisfield.(Maximum1500bytes)
IEEE 802.3

Figure: Ethernet (802.3) Frame Format
•Data:carriesdataencapsulatedfromtheupper-layer
protocols.
•Pad:Zeroesareaddedtothedatafieldtomakeminimum
datalength=46bytes.(Ifdataintheframeisinsufficientto
filltheframetoitsminimum64-bytesize,paddingbytesare
insertedtoensureatleasta64-byteframe.)
•FrameCheckSequence(FCS):Thissequencecontains4-
bytecyclicredundancycheck(CRC)value,whichiscreated
bysendingdeviceandisrecalculatedbyreceivingdeviceto
checkfordamagedframes.
IEEE 802.3

ETHERNET Evolution

Categories of standard ETHERNET

Comparison of ETHERNET and IEEE 802.3
10Base5,10Base2,10BaseF:Signalregenerationcanbedonewithhelpof
repeaters.
10BaseT:A hub functions as a repeater with additional functions.

10Base5
•Advantages:
•Lowattenuation
•Excellentnoiseimmunity
•Superiormechanicalstrength
•Disadvantages:
•Bulky
•Difficulttopull
•Transceiverboxesaretooexpensive
•Wiringrepresentedasignificantpartoftotalinstalledcost.
10Base2
•Advantages:
•Easiertoinstall
•Reducedhardwarecost
•BNCconnectorswidelydeployed(Lowerinstallationcosts)
•Disadvantages:
•Attenuationisnotgood
•CouldnotsupportasmanystationsduetosignalreflectioncausedbyBNCTee
connector.
ETHERNET (IEEE 802.3)

10BaseT
•Advantages:
•Fewercableproblems
•Easiertotroubleshootthancoax.
•Disadvantages:
•Cablelengthatmost100meters.
10BaseF
•Advantages:
•Couldbedonewithoutpullingnewwires.
•Eachhubamplifiesandrestoresincomingsignal.
ETHERNET (IEEE 802.3)

EXPERIENCESWITHETHERNET
•Ethernetsworkbestunderlightloads(Utilizationover
30%isconsideredheavy.)
•Networkcapacityiswastedbycollision.
•Mostnetworksarelimitedtoabout200hosts
(Specificationallowsforupto1024.)
•Transportlevelflowcontrolhelpsreduceload(numberof
backtobackpackets)
•Ethernetisinexpensive,fastandeasytoadminister.
ETHERNET (IEEE 802.3)

EXPERIENCESWITHETHERNET
EthernetProblems
•Ethernet’speakutilizationisprettylow(likeAloha).
•Peakthroughputworstwith
i.Morehosts:Morecollisionsneededtoidentifysinglesender.
ii.Smallerpacketsizes:Morefrequentarbitration.
iii.Longerlinks:collisiontakelongertoobserve,morewasted
bandwidths.
iv.Efficiencyisimprovedbyavoidingtheseconditions.
•WhydoesEthernetwin?
i.TherearelotsofLANprotocols
ii.Price
iii.Performance
iv.Availability
v.Easeofuse
vi.Scalability
ETHERNET (IEEE 802.3)

•Wirelesscommunicationisoneofthefastest-growing
technologiesbecausethedemandforconnecting
deviceswithoutuseofcablesisincreasing
everywhere.
•WirelessLANscanbefoundoncollegecampuses,in
officebuildings,andinmanypublicareas.
•IEEE802.11wirelessLANsaresometimescalled
wirelessEthernet.
•IEEE802.11operatesonthephysicalanddatalink
layers.
Wireless LAN

802.11 Wireless LAN
Providesnetworkconnectivityoverwirelessmedia
AnAccessPoint(AP)isinstalledtoactasBridge
betweenWirelessandWiredNetwork
TheAPisconnectedtowirednetworkandis
equippedwithantennaetoprovidewireless
connectivity
Network
connectivity
to the
legacy
wired LAN
Desktop
with PCI 802.11 LAN card
Laptop
with PCMCIA 802.11 LAN card
Access Point

•IEEE802.11definestwokindsofservices.Theyare
i.BasicServiceSet(BSS)
ii.ExtendedServiceSet(ESS)
IEEE 802.11 Wireless LAN

•BasicServiceSet(BSS)
•ABasicServiceSet(BSS)ismadeofstationaryormobilewireless
stationsandanoptionalcentralbasestation,knownastheAccessPoint
(AP).
•TheBSSwithoutanAPisastand-alonenetworkandcannotsenddata
tootherBSSs.Itiscalledanadhocnetwork.
•ABSSwithanAPissometimesreferredtoasaninfrastructure
network.
IEEE 802.11 Wireless LAN

•ExtendedServiceSet(ESS)
•AnExtendedServiceSet
(ESS)ismadeupoftwoor
moreBSSswithAccess
Points(AP).
•Inthiscase,theBSSsare
connectedthrougha
distributionsystem,whichis
usuallyawiredLANsuchas
anEthernet.
•Thedistributionsystem
connectstheAPsintheBSSs.
•Theextendedservicesetuses
twotypesofstations.They
are(i)Mobilestations(ii)
Stationarystations.
•Themobilestationsare
normalstationsinsideaBSS.
ThestationarystationsareAP
stationsthatarepartofa
wiredLAN.
IEEE 802.11 Wireless LAN

•StationTypes
•IEEE802.11definesthreetypesofstationsbasedontheir
mobilityinawirelessLAN.
i.No-transitionmobility
ii.BSS-transitionmobility
iii.ESS-transitionmobility
•Astationwithno-transitionmobilityiseitherstationary(not
moving)ormovingonlyinsideaBSS.
•AstationwithBSS-transitionmobilitycanmovefromoneBSS
toanother,butthemovementisconfinedinsideoneESS.
•AstationwithESS-transitionmobilitycanmovefromoneESS
toanother.
•However,IEEE802.11doesnotguaranteethatcommunication
iscontinuousduringthemove.
IEEE 802.11 Wireless LAN

•MACSublayer
•IEEE802.11definestwotypesofMACsublayers.
i.TheDistributedCoordinationFunction(DCF)
ii.ThePointCoordinationFunction(PCF)
IEEE 802.11 Wireless LAN

IEEE 802.11 Wireless LAN
Inwirelessnetworking,thehiddennodeproblemorhidden
terminalproblemoccurswhenanodeisvisiblefroma
wirelessaccesspoint(AP),butnotfromothernodes
communicatingwithsaidAP.Thisleadstodifficultiesin
mediaaccesscontrol.

IEEE 802.11 Wireless LAN
Distributed Coordination Function (DCF)

IEEE 802.11 Wireless LAN
Point Coordination Function (PCF)

Addressing Mechanism
•FourpossibleCasesofAddressing
•Case1:00inthiscaseToDS=0andFromDS=0
Thismeansthattheframeisnotgoingtoadistributionsystem(ToDS=0)
andisnotcomingfromadistributionsystem(FromDS=0).Theframeis
goingfromonestationinaBSStoanotherwithoutpassingthroughthe
distributionsystem.TheACKframeshouldbesenttotheoriginalsender.
•Case2:01inthiscaseToDS=0andFromDS=1
Thismeansthattheframeiscomingfromadistributionsystem(FromDS=
1).TheframeiscomingfromanAPandgoingtoastation.TheACKframe
shouldbesenttotheAP.NotethatAddress3containstheoriginalsenderof
theframe(inanotherBSS).
•Case3:10inthiscaseToDS=1andFromDS=0
Thismeansthattheframeisgoingtoadistributionsystem(FromDS=1).
TheframeisgoingfromastationtoAP.TheACKissenttotheoriginal
station.NotethatAddress3containsthefinaldestinationoftheframe(in
anotherBSS).
•Case4:11inthiscaseToDS=1andFromDS=1
ThismeansthattheframeisgoingfromAPtoanotherAPinawireless
distributionsystem.Weneedfouraddressestodefinetheoriginalsender,the
finaldestinationandtwointermediateAPs.

Addressing Mechanism
•IEEE802.11addressingmechanismspecifiesfourcases,defined
bythevalueofthetwoflagsintheFCfield,ToDSandFromDS.
•Eitherflagcanbeeither0or1,resultinginfourdifferent
situations.
•Address1istheaddressofthenextdevice.
•Address2istheaddressofthepreviousdevice.
•Address3isthefinaldestinationstation,iftheaddressisnot
definedbyAddress1.
•Address4istheoriginalsourcestation,ifitisnotthesameas
address2.

Physical Layer
•IEEE802.11LANhasseveralphysicallayersdefinedtooperatewith
itsMAClayer.
•Specificationofthe802.11typesare:
•IEEE802.11FHSS–FrequencyHoppingSpreadSpectrum
•IEEE802.11DSSS–DirectSequenceSpreadSpectrum
•IEEE802.11Infrared
•IEEE802.11aOFDM–OrthogonalFrequencyDivisionMultiplexing
•IEEE802.11bDSSS
•IEEE802.11gOFDM
•(FSK:FrequencyShiftKeying;PSK:PhaseShiftKeying;PPM:Pulse
PositionModulation;QAM:QuadratureAmplitudeModulation)

BLUETOOTH
•BluetoothisawirelessLANtechnologydesignedto
connectdevicesofdifferentfunctionssuchastelephones,
notebooks,computers,cameras,printers,coffeemakers,
andsoon.
•ABluetoothLANisanadhocnetwork,whichmeansthat
thenetworkisformedspontaneously.
•Thedevicesometimescalledgadgets,findeachotherand
makeanetworkcalledapiconet.
•ABluetoothLANcanevenbeconnectedtotheInternetif
oneofthegadgetshasthiscapability.
•ABluetoodLAN,bynature,cannotbelarge.
•Architecture
•Bluetoothdefinestwotypesofnetworks.
i.Piconet
ii.Scatternet

BLUETOOTH
•Architecture
•Bluetoothdefinestwotypesofnetworks.
i.Piconet
ii.Scatternet

BLUETOOTH
•Piconet
•ABluetoothnetworkiscalledapiconet,orasmallnet.
•Thecommunicationbetweentheprimaryandthesecondarycanbe
one-to-oneorone-to-many.
•Itcanhaveuptoeightstations,oneofwhichiscalledthemaster;the
restarecalledslaves.
•Slavessynchronizetheirclocksandhoppingsequencewiththe
master.

BLUETOOTH
•Scatternet
•Piconetscanbecombinedtoformwhatiscalledascatternet.
•Thisstationcanreceivemessagefromtheprimaryinthefirstpiconet
(asasecondary)and,actingasaprimary,deliverthemtosecondaries
inthesecondpiconet.
•Aslavestationinonepiconetcanbecomethemasterinanother
piconet.
•ABluetoothdevicehasabuilt-in-shortrangeradiotransmitter.

BLUETOOTH
•BluetoothLayers
•Bluetoothusesseverallayersthatdonotexactlymatchthoseofthe
Internetmodel.
•Bluetoothdevicesarelow-powerandhaverange10centimeterst0
10meters.
•Bluetoothusesa2.4GHzISMbanddividedinto79channelsof1
MHzeach.

BLUETOOTH
•RadioLayer
•RoughlyequaltophysicallayeroftheInternetmodel.
Physicallinkscanbesynchronousorasynchronous.
•UsesFrequency-HoppingSpreadSpectrum(FHSS).
•Changesitsmodulationfrequency1600timespersecond.
•Usesfrequencyshiftkeying(FSK)withGaussian
bandwidthfilteringtotransformbitstoasignal.

BLUETOOTH
•BasebandLayer
•RoughlyequaltoMACsublayerinLANs.Theaccess
methodisTimeDivisionMultipleAccess(TDMA).
•Theprimary(master)andsecondary(slave)communicate
witheachotherusingtimeslots.
•Thelengthofthetimeslotisexactlythesameasthedwell
time,625microseconds.
•TimedivisionduplexingTDMA(TDD-TDMA)isakind
ofhalf-duplexcommunicationinwhichtheslaveand
receiversendandreceivedata,butnotatthesametime
(half-duplex).

BLUETOOTH
•Single-secondarycommunication

BLUETOOTH
•Single-secondarycommunication
•AlsocalledSingle-slavecommunication
•Ifthepiconethasonlyonesecondary,theTDMAoperationisvery
simple.
•Thetimeisdividedintoslotsof625microseconds.
•Theprimaryusesevennumberedslots(0,2,4,…)andthesecondary
usesoddnumberedslots(1,3,5,…).
•TDD-TDMAallowstheprimaryandthesecondarytocommunicate
inhalfduplexmode.
•InSlot0,theprimarysendsandthesecondaryreceived;InSlot1,the
secondarysendsandtheprimaryreceives.Thecycleisrepeated.

BLUETOOTH
•Multiple-Secondarycommunication

BLUETOOTH
•Multiple-Secondarycommunication
•Alsocalledmultiple-slavecommunication(ifthereismorethanone
secondaryinthepiconet.)
•Masteruseseven-numberslots.
•Slavesendsinthenextodd-numberedslotifthepacketinthepreviouslot
wasaddressedtoit.
•Inslot0,theprimarysendsaframetosecondary1.
•Inslot1,onlysecondary1sendsaframetotheprimarybecausethe
previousframewasaddressedtosecondary1;othersecondariesaresilent.
•Inslot2,theprimarysendsaframetosecondary2.
•Inslot3,onlysecondary2sendsaframetotheprimarybecausethe
previousframewasaddressedtosecondary2;othersecondariesaresilent.
•Thecyclecontiunes.

BLUETOOTH
•PHYSICALLINKS
•Twotypesoflinkscanbecreatedbetweenaprimaryandasecondary:
i.SynchronousConnectionOriented(SCO)Link
ii.AsynchronousConnectionlessLink(ACL)
•SynchronousConnection-oriented(SCO)Link
•SCOisusedforreal-timeaudiowhereavoidingdelayisall
important.
•Avoidinglatencyismoreimportantthanintegrity.
•AsecondarycancreateuptothreeSCOlinkswiththeprimary,
sendingdigitizedaudio(PCM)at64kbpsineachlink.
•Transmissionusingslots.
•Noretransmission.
•AsynchronousConnectionlessLink(ACL)
•ACLisusedwhendataintegrityismoreimportantthanavoiding
latency.

BLUETOOTH
•FRAMEFORMAT
•Aframeinthebasebandlayercanbeoneofthreetypes:one-
slot,three-slot,orfive-slot.
•Aslotis625microseconds.
•Inaone-slotframeexchange,259microsecondsisneeded
forhoppingandcontrolmechanisms.Thesizeofaone-slot
frameis(625-259)366bits.
•Athree-slotframeoccupiesthreeslots.Since259micro
sendsisneededforhopping,thelengthoftheframeis3×
625–259=1616microsecondsorbits.
•Afive-slotframealsouses259bitsforhopping,which
meansthatthelengthoftheframeis5×625-259=2866
bits.

BLUETOOTH
•FRAMEFORMAT

BLUETOOTH
•FRAMEFORMAT
•Accesscode:This72-bitfieldnormallycontainssynchronizationbitsandtheidentifierofthe
primarytodistinguishtheframeofonepiconetfromanother.

BLUETOOTH
•L2CAP(LogicalLinkControlandAdaptationProtocol)
•EquivalenttoLLCsublayerinLANs.
•UsedfordataexchangeonACLlink.SCQchannelsdonotuse
L2CAP.
•Frameformatcontainsthefollowingthreefields:Length,
ChannelID,DataandControl.
•L2CAPcandoMultiplexing,segmentationandreassembly,
QoSandgroupmanagement.

Switching
Connectivity
Wheneverwehavemultipledevices,wehavetheproblemofhowto
connectthemtomakeone-on-onecommunicationpossible.
Onesolutionistoinstallapoint-to-pointconnectionbetweeneachpair
ofdevices(meshtopology)orbetweenacentraldevice(hub)and
everyotherdevice(startopology).
However,thesemethodsareimpracticalandwastefulwhenappliedto
verylargenetworks.
Thenumberandlengthofthelinksrequiretoomuchinfrastructureto
becostefficient,andthemajorityofthoselinkswouldbeidlemostof
thetime.
InBustopology,thedistancesbetweendevicesandthetotalnumber
ofdevicesincreasebeyondthecapacitiesofthemediaandequipment.
Abettersolutionisswitching.

Switches
Connectivity
ASwitchednetworkconsistsofaseriesofinterlinkednodes,called
Switches.
Switchesaredevicescapableofcreatingtemporaryconnections
betweentwoormoredeviceslinkedtotheswitch.
Inaswitchednetwork,someofthesenodesareconnectedtothe
communicatingdevices(e.g.telephones).Othersareusedonlyfor
routing.

Switches

Switches
Circuit-switchedNetwork
Circuitswitchingcreatesadirectphysicalconnectionbetweentwo
devicessuchasphonesorcomputers.
Acircuitswitchisadevicewithninputsandmoutputsthatcreatesa
temporaryconnectionbetweenaninputlinkandanoutputlink

Switches
PacketSwitching
Circuitswitchingwasdesignedforvoicecommunication.Inatelephone
conversation,forexample,onceacircuitisestablished,itremainsconnectedfor
thedurationofthesession.
1.Circuitswitchingislesswellsuitedtodataandothernon-voicetransmissions.
Non-voicetransmissionstendtobebursty;meaningthatdatacomeinspurt
withidlegapsbetweenthem.Whencircuit-switchedlinksareusedfordata
transmission,therefore,thelineisoftenidleanditsfacilitieswasted.
2.Asecondweaknessofcircuit-switchedconnectionsfordatatransmissionisinits
datarate.Acircuit-switchedlinkcreatestheequivalentofasinglecablebetween
twodevicesandtherebyassumeasingledatarateforbothdevices.
Thisassumptionlimitstheflexibilityandusefulnessofacircuit-switched
connectionfornetworksinterconnectingavarietyofdigitaldevices.
3.Third,circuitswitchingisinflexible.Onceacircuithasbeenestablished,that
circuitisthepathtakenbyallpartsofthetransmissionwhetheritremainsthe
mostefficient/availableornot.
Finally,circuitswitchingseesalltransmissionasequal.

Switches
Packet-switchedNetwork
Whenacomputerattemptstosendafiletoanothercomputer,thefile
isbrokenintopacketssothatitcanbesentacrossthenetworkinthe
mostefficientway.

Switches
ConnectionlessPacket-switchedNetwork
Eachpacketcontainscompleteaddressingorrouting
information(DestinationAddress,SourceAddress,Total
numberofpieces,Sequencenumber--writtenintheheader
sectionofpacket)

Switches
Connection-orientedPacket-switchedNetwork
Datapacketsaresentsequentiallyoverapredefinedroute.
Packetsareassembled,givenasequencenumberandthentransportedover
thenetworktoadestinationinorder.
Inthismode,addressinformationisnotrequired.Thisisalsoknownas
virtualcircuitswitching.

Switches
MessageswitchedNetwork
Messageswitchingisamethodinwhichthewhole
messageisstoredinaswitchandforwardedwhena
routeisavailable.

Switching andForwarding
Switch
Amechanismthatallowsusto
interconnectlinkstoforma
largenetwork
Amulti-input,multi-output
devicewhichtransferspackets
fromaninputtooneormore
outputs
Aswitchisconnectedtoasetof
linksandforeachoftheselinks,
runstheappropriatedatalink
protocoltocommunicatewith
thatnode
Adds the star topology
to the links
43

Switching andForwarding
A switch’s primary job is to receive incoming packets on one of its
links and to transmit them on some other link
This function is referred as switching or forwarding
According to OSIarchitecturethisis the
mainfunctionofthe
network layer
How does the switch decide which output port to place each packet
on?
It looks at the header of the packet for an identifier that it uses to
make the decision
Two common approaches
Datagram or Connectionless approach
Virtual circuit or Connection-oriented approach
A third approach source routing is less common
44

Switching andForwarding
packetcontains
Datagrams
Key Idea
Every
enoughinformationto
enable any switch to decide
how to get it to destination
Every packet
containsthe complete
destinationaddress
Todecidehowto
packet,a
forwarda
consults
aforwarding
switch
table(sometimes
called a routingtable)
An examplenetwork
Dest Port
-------------------
A 3
B.0
C.3
D.3
E.2
F.1
G.0
H.0
Forwarding Table
for Switch 2
45

Switching andForwarding
Characteristics of Connectionless (Datagram) Network
A host can send a packet anywhere at any time, since any packet that turns
up at the switch can be immediately forwarded using the forwarding table
When a host sends a packet, it does NOT know if the network is capable
of delivering it or if the destination host is even up and running
Each packet is forwarded independently of previous packets that might
have been sent to the same destination.
ThustwosuccessivepacketsfromhostA to
hostB mayfollow completely different paths
Aswitchorlinkfailuremightnothaveanyseriouseffecton
communicationifitispossibletofindanalternateroutearoundthefailure
andupdatetheforwardingtableaccordingly
Virtual Circuit Switching (connection-oriented)
Uses the concept of virtual circuit (VC)
First set up a virtual connection from the source host to the destination host
and then send the data
46

Switching andForwarding
Two-stage process
Connection setup
Data Transfer
Host A wants to send
packets to host B
Connection setup
Establish“connectionstate”ineachoftheswitches
betweenthesourceanddestinationhosts
Theconnectionstateforasingleconnectionconsistsofan
entryinthe“VCtable”ineachswitchthroughwhichthe
connectionpasses
47

Switching andForwarding
Characteristics of VC
SincehostAhastowaitfortheconnectionrequesttoreachthefarsideofthenetwork
andreturnbeforeitcansenditsfirstdatapacket,thereisatleastoneRTTofdelay
beforedataissent
WhiletheconnectionrequestcontainsthefulladdressforhostB(whichmightbequite
large,beingaglobalidentifieronthenetwork),eachdatapacketcontainsonlyasmall
identifier,whichisonlyuniqueononelink.
Thus the per-packet overhead caused by the header is reduced relative to the datagram model
Ifaswitchoralinkinaconnectionfails,theconnectionisbrokenandanewonewill
needtobeestablished.
Also the old one needs to be torn down to free up table storage space in the switches
Theissueofhowaswitchdecideswhichlinktoforwardtheconnectionrequestonhas
similaritieswiththefunctionofaroutingalgorithm
Comparison with the Datagram Model
Datagramnetworkhasnoconnectionestablishmentphaseandeachswitchprocesses
eachpacketindependently
Each arriving packet competes with all other packets for buffer space
If there are no buffers, the incoming packet must be dropped
48

Switching andForwarding
Good Properties of VC
By the time the host gets the go-ahead to send data, it knows quite a lot about the
network-
For example, that there is really a route to the receiver and that the receiver is
willing to receive data
It is also possible to allocate resources to the virtual circuit at the time it is established
X.25 network ( an early virtual-circuit-based networking technology but now
largely obsolete) allocates buffers per VC
In VC, we could imagine providing each circuit with a different quality of service (QoS)
The network gives the user some kind of performance related guarantee
Switches set aside the resources they need to meet this guarantee
For example, a percentage of each outgoing link’s bandwidth
Delay tolerance on each switch
Most popular examples of VC technologies are X.25, Frame Relay and ATM
However, with the success of the Internet’s connection-less model, none of them enjoys
great popularity today
49

Switching and Bridging
•BRIDGES
•Aclassofswitchthatisusedtoforwardpacketsbetween
shared-mediaLANssuchasEthernet.Suchswitchesare
sometimesknownbytheobviousnameofLANswitches;
historicallytheyhavealsobeenreferredtoasbridges.
•ItisanodethatforwardframesfromoneEthernettothe
other.Thisnodewouldbeinpromiscuousmode,accepting
allframestransmittedoneitheroftheEthernets,soitcould
forwardthemtotheother.Abridgeisconnectedbetween
twoLANswithport.
•Byusingtheportnumber,theLANsareaddressed.
•ConnectedLANsareknownasextendedLAN.

Switching and Bridging
•FunctionsofBRIDGES
•Bridgescandividethelargenetworkintosmallersegments.
•Abridgeoperatesinboththephysicallayerandthedatalink
layer.
•Asaphysicallayerdevice,itregeneratesthesignalitreceives.
•Asadatalinklayerdevice,thebridgecancheckthephysical
(MAC)addresses(sourceanddestination)containedinthe
frame.
•Bridgeswillkeepthetrafficofeachsegmentseparately.
•Bridgescancontrolthecongestionandisolatetheproblem
links.

Switching andForwarding
ATM (Asynchronous TransferMode)
Most well-known VC-based networkingtechnology
Somewhat pasts its peak in terms ofdeployment
Was important in the 1980s and early1990s
High-speed switchingtechnology
Was thought of to take over theworld
Connection-oriented packet-switchednetwork
Packets are calledcells
5 byte header + 48 bytepayload
Fixed length packets are easier to switch inhardware
Simpler todesign
ATM
VPI: Virtual PathIdentifier
CLP: Cell LossPriority
GFC: Generic Flow Control (notused)
VCI: Virtual CircuitIdentifier
(VPI + VCI together makes the VC number we talkedabout)
Type: management,congestion controlHEC: Header Error Check(CRC-8)
50

Source Routing
Alltheinformationaboutnetworktopologythatis
requiredtoswitchapacketacrossthenetworkis
providedbythesourcehost
Notes on Source Routing
Assumes that the source host knows enough about the
topology of the network
Analogous the problem of building the forwarding
tables in datagram networks or
figuring out where to send a setup packet in a virtual
circuit network
Wecannotpredicthowtheheaderneedstobe(#of
switchesinthepath)
Can be usedin both
datagramand virtualcircuit
networks
Forexample,IP,whichisadatagramprotocolincludesa
sourcerouteoptionthatallowsselectedpacketstobesource
routed.
Switching andForwarding
51

Bridges and LANSwitches
Bridges and LAN Switches
Class of switches that is used to forward packets between shared-media LANs such as
Ethernets
Known as LAN switches
Referred to as Bridges
Suppose you have a pair of Ethernets that you want to interconnect
One approach is put a repeater in between them
It might exceed the physical limitation of the Ethernet
No more than four repeaters between any pair of hosts
No more than a total of 2500 m in length is allowed
An alternative would be to put a node between the two Ethernets and have the node forward
frames from one Ethernet to the other
This node is called a Bridge
A collection of LANs connected by one or more bridges is usually said to form an Extended LAN
Simplest Strategy for Bridges
Accept LAN frames on their inputs and forward them out to all other outputs
Used by early bridges
Learning Bridges
Observe that there is no need to forward all the frames that a bridge receives
52

Consider the followingfigure
When a frame from host A that is addressed to host B arrives on port 1,there
is no need for the bridge to forward the frame out over port2.
How does a bridge come to learn on which port the various hostsreside?
Solution
Download a table into thebridge
Who does thedownload?
Human
Too much work formaintenance
Bridges and LANSwitches
Host Port
--------------------
A 1
B 1
C 1
X 2
Y 2
Z 2
53

Bridges and LANSwitches
Can the bridge learn this information by itself?
Yes
How
Each bridge inspects the source address in all the frames it receives
Record the information at the bridge and build the table
When a bridge first boots, this table is empty
Entries are added over time
A timeout is associated with each entry
The bridge discards the entry after a specified period of time
To protect against the situation in which a host is moved from one network to
another
Ifthebridgereceives a framethatis
addressedto hostnot currently in the table
Forward the frame out on all other ports
54

Bridges and LANSwitches
Strategy works fine if the extended LAN does not have aloop
init
Why?
Frames potentially loop through the extended LANforever
Bridges B1, B4, and B6 form aloop
55

Bridges and LANSwitches
How does an extended LAN come to have a loop in it?
Network is managed by more than one administrator
Forexample, it spansmultiple
departmentsin an
organization
Itis possible thatno singleperson
knowstheentire configuration of the network
A bridge that closes a loop might be added without anyone knowing
toprovideLoopsarebuiltintothenetwork
redundancy in case of failures
Solution
Distributed Spanning Tree Algorithm
56

Spanning TreeAlgorithm
Think of the extended LAN as being represented by a graph that
possibly has loops (cycles)
A spanning treeis a sub-graphof this
graphthatcoversallthe vertices but contains no
cycles
Spanning treekeepsallthevertices of
theoriginal graphbut throws out some of the edges
Example of (a) a cyclic graph; (b) a corresponding spanningtree.
57

Spanning TreeAlgorithm
Developed by Radia Perlman at Digital
A protocol used by a set of bridges to agree upon a spanning
tree for a particular extended LAN
IEEE802.1specificationforLANbridgesis
basedon this algorithm
Each bridge decides the ports over which it is and is not willing
to forward frames
In a sense the extended LAN is reduced to an acyclic tree
Details are NOT required for the exam purposes
Take point: Spanning Tree Algorithm removes the cycles/loops
from the extended (bridged) LANs
58

Limitation ofBridges
Donotscale
Spanningtreealgorithmdoesnotscale
Broadcastdoesnotscale
Nodesgetbotheredwithtoomanybroadcaststhatthe
bridgesforwardtoALLnodes
Donotaccommodateheterogeneity
EthernetwithEthernet,Wi-FiwithWi-Fi,etc.
Asolution
VirtualLAN(VLAN)
59

Virtual LANs(VLANs)
Allow a single extended LAN to be partitioned into
several logical LANs
Each VLAN is assigned an ID (or color)
Frames can only be travel between LANs segments
within the same VLAN
Partiallysolvesthebroadcastproblemin
theextended LAN
One Attractive feature of VLANs is
Wecanchange thelogicaltopology
oftheextended LAN without moving/changing
any wire or addresses
Just change the Bridge configuration
60

Virtual LANs(VLANs)
WhenaframefromXarrivesatbridgeB2,thebridgeobservesthat
itcameinaportthatwasconfiguredasbeinginVLAN100,soit
insertsaVLANheader(hastheVLANID)betweentheEthernet
headeranditspayload
WhentheframearrivesatB1,itwillonlyforwardittotheportof
VLAN100andnottoVLAN200
The link between B1 and B2 is considered to be in both VLANs
61

Computer Networks Unit 2 UNIT II DATA-LINK LAYER & MEDIA ACCESS

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Computer Networks Unit 2 UNIT II DATA-LINK LAYER &amp; MEDIA ACCESS

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77

Slide 78

Slide 79

Computer Networks Unit 2 UNIT II DATA-LINK LAYER & MEDIA ACCESS