Chapter4+The+Medium+Access+Control+Subayer.ppt

Chapter 4 The Medium Access Control Sublayer,College of Computer Science Chongqing University,Medium Access Control,Networks can be divided into point-to-point connections and multiaccess(broadcast)channels.In broadcast network,the key issue is how to determine who gets to use the channel.The protocols used to determine who goes next on a multiaccess channel belong to a sublayer of the data link layer called the MAC(Medium Access Control)sublayer.介质访问（控制）子层 The MAC sublayer is especially important in LANs,many of which use a multiaccess channel.WANs,in contrast,use point-to-point links,except for satellite networks.,The MAC Sublayer,Responsible for deciding who sends next on a multi-access linkAn important part of the link layer,especially for LANs,MAC is in here!,Contents,4.1 The Channel Allocation Problem4.2 Multiple Access Protocols4.3 Ethernet4.4 Ethernet Switch technology4.5 Wireless LANs4.6 Summary,4.1 The Channel Allocation Problem,Shared Wired Cabled Ethernet,Shared RF/Wireless802.11 WiFi,Shared RF/WirelessSatellite,Radio frequency is a shared medium,multiple users are using the same spectrum(e.g.800-825MHz),Network Links(1)point-to-point Link(2)multiaccess(broadcast)channels,shared wire or medium,Features of broadcast channels(1)a single shared channel is used by all nodes,multiple sending and receiving nodes(2)two or more simultaneous transmissions by nodes:interference-collision if node receives two or more signals at the same time(3)usually,all nodes are equal to each other,The multi-access problem:In a single channel broadcast network,When multiple nodes try to send messages simultaneously,who has the right to use the channel?,Solution:Multi Access Protocols:the protocols used to solve the multi-access problem,The multi-access problem:How to let distributed users(efficiently)share a single broadcast channel?,The multi-access problem:How to form a access queue for distributed users?The queueing theory can be use to efficiency of various multi-access protocols,The multi-access Problem,Multiple access protocols,FDMA,TDMA,CDMA,Controlled-access protocol,Static model,Dynamic model,WDMA,switching,Random AccessProtocol,Multiplexing allows several transmission sources to share a larger transmission capacity.Often used in hierarchical structures.Multiple access:two or more simultaneous transmissions share a broadcast channel.Often used in access networks,4.2 Multiple Access Protocol,Limited-ContentionProtocol,One-bit map,Binary Countdown,Tree walk,8,Ideal Multiple Access Protocol,Broadcast channel of rate R bpsWhen one node wants to transmit,it can send at rate R.When M nodes want to transmit,each can send at average rate R/MFully decentralized:no special node to coordinate transmissionsno synchronization of clocks,slotsSimple,Channel Partitioningdivide channel into smaller“pieces”(time slots,frequency,code)allocate piece to node for exclusive use,Multiplexing:allows several transmission sources to share a larger transmission capacity.Often used in hierarchical structures.Multiple access:two or more simultaneous transmissions share a broadcast channel Often used in access networks,FDM:Frequency Division Multiplexing(FDMA:frequency division multiple access)Each node has a frequency bandTDM:Time Division Multiplexing(TDMA:time division multiple access)Each node has a series of fixed time slotsWDM:Optical-domain version of FDM,wavelength division multiplexing Code Division Multiple Access(CDMA)each node has a different code,4.2.1 Static channel allocation,Independent traffic.N independent nodes generate frames for transmission.The probability of a frame being generated in an interval of length t is t,where is a constant(the arrival rate of new frames).Single Channel.No external way to coordinate sendersObservable Collision.All nodes can detect collisions.A collided frame must be transmitted again later.There are no errors.4a.Continuous Time.4b.Slotted Time.Time is divided into discrete intervals(slots).Frame transmissions always begin at the start of a slot.5a.Carrier Sense.Nodes can tell if the channel is in use before trying to use it.5b.No Carrier Sense.Nodes cannot sense the channel.,4.2.2 dynamic channel allocation,five key assumptions,4.2.3 Random Access Protocol,FeaturesNo node is superior to another nodeNo node is assigned the control over another.No node permits,or does not permit,another station to sendAt each instance,a node that has data to send uses a procedure defined by the protocol to make a decision on whether or not to send.random access:there is no scheduled time for a node to transmit.Transmission is random among the nodescontention methods(Collision):no rules specify which node should send next.nodes compete with one another to access the medium.,Considerations for random access protocol When can the node access the medium?What can the node do if the medium is busy?How can the node determine the success or failure of the transmission?What can the node do if there is an access conflict?,ALOHA:uses MA(Multiple Access)No carrier sensepure-ALOHAslotted ALOHACSMA:Carrier Sense Multiple AccessCSMA/CD:Collision Detection,used in classical EthernetCSMA/CA:Collision Avoidance,used in wireless channel,Evolution of random-access methods,Random Access Protocol,4.2.3.1 ALOHA(pure ALOHA),the earliest random access method for ALOHA System(ALOHANET)be developed at the University of Hawaii in early 1970.ALOHA System was designed to Use the lost-cost commercial radio equipment to connect the central computer on Oahu island with the consoles on the other islands(4 islands,7 campuses)it can be used on any shared medium.The original ALOHA protocol is called pure ALOHA.This is simple,but elegant protocol.,ALOHA Protocols,Anyone may transmit whenever they want(Continuous time model.)Each node waits for the acknowlwdge packet when a packet is sent out.if node has received the postive acknowledge packet,then it sends the next packetthis process is repeated until a successful transmission and acknowledgement occurs or until the process is terminated by the users console,Operation in ALOHA,errors:(1)random noise errors and(2)errors caused by interference with a packet sent by other consoles,collision in ALOHA,Vulnerable time is 2T,15,Slotted ALOHA,Assumptionsall frames same sizetime is divided into equal size slots,time to transmit 1 framenodes start to transmit frames only at beginning of slotsnodes are synchronizedif 2 or more nodes transmit in slot,all nodes detect collision,Operationwhen node obtains fresh frame,it transmits in next slotno collision,node can send new frame in next slotif collision,node retransmits frame in each subsequent slot with prob.p until success,Problem in pure ALOHA Problem 1:collision occurs at any time Solution:slotted time model any other problems?,Prossingle active node can continuously transmit at full rate of channelhighly decentralized:only slots in nodes need to be in syncsimple,Conscollisions,wasting slotsidle slotsnodes may be able to detect collision in less than time to transmit packetclock synchronization,Slotted ALOHA,Throughput versus offered traffic for ALOHA systems,At best for Pure ALOHA:channel used for useful transmissions 18%of time!,At best for Slotted ALOHA:channel used for useful transmissions 37%of time!,Performance of ALOHA,4.2.3.2 CSMA(carrier sense multiple access),Principle:sense before transmit or listen before talkIf channel sensed idle:transmit entire frameIf channel sensed busy,defer transmission Advantages:CSMA can reduce the possibility of collision,but cant eliminate it,Problem in ALOHA Problem 2:sender doesnt know the status of the channel when it tries to send data out Solution:detect the channel,sense the carrier any other problems?,At time t1,node B senses the medium and finds it idle,so it sends a frame.At time t2(t2 t1),node C senses the medium and finds it idle because,at this time,the first bits from node B have not reached node C.node C also sends a frame.The two signals collide and both frames are destroyed.,Collision in CSMA,Vulnerable Time(collision time)The vulnerable time for CSMA is the propagation time Tp.A collision will result if a node is ending a frame and any other node tries to send a frame during Tp simultaneously After the Tp,every node will already have heard the bit and will refrain from sending.,Vulnerable Time in CSMA,persistent vs.non-persistent CSMA,RandomAccess,No CarrierSense,CSMA,Persistant,Summary：CSMA,PureALOHO,SlottedALOHO,Non-Persistant,1-Persistant,p-Persistant,CSMA improves on ALOHA by sensing the channel!User doesnt send if it senses someone elseVariations on what to do if the channel is busy:1-persistent(greedy)sends as soon as idleNonpersistent waits a random time then tries againp-persistent sends with probability p when idle,Comparison of the channel utilization versus load for various random access protocols,Collision problem in CSMA:A collision will result during the vulnerable time(propagation time),it will waste the bandwidth to send data continually if collision occursHow to solve this problem?CD:collision detection,4.2.3.3 CSMA/CD,Flash,Collision of the first bit in CSMA/CD,Collision and abortion in CSMA/CD,Collision and abortion in CSMA/CD,If the two nodes involved in a collision are the maximum distance apart,the signal from the first takes time to reach the second,and the effect of the collision takes another time to reach the first.So the requirement is that the first node must still be transmitting after 2.,Minimum Frame Size is necessary in CSMA/CD,Minimum Frame Size=2 Ts(transmission rate),1 km,A,B,t,t=B sends data when idle,t=/2Collision,A,B,A,B,t=0 A sends datawhen idle,A,B,t=0,A,B,Tp=,CSMA/CD can be in one of three states:contention,transmission,or idle.,CSMA/CD improvement is to detect/abort collisions-Reduced contention times improve performance,Collision time is much shorter than frame time,4.2.3.4 wireless protocol,Question:Can we apply media access methods from fixed networks in wireless network?for example,can the CSMA/CD be used in the wireless LAN network?,Wireless has complications compared to wired.Nodes may have different coverage regionsLeads to hidden and exposed terminalsNodes cant detect collisions,i.e.,sense while sendingMakes collisions expensive and to be avoided,Hidden terminals 隐蔽站A sends to B,C cannot receive A C wants to send to B,C senses a“free”medium(CS fails)collision at B,A cannot receive the collision(CD fails)A is“hidden”for C,hidden and exposed terminals in wireless LAN,3.2.1,hidden and exposed terminals in wireless LAN,Exposed terminals暴露站B sends to A,C wants to send to another terminal(not A or B)C has to wait,CS signals a medium in usebut A is outside the radio range of C,therefore waiting is not necessaryC is“exposed”to B,MACA(Multiple Access with Collision Avoidance),MACA uses short signaling packets for collision avoidanceRTS(request to send):a sender request the right to send from a receiver with a short RTS packet before it sends a data packetCTS(clear to send):the receiver grants the right to send as soon as it is ready to receiveSignaling packets containsender addressreceiver addresspacket size(indicates the transmission time between sender and receiver)Variants of this method can be found in IEEE802.11 as DFWMAC(Distributed Foundation Wireless MAC),MACA avoids the problem of hidden terminalsA and C want to send to BA sends RTS(Request To Send)firstC waits after receiving CTS(Clear To Send)from BMACA avoids the problem of exposed terminalsB wants to send to A,C to another terminalnow C does not have to wait for it cannot receive CTS from A,MACA examples,4.2.4 Controlled Access Protocol,In controlled access,the stations consult one another to find which station has the right to send.A station cannot send unless it has been authorized by other stations.Usually,controlled access protocol is a collision-free protocol,Reservation for example:a bit-map protocol,binary countdown protocolPollingToken Passing,Basic Idea:a node needs to make a reservation before sending data.Each contention period consists of N slots(N nodes).If node i have a frame to send,it transmits a 1 bit during the slot.After all N slots passed by,each node has the knowledge of which node wishes to transmit the frame.Then frames transmission can be conducted in order,One-bit map protocol:reservation protocol,Binary Countdown,Basic idea Stations send their address in contention slot(log N bits instead of N bits)Medium ORs bits;stations give up when they send a“0”but see a“1”Station that sees its full address is next to send,.A dash indicates silence,Problem in One-bit map protocol it does not scale will to the networks with thousands of nodes because of the extra token 1 for each node,one primary node+many secondary nodes.All data exchanges must be made through the primary device even when the ultimate destination is a secondary device.The primary node controls the link;the secondary nodes follow its instructions.It is up to the primary device to determine which device is allowed to use the channel at a given time.,Polling,Flash,token-passing,The nodes in a network are organized in a logical ring,for each node,there is a predecessor and a successorThe token will be passed to the successor when the current node has no more data to send,For physical ring,the token does not have to have the addressFor the dual ring,main token+second token(for emergencies only),Used in FDDIFor Bus ring,the token has to have the addressFor Star ring,it makes the network less prone to failure,used in IBM Token-ring LAN,Flash,4.2.5 Limited-Contention protocols,Contention protocol(1)work well with the light load(2)wok badly with the high loadContention-free protocol(1)work well with the high load(2)wok badly with the light load,Problem How to combine the two ways togetherSolution Limited-Contention protocols,Each node has probability p to transmit frameThen Probability Ps that some node successfully acquires the channel during a given slot is given by kp(1-p)k-1.The best value of p is 1/k,Analysis of successful transmission,Acquisition probability for a symmetric contention channel,Problem:how to get the high acquisition probability?Solution:divided the nodes into groups,members in a group can contend the given slotExample:(1)each group has only node,such as the Binary Countdown protocol(2)each group contains all nodes,such as the ALOHA(3)Good:assign nodes to slot dynamically.Many nodes per slot when load is light.Few nodes per slot when load is high,Limited-Contention protocols,Already too many contenders for a good chance of one winner,Tree divides stations into groups(nodes)to pollDepth first search under nodes with poll collisionsStart search at lower levels if 1 station expected,