Protocols

Question 1

Simple Stop and Wait protocol

Answer 1

Is a data link layer protocol for the transmission of frames over noiseless channels
Provides unidirectional data transmission with flow control

Question 2

Simple Stop and Wait protocol operation

Answer 2

Sender sends 1 data frame
Receiver recieves the data frame and sends an acknowledgement(ACK)
Sender receives ACK and sends the next data frame

Question 3

Simple Stop and Wait protocol disadvantages

Answer 3

Slow (sender has to wait for ACK before sending next frame)
Cannot be used in noisy channel

Question 4

Simple Stop and Wait protocol problems

Answer 4

1. Damaged frame: receiver sends ACK on success or NAK on damaged frame. Then sender can retransmit
2. Lost data frame: if frame gets lost during transfer, we go into deadlock. Receiver is waiting for frame to arrive. Sender is waiting for ACK to arrive.
   Prevent by: sender sets a timeout interval. if it doesn’t get an ACK within this timeframe, sender will assume data frame was lost and will re-transmit
3. Lost ACK: if ACK is lost, sender will detect a timeout and re-trasmit the same frame, meaning the receiver will get a duplicate frame.
   Solve by: sender attaches a sequence number to each frame and receiver will check this on arrival and will discard any duplicates.

Question 5

Simple Stop and Wait protocol. Why is the length of the timeout interval important?

Answer 5

If it is too long, the sender will wait unnecessarily long before retransmission, causing the link to be idle
if it is too short, the protocol may fail due to the occurrence of duplicate ACKs
Can be solved by including the sequence number of the acknowledged frame in the ACK itself.
However all frames are still sent twice, causing 50% loss of transmission capacity

Question 6

ARQ(Automatic repeat ReQuest) protocols

Answer 6

Group of error - control protocols incorporated with stop and wait flow control protocol for transmission of data over noisy or unreliable networks
Provide automatic retransmission of frames that are corrupted or lost during transmission

Question 7

Stop and wait ARQ protocol operation

Answer 7

The sender sends the frame(keeps a copy of it) with a unique sequence number, then waits for ACK from the receiver
If a timeout occurs(frame or ACK is lost), the frame is retransmitted again
Frames with CRC errors are rejected by the receiver and NAK is sent
Duplicate frames or ACKs are also rejected

Question 8

Piggy-backing

Answer 8

similar to stop and wait ARQ, but data frame sent by a receiver carry acknowledgements of its received frames
advs:
better channel utilisation(fewer bits transmitted), less computation by the hosts(less work to pack, unpack and check the extra frames)
disadvs:
if the receiver waits too long to send a piggybacked ack, the sender will timeout and retransmit the frame

should only be a brief wait, if no data is available, the ACK is sent on its own. This requires a timeout from the server

Question 9

Go-Back N ARQ protocol

Answer 9

Allows for sending N frames before receiving the ack for the first frame
Frames are sequentially numbered
uses concept of sliding windows at the sender and receiver.
Sender window size is greater than 1
Receiver window size is always 1
Receiver only accepts frames that arrive in order
On error, receiver discards all frames that follow a missing/errored frame. sender continues unaware until timeout. then resends all frames starting from that frame
Min range of sequence numbers that must be used is window size +1

Question 10

Selective repeat ARQ protocol

Answer 10

Also provides for sending N frames before receiving ACK for first time
sender window size is greater than 1
receiver window is greater than 1
Receiever accepts frames anywhere in the receive window
On error, the receiver sends NAK. Receiver buffers frames. Sender continues unaware until NAK is received. Sender re sends corrupted/lost frame only.
Utilisation is much better than go back N if errors are common
Min range of sequence numbers that must be used is window size *2

Question 11

Differences between Go back N and selective repeat ARQ protocols

Answer 11

Go Back N: the minimum range of sequence numbers that must be used for it to work properly is the window size +1
Selective repeat: the minimum range of sequence numbers that must be used for it to work properly is the window size*2

Go back N: when a NAK is received, the sender will continue to send the next frames until a timeout occurs and then will re send all the frames starting from the corrupted/lost frame
Selective repeat: when a NAK is received, the sender will re-send the corrupted/lost frame only

Go back N: the receiver will only accept frames sent in order
Selective repeat: the receiver will accept frames in any order

Question 12

ALOHA protocols

Answer 12

Used on satellite channels

Question 13

Pure ALOHA

Answer 13

Hosts transmit whenever they want, and colliding frames are destroyed
If a frame was destroyed, the sender just waits a random amount of time and sends again
Utilisation is bad under high load(18%)
Hosts cant listen to channel

Question 14

Slotted ALOHA

Answer 14

