通信网络技术课件：chapter4 The Medium Access Control Sublayer

1、Computer Networks1RoadmapIntroductionPhysical LayerData Link LayerTransport LayerNetwork LayerMedium Access SublayerApplication Layer2The Medium Access ControlSublayerChapter 43What We Will Learn In This ChapterHow to handle broadcast networks. Different from point to point networks, a major issue i

2、s handling arbitration when there is competition for the channel. The bottom sublayer of the Data Link Layer, especially relevant for LANs.4.1 The Channel Allocation Problem4.2 Multiple Access Protocols4.3 Ethernet4.4 Wireless LANs4.5 Broadband Wireless4.6 Bluetooth4.7 Data Link Layer Switching4.8 S

3、ummary44.1 The Channel Allocation ProblemStatic Channel Allocation in LANs and MANsThe traditional (phone company) way of allocating a single channel is Frequency Division Multiplexing. (See Figure) FDM works fine for limited and fixed number of users.Inefficient to divide into fixed number of chunk

4、s. May not all be used, or may need more. Doesnt handle burstiness.5Queuing Theory(M/M/1)T = mean time delay (total time cost in the system)C = capacity (bps)l = arrival frame rate (frames/sec)1/ m = mean length (bits/frame)mC = service frame rate (frame/sec) 1T = - mC - lStatic Channel Allocation I

5、n LANs And MANS6FDMNow divide this channel into N subchannels, each with capacity C/N. Input rate on each of the N channels is l /N. Now 1 NT(FDM) = - = - = NT m(C/N) - l /N mC - l7Dynamic Channel Allocation in LANs and MANsPossible underlying assumptions include: 1.Station Model.2.Single Channel As

6、sumption.3.Collision Assumption.4a Continuous Time.4b Slotted Time.5a Carrier Sense.5b No Carrier Sense.84.2 Multiple Access ProtocolsWhen station has packet to sendTransmit at full channel data rate R.No a priori coordination among stationsTwo or more transmitting stations - “collision”Random acces

7、s MAC protocol specifies: How to detect collisionsHow to recover from collisions (e.g., via delayed retransmissions)9Multiple Access ProtocolsALOHAPure ALOHASlot ALOHACarrier Sense Multiple Access ProtocolsCSMA/CDWireless LAN ProtocolsCSMA/CA10Pure ALOHAEvery station transmits whenever it wants to.

8、Colliding frames are destroyed. The sender knows if its frame got destroyed, and if so waits a random time and then retransmits.1. ANY overlap is a collision.2. Best efficiency if frames are same size.11Pure ALOHAIn pure ALOHA, frames are transmitted at completely arbitrary times.12Pure ALOHA Vulner

9、able period for the shaded frame.13N stations competing for a channel,P(success by given node) = P(station transmits) . P(no other station transmits in t0-1,t0 . P(no other station transmits in t0,t0 +1 = p . (1-p)N-1 . (1-p)N-1= p . (1-p)2(N-1) /* choosing optimum p and then letting n - infty */ =

10、1/(2e) = .18Pure ALOHA14Pure ALOHAS = frames to be transmitted. In units of frames per frame time so that 0 S 1. G = S + frames retransmitted due to previous collisions.P0 = probability that a frame does NOT suffer collision.S = P0 x GProbability that k frames are generated during a given frame time

11、 (Poisson distribution): G k e-G Prk = -, Pr0= e-G k!Probability of no traffic initiated (zero frames) during the vulnerable period (In an interval two frame times long ): P0 = e-2G soThroughput per frame time is: S = G e -2G The maximum throughput occurs at G = 0.5, with S = 1/2e, which is about 0.

12、184. 15Pure ALOHAThroughput versus offered traffic for ALOHA systems.16Slotted ALOHAAssumptionsAll frames same sizeTime is divided into equal size slots, time to transmit 1 frameStations start to transmit frames only at beginning of slotsStations are synchronizedIf 2 or more stations transmit in slo

13、t, all nodes detect collisionOperationWhen station obtains fresh frame, it transmits in next slotNo collision, station can send new frame in next slotIf collision, station retransmits frame in each subsequent slot with prob. p until success17Slotted ALOHA18Slotted ALOHAProsSingle active station can

14、continuously transmit at full rate of channelHighly decentralized: only slots in stations need to be in syncSimpleConsCollisions, wasting slotsIdle slotsNodes may be able to detect collision in less than time to Transmit packet19Slotted ALOHASuppose N stations with many frames to send, each transmit

15、s in slot with probability pprob that 1st station has success in a slot = p(1-p)N-1prob that any station has a success = Np(1-p)N-1For max efficiency with N stations, find p* that maximizes Np(1-p)N-1For many stations, take limit of Np*(1-p*)N-1 as N goes to infinity, gives 1/e = .37At best: channel

16、 used for useful transmissions 37% of time!20Carrier Sense Multiple Access ProtocolsThis is where the sender listens before ejecting something on the wire. Collision occurs when a station hears something other than what it sent.Human analogy: listen before talk, dont interrupt others!PERSISTENT AND

17、NONPERSISTENT CSMA1-persistent CSMA Non-persistent CSMA (equivalent to 0-persistent CSMA)p-persistent CSMA For slotted channels.21Carrier Sense Multiple Access Protocols1-persistent CSMA Station listens. If channel idle, it transmits. If collision, wait a random time and try again. If channel busy,

18、wait until idle.If station wants to send AND channel = idle then do send.Success here depends on transmission time - how long after the channel is sensed as idle will it stay idle (there might in fact be someone elses request on the way.)22Carrier Sense Multiple Access ProtocolsNon-persistent CSMA (

19、equivalent to 0-persistent CSMA)Same as above EXCEPT, when channel is found to be busy, dont keep monitoring to find THE instant when it becomes free. Instead, wait a random time and then sense again.Leads to 1) better utilization and 2) longer delays than 1 - persistent. 23Carrier Sense Multiple Ac

