Media Access Control

 The bandwidth Delay Product determines the capacity of a "Pipe" in bits. Take this case:

The propagation delay is roughly 5μs/km. So the end to end delay is 5km * 5μs/km = 25μs. The Bandwidth-delay product is 1Mb/s * 25μs. 

Consider a channel with one-way delay of D = 250 msec, bandwidth B = 50kbps. The Bandwidth propagation is 2 * B * D, using packet sizes of s bits. Link utilization is fraction of time that sender is not blocked. For example, using stop and wait link utilization <= S/(2BD).

For stop-and-weight, the advantage is the receiver buffer size is only as large as one packet. Off the shelf switches are limited in their buffers. You might have a switch connected to 14 servers in one rack and you have the servers below it, they all connect with cables to the switch, the switch only has ~8KB to serve the flow of packets coming to the switch. The trade off for stop-and-wait is that I won't need a large buffer size. The thing is that the utilization of the network is going to grow large.

Now we are talking about the sliding window protocols. We have a window at the sender and receiver. The sender window identifies the packets from the range of packets that can be transmitted right now/sent right now. The larger the sender window, the more packets that the sender can send immediately. On the other hand, the receiver window defines the packets that the receiver is expecting now, the packets that are not expected will be dropped and not placed in the buffer. IF we want each side to be sender/receiver, then each side is going to maintain a sender or receiver window. For sliding window protocols, each end does not send one packet and wait for acknowledgement, instead each side contains sender and receiver window. 

The sending window corresponds to the set of frames that can be sent without waiting for an ack, and receiving window corresponds to the set of frames that can be accepted and buffered before passing. In sending window, we need to buffer for possible retransmission, and the windows can dynamically vary to accommodate next acknowledgements. In receiving window, the window advances with in-order arrivals, and we need to keep a good amount of buffer space for arrivals. 

The flow control protocols that rely on sliding window is Go-Back-N (used in data centers) and selective repeat. Stop-and-wait is inefficient for long links (w = 1), and best window depends on bandwidth delay. Again we want w = 2BD. 

Let's discuss Go-Back-N, since we want our buffer size to be small. In Go-Back-N, the receiver only accepts or acknowledges frames that arrive in order and discard frames that follow a mission/errored frame. Sender times out and resends all outstanding frames. 

The buffer size is small so this will be useful if I have shallow buffers. This corresponds to receive window of 1 but it performs poorly when error rate is high. 

So that's Go-Back-N. Now let's talk about the selective repeat. Cumulative Acknowledgement is acknowledging the sequence number and everything before it. Here, 3, 4, and 5 were buffered (and not dropped). Negative ACK causes a sender retransmission of missing frame before a timeout resends window. 

There is more action here than the other Go-Back-N. In order to avoid maintaining infinite size buffers, the buffer size capacity is limited to w packets numbered between 0 and w - 1 and they shouldn't be 0 and w - 1. When a receiver receives the packet it will buffer and send an acknowledgement to a sender.

Now if s = 8 and w = 7 then we have a new receive window overlapping the old window, and retransmits ambiguous signals. So then we cannot send enough. Some of the packets will be ignored because the receiver packets will not accommodate. ender would eventually time out and retransmit, but what should the receiver do? The receiver should slide its window. 

Now if s = 8 and w = 4, we have enough sequence numbers, but receiver is always waiting on a packet with a buffer. New receive window and old window doesn't overlap. So the receiver will slide the window. Remember flow control can be applied in Layer 2, (Go-Back-N are used in data centers). There are setups where these are also used in different layers. Doing flow control will enable the 2 ends to regulate the rate so that the sender does not overwhelm the receiver and react within packet losses. So, there is some complexity in the core if you did hop by hop. I can do security, hop-by-hop, end-to-end, or thorough a secure tunnel. 

Let's now go over media access control. It's kind of an interesting problem to think about. Media Access Control is the same as MAC protocols. There could be wireless channels, you can be sending web requests at the same time, so your requests may collide.  There are cases is cellular technology where you share the channel, so there is a chance that your signals will collide with other. Switch ethernet doesn't have shared media, but in the old days we had classic ethernet where we have one shared cable where multiple devices are sharing. It is quite a popular technology. 

