MIT 6.02 DRAFT Lecture NotesFall 2010 (Last update: October 18, 2010)Comments, questions or bug reports?Please contact [email protected] 10Sharing a Common Medium:Media Access ProtocolsThese are the lecture notes for Lectures 10 and 11 in Fall 2010.In this course so far, we have studied various techniques to develop a point-to-pointlink between two nodes communicating over a channel. The link includes techniques to:synchronize the receiver with the sender; ensure that there are enough transitions betweenvoltage levels (e.g., using 8b/10b encoding); to cope with inter-symbol interference andnoise; and to use channel coding to correct and detect bit errors.There are many communication channels, notably radio (wireless) and certain kindsof wired links (coaxial cables), where multiple nodes can all be connected and hear eachother’s transmissions (either perfectly or to varying degrees). The next few lectures ad-dress the fundamental question of how such a common communication channel—alsocalled a shared medium—can be shared between the different nodes.We will study two fundamental ways of sharing a medium: time sharing and frequencysharing. The idea in time sharing is to have the nodes coordinate with each other to divideup the access to the medium one at a time, in some fashion. The idea in frequency sharingis to divide up the frequency range available between the different transmitting nodes in away that there is little or no interference between concurrently transmitting nodes.This lecture and the next one focus on approaches to time sharing. We will investigatetwo common ways: time division multiple access, or TDMA, and contention protocols, a fullydistributed solution to the problem that is commonly used in many wireless networkstoday. The subsequent lectures discuss the technical ideas behind frequency sharing, par-ticularly frequency division muliplexing.These schemes are usually implemented as communication protocols. The term protocolrefers to the rules that govern what each node is allowed to do and how it should oper-ate. Protocols capture the “rules of engagement” that nodes must follow, so that they cancollectively obtain good performance. Because these sharing schemes define how multiplenodes should control their access to a shared medium, they are termed media access (MAC)protocols or multiple access protocols.Of particular interest to us are contention protocols, so called because the nodes contend12LECTURE 10. SHARING A COMMON MEDIUM:MEDIA ACCESS PROTO CO LSFigure 10-1: The locations of some of the Alohanet’s original ground stations are shown in light bluemarkers.with each other for the medium without pre-arranging a schedule that determines whoshould transmit when, or a frequency reservation that guarantees little or no interference.These protocols operate in laissez faire fashion: nodes get to send according to their ownvolition without any external agent telling them what to do.We will assume that any message is broken up into a set of one or more packets, and anode attempts to send each packet separately over the shared medium.� 10.1 Examples of Shared MediaSatellite communications. Perhaps the first example of a shared-medium network de-ployed for data communication was a satellite network: the Alohanet in Hawaii. The Alo-hanet was designed by a team led by Norm Abramson in the 1960s at the University ofHawaii as a way to connect computers in the different islands together (Figure 10-1). Acomputer on the satellite functioned as a switch to provide connectivity between the nodeson the islands; any packet between the islands had to be first sent over the uplink to theswitch,1and from there over the downlink to the desired destination. Both directions usedradio communication and the medium was shared. Eventually, this satellite network wasconnected to the ARPANET (the precursor to today’s Internet).Such satellite networks continue to be used today in various parts of the world, andthey are perhaps the most common (though expensive) way to obtain connectivity in thehigh seas and other remote regions of the world. Figure 10-2 shows the schematic of sucha network connecting islands in the Pacific Ocean and used for teleconferencing.In these satellite networks, the downlink usually runs over a different frequency bandfrom the uplinks, which all share the same frequency band. The different uplinks, however,need to be shared by different concurrent communications from the ground stations to thesatellite.1We will study switches in more detail in later lectures.SECTION 10.1. EXAMPLES OF SHARED MEDIA 3Figure 10-2: A satellite network. The “uplinks” from the ground stations to the satellite form a sharedmedium. (Picture from http://vidconf.net/)Wireless data networks. The most common example of a shared communicationmedium today, and one that is only increasing in popularity, uses radio. Examples in-clude cellular wireless networks (including standards like EDGE, 3G, and 4G), wirelessLANs (such as 802.11, the WiFi standard), and various other forms of radio-based com-munication. Broadcast is an inherent property of radio communication, especially withso-called omni-directional antennas, which radiate energy in all (or many) different direc-tions. However, radio broadcast isn’t perfect because of interference and the presence ofobstacles on certain paths, so different nodes may correctly receive different parts of anygiven transmission. This reception is probabilistic and the underlying random processesthat generate bit errors are hard to model.Shared bus networks. An example of a wired shared medium is Ethernet, which whenit was first developed (and for many years after) used a shared cable to which multiplenodes could be connected. Any packet sent over the Ethernet could be heard by all stationsconnected physically to the network, forming a perfect shared broadcast medium. If twoor more nodes sent packets that overlapped in time, both packets ended up being garbledand received in error.Over-the-air radio and television. Even before data communication, many countries inthe world had (and of course still have) radio and television, broadcast stations. Here, arelatively small number of transmitters share a frequency range to deliver radio or televi-sion content. Because each station was assumed to be active most of the time, the naturalapproach to sharing is to divide up the frequency range into smaller sub-ranges and allo-cate each sub-range