20、cess Protocolsp-persistent CSMA For slotted channels. If ready to send AND channel = idle then send with probability p, and with probability q = 1 - p defers to the next slot.24Persistent and Nonpersistent CSMAComparison of the channel utilization versus load for various random access protocols.25Ca

21、rrier sense multiple access with collision detection/CSMA/CDCSMA/CD stands for Carrier Sense Multiple Access with Collision Detection。“mulitple access” means that many computers are connected on one bus in some way.“carrier sense ” refers to that each station must check that the bus is free before s

22、ending data,if not free, then stop sending temporally,otherwise the collision will occur. In fact, there is not so-called carrier on the bus.Carrier sense means that applying some electronical tech check if there is data signal on the bus sent by other computer. 26Collision detection“collision detec

23、tion ” means that signal voltage value is measured when computer sends data.when a few stations send data to the bus simutaneously,signal voltage will be increased.when a station finds that signal voltage value surpass the threshold, that shows there are at least two stations sending data ,that is t

24、o say collision occurs.“collision ” is conflict ,so collision detection is called conflict detection sometimes.27After collision is detectedWhen collision occurs, transmitted signal on the bus get distorted seriously,useful information can not be recovered.For each station that is sending data, once

25、 collision is detected, it stops sending data immediately,then waiting a random time before sending data again, so network resource s waste can be prevented.28The effects of limited electromagnetic wave propagation speed on the bus When one station listens that the bus is free, the bus may be not fr

26、ee.The information from A to B can be transfered to B after a specified time.If B sends information before As information arrived at B , then collision must occur. The collision results in two invalid frame transmitted. 291 kmABtcollisiont = 2 A detected collision t = B sends dataB detected collisio

27、n t = t = 0one direction propagation timedelay 301 kmABtcollisiont = B detected channel is free,it began to send datat = / 2collision occuredt = 2 A detected collision t = sends data B B detected collision t = ABABAB t = 0 when A finds thatchannel is free, it senddata ABt = 0t = B find channel is bu

28、sy, thenstop sending data STOPt = 2 A detectedcollisionSTOPABone directonpropagation delay 31important properties The ethernet applying CSMA/CD can not carriy out full duplex communication . After each station sent out data, there is a range of time, during this time, collision can occur. This uncer

29、tainty makes the average traffic of whole ethernet far less than its maximum data rate. 32Contention timeAfter 2 at most , The first station can know if collision occur when it completes sending data. The round trip end to end propagation delay 2 is called contention time or collision window.If coll

30、ision is not detected after contention time, we can be sure there is no collision during the data sending. 33The length of contention time It is 51.2 s for ethernet .For a 10 Mb/s ethernet,512 bits(64 bytes) can be sent out during the contention time.For ethernet , when a station sends data , if fro

31、nt 64 bytes data has been sent out successfully, then later data can not be collided. 34The shortest valid frame lengthIf collision occurs ,it must be in the range of front 64 bytes data. Station stops sending data when collision is detected, so data sent must be less than 64 bytes. Ethernet specifi