When we get into cases, how do we deal with it? We have talked about one possible solution, the static solution we have seen before called multiplexing. Before we start our exchange you are given a frequency range to use different than what other devices are using (Frequency Division Multiplexing). We also use time division multiplexing. We also talk about CDMA (each device get the code same time same frequency range without interfering). 

We need the hardware to tune in to specific channel and do this coordination with brain/controller requires specific channel. In many cases, you cannot do multiplexing and you want to enable these devices to contend (compete for channel access). We're thinking with media access protocols about dynamic solutions, allowing devices getting access to media even though media is shared among multiple devices. How do we allow these devices to contend over a shared channel? Point to Point links exist on the internet core and on the edge as well. The objective of Media Access Protocols is to reduce the overall chance of collision. 

There are 2 solutions - static solutions (multiplexing, FM radio, etc.) and dynamic solutions, which we will discuss here. Static solutions has a disadvantage. If I gave a time slot and if we don't use it, we lose it. Such is the art of contention. Dynamic solutions don't have this problem. The dynamic solution allocates the channel to a user when he needs it, N times as efficient for N users as static solutions. The complexity is on deciding who gets the channel next to reduce probability of collision. 

Now, let's go over MAC, or the Media Access Control Sublayer. Notice that this depends on the channel. If I have ethernet, layer 2 is going to have some media access protocol vs speaking over wireless channel. MAC is responsibly for deciding who sends next on a multi-access channel. 

There is also a channel allocation problem. Given N users sharing a channel, we need to figure out how to allow users to access the channel while maximizing channel throughput (goodput). The goodput of a communication channel is the number of bits/sec in correct frames on the channel. Goodput is the valid/"good"/"clean" throughput. It doesn't count retransmitted byte. We want to maximize goodput.

We're gonna make some assumptions here. We assume independent traffic (each packet is not correlated to earlier or later packets). Most of the time the traffic is very steep on the internet. Many flows deal with very steep bursts of traffic (creates some correlation). MAC has single channel, observable collisions (needed for reliability), slotted time (slotting will improve performance vs continuous time) and carrier sense for collision detection. 

Let's first go through the ALOHA protocol. In pure aloha, users transmit frames whenever they have data and retry after a random time for collisions. If I have a device and you have a device, and the tower is in the middle, I send something in the middle and the tower will relay it to you. If we have 2 neighboring devices, if they transmit at the same time, the intermediate node/access point will not be able to make sense out of our signals. So, how does ALOHA work? So we retry after a random time for collision. If I have something to say, I will immediately say it. There is a chance we are going to collide, and we need to rely on acknowledgements. 

We want to do it as simple as possible since enhancements can come later. But once the number of devices grow then there is a good chance that the signals will interfere. Once we overlap, that's a collision, so none of the frames would be "good". So with ALOHA, if you have something to send, SEND. The cases that collide you can know about through acknowledgements and you can retransmit later. 

Let t be frame time. Assume new frames generated at mean rate of N frames per frame time. Stations also generate retransmissions of frames that suffered collisions. Assume new frames and retransmissions altogether generated at a mean rate of G frames per frame time G >= N. At low load, G = N. At high load, G >> N.  Throughput is the amount of data/number of bytes that were transferred over a period of time, sent over an access point. Because we know the access point of ALOHA is sitting between every device and is acting as the intermediate node. 

We will retransmit whatever frames result in a collision. Throughput counts the packets are retransmitted. Goodput doesn't. The frametime is the time to transmit the frame on the channel. The average frame time we can assume that new frames generate at a mean rate of N frames per frame. Stations also generate retransmission of frames.

We want to compute the Goodput of the ALOHA network. Let p0 be the probability of no collision when a frame is transmitted. The goodput S = G.p0. But how do we compute p0? Now how do we compute this probability? There is a key observation. Looking at certain frames, here notice that t is the frame time. Collisions happen when other users transmit during a vulnerable period that is twice the frame time. p0 is probability that no frame transmission is within 2t. How do we compute this? 

