MEDIA ACCESS CONTROL
• RandomAccessProtocols
• ControlledAccessProtocols
Copyright By PowCoder代写 加微信 powcoder
• ChannelizedAccessProtocols
Media Access Control (MAC)
• Whennodesorstationsareconnectedandusea common link, called a multipoint or broadcast link, we need a multiple-access protocol to coordinate access to the link
• Theproblemofcontrollingtheaccesstothemediumis similar to the rules of speaking in an assembly
• Manyprotocolshavebeendevisedtohandleaccesstoa shared link. All of these protocols belong to a sublayer in the data-link layer called media access control (MAC).
Multiple Access Protocols
Random Access
• Inrandomaccessorcontentionmethods,nostationis superior to another station and none is assigned the control over another.
• Thereisnoscheduledtimeforastationtotransmit. Transmission is random among the stations. That is why these methods are called random access.
• Norulesspecifywhichstationshouldsendnext. Stations compete with one another to access the medium. That is why these methods are also called contention methods
Random Access
• Inarandom-accessmethod,eachstationhastheright to the medium without being controlled by any other station.
• Ifmorethanonestationtriestosend,thereisan access conflict—collision—and the frames will be either destroyed or modified.
Random Access
• Toavoidaccessconflictortoresolveitwhenithappens, each station follows a procedure that answers the following questions:
❑ When can the station access the medium?
❑ What can the station do if the medium is busy?
❑ How can the station determine the success or failure of the transmission?
❑ What can the station do if there is an access conflict?
Pure ALOHA
• ALOHA,theearliestrandomaccessmethod,was developed at the University of Hawaii in early 1970
• Itwasdesignedforaradio(wireless)LAN,butitcanbe used on any shared medium
• TheoriginalALOHAprotocoliscalledpureALOHA
• Eachstationsendsaframewheneverithasaframeto send, it expects the receiver to send an acknowledgment. If the acknowledgment does not arrive after a time-out period, the station assumes that the frame (or the acknowledgment) has been destroyed and resends the frame
Pure ALOHA
Pure ALOHA
• Acollisioninvolvestwoormorestations.Ifallthese stations try to resend their frames after the time-out, the frames will collide again.
• PureALOHAdictatesthatwhenthetime-outperiod passes, each station waits a random amount of time before resending its frame.
• Therandomnesswillhelpavoidmorecollisions.Wecall this time the backoff time TB
• Thetime-outperiodisequaltothemaximumpossible round-trip propagation delay, which is twice the amount of time required to send a frame between the two most widely separated stations (2Tp)
Pure ALOHA
• The backoff time TB is a random value that normally depends on K (the number of attempted unsuccessful transmissions).
• The formula for TB depends on the implementation.
• Onecommonformulaisthebinaryexponentialbackoff. In this method, a multiplier R in the range [0, 2K−1] is randomly chosen and multiplied by:
– Tp (maximum propagation time) or
– Tfr (the average time required to send out a frame)
– TB =RTp orTB =RTfr
– the range of the random numbers increases after each collision. The value of Kmax is usually 15
Pure ALOHA
• ThestationsonawirelessALOHAnetworkarea maximum of 600 km apart. If we assume that signals propagate at 3 × 108 m/s, we find
– Tp =(600×103)/(3×108)=2ms
– ForK=2,therangeofRis{0,1,2,3}.
– ThismeansthatTB canbe0,2,4,or6ms,basedon the outcome of the random variable R
Vulnerable time
Vulnerable time
• vulnerabletimeisthelengthoftimeinwhichthereisa possibility of collision.
• Weassumethatthestationssendfixed-lengthframes with each frame taking Tfr seconds to send
• Pure ALOHA vulnerable time = 2Tfr
• ApureALOHAnetworktransmits200-bitframesona shared channel of 200 kbps. What is the requirement to make this frame collision-free?
• Solution: Average frame transmission time
– Tfr is 200 bits/200 kbps = 1 ms.
– Thevulnerabletimeis2×1ms=2ms.
– This means no station should send later than 1 ms before this station starts transmission and no station should start sending during the period (1 ms) that this station is sending.
Throughput
• Throughputisthenumberofframessuccessfully transmitted in a unit time
• LetuscallGtheaveragenumberofframesgenerated by the system during one frame transmission time.
• Itcanbestatisticallyproventhattheaverageratioof successfully transmitted frames for pure ALOHA S is
– S=G×e−2G.
– The maximum throughput Smax is 0.184, for G = 1⁄2
– WecanfinditbysettingthederivativeofSwith respect to G to 0
Throughput
• WeexpectG=1⁄2toproducethemaximumthroughput because the vulnerable time is 2 times the frame transmission time. Therefore, if a station generates only one frame in this vulnerable time (and no other stations generate a frame during this time), the frame will reach its destination successfully
• ApureALOHAnetworktransmits200-bitframesona shared channel of 200 kbps. What is the throughput if the system (all stations together) produces 1000 frames per second?
• Solution: The frame transmission time is
– 200 bit/200 kbps = 1 ms
– G=1000frame/secx1ms=1
– average ratio of successfully transmitted frames
S = G × e−2G = 0.135 (13.5%)
– This means that the throughput is 1000 × 0.135 = 135 frames. Only 135 frames out of 1000 will probably survive
• ApureALOHAnetworktransmits200-bitframesona shared channel of 200 kbps. What is the throughput if the system (all stations together) produces 500 frames per second?
• Solution: The frame transmission time is
– 200 bit/200 kbps = 1 ms
– G=500frame/secx1ms=0.5
– average ratio of successfully transmitted frames
S = G × e−2G = 0.184 (18.4%)
– This means that the throughput is 500× 0.184 = 92 frames. Only 92 frames out of 500 will probably survive
• ApureALOHAnetworktransmits200-bitframesona shared channel of 200 kbps. What is the throughput if the system (all stations together) produces 250 frames per second?
• Solution: The frame transmission time is
– 200 bit/200 kbps = 1 ms
– G=250frame/secx1ms=0.25
– average ratio of successfully transmitted frames
S = G × e−2G = 0.152 (15.2%)
– This means that the throughput is 250× 0.152 = 38 frames. Only 38 frames out of 250 will probably survive
Slotted ALOHA
• SlottedALOHAwasinventedtoimprovetheefficiencyof pure ALOHA.
• InslottedALOHAwe
– divide the time into slots of Tfr seconds and
– force the station to send only at the beginning of the time slot
Slotted ALOHA
Vulnerable time
• Becauseastationisallowedtosendonlyatthe beginning of the synchronized time slot, if a station misses this moment, it must wait until the beginning of the next time slot.
• Thismeansthatthestationwhichstartedatthe beginning of this slot has already finished sending its frame
• thereisstillthepossibilityofcollisioniftwostationstry to send at the beginning of the same time slot
• Thevulnerabletimeisnowreducedtoone-half,equal to Tfr
Vulnerable time
Throughput
• Itcanbeproventhattheaveragenumberofsuccessful transmissions for slotted ALOHA is
– The maximum throughput Smax is 0.368, when G = 1
– WecanfinditbysettingthederivativeofSwith respect to G to 0
• AslottedALOHAnetworktransmits200-bitframesona shared channel of 200 kbps. What is the throughput if the system (all stations together) produces 1000 frames per second?
• Solution: The frame transmission time is
– 200 bit/200 kbps = 1 ms
– G=1000frame/secx1ms=1
– average ratio of successfully transmitted frames
S = G × e−G = 0.368 (36.8%)
– This means that the throughput is 1000 × 0.368 = 368 frames. Only 368 frames out of 1000 will probably survive.
• AslottedALOHAnetworktransmits200-bitframesona shared channel of 200 kbps. What is the throughput if the system (all stations together) produces 500 frames per second?
• Solution: The frame transmission time is
– 200 bit/200 kbps = 1 ms
– G=500frame/secx1ms=0.5
– average ratio of successfully transmitted frames
S = G × e−G = 0.303 (30.3%)
This means that the throughput is 500 × 0.0303 = 151 frames. Only 151 frames out of 500 will probably survive
• AslottedALOHAnetworktransmits200-bitframesona shared channel of 200 kbps. What is the throughput if the system (all stations together) produces 250 frames per second?
• Solution: The frame transmission time is
– 200 bit/200 kbps = 1 ms
– G=250frame/secx1ms=0.25
– average ratio of successfully transmitted frames
S = G × e−G = 0.195 (19.5%)
– This means that the throughput is 250 × 0.195 = 49. Only 49 frames out of 250 will probably survive
Carrier sense multiple access CSMA
• Carrier sense multiple access (CSMA) was developed to minimize the chance of collision and increase performance
• CSMAisbasedontheprinciple“sensebeforetransmit” or “listen before talk”
• CSMAcanreducethepossibilityofcollision,butit cannot eliminate it
Carrier sense multiple access CSMA
• Thepossibilityofcollisionstillexistsbecauseof propagation delay; when a station sends a frame, it still takes time (although very short) for the first bit to reach every station and for every station to sense it
• Astationmaysensethemediumandfinditidle,only because the first bit sent by another station has not yet been received
Carrier sense multiple access CSMA
• Attimet1,stationBsensesthemediumandfindsit idle, so it sends a frame.
• Attimet2(t2>t1),stationCsensesthemediumand finds it idle because, at this time, the first bits from station B have not reached station C.
• StationCalsosendsaframe.Thetwosignalscollide and both frames are destroyed
Vulnerable Time
• ThevulnerabletimeforCSM .
• Thisisthetimeneededforasignaltopropagatefrom one end of the medium to the other.
Persistence Methods
• Whatshouldastationdoifthechannelisbusy?
• Whatshouldastationdoifthechannelisidle?
• Threemethodshavebeendevisedtoanswerthese questions:
– the 1-persistent method,
– the non-persistent method, and – the p-persistent method.
Persistence Methods
Persistence Methods – 1-Persistent
• The1-persistentmethodissimpleandstraightforward.
• Afterthestationfindsthelineidle,itsendsitsframe immediately (with probability 1).
• Thismethodhasthehighestchanceofcollisionbecause two or more stations may find the line idle and send their frames immediately.
Persistence Methods – Non-persistent
• Inthenonpersistentmethod,astationthathasaframe to send senses the line.
• Ifthelineisidle,itsendsimmediately.
• Ifthelineisnotidle,itwaitsarandomamountoftime and then senses the line again.
• Thisapproachreducesthechanceofcollisionbecauseit is unlikely that two or more stations will wait the same amount of time and retry to send simultaneously.
• Reducestheefficiencyofthenetworkbecausethe medium remains idle when there may be stations with frames to send
Persistence Methods – p-Persistent
• Thep-persistentmethodisusedifthechannelhastime slots with a slot duration equal to or greater than the maximum propagation time.
• Thep-persistentapproachcombinestheadvantagesof the other two strategies
• Itreducesthechanceofcollisionandimproves efficiency
Persistence Methods – p-Persistent
• afterthestationfindsthelineidleitfollowsthesesteps:
1. Withprobabilityp,thestationsendsitsframe
2. Withprobabilityq=1−p,thestationwaitsforthe beginning of the next time slot and checks the line again
a. Ifthelineisidle,itgoestostep1.
b. Ifthelineisbusy,itactsasthoughacollision has occurred and uses the backoff procedure
• TheCSMAmethoddoesnotspecifytheprocedure following a collision. Carrier sense multiple access with collision detection (CSMA/CD) augments the algorithm to handle the collision
• Astationmonitorsthemediumafteritsendsaframe
– if the transmission was successful, the station is finished.
– If there is a collision, the frame is sent again
CSMA/CD Minimum Frame Size
• ForCSMA/CDtowork,weneedarestrictiononthe frame size
• Beforesendingthelastbitoftheframe,thesending station must detect a collision, if any, and abort the transmission. This is so because the station, once the entire frame is sent, does not keep a copy of the frame and does not monitor the line for collision detection
• The frame transmission time Tfr must be at least two times the maximum propagation time Tp
– Tfr ≥ 2Tp
• AnetworkusingCSMA/CDhasabandwidthof10Mbps. If the maximum propagation time (including the delays in the devices and ignoring the time needed to send a jamming signal) is 25.6 μs, what is the minimum size of the frame?
• Solution: The minimum frame transmission time
– Tfr =2×Tp =51.2μs.
– This means, in the worst case, a station needs to transmit for a period of 51.2 μs to detect the collision.
– The minimum size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64 bytes
Flow diagram for the CSMA/CD
CSMA/CD Procedure
• TheCSMA/CDProcedureissimilartotheoneforthe ALOHA protocol, but there are differences
1. theadditionofthepersistenceprocess.Weneedto sense the channel before we start sending the frame by using one of the persistence processes (nonpersistent, 1-persistent, or p-persistent)
2. InALOHA,wefirsttransmittheentireframeand then wait for an acknowledgment. In CSMA/CD, transmission and collision detection are continuous processes. We do not send the entire frame and then look for a collision. The station transmits and receives continuously and simultaneously (using two different ports or a bidirectional port).
CSMA/CD Procedure
• TheCSMA/CDProcedureissimilartotheoneforthe ALOHA protocol, but there are differences
3. Sendingofashortjammingsignaltomakesure that all other stations become aware of the collision
Collision Detection
• Thelevelofenergyinachannelcanhavethreevalues:
– zero level, the channel is idle.
– normal level, a station has successfully captured the channel and is sending its frame.
– abnormal level, there is a collision and the level of the energy is twice the normal level.
• Astationmonitorstheenergyleveltodetermineifthe channel is idle, busy, or in collision mode
Throughput
• ThethroughputofCSMA/CDisgreaterthanthatofpure or slotted ALOHA.
• Themaximumthroughputoccursatadifferentvalueof G and is based on the persistence method and the value of p in the p-persistent approach.
• Forthe1-persistentmethod,themaximumthroughput is around 50 percent when G = 1.
• Forthenonpersistentmethod,themaximum throughput can go up to 90 percent when G is between 3 and 8.
• Carriersensemultipleaccesswithcollisionavoidance
(CSMA/CA) was invented for wireless networks
• CollisionsareavoidedthroughtheuseofCSMA/CA’s
three strategies:
– the inter-frame space,
– the contention window, and – acknowledgments
• Inter-frame Space (IFS):
– collisions are avoided by deferring transmission even if the channel is found idle.
– the station does not send immediately when it sense the channel idle. It waits for a period of time called the interframe space or IFS
– The IFS time allows the front of a transmitted signal by a distant station , if one exists, to reach this station
– IFS variable can also be used to prioritize stations or frame types
• Contention Window:
– After waiting an IFS time, if the channel is still idle, the station can send, but it still needs to wait a time equal to the contention window
– contention window is an amount of time divided into slots. A station that is ready to send chooses a random number of slots as its wait time
– Thenumberofslotsinthewindowchanges according to the binary exponential backoff strategy
– thestationneedstosensethechannelaftereach time slot. If the station finds the channel busy, it does not restart the process; it just stops the timer and restarts it when the channel is sensed as idle
• Acknowledgment:
– there still may be a collision resulting in destroyed data, or the data may be corrupted during the transmission
– The positive acknowledgment and the time-out timer can help guarantee that the receiver has received the frame
CSMA/CA – Frame Exchange
CSMA/CA – Frame Exchange
Before sending a frame, the source station senses the medium by checking the energy level at the carrier frequency
Afterthestationisfoundtobeidle,thestationwaitsfor a period of time called the DCF interframe space (DIFS); then the station sends a control frame called the request to send (RTS)
Thedestinationstationsendsacontrolframe,calledthe clear to send (CTS), to the source station, After receiving the RTS and waiting a period of time called the short interframe space (SIFS)
CSMA/CA – Frame Exchange
• Thesourcestationsendsdataafterwaitinganamount
of time equal to SIFS
• Thedestinationstation,afterwaitinganamountoftime equal to SIFS, sends an acknowledgment to show that the frame has been received
CSMA /CA vs /CD
• AcknowledgmentisneededinCSMA/CAprotocol because the station does not have any means to check for the successful arrival of its data at the destination.
• ThelackofcollisioninCSMA/CDisakindofindication to the source that data have arrived
Network Allocation Vector (NAV)
• WhenastationsendsanRTSframe,itincludesthe duration of time that it needs to occupy the channel.
• Thestationsthatareaffectedbythistransmission create a timer called a network allocation vector (NAV) that shows how much time must pass before these stations are allowed to check the channel for idleness
Controlled Access
• Incontrolledaccess,thestationsconsultoneanotherto find which station has the right to send. A station cannot send unless it has been authorized by other stations.
– Reservation
– Token Passing
Reservation
• Inthereservationmethod,astationneedstomakea reservation before sending data. Time is divided into intervals. In each interval, a reservation frame precedes the data frames sent in that interval
• Pollingworkswithtopologiesinwhichonedeviceis designated as a primary station and the other devices are secondary stations. All data exchanges must be made through the primary device even when the ultimate destination is a secondary device.
Token Passing
• Inthetoken-passingmethod,thestationsinanetwork are organized in a logical ring
• foreachstation,thereisapredecessorandasuccessor
• aspecialpacketcalledatokencirculatesthroughthe
• The possession of the token gives the station the
right to access the channel and send its data.
• Whenastationhassomedatatosend,itwaitsuntilit receives the token from its predecessor. It then holds the token and sends its data. When the station has no more data to send, it releases the token, passing it to the next logical station in the ring
Token Passing
Channelization
• Channelizationisamultiple-accessmethodinwhichthe available bandwidth of a link is shared in time, frequency, or through code, between different stations. In this section, we discuss three channelization protocols.
– Frequency-Division Multiple Access (FDMA) – Time-Division Multiple Access (TDMA)
– Code-Division Multiple Access (CDMA)
Frequency-Division Multiple Access (FDMA)
Frequency-Division Multiple Access (FDMA)
• FDMAandfrequency-divisionmultiplexing(FDM) conceptually seem similar, but there are differences between them.
• FDMisaphysicallayertechniquethatcombinesthe loads from low bandwidth channels and transmits them by using a high-bandwidth channel. The channels that are combined are low-pass. The multiplexer modulates the signals, combines them, and creates a bandpass signal. The bandwidth of each channel is shifted by the multiplexer.
Frequency-Division Multiple Access (FDMA)
• FDMAandfrequency-divisionmultiplexing(FDM) conceptually seem similar, but there are differences between them.
• FDMAisanaccessmethodinthedata-linklayer.The datalink layer in each station tells its physical layer to make a bandpass signal from the data passed to it. The signal must be created in the allocated band. There is no physical multiplexer at the physical layer. The signals created at each station are automatically bandpass- filtered. They are mixed w
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com