32、es the shortest valid frame length 64 bytes, the frame whose length is less than 64 bytes is considered as invalid frame resulting from collision .35Enforcing collision When a station is sending data, if collision is detected, it stops sending data , besides,it must send jamming signal informing oth

33、er stations that collision occus.36data frameJamming signalTJJamming siganl ABTBt sends dataB A detectscollision collision beginsThe timethat channelis occupiedA sends dataIn fact B can also detect collision,and stops sending data frame,besides, sending jamming signal。For the sake of simplicity，A st

34、ation sending jamming signal is only shown.37CSMA with Collision DetectionCSMA/CD can be in one of three states: contention, transmission, or idle.CSMA WITH COLLISIONS DETECTION:When a station detects a collision, it stops sending, even if in mid-frame. Waits a random time and then tries again.38Wha

35、t is contention interval - how long must station wait after it sends until it knows it got control of the channel? Its twice the time to travel to the furthest station.A begins to transmit at t=0ABB begins to transmit at t= tprop-B detectscollision at t= tpropABABA detectsCollision at t= 2tprop-CSMA

36、/CD39Wireless LAN ProtocolsA wireless LAN. (a) A transmitting. (b) B transmitting.40Wireless LAN Protocols (2)The MACA protocol. (a) A sending an RTS to B.(b) B responding with a CTS to A. 414.3 Ethernet - IEEE802.3Ethernet CablingManchester EncodingThe Ethernet MAC Sublayer ProtocolThe Binary Expon

37、ential Backoff AlgorithmEthernet PerformanceSwitched EthernetFast EthernetGigabit EthernetIEEE 802.2: Logical Link ControlRetrospective on Ethernet42IEEE 802 FamilyPHYData Link802.2 Logical Link Control802.1Management.802.16BroadbandWireless802.15PANBluetooth802.11WirelessLAN802.3CSMA/CDLANMedia Acc

38、ess ControlPhysical Layer Specifications802.1 MAC Bridges(1D,1Q)802.1D, Standard for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges. 802.1F, IEEE Standards for Local and Metropolitan Area Networks: Common Definitions and Procedures for IEEE 802 Management Information. 802.1

39、Q, IEEE Standards for Local and Metropolitan Area Networks: Virtual Bridged Local Area Networks 802-2001(former 1a)Overview & Architecture43Why Ethernet survived from all IEEE 802 standards?“Dominant” LAN technology: Cheap $20 for 100Mbs!First widely used LAN technologySimpler, cheaper than token LA

40、Ns and ATMKept up with speed race: 10, 100, 1000 MbpsMetcalfes Ethernetsketch44Ethernet CablingThe most common kinds of Ethernet cabling. 10Base5 means that it operates at 10Mbps, uses baseband signaling and can support segments of up to 500 meters.45IEEE 802.3 Family StandardsyearProtocolstandardMe

41、dium198210BASE5(DIX)802.3Thick coax198510BASE2802.3aThin coax199010BASE-T802.3iUTP199310BASE-F802.3jFiber Optics1995100BASE-T802.3u2 pairs of Category 5 UTP 1997Full Duplex802.3x19981000BASE-X802.3zFiber, Shielded TP19991000BASE-T802.3ab4 pair of Category 5 UTP 200210GBASE-X802.3aeFiber46Ethernet Ca

42、blingThree kinds of Ethernet cabling. (a) 10Base5, (b) 10Base2, (c) 10Base-T.47Ethernet CablingCable topologies. (a) Linear, (b) Spine, (c) Tree, (d) Segmented.48RepeaterA repeater is a physical layer device. It receives, amplifies (regenerates), and retransmits signals in both directions. As far as

43、 the software is concerned, a series of cable segments connected by repeaters is no different from a single cable (except for some delay introduced by the repeaters). A system may contain multiple cable segments and multiple repeaters, but no two transceivers may be more than 2.5 km apart and no pat

44、h between any two transceivers may traverse more than 4 repeaters. 49EncodingLife would be easy if:binary 0 = 0 voltsbinary 1 = 5 volts But theres no way to distinguish a 0 from nothing-happening. Need to know when is middle of bit WITHOUT a clock. 50Manchester Encoding(a) Binary encoding, (b) Manch

45、ester encoding, (c) Differential Manchester encoding.51Ethernet MAC Sublayer ProtocolFrame formats. (a) DIX Ethernet, (b) IEEE 802.3.52Ethernet MAC Sublayer ProtocolPacket Definition: Preamble = 7 bytes of 10101010 Start = 1 byte of 10101011 Destination = 6 bytes of MAC address multicast = sending t