Any transmission before t0 and after t0 + 2t I don't expect the collision. Now let's discuss Poisson Distribution. It's a discrete probability distribution that expresses probability of a given number of events occurring in a fixed interval of time if these events occur with a known average rate λ.

Pr[k] = λ^k . e ^ -λ/(k!)

P0 is the probability that no frame will be transmitted within 2t amount of time. We know we have G frames being transmitted per frame time. Now, we are talking about 2t period of time so the number of frames that will be generated in 2t period of time is 2G. So probability of no frame being transmitted during a period of time is:

So now the next graph will plot the goodput with certain values of G. Peak throughput is when G = 0.5. The Goodput that you are going to get out of ALOHANet is not going to exceed 18% whatever you do. 

So, max channel utilization is 18%. To improve on this, remember the vulnerable period is 2t seconds? We will try to shrink this vulnerable period. The idea is to only transmit the signal at the beginning of a clock/transmission slot. I don't expect the transmission to start someone between the ticks then overlap the new tick. Vulnerable period would only be t seconds in slotted aloha and will be 2t seconds in pure aloha. Let's see how this manifests itself. 

Slotted ALOHA is when users are allowed to transmit frames at beginning of a slot. Synchronization can be an issue and it reduces the vulnerable period to only t. So the p0, probability no frame will be transmitted within T amount of time is 

resulting in a goodput (S) of G.e^-G. This is TWICE as efficient as pure aloha, and the efficiency is up to 1/e (37%) for random traffic models. 

CSMA is Carrier Sense Multiple Access. This is another MAC protocol that we are going to discuss. Let's talk about different systems. CSMA term is clear talking about multiple devices trying to access the shared channel. Carrier is communication channel, carrier sense is what you are sensing. In carrier channel you have to figure out if another signal is trying to speak on the channel. There are few variants. 1 persistent(greedy) sends as soon as idle. Non-persistent waits a random time then tries again. p-persistent sends with probability p when idle (this applies to slotted channels mainly). These are variations on what to do if the channel is busy. Being polite is you might may have to wait a long time before transmitting your frame. Delay is longer but you are trying to reduce the chance of collision. 

1-persistent is greedy is where you are eager to transmit your frame. Non-persistent is the collide approach. I'll step back and let someone else transmit and take a random amount of time before trying again. 1 persistent is immediately transmit when channel is open. I between we have p persistent. Time is slotted here. 

Let's talk about the eager one first. A 1-persistent device is going to listen to the channel to see if anyone else is transmitting. If channel is idle then transmit frame. Else wait until channel is empty then transmit frame. If collision happens then wait for random period then start over. What is the problem with this? It leads to collision because everyone is way too aggressive to transmit. This is CSMA so it requires an antenna to receive and an antenna to send, so you added an extra feature, and enable devices to snoop on the channel before transmitting. 

In non-persistent CSMA, we listen to the channel to see if anyone else is transmitting. If the channel is idle, then transmit the frame. Else, wait for a random period and start all over. If the collision happens, then wait for a random period, then start all over. We ONLY transmit the frame if the channel is IDLE. You get better channel efficiency since your throughput S will be higher, especially for higher values of G. You are trading the goodput of channel for device delays. There will be a lot of questions about this tradeoff. 

1-persistent will get better throughput because less collision but longer delays. P-persistent CSMA is trying to get better throughput and lower delays at the same time. It has its own way of doing things. When a station has something to send, it's going to listen to the channel. We listen to channel to see if anyone else is transmitting. If channel is idle then transmit frame with probability p. Start all over at next slot with probability 1 - p. If the channel is not idle, wait for a random period, and start all over. If a collision happens, wait for a random period, then start all over. By playing with a value we want to know the appropriate p to mess around with the system. CSMA outperforms ALOHA, and being less persistent is better under high load. 