Divide the time up into discrete intervals, each interval corresponding to one frame
Hosts can only transmit at the start of each time slot
This requires one special station to emit a “pip” at the start of each interval. for all others to synchronise. This is double the efficiency of pure ALOHA at 37%
Hosts cant listen to channel

Question 15

CSMA(carrier sense multiple access) protocol

Answer 15

Hosts listen for the presence of a carrier signal and act accordingly
Only makes sense on systems with short delays such as LANs

Question 16

CSMA 1-persistant protocol

Answer 16

When a host has data to send, it first listens to the channel to see if anyone else is transmitting
If the channel is busy, the host keeps listening until it becomes idle
When the host detects an idle channel, it immediately transmits a complete frame with a probability of 1
If the frame is damaged, the host waits a random amount of time and starts all over again

Better than ALOHA, however if 2 hosts are waiting, both will detect that it has become idle and then transmit simultaneously

Question 17

CSMA non-persistent protocol

Answer 17

less greedy than 1 persistant

When a host has data to send, it first listens to the channel to see if anyone else is transmitting
When the host detects an idle channel, it immediately transmits a complete frame
When the sending host detects that the channel is busy, it waits a random period of time and then repeats the algorithm

leads to better utilisation, especially under high loads, but longer delays than 1 - persistent CSMA

Question 18

CSMA p-persistent protocol

Answer 18

This protocol applies to ‘slotted’ channels. One slot equals one frame transmission time - there is no pip

When a host becomes ready to send, it senses the channel. If it is idle, it transmits with a probability p (therefore the probability that it defers transmission until the next slot is q = 1-p)
If that slot is also idle, it either transmits or defers again, with probabilities p and q respectively
If a slot is busy, it waits a random amount of time and starts again

Question 19

CSMA/CD (collision detection) protocol

Answer 19

in other CSMA and ALOHA protocols, a host sends a complete frame then decides if it was damaged.

A host aborts its transmission as soon as it detects a collision, it waits a random period of time and then tries again
quickly terminating damaged frames saves time and bandwidth
widely used on LANs and classic Ethernet

Question 20

CSMA/CD protocol. Why can only a host detect a collision as it happens?

Answer 20

A host uses highly special electronics that allows it to hear while it is transmitting
Frame transmission time >= Round Trip Time

Question 21

Collision free protocols

Answer 21

Channel is divided up between the hosts with each host having its own private slot
These protocols have a longer delay

Question 22

Bit map protocol

Answer 22

Following a frame transmission period, there is a short contention period which consists exactly of N small slots for the N hosts on the channel
If a host j has a frame to send, it inserts a 1 into slot j of the contention period. After all N slots have passed by, each host has complete knowledge of which hosts wish to transmit
At that point, they begin transmitting in numerical order
Since everyone agrees on who goes next, there will never be any collisions

Question 23

Limited contention protocols

Answer 23

combine the best properties of the contention and collision-free protocols.
Uses contention at low loads to provide low delay, but uses a collision-free technique at high loads to provide high channel efficiency

Question 24

Adaptive tree walk protocol

Answer 24

Divide the hosts up into groups. Only members of group j are permitted to compete for slot j.
In the first contention slot following a successful frame transmission, slot 0, all hosts are permitted to acquire the channel
If one of them does so, fine.
If there is a collision, then during the next slot, slot 1, only those hosts falling under node 2 in the tree(first sub-tree) can compete.
if one of them acquires the channel, the next slot is reserved for those hosts under node 3(second sub tree). etc

Question 25

Binary exponential back-off protocol

Answer 25

After a collision, time is divided up into discrete slots whose length is equal to the worst case round-trip propagation time on the LAN cable
After the first collision, each host independently waits either 0 or 1 slot times before trying again. If two hosts collide and each one picks the same random number(0 or 1), they will collide again
After the second collision, each one picks either 0,1,2, or 3 at random and waits that number of slot times
if a third collision occurs, then. the number of slots to wait is chosen from the interval 0 to 2^3 – 1
After 10 collisions, the number is frozen at 2^10 -1 slots
After 16 collisions, report failure to the computer. Further recovery is handled by higher layers

Question 26

MACA protocol

Answer 26

RTS(request to send). CTS(clear to send)
A wants to send data to reciever, so it sends a short RTS
B Is within range of A, it hears RTS and sends CTS to allow A to transmit. Upon receipt of the CTS A begins transmission
C is within range of A, hears RTS and keeps quiet long enough for the CTS to be transmitted back to A without conflict
D is not within range of A so cant hear RTS. But is within range of B, hears CTS and keeps quiet during the upcoming data transmission.
E hears both control messages and, like D, must be silent until the data frame is complete

MACA overcomes the hidden terminal problem but collisions can still occur