46、o a group of stations. broadcast = (destination = all 1s) to all stations on network Source = 6 bytes of MAC address Length = number of bytes of data Data = comes down from network layer(=1500 B) Pad = ensures 64 bytes from destination address through checksum. checksum = 4 bytes of CRC.53Ethernet M

47、AC Sublayer ProtocolWhen a transceiver detects a collision, it truncates the current frame, which means that stray bits appear on the cable all the time. To make it easier to distinguish valid frames from garbage, Ethernet requires that there being a min frame lengthThe pad ensures transmission take

48、s enough time so its still being sent when the first bit reaches the destination. The frame needs to still be going out when the noise burst from another stations collision detection gets back to the sender.For a 10Mbps LAN, the round-trip time is nearly 50us in the worst case. A bit takes 100ns, so

49、 500 bits is the smallest frame that is guaranteed to work, for safety, this number was rounded to 512 bits or 64 bytes.54Ethernet MAC Sublayer Protocol 55The Binary Exponential Backoff AlgorithmAdapter doesnt transmit if it senses that some other adapter is transmitting, that is, carrier senseTrans

50、mitting adapter aborts when it senses that another adapter is transmitting, that is, collision detectionBefore attempting a retransmission, adapter waits a random time, that is, random access56The Binary Exponential Backoff Algorithm1. Adaptor gets datagram and creates frame2. If adapter senses chan

51、nel idle, it starts to transmit frame. If it senses channel busy, waits until channel idle and then transmits3. If adapter transmits entire frame without detecting another transmission, the adapter is done with frame !4. If adapter detects another transmission while transmitting, aborts and sends ja

52、m signal(48-bit)5. After aborting, adapter enters exponential backoff: after the mth collision, adapter chooses a K at random from 0,1,2,2m-1. Adapter waits K*512 bit times and returns to Step 257The Binary Exponential Backoff AlgorithmAfter a collision, station waits 0 or 1 slot. If it collides aga

53、in while doing this send, it picks a time of 0,1,2,3 slots. If again it collides the wait is 0 to 23 -1 times. The frozen Max time is 210 -1 (or equal to 10 collisions) . After 16 collisions, an error is reported.Slot is determined by the worst case times; 500 meters X 4 repeaters = 512 bit times =

54、51.2 sec .As the network speed goes up, the minimum frame length must go up or the maximum cable length must come down, proportionally.58IEEE Standard 802 PerformanceNote that channel efficiency depends on F - frame length, B - network bandwidth, L - cable length c - speed of signal propagation e -

55、optimal number of contention slots per frame. (512 bits = 64 bytes means a 64 byte frame has value = 1.) BUT, this is not the optimal value. 1channel efficiency = - 1 + 2 B L e / c F59IEEE Standard 802 PerformanceNote: Efforts focus on improving both B and L, but both of which will decrease efficien

56、cy for a given frame size. People want high bandwidth over long distances, which suggests that Ethernet implemented in this manner may not be the best system for these applications. So we will see switched Ethernet.Note on traffic patterns: arrivals are not Poisson, but self-similar. This means that

57、 fluctuations occur on any observation scale (kind of like fractals.)60Ethernet PerformanceEfficiency of Ethernet at 10 Mbps with 512-bit slot times.61Switched EthernetA simple example of switched Ethernet.62Switched EthernetUses 10Base-T to each of the hosts. And a high speed backplane between the

58、connectors. Works because the assumption is that many requests can be routed within the switch. Relieves congestion on the hub.Routing -Local (on-switch) destinations are sent there directly. Off-switch are sent to the backplane.Collision Detection - The connections on the switch form their own LAN

59、and do collision handling as weve just seen. Or the switch buffers the transmission and ensures no collisions occur.63Fast Ethernet(802.3u), 1995The original fast Ethernet cabling.KISS：Keep It Simple， Stupid。All fast Ethernet use hubs and switches.64100Base-TXCategory 5 wiring2 twisted pairs per sta

60、tionThe wires can handle clock rates of 125MHz, one to the hub and one from it.Binary coding is 4B/5B (125MHz*4/5=100MHz)Half-duplex in a hub (standard CSMA/CD)Full-duplex in a switch (buffered and highs-peed backplane switching)65Gigabit Ethernet(802.3z)Point-to-point configurationA two-station Eth