Why does 1 persistent do better than non-persistent when G is low, and vice-versa? Being greedy will pay off if there is no load, but adding more devices will result in more competition then everything will contend simultaneously leading to collisions. 0.01, 0.1, 0.5 that's pretty much p, transmit with a probability p. It's like also being polite. 0.1 persistent at low utilization will work like 0.01 persistent, then peak up at some point, then drifts down. Why is this the case? This might be midterm exam question. 

CSMA improvement is to detect/abort collisions, since this is CSMA/CD is Collision Detection. This is protocol for ethernet. When a station has data to send, it will listen to channel. If the channel is idle then we will transmit the frame immediately. We will detect collision. If the collision detected then abort the transmission, wait for a random period of time, and start all over. Else if the channel isn't idle, wait for random period and start all over. Ethernet frames are padded to get to the minimum size of an ethernet frame. I will assume channel is free and frame will make it. If a time has passed without hearing a collision, then I will continue the transmission of this frame. You're listening to see if what you hear is matching with what has transmitted. If you heard a collision this means that someone on the other end of the cable has decided to transmit on its own. 

The other way is to have a token and pass it between the devices, and the other devices cannot be transmit. With collision free protocols, we are going to aim for avoiding collisions altogether. This arrangement takes time and a portion of the chanenl. Just keep in mind that collision contention protocols have low delay and low channel efficiency and a high rate. Assume we have N stations. 

ALOHA and CSMA are contention protocols (they allow collisions). There's a low delay at low load, and channel inefficiency at high load. They are both contention-based protocols, meaning devices that want to use the channel for transmission and receiving will compete. Remember the advantage and disadvantage of contention-based protocols, since we'll come back to that later. If you follow, we should not get into the collision at all. But we also have advantages and disadvantages. 

 Now, let's talk about collision-free protocols. They prevent the possibility of collision. How do you get to that? The idea is to prepare a schedule. We maybe create a bitmap. We all snoop off channel and figure out if there is time. We can also have a token and pass it to the devices and the device that can transmit is the device which has the tokens. The other devices should not transmit.  Collisions reduce goodput and make the time to send a frame variable. Collision free protocol resolve the contention for the channel without any collisions. 

A system should know how many station exists. There are N stations each programmed with a unique address from 0 to N-1. There are setups in which you have a large number of devices. At least I know how many devices would be used in the system so I can arrange more. Assumption 1 is we want to know devices in the system, other thing is propagation delay. 

Example number 1 is the bitmap protocol. So we have in the beginning a small fram that has 8 slots. I should be the only one who can set a particular slot. So contention slots will appear periodically, and devices should know. In a bitmap protocol, the senders make a reservation to send before sending. They first set a bit in contention slot if that have data. Then they send in turn. 

Let's evaluate efficiency. Assume all the frames have the same size at low load. The channel efficiency is S/(S + N) where S is frame size and N is the overhead. Efficiency would depend on size of frame and number of bits inside of the contention slot. It's better if you send larger frames. At a high load, for each N frames, there is an overhead of N bits in a contention slot. At high load the N stations are willing to transmit. So we are sending S bits per channel. Efficiency is NS/(NS + N). 

Clearly, the efficiency is better at high load. I will wait at least for N contention slots will go through. The higher the number of devices, the more I have to wait. ALOHA at low load will purely send immediately, won't wait for N contention slots. So, let's talk about delays. At high load, the channel efficiency becomes high because there is no more contention. 

At low load how long are we going to wait? When ready to send, the "current" slot will be somewhere in the middle of the bitmap. We will have to wait for the N contention slots to pass and the new contention sequences to show up, so we will have to wait for N/2 + N = 1.5 N contention slots before transmitting the frame for low number station. For high number station, on average we need to wait for N/2 = 0.5N (if N = 8 roughly we will show around fourth bit) contention slots beofre transmitting the frame. We can get lucky and find our reservation slots right away. The average delay is (1.5N + 0.5N)/2 = N contention slots. You average both the luck and unlucky slots. You would be lucky if your station number is higher and unlucky if station number is lower. Channel efficiency would be better with more devices since the impact of the contention slots will be minimal. 

High load means that there are many devices that would like to transmit. How long would we have to wait? On average, we are going to have to wait for n contention slots (whether at high load or low load!) But then there are other stations that want to transmit, and they would be transmitted also in order. Worst case scenario we need to wait (N - 1).S contention slots before trransmitting a frame (time to wait for other frames to be transmitted). Average delay = (N) + (N - 1).S contention /bit slots. 

So the delay seems to grow definitely, however this high load delay when you compare to contention-based protocols. Contention based protocol  (low delay at low load, but low channel efficiency at high load) has a advantage at low load while contention free protocols (at high load better channel efficiency, but low load you have to wait for some period of time).  has an advantage at high load.

Now let's go over the token ring. In the token ring, the token is sent round ring defining the sending order. Station ith token may send a frame before passing. The idea can also be used without a ring, too. When the device has the token in hand, we can start the translation. Toekn sent round ring defines the sending order. The station with token may send a frame before passing. The idea can be used without a ring as well (token bus is an example). 

Token passes efficiency in a way very similar to Bitmap. We have no bias against low numbered stations because all of the devices will take turns. The only thing is that there will be delay (token between the devices). We would go with contention free protocol in high load (to avoid collision so channel efficiency will be high) and we used contention-based protocols with low loads (can compromise with efficiency there). 

Issue is Bitmap and token passing do not scale well to cases with large number of stations. The solution for this is binary countdown (contention free, but aims for better scalability). Instead of using the bitmap protocol (N Bits) we are going to use Log2N bits. It offers some scalability because you grow in number of contention slots. The way it works is that each device has an id, and we assume synchronization transmitted at same time. Stations send their address in teh contention slot (log N bits instead of N bits). We contend, one device will win, and this device ill transmit. The medium ORs bits, the stations give up when they send a "0" but see a "1". Station that sees its full address is the next to send. 

At low load, we will be costing some delay. At high load, we will go for collision-free protocols. Now we talk about contention-based protocols and contention-free protocols. 

Now we want best of both worlds. At high load, we get something similar to contention free protocols (efficiency) and contention based protocols at low load (low delay). High efficiency at high load, low efficiency at low load. 

If I have very high load, everyone wants to transmit, turn into contention free. If I realize if there is not much to that, in this case, I'll make them contend, since contention is good at low loads. We are going to control the size of the device that will be contended. As the number of stations increases, the channel efficiency will come down because the probability of getting your frame through is going to be lower. At low load large groups will contend and at high load small groups will contend. We want to divide stations into groups within which only a very small number are likely to want to send. 

Each internal node in a binary tree are stations. The binary Tree divides stations into STA groups. STAs are tree leaves. Each internal node corresponds to a group of STAs. 

Here is Adaptive Tree Walk. Group 1 will contend first. They get an order. Everyone will start a transmit if they have a frame to transmit. Some devices do not want to transmit. So, group 1 will contend. If no one wants to transmit, we're done. If one device wants to transmit, we're good to go. However, if we get into a collision, we go through all of the nodes of the tree in a depth-first fashion, using Depth-First Search. Assume that there was a collision. If we move to group 2 next, contend.  I move to group 4, contend. 

If there is a collision, go to A, then B. Once I'm done with 4, I move to 5. Contend. If there is no collision at all, I'm done with group 5. Finally, I move to group 3 and do the same. Big picture is that I'm trying to be optimistic. Maybe the load is low, so I make them collision. Once I do realize there is a collision, I start to split it. In collision we reduce contending group size doing depth-first search. If one STA is able to transmit a frame- then we continue DFS after skipping all STAs corresponding to node. We do the same thing if no STA attempts to transmit. If A, E, F are ready to transmit, there is a collision since A, E, F are part of group 1 and want to transmit at the same time.

 I only have 3 stations who want to transmit. E will be transmitted first, then F will transmit, then Group 7 will be tested/pulled. This adaptive tree approach is trying to reduce the size of the transmitting devices. With Adaptive Tree walk, we get best of both worlds. There might be some overhead since we are visiting multiple groups. Once you get to collision you know that many of the internal nodes will have collisions. So it transmits using depth-first search based on the position in the tree.